Исследование алгоритмов оптимизации конфигурирования и распределения заказов при решении задач ТПП в среде виртуального предприятия

ИССЛЕДОВАНИЕ АЛГОРИТМОВ ОПТИМИЗАЦИИ КОНФИГУРИРОВАНИЯ И РАСПРЕДЕЛЕНИЯ ЗАКАЗОВ ПРИ РЕШЕНИИ ЗАДАЧ ТПП В СРЕДЕ ВИРТУАЛЬНОГО

ПРЕДПРИЯТИЯ Ю.Н. Фомина

Научный руководитель - к.т.н., доцент Е.И. Яблочников

Важнейшей характеристикой современной организации ТПП является широкое использование кооперации. Предприятия, выполняющие различные работы по ТПП, рассматривают использование современных форм кооперирования с другими компаниями как одно из основных направлений укрепления своего бизнеса. Предлагаемая методология дает возможность планировать реализацию распределенного ТП.

Введение

Важнейшей характеристикой современной организации ТПП является широкое использование кооперации, когда вокруг основных предприятий существует круг партнеров-субподрядчиков. Виртуальное предприятие - это временная межпроизводственная кооперация ряда юридически независимых предприятий, которая:

создается в короткий срок и поддерживается с помощью современных информационных технологий;

путем интеграции возможностей участников разрабатывает и производит актуальную продукцию и услуги;

обходится без новых юридических образований, которые заменяются гибкой координацией.

Обычная форма организации предприятия подразумевает, что производители стараются наиболее выгодно для себя подобрать заказы под имеющиеся у них ресурсы. Участники виртуального предприятия, напротив, стремятся оптимальным образом подобрать ресурсы под имеющиеся заказы. Второй вариант ведения бизнеса позволяет получить наилучшее распределение ресурсов предприятия (например, нагрузки оборудования) [2]. Использование такой организации производства, как виртуальное предприятие, позволяет получать следующие преимущества:

позволяет находить наиболее выгодных и надежных партнеров из-за более широкой и динамичной среды виртуального предприятия;

предоставляет большие возможности для экономии времени и стоимости проектирования и изготовления;

способствует увеличению эффективности работы предприятий-участников за счет наиболее оптимального распределения ресурсов;

стимулирует распространение новых технологий, которые позволяют создавать продукцию с улучшенной конструкцией и лучшего качества;

позволяет выпускать продукцию, оптимально соответствующую требованиям покупателей, за счет более динамичной структуры виртуального предприятия.

Благодаря более низкой себестоимости производства при одновременном сокращении сроков выпуска и улучшении качества продукции виртуальные предприятия на сегодняшний день уже составляют серьезную конкуренцию крупным традиционных компаниям.

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

Целью работы в данном случае является выполнение оценки и выбора среди участников виртуального предприятия исполнителей заказов на ТПП изделий. Для этого необходимо предложить:

структуру для представления данных о ТПП для их последующего анализа;

подход к оптимальному конфигурированию и распределению заказов на решение задач ТПП в среде виртуального предприятия.

Основная часть

Особенностью проектирования ТП в распределенной среде является его многовариантность. Во-первых, заданное состояние изделия может достигаться за счет реализации различных вариантов технологического процесса. Например, комплексная операция, выполняемая на токарно-фрезерном обрабатывающем центре с ЧПУ, может заменить последовательность из нескольких токарных и фрезерных операций. Выбор того или иного варианта маршрута осуществляет обычно инженер-технолог, исходя из собственного опыта. Однако перевод ТПП изделия в среду виртуального предприятия накладывает более жесткие требования на выбор варианта ТП и его обоснование. Во-вторых, каждой задаче ТПП может соответствовать несколько потенциальных исполнителей, предлагающие различные варианты ее решения.

Таким образом, в распределенной производственной среде проектировщик создает универсальный технологический процесс, поскольку не обладает информацией о конкретных доступных возможностях, ресурсах и мощностях производителя. Этот начальный технологический процесс называется ресурсо-независимым технологическим процессом (РНТП) и лишь указывает подразумеваемые процедуры, необходимые для создания изделия. При разработке РНТП проектировщик определяет, какие именно задачи ТПП будут выполнены сторонним производителем.

