3.4 MTC Software ProNest 8 Nesting Software

Использование программы раскроя ProNest's приводит к эффективному использованию материалов, без падения скорости решения задачи или потери гибкости. Уникальная особенность Оптимизации Системы Раскроя позволяет автоматически оценивать различные стратегии раскроя, размеры листа и параметры раскроя, чтобы определить самое эффективное, дешевое решение.

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

Особенности системы:

• 
  Автоматический импорт CAD-документов (DWG, DXF, IGES, DSTV)
  
• 
  Определение стиля размещения исходя из используемого материала
  
• 
  Возможность перетаскивать детали вручную
  
• 
  Обнаружение наложений и примыканий
  
• 
  Управляемый пользователем постпроцессор
  

1. 
   Методы решения задачи
   

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

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

1. 
   Выбор очередности раскраиваемых заготовок.
   
2. 
   Выбор очередности детали для расположения на заготовке.
   
3. 
   Выбор варианта раскладки детали на листе заготовки.
   

4.1 Выбор очередности раскраиваемых заготовок

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

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


4.2 Выбор очередности детали для расположения на заготовке

- По площади детали. Детали упорядочиваются по площади и сначала размещаются те из них, чья площадь больше. Таким образом, удается сразу разместить те детали, которые наиболее требовательны к площади заготовки.

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




Рис. 1. а) Вариант, когда сначала была размещена «фигура 2», а затем «фигура 1». б) Вариант, когда сначала размещена «фигура 1», имеющая наибольшую площадь. В этом случае размещение «фигуры 2» невозможно.


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


4.3 Выбор варианта раскладки детали на листе заготовки

- По площади описанного прямоугольника. Из всех доступных положений заготовки выбирается то, при котором площадь описывающего прямоугольника наименьшая. Таким образом, положение детали с площадью si считается рациональным, если в точке Mi площадь описанного прямоугольника меньше, чем в одной из предыдущих положений. Определив для указанной точки Mi соответствующие значения параметров si (i, xi, yi), система автоматически просматривает положение в следующих точках и отбирает те из них, где площадь описанного прямоугольника минимально. На рис. 2, б площадь описанного прямоугольника меньше, чем на рис. 2, а.




Рис. 2. Построение описанного прямоугольника одной и той же детали.


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




Рис. 3. Использование гравитационной точки G для определения рационального положения детали.


5 Разработка информационной модели системы

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

Основным является класс схемы раскроя TNestingScheme, который помимо прочих параметров содержит два массива. Первый массив это массив деталей, которые будут размещаться во время решения задачи раскроя. А второй массив это массив заготовок, на которых будут размещаться детали. Оба массива строятся на базе класса ArrayList, каждый элемент которого является ссылкой на объект любого типа. Соответственно в массиве деталей каждый элемент будет являться ссылкой объект детали TSchemeElement, а в массиве заготовок это будет ссылкой на объект заготовки TSchemeLaying.

Класс TSchemeElement, поскольку он представляет собой деталь, должен содержать ее геометрию. Геометрию можно описать тем же способом, каким это сделано в T-FLEX, а именно разделением штриховки на контуры, а контуров на сегменты. Из этого выходит, что деталь может быть описана только одной геометрией, т.е. отношение классов TSchemeElement и TArea будет 1:1. Штриховка же должна содержать минимум один контур, и соответственно их отношение будет 1:1..*. Та же ситуация и с сегментами, контур должен содержать минимум один сегмент и их отношение будет также 1:1..*.

И наконец, класс TFigureRout, предназначенный для расчета задачи раскроя и хранения результатов раскроя. Он является членом класса TNestingScheme и соотносится с ним как 1:1.

Для представления отношений между классами был выбран язык моделирования UML, как наиболее подходящий для этой цели. На рис.1 представлена получившаяся диаграмма классов разрабатываемой системы.



Рис. 4. Диаграмма классов системы.


6 Разработка математической модели

Прежде чем начинать рассмотрение имеющихся способов решения задачи раскроя требуется разработать ее математическую модель.

Задача раскроя листового проката на детали различных сложных геометрических конфигураций заключается в следующем. Необходимо из прямоугольных m листов стандартной ширины H1, H2, …, Hj, …, Hm и определенной длины L1, L2, …, Lj, …, Lm выкроить n деталей площадью si (i = 1, …, n) различных размеров и конфигураций в определенных количествах. Требуется определить рациональный план раскроя листового проката, выбирая из множества заданных деталей детали с площадью si. Оставшиеся подмножества деталей рассматриваются в качестве исходных для заполнения следующего листаю.

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

Экономичность раскроя металла характеризуется коэффициентом раскроя Kp, который для двух или нескольких различных деталей определяется отношением суммы площадей всех деталей из листа к площади листа:

,

Где si – площадь i-й заготовки; ni – число i-х заготовок, вырезаемых из одного листа; S – общая площадь листа.

Таким образом в общем случае целью решения задачи раскроя будет являться минимизация коэффициента раскроя:




7 Разработка алгоритма

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

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


7.1 Преобразование геометрии

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

Поэтому для упрощения алгоритма и для повышения производительности следует преобразовать сложную геометрию. Так, например все кривые можно заменить ломаными линиями (полилиниями). В T-FLEX CAD эллипсы и дуги эллипса изначально представлены полилиниями, поэтому их геометрию упрощать не требуется, хотя в некоторых случаях, можно упростить ее еще, если брать опорные точки через n пропущенных точек. Остается решить вопрос с преобразованием геометрии окружностей и их дуг. На рис. 1 показан результат такого преобразования, а далее приведены пояснения.




Рис. 5. Замена окружности ломаной линией с шагом угла в 30 градусов.


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


7.2 Вычисление координат гравитационной точки (ГТ)

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

Для вычисления координат ГТ детали был выбран следующий метод: после того, как контур детали преобразован в полилинию, он будет представлять собой многоугольник. Сначала выбирается направление обхода многоугольника, либо по часовой стрелке, либо против. Одна из вершин многоугольника помечается как начальная и начиная с нее будет производиться обход (Рис.1). На каждом шаге обхода выбираются две соседние вершины, и вычисляется площадь сегмента ограниченного ребром, построенным на этих вершинах, осью абсцисс и двумя вертикалями, проходящими через точки начала и конца ребра. Если значение x точки начала ребра больше значения х точки конца ребра, то значение площади сегмента берется со знаком минус (A3), в противном случае она берется со знаком плюс (A0).




Рис. 6. Вычисление координат гравитационной точки путем разбиения детали на сегменты.


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



Рис. 7. Положение гравитационных точек прямоугольного треугольника (а) и прямоугольника (б).

Полученные значения координат ГТ и площадей простых фигур подставляются в формулы (1) и (2) для получения координат ГТ сегмента.

После того, как будут вычислены площади всех сегментов и их гравитационные точки, можно вычислить координаты гравитационной точки по формулам (1) и (2).



где - площадь i-го сегмента, а и - координаты гравитационной точки i-го сегмента.

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



Рис. 8. Результат преобразования всех контуров детали в одну полилинию.