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
V. M. Kotov
Белорусский государственный университет
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. Volchkova, G.P. K gipoteze o plotnykh open-shop raspisaniyakh / G.P. Volchkova // Vestnik BGU. Ser. 1.2. - 2004. - № 2. - S. 58-61.
3. Volchkova, G. P. O svoistve plotnykh raspisanii dlya zadachi Om||Cmax / G.P. Volchkova // Vestnik BGU. Ser. 1.2. - 2010. - № 2. - S. 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.
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: 694
Email this article 