Поверхности, получаемые удалением материала, могут иметь требования к точности обработки (взаимного расположения элементов детали). Операции удаления материала, имеющие высокие требования к точности, должны быть выполнены без перезакрепления, другими словами, каждая из них не может быть выполнена различными производителями. Если процессы изготовления двух отверстий имеют требования к точности взаимного расположения, отверстия развертываются за одну операцию. Подобные требования влекут за собой необходимость выполнения этих процессов в пределах одного установа, т. е. операция состоит из набора переходов, которые должны быть произведены без перезакрепления одним и тем же производителем. Поэтому увязка с конкретными ресурсами (т.е. распределение ресурсов для РНТП) должна выполняться на уровне операций.

Обычно РНТП состоит из нескольких операций. РНТП можно представить в виде разветвленного графа, вершинами которого являются операции, а ребра определяют последовательность выполнения операций. Такое представление ТП позволяет отобразить его многовариантную структуру. При этом параллельные ветви графа (множество эквивалентных вершин) соответствуют различным вариантам реализации ТП (подграфам, содержащим множество эквивалентных вершин) [3]. Для каждой операции ТП определено множество заказов З на выполнение работ средствами стороннего предприятия.

Зк е З, г = 0, ..., п,

где Зк - г -й заказ на выполнение ТПП; п - число заказов на выполнение ТПП к -й

операции. Таким образом, РНТП представляется двухуровневым графом. Верхний уровень называется операционным уровнем графа (ОУГ), а нижний - уровнем заказов (ЗУГ). На рис. 1 а, б представлен пример изображения РНТП в виде двухуровневого графа.

Рис. 2. Ресурсо-зависимый технологический процесс

Из рис. 1 видно, что множество заказов, соответствующих операциям, может быть пустым или включать один или несколько заказов.

Каждый узел ЗУГ определяет требования к его характеристикам, таким как тип, точность, связанные с ним геометрические элементы и другие. В соответствии с этими требованиями происходит выбор исполнителя заказа среди участников виртуального предприятия. Проектировщик составляет РНТП в соответствии с конструкцией изделия. Затем из опубликованного списка производителей выбираются конкретные производители, чьи производственные возможности и мощности соответствуют требованиям каждой операции. Следует отметить, что если поиск производителя не принес результатов, проектировщик может изменить конструкцию и/или составить новый РНТП. После выбора предприятие-заказчик передает конкретным производителям РНТП, который впоследствии становится ресурсо-зависимым технологическим процессом (РЗТП). В соответствии с этим определено множество потенциальных участников виртуального предприятия (потенциальных производителей).

Пг е П, г = 0, ..., I;

где Пк - потенциальный исполнитель г -го заказа на выполнение ТИП; I - общее число потенциальных исполнителей проекта ТПП.

Преобразование РНТП из рис. 1 в РЗТП показано на рис. 2.

На рис. 2 каждому заказу поставлены в соответствие возможные его исполнители. Следует отметить, что исполнитель может быть назначен на выполнение более чем одной операции.

Следующий шаг - выбор в ходе переговоров конкретного единственного производителя из ранее подобранных для каждого заказа. Подбор вариантов и определение характеристик выполнения заказа - предложений от потенциальных исполнителей в виде, например, приблизительных стоимости и времени выполнения заказа - осуществ-

ляется под управлением современных информационных технологий. Необходимо оценить каждого производителя, опираясь на полученные в ответ предложения на участие. На основании полученных данных на последнем этапе создается распределенный технологический процесс (РТП). РТП - это оптимальный набор производителей, каждому из которых поручается группа операций, что обеспечит проектировщику оптимальные или близкие к ним характеристики производственных параметров, таких как стоимость, качество и время изготовления. В данной работе предлагается методология оценки и оптимизации распределения задач ТПП среди потенциальных исполнителей, рассмотрены подходы к составлению окончательного РТП.

Прежде чем приступить к оценке и выбору производителей для РНТП, необходимо провести подготовку данных для сотрудничества. Процедура подготовки производится в следующем порядке:

упрощение: исключение из РЗТП таких операционных узлов и/или изначально необоснованно выбранных производителей, которые на данный момент недоступны или считаются неэкономичными;

