ИССЛЕДОВАНИЕ СВОЙСТВ ПЛОТНЫХ РАСПИСАНИЙ ПРИ ОГРАНИЧЕННОМ ЧИСЛЕ ПРИБОРОВ
Аннотация
Для задачи max Om||Cmax существует гипотеза, что в худшем случае для любого плотного расписания время завершения выполнения последней работы не более чем в 2-1/m раз превосходит время завершения в оптимальном расписании. Предлагается подход, который позволяет доказать гипотезу для случая m ≤ 9 и некоторых специальных случаев.
Об авторах
Г. П. Волчкова
Белорусский государственный университет
Россия
Россия
В. М. Котов
Белорусский государственный университет
Россия
Россия
Список литературы
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.
Рецензия
Для цитирования:
Волчкова Г.П., Котов В.М. ИССЛЕДОВАНИЕ СВОЙСТВ ПЛОТНЫХ РАСПИСАНИЙ ПРИ ОГРАНИЧЕННОМ ЧИСЛЕ ПРИБОРОВ. Информатика. 2015;(1):64-72.
For citation:
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.)
Просмотров: 671
Послать статью по эл. почте 