Теория расписаний. Задачи суммарного запаздывания для одного прибора

Саарбрюкен : LAP LAMBERT Academic Publishing, 2011.

Лазарев А. А., Гафаров Е. Р.

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

Ключевые слова: оптимизация, оптимальные системы, модели, теория графов, теория расписаний, приближенные алгоритмы, комбинаторный анализ, методы исследования операций, исследование операций, нелинейные детерминированные системы, математическая кибернетика