Фундаментальными задачами теории расписаний для одного
прибора являются задачи с критериями минимизации
суммарного запаздывания и задачи минимизации максимального
временного смещения. В данной книге приводится достаточно
полное исследование NP-трудной в обычном смысле задачи
минимизации суммарного запаздывания (total tardiness) и ее
взаимосвязь с задачей Разбиения. Выделен ряд новых
полиномиально и псевдо-полиномиальных разрешимых случаев
данной задачи. При исследовании были использованы как
стандартные методы дискретной оптимизации (метод
динамического программирования, - графическая модификация),
так и методы, учитывающие специфические особенности
задачи. Наряду с точными методами применялись и
приближенные метаэвристические подходы (метод "муравьиные
колонии"). С помощью графического подхода удалось показать
полиномиальную разрешимость обратной задачи - максимизации
суммарного запаздывания.