Том 3, номер 1, 1996 г., Стр. 57-74

УДК 519.854
С. В. Севастьянов, И. Д. Черных
Достаточное условие эффективной разрешимости задачи open shop

Аннотация:
Рассматривается задача open shop для $m$ машин и $n$ работ с критерием минимальности длины расписания. Продолжается рассмотрение подкласса задач с так называемым условием доминирования, когда нагрузка одной машины, называемой машиной-доминантой, превышает нагрузки остальных машин по крайней мере на величину $\Delta$. Доказывается, что при $\Delta\geqslant mp_{\max}$, где $p_{\max}$ – максимальная длительность операции, длина оптимального расписания равна нагрузке машины-доминанты, и приводится алгоритм с временной сложностью $O(nm^2)$ для нахождения такого расписания. Доказана также теорема о том, что для случая четырех машин с величиной доминирования $\Delta\geqslant (m-1)p_{\max}$ длина оптимального расписания также равна нагрузке машины-доминанты, и такое расписание может быть найдено за $O(n)$ операций.
Ил. 16, библиогр. 7.

Севастьянов С. В. ¹
Черных И. Д. ²
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия

Статья поступила 23 мая 1995 г.