8.5. Планирование работы производственного участка

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

Рассмотрим задачу оперативного планирования работы участка по обработке древесно-стружечных плит в условиях динамически изменяющегося портфеля заказов. Рассматриваемый участок является частью мебельного комбината, который выпускает мебельные стенки, состоящие из элементов типа шкаф, тумбочка и других. Производство носит позаказный характер — работа ориентирована на текущий пакет заказов клиентов. Каждый заказ включает в себя набор стандартных изделий. Поэтому главная цель работы участка — это своевременное выполнение заказов. Следовательно, целью планирования являются правильно назначаемые, согласованные с заказчиками и соблюдаемые сроки выполнения заказов [206].

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

Структура размещения оборудования на участке представлена на рисунке 8.23.

С входных рольгангов очередная выбранная для обработки партия заготовок транспортируется роботом_1 на вход линии_1 или линии_2 в зависимости от реализуемого техпроцесса. Данные линии являются кромкообразующими, они полностью взаимозаменяемы и работают в параллельном режиме. На них заготовки обрабатываются до требуемых размеров, а также обклеиваются их кромки. Заготовки на данных линиях проходят только одностороннюю обработку (обрабатывается только правая и передняя по движению кромки). После этого заготовки транспортируются слинии_1 транспортером, аслинии_2 роботом _ 2 на приемный накопи-

тель линий_31илинии_32. Это линии фирмы «Homag» для формирова™ ния кромок, которые полностью взаимозаменяемы. На них производится специальная обработка кромок (недоступная для линии_1 и лмнмм_2), а также обработка поверхностей заготовок. В зависимости от типа заготовки она может обрабатываться как на одной из этих линий, так и на обеих. Линия_31илиния_32 могут работать параллельно или последовательно. С них заготовки транспортируются роботомлибо на линию_1, либо на линию_2, в зависимости от того, на какой из этих линий транспортируемая партия заготовок обрабатывалась вначале. После повторной обработки на линии_1 или налинии_2 теперь уже партии готовых деталей попадают на выходные рольганги, где они ожидают момента комплектации изделия, чтобы при помощи робота _3 быть доставленными на выход участка.

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

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

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

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

Функции системы планирования представлены на рисунке 8.25.

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

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

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

Статические, т. е. не меняющиеся в процессе использования:

•    правило плановых сроков DDATE (Due date) — приоритет принимает значение, пропорциональное сроку, к которому должна быть изготовлена деталь. Он нацелен на запуск вперед тех деталей, которые раньше должны быть изготовлены;

•    правило LPT (Longest processing-time) — приоритет назначаемый детали пропорционален длительности ее обработки;

•    правило поэтапных плановых сроков OPNDD (Operation due date) — пррюритет назначается в соответствии со сроками выполнения промежуточных операций над деталью;

•    правило кратчайшей операции SPT (Shortest processing-time) — правило, обратное правилу LPT. Его цель — уменьшить межоперационное пролеживание деталей.

Динамические, изменяющиеся во времени:

•    правило по декору DEK — детали имеющие декор, такой же как предыдущая включенная в план, имеют больший пррюритет, чем остальные;

•    правило по стандартным деталям DET — стандартные детали запускаются в производство раньше уникальных, при этом преследуется цель уменьшения переналадки оборудования;

•    правило оставшихся этапов. Первой запускается деталь с наименьшим числом невыполненных операций обработки;

•    правило временного резерва на этап S/OPN (Slack per operation);

•    правило случайного выбора RND (Random) — детали выбираются равновероятно.

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

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

где ti и tj — соответственно опережение и запаздывание заказов во времени [мин.]; ttj, bj — весовые коэффициенты такие, что <С 6j, і = 1,2,...,/; j = 1, 2,..., J; n = / + J — общее количество заказов в пакете.

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

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

На основе проведенных исследований эффективности простых приоритетных правил был выбран вид составного правила как взвешенной суммы приоритетов, получаемых с использование простых правил:

где аі — весовой коэффициент, учитывающий важность j-ro приоритетного правила; Uji — значение приоритета і-й детали, полученное при использовании j-ro пррюритетного правила.

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

Одна из главных проблем данного подхода — получение адекватной оценки для принимаемых решений, т. е. прогнозирование их последствий в будущем. Для этой цели используется имитационная модель, реализованная на языке РДО. Используемый для определения оптимальных значений весовых коэффициентов ПГА также реализован на РДО (см. п. 5.2).

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

•    один ген хранит в себе весовой коэффициент одного из приоритетных правил;

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

•    позиция гена-правила в хромосоме остается неизменной.

