РАЗРАБОТКА И РЕАЛИЗАЦИЯ АДАПТИВНОГО АЛГОРИТМА МУРАВЬИНОЙ КОЛОНИИ ДЛЯ РЕШЕНИЯ ЗАДАЧ КАЛЕНДАРНОГО ПЛАНИРОВАНИЯ
Матренин П.В.
Научный руководитель к.т.н Секаев В.Г.
Новосибирский государственный технический университет
Введение
Во всех сферах человеческой деятельности для эффективного достижения результата необходимо составлять расписания и временные планы. Распространенность и сложность таких задач вместе с постоянным повышением уровня автоматизации привели к развитию интереса к теории синтеза расписаний и календарному планирование.
Качество функционирования организаций во многом определяется эффективностью планирования и оперативного управления при этом требования к снижению сроков выполнения работ, повышению оперативности и гибкости управления непрерывно ужесточаются.
Задачи календарного планирования отражают процесс распределения во времени ограниченного числа ресурсов для выполнения проекта, состоящего из заданного множества взаимосвязанных работ. Эти задачи особенно важны в промышленном производстве, строительстве, составлении расписания образовательных и медицинских учреждений и управлении проектами, например при разработке программно обеспечения.
Согласно результатам большинства исследований, детерминированные задачи календарного планирования относятся к NP-трудным задачам упорядочения и носят комбинаторный характер [1,2,3]. Для решения задачи применяют различные способы, в данной работе исследуется перспективный, возникший всего 20 лет назад [4], метод решения оптимизационных задач – метод колонии муравьев.
Многие существующие способы решения данного класса задач подвергаются критике из-за недостаточной практической ориентации методов, поэтому в данной работе кроме исследования и усовершенствования метода создано программное приложение для составления календарных планов, как пример практической реализации разработанных алгоритмов. Разработанное приложение не является информационной системой календарного планирования, а представляет собой ту часть информационной системы, которая использует необходимую нормативно-справочную и текущую информацию организации, непосредственно генерирует квазиоптимальные планы и отчеты, с их сохранением в базе данных организации.
Таки образом, целью работы данной работы является разработка и исследование метода колонии муравьев в задачах календарного планирования.
1 Описание предметной области
1.1 Формализованная постановка задачи календарного планирования
Большинство задач по составлению календарных планов связаны с понятием многостадийных обслуживающих систем [1], то есть систем, в которых процесс обслуживания требований состоит их нескольких стадий. Изготовление детали состоит из последовательности операций, выполняемых на станках. Занятия у группы студентов проходят в несколько пар в определенных кабинетах и у определенных преподавателей. Разработка программного продукта включает анализ предметной области, постановку задач, разработку, построение алгоритмов, кодирование, отладку, тестирование, документирование, причем на каждый из этапов может быть назначена конкретная группа исполнителей.
Несмотря на разнообразие производственных систем и технологий, формализованная математическая запись задачи календарного планирования, данная в [1] имеет право считаться универсальной, базовой для любых многостадийных систем. Данное утверждение было подтверждено также при анализе предметной области (пункт 1.2).
Формализованная постановка задачи. Имеется конечное множество N={1,2,…,n} требований (работ, партий деталей, станочных плит и т.п.) и конечное множество M={1,2,…,m} приборов (станков, исполнителей, рабочих станций).
Процесс обслуживания требования i (i  N) включает ri стадий (этапов, технологических операций). При этом каждому требованию i и каждой стадии q (1 ≤ q ≤ ri) его обслуживания сопоставляется некоторое подмножество приборов Miq из множества M. Предполагается, что каждый прибор одновременно может обслуживать не более одного требования.
В таких системах с последовательными приборами для каждого требования iN задается своя, специфическая для этого требования последовательность Li его обслуживания приборами:
Li=(L1 i, L2 i,…, Lri i). (1.1)
Требование i сначала обслуживается прибором L1i, затем прибором L2i и т.д. Последовательности обслуживания могут быть различными для разных требований и могут содержать повторения приборов.
Если требование i на стадии q должно быть обслужено прибором l, то предполагается заданной длительность tliq его обслуживания этим прибором. Процесс функционирования системы может быть описан путем задания расписания (календарного плана, плана-графика), т.е. некоторой совокупности указаний относительно того, какие именно требования какими именно приборами обслуживаются в каждый момент времени. При этих предположениях расписание можно рассматривать как совокупность {s1(t), s2(t),…, sm(t)} кусочно-постоянных непрерывных слева функций, каждая из которых задана на интервале 0≤t<∞ и принимает значения 0,1,…, N.
s={s1(t), s2(t),…, sm(t)} (1.2)
Если sl(t’) = i , sl(t’) ≠ 0 , lM , iN , то в момент времени t’ прибор l обслуживает требование i. Если sl(t’) = 0, то в момент времени t’ прибор l простаивает.
При задании расписания должны соблюдаться все условия и ограничения, вытекающие из постановки рассматриваемой задачи, то есть расписание должно быть допустимым. Построение допустимого расписания и даже выяснение того факта, существует ли оно вообще является далеко не тривиальной задачей.
Если существует несколько допустимых расписаний, необходимо выбрать лучше из них, что приводит к сложной и многоплановой проблеме оценки расписания. В классической теории расписания за критерий качества берется время завершения выполнения всех требований или время завершения последнего требования (очевидно, что это одна и та же величина).
Оценка качества расписания осуществляется следующим способом. Каждое допустимое расписание s однозначно определяет вектор моментов завершения обслуживания требований.
T(s)=(T1(s),T2(s),…,Tn(s)) (1.3)
Задается некоторая действительная неубывающая по каждой из переменных функция F(x),
F(x)=F(x1,x2,…,xn) . (1.4)
Тогда качество расписания s оценивается значением этой функции при x=T(s). Из двух расписаний лучшим считается то, которому соответствует меньшее значение F(x). При построении оптимального по быстродействию расписания выбирается максимальное значение, так как момент завершения выполнения самого длительного требования совпадает, как уже сказано, с моментов окончания выполнения всех требований из множества N, таким образом,
F(x)=max{xi} , i=1,n . (1.5)
В этом случае
F(T(s))=Tmax(s), где Tmax(s)=max{Ti(s)} , i=1,n . (1.6)
Из приведенной выше постановки сразу заметны основные сложности задачи: дискретность, многовариантность, многофакторность, невозможность построения целевой функции в виде алгебраического выражения, зависящего от управляемых переменных, как в задаче коммивояжера или транспортной задаче, так как целевая функция рассчитывается только алгоритмически.
Многостадийные системы делят на следующие классы:
- системы “flow-shop” предполагает, что каждое требование должно быть обслужено каждым из приборов 1,…,m в порядке 1,…,m;
- системы “open-shop” отличается порядком прохождения требований, он может быть произвольным, в этом случае маршрут прохождения по приборам является частью искомого решения;
- системы “job-shop” наиболее близки к реальным ситуациям, когда маршруты требований строго заданы, но отличаются для разных требований и могут содержать повторы приборов.
Очевидно, что системы “flow-shop” являются частным случаем систем “job-shop”. В данной работе рассматриваются именно “job-shop” системы.
Для задачи КП точное решение при помощи линейного программирования может быть получено только для одного или двух приборов, а для реальных производственных задач точное оптимальное решение может быть найдено только теоретически (без учета фактора времени выполнения расчетов), на практике же это неосуществимо.
Для решения задачи КП используют различные приближенные методы, позволяющие находить близкие к оптимальным (квазиоптимальные) решения. Обзор методов дан в следующем разделе работы (пункт 2.1). Особенностью большинства этих методов является подход к целевой функции как к «черному ящику», так чтобы метод мог работать при добавлении ограничений или изменении критерия оптимальности. Такой подход дает преимущества при использовании на практике, когда возможны некоторые изменения в математической модели, ведь любая модель абстрагирует и упрощает реальность.
Чтобы разрабатываемый в данной работе метод был эффективным, нужно рассмотреть реальные ситуации, которые возникают при составлении планов в различных областях деятельности.
1.2 Описание и особенности календарного планирования в организации
Календарный план производства или план работ над проектом является расписанием работ по заказу в рамках требуемой продолжительности, т.е. распределение производственных работ по срокам для каждого оборудования или исполнителя. Календарный производственный план должен обеспечить равномерный выпуск продукции в заданные сроки на имеющемся оборудовании, максимально его загрузив. Календарной план в случае проектной деятельности должен обеспечить своевременное выполнение всех частей проекта с учетом имеющихся групп исполнителей (например, разработчиков ПО).
Сам по себе календарный план это проектно-технологический документ, который устанавливает полный перечень работ проекта их последовательность, взаимосвязи, а также закрепляет за этими работами исполнителей и другие ресурсы необходимые для их выполнения.
В отличие от математической постановки задачи в реальных ситуациях часто возникают ситуации, когда срочный заказ или поломка оборудования заставляют пересматривать и корректировать планы по ходу их выполнения. Таким образом, в реальных условиях часто возникают отклонения, которые могут быть связаны с поломками оборудования или инструмента, отсутствием сырья на складах, увольнением сотрудников, несчастным случаем или браком какой-либо детали. Возникает необходимость внесения изменений в расписание.
Вторым отличием является наличие не только временного показателя эффективности, но и других критериев, таких как загрузка производственных мощностей, экономические показатели и т.д. Из-за этого многие недостаточно гибкие методы решения задач КП оказываются неэффективными на практике.
Таким образом, для получения полной картины к математической постановке задачи КП нужно прибавить ограничения, которые накладываются на выполнение работ, учет интервалов времени, когда ресурсы доступны, и учет дополнительных критериев эффективности. Учет временных интервалов доступности ресурсов предполагает не только возможные сбои и поломки, но и длительность рабочего дня или смены, количество смен и т.д.
При использовании автоматизированной системы КП эффективность работы повышается не только из-за оптимизации использования ресурсов, но и благодаря переходу к безбумажной документации, исключению неточностей в планах, отсутствию дублирования информации.
Необходимо учитывать, что на современных предприятиях часто уже существуют автоматизированные информационные системы, состоящие, например, из бухгалтерской подсистемы, складского учета, подсистемы работы с кадрами и т.д.
Если для внедрения системы планирования потребуется полная реконструкция существующей системы, это приведет к резкому повышению стоимости и времени разработки и внедрения, но может в итоге повысить эффективность функционирования всех подсистем предприятия. Если же организация по каким-либо причинам не готова к коренной перестройке (нехватка средств, нежелание переобучать персонал, внедрение имеющейся АИС произошло совсем недавно и т.п.), но нуждается в программном средстве составления планов и расписаний, то эффективнее использовать гибкую систему КП, быстро дорабатывающуюся под все индивидуальные требования и легко интегрирующуюся с существующей АИС. Такое программное приложение может использоваться даже для составления индивидуальных планов одного человека (суть такой задачи не в оптимизации, а в предоставлении удобного инструмента создания планов и отчетов), так как для этого можно использовать самую простую версию программы, не требующую установки и сопровождения.
Календарное планирование загрузки производственных мощностей и распределения заказов между группами исполнителей имеет много общего [1], но различается терминологией. Возможность применять систему КП в разных предметных областях делает ее более гибкой и универсальной, поэтому ниже приведены основные термины из области производственных систем, затем из сферы управления проектами.
2 Метод колонии муравьев при решении задач КП
2.1 Описание метода
Муравьи решают проблемы поиска путей с помощью химической регуляции [4]. Каждый муравей оставляет за собой на земле дорожку особых веществ - феромонов. Другой муравей, почуяв след на земле, устремляется по нему. Чем больше по одному пути прошло муравьев - тем явнее след, а чем явнее след - тем большее «желание» пойти в ту же сторону возникает у муравьев. Поскольку муравьи, нашедшие самый короткий путь к «кормушке», тратят меньше времени на путь туда и обратно, их след быстро становится самым заметным. Он привлекает большее число муравьев, и круг замыкается. Остальные пути – менее используемые – постепенно пропадают. Можно сформулировать основные принципы взаимодействия муравьев:
- случайность;
- многократность;
- положительная обратная связь;
- отрицательная обратная связь.
Основная идея алгоритма МК состоит в реализации принципа коллективного разума. Для поиска экстремума целевой функции алгоритм использует параллельно несколько агентов (искусственных муравьев), которые в ходе поиска накапливают статистическую информацию. Эта информация аккумулируется в общедоступном банке данных и используется агентами независимо друг от друга. Каждый агент действует по правилам вероятностного алгоритма и при выборе направления ориентируется не только на приращение целевой функции, но и на статистическую информацию, отражающую предысторию коллективного поиска.
Метод МК является итеративным. На каждой его итерации определенное количество агентов строят такое же количество допустимых решений задачи. Среди этих решений выбирается часть наилучших по целевой функции и в этой части отыскиваются повторяющиеся компоненты решений. Полученная информация запоминается и на последующих итерациях данные компоненты будут иметь большую вероятность войти в решение, чем это было на предыдущих итерациях.
Так как каждый муравей выполняет примитивные действия, то и алгоритм получается очень простым и сводится к многократному обходу некоторого графа, дуги которого имею не только вес, но и дополнительную динамически меняющуюся количественную характеристику, называемую количеством феромона или просто феромоном.
Для решения задачи КП методом муравьиной колонии (МК) необходимо [4]:
представить задачу в виде ориентированного взвешенного графа (в отличие от задачи коммивояжера), на котором муравьи будут строить решение;
определить значение следа феромона;
определить эвристику поведения муравья при построении решения;
реализовать локальный поиск;
настроить параметры алгоритма.
Определяющим для решения задачи также являются:
количество муравьев;
сочетание с жадными эвристиками и локальным поиском;
момент обновления феромона.
Итерационный алгоритм МК включает построение решения всеми муравьями, улучшение решения методом локального поиска, обновление феромона. Построение решения начинается с пустого частичного решения, которое расширяется путем добавления к нему новой допустимой компоненты решения. Выбор компоненты решения осуществляется по правилам вероятностного выбора на каждом шаге построения решения:
 . (6)
