Структурные преобразования размещений прямоугольных объектов в системах автоматизированного проектирования раскроя - упаковки

• Автор: Мухаметзянов, Рустем Загирович
• Шифр специальности: 05.13.12
• Научная степень: Кандидатская
• Год защиты: 1999
• Место защиты: Уфа
• Количество страниц: 112 с. : ил.

ОГЛАВЛЕНИЕ
Введение
Глава 1. Постановка задачи и обзор существующих методов
решения задачи упаковки прямоугольных объектов
1.1. Автоматизация проектирования и технологической
подготовки раскройно-заготовительного производства
1.2. Классификация задач раскроя-упаковки. Основные
этапы развития
1.3. Приближенные методы решения задачи негильотинного прямоугольного раскроя
1.4. Точные методы решения задачи нешльотанного
прямоугольного раскроя
1.5. Математическая постановка задачи прямоугольной
упаковки листов
1.6. Основные результаты и выводы по первой главе
Глава 2. Алгоритмы локального поиска для решения задачи
прямоугольной упаковки
2.1. Блочная модель представления прямоугольной
упаковки. Линейная аппроксимация задачи негильо
тинного прямоугольного раскроя
2.2. Метод последовательного уточнения оценок
2.3. Применение метода динамического перебора для
поиска ПОЛР
2.4. Вычислительный эксперимент. Сравнительный
анализ методов «первый подходящий с упорядочиванием», «последовательного уточнения оценок» и «динамического перебора»
2.5. Основные результаты и выводы по второй главе

Глава 3. Структурные преобразования прямоугольной
упаковки
3.1 Уетоды изменения структуры прямоугольной
упаковки, основанные на блочном ее представлении
3.1.1 Алгоритм преобразования структуры упаковки «снизу
вверх»
3.1.2 Алгоритм преобразования структуры упаковки
«сверху вниз»
3.2. Применение алгоритмов проверки планарности графа
к задаче упаковки прямоугольных объектов
3.3. Вычислительный эксперимент. Определение
эффективности, трудоемкости алгоритмов по преобразованию структуры упаковки
3.4. Основные результаты и выводы по третьей главе
Глава 4. Система автоматизации проектирования раскроя-
упаковки
4.1 Современное состояние раскройно-заготовительного
производства
4.2 Структура САПР раскроя-упаковки
4.3 Применение разработанного программного обеспечения в САПР раскроя-упаковки
4.3.1 Подсистема препроцессорной обработки
информации
4.3.2 Подсистема генерирования раскройных карт
4.4 Включение подсистемы генерирования раскройных
карт прямоугольного раскроя в САПР раскроя-упаковки “Cut-CAD”
4.5 Выводы по четвертой главе
Заключение
Литература Приложение

листа, и будет состоять из следующих этапов:
1. Определение области упаковки: выбор вертикального отрезка границы, разделяющей занятую часть листа от незанятой, наименее удаленного от исходной грани листа. Эта подзадача решается путем
определения множества прямоугольников Iй и вычисления их суммарной ширины, где ц - номер текущего кортежа. На первом шаге (д = 1) областью упаковки является исходная боковая грань листа;
2. Упаковка прямоугольников из множества еще не упакованных Iм в ширину выбранного отрезка. Проверка возможности упаковки прямоугольника по длине и ширине: ширина прямоугольника должна быть меньше ширины области упаковки, а по длине прямоугольник должен помещаться в неупакованную часть листа;
3. Если множество Г не пусто, и ни один прямоугольник из него не помещается в область упаковки, то приступаем к упаковке следующего листа;
4. Построение очередного (/+1)-го кортежа /л.
Данные шаги повторяются до тех пор, пока все прямоугольники не будут упакованы в листы.
Алгоритмы, использующие предложенную схему построения карт раскроя листов, различаются только на втором этапе, т.е. по способу укладки прямоугольников в текущую область упаковки. Могут быть предложены различные подходы для решения этой подзадачи. Здесь предлагается использовать два таких метода. Первых из них «метод последовательного уточнения оценок» основывается на построении некоторого приоритетного списка прямоугольников, используя который происходит заполнение области упаковки. Второй - «динамического перебора», базируется на идее минимизация отхода (неиспользованной части области упаковки).