Перейти к основному содержанию
ИТарктика
УДК: 608.3; 519.673
Берш Алексей Васильевич, Мельников Вадим Андреевич
генеральный директор общества с ограниченной ответственностью «СТАЛКЕР КОММУНИКАЦИОННАЯ ГРУППА»;
руководитель совместной научно-технической лаборатории «СТАЛКЕР» (ООО «СТАЛКЕР» и Федеральное государственное бюджетное образовательное учреждение высшего образования «СыктГУ им. Питирима Сорокина»)

студент, Институт точных наук и информационных технологий
ФГБОУ ВО «СыктГУ им. Питирима Сорокина»

Алгоритм для раскроя двумерного материала
Аннотация:

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

Ключевые слова: раскрой, генетические алгоритмы, двумерное пространство..

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

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

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

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

Пример: соотношение потерь в денежном (руб.) и количественном (квадратные метры) выражении при фигурной резке стекла на предприятии ООО «Белые окна», полученное по результатам применения ПО «Раскрой».

ло

Рис.1. Соотношение потерь при резке стекла (руб.).

дло

Рис.2. Соотношение потерь при резке стекла (М2).

 

Основная характеристика раскроя — количество измерений:

  • раскрой в одномерном пространстве;
  • раскрой в двумерном пространстве;
  • раскрой в трёхмерном пространстве.

Например, загрузка поддонов является задачей в двумерном пространстве. В отличие от задач в двух и более измерениях, задача в одномерном пространстве имеет явное решение. Достаточно подробно данная задача описывается в книге Канторовича-Залгаллера – «Рациональный раскрой промышленных материалов» [2]. Так же в данной книге можно найти методы решения задач двумерного раскроя для случая прямоугольных заготовок.

К другим основным характеристикам «раскроя» относятся: количественные характеристики, геометрические характеристики и характеристики по ограничениям на результат.

Прежде чем переходить к алгоритмам, применяемым для решения задачи раскроя, следует рассмотреть математическую постановку задачи. Задача ставится по аналогии с задачей раскроя в одномерном пространстве [3].

Имеется сырьё площади S, на котором необходимо расставить заготовки M различных типов. Площади заготовок задаются вектором s, а количество заготовок каждого типа задаётся вектором b.

Пусть матрица A[M,N]  – целочисленная матрица всех потенциально возможных способов раскроя одной единицы сырья, |N|=n – число таких способов. Потенциально возможный способ раскроя – столбец матрицы  ка, удовлетворяющий условию:

                    ьти                                           (1)

Пусть x[M]Изображение удалено. – искомый вектор, являющийся некоторым столбцом матрицы A. Тогда задача минимизации суммарных отходов сырья запишется следующим образом:

пг

f=S-xTM⋅sMminxM≤b[M]S-xTM⋅sM≥0xM≥0[M]                                     (2)

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

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

  • Данный продукт реализует решение задачи с помощью генетических алгоритмов.
  • Предполагается уменьшение отходов при внедрении продукта до 21,3%.
  • Генетический алгоритм гарантированно находит некоторое решение, предположительно являющееся оптимальным – некоторая последовательность фигур.
  • Представления фигур: аппроксимация полигоном, растром, true shape.
  • В настоящий момент подготовлен «пакет документов» для патентования инновационного решения.
  • Внедрение продукта не предполагает изменения технологии производства, так как является лишь математическим решением задачи подготовки плана раскроя. Сам технический план не затрагивается.

шо

Рис.3. Пример работы ПО «РАСКРОЙ»: 63 фигуры за 2,4 минуты.

При использовании программы «раскроя» потери (отходы) при раскрое материала составляют в среднем 2,7%, что на 21,3% меньше, чем потери при резке материала без использования программы «раскроя».

Финансовая выгода от использования программы «раскроя» на примере резки стекла составляет 2 096 454 рублей.

длот

Рис.4. Соотношение затрат при использовании программы «раскроя».

Примечание: расчёт составлен по результатам фигурной резки стекла на предприятии ООО «Белые окна» с применением ПО «Раскрой».

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

К конкурентным преимуществам разрабатываемого программного обеспечения можно отнести:

  • является самостоятельным программным обеспечением;
  • кроссплатформенность, позволяющая интегрировать ПО непосредственно в станки с ЧПУ;
  • возможность регулировать соотношение скорость-качество;
  • низкие требования к аппаратным ресурсам.

Список литературы

  1. Dyckhoff H. A typology of cutting and packing problems. [Text] / European Journal of Operational Research. – 1990. – № 44. – P. 150—152.
  2. Залгаллер В.А., Канторович Л.В. Рациональный раскрой промышленных материалов. [Текст] / Новосибирск: Наука. – 1971. – 299 с.
  3. Никитенков, В.Л., Холопов А.В. Задачи линейного программирования и методы их решения. [Текст] / Сыктывкар: СыктГУ. – 2008. – 143 с.