Коэффициент α определяет степень влияния количества феромона на k-м ребре (fк) на вероятность того, что муравей выберет это ребро. В знаменателе – сумма по всем доступным из узла ребрам.
Обновление феромона необходимо для его увеличения на лучшем (коротком) пути и уменьшения для плохих решений. Используется также испарение феромона для того, чтобы избежать слишком большой сходимости алгоритма.
Если F – значение целевой функции на маршруте, то количество феромона, нанесенного муравьем на все ребра маршрута Δf можно определить так:
 . (7)
Коэффициенты β и γ – коэффициенты интенсивности выделения феромона. Коэффициент β введен, чтобы сделать зависимость нанесения феромона на граф более гибкой (не обязательно линейной).
Коэффициент ρ влияет на испаряемость феромона, при этом считается, что на ребрах всегда должно оставаться некоторое минимальное не нулевое количество феромона, иначе вероятность выбора ребра может оказаться нулевой и оно будет «игнорироваться» муравьями. Максимальное значение так же ограничено, что предотвращает возможную сходимость алгоритма к одному, далеком от оптимального, решению. Коэффициент принимает значения от 0 (нет испарения) до 1 (испаряется до минимального уровня).
 (8)
В ходе экспериментальных исследований было выявлено улучшение результатов при усилении значимости текущего наилучшего решения. Для этого на все ребра пути, соответствующего лучшему результату, на каждой итерации добавляется некоторое количество феромона, определяемое коэффициентом λ. Ограничение на максимально количество феромона учитывается и здесь.
 (9)
