Достаточное условие эффективной разрешимости задачи 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