Составленная таким образом особь-хромосома представляется в двоичном формате для участия в работе ПГА. Каждый ген состоит из одного байта, т. е. в нем может храниться число от О до 255. Так как для кодировки вещественного числа необходимо использовать дополнительные разряды, то изначально весовой коэффициент представлен в гене в виде целого числа в интервале [0..255], которое потом масштабируется на необходимый нам интервал [0,0.. 1,0] путем деления содержимого гена на 255,0.

На рисунке 8.26 приведены результаты одного из прогонов ПГА. Здесь представлены изменения критерия оптимизации Г для худшей, лучшей особей в поколениях, а так же среднее значение критерия по поколениям.

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

где 18000 — максимально возможное значение критерия Г, которое определяется по интервалу генерации плановых сроков заказов.

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

Улучшение использования материала на основе применения оптимизационных алгоритмов при разделке бревен имеет важное значение для предприятий лесоперерабатывающей промышленности. Рассмотрим особенности решения этой задачи применительно к типовому участку разделки бревен фирмы Heidelberger Holzverarbeitmig GmbH, ФРГ (рис. 8.28) [207].

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

Оборудование участка (см. рис. 8.28) вкл.ючает в себя конвейеры, транспортеры, позицию измерения размеров бревен, торцовочной пилы, накопителей и пульта диспетчера. Приемные транспортеры 1 и 2 служат для приема партий бревен и выдачи их по одному на конвейеры. Распилка бревна на пилоблоки осуществляется на позиции распила. Имеется позиция измерения, расположенная на конвейере 2. При прохождении бревна через систему ультразвуковых датчиков проводится замер диаметра бревна через каждые 5 см длины. Профиль бревна высвечивается на ЭВМ оператора, который, исходя из портфеля заказов, решает, как его распилить. Для этого он анализирует портфель заказов и, используя свой опыт (эвристики), ставит на экране ЭВМ .метки для распилки.

Транспортер 3 служит для передачи пилоблоков с конвейера 3 на конвейер 4. Вдоль конвейера 4 расположены 28 накопителей (име.ющие номера с 1 по 28) для пилоблоков различной длины. Накопители 29 и 30 служат для остатков от бревен после распила. Таким образом, на вход участка поступают партии бревен, которые затем пилятся по одно.му в произвольном порядке, а на выходе накапливаются пилоблоки.

Бревно условно представляется как усеченный конус, размеры которого полностью известны после прохождения бревна через позицию измерения (см. рис. 8.28). В сечении бревно круглое или эллиптическое. Искривление бревен в данной постановке не учитывается, что отвечает, по статистическим данным фирмы, приблизительно 90% случаев в реальном производстве. Длина бревна может достигать 24 м.

В каждый .MO.MCHT времени t в системе имеется множество заказов, образующих портфель заказов {N^ (t) — число заказов в момент времени t):

Каждый і-ш заказ из множества Zi (t) G Z (t) содержит в общем случае несколько позиций:

где щ — число позиций в заказе.

Каждая j-я позиция і-го заказа имеет следующие атрибуты:

где kij — число изделий j-ro вида в і-м заказе; ti — время его поступления в систему; Ті — плановый срок выпуска заказа; Xij — дополнительные свойства: вид древисины, класс качества изделий, сорт древесины и др.; Hij, Wij, Lij —соответственно высота, ширина и длина j-ro изделия, они определяются существующим стандартом, например, D1N 4070 (табл. 8.2).

В процессе проведения исследований разработана имитационная модель участка распиловки бревен с использованием интеллектуального языка имитационного моделирования РДО [207].

Специфика данной задачи требует рассмотрения большого числа возможных компоновок заказов в распиливаемом бревне. Учитывая, что время на обработку данных и принятие решения ограничено малым временем прохождения распиливаемого бревна от точки измерения до пилы, получаем оптимизационную задачу с ограничением на время принятия решения. Решения желательно принимать не дольше чем, за 10-15 с. В противном случае возникающие простои существенно снижают эффективность работы участка.

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

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

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

каждому пилоблоку присваиваем двоичный порядковый номер, соответствующий гену в генетическом алгоритме (рис. 8.30, б). Из полученных генов случайным образом составляется особь (в понятиях задачи особи соответствует бревно). Так как бревно не может превышать по длине 24 м, а пилоблок (согласно ГОСТу) не превышает 3 м, то особь состоит из восьми генов. Из получаемых вариантов особей формируется популяция (рис. 8.30, в).

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

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

