Cоставление расписаний как задача удовлетворения ограничений (на примере планирования открытых горных работ)

Аннотация

Описываемые в статье исследования направлены на развитие методов составления расписаний. Принципиальным недостатком существующих методов смешано- целочисленного линейного программирования в применении к рассматриваемым задачам является то, что они слишком требовательны к объемам оперативной памяти. Сложность же применения процедур локального поиска к подобным задачам высокой размерности состоит в разработке эффективного способа нахождения приемлемого первоначального приближения и определении функции перехода в соседнее состояние, которая бы позволила достаточно быстро достичь оптимума. В теории исследования операций добавление к задаче дополнительных условий может привести к принципиальному изменению используемой схемы решения задачи. Предлагаемые в статье методы реализованы в рамках парадигмы программирования в ограничениях, что позволяет более экономно с точки зрения оперативной памяти представлять зависимости предметной области, а также обеспечивает возможность поэтапного учета разнородных условий задачи без принципиального изменения схемы поиска решений. Существенная часть исследований посвящена использованию методов логического вывода на ограничениях для снижения размерности пространства поиска и ускорения процесса вычислений. Подход к составлению расписаний проиллюстрирован на задаче оптимизации планирования открытых горных работ, которую впервые предложено решать как задачу удовлетворения ограничений. Для нахождения первого допустимого решения предложен метод «жадного» поиска, результат применения которого затем может быть улучшен с помощью разработанного гибридного метода. Оба метода опираются на оригинальные процедуры вывода на ограничениях. Предложенный подход доказал свою эффективность для блочных моделей размерностью в десятки и сотни тысяч блоков.