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

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

ОГЛАВЛЕНИЕ

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

ВВЕДЕНИЕ

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

1.1. Основные модели упаковки и раскроя.

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

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

1.2.2. Применение методов комбинаторной оптимизации.

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

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

Выводы по первой главе

, Задачи, решаемые в диссертационной работе.
ГЛАВА 2. КОНСТРУКТИВНЫЙ МЕТОД ДИНАМИЧЕСКОГО ПЕРЕБОРА ДЛЯ РЕШЕНИЯ ЗАДАЧ ОРТОГОНАЛЬНОЙ УПАКОВКИ
2.1. Метод динамического перебора для решения задачи
одномерной упаковки.
2.2. Метод динамического перебора для решения задач
прямоугольной упаковки
2.2.1. Гибридный метод динамического перебора для решения задачи прямоугольной упаковки.
2.2.2. Метод динамического перебора с элементами стохастики для решения задач прямоугольной упаковки
2.3. Метод динамического перебора для решения задачи параллелепипедной
упаковки
Выводы по второй главе.
ГЛАВА 3. КОНСТРУКТИВНЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ПРЯМОУГОЛЬНОЙ УПАКОВКИ НА БАЗЕ МЕТАЭВРИСТИКИ МУРАВЬИНОЙ КОЛОНИИ
3.1. Методы решения задач прямоугольной упаковки на базе метаэвристики муравьиной колонии.
3.2. Гибридизация алгоритма муравьиной колонии и динамического перебора
для решения задач прямоугольной упаковки.
Выводы по третьей главе
ГЛАВА 4. НЕКОТОРЫЕ ЭВРИСТИЧЕСКИЕ МЕТОДЫ ДЛЯ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО И ГИЛЬОТИННОГО РАСКРОЯ.
4.1. Метод перебора с усечением для решения задач одномерной упаковки.
4.2. Метод на базе процедур алгоритма имитация отжига для решения задач прямоугольного гильотинного раскроя
4.3. Практическое применение метода перебора с усечением и метода на базе
процедур имитации отжига.
Выводы по четвертой главе
ГЛАВА 5. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ И АНАЛИЗ РАЗРАБОТАННЫХ МЕТОДОВ УПАКОВКИ И РАСКРОЯ
5.1. Анализ и выбор методик исследования предлагаемых алгоритмов упаковки и раскроя
5.2. Анализ эффективности алгоритмов перебора с усечением и динамического перебора для решения задачи одномерной упаковки
5.3. Анализ эффективности алгоритма динамического перебора для решения задачи двухмерной упаковки
5.4. Анализ эффективности алгоритма муравьиной колонии для решения задач двухмерной упаковки .
5.5. Анализ эффективности для решения задач прямоугольного раскроя на базе процедур метаэвристики имитации отжига
5.6. Анализ эффективности алгоритмов для решения задач параллелепинедной упаковки
5.7. Практическое применение разработанных алгоритмов и программ для решения задач параллелепипедной упаковки
Выводы по пятой главе.
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА


Примерами задач, сводящихся к задачам упаковки и раскроя, являются следующие оптимальное планирование работ в вычислительных системах реального времени составление графика выполнения работ на различных производствах размещение компонентов на чипе при проектировании сверхбольших интегральных схем СБИС упаковка грузов в транспортных контейнерах планировка помещений. Основой для отнесения какойлибо из перечисленных задач к классу СР является наличие двух групп объектов. К первой группе относятся большие объекты, ко второй группе малые. Между элементами этих групп устанавливается и оценивается соответствие. I или упаковка . Классификация основных моделей задач СР разработана в школе под руководством Э. А. Мухачевой и изображена на рис. При этом существенное различие этих моделей определяется двумя основными факторами геометрией объектов и объемом выпускаемой продукции. Что касается первого фактора, то особо выделены проблемы нестинга размещения деталей сложной геометрической формы в заданных областях. Для них на первый план выступают информационные проблемы задания фигур, учета и обеспечения их непересечения, кодировки и другие. Наиболее известны работы в этой области Ю. Г. Стояна , М. А. Верхотурова , , 8 В. В. Мартынова . Задачи СР, определяемые вторым фактором, разделяются на два класса задачи в условиях массового крупносерийного производства продукции и в условиях единичного мелкосерийного производства. Задачи СР по сути являются прикладными комбинаторных задач исследования операций и их решение с помощью линейного программирования непрерывная релаксация, дающая решения при дополнительных условиях, возникающих в рамках массового производства. При решении этих задач в условиях единичного производства существенным является требование целочисленности получаемых решений, что касается массового производства, то оно является необязательным. На схеме рис. Р обычно решаются в условиях массового производства, а задачи генерации в условиях единичного производства. В работе рассматриваются задачи упаковки и раскроя в условиях единичного производства. На тему упаковкираскроя было выпущено шесть специальных изданий под редакцией Н. Ii ii, i , i i Информационные технологии, Автоматика и телемеханика, Дискретный анализ и исследование операций, Вестник высшей школы, Кузнечноштамповочное производство и других центральных и ведомственных изданиях. При этом статьи и книги имеют как теоретический, так и прикладной характер. Н. Гэри и Д. Джонсон показали, что задача одномерной упаковки в контейнер принадлежит классу трудных проблем и для ее точного решения необходим полный перебор. Рис. Ввиду неполиномиальной сложности точных алгоритмов, авторами многих работ уделяется значительное внимание приближенным и эвристическим методам. Требуется раскроить заданный материал таким образом, чтобы расход материала был минимальным задача . Задачи ВРР и описываются сходными целочисленными моделями, инвариантными к производственным условиям. Основное внимание в работе уделяется задачам одномерной, прямоугольной и параллелепипедной упаковки. Задача одномерной упаковки 1 ii i i 1 состоит в следующем. Даны контейнеры заданной вместимости и набор из т предметов с весами , е Т, , , i 1,2,. Требуется упаковать предметы в контейнеры так, чтобы количество занятых контейнеров было минимально. На рис. На рис. Среди задач упаковки в контейнеры, кроме одномерного случая, рассматриваются задачи ортогональной упаковки в полубесконечную полосу 1. Термин 1. На рис. I 1 3 Р vv 2, 1,3,4,3,2,1. Рис. Рис. I 1 . Рис. Задача прямоугольной упаковки в полосу состоит в следующем. Исходная информация задается набором данных , т, и, , IV, т, у, е 2Г, где IV ширина полубесконечной полосы т количество прямоугольников ИИ,И2,. Н,,. ИП вектор ширин прямоугольников ,2,. Вводится прямоугольная система координат ХОУ, у которой оси ОХ и ОУ совпадают соответственно с нижней неограниченной и боковой сторонами полосы. Решение задачи представляется в виде набора элементов Х, К, где ХхI, Х2,. Уу1, у2, . ХиУ. Прямоугольники не выходят за границы полосы для всех1,. В задаче упаковки в прямоугольные листы ВР, кроме ширины листа IV, известна его длина Ь. Обычно исходная информация о прямоугольниках такова, что одного листа для их размещения бывает недостаточно и требуется найти упаковку с минимальным числом занятых листов.