Труды КНЦ вып.9 (ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ вып. 10/2018(9))

от количества временных меток. Во-первых, набор возможных вариантов излишне велик, поскольку реальное количество вариантов значительно меньше, чем набор всех возможных присваиваний. Это затрудняет поиск решений из-за огромного размера пространства поиска. Во-вторых, подход зависит от дискретизации времени, что делает необходимым определять атомарные временные интервалы, прежде чем задача может быть решена. Хуже того, размер представления зависит от способа дискретизации времени - измеряется ли время в часах, минутах, секундах. Второй подход к представлению задач составления расписаний в виде задач CSP основан на введении для каждой пары задач двух переменных. Если обеим этим переменным присваивается значение «ложь», то две задачи могут перекрываться во времени; присвоение «истины» для обеих переменных запрещено. Данный подход к представлению задач CSP имеет большое значение для устранения изложенных выше недостатков. В частности, результирующее пространство поиска в этом случае значительно меньше, поиск осуществляется на булевых переменных. Данное представление задачи не зависит от способа дискретизации времени, так как существуют алгоритмы, которые могут отслеживать диапазон времен начала заданий без использования дискретизированных временных точек (см., например, [25]). Следовательно, минимальная длина графика может быть определена непосредственно на основе заданного частичного порядка. В последние годы многие исследователи ИИ изучали задачи выполнимости в качестве альтернативы общей формулировке задачи удовлетворения ограничений. Задача выполнимости является задачей удовлетворения ограничений, где каждая переменная является булевской переменной и каждое ограничение имеет форму дизъюнкции литералов, каждый из которых представляет переменную или отрицание переменной. Работа в этой области привела к разработке различных быстрых и эффективных алгоритмов выполнимости [33]. Однако, было выявлено, что затраты на представление временных ограничений в рамках этого подхода нивелируют любые преимущества, обеспечиваемые более быстрыми алгоритмами [34]. До этого задача составления расписаний рассматривалась нами как задача удовлетворения ограничений. Однако задачи составления расписаний часто являются проблемами оптимизации. Задача удовлетворения ограничений легко может быть расширена до задачи оптимизации ограничений (COP). Все, что требуется, - это функция, которая отображает решение с помощью вещественнозначной функции стоимости или функции оценки [35]. Задачи оптимизации ограничений не изучались так широко, как обычные CSP. Тем не менее, имеется ряд полезных методов для решения COP. Многие из этих методов являются адаптацией методов удовлетворения ограничений, а другие используют более ранние методы оптимизации, такие как имитация отжига. Сведение задачи составления расписаний к задаче CSP позволяет использовать широкий арсенал средств CSP: алгоритмы распространения ограничений, поиск в глубину с возвратами, структурные алгоритмы, алгоритмы локального поиска, алгоритмы обработки глобальных ограничений и т.п. [36, 37]. С учетом того, что задачи составления расписаний требуют анализа временных и ресурсных ограничений, были разработаны специальные методы 32