About one optimal solution example to the integrated 2d nesting and routing problem for cnc sheet cutting machines

Full Text

Введение

Во многих отраслях промышленности, включая авиастроение, автомобилестроение, машиностроение и др., широко распространен процесс резки листовых материалов в качестве заготовительной операции. Этот процесс заключается в вырезке плоских деталей из листового материала на технологическом оборудовании с числовым программным управлением (ЧПУ). В настоящее время в производственном цикле листовой обработки широкое применение нашло оборудование лазерной, кислородной, плазменной и гидроабразивной резки.

Проектирование управляющих программ (УП) для оборудования листовой резки с ЧПУ предполагает на первом этапе проектирование раскройной карты листового материала, при этом возникает известная задача раскроя-упаковки 2D Irregular Shape Packing Problem, или задача «нестинга» (Nesting Problem), которая относится к широкому классу задач Cutting&Packing [1]. На втором этапе для разработанной на первом этапе карты раскроя назначается траектория перемещения режущего инструмента, что порождает актуальные оптимизационные задачи минимизации времени и стоимости процесса резки деталей из листового материала на оборудовании с ЧПУ (Cutting Path Problem) [2, 3]. Следует отметить, что современные системы автоматизированного проектирования УП (Computer Aided Manufacturing, CAM-системы) в общем случае не гарантируют получения ни оптимального по затратам использованного материала варианта раскроя, ни оптимального по временным и стоимостным параметрам маршрута резки. Более того, даже оптимальное решение задачи маршрутизации, полученное для оптимального варианта раскроя, в общем случае не гарантирует экстремум интегрированного стоимостного оптимизационного критерия интегрированная задачи раскроя и маршрутизации (INRP), исследуемой в данной работе. Этот факт будет доказан и проиллюстрирован ниже. Интегрированная задача раскроя и маршрутизации представляет собой объединение двух упомянутых выше известных оптимизационных задач – задачу 2D-раскроя листового материала и задачу оптимальной маршрутизации инструмента машин листовой резки с ЧПУ. Отметим, что научные публикации, в которых задача оптимизации траектории инструмента рассматривается совместно с задачей раскроя, очень малочисленны, при этом оптимизационные критерии задачи 2D-раскроя и задачи маршрутизации, рассмотренные в этих работах, различны, поэтому, строго говоря, можно говорить о только двухкритериальных задачах оптимизации. Фактически первый критерий (величина расхода материала при раскрое) даже не учитывается, а задачей авторов является формирование раскройных планов, позволяющих уменьшить время процесса резки. В данной работе впервые дается полная математическая формулировка задачи INRP для единого оптимизационного критерия.

В существующих САМ-системах есть отдельные модули, которые позволяют в частных случаях решать некоторые оптимизационные задачи маршрутизации инструмента (например, минимизацию холостого хода), особенно если при проектировании траектории инструмента применяется стандартная техника резки «по замкнутому контуру». В свою очередь, применение техники т. н. мульти-контурной резки, когда несколько контуров вырезаются без выключения инструмента с использованием только одной точки врезки (см., например, применение «мостов» [4]) и техники совмещенного реза [5] на этапе маршрутизации инструмента может значительно сократить временные и стоимостные характеристики процесса резки. Однако для этих целей пользователи САМ-систем, как правило, вынуждены использовать интерактивный режим проектирования, который позволяет также выбирать допустимую с точки зрения деформаций материала траекторию резки деталей. Таким образом, актуальность разработки алгоритмического обеспечения, позволяющего в автоматическом режиме формировать раскройные карты и траекторию инструмента, обеспечивающего минимизацию расхода материала и стоимость процесса резки при одновременном соблюдении технологических ограничений резки, не уменьшается, несмотря на прогресс в создании высокоэффективного инженерного программного обеспечения. Следует отметить и невозможность применения точных алгоритмов для решения задач «нестинга» и Cutting Path Problem в реальном диапазоне размерностей из-за NP-трудности обеих задач. Строго говоря, термин NP применим только для упрощенных дискретных моделей задач фигурного раскроя и маршрутизации, поскольку эти задачи в изначальной постановке предполагают наличие континуального множества допустимых решений и не являются задачами дискретной оптимизации.

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

Результаты и обсуждение

Обзор текущего состояния исследований

