Пример 10.9. Задача составления расписания

Как отмечено выше, в главе 9, важной для практических приложений является задача составления расписания, состоящая в упорядочении набора заданий (работ). В этой задаче заданы список заданий и ограничения, какие задачи могут быть выполнены одновременно, выполнение каких заданий должно предшествовать выполнению других и т.д.

Для решения этой задачи нужно найти присвоение времен начал работ заданиям так, чтобы все ограничения удовлетворялись.

Рассмотрим задачу составления расписания для пяти заданий , каждое из которых может быть выполнено за один час. Задания могут начинаться в 1:00, 2:00 или 3:00.

Любые работы могут выполняться одновременно, учитывая ограниче­ния на то, что может начинаться после , может начинаться до и после , не может начинаться в то же время, что или , не может начинаться в 2:00.

Можно построить модель составления графика, введя пять переменных, соответствующих заданиям с доменами . Соответствующий граф ограничений показан на рис. 10.3.

Рис. 10.3. Граф ограничений и отношения задачи составления графика.

Другие практические приложения УО и программирования в ограниче­ниях приведены ниже, в разделе 10.2.5.