Проектирование нерегулярного раскроя листовых материалов на заготовки сложных форм с использованием дискретно-логического представления информации

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

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

— задачи оптимального раскроя материала на заготовки произвольной формы, решаемые при производстве изделий в машиностроительной, авиастроительной, судостроительной, текстильной, кожевенной, деревообрабатывающей, мебельной и многих других отраслях промышленности;

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

— задачи распределения — от памяти вычислительных машин до участков леса, предназначенных для вырубки или посадки.

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

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

От качества решения данных задач зависит стоимость строительства, эффективность использования площадей, транспорта, складских помещений, технологичность, сокращение сроков и стоимости проектирования [39].

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

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

Анализ отечественной и зарубежной литературы, информационных /Мегие^-источников позволяет сделать вывод, что исследованием и разработкой методов решения данного класса задач занимаются: Харьковская школа Р-У академика Стояна Ю.Г.- Институт алгоритмов и научных вычислений Германии (Ленгауэр Т.) — Миленковик В., Даниэльс К. (США) — Доусланд К., Доусланд В. (Великобритания) — ряд российских ученых, среди которых: Вер-хотуров М.А., Мартынов В. В., Мухачева Э. А., Петунии A.A., Фроловский В. Д. Несмотря на это и на широкое распространение оборудования, позволяющего использовать эти методы на производстве: — до сих пор в большинстве случаев на карты Р-У проектируются вручную или примитивными интерактивными программными средствами. Это нарушает непрерывность процесса автоматизации и приводит к нерациональному использованию дорогостоящих материалов и высокопроизводительного оборудования для Р-У. Причиной такого состояния является отсутствие эффективного математического обеспечения для систем автоматизации проектирования раскроя-упаковки деталей сложных форм.

— профессиональные укладчики при ручном размещении при решении задач нерегулярного раскроя-упаковки часто получают результаты лучшие, чем сгенерированные на ЭВМ.

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

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

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

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

Основные задачи исследования в соответствии с поставленной целью сформулированы следующим образом:

1. Разработать эффективные и надежные алгоритмы:

— представления деталей в виде, удобном для реализации условий взаимного непересечения деталей между собой и областью размещения,.

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

— учет технологических особенностей оборудования при проектировании раскроя.

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

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

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

Методы исследования.

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

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

Результаты, выносимые на защиту:

1. Методы и алгоритмы применения дискретно-логического представления информации и цепного кодирования для аппроксимации, размещения и учета технологических особенностей оборудования при проектировании нерегулярного двумерного раскроя деталей сложных форм.

2. Адаптация метода дискретной оптимизации GRASP для решения задачи построения рационального пути режущего инструмента в системах автоматизации проектирования раскроя.

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

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

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

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

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

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

Практическая значимость работы.

Разработанные в диссертации методы и алгоритмы решения задач нерегулярного раскроя-упаковки деталей сложных форм, а также других задач, возникающих при создании САПР раскроя, дают возможность на единой основе создавать надежное и гибкое программное обеспечение, легко адаптируемое к любым производственным условиям и допускающее возможность широкого использования в различных отраслях промышленности. Кроме того, использованные алгоритмы оптимизации, на основе методов локального поиска, позволяют создать комплекс программных средств, быстро генерирующих высокоэкономичные карты раскроя — упаковки и программы для станков с ЧПУ. Все это дало возможность применить полученные результаты для разработки при создании автономного комплекса программных средств. На базе проведенных исследований, разработан работающий в среде Microsoft Windows 9х/2000/ХР программный продукт для решения задач САПР Р-У — «NestCAD», который на практике показал высокую эффективность за счет хорошей настраиваемое&tradeи быстрой адаптации к условиям работы производств различного вида в разнообразных отраслях промышленности, уменьшения времени проектирования карт Р-У (в 2−4 раза), экономии материала (до 5%) и энергии (до 6%).

Основание для выполнения исследований.

Работы в данном направлении проводились автором в Уфимском государственном авиационном техническом университете в 1999;2002 годах в рамках хоздоговорных научно-исследовательских работ с ОАО «Уралхим-маш» г. Екатеринбург и ОДО «Лама» г. Бирск.

В 1999;2001 г. г. работа была поддержана РФФИ, проекты 01−99−937 и 01−01−510.

Внедрение результатов:

— в Акционерном обществе «Химмаш», г. Екатеринбург (алгоритмическое и программного обеспечения рационального раскроя плоских материалов на фигурные заготовки);

— в Обществе с дополнительной ответственностью «Лама», г. Бирск (система автоматизированного раскроя листового материала при производстве разверток в мебельной промышленности).

Апробация работы. Основные результаты работы докладывались и обсуждались на следующих конференциях:

— Республиканская научно-техническая конференция «Интеллектуальное управление в сложных средах», Уфа, 1999 г.

— Международная научная конференция «Моделирование, вычисления, проектирование в условиях неопределенности, Уфа, 2000 г.

— Первая всероссийская научно-практическая конференция по вопросам решения оптимизационных задач в промышленности «Ресурсосберегающие технологии: математическое обеспечение оптимизационных задач в системах автоматизированного проектирования», Санкт-Петербург, 2001 г.

Публикации.

По теме диссертации опубликованы 10 работ, в том числе 5 статей, 4 доклада научно-технической конференции и 1 тезис докладов.

Структура работы.

Диссертация состоит из введения, четырех глав, выводов, списка литературы и приложений. Объем основной части диссертации составляет 137 страниц, кроме того, работа содержит 32 рисунка и 4 таблицы.

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

1. На базе дискретно-логического представления информации и цепного кодирования разработаны следующие методы и алгоритмы:

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

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

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

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

3. Разработана трехуровневая структура блока оптимизации размещения САПР раскроя, ориентированная на применение для генерации размещения деталей дискретных методов локального поиска и содержащая блок планирования и управления — 1-ый уровеньблок оптимизации и обработки данных о геометрии — 2-ой уровеньменеджер приоритетного списка и управляющих воздействий, блоки подсчета геометрических и интегральных характеристик — 3-ий уровень. Определены принципы взаимодействия компонентов структуры и направления информационных потоков между ними. Такая структура блока оптимизации размещения не зависит от используемых в системе способов представления информации, методов моделирования различного типа геометрических преобразований, и от всевозможных видов оптимизационных механизмов, что позволяет разрабатывать гибкое программное обеспечение САПР раскроя.

4. На базе разработанных методов и алгоритмов с использованием средств организации комплексов программ создан программный продукт «МезЮАО», позволяющий в автономном режиме решать задачи нерегулярного двумерного раскроя деталей сложных форм. Он может быть использован для автоматизации деятельности промышленных и проектных организаций, связанных с решением задач раскроя. Для проверки качества разработанных методов и алгоритмов проведен вычислительный эксперимент, а также сравнение полученных решений с результатами других распространенных в настоящее время на рынке пакетов программ для автоматизации раскроя. Эксперимент показал высокую эффективности разработанных алгоритмов, позволяющих при снижении времени счета в 2−4 раза повысить в среднем на 4,5% экономию материала и снизить на 4−6% расход энергии на движение режущего инструмента.

Заключение

.

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

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