Содержание к диссертации
Введение
ГЛАВА 1. Модели и методы решения задач ортогональной упаковки и раскроя 18
1.1. Основные модели упаковки и раскроя 18
1.2. Обзор методов решения задач одномерной, двухмерной и трехмерной упаковки и раскроя 32
1.2.1. Использование методов математического программирования 32
1.2.2. Применение методов комбинаторной оптимизации 33
1.2.3. Приближенные и эвристические методы 35
1.2.4. Вероятностные методы локального поиска оптимума 48
Выводы по первой главе 55
Задачи, решаемые в диссертационной работе 56
ГЛАВА 2. Конструктивный метод динамического переборадля решения задач ортогональной упаковки 58
2.1. Метод динамического перебора для решения задачи одномерной упаковки 58
2.2. Метод динамического перебора для решения задач прямоугольной упаковки 73
2.2.1. Гибридный метод динамического перебора для решения задачи прямоугольной упаковки 82
2.2.2. Метод динамического перебора с элементами стохастики для решения задач прямоугольной упаковки 92
2.3. Метод динамического перебора для решения задачи параллелепипедной упаковки 95
Выводы по второй главе 111
ГЛАВА 3. Конструктивные методы решения задач прямо угольной упаковки на базе метаэвристики муравьиной колонии 113
3.1. Методы решения задач прямоугольной упаковки на базе метаэвристики муравьиной колонии 113
3.2. Гибридизация алгоритма муравьиной колонии и динамического перебора для решения задач прямоугольной упаковки 131
Выводы по третьей главе 141
ГЛАВА 4. Некоторые эвристические методы для решения задач линейного и гильотинного раскроя 142
4.1. Метод перебора с усечением для решения задач одномерной упаковки 142
4.2. Метод на базе процедур алгоритма имитация отжига для решения задач прямоугольного гильотинного раскроя 153
4.3. Практическое применение метода перебора с усечением и метода на базе процедур имитации отжига 160
Выводы по четвертой главе 168
ГЛАВА 5. Экспериментальное исследование и анализ разработанных методов упаковки и раскроя 170
5.1. Анализ и выбор методик исследования предлагаемых алгоритмов упаковки и раскроя 170
5.2. Анализ эффективности алгоритмов перебора с усечением и динамического перебора для решения задачи одномерной упаковки 176
5.3. Анализ эффективности алгоритма динамического перебора для решения задачи двухмерной упаковки 190
5.4. Анализ эффективности алгоритма муравьиной колонии для решения задач двухмерной упаковки 201
5.5. Анализ эффективности для решения задач прямоугольного раскроя на базе процедур метаэвристики имитации отжига 215
5.6. Анализ эффективности алгоритмов для решения задач параллелепипедной упаковки 216
5.7. Практическое применение разработанных алгоритмов и программ для решения задач параллелепипедной упаковки 232
Выводы по пятой главе 241
Заключение 243
Литература
- Обзор методов решения задач одномерной, двухмерной и трехмерной упаковки и раскроя
- Метод динамического перебора для решения задач прямоугольной упаковки
- Гибридизация алгоритма муравьиной колонии и динамического перебора для решения задач прямоугольной упаковки
- Практическое применение метода перебора с усечением и метода на базе процедур имитации отжига
Введение к работе
Современный период развития производственных технологических процес-' сов характеризуется оптимизацией этапов жизненного цикла продукции, обусловленной динамически изменяющимся ассортиментом и номенклатурой изделий при ужесточении требований к себестоимости продукции. В этих условиях актуальным является решение оптимизационных задач упаковки и раскроя. Современное производство характеризуется необходимостью тщательного анализа и экономии требуемого расхода материала на этапе проектирования изделия, а также разнообразным ассортиментом деталей и изделий. Задачи упаковки и раскроя в условиях единичного производства возникают при индивидуальном производстве изделий, как правило, из дорогостоящих материалов, при планирова-I нии размещений различных предметов в контейнерах, при этом конструирование таких размещений и раскроев представляет далеко не тривиальную задачу.
В рамках класса задач упаковки и раскроя все проблемы объединены единой логической основой, а именно: наличием двух видов объектов - малых и крупных, для которых решается задача оптимального размещения малых объектов в крупные.
Как известно, задачи упаковки и раскроя относятся к классу целочисленных задач математического программирования. Классические методы линейного программирования решения задач упаковки и раскроя, успешно применяемые в условиях массового производства, в условиях единичного производства трудно применимы.
Фундаментальные научные результаты в области решения задач раскроя в условиях массового производства принадлежат Л.В. Канторовичу и В.А. Залгал-леру. Результаты дальнейших исследований в этой области отражены в работах В.А. Булавского и М.А. Яковлевой, Э.А. Мухачевой, И.В. Романовского, В.А.
Кузнецова, а за рубежом П. Гилмори и Р. Гомори, И. Терно и Г. Шайтхауэра и
др.
Задачи раскроя и упаковки, ориентированные на единичное производство, относятся к классу iVP-трудных задач комбинаторной оптимизации, т.е. для их решения нет методов и алгоритмов, находящих точное решение за полиномиальное время. Существующие точные методы решения задач упаковки и раскроя основаны на схеме полного перебора, поэтому они оказываются мало пригодными для решения задач, встречающихся на практике. Асимптотически точные методы решения задачи одномерной и двухмерной упаковки разработаны Э.Х. Гимади, В.В. Залюбовским и другими авторами.
В связи с Л^-трудностью задач раскроя-упаковки одним из актуальных направлений исследований в настоящее время является разработка эффективных приближенных и эвристических методов. Среди них выделяются конструктивные методы, решение задачи строится покомпонентно, добавлением нового компонента к частично построенному решению до тех пор, пока оно не построено полностью и методы локального поиска оптимума, поиск локально оптимальных решений ведется в некоторой окрестности допустимого решения. Разработке эвристических методов локального поиска оптимума при решении задач упаковки и раскроя посвящены работы М. Дориго, И.П. Норенкова, Ю.А. Кочетова, Э.А. Мухачевой, Э. Фолкенауэра Э. и др.
На практике наиболее часто встречающимися задачами являются ортогональная упаковка и раскрой, где в качестве малых объектов выступают заготовки прямоугольной формы, ящики различных размеров, а в качестве крупных -материал, поступающий в виде рулонов, полос, прямоугольных листов, стержней, контейнеры различной емкости. В настоящее время разработано множество эвристических методов решения таких задач, что осложняет их выбор и оценку качества полученных решений при практической реализации в условиях единичного производства.
Таким образом, проблема разработки теоретической основы расчета рациональной упаковки и раскроя, направленной на унификацию методов поиска решений, является актуальной и своевременной.
Цель и задачи исследования
Целью диссертационной работы является разработка унифицированных методов для решения задач ортогональной упаковки и раскроя, обеспечивающих экономию материальных ресурсов в условиях единичного производства на основе конструктивных методов.
Для достижения указанной цели в работе поставлены и решены следующие задачи:
Разработать теоретические основы нового направления в создании унифицированных методов расчета для решения задач рациональной упаковки и раскроя в различных постановках.
Разработать унифицированный метод, позволяющий на общей теоретической основе создать математическое обеспечение для решения задач одномерной, прямоугольной и параллелепипедной упаковки и раскроя.
Разработать конструктивный метод и алгоритмы для решения задач одномерной упаковки и раскроя.
Разработать методы, алгоритмы для решения задач ортогональной упаковки и раскроя на базе известных метаэвристик.
Реализовать и внедрить полученные теоретические результаты в виде методик, алгоритмов и прикладного программного обеспечения на промышленных предприятиях и в учебном процессе.
Методы исследования
Результаты исследований, выполненных в работе, базируются на методе динамического программирования, основных понятиях и алгоритмах из теории графов, стандартных схемах метаэвристических методов. При разработке алгоритмов и программного обеспечения использовались принципы модульного и структурного программирования. Для оценки эффективности полученных результатов использовались стандартные методики оценки результатов численного эксперимента.
Основные научные результаты, полученные автором и выносимые на защиту
Теоретические основы расчета рациональной упаковки и раскроя, базирующиеся на модифицированном псевдополиномиальном алгоритме решения задачи 0-1 рюкзак, что позволяет решать задачу л-мерной упаковки (п = 1,2,3) в рамках единого подхода. Это обеспечивает высокое качество получаемых решений задач упаковки и раскроя, а также инвариантность к размерности решаемых задач.
Конструктивный метод динамического перебора на базе предложенной модификации метода решения задачи 0-1 рюкзак для прямоугольной упаковки в детерминированном и рандомизированном вариантах, позволяющий получать множество квазиоптимальных решений, что дает возможность осуществить выбор наиболее подходящего варианта в случае изменения технологических и организационных ограничений.
Конструктивный метод перебора с усечением для решения задач одномерной упаковки, обеспечивающий высокое качество решений и позволяющий повысить скорость поиска решения, что важно при решении задач большой размерности.
Методы и алгоритмы на базе известной конструктивной метаэвристики муравьиная колония для задач прямоугольной упаковки.
5. Математическое и программное обеспечение, реализующее разработанные конструктивные методы и позволяющее решать задачи /7-мерной упаковки (п = 1,2,3), возникающие в условиях единичного производства. Результаты анализа эффективности разработанного математического обеспечения для решения задач одномерной, прямоугольной и параллелепипедной упаковки, полученные на базе численного эксперимента.
Научная новизна результатов
Разработана теоретическая база создания нового унифицированного метода высокой эффективности для решения задачи ортогональной л-мерной упаковки («=1,2,3).
Предложен конструктивный метод динамического перебора для решения задач ортогональной упаковки. В отличие от существующих конструктивных методов он впервые основан на оптимизационном алгоритме 0-1 рюкзак и его гибридизации с эвристическими приемами.
Предложен конструктивный метод перебора с усечением для решения задачи одномерной упаковки большой размерности. Этот метод превосходит многие существующие алгоритмы по эффективности и временной производительности и почти всегда позволяет получать оптимальное или близкое к нему решение.
Для решения задач прямоугольной упаковки предложено применение конструктивной метаэвристики муравьиная колония. Это позволяет получать допустимые и близкие к оптимальным решения задач прямоугольной упаковки.
Разработано эффективное математическое обеспечение, основанное на предложенных методах и алгоритмах упаковки и раскроя в условиях единичного производства, позволяющее получить множество квазиоптимальных решений и служащее основой для внедрения программного обеспечения при решении оптимизационных задач упаковки и раскроя промышленных объектов.
Обоснованность и достоверность результатов диссертации
Обоснованность результатов, полученных в диссертационной работе, базируется на использовании апробированных научных положений и методов исследования, корректном применении математического аппарата, согласованности новых результатов с известными теоретическими положениями.
Достоверность полученных результатов и выводов подтверждается проведенными численными экспериментами.
Практическая значимость результатов
Практическая ценность результатов, полученных в диссертации, заключается в разработке:
методики решения задач одномерной упаковки на базе унифицированного метода, позволяющего создать гибкое математическое и программное обеспечение, легко адаптируемое к производственным условиям;
методики решения задач параллелепипедной упаковки на базе унифицированного метода, позволяющего создать гибкое математическое и программное обеспечение, легко адаптируемое к производственным условиям;
методического, алгоритмического и программного обеспечения решения задач поиска оптимальных решений упаковки и раскроя промышленных объектов, позволяющего сократить в 1,5-2 раза сроки подготовки оптимальных решений при упаковке и раскрое и повысить показатели эффективности при решении задачи ресурсосбережения на 5-10%.
Результаты диссертационной работы внедрены в виде методов, алгоритмов, методик и программного обеспечения на ООО «Уралтехнопроект» (г. Екатеринбург), 000 «ВИВ-ФАРМ» (г. Москва), ГУП УАП «Гидравлика» (г. Уфа), а также в учебном процессе Уфимского государственного авиационного технического университета.
Связь исследований с научными программами
Исследования проводились в рамках научных проектов №01-01-00510, №03-01-07002 Российского Фонда Фундаментальных исследований.
Апробация работы
Основные научные и практические результаты диссертации докладывались и обсуждались на следующих конференциях:
Международной научно-технической конференции «Актуальные проблемы математического моделирования и автоматизированного проектирования в машиностроении: МОДЕЛЬ-ПРОЕКТ 95», Казань, 1995;
Конференции «Комплексный анализ, дифференциальные уравнения, численные методы и приложения. Геометрические задачи», Уфа, ИМВЦ РАН,
I 1996;
1-Й Сибирских конгрессах по прикладной и индустриальной математике (ИНПРИМ-96,98), Новосибирск, 1996,1998;
16-ой Европейской конференции по исследованию операций, Брюссель, Бельгия, 1998;
Международной Сибирской конференции по исследованию операций, Новосибирск, 1998;
Международной конференции «Поддержка жизненного цикла в производственных системах», Бремен, Германия, 1998;
I Конференции «Математическое программирование и приложения», УрО
РАН, Екатеринбург, 1999,2003;
Первой Всероссийской научно-практической конференции по вопросам
решения оптимизационных задач в промышленности «Ресурсосберегающие тех-
нологии: математическое обеспечение оптимизационных задач в системах автоматизированного проектирования», С-Петербург, 2001;
Международной конференции «Дискретный анализ и исследование операций» (DAOR), Новосибирск, 2000, 2002, 2004;
16-ой международной конференции по исследованию операций, Эдинбург, Великобритания, 2002;
Международной конференции «Компьютерные науки и информационные технологии» (CSIT), Уфа, 2003-2005;
13-й Байкальской международной школе-семинаре, Иркутск, 2005;
Международной уфимской зимней школе-конференции по математике, Уфа, 2005;
Международном семинаре европейской группы по раскрою и упаковке (EuroSICUP), Порто, Португалия, 2006;
III Всероссийская конференция «Проблемы оптимизации и экономические приложения», Омск, 2006.
Публикации
Результаты диссертационной работы отражены в 80 публикациях, в том числе в одной монографии (в соавторстве), учебном пособии (в соавторстве), 31 статье, в том числе 8 статьях в изданиях из списка ВАК, 40 материалах международных и российских конференций, 2 свидетельствах государственной регистрации программ для ЭВМ.
Структура и объем работы
Диссертация состоит из введения, пяти глав основного материала, библиографического списка и содержит 265 страницы основного текста. Библиографический список включает 191 наименование литературы.
Краткое содержание работы
Во введении обосновывается актуальность темы исследований в области задач упаковки и раскроя промышленных материалов. Формулируется цель работы и решаемые в ней задачи, обсуждается научная новизна и практическая ценность выносимых на защиту результатов.
В первой главе проводится анализ существующих постановок и методов поиска рациональных решений в классе задач ортогональной упаковки и раскроя для условий единичного производства.
Рассмотрены задачи ортогональной л-мерной упаковки, где «=1,2,3 (Bin Packing Problem, ВРР) и раскроя (Cutting Stock Problem, CSP). В работе приводятся различные постановки задач ВРР и CSP. Основное внимание уделяется задачам одномерной, прямоугольной и параллелепипедной упаковке.
В работе приведен аналитический обзор различных методов решения задач ортогональной упаковки и раскроя: методы математического программирования, методы типа ветвей и границ, асимптотически точные методы, однопроходные и многопроходные эвристические методы, метаэвристики. Как показано в обзоре, большинство методов решения задач упаковки и раскроя развиваются в двух направлениях: ведется поиск локально-оптимальных решений в некоторой окрестности исходного допустимого решения с применением декодеров - алгоритмов, которые по закодированному решению восстанавливают эскиз упаковки и вычисляют значение целевой функции. Другим направлением является разработка конструктивных методов, имеющих дело с покомпонентным построением упаковки, а именно: к частично построенной упаковке добавляется новый компонент до тех пор, пока упаковка не будет построена полностью. В работе выполнено исследование в рамках этого направления.
На основе проведенного анализа методов и алгоритмов поиска оптимальных решений в классе задач ортогональной упаковки и раскроя для условий единичного производства сделан вывод о том, что в настоящее время в этой об-
ласти исследований существует ряд нерешенных задач.
Во второй главе разработаны теоретические основы расчета рациональной упаковки, базирующиеся на модифицированном псевдополиномиальном алгоритме решения задачи 0-1 рюкзак для решения задачи «-мерной упаковки (п = 1,2,3).
Предложен унифицированный конструктивный метод динамического перебора для решения задач одномерной и прямоугольной упаковки на базе модифицированного метода решения задачи 0-1 рюкзак в детерминированном и стохастическом вариантах, позволяющий получить множество различных упаковок с одним и тем же значением целевой функции
Предложена процедура перестройки, реализующая нужную перестановку прямоугольников для частного случая - безотходной упаковки - на базе алгоритма проверки планарности графа.
При разработке методов решения задачи параллелепипедной упаковки использовался известный подход, базирующийся на декомпозиции исходной задачи и сведении ее к задаче меньшей размерности путем разбиения упаковки на слои специальной структуры. В предложенных методах слои формируются с помощью метода динамического перебора, позволяющего получить более плотную упаковку в рамках слоя, а также множество различных упаковок с одним и тем же значением целевой функции.
В третьей главе предложены методы решения задач прямоугольной упаковки на базе конструктивной метаэвристики муравьиной колонии, а также гибридный метод, основанный на алгоритме муравьиной колонии и методе динамического перебора.
Разработан конструктивный метод для решения задач прямоугольной упаковки на базе метаэвристики муравьиной колонии. С целью получения более плотной упаковки прямоугольников разработан гибридный алгоритм на базе алгоритмов муравьиной колонии и алгоритма формирования множества кортежей в методе динамического перебора.
В четвертой главе диссертации разработан конструктивный метод перебора с усечением для решения задач одномерной упаковки и метод на базе процедур метаэвристики имитация отжига для решения задач прямоугольного гильотинного раскроя.
Разработан конструктивный метод перебора с усечением для решения задачи одномерной упаковки, в котором происходят направленные изменения частичного и построенного решения. Эти изменения основаны на переборе различных вариантов упаковки путем обмена предметов между контейнерами (разрешен обмен предмета из одного контейнера на один предмет из другого контейнера). Все множество вариантов обмена предметами сокращается за счет введения правил отсечения.
Разработан метод для решения задач прямоугольного гильотинного раскроя на базе основных процедур метаэвристики имитация отжига.
В пятой главе рассматривается экспериментальное исследование эффективности разработанных методов и алгоритмов, а также результаты их внедрения в виде программного обеспечения.
Для оценки эффективности разработанного математического обеспечения на основе известной методики Вешера Г. была проведена серия численных экспериментов. Кроме того, представлены результаты экспериментальных исследований разработанных алгоритмов для задач электронной библиотеки OR-library, размещенной на сайте .
Предложенные методы и алгоритмы для решения задачи ортогональной п-мерной упаковки ВРР (п=\,2,3) инвариантны к технологическим ограничениям, возникающим в единичном производстве. Предложенные методы решения задачи одномерной упаковки применялись при решении задачи «Использование отходов по цехам» (ГУП УАП «Гидравлика»), что позволяет обеспечить экономию материалов и сокращение сроков при проектировании планов упаковки деталей в составе автоматизированного рабочего места технолога планово-заготовительного производства. Предложенные методы решения задачи парал-
лелепипедной упаковки применялись при упаковке железнодорожных платформ и вагонов разногабаритными ящиками (ООО «Уралтехнопроект»), а также при размещении ящиков с медикаментами и изделиями медицинского назначения на фармацевтическом складе (000 «ВИВ-ФАРМ»).
Обзор методов решения задач одномерной, двухмерной и трехмерной упаковки и раскроя
Фундаментальное изложение проблемы одно- и двухмерного раскроя дано в книге российских ученых Л.В. Канторовича и В.А. Залгаллера [38]. Задачи раскроя рассматривались ими как примеры применения ранее развитого Л.В. Канторовичем линейного программирования. Аналогичные методы получили развитие в 60-е годы за рубежом в работах P. Gilmore, R. Gomory [125-127] а позднее G. Scheithauer, J. Terno [163]. Для решения задачи генерирования раскроя были разработаны метод склейки [72], сеточный метод для линейного раскроя В.А. Булавским и М.А. Яковлевой [4], для гильотинного раскроя Э.А. Мухачевой [65]. На базе линейного программирования Э.А. Мухачевой разработаны также алгоритмы условной оптимизации, учитывающие специфику реального производства [60]. Поскольку задачи упаковки и раскроя являются проблемами комбинаторной оптимизации, то их решение с помощью линейного программирования - не более чем непрерывная релаксация, которая дает решение, близкое к оптимальному при дополнительных ограничениях, возникающих в условиях массового производства. Приближение непрерывной релаксации к целочисленному оптимуму реализовали G. Scheithauer, J. Terno, A. Muller [164, 165], Э.А. Мухачева [154, 155]. Они предложили решать задачи линейного и гильотинного раскроя методом отсекающих плоскостей Гомори.
Продолжают развиваться точные алгоритмы на базе линейного целочисленного программирования [88, 89, 131]. Методы решения задач линейного и гильотинного прямоугольного раскроя в условиях массового и серийного производства с использованием линейного программирования описаны в работах Э.А. Мухачевой [60, 62], И.В. Романовского [72-75]. Исследования метода решения гильотинного раскроя продолжены в работах [47], [129], [176, 177].
Для решения NP-трудных задач упаковки и раскроя применяются комбинаторные методы. Основная идея комбинаторных методов заключается в выделении из множества допустимых решений подмножеств, не содержащих оптимальных решений. Процедуры нахождения таких подмножеств и их отсев составляют суть комбинаторного алгоритма [76]. И.В. Романовский и Н.П. Христова предложили для решения задач упаковки метод дихотомии [75], который получил развитие в работе СВ. Кацева [39]. И.В. Романовским предложен метод «ветвей и границ» {Method Branch and Bound, MBB) для решения задачи одномерного раскроя [72]. S. Martello, P. Toth предложили улучшенные версии МВВ, называемые методами МТР, для решения 1DBP [150]. Размерность задач, разрешимая этими алгоритмами, не велика ( 200). Перспективы повышения эффективности алгоритмов МВВ состоят в их гибридизации с другими (чаще эвристическими) приемами и алгоритмами. Впервые гибридизация точного алгоритма МВВ с эвристиками выполнена A. Scholl, R. Klein, G. Yuergens. Ими разработан гибридный алгоритм BISON [166]. Другой подход к переборным методам решения задач 1.5DBP и 2DBP разработан в середине 80-х гг. А.И. Липовец-ким [48]. На основе понятия «зоны» доказывается, что для любой упаковки прямоугольников можно указать такой их порядок, при котором каждый следующий прямоугольник не пересекается ни с одной из зон предыдущих (топологическая сортировка). Метод зон реализован, усовершенствован и исследован В.В. Бухваловой [5]. В [66] предложен гибридный метод непрерывной оптимизации и переборного алгоритма к решению задачи упаковки многоугольников, где в качестве частного случая рассматривается задача 1 5DBP. Несколько точных алгоритмов, базирующихся на МВВ, предложено S. Martello, D. Vigo [151], P.Vance [186].
Несмотря на многообразие различных подходов к созданию комбинаторных алгоритмов, размерность решаемых задач редко превосходит т=20. Это связано с тем, что пока не найдено способа определения эффективной нижней границы и для доказательства оптимальности приходится перебирать все возможные варианты. Новые нижние границы и их связь с методом «ветвей и границ» установлены P. Schwerin, G. Waescher [167]. М. Boschetti в 2002 г. предложил несколько новых методик подсчета нижней границы [95]. Другой подход для нахождения нижних границ предложен S.P. Fekete, J. Schepers [116 - 118]. Показано, что нижние границы, разработанные ими на основе использо вания двойственно выполнимых функций, доминируют над всеми элементарны ми классами нижних границ. Появление методик получения нижних границ по зволило значительно расширить размерность задач (в отдельных случаях до 100).
Метод динамического перебора для решения задач прямоугольной упаковки
Метод DS, разработанный для задач одномерной упаковки, был модифицирован для решения задач прямоугольной упаковки. Большинство известных алгоритмов решения задач прямоугольной упаковки в качестве исходного решения используют приоритетный список - перестановку из номеров заданных прямоугольников. Приоритетный список - это код решения задачи упаковки. Для вычисления значения целевой функции и восстановления эскиза прямоугольной упаковки по коду (приоритетному списку) применяются специальные процедуры - декодеры, как правило, представляющие собой простые однопроходные эвристики полиномиальной сложности. При этом поиск оптимального решения осуществляется на множестве различных перестановок. Основное отличие метода DS от этого подхода состоит в том, что он является да DS от этого подхода состоит в том, что он является конструктивным методом, имеющим дело с покомпонентным построением упаковки, а именно: к частично построенной упаковке добавляется новый компонент до тех пор, пока упаковка не будет построена полностью.
При решении задач прямоугольной упаковки J.5DBP и 2DBP в качестве чисел Wy i=I,2,...,т, и W соответственно выступают ширины прямоугольников и ширина полосы (листа). Пусть дана произвольная прямоугольная упаковка полубесконечной полосы (Rectangular Packing, RP) ширины W прямоугольниками заданных размеров (w,;/,), i=\,2,..,m. При этом упаковка мысленно разрезается вертикальными резами, проходящими через правые стороны прямоугольников. В каждом вертикальном резе выделяется опорная грань - непрерывный отрезок в упаковке, параллельный боковой стороне полосы, являющийся объединением левых вертикальных сторон, упакованных в полосу прямоугольников (см. рис. 2.9).
Рассмотрим процедуру размещения кортежей в RP. Назовем свободной областью полубесконечной полосы крайнюю левую полубесконечную прямоугольную область, незанятую прямоугольниками и примыкающую к опорной грани.
Обозначим через W0 длину опорной грани (см. рис.2.10) Пусть нижней и верхней гранью свободной области будет общая граница снизу и сверху свободной области с прямоугольниками или стороной полосы. Обозначим через Уъ и Vt длину нижней и верхней грани (см. рис.2.10). Если свободная область граничит снизу (сверху) со стороной полосы, то Vb = оо (Vt = оо) (см. рис.2.11).
Обозначим через 1тт и 1тах минимальную и максимальную длину прямоугольников в кортеже, а через wk ширину кортежа (сумму ширин прямоугольников, входящих в кортеж) (см. рис.2.11).
Поскольку в RP размещаются кортежи, которые могут состоять из нескольких прямоугольников, то необходимо упорядочить прямоугольники по уменьшению длин в кортеже перед формированием множества кортежей для предотвращения «выступающих» прямоугольников в упаковке, которые в большинстве случаев значительно увеличивают длину занятой части полосы (см. рис.2.14).
При этом возможны два способа размещения кортежа в свободной области полосы: упорядочить кортеж по возрастанию длины, и тогда самый длинный прямоугольник в кортеже будет прижат к нижней грани свободной области (кортеж (5,7) на рис.2.9). упорядочить кортеж по убыванию длины, и тогда самый длинный прямоугольник в кортеже будет прижат к верхнему краю свободной области (кортеж (2,6) на рис.2.9).
Для предотвращения «выступающих» прямоугольников определим правило упорядочивания кортежей: если Vb= К, = со, то упорядочить кортеж по возрастанию длины прямоугольников;
1) если Уь = со или Vt Ф со, то если V, 1тах, то упорядочить кортеж по убыванию длины прямоугольников, иначе по возрастанию;
2) если Vb фаз или У, = со, то если Уь 1тса, то упорядочить кортеж по возрастанию длины прямоугольников, иначе по убыванию;
3) если Vb Vt, то кортеж упорядочить по убыванию длины прямоугольников, иначе по возрастанию. На рис.2.15 представлена структурограмма процедуры DC размещения кортежей. Процедура размещения DC Входные данные: б С- список кортежей из /Г; Z- число кортежей в SC; (w,; /,), i=l,2,...,m, - размеры прямоугольников; W- ширины полубесконечной полосы; Выходные данные: план упаковки с длиной L занятой части полосы. Дляг=1,...,2 Определить параметры свободной области: Wn,Vt, Vb Если ширина кортежа wk Wo, то Нет Если (Vb = оо л V, = оо) v (Vb - л V, Ф оо л Vt Lax) V (Vb Ф СО Л V, = 00 Л Vb lmax) v(VbфcOAVlф « лУь У,) Да крайний левый участок свободной области размера Wo и длиной min{K,, Vb} помечается как использованный Да кортеж упорядочить по возрастанию длины прямоугольников Нет кортеж упорядочить по убыванию длины прямоугольников Разместить кортеж в свободной области Определить длину L занятой части полосы
Идея метода DS для решения задачи 1.5DBP состоит в поиске локальных минимумов в процессе упаковки прямоугольников для каждой длины опорной грани (см. рис. 2.9), а именно: решается задача локальной упаковки (Local Packing Problem, LPP).
Постановка задачи LPP формулируется следующим образом: необходимо найти miny при следующем условии IHVZ, + = O, .) 0, z,e{0,l}; / = l,2,...,m, (2.1) где Wl - ширина /-го прямоугольника, цг0 є S, S - множество длин опорных граней, z, = 1 если используется /-я ширина прямоугольника, и zt — 0 в противном случае.
Для решения задачи LPP применен алгоритм MP А. Так же как и при решении 1DBP, для каждой суммы w+w, W0, i=1,2,...,т, weM,./, находится кортеж из номеров прямоугольников, ширины которых вошли в сумму w+w,. При этом кортеж находится даже в том случае, если число w+w, Wo уже есть во множестве М,. Это позволяет находить не одну, а несколько комбинаций чисел w„ i=l,2,...,m, которые в сумме будут давать число we М„ i=l,2,...,m. Совокупность найденных кортежей образует множество К. Из этих номеров формируются кортежи, как показано на рис. 2.9.
Гибридизация алгоритма муравьиной колонии и динамического перебора для решения задач прямоугольной упаковки
С целью получения более плотной упаковки прямоугольников в боксах при решении задач прямоугольной упаковки (см. рис. 3.4) предлагается гибридизация двух алгоритмов: алгоритма АСР и алгоритма формирования множества К кортежей в методе динамического перебора DSR. В качестве компонентов решения в гибридном алгоритме ACP-DSR выступают кортежи. Каждому элементу кортежа из К соответствует пара (w,,/,), где Wl- ширина, а /,- длина заданного прямоугольника, і =1,...,т, т- количество заданных прямоугольников. Для каждого кортежа се К вводятся следующие характеристики: т 1) ширина wc кортежа с: \Vc Hwn причем wc W, W- ширина полосы, если решается задача 1.5DBP, либо ширина листа (для задачи 2DBP); 2) длина 1С кортежа с: lc = max//; (=1, ,т т 3) оценка 7(с) кортежа с: 77(c) = X w, /, /=1
Алгоритм ACP-DSR по структуре аналогичен алгоритму АСР. При этом первоначально значение уровеня феромона f 0 определяется как величина, обратно пропорциональная произведению m-LFFD, где т- количество заданных прямоугольников, a LFFD - длина упаковки, полученная с помощью метода «первый подходящий» (FFD). В процессе работы алгоритма феромон наносится на последовательности двух кортежей из К
На рис. 3.6 приведена структурограмма предлагаемого гибридного алгоритма ACP-DSR для решения задач упаковки и раскроя 132 Алгоритм ACP-DSR Входные данные: список кортежей из К, полученных по DSR; (w,; /,), i=l,2,...,т, - размеры прямоугольников; W- ширина полубесконечной полосы (листа); qo, а, /3 - параметры алгоритма; а- количество агентов
Процедура BF -получение начального уровня феромона 0 Пока не достигнуты условия остановки алгоритма Для всех агентов а выполнить
Процедура SC, процедура РВ - заполнение первого бокса Для упаковок RP, построение которых не закончено
Процедура РВ, процедура iSTVC-нахождение и заполнение очередного бокса
Процедура UEL- обновление уровня феромона на шаге Процедура f/EG-обновить уровень феромона в конце итерации Рис. 3.6. Структурограмма алгоритма ACP-DSR Рассмотрим далее основные процедуры предлагаемого гибридного алгоритма ACP-DSR. Процедура BF. В этой процедуре вычисляется начальное значение уровеня феромона f0 по следующей формуле: f0= . Первоначально уровень фе LFFD ромона принимается равным хо Для всех пар кортежей из К .
Процедура SC. В процедуре выполняется случайный выбор каждым агентом кортежа се К для размещения его в ширину полосы или листа. При этом формируется список R из номеров прямоугольников, не вошедших в выбранный кортеж.
Процедура РВ. В процедуре выбирается ближайший к началу полосы (листа) бокс w 5/j 5 ]} (см. рис.3.4), и в нем размещается кортеж из множества К » соответствующий ширине w бокса. При этом возможна перестройка элементов в кортеже, если: а) lc \% . В этом случае элементы кортежа переупорядочиваются таким образом, чтобы прямоугольник, имеющий наибольшую длину, прижимался к /j1 - стороне бокса. Остальные элементы кортежа располагаются последовательно по убыванию длин соответствующих им прямоугольников. б) 1с }г. Элементы кортежа переупорядочиваются таким образом, чтобы прямоугольник, имеющий наибольшую длину, прижимался к /г-стороне бокса. Остальные элементы кортежа располагаются аналогично случаю а.
Процедура SNC. В процедуре выбирается следующий кортеж для упаковки очередного бокса. Выбор кортежа зависит от реализации равномерно распределенной величины Q. Если произойдет событие iQ = язю), где q0 є (0,1) - заданное пороговое значение, то выбор кортежа се К производится по формуле: c -argmax\ra(d,c)-7lfi(c)), (3.9) сек где d - последний использованный кортеж; a, fi - управляющие параметры алгоритма, задаваемые при инициализации; rj(c) - оценка кортежа с; величина Ta{d,c)-rj (с)- выражение для общей оценки выбираемого кортежа. Если произойдет событие {Q = q qo}, то выбор кортежа с Є К происходит с вероятностью р(с) по формуле: р(с) = Ta(d,c)f{c) Z Ta{d,c)-rf{c) с К (3.10)
Процедура UEL. В процедуре выполняется обновление феромона на шаге: г (d,c) -(l-)r (d,c) + o, где Е, - это коэффициент, задаваемый при инициализации алгоритма, величина (1 - ) представляет собой испарение феромона, % є (0,1).
Процедура UEG. В процедуре выполняется обновление феромона в конце итерации: т (d,c) -(\-p)T (d,c) + AT (d,c), где А х (d, с) = , Lbest - значение целевой функции лучшей упаковки ите Libest рации.
Рассмотри далее пример решения задачи упаковки в полосу 1.5DBP с помощью предлагаемого алгоритма A CP-DSR.
Пример 3.1. Пусть ширина полосы W=5, количество прямоугольников w=7. Размеры прямоугольников даны в табл. 3.6. Требуется упаковать заданные прямоугольники таким образом, чтобы длина занятой части полосы была минимальна.
Практическое применение метода перебора с усечением и метода на базе процедур имитации отжига
Предложенные методы решения задачи одномерной упаковки: - метод перебора с усечением; - метод динамического перебора были апробированы на практических задачах на ГУП УАП «Гидравлика», (г.Уфа). При этом решалась задача одномерного раскроя прутков одинаковых или смешанных длин. Применение разработанных методов позволило обеспечить экономию материалов и сокращение сроков при проектировании планов упаковки деталей в составе автоматизированного рабочего места технолога планово-заготовительного производства.
Основные подсистемы САПР раскроя-упаковки, используемые на предприятии «Гидравлика», включают:
1. Подсистемы препроцессорной обработки исходной информации об объектах и областях размещения, которая предназначена для подготовки, хранения и редактирования данных о геометрии объектов для решения конкретной задачи.
2. Подсистемы генерирования карт раскроя, основной целью которой является формирование на основе задания рационального размещения геометрических объектов в автоматическом режиме. Поиск и выбор рационального решения осуществляется программными процедурами на основе исходных требований, сформулированных оператором.
3. Подсистемы постпроцессорной обработки информации о раскраиваемых объектах (подсистема разработки технологического процесса раскроя-упаковки).
Подсистема препроцессорной обработки информации осуществляет предварительную подготовку исходной информации для решения задачи рационального раскроя. Подсистема выполняет следующие функции: интерактивный выбор объектов, необходимых для раскроя; интерактивное изменение параметров раскраиваемых заготовок; получение выходной информации о заготовках в виде текстовых файлов. Разработанные методы инвариантны к технологическим ограничениям, возникающим при решении технических задач. К числу таких ограничений относятся припуски на резку заготовок (ширину реза), припуски на последующую механическую обработку (на строгание после резки).
Было разработано программное обеспечение для подсистемы генерирования карт раскроя прутков. В качестве исходной информации выступают размеры прутков и размеры заготовок. Последние рассчитываются с учетом припусков и закодированы определенным образом.
На основе предлагаемых в работе алгоритмов, разработано программное обеспечение для решения задачи одномерного раскроя, которое включено в подсистему препроцессорной обработки информации и подсистему генерирования карт раскроя (прутков).
Входными данными для программного продукта являются текстовые файлы с расширением .Ьрр и .cut, содержащие информацию о размерах прутков и заготовок, соответственно.
Программное обеспечение позволяет создавать новые текстовые файлы и редактировать существующие. У выбранной заготовки или прутка можно изменять такие параметры, как длина, припуски на разрез и на зажим.
Подсистема постпроцессорной обработки информации формирует управляющие программы для станков с ЧПУ. Подготовка таких программ требует выполнения трудоемких математических расчетов и разработки алгоритмов формирования пути инструмента при выполнении раскроя, что само по себе является самостоятельной задачей и в данной работе не рассматривается.
Подсистема генерирования карт раскроя позволяет облегчить труд технолога за счет автоматизации этого процесса на этапе технологической подготов ки производства. Основной целью подсистемы является формирование на основе задания на раскрой рационального размещения заготовок в прутки. Подсистема генерирования карт упаковки выполняет следующие функции: ввод задания на раскрой или выбор пользователем задания на раскрой из существующего набора входных заданий в интерактивном режиме, запуск процесса размещения заготовок на основе введенного задания, автоматический процесс генерирования карт упаковки за счет разработанного программного обеспечения, визуализация процесса раскроя в графическом режиме, просмотр результатов раскроя в графическом виде, сохранение результатов генерирования карт раскроя в виде выходных файлов.
Выходными данными подсистемы генерирования карт раскроя являются текстовые файлы с расширением .гер, содержащие информацию о количество заготовок, размещенных в прутках, коэффициенте раскроя как критерия качества получаемых карт. Сгенерированная карта раскроя отображается на экране дисплея.
Программное обеспечение на базе методов усечения и динамического перебора было включено в состав автоматизированного рабочего места технолога раскройно-заготовительного производства на предприятии «Гидравлика». Бюро нормирования материала предоставило техническое задание для задачи «Использование отходов по цехам».
