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

Графический метод - это модификация метода динамического программирования [29]. Преимущества графического метода заключаются в следующем: • с помощью графического метода можно решать примеры с нецелочисленными параметрами; • известно, что для некоторых задач графический метод имеет полиномиальную трудоемкость, в то время как исходный алгоритм метода динамического программирования - псевдополиномиальную. Метод ветвей и границ (B&B) широко используется для нахождения точного (оптимального) решения задач дискретной оптимизации. Чтобы построить алгоритм, основанный на методе Ветвей и Границ, необходимо определить способ ветвления и способы вычисления нижних и верхних оценок. В отличие от задач планирования задачи составления расписаний включают только небольшой фиксированный набор вариантов, в то время как проблемы планирования часто связаны с каскадными множества вариантов, которые взаимодействуют сложными способами. В задаче составления расписаний априорно имеется набор заданий, хотя некоторые из них могут быть необязательными. В проблеме планирования обычно неизвестно, сколько заданий или действий потребуется для достижения цели. Существует обширная литература по теории расписаний в рамках теории исследования операций [27, 28]. Отличие большинства работ по интеллектуальному планированию от работ в области исследования операций заключается в том, что работы в рамках ИИ имеет тенденцию сосредотачиваться на общих представлениях и методах, которые охватывают ряд различных типов задач планирования. Напротив, работы по исследованию операций часто фокусируются на разработке оптимизированных методов для конкретных классов задач составления расписаний, таких как open-shop, flow-shop, job-shop, release dates и т.п.. В качестве примера рассмотрим [32]. В этой работе задачи составления расписаний классифицируются в соответствии с примерно 10 функциями, каждая из которых имеет от 2 до 10 значений. Конкретные подходы к решению многих из этих классов задач часто основаны на специализированных представлениях и алгоритмах. В ИИ наиболее распространенным подходом к решению задачи составления расписаний является представление ее как задачи удовлетворения ограничений и использование общих методов удовлетворения ограничений [26, 27]. Для моделирования задач составления расписаний в виде CSP применяются два основных подхода, отличающиеся способом кодирования исходной информации и требованиями к решениям. В рамках первого подхода требуется назначить время начала каждому заданию, чтобы все заданные временные и ресурсные ограничения были удовлетворены. Второй поход предполагает, что в процессе решения между заданиями будут установлены отношения частичного порядка таким образом, чтобы все имеющиеся временные и ресурсные ограничения удовлетворялись. Большая часть первоначальных работ, где составление расписаний рассматривалось в качестве задачи CSP, была выполнена в рамках первого подхода, и для некоторых приложений он по-прежнему является предпочтительным представлением. Однако существуют также недостатки, возникающие в результате того, что появляется множество вариантов, зависящих 31