О сложности построения многопроцессорных расписаний с малым количеством прерываний

Доказана NP-трудность задачи open-shop для n процессоров при разрешенных $n-3$ прерываниях [1]. Работа сделана в рамках цикла работ автора, посвященных теории расписаний, насчитывающего уже около сотни цитирований.

Список литературы

1. Е. В. Щепин, “О сложности построения многопроцессорных расписаний с малым количеством прерываний”, Современные проблемы математики, механики и математической физики, Сборник статей, Тр. МИАН, 290, МАИК, М., 2015, 178–190      ; E. V. Shchepin, “On the Complexity of Constructing Multiprocessor Little-Preemptive Schedules”, Proc. Steklov Inst. Math., 290 (2015), 166–177