Preview

Информатика

Расширенный поиск

ИССЛЕДОВАНИЕ СВОЙСТВ ПЛОТНЫХ РАСПИСАНИЙ ПРИ ОГРАНИЧЕННОМ ЧИСЛЕ ПРИБОРОВ

Полный текст:

Аннотация

Для задачи 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.)

Просмотров: 199


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1816-0301 (Print)
ISSN 2617-6963 (Online)