Построение расписаний выполнения независимых работ на идентичных параллельных машинах с прерываниями и миграционными задержками

Представлены результаты по сложности и аппроксимации задачи на минимум длины расписания выполнения $n$ независимых работ на $m$ идентичных параллельных машинах при допущении прерываний операций и с миграционной задержкой $d$. Найдена точная граница значений задержки $d$, при пересечении которой полиномиально разрешимая задача становится $NP$-трудной в сильном смысле. Получены первые результаты в поддержку предположения о том, что для любого примера существует оптимальное расписание с не более чем $m-1$ миграцией. Представлен $\left(1+\dfrac1{\log_2n}\right)$-приближающий алгоритм линейной трудоёмкости для случая двух машин.

Статья представлена к публикации членом редколлегии: А. А. Лазарев