Semionline-версия задачи теории расписаний с двумя группами предметов

  • Владимир Михайлович Котов Белорусский государственный университет, пр. Независимости, 4, 220030, г. Минск, Беларусь
  • Наталья Сергеевна Богданова Гомельский государственный технический университет им. П. О. Сухого, пр. Октября, 48, 246746, г. Гомель, Беларусь https://orcid.org/0000-0003-3641-8663
DOI: https://doi.org/10.33581/2520-6508-2019-3-134-138

Аннотация

Предложен метод упаковки для задачи semionline с двумя группами предметов. Алгоритмом решения этой задачи является распределение предметов из первой группы с использованием групповой технологии, после чего применяется LS-алгоритм для назначения предметов из второй группы. Чтобы доказать оценку алгоритма, введены разные типы упаковок. В соответствии с весами предметов определены классы предметов. Предложен алгоритм распределения предметов из первой группы для получения необходимых упаковок. На втором этапе применяется алгоритм «в минимально загруженный» с наихудшей оценкой 17/9.

Биографии авторов

Владимир Михайлович Котов, Белорусский государственный университет, пр. Независимости, 4, 220030, г. Минск, Беларусь

доктор физико-математических наук, профессор; заведующий кафедрой дискретной математики и алгоритмики факультета прикладной математики и информатики

Наталья Сергеевна Богданова, Гомельский государственный технический университет им. П. О. Сухого, пр. Октября, 48, 246746, г. Гомель, Беларусь

старший преподаватель кафедры информатики факультета автоматизированных и информационных систем

Литература

  1. Kellerer H, Kotov V, Speranza MG, Tuza Z. Semi on-line algorithms for the partition problem. Operations Research Letters. 1997;21(5):235–242. DOI: 10.1016/ S0167-6377(98)00005-4.
  2. Albers S, Hellwig M. Semi-online scheduling revisited. Theoretical Computer Science. 2012;443:1– 9. DOI: 10.1016/jagm. 2012.03.031.
  3. He Y, Zhang G. Semi on-line scheduling on two identical machines. Computing. 1999;62(3):179 –187. DOI: 10.1007/s006070050020.
  4. Gabay M, Kotov V, Brauner N. Semi-online bin stretching with bunch techniques. Theoretical Computer Science. 2015;602: 103–113. DOI: 10.1016/j.tcs.2015.07.065.
  5. Kellerer H, Kotov V, Gabay M. An efficient algorithm for semi-online multiprocessor scheduling with given total processing time. Journal of Scheduling. 2015;18(6):623– 630. DOI: 10.1007/s10951-015-0430-4.
Опубликован
2019-11-20
Ключевые слова: метод упаковки, разбиение, планирование, наихудшая оценка, semionline
Как цитировать
Котов, В. М., & Богданова, Н. С. (2019). Semionline-версия задачи теории расписаний с двумя группами предметов. Журнал Белорусского государственного университета. Математика. Информатика, 3, 134-138. https://doi.org/10.33581/2520-6508-2019-3-134-138
Выпуск
№ 3 (2019): Журнал Белорусского государственного университета. Математика. Информатика
Раздел
Краткие сообщения

Copyright (c) 2019 Журнал Белорусского государственного университета. Математика. Информатика

Лицензия Creative Commons

Это произведение доступно по лицензии Creative Commons «Attribution-NonCommercial» («Атрибуция — Некоммерческое использование») 4.0 Всемирная.

Авторы, публикующиеся в данном журнале, соглашаются со следующим:

  1. Авторы сохраняют за собой авторские права на работу и предоставляют журналу право первой публикации работы на условиях лицензии Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
  2. Авторы сохраняют право заключать отдельные контрактные договоренности, касающиеся неэксклюзивного распространения версии работы в опубликованном здесь виде (например, размещение ее в институтском хранилище, публикацию в книге) со ссылкой на ее оригинальную публикацию в этом журнале.
  3. Авторы имеют право размещать их работу в интернете (например, в институтском хранилище или на персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу. (См. The Effect of Open Access).