Качество получаемых решений в МК методах, отмечается в [4], во многом зависит от:
- выбора условно оптимального решения на шаге инициализации;
- настроечных параметров в вероятностно-пропорциональном правиле выбора пути на основе текущего количества феромона;
- параметров правил откладывания, испарения и начального распределения феромона.
Представим поиск решения задачи КП следующим образом. Пусть W – суммарное количество этапов всех работ из множества N.
Для того чтобы полностью задать расписание, достаточно указать, какую работу загружать на нужный ей прибор на каждом i-м шаге, i=1,2,…,W. Тогда у графа будет W+1 вершин, причем первая вершина соединена только со второй, вторая – с первой и третьей, третья – со второй и четвертой и так далее. Вершина с номером W+1 соединена только с вершиной W. Ребра, соединяющие вершины, соответствуют работам.
Проходя по графу, муравей “запоминает” последовательность работ. Как только работа i попала в эту последовательность столько раз, сколько у нее этапов (ri), муравей начинает игнорировать соответствующие ей ребра до конца пути.
Рассмотрим простой пример. Имеется три требования (A,B,C), причем работа A состоит из двух этапов, а работы B и C содержат по три этапа. Таким образом, W=2+3+3=8.
На рисунке 1 представлен соответствующий граф.
Рисунок 1 – Пример графа
Пример движения муравья на данному графу проиллюстрирован а рисунке 2.
Рисунок 2 – Пример прохода муравья по графу
Допустим, что с учетом имеющегося на ребрах количества феромона, на первом шаге муравей выбрал требование A, на втором шаге – B, на третьем – снова А. Выбранные дуги на рисунке 2 выделены утолщением. Так как требование А содержит два этапа, больше ее выбирать нельзя, и оставшиеся дуги, соответствующие А, игнорируются муравьем в данном проходе по графу (на рисунке отмечены серым цветом и пунктиром).
Затем муравей выбирает дуги C,C,B,C, после чего в предпоследнем узле графа остается выбрать только работу B. Таким образом, на данном проходе по графу будет сформирована последовательность A,B,A,C,C,B,C,B.
Далее необходимо определить значение целевой функции, т.е. время окончания всех работ и количество феромона, которое необходимо добавить на выбранные в данном проходе ребра графа.
|
