Методы решения задач ортогональной упаковки на базе технологии блочных структур

• Автор: Филиппова, Анна Сергеевна
• Шифр специальности: 05.13.18
• Научная степень: Докторская
• Год защиты: 2006
• Место защиты: Уфа
• Количество страниц: 338 с. : ил.

СОДЕРЖАНИЕ

СПИСОК ИСПОЛЬЗУЕМЫХ СОКРАЩЕНИЙ

ВВЕДЕНИЕ.

МОДЕЛИ И МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ОРТОГОНАЛЬНОЙ УПАКОВКИ И РАСКРОЯ

1.1. Комбинаторная задача оптимизации

1.2. Задачи раскроя и упаковки.

1.3. Математические модели задач прямоугольной упаковки и раскроя

1.4. Обзор методов решения для задач прямоугольной

упаковки и раскроя.

1.5. Краткий обзор основных технологий решения ВР

1.6. Проблемы кодирования и декодирования прямоугольных упаковок.

1.7. Применение методов решения задач СР в системах автоматизации раскрояупаковки.
1.8. Результаты и выводы по главе 1
2. БЛОКСТРУКТУРЫ ПРЯМОУГОЛЬНОЙ УПАКОВКИ
2.1. Пара блокструктур как способ кодирования прямоугольной упаковки.
2.2. Вертикальная блокструктура.
2.3. Связь между блокструктурами и линейным раскроем. Прямоугольноориентированный линейный раскрой
2.4. Воспроизведение перестановки в блокструктуру.
2.5. Воспроизведение перестановки в пару блокструктур.
2.6. Преобразование пары последовательностей в пару блокструктур
2.7. Локальная нижняя граница прямоугольной упаковки.
2.8.Численный эксперимент
2.9. Общие схемы решения задачи прямоугольной
упаковки на базе технологии блочных структур.
2 Результаты и выводы по главе 2.
3. ЗАДАЧИ ЛИНЕЙНОГО РАСКРОЯ И УПАКОВКИ
3.1. Модели и методы линейного программирования
для решения задач одномерного раскроя
3.2. Локальный поиск оптимума в задачах одномерного
раскроя и упаковки.
3.3. Результаты и выводы по главе 3
4. МЕТОДЫ КОНСТРУИРОВАНИЯ ПРЯМОУГОЛЬНЫХ УПАКОВОК В ПОЛУ БЕСКОНЕЧНОЙ ПОЛОСЕ
4.1. Конструирование прямоугольной упаковки полубесконечной полосы на базе стратегии
нижнийлевый.
4.2. Уровневые стратегии конструирования прямоугольных упаковок.
4.3. Блочные стратегии конструирования прямоугольных
упаковок.
4.4. Свойство реставрации декодеров
4.5. Численные эксперименты
4.6. Результаты и выводы по главе 4
5. ЭВОЛЮЦИОННЫЕ МЕТОДЫ ЛОКАЛЬНОГО ПОИСКА ОПТИМУМА В ЗАДАЧАХ ПРЯМОУГОЛЬНОЙ
УПАКОВКИ В ПОЛОСУ.
5.1. Общие схемы эволюционного алгоритма
5.2. Алгоритм 11ЕА блочной структуры с локальной
нижней границей.
5.3. Генетические алгоритмы.
5.4. Численные эксперименты.
5.5. Результаты и выводы по главе 5.
6. ПРИМЕНЕНИЕ БЛОЧНЫХ ТЕХНОЛОГИЙ ДЛЯ КОНСТРУИРОВАНИЯ АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧ
УПАКОВКИ И ПОКРЫТИЯ.
6.1. Алгоритмы размещения прямоугольных предметов
на листах контейнерной упаковки.
6.2. Задача и алгоритмы упаковки трехмерного
контейнера
6.3. Применение метода парных списков к решению задач упаковки в квадрант
6.4. Применение блочной технологии для решения двумерной задачи максимального покрытия
6.5. Развитие и применение блочной технологии в задачах комбинаторной оптимизации
6.6. Результаты и выводы по главе 6.
ЗАКЛЮЧЕНИЕ.
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ


