ОБ ОДНОМ ПОДХОДЕ К ВЫБОРУ АЛГОРИТМА РАСЧЕТА ФИГУРНОГО РАСКРОЯ
А.А. Петунин
Уральский государственный технический университет – УПИ
В различных отраслях промышленности на заготовительном этапе производства возникают задачи рационального раскроя материала. С точки зрения геометрической оптимизации они относятся к задачам раскроя-упаковки (Cutting & Packing, C&P) [1], для которых не известны алгоритмы решения полиномиальной сложности. Одной из наиболее трудных в проблеме C&P является задача фигурного раскроя или проблема «нестинга» (nesting). В общем случае, под «нестингом» понимается оптимальное размещение геометрических объектов сложной формы в заданных областях. Оптимизационную задачу можно сформулировать следующим образом.
Пусть –двумерныегеометрические объекты (точечные множества), представляющие собой односвязные или многосвязные области, ограниченные одной или несколькими замкнутыми кривыми (граничными контурами). Данные объекты являются геометрическими моделями заготовок. Пусть также заданы – области размещения объектов (в общем случае, различные и многосвязные). Местоположение каждой заготовки в области размещения определяется тремя параметрами где – абсцисса и ордината фиксированной точки (полюса) в некоторой системе координат, – параметр, задающий ориентацию (угол поворота) объекта на плоскости. Таким образом, необходимо определить параметров размещения заготовок, при которых некоторая целевая функция
достигает своего экстремума и выполняются условия взаимного не пересечения объектов, условия размещения объектов внутри одной из областей размещения В1,В2,...,Вm , а также ряд дополнительных условий, определяемых свойствами раскраиваемого материала, серийностью производства и особенностями технологического оборудования, используемого для раскроя, т.е.
(1)
(2)
(3)
(4)
где (2) – условия взаимного не пересечения объектов, (3) – условия размещения в области размещения, (4) – другие условия, которые совместно с (2) и (3) определяют область допустимых решений, удовлетворяющих дополнительным геометрическим и технологическим ограничениям. На практике в качестве целевой функции F чаще всего используют функцию, значение которой равно т.н. коэффициенту использования материала (КИМ) или коэффициенту раскроя k.
, где Si– площадьi –того объекта, P– суммарная площадь занятой части областей размещения (использованного материала).
Сформулированная задача относится к классу задач математического программирования, для которых не существуют аналитических методов решения (прежде всего, из-за того, что ограничения (2)-(4) в аналитическом виде неизвестны). При решении такого рода задач используются вычислительные алгоритмы, в основном, приближенные [2-4]. Методы, гарантирующие получение глобального экстремума (точные методы), применимы к задачам c небольшой размерностью n и с сильными ограничениями на геометрическую форму заготовок [5-7]. В современном программном обеспечении для решения задач фигурного раскроя применяются как полностью автоматические методы, так и диалоговое проектирование, которое во многих случаях более эффективно, нежели другие методы.
Использование интерактивных методов связано еще и с тем, что эффективность алгоритмов автоматического проектирования фигурного раскроя существенно зависит от условий задачи: геометрической формы заготовок, их ассортимента, количественных характеристик, размеров материала и пр., причем характер этой зависимости остается крайне малоисследованным. Проведение таких исследований позволит повысить долю задач, решаемых в системах автоматизированного проектирования (САПР) раскроя материала в автоматическом режиме за счет того, что «неперспективные» алгоритмы будут отброшены еще на этапе анализа условий задачи. Предлагаемый подход можно реализовать следующим образом.
1. Вводим некоторую классификацию заданий фигурного раскроя листового материала, т.е. разбиение множества заданий на группы (классы) по определенным признакам.
2. Проводим тестирование имеющихся в распоряжении разработчика алгоритмов раскроя с целью выявления наиболее эффективного для каждого класса заданий.
3. Разрабатываем и включаем в состав программного обеспечения САПР фигурного раскроя процедуру автоматического выбора алгоритма в соответствии с результатами тестирования.
4. При решении конкретной задачи раскроя проводим предварительный анализ задания на предмет его принадлежности к какой-либо группе и выбираем алгоритм решения в соответствии с разработанной процедурой автоматического выбора алгоритма.
Для реализации сформулированного подхода предлагается произвести разбиение всех заданий фигурного раскроя по трем признакам: серийности производства, «прямоугольности» задания и преобладанию «крупных» заготовок над «мелкими». Поясним эти понятия.
Существующая в настоящее время типология производства по степени его серийности подразумевает три типа производства: единичное, мелкосерийное, крупносерийное (массовое). В качестве формального разделения задания на раскрой по признаку серийности будем использовать следующее правило: если суммарная площадь заготовок в задании не превосходит пятикратного значения площади области размещения, то задание будем относить к классу «единичных». Если суммарная площадь заготовок в задании превосходит двадцатикратное значение площади области , то задание будем относить к классу «крупносерийных». Остальные задания будем считать «мелкосерийными». Отметим, что данное разделение заданий сделано для проведения процедуры тестирования и не может служить определением понятий серийности производства.
В [8] было введено понятие «прямоугольности» задания. Поясним этот термин. Прямоугольностью задания на раскрой называется величина равная средней величине прямоугольности отдельных заготовок в задании, т.е.
, где – коэффициент прямоугольности заготовки . Прямоугольностью заготовки называется величина , где Si -площадь заготовки, - минимальная площадь среди прямоугольников, описанных вокруг внешнего контура заготовки.
По степени прямоугольности все задания будем разделять на 2 группы: задание со степенью прямоугольности 0.8 и все остальные.
По степени преобладания крупных заготовок все задания фигурного раскроя листового материала также разобьем на 2 группы: Задание считается состоящим из крупных заготовок, если суммарная площадь крупных заготовок составляют не менее 80% от площади всех заготовок в задании. Крупной называется заготовка, один из габаритов которой составляет не менее 0.6 от ширины листа.
Таким образом, в соответствии с тремя признаками все задания фигурного раскроя можно разбить на 12 классов. Для каждого из классов было подготовлено по 10 различных заданий (всего 120). Номенклатура заготовок была представлена ЗАО «Проммашсервис» (г.Екатеринбург). Число заготовок различной геометрической формы в заданиях варьировалось от 5 до 20. Суммарное число заготовок в заданиях выбиралось исходя из суммарной площади листов в задании (для тестирования использовался лист размерами 6000x1800 мм).
В качестве тестируемых алгоритмов были выбраны 2 алгоритма фигурного раскроя (NCL и «Штабель»), входящие в состав САПР «СИРИУС» [9] и алгоритм Nesting Factory, разработанный компанией Algomate (Израиль) [10]. Этот алгоритм имеет интерфейс с САПР «СИРИУС».
На рис. 1 показаны результаты тестирования алгоритмов для заданий единичного типа, состоящих из крупных заготовок со степенью прямоугольности 0.8, а на рис.2 - со степенью прямоугольности 0.8. На горизонтальной оси отмечено суммарное количество заготовок в каждом из 10 заданий, на вертикальной оси – КИМ для каждого из трех тестируемых алгоритмов.
Рис.1 – Единичное производство, крупные и непрямоугольные заготовки
Рис.2 – Единичное производство, крупные и прямоугольные заготовки
На рис.3. приведена схема выбора алгоритма раскроя, полученная на основании результатов проведенного тестирования. Номерами (от 1 до 12) обозначены классы заданий.
Единичное производство, крупные и непрямоугольные заготовки
Единичное производство, крупные и прямоугольные заготовки
Единичное производство, мелкие и непрямоугольные заготовки
Единичное производство, мелкие и прямоугольные заготовки
Мелкосерийное, крупные и непрямоугольные заготовки
Мелкосерийное, крупные и прямоугольные заготовки
Мелкосерийное, мелкие и непрямоугольные заготовки
Мелкосерийное, мелкие и прямоугольные заготовки
Крупносерийное, крупные и непрямоугольные заготовки
Крупносерийное, крупные и прямоугольные заготовки
Крупносерийное, мелкие и непрямоугольные заготовки
Крупносерийное, мелкие и прямоугольные заготовки
Рис.3 Схема автоматического выбора алгоритма фигурного раскроя в зависимости от класса задания
Таким образом, при решении задач фигурного раскроя в автоматическом режиме выбирается наиболее эффективный алгоритм оптимизации, что сокращает время проектирования рационального варианта раскроя и повышает коэффициент раскроя. Возможна реализация схемы автоматического выбора алгоритма с процедурой «самообучения» (т.е. с продолжением тестирования всех алгоритмов и изменением алгоритма выбора на основании результатов тестирования) при условии наличия достаточного временного ресурса у пользователя.
Выводы
При разработке универсальных САПР фигурного раскроя, ориентированных на решение широко круга задач раскроя, описанный подход, основанный на автоматическом выборе метода оптимизации с использованием сравнительного анализа алгоритмов, является наиболее целесообразным, поскольку попытки создать универсальный алгоритм фигурного раскроя, одинаково эффективный для всех классов задач, представляются автору малоперспективными.
СПИСОК ЛИТЕРАТУРЫ
Dykhoff H. A typology of cutting and packing problems // European Journal of Operational research. – 1990 – V.44 - P.145-159.
Мухачева Э.А., Верхотуров М.А., Мартынов В.В. Модели и методы расчета раскроя-упаковки геометрических объектов. - Уфа: УГАТУ, 1998. - 216с.
Фроловский В.Д. Оптимальное группирование геометрических объектов при проектировании карт раскроя материалов // Программные продукты и системы. - 2000, N3. - C.47-48.
Петунин А.А., Полевов А.В., Куреннов Д.В. Об одном подходе к решению задач раскроя-упаковки // Конструирование и технология изготовления машин. Сборник научных трудов. - Ч2. Вестник УГТУ-УПИ. Екатеринбург: УГТУ-УПИ, N18(70), 2005г. - С.212-216.
Липовецкий А.И. Свойства прямоугольных укладок // Препринт. УрО АН ССР, Институт машиноведения. Свердловск. - 1988. - 48с.
Картак В.М. Матричный алгоритм поиска оптимального решения для задачи упаковки прямоугольников в полубесконечную полосу // Информационные технологии. - 2008, N2. - C.24-30
Корницкая М.Н. Автоматизация пpоектиpования каpт фигуpного неpегуляpного pаскpоя в условиях единичного пpоизводства на основе аппpоксимационного подхода: Диссертация на соискание ученой степени кандидата технических наук. Уральский политехнический институт. - Свердловск, 1990. - 130с.
Петунин А.А., Мухачева Э.А., Мухачева А.С. Метод прямоугольной аппроксимации для решения задач нерегулярного фигурного раскроя-упаковки // Информационные технологии. - 2008, N1. - C.28-31.
Петунин А.А. Интегрированная САПР “Сириус” для автоматизации раскройно-заготовительного производства. Концепция. Опыт разработки и внедрения // Ресурсосберегающие технологии: математическое обеспечение оптимизационных задач в системах автоматизированного проектирования. (Сборник докладов первой всероссийской научно-практической конференции по вопросам решения оптимизационных задач в промышленности). - Санкт-Петербург: ЦНИИТС, 2001. - С.126-129.
Петунин А.А. Об одном подходе к выбору алгоритма расчета фигурного раскроя // III Международная научная конференция «Современные проблемы информатизации в системах моделирования, программирования и телекоммуникациях».
URL: http://econf.rae.ru/article/4803 (дата обращения: 20.04.2024).
Прочитать публикацию в формате PDF
–двумерныегеометрические объекты (точечные множества), представляющие собой односвязные или многосвязные области, ограниченные одной или несколькими замкнутыми кривыми (граничными контурами). Данные объекты являются геометрическими моделями заготовок. Пусть также заданы 
– области размещения объектов (в общем случае, различные и многосвязные). Местоположение каждой заготовки 
в области размещения определяется тремя параметрами 
где 
– абсцисса и ордината фиксированной точки (полюса) в некоторой системе координат, 
– параметр, задающий ориентацию (угол поворота) объекта на плоскости. Таким образом, необходимо определить 
параметров размещения заготовок, при которых некоторая целевая функция 
(1)
(2)
(3)
(4)
, где Si– площадьi –того объекта, P– суммарная площадь занятой части областей размещения (использованного материала).
, то задание будем относить к классу «единичных». Если суммарная площадь заготовок в задании превосходит двадцатикратное значение площади области 
называется величина равная средней величине прямоугольности отдельных заготовок в задании, т.е.
, где 
– коэффициент прямоугольности заготовки 
, где Si -площадь заготовки, 
- минимальная площадь среди прямоугольников, описанных вокруг внешнего контура заготовки.
0.8 и все остальные. 
0.8, а на рис.2 - со степенью прямоугольности 
