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

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

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

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

Любые работы могут выполняться одновременно, учитывая ограниче­ния на то, что Пример 10.9. Задача составления расписания - №2 - открытая онлайн библиотека может начинаться после Пример 10.9. Задача составления расписания - №3 - открытая онлайн библиотека , Пример 10.9. Задача составления расписания - №3 - открытая онлайн библиотека может начинаться до Пример 10.9. Задача составления расписания - №5 - открытая онлайн библиотека и после Пример 10.9. Задача составления расписания - №6 - открытая онлайн библиотека , Пример 10.9. Задача составления расписания - №7 - открытая онлайн библиотека не может начинаться в то же время, что Пример 10.9. Задача составления расписания - №2 - открытая онлайн библиотека или Пример 10.9. Задача составления расписания - №5 - открытая онлайн библиотека , Пример 10.9. Задача составления расписания - №5 - открытая онлайн библиотека не может начинаться в 2:00.

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

Пример 10.9. Задача составления расписания - №12 - открытая онлайн библиотека

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

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