Блочные модели и генетические алгоритмы в задаче поиска рациональной прямоугольной упаковки и раскроя

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

Оглавление

ИСПОЛЬЗОВАННЫЕ ОБОЗНАЧЕНИЯ.

ВВЕДЕНИЕ.

1. ЗАДАЧИ РАСКРОЯУПАКОВКИ ОБЗОР МЕТОДОВ РЕШЕНИЯ.

1.1. Задачи одно и двумерного раскрояупаковки.

1. . 1. Простейшая одномерная задача раскроя и упаковки

1.1.2. Задача прямоугольной упаковки в полубесконечную полосу.

1.1.3. Задача прямоугольной упаковки в листы

1.1.4. Задача гильотинного раскроя

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

1.2.1. Использование методов математического программирования

1.2.2. Применение методов комбинаторной оптимизации
1.2.3. Приближенные и эвристические методы
1.2.4. Вероятностные методы локального поиска оптимума
1.3. Основные задачи исследования
1.4. Выводы
2. МОДЕЛИРОВАНИЕ ПРЯМОУГОЛЬНЫХ УПАКОВОК
2.1. Математические модели задач упаковки в полосу и на листы
2.2. Блочная модель упаковки.
2.3. Способы кодирования упаковок
2.4. Алгоритмы декодеры. Блочный декодер.
2.5. СВОЙСТВО ДЕКОДЕРОВ IЩЯ
2.6. Выводы
3. ГЕНЕТИЧЕСКИЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ УПАКОВКИ.
3.1. Общая характеристика генетических методов.
3.2. Генетический блочный алгоритм.
3.3. Оценка эффективности алгоритмов. Нижние границы.
3.4. Выводы
4. ЗАДАЧА ГИЛЬОТИННОГО РАСКРОЯ.
4.1. Математическая модель задачи раскроя полосы
4.2. Использование мультиметодной технологии. Гильотинный
ГЕНЕТИЧЕСКИЙ АЛГОРИТМ.
4.3. Метод дискриминации простых эвристик.
4.4. Выводы.
5. ВЫЧИСЛИТЕЛЬНЫЙ ЭКСПЕРИМЕНТ
5.1. Программная реализация алгоритмов
5.2. Исследование эффективности способов кодирования упаковки и алгоритмов декодеров при использовании генетических алгоритмов
5.3. Исследование декодеров. Проверка на наличие свойства реставрации
5.4. Исследование эффективности генетического блочного алгоритма. Сравнительный эксперимент с метаэвристическими алгоритмами
5.5. Исследование эффективности генетического гильотинного алгоритма с применением дискриминации эвристик.
5.6. Выводы.
ЗАКЛЮЧЕНИЕ.
СПИСОК ЛИТЕРАТУРЫ


ИСПОЛЬЗОВАННЫЕ ОБОЗНАЧЕНИЯ. ВВЕДЕНИЕ. ЗАДАЧИ РАСКРОЯ-УПАКОВКИ: ОБЗОР МЕТОДОВ РЕШЕНИЯ. Задачи одно и двумерного раскроя-упаковки. Задача прямоугольной упаковки в полубесконечную полосу. Блочная модель упаковки. Алгоритмы декодеры. Блочный декодер. ГЕНЕТИЧЕСКИЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ УПАКОВКИ. Общая характеристика генетических методов. Генетический блочный алгоритм. Оценка эффективности алгоритмов. Нижние границы. ЗАДАЧА ГИЛЬОТИННОГО РАСКРОЯ. Использование мультиметодной технологии. ГЕНЕТИЧЕСКИЙ АЛГОРИТМ. Метод дискриминации простых эвристик. Выводы. Исследование декодеров. Исследование эффективности генетического блочного алгоритма. Исследование эффективности генетического гильотинного алгоритма с применением дискриминации эвристик. Выводы. ЗАКЛЮЧЕНИЕ. DBP - 1. Актуальность проблемы. Задачи раскроя-упаковки представляют собой важный раздел задач дискретной оптимизации, исследования операций и их приложений. Актуальность проблемы создания эффективных алгоритмов для решения задачи раскроя-упаковки двумерного прямоугольного ресурса обусловлена как широким практическим применением задач в различных отраслях производства, так и трудностью создания адекватных математических моделей и методов их решения. Сложность решения задачи раскроя-упаковки обусловлена ее принадлежностью к классу ЫР-трудных задач комбинаторной оптимизации. Исследуемая задача является ЫР-трудной в сильном смысле, так как содержит в качестве подзадачи также ЫР-трудную задачу. Во многих случаях применение точных методов для ее решения невозможно из-за больших затрат вычислительного времени. В связи с этим большое значение приобретает разработка и исследование эвристических методов оптимизации, в том числе метаэвристик. В их числе широкое применение получили генетические алгоритмы. Известна асимптотическая сходимость таких методов. Однако практически оптимум достигается не всегда. Кроме того, до сих пор не известны способы построения нижних границ, позволяющие констатировать достижение оптимума. Вместе с тем на практике метаэвристики очень хорошо себя зарекомендовали. Качество полученного решения зависит не только от выбранного метода расчета раскроя-упаковки. Важную роль выполняют и способы кодирования и дешифровки упаковок. Исходя из вышеизложенного, представляет интерес разработка и применение новых генетических алгоритмов для решения задачи раскроя-упаковки прямоугольных предметов на базе эффективных принципов кодирования упаковок. Разработанное алгоритмическое и программное обеспечение становится конкурентоспособным в ряду точных и эвристических подходов. В этом состоит актуальность данной разработки. Целью работы является разработка и исследование моделей и методов решения задачи прямоугольной упаковки и раскроя на базе блочной и мультиметод ной технологий. Применение мультиметодной технологии дискретной оптимизации И. Разработка программного обеспечения на базе предложенных методов. Анализ эффективности и характеристик разработанных алгоритмов на основе результатов численных экспериментов и сравнение эффективности методов с другими, описанными в литературе. Генетический алгоритм гильотинного раскроя на базе мультиметодной технологии дискретной оптимизации И. Исследование эффективности предложенных методов на основе результатов вычислительного эксперимента. Научная новизна работы. Блочный способ кодирования, основывающийся на блочной модели упаковки, который позволил применить для решения задачи новый тип алгоритмов декодирования.