автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.12, диссертация на тему:Структурные преобразования размещений прямоугольных объектов в системах автоматизированного проектирования раскроя - упаковки

УФИМСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

СТРУКТУРНЫЕ ПРЕОБРАЗОВАНИЯ РАЗМЕЩЕНИЙ ПРЯМОУГОЛЬНЫХ ОБЪЕКТОВ В СИСТЕМАХ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ РАСКРОЯ-УПАКОВКИ

Специальность 05.13.12 - Системы автоматизации

проектирования

Диссертация на соискание ученой степени кандидата технических наук

На правых рукописи

Мухаметзянов Рустем Загирович

Научный руководитель -доктор технических наук, профессор Э.А.Мухачева

УФА 1999

ОГЛАВЛЕНИЕ

Введение ........................................................................................... 5

Глава 1. Постановка задачи и обзор существующих методов

решения задачи упаковки прямоугольных объектов..... 10

1.1. Автоматизация проектирования и технологической подготовки раскройно-заготовительного производства 10

1.2. Классификация задач раскроя-упаковки. Основные этапы развития...............................................................................12

1.3. Приближенные методы решения задачи негильотинного прямоугольного раскроя....................... 16

1.4. Точные методы решения задачи негильотинного прямоугольного раскроя.................................................. 21

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

1.6. Основные результаты и выводы по первой главе......... 27

Глава 2. Алгоритмы локального поиска для решения задачи

прямоугольной упаковки............................................................29

2.1. Блочная модель представления прямоугольной упаковки. Линейная аппроксимация задачи негильо- 29 тинного прямоугольного раскроя....................................

2.2. Метод последовательного уточнения оценок................ 36

2.3. Применение метода динамического перебора для поиска ПОЛР................................................................................41

2.4. Вычислительный эксперимент. Сравнительный анализ методов «первый подходящий с упорядочиванием», «последовательного уточнения оценок» и «динамического перебора»..................................................................47

2.5. Основные результаты и выводы по второй главе......... 50

Глава 3. Структурные преобразования прямоугольной

упаковки............................................................................. 52

3.1 Методы изменения структуры прямоугольной упаковки, основанные на блочном ее представлении.................................................................. 52

3.1.1 Алгоритм преобразования структуры упаковки «снизу вверх»................................................................................ 57

3.1.2 Алгоритм преобразования структуры упаковки «сверху вниз» .................................................................. 58

3.2. Применение алгоритмов проверки планарности графа

к задаче упаковки прямоугольных объектов.................. 62

3.3. Вычислительный эксперимент. Определение эффективности, трудоемкости алгоритмов по преобразованию структуры упаковки. 67

3.4. Основные результаты и выводы по третьей главе....... 71

Глава 4. Система автоматизации проектирования раскроя-

упаковки............................................................................. 73

4.1 Современное состояние раскройно-заготовительного производства.................................................................... 73

4.2 Структура САПР раскроя-упаковки................................ 78

4.3 Применение разработанного программного обеспечения в САПР раскроя-упаковки........................................ 81

4.3.1 Подсистема препроцессорной обработки информации...................................................................... 83

4.3.2 Подсистема генерирования раскройных карт................ 84

4.4 Включение подсистемы генерирования раскройных карт прямоугольного раскроя в САПР раскроя-упаковки "Cut-CAD".......................................................... 85

4.5 Выводы по четвертой главе............................................ 87

Заключение..............................................................................................90

Литература................................................................................................92

Приложение 1......................................................................................100

ВВЕДЕНИЕ

Высокие требования современного производства диктуют создание новых технологий проектирования и изготовления изделий, что должно вести к комплексной экономии всех видов ресурсов. Определяющими факторами успеха в промышленном производстве сегодня и в обозримом будущем являются: уменьшение времени выхода продукции на рынок, снижение стоимости и повышение качества. Значительное сокращение цикла проектирования и подготовки производства, подразумевающее внедрение систем автоматизации проектирования (САПР) и автоматизированных систем технологической подготовки производства (АСТПП), может способствовать созданию конкурентоспособной продукции и своевременному выходу ее на рынок.

Среди множества задач, возникающих в проектировании, особое место занимают задачи, связанные с компоновкой и размещением объектов - задачи раскроя и упаковки. Среди многообразия постановок задач раскроя самостоятельный интерес представляют задачи прямоугольного раскроя. Это объясняется высокой долей прямоугольных заготовок в общей массе выкраиваемых деталей, применением прямоугольного раскроя при получении фигурных деталей. К таким задачам относятся, например, оптимизация складирования грузов, планирование помещений, проектирование систем, конструктивно выполненных в виде набора блоков, компоновка деталей. От качества решения этих задач зависит стоимость строительства, эффективность использования площадей, транспорта, складских помещений, технологичность, сокращение сроков и стоимости проектирования.

