Н.А. Лутовинова, Классические задачи теориирасписаний

Доклад носит обзорный характер и посвящён введению в классическую теорию расписаний — раздел дискретной оптимизации, изучающий задачи распределения работ по приборам с целью минимизации заданного критерия качества. Разбираются основные классы приборов: одиночный прибор, параллельные приборы различных типов, а также специализированные конфигурации — flow shop, job shop и open shop. Среди рассматриваемых ограничений — моменты готовности работ, отношения предшествования, допустимость прерываний и условие выполнения без ожидания между операциями. В качестве целевых функций обсуждаются максимальное время завершения, максимальное запаздывание, суммарные и взвешенные времена завершения, опоздания и количество опоздавших работ. Рассматривается понятие полиномиальной сводимости задач друг к другу, что позволяет выстроить иерархию сложности по типу приборов, ограничениям и критериям оптимальности. Даётся обзор классических алгоритмов и эвристик: правила упорядочивания по ранним срокам, наименьшему времени выполнения, взвешенному времени выполнения, наибольшему времени выполнения и общая схема списочного планирования.