Решение NP-трудной задачи теории расписаний минимизации суммарного запаздывания

Рассматривается классическая NP-трудная в обычном смысле задача теории расписаний для одного прибора минимизации суммарного запаздывания $1\|\sum T_j$. Проведен полный анализ NP-трудного случая задачи. Предлагается процедура разбиения исходного множества требований на подмножества. Построены алгоритмы нахождения оптимального расписания в зависимости от количества подмножеств. Трудоемкость алгоритмов не превышает $O(n^2\sum p_j)$ операций, где $n$ – количество требований, а $p_j$ – продолжительность обслуживания $j$-го требования, $j=1,2,\dots,n$. Библ. 11.