informИнформатикаInformatics1816-03012617-6963UIIP NASBinform-8Research ArticleМАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕMATHEMATICAL MODELINGИССЛЕДОВАНИЕ СВОЙСТВ ПЛОТНЫХ РАСПИСАНИЙ ПРИ ОГРАНИЧЕННОМ ЧИСЛЕ ПРИБОРОВSTUDYING PROPERTIES OF DENSE SCHEDULES UNDER CONDITION OF LIMITED NUMBER OF SERVICE UNITSВолчковаГ. П.VolchkovaG. P.volchkovagp@mail.ruКотовВ. М.KotovV. M.kotovvm@yandex.ruБелорусский государственный университетRussian Federation201525092016016472Copyright © Волчкова Г.П., Котов В.М., 20162016Волчкова Г.П., Котов В.М.Volchkova G.P., Kotov V.M.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/8

Для задачи max Om||Cmax существует гипотеза, что в худшем случае для любого плотного расписания время завершения выполнения последней работы не более чем в 2-1/m раз превосходит время завершения в оптимальном расписании. Предлагается подход, который позволяет доказать гипотезу для случая m ≤ 9 и некоторых специальных случаев.

There is a conjecture that for any dense schedule in the problem Om||Cmax the makespan is atmost (2− 1/m) times the makespan of the optimal schedule, where “m” is the number of machines. In the paper the conjecture is proved for m ≤ 9 аnd some other special cases.

ReferencesChen, B. Approximation algorithms for three machine open shop scheduling / B. Chen, V.A. Strusevich // ORSA J. Comput. – 1993. – Vol. 5. – P. 321–326.Chen, B. Approximation algorithms for three machine open shop scheduling / B. Chen, V.A. Strusevich // ORSA J. Comput. – 1993. – Vol. 5. – P. 321–326.Волчкова, Г.П. К гипотезе о плотных open-shop расписаниях / Г.П. Волчкова // Вестник БГУ. Сер. 1.2. – 2004. – № 2. – С. 58–61.Волчкова, Г.П. К гипотезе о плотных open-shop расписаниях / Г.П. Волчкова // Вестник БГУ. Сер. 1.2. – 2004. – № 2. – С. 58–61.Волчкова, Г. П. О свойстве плотных расписаний для задачи Om||Cmax / Г.П. Волчкова // Вестник БГУ. Сер. 1.2. – 2010. – № 2. – С. 127–130.Волчкова, Г. П. О свойстве плотных расписаний для задачи Om||Cmax / Г.П. Волчкова // Вестник БГУ. Сер. 1.2. – 2010. – № 2. – С. 127–130.Open-shop dense schedules : properties and worst-case performance ratio / B. Chen [et al.] // Journal of scheduling. – 2012. – Vol. 15, no. 1. – P. 3–11.Open-shop dense schedules : properties and worst-case performance ratio / B. Chen [et al.] // Journal of scheduling. – 2012. – Vol. 15, no. 1. – P. 3–11.

The authors declare that there are no conflicts of interest present.