Модели и методы оптимизации упаковки N-мерных параллелепипедов

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

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

Диссертационная работа посвящена построениям точных алгоритмов решения задач раскроя-упаковки. Методы, нацеленные на получение оптимального решения этой проблемы, до сих пор остаются мало изученными. Причиной этого является КРполнота рассматриваемой задачи в сильном смысле (задача линейного целочисленного раскроя в частном случае дает задачу 3-РАЗБИЕНИЕ), так что мало надежды на отыскание даже псевдополиномиального точного алгоритма решения этой задачи. На данный момент теория ЫР задач говорит, что для нахождения оптимального решения рассматриваемых задач существует только один путь — полный перебор всех допустимых вариантов и выбор из них оптимального [37].

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

Диссертация посвящена разработке точного алгоритма решения задачи линейного целочисленного раскроя (ЛЦР), базирующегося на методе ветвей и границ, и его программной реализации-, созданию оптимизационного алгоритма решения задачи упаковки Имерных прямоугольных параллелепипедов в полубесконечную область.

Научная новизна диссертационной работы заключается в следующем: разработан точный алгоритм решения задачи линейного целочисленного раскроя, базирующийся на методе ветвей и границ. разработан и применён метод группировки для решения задач ЛЦР с большим количеством типов заготовок, подтвердивший свою эффективность в вычислительных экспериментахразработана математическая модель задач упаковки 1М-мерных прямоугольных объектов (N>2) в полубесконечную область. разработан метод решения задач упаковки Ы-мерных прямоугольных объектов.

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

Результаты работы и отдельные её разделы докладывались и обсуждались: на 10-й Байкальской школе-семинаре «Методы оптимизации и их приложения» (1995, г. Иркутск), на семинаре в Институте вычислительной математики Дрезденского технического университета (1996г. г. Дрезден ФРГ), на международной конференции по исследованию операций (1998, г. Новосибирск), на семинарах кафедры Вычислительной математики и кибернетики Уфимского авиационного технического университета.

В первой главе диссертации изложена общая классификация задач раскроя-упаковки. Приводится краткий обзор методов решения задачи раскрояупаковки (11−11).

В основу классификации моделей положены известные работы Л. В. Канторовича и В. А. Залгаллера, Э. А. Мухачевой, И. Терно и Дикхофа .

С учетом. приведенной классификации задачи, рассматриваемые в диссертационной работе, могут быть представлены как 1/У/1/М. [5].

Среди работ, посвященных линейному раскрою, выделяется статья Г. Вешера [33], в котором приводятся результаты вычислительных экспериментов для ряда алгоритмов с указаниям для них наиболее трудных классов задач.

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

Задача линейного целочисленного раскроя состоит в следующем:

Одномерные материальные предметы одинаковой длины Ь (прутки) должны быть разделены на меньшие части (заготовки) требуемых длин /1,/2,.,/т, так чтобы удовлетворить заказанные потребности Ь1, Ь2,., Ьт. При этом требуется минимизировать общее количество используемого материала.

План раскроя — матрица, столбцы которой отвечают раскрою прутков (карты раскроя), а строкизаготовкам. а11 а21%1 1 ак1 а12 а22 а32 1 ак2.

Е1п а2п а3п 1 акш а, — количество г-о вида заготовок в]-м раскрое прутка — К — количество прутков в раскрое;

Как уже было отмечено, данная задача является №>- полной в трудном смысле. Поэтому для её решения приемлем только один подходполный перебор всех допустимых вариантов и выбор из них оптимального.

Идея базовой схемы, предложенной А. Кацевым [47], состоит в следующем: методом полного перебора ищется такое размещение заготовок в прутках, чтобы суммарный остаток не превосходил допустимого резерва. Если это удаётся, то рассчитывается новое значение допустимого резерва затем перебор продолжается. В случае когда достигнута нижняя граница или перебор не дал результата, работа алгоритма останавливается и текущее значение верхней границы будет оптимальным результатом.

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

1 2 План раскроя, А считается эквивалентным плану, А в том случае, если они состоят из одних и тех же карт раскроя и отличаются только порядком их расположения.

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

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

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

