Оперативно-календарное планирование и рассмотрение стадий использования гибридного ACO алгоритма.
Введение
Производство сегодня прежде всего ориентировано на увеличение дохода всеми возможными способами. Фабрики перемещены в страны низкой зарплаты, чтобы гарантировать, акционерам максимальную прибыль. Такие решения сталкиваются с дебатами о морали, этике и обязанностями, которые компании имеют перед обществом, начиная с потери всего завода – изготовителя может быть разрушительным сообществу. Альтернатива индустриальной перелокализации пытается поддержать доходность через развитие эффективных производственных программ, лучшее использование ресурсов и лучшее планирование в существующих заводах - изготовителях. Значение эффективных методов планирования, другими словами, растет, и будет вероятно расти.
Главная мысль этой главы - решение MT10 проблемы оперативно-календарного планирования используя 4 разных варианта Оптимизации Муравьиного алгоритма(ACO) и попытаться оценить их. Гибридная модель, которая использует алгоритм постобработки, чтобы улучшить результирующее планирование, также пробуют для всех четырех версий ACO. Термин «видимость» объяснен в контексте оперативно-календарного планирования, и включен в испытания. Когда мы говорим о проблемах оперативно-календарного планирования, мы подразумеваем ряд аппаратов М., ряд задач J и ряда операций O. Для каждой операции есть задача к который она принадлежит, аппарат, на которой она должна быть обработана, предопределенная продолжительность обработки на этом аппарате, так же как предопределенный порядок обработки на аппаратах. Проблема минимизировать период обработки, гарантируя, что не больше, чем одна задача может быть обработана в то же самое время на том же самом аппарате, и если задача начинается, она должна быть закончена (и не может быть прервана). Были многочисленные публикации успешных алгоритмов, относящихся к проблеме оперативно-календарного планирования. Среди точных математических методов Смешанное линейное программирование целых чисел и Branch & Bound, среди методов аппроксимации есть Алгоритм Планирования (см. Panwalker & Iskander, 1977), которые назначают одну операцию за один раз из списка который сортирован по некоторому приоритетному правилу, Shifting Bottleneck Адамса (1988 Simulated Annealing Ван Лэарховена (1988), Запрещённый поиск впервые использовался в оперативно-календарном планировании Тиллардом (1989) и Генетический алгоритм Наканой и Ямадой (1991). Нововведением в этих подходах к JSP, оптимизация муравьиным алгоритмом стала все более и более популярной, когда дело доходит до алгоритмов то процессы подражательного поведения, которые существуют в природе. Первый алгоритм ACO был введен Марко Доригом в его докторском тезисе (1992) и назван Муравьиной системой (AS). С тех пор как появился алгоритм, который эффективен когда доходит до типов проблемы, которые сформулированы как проблема коммивояжер (TSP) и квадратная проблема назначения (QAP). Как результат исследования относительно алгоритмов ACO, появились некоторые очень успешные варианты.
Есть Элитные AS, предложенная Dorigo и др. (1996), в который обновляющие феромон правила основаны на лучшем решении, найденному пока, идея в том, чтобы эксплуатировать компоненты решения в пределах того решения. У Системы Колонии муравьев (ACS) Dorigo и Gambardella (1997) есть несколько модификаций к оригиналу AS. Это использует измененное правило, когда муравей выбирает следующий узел путешествия, он использует лучшее пока правило феромона, но применяет испарение феромона только к компонентам, которые находятся в лучшем пока решении. Это также использует местное обновление правила феромона, чтобы уменьшить ценность феромона на посещаемых компонентах решения, чтобы продолжить исследование. Основанный на разряде AS (RAS) Bullnheimer и др. (1999), вариант где элитный муравей так же как выборка муравьев с хорошими решениями во время того повторения добирается, чтобы обновить следы феромона. max-min AS (MMAS) от Stutzle и Hoos (2000), подход, который обновляет следы феромона, согласно некоторой мере по конвергенции, с любым лучшим итерационным муравьем или лучшим по расстоянию муравьем. Алгоритм использует более низкое содержание феромона (> 0) так же ограничивается максимальное количество феромона которое может иметь след. Нижний предел поощренного муравья, с исследовательским поведением и верхняя граница запрещают преждевременнкю конвергенция из-за элитного решения, доминирующего над другими решениями.
Как пример надежности ACO, Jayaraman и др. (2000) использовал алгоритм ACO в решение комбинаторной проблемы оптимизации многопрофильного планирования партии так же как непрерывная проблема оптимизации функции для проекта многопрофильного завода с единственной кампанией продукта и ограничением горизонта. Дальнейшие реальные приложения алгоритма ACO использовало бы ACO, чтобы решить установленный набор проблем транспортных средства как сделано Коллом и Макмалленом (2004) и проблема динамического регионального планирования для медсестер в Австрии от Gutjahr и Rauner (2005). Прежняя исследование закончилась результатами был двусмысленным, но в последнем исследовании ACO был по сравнен с greedy assignment алгоритмом и были достигнутые очень существенные усовершенствования. Kuo-Ching Ying и др. (2004) применял систему колонии муравьев к календарному упорядочиванию потока и эффективно решил проблему n/m/P/Cmax , и прокомментировал, что система колонии муравьев metaheuristic хорошо стоит исследовать в контексте решения различных проблем планирования. Примером ACO и потокового календарного планирования в недавнем времени было использовано исследование Gajpal и Rajendran (2006), где они использовали новый алгоритм ACO (NACO), чтобы минимизировать завершение различных задач, показывая, что работа с алгоритмами ACO - продолжающийся процесс, чтобы изменить и улучшить оригинал AS и примените его ко множеству задач планирования. Для двух из представленных выше алгоритмов ACO, ACS и MMAS, была доказана конвергенция к оптимальному решению (Dorigo и Stutzle, 2004 так же как Stutzle и Dorigo, 2002). Стоит помнить, что результаты конвергенции не позволяют предсказанию быстро найти оптимальное решение.
Постановка задачи
Проблема оперативно-календарного планирования (JSP) может быть характеризована как n задач, которые будут обработаны на м аппаратах. Вообще это - ряд параллельных и противоречивых целей, которые будут удовлетворены, используя конечный набор ресурсов, где ресурсы называют аппаратами и основные задачами, называют задачами. Каждая задача - запрос о планировании ряда операций согласно плану процесса который определяет ограничения предшествования. Мы имеем:
Для каждой операции 
есть работа Ji, которой она
принадлежит, аппарат Mj, на котором она запускается и продолжительность обработки pij операции uij, где pij -
неотрицательное целое число. Каждая работа - цепь операций, и каждая операция должна быть обработана на данном аппарате в
течение данного времени. Задача состоит в том, чтобы найти стартовые времена всех операций таким образом что время
завершения самой последней операции минимально. Должен быть поддержан порядок цепочкой каждой задачи и каждый аппарат может
только обработать одну задачу в то же самое время. Никакая задача не может быть прерванной; как только операция начинается,
она должна быть закончена. Решение s к случаю n x м. JSP определяет порядок обработки относительно всех задач на каждом
аппарате и неявно определяет самое раннее время начала и завершения для каждой операции. Максимум из времен завершения
называют период обработки, и большинство исследований сводятся к проблеме минимизация периода обработки. Приведенный пример
JSP мы можем связать с этим дизъюнктивный Г графа = (V, A, E), где V набор узла, A - соединительный набор дуги, и E -
дизъюнктивный набор дуги. Узлы V соответствуют всем операциям и двум фиктивным узлам, источнику и сливу. Соединительные
дуги A представляют отношения предшествования между операциями единичных задач и дизъюнктивные дуги E представляют всех пар
операций, которые будут выполнены на том же самом аппарате. У всех дуг, происходящих от узла, есть продолжительность
обработки операции выполненных в этом узле - это их длина. У источника есть соединительные дуги с нулевой длинной для всех
первых операций задачи и у слива есть соединительные дуги, прибывающие из всех последних операций. Выполняемое планирование
соответствует выбору одной дуги от каждой дизъюнктивной дуги и соединяется таким образом, чтобы получающийся направленный
граф был нециклическим, то есть чтобы не было петель. Проблема уменьшения периода обработки уменьшается до обнаружения ряда
дизъюнктивных дуг которые минимизируют длину критического пути в направленном графе. Всестороннее описание из дизъюнктивных
графов относительно проблемы оперативно-календарного планирования могут быть найдены в статья о AS и JSP Colorni и др. (1993).
Проблема MT10 - 10 x 10 случаев, сформулированна Muth и Томпсоном в 1963. Она состоит в том что у 10 задач, обработанных на
10 аппаратах, и у каждой задачи представлено 10 заданий. Продолжительность обработки изменяется с самой короткой, в 2
единицы времени и самые длинные 99 единиц времени. У нее репутация одной из самых трудных комбинаторных проблем когда-либо
рассматриваемый, и была точно решена в 1989 Carlier и Пинсоном, использующих branch and bound. Это - типичная проблема
оперативно-календарного планирования.
Гибридный алгоритм ACO
Алгоритм состоит из двух частей. У нас есть часть ACO, где муравьи перемещаются по области поиска, пытаясь построить подходящий путь. Когда все муравьи построили свой путь, временные отметки были также вычислены для отдельных операций в определенном списке определенном путем, который позволяет нам вычислять период обработки. Части постобработки приводятся в действие когда есть полный список, чтобы воздействовать на них. Глобальное обновление феромона ACO происходит только после того, как постобработка закончилась. После обновления феромона ACO начинается следующая итерация.
Алгоритм постобработки
Алгоритм постобработки применяется после того, как все муравьи построили свой путь. Это алгоритм - эффективная местная процедура поиска, основанная на подходе Nowicki и Smutnicki (1996). Местный поиск начинается идентифицируя критический путь в построенном списке. Критический путь разлагается на много блоков, где блок - максимальная последовательность смежных операций, которые требуют того же самого аппарата. Размер блока может измениться от одной операции до всех операций, которые намечены на одном аппарате. В зависимости от блока меняются операции. Мы начинаем с последнего блока в критическом пути, у которого есть больший размер чем 1 и его последняя операция в блоке. Размер блока должен быть большим чем 1 либо не произойдет обмена. Идентифицированная операция меняется с ее предшественником в том же самом блоке, и необходимые изменения внесены в путь муравья так же как и временные отметки запланированных операций. Если обмен улучшает период обработки, он принят, иначе обмен отменяется, и меняется следующая пара в блоке. Если блок больше не содержит обменов мы двигаемся в предыдущий блок. Отметим, что принятый обмен означает что критический путь может измениться, и новый критический путь должен быть идентифицирован. Если никакой обмен операций в критическом пути не улучшает период обработки, поиск заканчивается. Это означает, что муравьиный путь может измениться в части постобработки алгоритма. Муравьиный путь после самой первой законченной постобработки, может радикально отличаться от того, полученного первым повторением ACO, но следующая постобработка начинается после первого раунда вычислений намного легче. На рис. 1 показан критический путь и возможные обмены в списке в качестве примера.
Что такое видимость?
Дополнительная проблема при работе с муравьиным алгоритмом - работа видимости. Есть общие черты между правилами приоритета, используемыми в эвристических подходах и видимости одного муравья, которые пытаются оценить и сделать выбор того, куда пойти после определенного узла. Обычно видимость упоминается как окрестность муравья, то есть узлы, которые близки к узлу где в настоящее время находится муравей. Это - показатель того, какие узлы муравей может видеть стоя на указанном узле. Независимо от того, на каком узле стоит муравей, расстояние ко всем другим узлам может быть получено из предрасчетной таблицы расстояний. Когда значения попадают в списки, не понятно, что такое видимость и как влияет на вычислениях относительно ACO. Расстояние в единицах времени от узла на пути к следующему не известно, пока не вычислены временные отрезки для всего пути. Другая проблема с ACO и МП 10 в том, что одного запрещённого списка (посещенных узлов) недостаточно. Так как задачи в каждой работе должны быть выполнены в правильном порядке, то есть, задача A3 должена быть сделан перед A4 и т.д., необходим список кандидата. Список кандидата имеет весь выбор узлов, в которые муравей может попасть из узла, в котором он в настоящее время находится. Это означает что должны быть вычислены только вероятности выбора для узлов в списке кандидата, который ускоряет алгоритм.