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

Представлен эффективный метод решения классической NP-трудной задачи теории расписаний для одного прибора минимизации суммарного запаздывания $1||\sum T_{j} $. Предлагается алгоритм решения задачи, основанный на декомпозиции исходной задачи на подзадачи своевременного обслуживания каждого из требований и размещении в конец расписаний тех из них, прирост запаздывания которых в наибольшей степени компенсируется сокращением запаздываний предшествующих требований. Трудоемкость алгоритма не превышает $O\left(n^{2} \right)$ операций, где $n$ – количество требований.