Очевидно, что данное ограничение не может отсечь оптимальный план и поэтому оно приемлемо для использования в оптимальном алгоритме. Не трудно убедиться, что применения этого ограничения снижает трудоемкость алгоритма по сравнению с начальной схемой в К! — раз. Сложность представленного алгоритма: где: кколичество карт раскроя, входящих в плант- общее количество заготовок. т/к — среднее количество заготовок, входящих в одну карту раскроя.

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

Очевидно, что любая классическая задача, где каждой заготовке 4 соответствует некоторая комплектность Ьк > легко преобразуется в Р-задачу путем включения заготовки длины 1кЪк раз.

Пусть даны две задачи Р 1={Ь, 1п, т1) и? г=(Щ2рт2), ге 1. ть]е 1. т2 где Ьдлина’пруткат/, т2- количество заготовок в задачах Р1, Р2- 1Н, 12] - длины заготовок в задачах Р1, Р2.

Задача Р1 доминирует над Р2, если каждой заготовке из Р1 можно сопоставить заготовку из Р2, чтобы для каждой из получившихся пар выполнялось условие 1ц <12] для всех ге 1. т и некоторых{1,2,. , т2} при этом каждой заготовке из Р2 сопоставляется не более чем одна из Р1.

Пусть Х*(Р) — количество прутков в оптимальном целочисленном решении задачи Р. Тогда очевидным является утверждение: Если задача Р1={Ь, 1ц, т/) доминирует над У2-(Ь, 12], т2), то выполняется неравенство Ъ*{Р1)<�Х*(Р2).

Данное свойство означает, что решив некоторую задачу Р1 можно выделить множество задач оптимальные решения которых «не лучше» чем уР1.

Базируясь на этом свойстве задачи ЛЦР, можно построить дополнительное отсечение. Идея его заключается в том, что бы на каждом шаге работы алгоритма проверять получаемые подзадачи на доминантность и отсекать при. этом неперспективные.

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

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

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

Известно, что задача линейного целочисленного раскроя (ЛЦР) является задачей линейного целочисленного программирования (ЛЦП) с неявно заданной матрицей ограничений.

Обозначим через: Е = (1,т, 1, Ь) задачу ЛЦР, где Ьдлина прутка, т-количество типов заготовок, 1=(11,12—, 11Г) и Ь=(Ь1,Ь2>. Ьгп) — длины и комплектности заготовок соответственно.

Тогда отвечающая ей задача ЛЦП можно сформулировать следующим образом :

Требуется найти совокупность раскроев г-> г2^, их количество п и вектор интенсивностей их применения х = (х1,х2,., хп) удовлетворяющих условиям:

1°. > О, целые у = 1 ,., пп п.

3°, г (х) =. достигает минимума.

7 = 1 7.

Где, известны всевозможные способы раскроя прутка (карты раскроя) a (rj) = {aj->aj2>-~>ajm) J= каждый из которых представляет собой т — мерный вектор и — количество заготовок вида i, вырезаемых в jм способе раскроя.

Данную задачу можно представить как частный случай модели стандартной линейной целочисленной минимизации: z = cTXmitl^AX = b, x > 0, целые, а соответствующая ей задача линейного программирования имеет вид: z = сТх —> min, Ax>b, x> 0.

Обозначим: z (Е) — оптимальное значение целочисленной задачиzc (E)~ оптимальное значение соответствующей задачи линейного программирования (ЛП).

