Модели и методы решения задач прямоугольного раскроя и упаковки на базе метаэвристики "Поиск с запретами"

• Автор: Ермаченко, Александр Иванович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Уфа
• Количество страниц: 95 с. : ил.

Оглавление
Введение.

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

1.1. Задачи раскроя и упаковки и их классификация

1.2. Методы математического программирования.

1.3. Точные методы комбинаторной оптимизации.

1.4. Приближенные и эвристические методы.

1.5. Вероятностные методы локального поиска оптимума.

1.5.1. Генетические алгоритмы

1.5.2. Поиск с запретами.

1.5.3. Имитация отжига.

1.5.4. Муравьиная колония
1.6. Использование декодеров.
1.7. Численные эксперименты
1.8. Выводы
2. Математические модели задач двумерного прямоугольного раскроя. Процедуры кодирования и декодирования
2.1. Исходная информация задач двумерного прямоугольного раскроя
2.2. Модель прямоугольной упаковки и условия допустимости
2.3. Постановка задач прямоугольного раскроя и упаковки
2.4. Процедуры декодирования в решении задач двумерного прямоугольного раскроя и упаковки.
2.4.1. Рекурсивный декодер
2.4.2. Декодер поиска пустых корзин.
2.4.3. Декодер Нижний левый.
2.4.4. Блочный декодер
2.5. Декодер последовательного конструирования для прямоугольной упаковки.
.6. Выводы по второй главе.
3. Метод поиска с запретами е переменными окрестностями и
вторичными оценками для решения задач двумерного прямоугольного
раскроя.
3.1. Мстаэвристическая методика поиска с запретами для решения задач дискретной оптимизации
3.2. Алгоритм поиска с запретами с переменными окрестностями и вторичными оценками для решения задач двумерного прямоугольного раскроя.
3.3. Реализация метода поиска с запретами в составе автоматизированной системы проектирования карг двумерного прямоугольного раскроя СЕТАМ1СиТ
3.4. Выводы по третьей главе
4. Численные эксперименты.
4.1. Выбор числа шагов до смены вторичной оценки
4.2. Эксперимент на случайно сгенерированных примерах.
4.2.1. Примеры с количеством предметов
4.2.2. Примеры с количеством предметов 0.
4.3. Сравнение декодера последовательного конструирования и блочного декодера
4.4. Эксперимент на безотходных примерах Евы Хоппер.
4.5. Выводы по четвертой главе
Заключение.
Литература


Примеры с количеством предметов 0. Эксперимент на безотходных примерах Евы Хоппер. Заключение. Литература. Диссертационная работа посвящена разработке методов расчета для задачи двумерного прямоугольного раскроя рулонного и листового материала на базе метаэвристики «Поиск с запретами», и реализации разработанных методов в составе программного обеспечения для автоматизированного проектирования раскроя. Актуальность темы исследования. Актуальность проблемы создания эффективных эвристических и метаэвристических алгоритмов для решения задачи двумерного прямоугольного раскроя-упаковки обусловлена высокой сложностью решаемых задач, а также обширной областью практического применения данных задач. Проблемы раскроя-упаковки являются важным классом задач дискретной оптимизации. К прямоугольному раскрою-упаковке двумерного материала сводятся многие реальные процессы. Задача раскроя-упаковки принадлежит к классу ЫР-трудных задач, то есть для ее точного решения не существует алгоритма полиномиальной сложности. Более того, рассматриваемая задача является ЫР-трудной в сильном смысле, так как содержит ЫР-трудную задачу в качестве подзадачи. До сих пор не разработано эффективных и достаточно точных способов расчета нижних границ для данной задачи, позволяющих определить достижение оптимума. Таким образом, точные алгоритмы сводятся к полному перебору вариантов. В связи с этим, использование точных алгоритмов для решения задачи раскроя-упаковки часто оказывается нецелесообразным и невозможным по причине больших затрат времени. Поэтому большое значение уделяется разработке и исследованию эвристических методов оптимизации. Одним из перспективных направлений является разработка метаэвристических алгоритмов, основанных на известных метаэвристических подходах, с успехом используемых для решения многих задач дискретной оптимизации. На данный момент для решения задач дискретной оптимизации наиболее активно используются генетические алгоритмы. Также широкое распространение получили метаэвристики «Поиск с запретами», «Имитация отжига» и «Муравьиной колонии». Помимо выбранной методики и особенностей ее реализации конкретным автором, большое влияние на качество и быстроту получения результата оказывает выбор алгоритма декодера. Под декодером обычно понимается процедура, которая позволяет на основе абстрактной информации (например, приоритетный список заготовок), однозначно определить взаимное положение заготовок и построить карту раскроя. Выбор декодера является важным вопросом при проектировании нового метода. От него не в меньшей степени зависит качество конечного результата, чем от построения алгоритма метаэвристики. Также очень важен правильный выбор способа генерации множества решений на очередном шаге алгоритма и оценочной функции. Таким образом, представляет интерес разработка и программная реализация метаэвристических алгоритмов, а также исследование их поведения на разных классах задач раскроя-упаковки и с применением различных процедур декодеров, с целью выявления наиболее перспективных путей дальнейшего развития таких методов. Особенно важным представляется возможность использования программного обеспечения на базе разработанных метаэвристических алгоритмов для оперативного и высокоэффективного проектирования отдельных производственных процессов и в составе более сложных систем автоматизации производственного цикла. В этом заключается актуальность данной работы. Разработать метод решения задач прямоугольного раскроя и упаковки на базе метаэвристики «Поиска с запретами». Разработать программное обеспечение на основе предложенных методов. Провести численные эксперименты на тестовых наборах данных и сравнить полученные результаты с результатами других исследователей. Результаты исследований, выполненных в работе, базируются на методах исследования операций, теории и практике математического моделирования, принципах модульного и структурного программирования. Для анализа эффективности методов применялись численные эксперименты и методы их обработки.