Проектирование планов (карт) раскроя, по сути, является задачей геометрического проектирования, заключающейся в оптимизации

размещения геометрических объектов в заданных областях. От того, насколько рационально эта задача решается, зависит эффективность использования материала при раскрое. На выбор математических моделей и методов решения задач раскроя существенное влияние оказывает и характер производства. Представляют интерес задачи раскроя в условиях мелкосерийного и единичного производства.

Условия мелкосерийного (единичного) производства требуют рассмотрения задач планирования раскроя как задачи целочисленного математического программирования (ЦМП). Точные методы решения задач данного класса не пригодны в условиях реального производства. Это объясняется сложностью задач и трудоемкостью их решения. Поэтому становится актуальной проблема разработки и использования эффективных эвристических оптимизационных методов решения задачи прямоугольного раскроя.

Целью диссертационной работы является разработка и исследование методов и алгоритмов раскроя-упаковки прямоугольных объектов в прямоугольных областях, позволяющих найти рациональное решение, близкое к оптимальному, разработка на этой базе программного обеспечения.

Задачи исследования. Для достижения поставленной цели в работе сформулированы и решены следующие задачи:

- разработаны математические модели задачи прямоугольной упаковки и определено их место в комплексной САПР раскроя-упаковки;

- разработаны и исследованы методы преобразования внутренней структуры прямоугольной упаковки, основанные на изучении ее топологических свойств;

- модифицированы алгоритмы "первый подходящий с упорядочиванием", "последовательного уточнения оценок" и

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

- разработано программное обеспечение, реализующее предложенные методы и алгоритмы;

- проведен вычислительный эксперимент.

Методы исследования. Результаты исследований, выполненных в работе, базируются на основных положениях систем автоматизации проектирования, численных методах математического программирования и теории графов, принципах модульного и структурного программирования, машинной графики. Применялся вычислительный эксперимент для анализа эффективности алгоритмов.

Научная новизна работы заключается в следующем:

- разработаны и исследованы новые методы преобразования структуры прямоугольной упаковки, основанные на изучении ее топологических свойств;

- модифицированы алгоритмы "первый подходящий с упорядочиванием", "последовательного уточнения оценок" и "динамического перебора" для решения задач планирования прямоугольной упаковки листов с учетом особенностей САПР единичного и мелкосерийного производства.

Практическая ценность. Разработанные в диссертации методы и алгоритмы служат оптимизационным ядром в САПР раскройно-заготовительного производства, а также применимы для решения большого круга других прикладных задач. Разработанное программное обеспечение может использоваться для решения задачи прямоугольного раскроя, нерегулярной упаковки в условиях единичного и мелко серийного производства, содержит развитый интерфейс и может использоваться как автономно, так и в составе САПР раскроя-упаковки.

На защиту выносятся:

1. Математические модели задачи прямоугольной упаковки в составе САПР раскроя-упаковки.

2. Модификация алгоритмов «первый подходящий с упорядочиванием», «последовательного уточнения оценок» и «динамического перебора» для решения задач планирования прямоугольной упаковки листов.

3. Методы и алгоритмы, реализующие преобразование структуры прямоугольной упаковки на основе ее топологических свойств.

4. Программное обеспечение, реализующее разработанные алгоритмы размещения прямоугольников.

Структура работы. Диссертация состоит из введения, четырех глав, заключения, библиографии и приложений.

В первой главе представлена классификация задач раскроя-упаковки и место исследуемой задачи в общей проблеме оптимизации раскроя, приводится обзор работ по решению задачи размещения прямоугольных объектов, обосновывается необходимость автоматизации проектирования задач раскроя-упаковки. Формулируется и ставится задача исследования, приводится математическая модель для ее решения.

Во второй главе формализуется и исследуется задача прямоугольного раскроя-упаковки, описывается математическая модель для ее решения, предлагаются эвристические алгоритмы полиномиальной сложности для нахождения решения задачи прямоугольной упаковки.

В третьей главе рассматриваются топологические свойства прямоугольной упаковки. Описываются алгоритмы изменения структуры плана раскроя, основанные на блочной модели представления карты раскроя. Приведены результаты вычислительного эксперимента.

В четвертой главе описано программное обеспечение, созданное на основе разработанных алгоритмов; даны рекомендации по его использованию в рамках подсистемы препроцессорной подготовки информации и подсистемы генерирования карт раскроя-упаковки. Рассмотрена структура САПР раскроя-упаковки, функции АРМ технолога раскройно-заготовительного производства. Дана методика включения разработанных алгоритмов в САПР раскроя-упаковки.

Заключение содержит основные результаты диссертационной работы.

Основные результаты диссертационной работы докладывались и обсуздались на международных конференциях и семинарах:

- в институте математики Дрезденского технического университета;

- на конференции EURO XVIII в Брюсселе;

- на международной конференции "Проблемы оптимизации и экономические приложения" (1997г., г. Омск);

