Содержание к диссертации
Введение
Модели и методы решения задач ортогональной упаковки и раскроя 29
1.1. Комбинаторная задача оптимизации 31
1.2. Задачи раскроя и упаковки 33
1.3. Математические модели задач прямоугольной упаковки и раскроя 46
1.4. Обзор методов решения для задач прямоугольной упаковки и раскроя 49
1.5. Краткий обзор основных технологий решения 2DBP 66
1.6. Проблемы кодирования и декодирования прямоугольных упаковок 74
1.7. Применение методов решения задач С&Р в системах автоматизации раскроя-упаковки 76
1.8. Результаты и выводы по главе 1 81
2. Блок-структуры прямоугольной упаковки 82
2.1. Пара блок-структур как способ кодирования прямоугольной упаковки 82
2.2. Вертикальная блок-структура 88
2.3. Связь между блок-структурами и линейным раскроем. Прямоугольно-ориентированный линейный раскрой 92
2.4. Воспроизведение перестановки в блок-структуру 96
2.5. Воспроизведение перестановки в пару блок-структур 99
2.6. Преобразование пары последовательностей в пару блок-структур .102
2.7. Локальная нижняя граница прямоугольной упаковки 107
2.8.Численный эксперимент 120
2.9. Общие схемы решения задачи прямоугольной упаковки на базе технологии блочных структур .123
2.10. Результаты и выводы по главе 2 126
3. Задачи линейного раскроя и упаковки 128
3.1. Модели и методы линейного программирования для решения задач одномерного раскроя 129
3.2. Локальный поиск оптимума в задачах одномерного раскроя и упаковки 145
3.3. Результаты и выводы по главе 3 167
4. Методы конструирования прямоугольных упаковок в полубесконечной полосе 168
4.1. Конструирование прямоугольной упаковки полубесконечной полосы на базе стратегии «нижний-левый» 169
4.2. Уровневые стратегии конструирования прямоугольных упаковок 174
4.3. Блочные стратегии конструирования прямоугольных упаковок 177
4.4. Свойство «реставрации» декодеров 203
4.5. Численные эксперименты 204
4.6. Результаты и выводы по главе 4 211
5. Эволюционные методы локального поиска оптимума в задачах прямоугольной упаковки в полосу 212
5.1. Общие схемы эволюционного алгоритма 213
5.2. Алгоритм (1+1)-ЕА блочной структуры с локальной нижней границей 218
5.3. Генетические алгоритмы 222
5.4. Численные эксперименты 228
5.5. Результаты и выводы по главе 5 255
6. Применение блочных технологий для конструирования алгоритмов решения задач упаковки и покрытия 258
6.1. Алгоритмы размещения прямоугольных предметов на листах (контейнерной упаковки) 258
6.2. Задача и алгоритмы упаковки трехмерного контейнера 268
6.3. Применение метода парных списков к решению задач упаковки в квадрант 286
6.4. Применение блочной технологии для решения двумерной задачи максимального покрытия 290
6.5. Развитие и применение блочной технологии в задачах комбинаторной оптимизации 299
6.6. Результаты и выводы по главе 6 301
Заключение 303
Список использованной литературы 305
- Математические модели задач прямоугольной упаковки и раскроя
- Связь между блок-структурами и линейным раскроем. Прямоугольно-ориентированный линейный раскрой
- Локальный поиск оптимума в задачах одномерного раскроя и упаковки
- Свойство «реставрации» декодеров
Введение к работе
Актуальность проблемы. Исследование технологических процессов в различных отраслях промышленности показывает, что многие из этапов заготовительного производства связаны с раскроем и размещением деталей. Эти процессы являются очень важными с точки зрения экономии ресурсов и сложными для принятия решений. Возникают оптимизационные задачи раскроя и упаковки в процессе планирования и заказа материалов, а также на этапе оперативного проектирования карт раскроя и упаковки. Принятие оптимального или близкого к нему решения позволяет существенно сократить расход материала и понизить себестоимость продукции. В условиях глобальной автоматизации промышленных процессов давно появилась необходимость в создании и использовании систем автоматизации проектирования подготовки раскроя и упаковки. К серьезным компьютерным продуктам, разработанным в России в этом направлении, можно отнести САПР «СИРИУС» (Екатеринбург) и «ТЕХТРАН-РАСКРОЙ» (С.-Петербург). Первая базируется на работах Р.А. Вайсбурда и А А Петунина, вторая - на методах сквозного проектирования, развитых В.Д. Фроловским. Применение классических методов раскроя осуществлено В.А. Ворониным и В.А. Кузнецовым в лесоперерабатывающих комплексах Карелии. Больших успехов добиваются за рубежом. Общим недостатком всех систем является слабая степень оптимизации раскроя и упаковки. В хорошее сервисное окружение оказываются зашитыми неэффективные методы расчета.
Кроме того, появилось огромное количество мелких и средних предприятий, которые не могут позволить приобретение комплексов сквозного проектирования. Поэтому разработка и исследование численных методов оптимизации раскроя и упаковки, направленных на получение ресурсосберегающих технологий, является актуальной проблемой. Более того, задачи раскроя-упаковки встречаются не только в связи с проектированием технологической подготовки производства изделий. Проблема объединяет разные по математической и прикладной постановке задачи. В литературе они встречаются под различными названиями. Общим для них является наличие двух групп объектов. Требуется установить соответствие и порядок назначения между ними так, чтобы некоторая целевая функция достигала минимума. В индивидуальных производственны" условиях задачи раскроя-упаковки оказываются NP-трудными, именно они охватывают огромный пласт прикладных и теоретических проблем. Принципиально различаются задачи упаковки геометрических объектов сложных форм (нестинга) и ортогональной упаковки прямоугольных объектов. В области нестинга известны работы Л.Б. Беляковой, М.А. Верхотурова, В.В. Мартынова, Ю.Г. Стояна, и других ученых. В области ортогональной упаковки - это работы Санкт-Петербургской (В.В. Бухвалова, И.В. Романовский), Новосибирской (Э.Х. Гимади, А.А. Колоколов, Ю.А. Кочетов), Петрозаводской (В.А. Воронин, В А. Кузнецов) и Уфимской (А.Ф. Валеева, Э.А. Мухачева) школ. За рубежом многие ученые занимаются этой проблемой. Наиболее известны работы X. Дикхоффа (Н. Dyckhoff),
А. Бортфельда (A. Bortfeld), И. Фолкнера (E. Folkenauer), E. Хоппер (E. Hopper), С. Имахори (S. Imahori), С. Мартелло (S. Martello), Г. Шайтхауера (G. Sheithauer), П. Ванг (P. Wang), Г. Вешера (G. Wascher) и другие. Следует отметить, что методы, разработанные для ортогональной упаковки с успехом применяются и для задач нестинга. Ввиду NP-трудности рассматриваемых задач, применение точных методов приводит к непреодолимым препятствиям, в связи с высокой размерностью решаемых задач.
В связи со сказанным, создание ресурсосберегающей технологии разработки конструирования упаковки и раскроя, включающей новые эффективные стратегии и алгоритмы, представляет актуальную теоретическую проблему, применение которой позволяет решать широкий круг задач, в том числе и возникающих при проектировании технологической подготовки раскройно-заготовительного производства.
Объектом исследования является комплекс задач оптимизации раскроя-упаковки, инвариантных к производственным условиям различных отраслей промышленности, но допускающих учет технологических и организационных ограничений в рамках разрабатываемой технологии и алгоритмов расчета раскроя-упаковки.
Цель и задачи исследования. Целью диссертационной работы является создание многофункциональной технологии, направленной на экономное использование материальных ресурсов, включающей: кодирование и конструирование упаковок; вычисление нижних границ; разработку новых и модификацию известных алгоритмов локального поиска и исследование их эффективности.
Для достижения цели в работе поставлены и решены следующие задачи"
Предложить многофункциональную технологию моделирования методов и оценки качества решений для задач ортогональной упаковки.
Разработать модели и методы кодирования и декодирования с использованием блочных структур; провести численное сравнение декодеров.
Разработать способ определения окрестности локально-оптимального решения и алгоритм поиска этого решения.
Разработать эволюционные методы локального поиска оптимальной упаковки с использованием декодеров блочной структуры. Провести численное исследование эффективности разработанных алгоритмов.
Предложить способ синтеза разработанных алгоритмов для создания единой технологической системы конструирования и расчета упаковок.
Адаптировать блочную технологию для различных моделей и практических задач рассматриваемого класса.
Методы исследования. Для изложения теоретических основ в диссертации использовались методы исследования операций и математического программирования, теория и численные методы линейного и целочисленного программирования; элементы динамического программирования; комбинаторные методы решения задач дискретной оптимизации; приближенные и эвристические методы решения комбинаторных задач; методы экспериментального исследования с использованием современной вычислительной техники.
Основные научные результаты, полученные автором и выносимые на защиту
В диссертации предложена технология конструирования прямоугольной упаковки {блочная технология), рис. 1. Она ориентирована на разработку алгоритмов и их применение в производственных системах с учетом следующих требований: получение качественных (близких к оптимальным) упаковок с большим количеством деталей (до 1000 различных наименований) и с минимальными временными затратами. Кроме того, условием применения алгоритмов является облегченная адаптация к различным производственным требованиям, достигаемая доступными схемами и их программной реализацией.
На защиту выносятся следующие результаты:
Теоретические основы блочной технологии, представляющей способы моделирования методов решения задачи ортогональной упаковки в полубесконечную полосу на основе кодирования блочными структурами.
Блочный способ определения нижних границ и поиска локально-оптимального решения в их окрестности.
Основные способы конструирования упаковок на базе блочных структур: «замещения» и «двойных списков», их базовые и улучшенные версии.
Эволюционные алгоритмы решения задач ортогональной упаковки: блочные модификации классического генетического алгоритма и эволюционного алгоритма (1+1)-ЕА с локальной нижней границей; разработка генетического блочного алгоритма; алгоритмы с синтезом простых декодеров конструирования упаковок, допускающих учет технологических параметров
Методика применения технологии блочных структур для разработки алгоритмов решения различных задач ортогональной упаковки.
кодирование
нижние границы
декодеры
алгоритмы
локального
поиска
алгоритм синтеза
Рис. 1 - Основные функциональные элементы блочной технологии
Научная новизна результатов
В диссертации предложена технология блочных структур для моделирования упаковок, разработки и исследования методов и алгоритмов решения задач ортогональной упаковки
Разработаны теоретические основы многофункциональной блочной технологии, базирующейся на ортогональных разбиениях упаковок на блоки для моделирования методов решения и оценки их эффективности в задачах прямоугольной упаковки в различных постановках.
Предложены и обоснованы процедуры определения нижних границ, отличающиеся от известных возможностью итерационного приближения к оптимальному или локально-оптимальному решениям. Они позволяют оценивать эффективность решения на различных этапах его получения.
Предложен алгоритм поиска лучшего решения в окрестности локальной границы. Поиск в этой окрестности позволяет получать решение, приближающееся к функции цели прямоугольно-ориентированного линейного раскроя, имеющей смысл локальной или глобальной нижней границы.
Создан метод кодирования упаковок блок-структурами: доказаны необходимые и достаточные условия соответствия блок-структур и упаковок Это позволило разработать алгоритмы преобразования ранее известных кодов в «блок-структуры» для использования на различных уровнях при решении задачи упаковки.
Предложены декодеры, использующие блочную структуру, отличающиеся от известных конструированием упаковки путем перемещения прямоугольников только в одном направлении Это позволяет повышать эффективность работы декодеров и оперативно включать в них технологические или иные ограничения
Разработаны эволюционные методы с использованием различных блочных декодеров. Это позволяет конструировать быстрые и высоко эффективные методы расчета рациональных упаковок.
7 Предложена гибридизация декодеров блочной структуры для создания индивидуальных программных комплексов на базе конкретных эволюционных алгоритмов, синтез которых представляет единую систему блочных технологий для решения задач ортогональной упаковки. 8. Предложена адаптация блочной технологии, позволяющая решать практические задачи прямоугольной упаковки в листы и открытый квадрант, па-раллелепипедной упаковки и простейших задач покрытия.
Обоснованность и достоверность результатов диссертации. Обоснованы теоретические положения в виде свойств и условий соответствия блок-структур и упаковки, области поиска допустимых и оптимальных решений, существования и поиска локальной нижней границы; они и другие результаты базируются на использовании апробированных методов исследования и корректном применении математического аппарата. Достоверность выводов подтверждается результатами проведенных численных экспериментов.
Практическая значимость результатов. Разработанная в диссертации блочная технология ориентирована на создание методов расчета упаковок с
учетом ограничений, возникающих в производственных системах. Для использования блочной технологии удобны метаэвристики, в составе которых применяются инвариантные к производству процедуры. Производственный фон включается только в процедуры конструирования упаковок, т.е. в декодеры. Такое включение может быть реализовано простыми приемами пользователя. Предлагаемый комплекс алгоритмов и программ отличается от аналогов малыми временными затратами для расчета ресурсосберегающих упаковок за счет применения высокоэффективных эволюционных алгоритмов с быстродействующими блочными декодерами. Это подтверждено использованием блочных технологий в процессе размещения контейнеров (ящиков) на складах и транспортных средствах, ЗАО «Новое время», г. Уфа; технологической подготовки производства металлоконструкций, ОАО «Буммаш», г. Ижевск; в подготовке производства целлюлозно-бумажной промышленности, г. Петрозаводск. Программное обеспечение интегрировано в промышленную систему Техтран-Раскрой, г. С.Петербург и автоматизированную систему проектирования прямоугольного раскроя, CETAMI-CUT, г. Уфа. Программы официально зарегистрированы, свидетельства № 2004611452, №2006612649 Результаты работы используются в учебном процессе Уфимского государственного технического университета, Уральского государственного технического университета - УПИ и Башкирского государственного университета.
Связь исследований с научными проеістами. Работа выполнялась при поддержке Российского Фонда Фундаментальных Исследований, проекты 99-01-00937, 01-01-00510, 02-01-06331, 03-01-07002; фонда Президента РФ поддержки молодых кандидатов наук, проект МК 145.2003.01; программы Мин. Образования РФ «Научные исследования высшей школы в области производственных технологий» (2001), раздел технологии современных заготовительных производств.
Апробация работы. Основные научные и практические результаты диссертации докладывались и обсуждались на Международных и Российских научных конференциях, в том числе: Сибирском конгрессе по прикладной и индустриальной математике (ИНПРИМ-98) г.Новосибирск, 1998; Международной Сибирской конференции «Дискретный анализ и исследование операций», ИМ СО РАН, г.Новосибирск, 1998, 2000, 2002, 2004; 16-ой Европейской конференции по исследованию операций, г. Брюссель, Бельгия, 1998 ; Международной конференции IFORS-2000, г. Сан-Антонио, США, 2000; Международной конференции IFORS 2002, Эдинбург, Англия 2002; «Европейский научный семинар ESICUP», Виттенберг, Германия, 2004; Международные конференции «Математическое программирование и приложения», ИММ УРО РАН г. Екатеринбург, 1999, 2001, 2003, 2004, 2007; Международная научная конференция «Моделирование, вычисление, проектирование в условиях неопределенности», УГАТУ, Уфа, 2000, Байкальская международная школа-семинар «Математическое программирование», г. Иркутск 2002, 2005; Всероссийская научно-практическая конференция «Ресурсосберегающие технологии», Санкт-Петербург, 2001; Международная конференция «Математика и экономика старые проблемы и новые подходы», памяти Л В. Канторовича, С-Петербург,
2004; Всероссийская конференция «Проблемы оптимизации и экономические приложения», Омск, 2003, 2006, Международная конференция CSIT, УГАТУ, Уфа, 2002, 2004, 2005; Международная Уфимская зимняя школа-конференция по математике и физике, БГУ, Уфа, 2005; на семинарах Института Вычислительной математики Дрезденского технического университета, Дрезден, 2002, семинарах кафедр «Вычислительной математики и кибернетики» и «Компьютерной математики» УГАТУ.
Публикации. По теме диссертации опубликовано более 80 работ. Основные результаты представлены в работах [1-40]. В число указанных публикаций входят 22 статьи из «перечня ВАК ведущих научных журналов и изданий, в которых должны быть опубликованы основные научные результаты на соискание ученой степени доктора наук» В совместных работах с проф Э.А. Мухачевой, доц. А.Ф. Валеевой, доц. В.М Картаком и аспирантами УГАТУ А.В. Чиглинцевым, P.P. Ширгазиным принадлежат автору диссертации следующие разделы: идеи и подходы к созданию технологии блочных структур; блочные методы кодирования и декодирования упаковок; необходимые и достаточные условия соответствия блок-структур и упаковок; аппроксимация прямоугольной упаковки парой ослабленных задач прямоугольно ориентированного линейного раскроя; способ «замещения» в блочных алгоритмах конструирования упаковки; алгоритмы «двойныхх списков» и генетического блочного алгоритма с новой идентификацией элементов генетики, проведение и анализ результатов численного эксперимента Э.А. Мухачевой принадлежат идеи разделения упаковки на прямоугольные блоки и ситуации «перестройки», возникающей в ходе конструирования упаковок. А.В. Чиглинцеву принадлежат разработки блочных декодеров с использованием стратегий нижний-левый и свойство «реставрации» некоторых декодеров. В М. Картак ввел условие неперекрытия прямоугольников для пары блок-структуре.
Структура и объем работы. Диссертация состоит из введения, шести глав основного материала, заключения, библиографического списка и приложений; содержит 325 страниц основного текста. Библиографический список включает 212 наименований литературы.
Математические модели задач прямоугольной упаковки и раскроя
Определяющим локальную нижнюю границу является следующее утверждение. Пусть L и N допустимые решения задачи 2DSP и отвечающей ей задачи ROCS, полученные алгоритмом NF с перестановкой ж. Тогда Ц является локальной нижней границей для любого допустимого решения задачи 2DSP, полученного NF для перестановки ж , эквивалентной ж.
Множество эквивалентных перестановок {ж}, отличающихся друг от друга только перестановками пассивной пары элементов, определяет ROLC-окрестность прямоугольной упаковки RP. Установленная связь между перестановкой ж и блок структурами ROLC и RP позволяет организовать поиск решения в ROLC окрестности. При этом выполняется неравенство L(RP,;r) ?V(ROLC,;r) = A, какие бы пассивные изменения в списке ж не произошли.
В главе 3 представлены задачи одномерного раскроя-упаковки и основные методы их решения. Наряду с задачами одномерного раскроя, подробно описаны задачи прямоугольно-ориентированного раскроя и пригодные для ее решения алгоритмы. Особое внимание уделено методу последовательного уточнения оценок (Sequential Value Correction, SVC), идея которого связана с объективно-обусловленными оценками Л.В. Канторовича. Эта глава имеет важное вспомогательное значение. В начале главы описаны некоторые популярные методы решения задач одномерного раскроя и упаковки: релаксация линейным программированием; генетический алгоритм и метод последовательного уточнения оценок. Далее приведена модель задачи прямоугольно 23 ориентированного раскроя, ее особенности и методы решения. В заключение главы приведены результаты численных экспериментов и принцип разделения задач на классы по степени трудности достижения оптимума с помощью предлагаемых алгоритмов.
В главе 4 приведена общая характеристика известных уровневых и безуровневых декодеров нижний-левый (Bottom-Left, BL) и усовершенствованный алгоритм «нижний-левый» (IBL), представляющих альтернативу блочной технологии и развитые в работах западных ученых. Далее приведены разработанные в диссертации способы декодирования: «замещение», «парных списков блок-структур» и «блочные». Алгоритмы замещения (Substation, Sub). Рассматриваются одно-или малопроходные методы и алгоритмы конструирования прямоугольных упаковок. Исходной информацией являются (\V, т, w, /) и перестановка 7г = (\(л-),2(7г),...,і(7г),...,т(7г)). По мере надобности задается признак возможности поворота детали в полосе. Однопроходные алгоритмы замещения базируются на свойстве 6 неперекрытия прямоугольников.
Описаны алгоритмы: замещение следующим подходящим (SubNF); замещение первым подходящим (SubFF); замещение лучшим подходящим (SubBF).
Метод перестройки (Reconstruction, Rec). Выполняется в качестве дополнительной процедуры в процессе конструирования упаковки. В диссертации она описана в рамках алгоритмов Sub.
Предположим, что получено частичное решение задачи ROCS. Оно представлено списком S и удовлетворяет свойствам 1 и 2 . Определяющим для RP является выполнение свойства 6 размещаемости прямоугольников. Нарушение свойства приводит к ситуации перестройки Для ее преодоления предложены два переборных алгоритма: «сверху-вниз» (Up-Down Reconstruction, URec) и «снизу 24 вверх» (Down-Up Reconstruction, DRec). С ними проведены численные эксперименты.
Метод поиска двойных блок-структур (Double Block Structure Search, DBSS). Алгоритм DBSS конструирует RP в два этапа. На первом решается задача вертикальная задача ROCS при заданной перестановке ЇЇ . На втором этапе решается горизонтальная задача ROCS с учетом условий неперекрытия 3. Если решение удовлетворяет условию N W, то ROLC - допустимо, вычисляют координаты (х; у) упаковки.
Декодеры блочной структуры. Блочный декодер BD разработан для генетического блочного алгоритма GBA. Там он применяется на этапе расшифровки я. Вместе с тем BD ориентирован на формирование блочной структуры любой RP. Усовершенствованный блочный декодер (Improved BD, IBD). Использует корректное изменение длины блоков, ширины пустых участков, а также добавление новых блоков. Дальнейшее развитие представляет плавающий декодер (FBD).
Развитие декодеров блочной структуры. Пусть имеется прямоугольная упаковка RP длины L в полосу ширины W и представлена ее вертикальная блок-структура. При этом легко вычисляется и фиксируется л:-координата каждого размещенного прямоугольника. В модификации нет априорного закрепления у координаты за прямоугольником. Она может изменятся в процессе конструирования упаковки.
Связь между блок-структурами и линейным раскроем. Прямоугольно-ориентированный линейный раскрой
Базовой здесь является следующая хорошо известная проблема. Задача линейного раскроя {Cutting Stock Problem, IDCS).
Имеется материал, поступающий в виде стержней длины Z. Путем его раскроя требуется получить набор из т различных предметов заданной длины Л./, / = \,т, и в необходимом количестве bf каждого вида / = \,т. Требуется раскроить материал на линейные предметы (элементы) с минимальными затратами материала. Задача 1DCS задается информационным вектором (Z; т; Я; Ь); Л = (Л\,...,Лт); b = (b\,...,bm). Вектор а] =(а1у,а2ь-,о/иу) eZ+ описывает у -й шаблон раскроя; компоненты ац указывают количество получаемых элементов типа /. Матрица А = (ау), i-\,m; j-\,п называется раскройной матрицей. Обозначим х;, j = \,n интенсивность применения раскроя j. Тогда проблема планирования оптимального раскроя материала сводится к решению (2.3) Заметим, что шаблон раскроя j может быть записан как (і (/),2(у),...,/(/),...), в котором перечислены номера /(/ ) заготовок, получаемых по шаблону/. Тогда план раскроя материала представляет совокупность из п записей с указанием интенсивности х .применения каждой из них. Этот план можно задать в виде где S- список шаблонов, N - количество расходуемых стержней. Пусть задана исходная информация (W; т; w; I) задачи 2DSP.
Если положить Z=IV; Xi=wf, bi=li); і = \,т, то 2DSP трансформируется в 1DCS с (Z=W; т; X = w; Ъ=1). Пара (S; N) (здесь N имеет смысл израсходованной длины материала) определяет ее решение, S = {\U)Xj%AJ),-.)Zj, J = Vr;N=Zxj, (2.4) где Xj интенсивность примененияу -го шаблона. Если положить Z=JV; Я/=//5 b w,; і = \,т, то 2 DSP трансформируется в задачу линейного раскроя 1DCS с (Z= N; т; Я = 1; b=w). Пара (S;N) определяет ее решение S=(\(j),2Ul-i(J),-)nj, J = lq;N=YrJj, (2.5) У=1 где ]: - интенсивность применения у-го шаблона. Определим прямоугольно-ориентированные задачи линейного раскроя (Rectangular Oriented CS, ROCS). Задача ROCS. При исходных данных 2DSP и Z=W; X = w, b=l, найти допустимое решение (S; N) задачи 1DCS, удовлетворяющее свойствам 1,2.
Будем считать здесь и далее, что размеры (Wj, If) всех прямоугольников целые, иначе их можно округлить до ближайшего целого числа. Задача ROCS . При исходных данных 2DSP и Z= N;A = l; b=w, найти допустимое решение (S;N) задачи 1DCS , удовлетворяющее свойствам 1, 2, 3 и условию
Учет ограничения 1 не представляет труда. Что касается 2 , то продолженность элементов в соседних записях удобно учитывать в рамках алгоритмов последовательного раскроя, когда шаблоны раскроя генерируются один за другим по мере их заполнения деталями из приоритетного списка л. Среди алгоритмов локального поиска это -однопроходные и малопроходные эвристики, например «следующий подходящий» (Next Fit, NF), «первый подходящий» (First Fit, FF), «лучший подходящий» (Best Fit, BF).
Характеристика алгоритмов NF и FF для решения задач ROCS(ROCS ). За основу работы декодеров удобно принять схему, имитирующую действия мастера в раскройном цехе. Представим процесс в виде выполнения последовательности тактов, на каждом из которых разрезается на детали (элементы) очередной стержень. Предположим, что известен приоритетный список ЇЇ , в котором каким-то образом упорядочены детали. В начале у-го такта от целого стержня отрезается первая из ЇЇ деталь с номером І(ЇЇ), ее длина Аип\ не превышает длины Z стержня. Потребность Ъ\ в этой детали корректируется, полагая Ь лу.= Ьіґп\-\. Если Ь;=0, то элемент / удаляется из списка ж. От полученного остатка длины Z:=Z- Хип\ вновь отрезается следующая (алгоритм NF) или если это невозможно первая из ж возможная (алгоритм FF) деталь. Если подходящей нет, то такт закончен, и полученный шаблону характеризуется записью (1(/), 2(f), ...), интенсивность Xj применения шаблона определяется как ттЬил. Следующий такт начинается с раскроя целого стержня. і Модификация NF и FF для прямоугольно-ориентированного линейного раскроя состоит в следующих процедурах: 1. /(/") включается в шаблону только один раз. Тогда все элементы каждого шаблона различные. 2. Каждый очередной такт j начинается с включения в запись шаблона детали / є / _[, для которой &, 0. В работе [19] показано, что при заданной перестановке ж и Ь=(\, 1, ..., 1) алгоритм NF обеспечивает одномерную упаковку с минимальным количеством шаблонов. Это утверждение нетрудно пролангировать на задачу ROCS(ROCS ). Для этого достаточно повторить /-й элемент Ьі раз. и считать их разными. Вычислительная сложность онн-лайн версий этих алгоритмов составляет соответственно 0{т) и 0(m\ogm).
Характеристика алгоритма BF. Выделяются два вида алгоритмов. Они определяются порядком упаковки предметов в корзины. Он-лайн алгоритмы рассматривают предметы в заданном порядке и упаковывают их в корзину, выбираемую с помощью некоторой стратегии. Офф-лайн алгоритмы вначале упорядочивают предметы. Каждый раз отрезается от стержня или его остатка подходящая деталь максимальной длины (оценки). Алгоритм легко реализуется, если элементы в списке ж упорядочены по невозрастанию.
Локальный поиск оптимума в задачах одномерного раскроя и упаковки
Предположим, что уже имеется некоторая перестановка л, т.е. шифр упаковки. Он может быть расшифрован различными способами и в результате получают различные упаковки (см. пример 4.1) и, что самое главное, различной длины. Поэтому выбор подходящего декодера - это важный момент в процессе построения упаковок.
Проиллюстрируем сказанное на примере. На рис. 4.5 и 4.11 приведены упаковки одного и того же набора прямоугольников с помощью стратегий NF, FF и BF. В первом случае использовались уровневые структуры, во-втором - блочные. Длины упаковок, изображенных на рис. 4.11 соответственно равны: L\{Sub) = l\ +/4 +/5; L2(Sub) = l\ +/3; L Sub)-/3 +І2- Сравнивая их с длинами L\, //? и 3 уровневых упаковок, заключаем, что L](Sub) L\; L2(Sub) L2 , L,2(Sub) L2. Однако это не означает явного преимущества блочных структур по сравнению с уровневыми представлениями. Безусловным преимуществом блочных структур является лучшее использование свободных для размещения областей. Однако уровневые структуры удобно ориентированы как на гильотинный раскрой так и на упаковку. Этот феномен хорошо продемонстрировал A. Bortfeldt [104] для случаев, когда имеется достаточное количество небольших деталей, распределенных по различным уровням. Тем не менее преимущества в этом смысле блочных декодеров хорошо подтверждается численными экспериментами на примерах.
Метод перестройки применяется в рамках Sub или иного алгоритма в ситуации, когда изменение порядка размещения деталей в блоках может привести к уменьшению общей длины L упаковки. Впервые серьезная публикация в этом направлении появилась в 1997 году [106]. Там приведена интерпретация ситуации Rec на графах и описан алгоритм, сходный с проверкой планарности графа. В 2000 году опубликована статья [57], в которой приведены два переборных алгоритма перестройки.
Топологические свойства упаковок. Предположим, что задача ROCS решена и известно ее оптимальное решение Л. Это решение представлено списком S, удовлетворяющим свойствам 1 и 2 (см. гл. 2) Определяющим для RP является выполнение свойства 4 размещаемости прямоугольников. Предположим, что для некоторой пары соседних кортежей (/, j+\) нарушено это свойство. Тогда будем говорить, что при переходе с кортежа j к кортежу (/+1) возникла ситуация перестройки, а соответствующие области (/+1)-го блока назовем критическими. Рассмотрим интерпретацию указанной ситуации на графах. Рассмотрим вначале наглядный пример. На рис. 4.12, а и б изображены упаковки RP1 и RP2 в полосу одних и тех же прямоугольников и L(RP1) L(RP2). Четыре первых блока в этих упаковках различаются только перестановкой прямоугольников, входящих в них. В случае а в блоке №5 не удается разместить девятый прямоугольник. Здесь мы встретились с ситуацией перестройки. Продолжения областей 4-го, 6-го и 8-го прямоугольников на 5-й блок критические. Если удастся их объединить в одну общую область, то критическая ситуация преодолена. В случае б, полученном после перестановки прямоугольников в блоках №1-№4 случая а, освободилось место для размещения девятого прямоугольника в блоке №5 (выполнено свойство размещаемости). Процедуру, реализующую нужную перестановку прямоугольников в блоках, назовем перестройкой.
Непрерывный отрезок в RP, параллельный боковой стороне полосы, являющийся объединением левых вертикальных сторон упакованных в полосу прямоугольников, назовем опорной гранью этих прямоугольников.
Сопоставим первым четырем блокам упаковок, изображенных на рис. 4.12, неориентированные графы. Вершины графа отвечают опорным граням начальных элементов, а ребра графа прямоугольникам. На рис. 4.13, а и 4.13, б сплошными линиями изображены фрагменты графов, соответствующих случаям а и б, рис. 4.12.
Граф, отвечающий прямоугольной упаковке, назовем RP-графом. Известно, что граф, для которого существует ему изоморфный с плоским изображением, называется планарным. Плоское изображение графа разбивает плоскость на связные компоненты, одна из которых является неограниченной.
Утверждение 4.2. Для объединения освободившихся областей в блоке j необходимо и достаточно, чтобы граф, отвечающий первым j блокам после размещения рядом отмеченных вершин, оставался RP-графом.
Вершины, инцидентные ребрам 5 и 7, являются висячими для графов, изображенных на рис. 4.13. В случае а они расположены во внутренней грани графа, а в случае б - во внешней. Таким образом, задача объединения свободных областей сводится к построению плоского изображения RP-графа, у которого висячие вершины расположены во внешней неограниченной грани.
Свойство «реставрации» декодеров
Рассматривается задача ортогонального размещения прямоугольных предметов на прямоугольных листах заданных размеров. Задача имеет многочисленные приложения: упаковка прямоугольных предметов в контейнеры; негильотинный прямоугольный раскрой в машиностроении; размещение предметов (ящиков, коробок) на стеллажах; размещение элементов электронных схем; загрузки транспорта; распределение двухмерного производственного ресурса; ряд задач планирования занятости и другие. Постановка задачи и ее математическая модель приведены в главе 2. Для удобства повторим постановку задачи упаковки в листы.
Постановка задачи. Имеется неограниченное количество прямоугольных листов заданной ширины Wm длины L, а также набор из т прямоугольных предметов (элементов), заданных размеров w,; /,-, i = \,m. Требуется разместить предметы на листы при следующих условиях:
Соответствующая этим условиям карта размещения прямоугольных предметов на листах называется прямоугольной упаковкой (rectangular packing, RP). Качество упаковки в лист характеризуется коэффициентом (Coefficient packing, СР), отношением площади упакованных предметов к суммарной площади занятых листов. В задаче требуется упаковать все предметы в минимальное количество листов.
Задача ортогонального размещения деталей на листах является NP-трудной проблемой комбинаторной оптимизации. Для построения точного решения используются различные направления: методы отсечения Гомори; метод ветвей и границ и его различные модификации; асимптотически точные алгоритмы Э.Х. Гимади и В.В. Залюбовского. Ввиду NP-трудности и практического применения задач вызывают значительный интерес методы локального поиска оптимума. К таковым относятся простые однопроходные эвристики, многопроходные эвристики и вероятностные алгоритмы, в том числе метаэвристики. Развитию эвристических методов, основанных на блочных структурах и посвящен этот раздел.
Использование блочных структур для конструирования прямоугольного размещения на листах. Особенности задачи размещения в основном касаются вопросов конструирования декодеров размещения. Поэтому остановимся подробно на процедуре формирования блочных структур для упаковок на листы.
Сначала формируется перестановка ж - последовательность номеров прямоугольных предметов, в соответствии с которой будет осуществляться их последовательное размещение на листах по тому или иному алгоритму.
Существует несколько принципов формирования перестановок: упорядочивание по убыванию длин, ширин, площадей прямоугольников; случайная перестановка и некоторые другие. Он может быть также получен как результат текущего или окончательного решения задачи с помощью того или иного алгоритма. Например, при использовании генетического алгоритма новую ж получают в результате реализации процедур «скрещивание» или «мутация». Наконец, ж часто формируется случайно.
Пусть список ж уже сформирован. Нужно выполнить операцию «воспроизведение ROLC». Возможны модификации различных блочных алгоритмов для решения этой задачи. Мы рассмотрим модификацию алгоритма с нижней границей и поиском лучшего решения в ее окрестности. Основной алгоритм для решения задачи упаковки в полубесконечную полосу приведен в главах 4 и 5. Он состоит в выполнении следующих основных процедур: построение перестановки ж; воспроизведение ROLC; конкатенация ROLC и построение новой перестановки жпем.\ воспроизведение RP; селекция
RP. Особенности задачи упаковки в листы влияют на алгоритмы воспроизведения. На их модификации мы и остановимся. Перечислим некоторые понятия, используемые в модифицируемом алгоритме. Опишем некоторые, используемые далее, понятия. Резерв по ширине (ru) - ширина свободного пространства в кортеже, куда могут быть размещены прямоугольники. Равняется разности между шириной полосы и суммой ширин размещенных прямоугольников перед формированием очередного блока.
Ширину размещения можно также вычислять как разность ширины листа и сумму ширин прямоугольников, продолженных из предыдущего блока.
Резерв по длине (г/) - длина свободного пространства на листе, куда могут быть размещены прямоугольники. Вычисляется как разность между длиной листа и суммой длин блоков, формирование которых уже завершено.
Будем размещать прямоугольники следуя алгоритму FF с учетом возможности упаковки каждого элемента целиком в лист.
Перед началом работы алгоритма воспроизведения ROLC имеем: rw=W=20; Г[ = L-20. Размещаем первые из п три прямоугольника, получаем блок длины х\ =min{l4,10,17} =10; структуру (3, 2, 1) 7і=Ю заносим в позицию №1 табл. 6.1. Первые три компоненты вектора /?:=/ уменьшаются на величину %\ =Ю- Тогда имеем: /Л :=(4, 0, 7, 10, 4 ,11, 7, 3, 5, 9. Полностью упакован второй элемент. Резерв по ширине rw=W-(w] +и з) = 8; резерв подлине r\ = L-71=20-10=10. Эти значения заносим в позицию №2 табл. 6.1. Следующий подходящий элемент -седьмой, предшествующий ему в ЇЇ шестой элемент не может быть размещенным, т.к. 1 -11 10. Длина блока №2, %г = minIM \b ,bjj=A. После корректировки fr получаем fr =(0, 0, 3, 10, 4, 11, 3, 3, 5, 9); резервы rw=20-(6+8)=6; /7=20-(10+4)=6. Этих резервов не достаточно для размещения нового элемента. Остается блок (3, 7) длины 7з=3. После завершения их размещения ги,=20; г\ Ъ. Этого достаточно для размещения элемента №8. Остаются не размещенными элементы 4, 5 ,6, 9, 10. Повторяем для них алгоритм в порядке ЇЇ =(6, 4, 10, 9, 5), см. табл. 6.2.
