STUDYING PROPERTIES OF DENSE SCHEDULES UNDER CONDITION OF LIMITED NUMBER OF SERVICE UNITS
Abstract
There is a conjecture that for any dense schedule in the problem Om||Cmax the makespan is at
most (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.
About the Authors
G. P. Volchkova
Белорусский государственный университет
Russian Federation
Russian Federation
V. M. Kotov
Белорусский государственный университет
Russian Federation
Russian Federation
References
1. Chen, B. Approximation algorithms for three machine open shop scheduling / B. Chen, V.A. Strusevich // ORSA J. Comput. – 1993. – Vol. 5. – P. 321–326.
2. Волчкова, Г.П. К гипотезе о плотных open-shop расписаниях / Г.П. Волчкова // Вестник БГУ. Сер. 1.2. – 2004. – № 2. – С. 58–61.
3. Волчкова, Г. П. О свойстве плотных расписаний для задачи Om||Cmax / Г.П. Волчкова // Вестник БГУ. Сер. 1.2. – 2010. – № 2. – С. 127–130.
4. 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.
Review
For citations:
Volchkova G.P., Kotov V.M. STUDYING PROPERTIES OF DENSE SCHEDULES UNDER CONDITION OF LIMITED NUMBER OF SERVICE UNITS. Informatics. 2015;(1):64-72. (In Russ.)
Views: 676
Email this article 