расширение РЗТП за счет увеличения альтернатив для выбора производителя так, что каждый узел графа характеризовался бы единственным производителем.

объединение: группирование операционных узлов, которые могут быть выполнены одним производителем.

Цель упрощения - исключить нереализуемые или неэкономичные операции или варианты производителей из РЗТП. Следующий этап - расширение - для расширения сокращенного РНТП путем дублирования узлов графа. Это означает, что операционный узел, включающий в себя несколько возможных производителей, дублируется столько раз, сколько существует вариантов производителей. Например, если заказ г на рис. 3а обладает т возможными вариантами производителей, то он дублируется т раз в набор (Згк, Зк2,..., Зкт) как показано на рис. 3б.

В этом случае каждая дублированная операция несет одну и ту же информацию, но предназначается разным производителям (П1,..., П,..., Пт ). Результатом этапа расширения является увеличенный РЗТП, в котором каждый операционный узел связан только с одним производителем.

На последнем этапе производится объединение узлов ЗУГ, которые могут быть выполнены одним производителем, группируются они с целью снижения транспортных затрат и расходов на управление. После окончания подготовки данных для сотрудничества можно приступать выбору и оценке исполнителей, т.е. к формированию РТП. Для

Рис. 3. Расширение РЗТП

проведения такого анализа необходимо выделить критерии выбора оптимального решения. В самом простом случае в качестве критериев выбора оптимального варианта РЗТП могут быть использованы такие показатели, как время и стоимость выполнения заказа. При этом необходимо обследовать все множество возможных решений и выбрать то из них, которое позволяет минимизировать эти показатели.

Данная задача аналогична «задаче коммивояжера» (ЗКВ) [4, 5]. В исходном варианте ЗКВ состоит в том, чтобы по данному списку городов определить в каком порядке коммивояжер должен посетить каждый из них по одному разу, чтобы получившийся маршрут был кратчайшим из возможных или хотя бы близким к таковому. ЗКВ может быть решена несколькими методами. Вот некоторые из них:

«алгоритм жадности» или метод поиска «ближайшего соседа»;

метод полного перебора;

метод «ветвей и границ»;

метод «восхождения»;

генетический алгоритм (ГА).

Из всех перечисленных методов наиболее длительным в плане расходования машинного времени является метод полного перебора. Наиболее выгодными являются метод «ветвей и границ» и генетические алгоритмы. Наибольший экономический эффект получается при решении ЗКВ с использованием генетических алгоритмов. Использование того или иного метода поиска оптимального решения зависит от размера пространства поиска. Если проектировщик имеет дело с небольшим ТП, содержащим не так много вариантов исполнения, то в данном случае имеет смысл воспользоваться, например, «алгоритмом жадности». Это позволит определить оптимум. Однако, если необходимо проанализировать более сложный ТП, который может включать несколько сотен операций и множество вариантов реализации ТП, а также множество потенциальных исполнителей для каждой задачи ТПП, поиск оптимума может потребовать значительных машинных ресурсов и занять продолжительно время. Стоит отметить, что в общем случае ГА не находят оптимального решения очень трудных задач, однако использование данного метода дает достаточно хороший результат.

Изложенные условия позволяют считать ГА наиболее эффективным методом для определения оптимальной последовательности производителей при решении задач ТПП в среде виртуального предприятия.

ГА, один из производно-свободных методов оптимизации, основан на понятии естественного отбора и эволюционных процессов. В отличие от методов наследования, таких как искусственные нейронные системы, в ГА используется большой объем вычислений для получения оптимального решения, что обусловлено характерными для ГА повторяющейся структурой и случайностью сочетаний. Тем не менее, непрерывная решается задача или дискретная, согласно ГА будут найдены решения с помощью характерной предметной функции, и эти решения будут наиболее оптимальными вариантами во всем пространстве решений. Благодаря этим особенностям область применения ГА широка и разнообразна, включает в себя задачи проектирования промышленного оборудования, проектирования зданий, определения параметров предпочтительной модели и оптимизации параметров процесса. После достижения критерия остановки в качестве оптимального решения отбирается вариант (квазиоптимум), обладающий лучшим сочетанием интересующих нас качеств [3].

Генетические алгоритмы обладают следующими достоинствами:

позволяют решать задачу оптимизации с любым количеством вершин в графе ЗУГ;