Говорят, что задача линейного целочисленного раскроя Е обладает свойством округления до целого вверх (IRUP) [23], если zE) = [zc (E)1.

Для проверки свойств IRUP некоторой задачи ЛЦР эффективно построение так называемой остаточной задачи. Имеем некоторую задачу раскроя E = (m, L, l, b) и пусть Xеинтенсивности планов раскроев, определяемые «из оптимального решения соответствующей задачи ЛП: z = eTxc —> min, Ах = b, xc > 0.

Тогда задача Е = (l, т, 1, Ь-а[хс J) является остаточной к е.

И. Терно [26] было показано, что для выполнимости свойства IR «U Р некоторой задачи Е, достаточно доказать IR U Р для соответствующего остаточного случая Е.

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

В связи с этим схема применения переборного алгоритма будет выглядеть следующим образом: Пусть дана некоторая задача Е :

1. Симплексалгоритмом решается соответствующая ей задача ЛП z = етх -" min, Ах = b, х > 0.

2. Исходя из решения задачи ЛП формируется задача остатка.

E = (m, l, L, b-A[xc J).

3. Решается задача остатка переборным алгоритмом.

4. Если задача остатка обладает свойством IRUP, то оптимальное решение найдено, иначе для получения оптимального решения необходимо применить переборный алгоритм для всей задачи Е .

Описанная схема во многих случаях позволяет находить оптимальные решения для задач с большой комплектностью заготовок. Однако, когда число типов заготовок велико (>100), а требуемая их комплектность мала (<5), данная схема будет работать неэффективно, т.к. задача остатка практически не будет отличатся от исходной задачи и применение ЛП не позволит сократить размерность задачи Е которую необходимо решать переборным алгоритмом.

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

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

1. Е доминирует над Ег.

2. Выполняется условие.

3. Задача Ег — обладает свойством Ш1/Р.

Если задача Ег удовлетворяет условиям 1,2,3, то значения оптимального целочисленного решения задач Е и Ег совпадают т. е (2*(Ег)=?*(Е)).

В силу того, что задача Ег содержит меньшее число типов заготовок по сравнению с Е, задача остатка Ег будет иметь меньшую размерность чем.

Е, а следовательно, время, затрачиваемое на её решение, уменьшается.

Очевидно, что из решения 2*(Ег) и соответствующего ему плана раскроя получается план раскроя, удовлетворяющий условию задачи Е, с выполнением условия (2*(Ег)=2*(Е)). Это следует из доминантности задачи Е над Ег. (Получение окончательного решения осуществляется путем замены заготовок в плане раскроя для задачи Ег на парные им, но имеющим не большею длину из Е).

Применяемая в диссертационной работе процедура группировки, позволяет в большинстве случаев находить оптимальные решения для примеров, содержащих 300−400 типов заготовок. Ранее еще не удавалось получать оптимальные результаты для задач такой размерности.

В третей главе рассматривается задача 1Г-мерной упаковки. Приводится постановка задачи и её математическая модель. Для возможности построения алгоритма решения вводится дополнительная задача заполнения. Дается определение связанного множества задач заполнения. Приведен ряд теорем, показывающий соответствие между задачей мерной упаковки и связанным множеством задач заполнения.

В общем случае задачу И-мерной прямоугольной упаковки можно описать в следующем виде: Дано :

1. N >1 — мерность евклидова пространства.

2. Полубесконечный КГмерный прямоугольный параллелепипед с основанием 0=(01,02,., 0н-1).

3. Набор состоящий из т Ы-мерных прямоугольных параллелепипедов Р1=(р1Ьр12,., рш), Р2=(р2ьР22,", Р2к), —, Рт=(ртьРт2,—, Рты) (заготовки), где ру-длины ребер.

Назовем прямоугольной упаковкой Р1, Р2,.Рт в О такое расположение заготовок внутри О (когда ни одна из заготовок не выходит за пределы области О), при котором выполняются следующие условия :

1. Грани заготовок расположены параллельно граням О.

2. Заготовки между собой не пересекаются. положительное число, отвечающее условию, что все заготовки упаковываются в прямоугольный параллелепипед (01,02,.¦ 1 .

Требуется: найти такую упаковку заготовок в О, в которой принимает наименьшее значение.

Для решения поставленной задачи было введено понятие задачи заполнения:

Для заданных значений Мг (<�Р>^о), где гнатуральное число от 1 до Ы;

Р>~ набор, состоящий из ш Ы-мерных векторов Р;

Ъодействительное положительное числотребуется найти бинарную матрицу Аг (ш х к) и вектор отвечающие определенным условиям:

• к<�ш;

• гг0=0-гг1>0 1=1.к.

— 1.

• ^ = 1ШП К *рп *2гд.

1.т, а, у=1) /=1 к.

• IX =Ри -1с1″ к.

1 к.

• У г. <г ^ П — О 1.

• Не существует такого X и что ай.]=1, %=0, для 1=1.к и к>ц>0. (Условие непрерывности расположения «единиц» в строках матрицы А) .

Геометрический смысл матрицы, А заключается в следующем: Каждый столбец (кортеж) матрицы, А характеризует некоторое сечение параллелепипеда О (1Г-1)-мерной гиперплоскостью, где Аг (1^)=1 означает, что ]-тая плоскость пересекает заготовку Р^.

— это расстояние между двумя соседними секущими плоскостями. Секущие плоскости проводятся по г-тым «задним» граням.

Для установления связи между задачей заполнения и искомой упаковкой вводится следующее определение:

Множество задач (М^^Р^О, М2(<�Р>, г2), ., Мм (<�Р>, гн)) называется связанным, если не существует таких 1 и что для любого г=1.ЛЧ найдется такое 8 Г, при котором будут верны следующие условия АГ (8ГД)=1 и.

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

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

Теорема 1. Любую М-мерную упаковку X можно представить в виде связанного множества (М1(<�Р>, 01), М2(<�Р>, 02),., МК (<�Р>, 2Н (Х)). Теорема 2. Каждому связанному множеству (М}(<�Р>, 01), М2(<�Р>, 02),., Мм (<�Р>, 2м)) соответствует некоторая упаковка X, в которой.

Теорема 3. Связанное множество, при котором достигается минимальное значение Ъц, соответствует оптимальной упаковке.

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

Нахождение допустимых матриц А,. и2гв задаче заполнения Мг (<Р>, сводится к решению задачи линейного раскроя (ЛР) с дополнительными ограничениями, накладываемыми на план раскроя: 1°. Матрица плана раскроя должна быть бинарной.

2°. Непрерывность заполнения по строкам — все единицы в строках должны располагаться друг за другом.

При этом требуется найти не минимальное значение затраченных прутков (сумма интенсивностей), а только уменьшить его до порогового значения (70).

Получившийся план раскроя и будет искомая матрица Аг, а интенсивности карт раскроя — вектор Ъг.

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

1. Основные действия выполняются с бинарными матрицами (особенно важно при реализации на ЭВМ).

2. Требуемая память растет линейно в зависимости от мерности рассматриваемых объектов.

3. Гибкостьвозможность модификации при изменении геометрии рассматриваемых объектов или целевой функции.

В четвертой главе дана конкретизированная постановка задачи двумерной прямоугольной упаковки в полубесконечную полосу. Приведен алгоритм для случая N=2. В алгоритм так же были введены дополнительные отсечения, базирующиеся на геометрических свойствах рассматриваемых объектов и позволяющие существенно повысить производительность. Приведены результаты вычислительных экспериментов, проведено сравнение с методом зон Липовецкого [50].

Заключение

.

Диссертационная работа посвящена разработки точных алгоритмов упаковки 14- мерных прямоугольных параллелепипедов. Отдельно были рассмотрены случае когда N=1 и N>2 и показана сводимость второй ситуации к первой. Программная реализация представленных алгоритмов позволяет решать большой круг практических задач. Основные научные результаты диссертационной работы состоят в следующем :

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

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

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

4. Разработана математическая модель И-мерной прямоугольной упаковки параллелепипедов (N>2).

5. Введены понятиязадача заполнения и связанное множество задач заполнения. Показано, что задача заполнения является задачей ЛЦР с дополнительными ограничениями.

6. Доказан ряд теорем, показывающий связь между связанным множеством задач заполнения и задачей 14-мерной прямоугольной упаковки параллелепипедов (N>2).

7. Разработан алгоритм связанных заполнений (СЗ) для точного решения задачи Ы-мерной прямоугольной упаковки параллелепипедов (N>2).

8. Программно реализован СЗ-алгоритм для случая N=2. Проведены вычислительные эксперименты, подтверждающие перспективность данного подхода.