По-видимому, впервые интегрированная задача 2D-раскроя и маршрутизации инструмента машин листовой резки с ЧПУ для случая одной целевой функции была сформулирована в [6]. Однако материалы конференции были опубликованы только в бумажном виде и не размещались в Интернете. Разработка концепции одного стоимостного критерия для INRP связана с необходимостью получения научно обоснованных данных о стоимости процесса резки на различном технологическом оборудовании с ЧПУ для различных марок и толщин материала. Такого рода табличные данные стали появляться только в последнее время (см., например, [7]), что создает хорошие предпосылки для создания оптимизационных алгоритмов, эффективных для решения практических задач. По существу, отсутствие данных, содержащих стоимостные параметры резки деталей для различных марок и толщин материала для конкретных типов технологического оборудования с ЧПУ, и есть основная причина того, что однокритериальная оптимизационная задача INRP не исследуется современными учеными. Если рассматривать статьи по проблеме интеграции задачи раскроя и маршрутизации в рамках многокритериальной оптимизации, то следует отметить [8], в которой рассматривается задача упаковки фигурных заготовок в полосе (Irregular Strip Packing Problem, 2D-SPP) и задача минимизации длины реза этих заготовок. В качестве целевой функции для задачи 2D-раскроя используется длина занятой части полосы. Авторы разработали математическую модель, которая обеспечивает получение точных решений интегрированной задачи при условии дискретизации множества допустимых вариантов размещения заготовок на раскройном плане. Как известно, получение точных решений в рамках предложенной модели возможно только для задач малой размерности из-за NP-трудности обеих оптимизационных задач. Примером разработки алгоритмов, ориентированных на получение экстремальных решений задачи маршрутизации инструмента при использовании непрерывной модели, является работа [9]. Вместе с тем, как уже отмечалось во введении, адекватность полученных оптимизационных решений задачи INRP зависит от технических характеристик использованного оборудования для резки. В [10] для проектирования технологических процессов раскроя кожи предложен подход, где формирование раскройной карты остается за человеком, а задача маршрутизации инструмента машины резки решается автоматически. Также двухэтапное проектирования маршрута инструмента описано в [11], где на втором этапе предложено использовать одну из популярных метаэвристик – алгоритм эмуляции отжига. Многокритериальный подход также используется в [12] для решения задачи комбинированного планирования раскроя и процесса резки при изготовлении металлоконструкций. В этой статье описана трехэтапная процедура решения, которая включает в себя разделение деталей для резки на несколько групп по некоторым правилам, создание различных вариантов раскройных карт в различных стратегиях и выбор подходящих маршрутов резки.

Разумеется, что любые алгоритмы решения интегрированных задач 2D-раскроя и маршрутизации базируются на подходах, предлагаемых исследователями при решении каждой из этих задач отдельно. Детальный обзор применяемых математических моделей, используемых для решения задач нерегулярного фигурного раскроя, приведен в [13, 14]. В общем случае, задачи «нестинга» содержательно формулируются следующим образом.