Для решения задач С&Р применяется модель LP с неявно заданной информацией о раскроях (столбцах матрицы). Для генерации столбцов В. А. Залгаллером был предложен прием, предвосхитивший появившееся позднее динамическое программирование. Аналогичные методы получили развитие в -е годы за рубежом в работах P. Gilmore & R. Gomory [7-9] и позднее, J. Temo, R. Lindeman & G. Scheithauer [1]. Для решения задачи генерирования раскроя были разработаны метод склейки И. В. Романовским [-], сеточный метод для линейного раскроя В. А. Булавским и М. А. Яковлевой [5], для гильотинного раскроя Э. А. Мухачевой [, ]. На базе линейного программирования Э. А. Мухачевой разработаны также алгоритмы условной оптимизации, учитывающие специфику реального производства []. В то время основной целью этих и многих других работ являлось применение линейного программирования в сфере производственных задач. Эта цель в той или иной мере была достигнута в условиях массового и серийного производства. В зарубежной литературе признан приоритет Л. В. Канторовича и В. А. Залгаллера [2, 3]. Далее задачи раскроя-упаковки рассматриваются как прикладные проблемы комбинаторных задач исследования операций. М. Гэри и Д. Джонсон показали, что задача одномерной упаковки в контейнер (ID Bin Packing Problem, 1DBP) принадлежит к классу NP-трудных задач и для точного решения необходимо применять схемы полного перебора [, 5]. Под задачами раскроя-упаковки понимается широкий класс проблем, допускающих различное прикладное толкование. Общим для этого класса является наличие двух групп объектов. Между элементами этих групп устанавливается и оценивается соответствие. Впервые качественная типология в области раскроя-упаковки проведена в г. Н. Dykhoff [3]. Она принята в мировой практике и используется при изучении моделей и методов решения задач раскроя-упаковки. Разнообразие моделей определяется прежде всего фактором геометрии. Различаются задачи линейного (одномерного), прямоугольного (двухмерного) и параллелепипедного (трехмерного) раскроя-упаковки. Среди этих задач выделяются гильотинный раскрой и упаковка. Особо выделены проблемы нестинга, размещения деталей сложной геометрической формы в заданных областях. Для них на первый план выступают информационные проблемы задания фигур, учета и обеспечения их нсперекрытия, кодировки и другие [, ]. Задачи С&Р являются типичными представителями NP-трудных проблем, и для их решения (включая проблемы нестинга) применяются общие подходы: точные методы, простые эвристики и метаэвристики. Ввиду неполиномиальной сложности точных алгоритмов, авторами многих работ уделяется значительное внимание приближенным методам и эвристикам. В течение -х годов прошлого столетия на тему раскроя-упаковки был выпущен ряд специальных изданий: под редакцией Н. G. Wascher в г. S. Martello в г. Y. Lirov в г. E. Bischoff & G. Wascher в г. E. Mukhacheva в г. H. Yanasse в г. P. Wang & G. Washer в г. Е. Hopper & В. С.Н. Turton в г. Более того, сотни статей опубликованы в международных и российских журналах: European Journal of Operational Research (EJOR), Computers Sc Operational Research, Computers & Industrial Engineering, Operations Research Letters, Pesquisa Operacional; Информационные технологии, Автоматика и телемеханика, Дискретный анализ и исследование операций, Вестник высшей школы, Кузнечно-штамповочное производство и других центральных и ведомственных изданиях. При этом статьи и книги имеют как теоретический, так и прикладной характер. Причина растущего интереса к задачам раскроя-упаковки состоит в их принадлежности к NP-трудным проблемам, в широкой применимости результатов, разнообразии и сложности задач реального мира, которые можно реализовать как NP-трудные. В качестве основной здесь рассматривается двухмерная задача упаковки, ее частный случай одномерный раскрой, прямоугольная упаковка полубесконечной полосы и сопутствующие им проблемы. F, (1. F - область определения, а хе F - допустимое решение. Допустимое решение x*eF оптимально, если f(x*)^x)) для всех допустимых решений хе/% и/(**) называют оптимальной величиной.