разрешают распараллелить задачу;

допускают ограничение решения задачи как по времени, так и по заданному критерию останова;

обладают высоким быстродействием и могут использовать решения, полученные другими методами, как начальные приближения с их последующей оптимизацией;

имеют большое количество настроек, позволяющих изменять условия и время сходимости.

Относительно проблематики ТПП хромосома ГА соответствует варианту РЗТП. Хромосома состоит из генов, каждый ген соответствует определенному заказу РЗТП (имеется в виду уровень заказов графа РЗТП) и должен быть закодирован таким образом, чтобы однозначно описывать характеристики заказа (время и стоимость его выполнения). При этом такие данные, как конкретные заказ, исполнитель, время и стоимость выполнения заказа, являются фенотипом описываемой системы. В свою очередь, последовательность генов, содержащая эту же, но уже закодированную информацию, является генотипом данной системы. Таким образом, для решения задачи нам необходимо представить характеристики каждого заказа в форме, подходящей для использования в ГА. Все дальнейшее функционирование механизмов генетического алгоритма производится на уровне генотипа, позволяя обойтись без семантики описываемой системы. Это обстоятельство как раз и определяет широкое применение ГА в различных областях.

Генетические алгоритмы решают задачи, работая с популяцией из некоторого числа наугад взятых решений. Относительно рассматриваемой проблематики ТПП под решением понимается вариант РЗТП. Далее с помощью генетических операторов происходит изменение хромосом выбранной популяции, что позволяет выйти за ее рамки и определить оптимальное решение на всем множестве решений с хорошей степенью вероятности. К генетическим операторам относятся скрещивание (его также называют кроссовер или кроссинговер), мутация и инверсия.

Итак, если ЗКВ включает несколько сотен объектов, то ее решение является трудной задачей для современных ПК. При этом объем пространства поиска очень велик, даже лучший из выбранных вариантов может оказаться плохим. Для решения таких задач следует использовать ГА. Для реализации ГА необходимо сымитировать «выживание сильнейших» хромосом, выделяя их среди остальных. Для этого требуется:

в начальный момент времени t = 0 необходимо случайным образом сформировать начальную популяцию (первое поколение), состоящую из k особей: Popul0 = {Ab A2,..., Ak}, где A1 - вариант РТП, i е (0, к);

вычислить приспособленность каждой особи из этой популяции и популяции в целом с помощью, так называемой, фитнес-функции: FAi = fit(Ai), где i е (0, к) (значение этой функции определяет, насколько хорошо подходит особь, описанная данной хромосомой, для решения задачи), Ft = fit(Bt) , где t - поколение популяции

(первоначально Popul0);

выбрать особь Ac из популяции: Ac = get(Popult) ;

с определенной вероятностью выбрать вторую особь из популяции Ac1 = get (Popult) и провести операцию кроссовера: Ac = cros sin g (Ac, Ac1);

с определенной вероятностью выполнить операцию мутации: Ac = mutationg(Ac) ;

с определенной вероятностью выполнить операцию инверсии: Ac = inversion( Ac);

поместить полученную хромосому в новую популяцию: insert{Bt+1, Ac };

выполнить операции, начиная с пункта 3, k раз;

увеличить номер текущей популяции (эпохи) t = t +1;

если выполнилось условие останова, то завершить работу, иначе выполнить операции, начиная с пункта 2 [6].

Теперь необходимо более подробно рассмотреть отдельные этапы алгоритма. Наибольшую роль в успешном функционировании алгоритма играет этап отбора родительских хромосом (пункты 3 и 4). При этом возможны различные варианты. Наиболее часто используется метод отбора, называемый рулеткой. «Колесо рулетки» используется для выбора из текущего поколения хромосом, которые сохранятся в следующем поколении. Другой часто используемый метод - турнирный отбор. Он заключается в том, что случайно выбирается несколько особей из популяции (обычно два) и победителем становится особь с наибольшей приспособленностью. Кроме того, в некоторых реализациях алгоритма применяется так называемая стратегия элитизма, которая заключается в том, что особи с наибольшей приспособленностью гарантированно переходят в новую популяцию. Использование элитизма обычно позволяет ускорить сходимость генетического алгоритма. Недостаток использования стратегии элитизма - в том, что повышается вероятность попадания алгоритма в локальный минимум (ЗКВ относится к многоэкстремальным задачам) [3]. Другой важный момент - определение критериев останова. Обычно в качестве них применяются или ограничение на максимальное число эпох функционирования алгоритма, или определение его сходимости, обычно путем сравнивания приспособленности популяции на нескольких эпохах и остановки при стабилизации этого параметра.