- на семинарах кафедры вычислительной математики и кибернетики Уфимского государственного авиационного технического университета и научно-теоретической конференции (1995г., г. Уфа).

Публикации. По теме диссертации опубликовано 6 работ.

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

1.1. Автоматизация проектирования и технологической подготовки раскройно-заготовительного производства

Реалии экономической жизни ставят перед отечественными производителями сложную задачу. Если они хотят остаться на рынке и выжить, то должны в корне менять технологию проектирования своих изделий. Поэтому сегодня конструирование и технологическая подготовка производства осуществляются с использованием так называемых "тяжелых САПР", выбор и организация работы которых проходят в рамках единой концепции развития средств проектирования и технологической подготовки производства.

Целью технологической подготовки производства является достижение в процессе изготовления продукции оптимального соотношения мевду затратами и получаемыми результатами. Увеличение доли мелкосерийного производства требует создания автоматизированных систем технологической подготовки, так как именно при данном характере производства преимущества использования автоматизированных систем проявляются в наибольшей степени [77].

Разработки в области автоматизации технологической подготовки производства (ТПП) создали условия для широкого внедрения автоматизированных систем ТПП и автоматизированного программирования систем ЧПУ. Объектами ТПП являются заготовки, основное и вспомогательное оборудование. Заготовка - это объект, подвергаемый в процессе ТПП непосредственному воздействию

режущего инструмента. Множество заготовок может дать обоснование выбору технологического процесса. Речь идет о единичном, мелко- и среднесерийном, а также массовом производстве. Вид материала - это еще одна из характеристик объекта ТПП, так как сведения о материале детали являются одним из критериев проектирования технологического процесса наряду с требованиями к инструменту и станкам.

Процесс производства деталей принято делить на заготовительный этап и этап механической обработки. Трудоемкости обоих этапов связаны между собой, т.е. уменьшение ее на одном из этапов может привести к увеличению трудоемкости на другом. Необходимо подчеркнуть, что создание систем автоматизированной технологической подготовки заготовительного производства наиболее актуально в настоящее и будущее время [29].

Раскройно-заготовительные работы являются одной из начальных стадий ТПП и закладывают основы рационального функционирования всех последующих производственных звеньев. Именно на этом этапе определяются оптимальные размеры заготовок, находится оптимальный способ их размещения на заданном материале, по сгенерированным картам раскроя рассчитываются нормы расхода, как на каждую деталь, так и заказ материала на плановый период в целом. Процесс составления карт раскроя является сложным и трудоемким, особенно в условиях единичного и мелкосерийного производства, которые отличаются большой номенклатурой деталей и типоразмеров используемого материала, частой сменяемостью заказов. Поэтому технолог без использования средств автоматизации не в состоянии спроектировать раскройные карты, состоящие из большого количества разногабаритных деталей, с минимальными отходами, в сжатые сроки и с учетом технологических ограничений.

Только оптимальное проектирование на всех этапах разработки технологического . процесса позволяет добиться качества проектирования и эффективности процесса производства в целом.

1.2. Классификация задач раскроя-упаковки. Основные

этапы развития.

Задача оптимального раскроя материала имеет различные математические постановки, на которые оказывают влияние ряд факторов: геометрическая форма размещаемых в исходном материале заготовок, тип раскройного оборудования, объем выпускаемой продукции, различные технологические характеристики раскраиваемого материала (см. рис. 1.1.).

В зависимости от формы заготовок различают задачи фигурного и нефигурного раскроя. К задачам нефигурного раскроя относят линейный раскрой материала, когда заготовки имеют лишь один линейный размер (раскрой прутка, рулона), и прямоугольный раскрой, когда исходные заготовки - прямоугольники. При фигурном раскрое геометрическая форма заготовок произвольная. В различных отраслях промышленности используются разнообразные виды раскройного оборудования: гильотинные ножницы, фрезы, пилы, разрешающие только сквозные резы, параллельные кромкам материала. При таком виде оборудования получаем гильотинный (регулярный) раскрой материала. Распространение термического и лазерного оборудования, позволяющего раскраивать заготовки различной конфигурации, привело к появлению негильотинного (нерегулярного) раскроя.

По объему выпускаемой продукции задачи раскроя подразделяются на задачи раскроя в условиях массового (серийного)

Рис. 1.1 Классификационные признаки задач раскроя

производства и задачи раскроя в условиях единичного (мелкосерийного) производства.

Наиболее исследованными являются задачи линейного и прямоугольного гильотинного раскроя в условиях массового производства. Это связано с простой формой заготовок, а также с ограничениями на их расположение, т.к. разрешаются только сквозные резы, параллельные кромкам раскройного листа. Они описываются непрерывными моделями линейного программирования. Задачи раскроя в условиях единичного (мелкосерийного) производства описываются моделями целочисленного линейного программирования или другими моделя