8.3. Решение задачи плоской раскладки

В производстве одними из типовых являются задачи рационального раскроя и раскладки материала. Постоянный рост цен на материалы требует минимизации отходов при производстве изделий. Как правило, в качестве критерия эффективности принимается коэффициент использования материала (КИМ'Х Оптимальный раскрой промышленных материалов как научное направление получил начальное развитие в трудах Л. Канторовича

[202]. Для решения задач раскроя и размещения предложено много матема™ тических методов, однако все они ориентированы на решение статической задачи, когда исходная информация заранее полностью известна и не меняется в процессе производства. На производстве лишь 40% подобных задач решается автоматизировано с привлечением строгих математических методов.

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

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

Если не рассматривать организационные особенности производства, то задача по раскрою материала формулируется так: необходимо выбрать из портфеля заказов некоторое коліічество блоков и с учетом направленности пленки уложить их на поверхность плиты пресса; при этом необходимо добиться уменьшения потерь пленки. Так как потери материала должны быть минимальными, соответственно КИМ необходимо максимизировать. Он определяется согласно следующей формуле:

где 5бл — суммарная площадь всех блоков, уложенных на поверхность плиты пресса перед прессованием; ^пл — площадь поверхности плиты пресса.

Для того, чтобы оценить качество расчетного (полученного в результате решения задачи) коэффициента, необходимо знать его теоретически максимальное значение, поскольку во многих случаях достижение КИМ' = 1 невозможно. Зная это значение, и сравнив его с полученным, при решении задачи, можно сделать вывод о качестве полученного раскроя. Для решения задачи используем гибридную систему, включающую имитационную модель и блок генетической оптимизации (см. рис. 5.2 и 5.3).

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

торое должно быть близким к оптимальному или равно ему. Для решения задачи оптимизации КИМ использован ПГА. Основу имитационной модели составляет алгоритм, реализуюш,ий укладку блоков. Он описывает работу системы, т. е. проверяет возможность укладки очередного блока и осуществляет ее. Исходными данными для него являются значения номеров блоков, которые выдает алгоритм оптимизации, т. е. ГА [203]. Каждый блок имеет в портфеле заказов свой идентификационный номер, который точно его определяет. Для реализации процесса укладки блоков на поверхность плиты пресса необходимо определить номера блоков, которые нужно выбрать из портфеля заказов, и найти очередность их укладки на пресс. Каждому блоку в портфеле заказов ставится в соответствие его порядковый номер, который принимает значения от О до коліічества блоков в портфеле заказов. Именно с порядковыми номерами и работает оптимизационный алгоритм, пріічем один набор порядковых номеров представляет собой отдельное решение, которое реализуется имитационной моделью и для которого определяется КИМ.

При каждом запуске система должна автоматически определять длину строки-хромосомы. Коліічество генов в каждой особи равно числу блоков в таблице невыполненных заказов. Способ кодирования значений номеров блоков в двоичную форму для работы генетического алгоритма представлен на рис. 8.9. Предположим, что в текущий момент в портфеле заказов находится 15 блоков. Тогда особь представляет собой битовую строку- хромосому длиной 60 бит. Гены в этой строке имеют длину по 4 бита. Гены представляют собой закодированные значения порядковых номеров блоков. Каждый ген имеет длину 4 бита из условия возможности кодирования максимального номера блока (в данном случае 4 бита обеспечивают кодирование в двоіічной форме числа 15). Коліічество генов равно числу блоков, т. е. равно 15. Таким образом, каждая особь — это одно решение, в которой отдельный ген определяет порядковый номер для соответствующего блока.

Оптимизируемой веліічиной для генеттеского алгоритма является целевая функция, рассчитываемая для особей. Поэтому необходимо выбрать такую целевую функцию, которая растет с увеличением значения критерия, в качестве которого используется КИМ. Данная функция была выбрана на основании проведенных экспериментов с моделью, исходя из условия обеспечения правильного развития популяции. Она равна: ЦФ = (КИМ)^.

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

•    количество особей в популяции — 30;

•    вероятность скрещивания — 0,6;

•    вероятность мутации — 0,3.

Момент остановки работы генетического алгоритма определялся из условия:

где ЦФтах — максимальное значение целевой функции в текущей популяции; ЦФср — среднее значение целевой функции в текущей популяции.

Алгоритм укладки блоков на поверхность пресса является основой имитационной модели. Исходными данными для его работы является набор порядковых номеров блоков, рассчитанных генетическим алгоритмом (рис. 8.10).

Рассмотрим функции отдельных блоков алгоритма:

•    Расшифроет битое. Здесь осуществляется расшифровка строки-хромосомы, т. е. определение порядковых номеров.

•    Выбор очередного порядкового номера и сущеатуютли блоки с дан- нылі порядковылі ноліеролі? Первый блок схемы ведет счет порядковых номеров блоков в портфеле заказов. Второй проверяет, есть ли блоки с данным порядковым номером. Если такие (такой) блоки существуют, то идем дальше; если нет, то определяем следующий порядковый номер.

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

•    Существуют варианты укладки блока? и Укладка блока. Если не существует вариантов укладки блока на поверхность плиты пресса, то данная особь заканчивает обрабатываться. Если такие варианты укладки существуют, то происходит укладка одним из двух способов. Укладка блока производится по наименьшей координате, т. е. когда расстояние от левого верхнего угла блока до левого верхнего угла поверхности пресса наименьшее.

•    Данный блок последний? и Расчет ЦФ, Если данный блок последний, то производится расчет ЦФ для особи, если нет, то производится выбор блока со следующим порядковым номером.

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

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

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

Критерием оценки качества получаемого решения в данной модели является КИМ. Поэтому, чтобы оценить качество получаемого решения, использовались специально подобранные портфели заказов. Каждый портфель заказов составлялся из таких наборов блоков, для которых существовали варианты укладки с КИМ = 1. Для указанных выше параметров генетического алгоритма система в 90% случаях находила решения, при которых КИМ > 0,95, причем в некоторых случаях были получены оптимальные решения, то есть, КИМ = 1.

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

заказы делятся на два типа: срочные и обычные. Очевидно, что срочные заказы должны выполняться в первую очередь и это необходимо учитывать при составлении карт раскроя.

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

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

где /1^1 — параметр, учитывающий срочность заказа; К2 — параметр, учитывающий приоритет заказа; — параметр, определяющий КИМ (т. е. Кз = КИМ); щ — весовые коэффициенты, г = 1,2,3.

Для расчета параметра К\ необходимо учитывать срочность заказа для блоков, укладываемых на поверхность пресса. На входе системы все гарнитуры делятся на два типа: срочные и обычные. Так как при составлении портфеля заказов гарнитуры разбиваются на блоки, то все блоки по срочности заказа также делятся на два типа: срочные и обычные. В модели системы при описании каждого блока присутствует параметр срочность, который является булевой переменной и может принимать значения О или 1. Именно эти значения используются для нахождения параметра которое производится следующим образом: для вновь создаваемой карты параметр К\ изначально равен 0; для каждого блока, входящего в данную карту, к значению К\ прибавляется значение параметра срочность. Таким образом, значение К\ равно числу срочных блоков в данной карте раскроя.

Расчет параметра К2 осуществляется аналогично расчету параметра /1^1, только для этого используется значение приоритета блока. В описании каждого блока имеется параметр приоритет, который также является булевой переменной и может принимать значения О или 1. В отличие от параметра срочность, который задан и не меняется во время работы системы, параметр приоритет изначально для каждого блока имеет значение О и увеличивается по мере формирования карт раскроя. В данной схеме принцип увеличения приоритета задан в виде пороговой одноступенчатой функции, значение которой изменяется на 60%. Это значит, что когда число готовых блоков данного гарнитура составляет 60% или более от общего числа блоков в гарнитуре, то для оставшихся (невыполненных) блоков данного гарнитура приоритет становится равным I.

Параметр представляет собой КИМ и рассчитывается точно так же, как и ранее.

Весовые коэффициенты щ определяют значимость каждого из парамет™ ров, входящих в формулу для расчета ЦФ. Так как условия производства часто меняются, то для того, чтобы система была более гибкой, значения весовых коэффициентов вводятся пользователем через интерфейсный блок. Таким образом, пользователь сам может определять значимость каждого параметра в зависимости от ситуации. Для проведения исследований весовые коэффициенты были выбраны следующие: аі = 10; а2 = 1; «з = 5.

 

 

 

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

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

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

где N — количество не уложенных блоков в портфеле заказов; D — некоторый параметр (делитель).

Как видно из выражения, для определения количества точек разрыва и точек мутации необходимо знать значение делителя. Данный параметр был найден в результате исследований: D =

= 10.

Далее представлены результаты исследований системы при различном числе блоков в портфеле заказов, соответственно 20, 50 и 100 блоков.

Первые две гистограммы гшлюстри- руют работу «старого» алгоритма, причем рассматривается не только изменение ЦФ по поколениям, но и число срочных блоков в карте (рис. 8.12 и 8.13). Следующих две гистограммы отражают работу модернизированного алгоритма (рис. 8.14 и 8.15).

 

На рисунке 8.16 приведен график зависимости значения максимальной ЦФ от значения делителя в формуле для расчета количества точек разрыва и точек мутации. Как видно из графика, существует некоторое оптимальное значение данного параметра.