Составление расписаний с ресурсными ограничениями

Реальные задачи составления расписаний усложняются из-за наличия ограничений на ресурсы. Например, для установки в автомобиль двигателя требуется лебедка для двигателя. Если есть только одна лебедка, то нельзя одновременно устанавливать двигатель #1 в автомобиль d и двигатель Е2 в автомобиль С2, поэтому расписание, показанное на рис. 12.1, будет неосуществимым. В данном примере лебедка для двигателя представляет собой пример повторно применяемого ресурса — ресурса, который "занят" во время действия, но снова становится доступным после завершения этого действия. Следует отметить, что повторно применяемые ресурсы невозможно учесть в нашем стандартном описании действий в терминах предусловий и результатов, поскольку количество доступных ресурсов после завершения действия остается неизменным1. По этой причине дополним наше представление, включив в него поле в форме Resource: R(k), которое означает, что для выполнения данного действия требуются к единиц ресурса R. Требования к ресурсам являются одновременно и предпосылкой (действие не может быть выполнено, если ресурс недоступен), и временным результатом, в том смысле, что во время выполнения действия доступность ресурса г сокращается на к единиц. В листинге 12.2 показано, как дополнить задачу сборки автомобилей для включения трех ресурсов — лебедки для двигателя, с помощью которой устанавливаются двигатели, станции монтажа колес, на которой устанавливаются колеса, и двух контролёров. На рис. 12.2 показано решение с самым быстрым временем завершения, 115 минут. Это время больше по сравнению с 80 минутами, которые требовались для выполнения расписания без ресурсных ограничений. Следует отметить, что нет такого промежутка времени, в который требовались бы оба контролёра, поэтому, составив данное расписание, можно сразу же перевести одного из двух контролёров на другой участок, где он будет приносить больше пользы.
Листинг 12.2. Задача составления производственного расписания для сборки двух автомобилей с учетом ресурсов. Доступными ресурсами являются одна станция сборки двигателя, одна станция сборки колес и два контролёра. Обозначение Resource: г указывает, что ресурс г используется во время выполнения действия, но снова становится свободным после завершения этого действия
Init {Chassis (Ci) л Chassis (С2)
л Engine{Elt Clt 30) л Engine{E2, С2, 60) л Wheels (Wlt Clt 30) л Wheels (W2, C2, 15) л EngineHoists(1) л WheelStations(1) л Inspectors(2))
Goal {Done id) л Done{C2))
Action{AddEngine(e, c) ,
Precond: Engine{e, c, d) л Chassis(c) л —\EngineIn{c), Effect: Engineln{c) л Duration{d),
Resource: EngineHoists(1) ) Action{AddWheels(w, c) ,
Precond: Engineln(c) л Wheels{w, c, d) л Chassis(c),
Effect: WheelsOn(c) л Duration(d),
Resource: Wheel Stations(1) ) Action(Inspect(c),
Precond: Engineln{c) л IVheelsOn (с) ,
Effect: Done(c) л Duration(10),
Представление ресурсов в виде числовых количественных значений, таких как Inspectors (2), а не именованных сущностей, таких как Inspector (11) и Inspector (Т2), может служить примером очень продуктивного метода, называемого агрегированием. Основная идея агрегирования состоит в том, что отдельные объекты должны группироваться в количественные величины, если все объекты неразличимы применительно к рассматриваемому назначению. В данной задаче сборки не имеет значения, какой именно контролёр проверит автомобиль, поэтому нет необходимости проводить между ними различие. (Та же идея может применяться при решении задачи с миссионерами и каннибалами, приведенной в упр. 3.9.) Агрегирование представляет собой важный способ уменьшения сложности задач. Рассмотрим, что произойдет, если будет предложено расписание, в котором имеется 10 одновременных действий по проверке inspect, но в наличии есть только 9 контролёров. Если контролёры представлены с помощью количественных величин, неудача будет обнаружена немедленно и алгоритм выполнит возврат, чтобы попытаться составить другое расписание. А если бы контролёры были представлены как отдельные лица, то в алгоритме пришлось бы выполнять возвраты для опробования всех 10! способов назначения контролёров для выполнения действий Inspect, притом что положительный результат так и не был бы получен.
Несмотря на их преимущества, ресурсные ограничения приводят к усложнению задач планирования, поскольку в них вводятся дополнительные зависимости между действиями. К тому же составление расписания без ограничений с использованием метода критического пути является несложным, а задача поиска расписания с ресурсными ограничениями, характеризующегося самым ранним возможным временем завершения, является NP-трудной. Такая сложность часто наблюдается не только в теории, но и на практике. Одно из заданий, которое предложили исследователям для проверки их сил в 1963 году (найти оптимальное расписание для задачи, в которой рассматриваются только 10 машин и 10 работ по 100 действий каждая), не удавалось решить в течение 23 лет [900]. Для его решения было опробовано много подходов, включая метод ветвей и границ, алгоритм эмуляции отжига, поиск с запретами, метод удовлетворения ограничений и другие методы, описанные в части II этой книги. Одной из простых, но широко применяемых эвристик является алгоритм с минимальным резервом. В нем планирование действий осуществляется в режиме жадного поиска. Во время каждой итерации в этом алгоритме рассматриваются не введенные в расписание действия, для которых в расписании заданы все их преемники, и в расписание вводится то действие, которое имеет наименьший резерв для самого раннего возможного времени начала. После этого в алгоритме обновляются значения времени ES и LS для каждого затронутого действия и повторяется итерация. Эвристика основана на том же принципе, что и эвристика с "наиболее ограниченной переменной" в задачах удовлетворения ограничений. Этот алгоритм хорошо работает на практике, но применительно к рассматриваемой задаче сборки он привел к получению 130-минутного решения, а не 115-минутного решения, показанного на рис. 12.2.
Подход, принятый в этом разделе, состоит в том, что "вначале следует оставлять план, а затем расписание". Это означает, что общая задача подразделяется на этап планирования, в котором выбираются и частично упорядочиваются действия для достижения целей данной задачи, и на следующий за ним этап составления расписания, в котором в план вводится временная информация для обеспечения того, чтобы он соответствовал ограничениям по ресурсам и срокам. Такой подход широко применяется в организациях, занимающихся реальным планированием производства и поставок, в которых этап планирования часто выполняется экспертами-людьми. Однако, если существуют жесткие ограничения на ресурсы, могут возникать такие ситуации, что одни допустимые планы приводят к получению гораздо более лучших графиков, чем другие. В этом случае имеет смысл интегрировать этапы планирования и составления расписаний, принимая во внимание продолжительности и совпадения действий во времени на этапе создания плана с частичным упорядочением. Для учета такой информации могут быть дополнены некоторые алгоритмы планирования, описанные в главе 11. Например, планировщики с частичным упорядочением могут обнаруживать нарушения ресурсных ограничений во многом с помощью такого же способа, который в них используется для обнаружения конфликтов с помощью причинных связей. А эвристики могут быть модифицированы для оценки общего времени завершения плана, а не просто суммарной стоимости всей действий. В настоящее время в этой области исследований ведется активная работа.







Материалы

Яндекс.Метрика