Пусть задано конечное множество двумерных геометрических объектов (множеств точек), представляющих собой односвязные или многосвязные области, ограниченные одной или несколькими замкнутыми кривыми (граничными контурами). Эти объекты представляют собой геометрические модели деталей. Пусть также на плоскости задан набор ограниченных областей размещения объектов (кусков материала). Необходимо разместить данные объекты в заданных областях таким образом, чтобы были соблюдены условия взаимного непересечения объектов, а также ряд дополнительных условий. Эти условия могут быть связаны со свойствами разрезаемого материала, серийностью производства, особенностями технологического оборудования, используемого для получения деталей из данного материала и т. д. Геометрическая форма области размещения может быть любой, но чаще всего это полу-бесконечная прямоугольная полоса (Irregular Strip Packing Problem, задача нерегулярной двумерной упаковки в полосе) или набор прямоугольников (2D Bin Packing Problem, упаковка в контейнеры). Если задана только одна область размещения, и не все объекты можно разместить в ней, то такая задача называется задачей о рюкзаке (Knapsack Problem). Оптимизационная задача раскроя заключается в поиске варианта размещения деталей (карты раскроя), для которого некоторая целевая функция достигает экстремума. В качестве такой функции чаще всего используется площадь использованного материала, или коэффициент использования материала КИМ (отношение общей площади размещенных деталей к площади использованного материала). Как известно, современные вычислительные алгоритмы не гарантируют получение оптимального решения для подавляющего числа практических задач «нестинга», но еще одна проблема оптимизации заключается в том, что оценка точности полученного решения также является нерешенной математической проблемой, включая и решение, которое является оптимальным, поскольку факт его оптимальности чаще всего невозможно доказать. Следует отметить, что для этих задач даже построение конечного множества допустимых вариантов раскроя небольшой размерности представляет сложную математическую и вычислительную проблему. Поэтому реальная минимизация функции стоимости раскроя (получение глобального экстремума) возможна только для простых геометрических форм [15]. Если все раскраиваемые детали имеют прямоугольную форму, то для такого класса задач современный математический аппарат позволяет разрабатывать специальные алгоритмы и соответствующее программное обеспечение, позволяющее получать на современных компьютерах точные или близкие к оптимальным решения задач в реальном диапазоне размерностей за приемлемое время (см., в частности, [16]). Вместе с тем, большая часть статей, исследующих задачи прямоугольного раскроя, посвящена применению эвристик [17]. Из последних работ на эту тему, содержащую хороший обзор моделей решения таких задач, отметим [18]. Помимо решения оптимизационных проблем пользователям CAM-систем на этапе раскроя приходится учитывать и некоторые технологические ограничения, связанные с применяемым технологическим оборудованием. Число публикаций по исследованию проблематики задачи маршрутизации режущего инструмента для машин листовой резки с ЧПУ уступает числу публикаций по Cutting&Packing, но в последние годы их число неуклонно растет. Обзор работ по маршрутизации инструмента машин лазерной резки приведен, например, в [2]. Здесь же дана классификация задач Cutting Path Problem. Большая часть математических моделей, используемых при решении задач маршрутизации инструмента, относится к моделям дискретной оптимизации. Задачи небольшой размерности могут быть решены с помощью точных методов [19], но, как и при решении задач раскроя – упаковки, современные алгоритмы ориентированы в основном на применение эвристических методов [20-23]. При этом часто в публикуемых алгоритмах не учитывают важные технологические ограничения листовой резки на оборудовании с ЧПУ. В частности, учет термических деформаций заготовок и искажение их геометрических размеров не являются предметом большинства исследований, что делает эти работы не в полной мере приемлемыми на практике. Из работ, учитывающих тепловые деформации материала при моделировании маршрута резки для машин листовой термической резки ч ЧПУ, отметим работы [24-27]. Обсуждаемый в данной работе подход для поиска минимального значения интегрированного стоимостного критерия задачи INRP ориентирован также и на уменьшение тепловых деформаций материала при термической резке, поскольку применение мульти-контурной техники резки совместно с техникой совмещенного реза пользователи CAM-систем обычно используют не столько для оптимизации раскроя или стоимости процесса резки, сколько для уменьшения термических деформаций материала.

Постановка задачи

Рассмотрим INRP в следующей постановке. В качестве основной задачи двумерного раскроя будем рассматривать задачу нерегулярного фигурного раскроя в прямоугольной полосе фиксированной ширины (2D-SPP), которая заключается в минимизации занятой части длины или площади этой полосы при размещении в ней конечного набора деталей произвольных заданных геометрических форм (в общем случае, различных). Для оценки качества решения в нашей постановке будем использовать стоимость использованного материала, рассчитанную через его массу m, умноженную на стоимость единицы массы материала $C_{mat}$:

$C_{nest}=m\times C_{mat}$ (1)

Очевидно, что допустимый вариант раскроя с минимальным значением площади используемого материала также будет соответствовать минимальному значению $C_{nest}$.

При получении деталей из листового материала на машине с ЧПУ стоимость процесса резки зависит от 3-х основных компонент траектории перемещения режущего инструмента (см. рис. 1): рабочего хода с включенным режущим инструментом (выделено пунктиром красного цвета), холостого хода с выключенным инструментом (синий цвет) и точек врезки в материал (точек пробивки) (отмечены кругами красного цвета). На рис. 1 показана схема резки (маршрута резки) двух заготовок с применением стандартной техники резки по целому контуру (а) и т. н. «цепной» резки, которая является частным случаем упомянутой выше мульти-контурной техники резки. Стоимость процесса резки, независимо от применяемой техники резки, рассчитывается по формуле (2) (см., например, [7]):

$C_{cut}=L_{off}\times C_{off}+L_{on}\times C_{on}+N_{pt}\times C_{pt}$ (2),

 

Рисунок 1 – Пример схемы резки двух заготовок с использованием стандартной (а) и мульти-контурной («цепной») (б) техник резки

 