В качестве оптимизируемой величины (функции пригодности) был применен коэффициент использования материала (КИМ) по объему. Как ограничение использовали КИМ по длине, что не помешало ему иметь высокие значения в процессе решения.

КИМ по объему определяется как суммарный объем пилоблоков, деленный на объем бревна:

КИМ' бревна по длине Uf равен суммарной длине пилоблоков, деленной на длину бревна, из которого они выпилены. Этот критерий можно использовать, если есть заказы на изделия большой длины:

где Lpk^Vpk — длина и объем к-то пилоблока соответственно; Lt^Vt — длина и объем бревна соответственно.

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

Воспроизведение. Каждой особи в популяции присваивается соответствующее по величине значение функции пригодности. В качестве таковой используется величина КИМ, которую необходимо оптимизировать. Цель воспроизведения состоит в том, чтобы отобрать для дальнейшей работы «сильнейшие» особи. Реализуется это с помощью простейшей рулетки (розыгрыша). Чем больше функция пригодности, тем больший сектор на рулетке получает данная особь, т. е. тем большая вероятность для данной особи воспроизвести в новой популяции свою копию. Рулетка раскручивается столько раз, сколько особей в популяции, после чего получается очередная новая популяция.

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

Мутация. Данный оператор сдерживает распространение особо «сильных» особей в популяции на первых поколениях с целью гарантированного непопадания в локальный оптимум. Для этого оператор мутации инвертирует определенное число битов в популяции на противоположные. Применение генетических операторов для поставленной задачи раскроя имеет некоторые особенности. При воспроизведении розыгрыш воспроизводимых особей реализуется с помощью случайного выбора на суммарном поле значений функции пригодности. Мутация представляется отношением числа измеренных битов к общему числу битов в популяции. Это соотношение при разработке ПГА выбирали экспериментальным путем при реализации алгоритма на единичных бревнах.

Структурная схема ПГА представлена на рис. 8.31. Для учета физической реализации особи были введены так называемые «штрафы», которые уменьшали значение функции пригодности особи, если та не удовлетворяла ограничениям по длине или диаметру.

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

с использованием алгоритма осуществлялась имитация распиловки на портфелях из 10, 20, 30, 50 и 100 заказов и он был модифицирован с учетом оптимальных значений параметров. Представленный на рис. 8.31 циюі поиска осуществляется до тех пор, пока не будет исчерпан весь портфель заказов. Время работы алгоритма для указанных портфелях заказов составило несколько секунд, что меньше требуемого.

На рис. 8.32 приведен вид интерфейса оператора, где представлен результат раскроя очередного бревна.

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

ными экспертами. Критериями служили коэффициенты использования материала по объему и длине. Пакет считался выполненным, когда в нем не оставалось ни одного невыполненного заказа. При этом число бревен, идущих на одинаковые пакеты заказов, у каждого алгоритма отличалось. В качестве итоговой оценки для сравнения брали среднее значение по КИМ всех распиленных бревен. Сравнительные результаты приведены в виде графиков на рис. 8.33. Чем больше заказов в пакете, тем лучшие показатели обеспечивают практически все из сравниваемых алгоритмов, что объясняется большим числом возможных сочетаний изделий в пилоблоке. Простой генетііческий алгоритм показывает устойчиво лучшие результаты при использовании в качестве критерия КИМ по длине (до 95% использования длины бревна). При оптимизации КИМ по объему столь явного преимущества не наблюдалось.

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

Рассмотрим влияние размера популяции (поколения) на показатели работы системы. Условия экспериментов были следующими: число заказов N = 20; число поколений Nz{t) = 5; вероятность скрещивания рс = 0,6; вероятность мутации рт = 0,03. На графиках (рис. 8.34) приведены средние значения показателей для раскроя бревна и их среднее квадратітческое отклонение. Размер популяции принимался равным 20, 40, 100 особям.

В результате экспериментов можно сделать вывод, что увеличение поколения выше 40 особей не рационально, так как ведет к увеличению времени

 

расчетов и лишь к незначительному улучшению качества раскроя.

Влияние изменения числа заказов в системе на показатели ее работы представлено на графиках (рис. 8.35). Условия экспериментов были приняты следуюш,ими: число поколений = 10; рс = 0,6; рт = 0,03. Представлены средние значения показателей для бревна, их среднее квадратическое отклонение по раскрою 100 бревен. Число заказов N изменялось от 5 до 50. Размер популяции принимал значения 20 и 40 особей.

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

 

с использованием генетической оптимизации. Показатели использования материала по длине и по объему с увеличением числа заказов больше 10 улучшаются незначительно.

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