Вычисление приспособленности хромосомы - это единственная часть программы, в которой необходимо иметь представление о том, что же на самом деле кодирует хромосома. Поэтому для каждой прикладной задачи необходимо писать собственную фит-нес-функцию. В задаче по оптимизации распределения задач ТПП в среде виртуального предприятия фитнес-функция будет зависеть от двух переменных (первоначально были определены два критерия выбора варианта заказа: время и стоимость его выполнения) [7]. При этом задача назначения приоритетов на критерии выбора предоставляется для выполнения проектировщику. Это обстоятельство связано с тем, что методы ведения бизнеса различных предприятий могут значительно отличаться. Например, одна компания при размещении своего заказа может руководствоваться такими приоритетами, как качество и сроки исполнения, а другая - стоимостью его реализации.

Приоритеты критериев в фитнес-функции будут отражаться в виде весовых коэффициентов. Таким образом, фитнес-функция (для двух критериев) распределения заказов среди участников виртуального предприятия будет выглядеть следующим образом:

Fas = fit

FA, = 1САг +2TA ,

где CA и ТA - соответственно стоимость и время реализации совокупности заказов РЗТП среди выбранных производителей, а ш1 и ш2 - их весовые коэффициенты.

ш1 +ш2 = 1.

n=max

При этом стоимость и время РЗТП равняются СА = Z C (3in ), ТА = ^Т (3in ),

n=0 n=0

где C(3in) и Т(3in) - соответственно, стоимость и время выполнения n -го заказа i -го варианта РЗТП, а max(n) - количество заказов в данном варианте РЗТП. Следует отметить, что n - это порядковый номер заказа в последовательности заказов, относящихся к выбранному РТП, а не обозначение соответствия заказа конкретной операции, как показано на рис. 1. Таким образом, искомая фитнес-функция определяется по формуле

n=max

Fa,i =i ZС(Зп)+2 ZT(3m).

2

n=0 n=0

Как было сказано ранее, хромосомы содержат закодированную информацию. Требуется определить, какой код необходимо использовать для описания РЗТП, т.е. найти такой вид кодирования РЗТП, который позволит по найденной хромосоме (результату решения

ЗКВ с помощью ГА) однозначно определять, какой последовательности заказов, а также их исполнителей он соответствует. Кроме того, при определении приспособленности особей популяции необходимо по коду хромосомы определить конкретные значения С (Зп) и

Т (Зп) заказа. Для этого необходимо построить матрицу приспособленности, столбцы которой будут соответствовать потенциальным исполнителям заказов РЗТП, а строки - заказам, входящим в РНТП. Матрица будет иметь размерность X х У, где X - число всех заказов оцениваемого РНТП, а У - численность участников виртуального предприятия, задействованных в выполнении ТПП данного изделия. Ячейки матрицы будут содержать значения фитнес-функции (приспособленности) для конкретных заказов и исполнителей (= ш1С (Зп) + ш2Т (Зп)). Полученная матрица представлена на рис. 4.

П: П2 ... Пу

З1 Fn ^12 ... ?1у

З2 ^22 ... Р2у

З х Р1х З5 1 ... К 1 ху

Рис. 4. Матрица приспособленности для анализируемой системы

Итак, хромосома РЗТП состоит из генов, каждый из которых соответствует заказу РЗТП. Гены в хромосоме должны быть расположены в той же последовательности, что и заказы в графике РЗТП (ЗУР). Для выполнения исходных требований по кодированию РЗТП ген должен состоять из номера заказа и номера исполнителя. При этом для каждого гена становится возможным определить по матрице приспособленности его значение фитнес-функции. Следует отметить, что часть ячеек матрицы будет иметь нулевые значения. Это обстоятельство связано с тем, что конкретному заказу соответствует ограниченное множество потенциальных исполнителей.