где L_on – суммарная длина траектории рабочего хода; C_on – стоимость единицы пути рабочего хода; L_off – суммарная длина траектории холостого хода; C_off – стоимость единицы пути холостого хода; N_pt – количество точек врезки в материал; C_pt – стоимость одной врезки. Тогда интегрированный критерий стоимости C_INRP, суммирующий стоимость используемого материала и стоимость процесса резки на станке с ЧПУ, вычисляется очевидным образом:

$C_{INRP}=C_{nest}+C_{cut}$ (3)

Отметим, что значения параметров стоимости процесса резки C_on, C_off and C_pt зависят не только от станка с ЧПУ, но и от марки и толщины материала. Таким образом, целью оптимизационной задачи INRP является поиск допустимого варианта раскроя и соответствующего маршрута резки для машины с ЧПУ с минимальной общей целевой функцией затрат на раскрой и процесс резки (3). Как мы уже отмечали, схема резания допустима, если выполняются определенные условия, включая ограничения, обусловленные технологическими требованиями к процессу резку деталей на конкретном технологическом оборудовании с ЧПУ, например, т. н. «припуск на рез» или соблюдение правил «жесткости листа», позволяющих уменьшить тепловые деформации материала и искажение геометрических размеров вырезаемых деталей.

В качестве иллюстрации постановки задачи рассмотрим один простой пример задачи упаковки 11-ти деталей из алюминиевого листа (10-ти конгруэнтных полукругов 2-х типоразмеров и одного кольца в прямоугольной полосе шириной 1500 мм (задача относится к классу 2D Irregular Strip Packing Problem) и дальнейшего получения этих деталей из алюминиевого листа АМг3М толщиной 5 мм. Радиус полукругов – 470 мм (8 шт.) и 295 мм (2 шт.), радиус внешней окружности кольца – 312 мм, внутренней – 45 мм. Минимальное расстояние между деталями – 5 мм, минимальное расстояние до края полосы – 5 мм. На рис. 2 показаны два варианта раскроя с длиной занятой части полосы 2860 мм (а) и 2866 мм (б) и стоимостью использованного материала $C_{nest}$= 23595 руб. и $C_{nest}$= 23645 руб. соответственно.

 

Рисунок 2 – Пример двух раскройных карт для 11-ти алюминиевых деталей

 

Рис. 3 показывает соответствующие вариантам раскроя оптимальные маршруты резки со стоимостью процесса резки $C_{cut}$= 8520 руб. и $C_{cut}$= 7502руб. Схема резки 3-х пар деталей в нижнем ряду на рис. 3 (б) с использованием техники совмещенного реза и одной точки врезки показана на рис. 3 (с). В данном примере для вычисления значения стоимости процесса резки использованы данные о стоимости лазерной резки на станке ByStar3015 [7]. Значения стоимостных параметров процесса резки для алюминиевого листа АМг3М толщиной 5 мм следующие: C_on – 328,2 руб./м, C_{off –} 0,42 руб./м, C_{pt –} 32,2 руб.

 

Рисунок 3 – Схемы маршрутов резки для примеров раскроя на рисунке 2

 

Для поиска маршрута резки с минимальным значением $C_{cut}$ была использована дискретная модель задачи Cutting Path Problem в форме задачи о последовательном обходе мегаполисов [28] и применен алгоритм динамического программирования, который гарантирует оптимальное решение для этих условий. Значение интегрированного критерия C_INRP для варианта раскроя 2 (а) и маршрута резки 3 (а) равно 32115 руб. (23595 руб.+8520 руб.). Как мы видим, увеличение стоимости использованного материала на 50 руб. для раскройной карты 2 (б) с лихвой компенсируется уменьшением стоимости процесса резки на рабочем ходе за счет возможности применения техники совмещенного реза (выделен красной линией на рис. 2(б)). Поскольку суммарная длина совмещенных резов для этого варианта раскроя 2820 мм (3х940мм), то стоимость процесса резки уменьшится как минимум на 925 руб. При этом число точек врезки также сокращается с 12-ти (применении стандартной техники резки) до 9-ти. Незначительное увеличение холостого хода инструмента практически не влияет на суммарную стоимость процесса резки $C_{cut}$. Фактически она равна, как приведено выше, 7502 руб. В результате величина интегрированного критерия C_INRP для раскроя 2(б) и маршрута резки 3(б) составила 23645 руб.+ 7502 руб. =31147 руб.

Основной подход к решению задачи INRP

Заметим, что раскройная карта должна удовлетворять технологическим требованиям резки, поскольку используется конкретная машина листовой резки с ЧПУ. В свою очередь, траектория резания считается заданной, если для данной раскройной карты задана траектория инструмента, обеспечивающая вырезание всех раскроенных деталей из материала, указаны все необходимые точки врезки и точки выключения инструмента, а также движение инструмента между этими точками в режиме рабочего и холостого хода. При этом проектируемая траектория должна удовлетворять требованию допустимости деформаций термического материала, вызванных технологией термической резки. Понятно, что для любого фиксированного раскроя, чтобы найти путь резания с минимальным значением С_cut, необходимо стремиться минимизировать значения L_on and N_pt, так как стоимость холостого хода C_off современных станков для листовой резки с ЧП очень мала по сравнению с C_on and C_pt. Поэтому основным подходом к проектированию раскройных карт и маршрутов резки является формирование некоторого количества допустимых рациональных раскройных карт, допускающих применение техник совмещенного реза и мульти-контурной резки. К сожалению, в современных CAM-системах пользователи для этих целей должны применять преимущественно интерактивные процедуры, основанные на группировке конгруэнтных деталей с последующим формированием раскройных карт из сформированных групп и проектированием маршрутов резки с минимальными значениями времени и стоимости процесса резки. Пример формирования группы треугольных деталей показан на рис. 4.

 

Рисунок 4 – Схема резки группы треугольных деталей с применением мульти-контурной резки с совмещенным резом

 

Описание разработанных (для некоторых частных случаев задачи INRP) алгоритмов проектирования маршрутов резки в автоматическом режиме выходит за рамки тематики этой статьи, поэтому ограничимся примером двух раскройных карт для треугольных деталей (рис. 5), полученных в полуавтоматическом режиме с целью минимизации значений L_on and N_pt, что обеспечивает существенное уменьшение интегрированного критерия C_INRP при получении этих деталей из большинства марок материала на различном технологическом оборудовании с ЧПУ в сравнении с раскройными картами, предполагающими использование стандартной техники резки. Данные раскройные карты были спроектированы на одном из машиностроительных предприятий г. Екатеринбурга.

 

Рисунок 5 – Раскройные карты с треугольными деталями, вырезаемыми с применением техники совмещенного реза

 

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

О глобальном экстремуме задачи INRP

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

Пусть $A=\left\{nest\right\}$ множество всех допустимых раскройных карт для исходной задачи (1), и на этом множестве задана целевая функция $F_1\left(nest\right)=C_{nest}$. Тогда оптимальное решение задачи раскроя $nest*\in A$ будет удовлетворять следующему условию: $F_1(nest*)\le F_1\left(nest\right)$$\forall nest\in A$. Обозначим через $R_{nest}=\left\{rout{e}_{nest}\right\}$ множество всех допустимых маршрутов резки для раскроя nest, на котором задана целевая функция $F_2\left(rout{e}_{nest}\right)=C_{cut}$ (2). Пусть также найден оптимальный маршрут резки $route{*}_{nest*}\in R_{nest*}$ для оптимального раскройного плана nest* с минимальным значением  для заданных значений стоимостных параметров C_on, C_off и N_pt, т. е.  $F_2\left(route{*}_{nest*}\right)\le F_2\left(rout{e}_{nest*}\right)$$\forall rout{e}_{nest*}\in R_{nest*}$  Тогда справедливо следующее Утверждение:

Утверждение.

Значение $F=F_1(nest*)+F_2\left(route{*}_{nest*}\right)$, в общем случае, не является минимально возможным значением интегрированного критерия C_INRP (3) задачи (1)–(3).

Сформулированное утверждение еще раз подтверждает актуальность разработки алгоритмов для интегрированной задачи 2D-раскроя листового материала на фигурные заготовки и маршрутизации инструмента машин листовой резки с ЧПУ с единым стоимостным критерием оптимизации. Для доказательства этого утверждения достаточно привести один пример. Рассмотрим один простой пример задачи упаковки пяти заготовок (3-х кругов одного диаметра и двух прямоугольников) в прямоугольной полосе шириной 1500 мм (задача относится к классу 2D Irregular Strip Packing Problem). Диаметр кругов – 745 мм, размеры прямоугольников – 693 мм х 270 мм и 693 мм х 470 мм. Минимальное расстояние между внешними контурами деталей (припуск на рез) – 5 мм, минимальное расстояние до края полосы – 2,5 мм. Ширина совмещенного реза – 1,8 мм. На рис. 6 (а) показан вариант раскроя, который является оптимальным решением задачи «нестинга», поскольку обеспечивает минимальную длину занятой части полосы (приблизительно 1447 мм) и минимальную площадь использованного материала, значение которой в данном конкретном случае является глобальным экстремумом. Как нетрудно видеть, оптимальное значение  теперь легко вычисляется по формуле (1).

 

Рисунок 6 – Пример оптимального 2D-раскроя и соответствующему ему оптимального маршрута резки

 

На рис. 6 (б) показана схема оптимального маршрута резки для этого модельного примера. Мы уже отмечали, что для реальных задач «нестинга» чрезвычайно редко удается доказать, что полученный с помощью какого-либо алгоритма вариант раскроя является глобальным экстремумом задачи (1). В данном случае это удалось сделать, поскольку простые геометрические вычисления показывают, что любое другое размещение кругов в полосе увеличивает длину ее занятой части. Как и в случае с примерами на рис. 2 и 3, для построения оптимальной траектории инструмента машины с ЧПУ был использован алгоритм динамического программирования. Величина интегрированного критерия C_INRP рассчитана для материала марки Ст3 толщины 20 мм и машины гидроабразивной резки PTV WJX XYG-1Z-EKO. Данные по стоимостным параметрам C_on, C_off и C_pt для данного вида оборудования предоставлены одним из российских предприятий, оказывающим услуги по листовой резке. Стоимость использованного материала  в данном случае составила приблизительно 10223 руб., стоимость процесса резки – 9815 руб., а величина интегрированного критерия C_{INRP –} 10224 руб. + 9815 руб. = 20039 руб. На рис.7 (а) приведен вариант неоптимального раскроя для этого примера с длиной использованного материала 14997 мм и значением  = 10596 руб. Однако совмещенный рез (выделен красным цветом) позволяет уменьшить величину стоимости процесса резки до 9282 руб., а суммарный критерий C_{INRP –} до 19878 руб. Схема резки двух прямоугольников на рис. 7 (б) аналогична схеме резки полукругов на рис. 3 (б).

 

Рисунок 7 – Пример неоптимального раскроя и схемы маршрута резки с меньшим значением интегрированного критерия Сcut, чем для оптимального раскроя

 

Таким образом, подтверждена справедливость сформулированного утверждения и независимость глобального экстремума задачи INRP от глобального экстремума задачи «нестинга» для данного конкретного примера. Этот факт представляется важным еще и потому, что позволяет пользователю CAM-систем при проектировании управляющих программ для машин листовой резки с ЧПУ изначально отказаться от идеи поиска оптимального решения задачи 2D-раскроя и ориентироваться на формирование вариантов раскроя, перспективных с точки зрения величины интегрированного критерия C_INRP. К перспективным вариантам могут быть отнесены раскройные карты с совмещенным резом и допускающие применение техники мульти-контурной резки.

Заключение и выводы

1. В статье впервые дана полная математическая постановка новой экстремальной задачи (INRP, Integrated Nesting and Routing Problem) c одной интегрированной аддитивной целевой функцией стоимости, объединяющая две известные оптимизационные задачи: задачу фигурного 2D-раскроя (Nesting Problem) и задачу оптимальной маршрутизации инструмента машин листовой резки с ЧПУ (Cutting Path Problem).
2. На модельном примере доказано утверждение о независимости глобального экстремума INRP от глобального экстремума задачи «нестинга», соответствующей интегрированной задаче.
3. Наряду с модельным примером приведен практический пример, обосновывающий актуальность интегрированной задачи INRP.

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

About the authors

Alexander A. Petunin

Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences

Author for correspondence.
Email: a.a.petunin@urfu.ru

Doctor of Technical Sciences, Professor, Ural Federal University,  Leading Researcher

Russian Federation, Ekaterinburg

Natalya S. Kotel

Ural Federal University

Email: n.s.skliarova@urfu.ru

Senior Lecturer

Russian Federation, Ekaterinburg

Anastasia F. Tavaeva

Researcher of Ural Federal University

Email: tavaeva_a_f@bk.ru

Ph. D. in engineering, Chief Specialist,  Ural Optical and Mechanical Plant

Russian Federation, Ekaterinburg

References

Supplementary files