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

После того, как были освещены некоторые технологии планирования, нацеленные на поддержку неопределенности, вещественных величин, кратко затронем подход, предназначенный для работы с непрерывным временем. Рассмотрим системы [23, 24], которые объединили идеи планирования POCL и используют интервальное представление для действий и предложений. Данные системы опираются на методы удовлетворения ограничений для представления и управления отношениями между интервалами. Мы будем называть этот подход - основанный на ограничениях интервальный подход (CBI aproach). Аллен представил набор из семи основных интервальных отношений (и их обратных), которые могут быть использованы для описания отношений между интервалами. Аллен описывает мир, утверждая, что предложения занимают интервалы времени. Аналогичным образом, действия и события описываются как некоторые интервалы. Ограничения между интервалами описывают отношения между действиями (или событиями). Планировщик работает в обратном направлении от целей, добавляя к плану новые действия, которые, в свою очередь, вводят новые подцели в силу интервальных ограничений. Ограничения на интервалах затем переводятся в простые равенства и неравенства ограничения между конечными точками. Проверка вывода и согласованности в этой сети ограничений часто может быть выполнена с использованием быстрых алгоритмов дуговой совместности [25]. Планировщики CBI можно рассматривать как динамические механизмы удовлетворения ограничений - планировщик поочередно добавляет новые ограничения для сети, затем использует методы удовлетворения ограничений для распространения эффектов этих ограничений и для проверки согласованности. Теперь кратко опишем исследования в области составления расписаний. Составление расписаний и методы искусственного интеллекта Составление расписаний не получало серьезного внимания в сообществе искусственного интеллекта до начала 1980-х годов, пока не начались разработки систем составления расписаний, управляемых ограничениями [26]. С того времени все большее число исследователей ИИ работает в этой области. Общая концепция составления расписаний в ИИ заключается в том, что это особый случай планирования, в котором действия уже выбраны, а требуется определить их допустимый порядок. Два хорошо известных учебника по исследованию операций [27, 28] определяют проблему составления расписания как проблему назначения ограниченных ресурсов заданиям с учетом времени для оптимизации одной или нескольких целей. В этом определении есть три важных момента: • В основе задач составления расписаний лежат рассуждения о времени и ресурсах. • Проблема составления расписания - это почти всегда проблема оптимизации. • Проблема составления расписания также связана с выбором. Часто он не просто ограничивается выбором порядка заданий, но включает выбор того, какие ресурсы использовать для каждого задания. Для данного задания могут быть доступны несколько альтернативных ресурсов с разными затратами и / или продолжительностью. В рамках теории расписаний принято выделять следующие разделы: 29