Если допустить, что число потенциальных исполнителей проекта имеет трехзначное значение, а число заказов оцениваемого проекта - четырехзначное, то для кодирования каждого гена потребуется использовать десятичный код, состоящий из семи цифр. Например, для последовательности заказов, представленных на рис. 2, хромосома может выглядеть так, как указано на рис. 5.

1 ген 2 ген 3 ген 4 ген 5 ген

0001001 0002003 0003002 0004001 0005004

Рис. 5. Пример построения хромосомы для РЗТП

Поиск оптимального решения задачи ЗКВ с помощью ГА также включает в себя

использование генетических операторов кроссинговера, мутации и инверсии. Исполь-

зование этих операций позволяет расширить область поиска и исключить возможность принятия в качестве решения задачи локального оптимума выбранной популяции. При кроссинговере хромосомы группируются в пары, и случайным образом выбирается точка кроссинговера. После этого «генетический материал» родителей смешивается. Однако если в выбранной популяции представлен не весь «генетический материал», то использование скрещивания не позволит получить недостающие гены, что исключит из анализа часть множества решений. Мутация предназначена для того, чтобы избежать подобных ситуаций и увеличить вариабельность популяции. Выполнение этой операции приводит к тому, что одна произвольно выбранная ячейка хромосомы случайным образом меняет свое значение. Кроме того, используется также оператор инверсии, который разбивает хромосому на две части и затем меняет их местами [7].

В соответствии с ГА лучшая хромосома (представляющая вариант РЗТП) получается в последнем поколении. Выбранная хромосома должна быть декодирована в РТП, для этого используется матрица приспособленности. По сути, данный процесс является обратным процессу кодирования РЗТП. Этот этап является последним, его результат -получение решения задачи КМВ для оптимизации конфигурирования и распределения заказов на решении задач ТПП в среде виртуального предприятия.

Заключение

Целью данной работы является оценка и выбор среди участников виртуального предприятия исполнителей заказов на ТПП изделий. Одной из основных задач конфигурирования ВП является задача размещения заказа. Для ее реализации необходимо определить механизм (алгоритм) поиска конкретного производителя (исполнителя заказа), а также критерии выбора этой компании среди участников виртуального предприятия.

При выполнении исследования был предложен ряд методик по оптимизации конфигурирования и распределения заказов при решении задач ТПП в среде виртуального предприятия:

• методология упрощения составления и оценки технологического процесса в структуре распределенного производства;

• метод представления РЗТП в виде двухуровневого графа, что позволяет описывать и оценивать множество заказов рассматриваемого проекта;

• методика (генетический алгоритм) оценки и выбора оптимальной последовательности производителей для реализации РТП;

• методика вычисления фитнес-функции для нахождения оптимального РТП;

• метод кодирования хромосомы РЗТП, который охватывает все множество решений при поиске оптимальной конфигурации РТП.

Предложенная методология дает возможность объединения планирования и производства в распределенной производственной среде. В конечном счете, ее можно использовать как быструю и эффективную форму виртуального производственного предприятия.

Литература

1. Schuh G., Millarg K., Goransson A. Virtuelle Fabrik: neue Marktchansen durch dynamische Netzwerke // Munchen, Wien: Carl Hanser Verlag, 1998.

2. Яблочников Е.И. Автоматизация технологической подготовки производства в приборостроении // Учебное пособие. СПб: СПбГИТМО (ТУ), 2002. 92 с.

3. Романовский И.В. Алгоритмы решения экстремальных задач./ М.: Наука, 1977. 352 с.

4. Cho H. and Wysk R.A. Intelligent workstation controller for computer integrated manufacturing: problem and models. // Journal of manufacturing Systems. 1995/14(4). Р. 252263.

5. Joo J., Park S. and Cho H. Adaptive and dynamic process planning using neural networks. // International Journal of Production Research. 2001. 39(13). Р. 2923-2946.

6. Стариков А.В. Генетические алгоритмы - математический аппарат. BaseGroup Labs, 2001. 5 с.

7. Clement R.P., Wren A. Genetic Algorithms and Bus-Driver Scheduling // Presented at the 6th International Conference for Computer-Aided Transport Scheduling, Lisbon, Portugal, 1993. 9 c.