К гипотезе Ситтерса–Фишкина

Рассматривается вопрос о минимальном числе миграций в оптимальном расписании задачи $Pm|pmtn(delay=d)|C_\mathrm{max}$ на параллельных машинах с разрешенными прерываниями и константной задержкой при миграциях работ. В частности, рассматривается гипотеза Ситтерса–Фишкина о том, что для любого примера задачи существует оптимальное расписание с не более чем $m-1$ миграциями, где $m$ – число машин. Гипотеза была подтверждена в [1] для случая $m\leqslant3$. В данной работе получено подтверждение гипотезы в случае четырех машин.

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