Парадигма программирования в ограничениях при решении задач составления расписаний: аналитический обзор

Аннотация

В статье рассмотрен подход к решению задач составления расписаний на основе парадигмы программирования в ограничениях. Любой метод удовлетворения ограничений включает две обязательные части: a) компоненту, отвечающую за поиск; b) компоненту, осуществляющую вывод на ограничениях (распространение ограничений). При реализации первой компоненты обычно применяется определенный вариант поиска в глубину с возвратами с использованием эвристик для выбора преемника текущего узла в дереве поиска. Вторая компонента реализуется с применением механизма глобальных ограничений. Глобальные ограничения можно рассматривать как составные ограничения, представляющие собой набор более простых однотипных ограничений. Алгоритмы распространения глобальных ограничений, как правило, подкреплены соответствующими развитыми теориями, позволяющими организовывать высокопроизводительные вычисления. Технология программирования в ограничениях позволяет реализовывать общие методы решения сложных комбинаторных задач, а также дает возможность интегрировать с помощью механизма глобальных ограничений существующие методы теории исследования операций, направленные на решение узких классов задач. При решении задач составления расписаний основные ограничения могут быть типизированы следующим образом: ограничения на порядок выполнения операций, ограничения на унарные (дистрибутивные) ресурсы, ограничения на кумулятивные ресурсы. В настоящей работе произведен обзор основных классов задач составления расписаний и сделан акцент на типах ограничений, которые в них используются. Для решения упомянутых задач могут быть использованы методы удовлетворения ограничений общего назначения, однако более перспективным считается применение специализированных эвристик и глобальных ограничений. В работе произведен обзор наиболее популярных эвристик, используемых при решении задач составления расписаний, а также глобальных ограничений таких, как: глобальное ограничение на дизъюнктивные ресурсы, глобальное ограничение на кумулятивные ресурсы, глобальное ограничение на мощность множеств. В статье обсуждаются особенности реализации различных классов задач составления расписаний с использованием современных сред и библиотек программирования в ограничениях.