Оптимальный раскрой материалов

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

На практике наиболее часто материальные ресурсы представлены в виде рулонов (Рис.1), полос, прямоугольных листов, стержней и т.п.

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

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

Однако учитывая современное развитие высокопроизводительных средств вычислительной техники (таких как CUDA - Compute Unified Device Architecture), появляется больше возможностей для использования точных алгоритмов, что ведет к повышению точности расчетов. CUDA - программно-аппаратная архитектура, которая позволяет существенно (на несколько порядков) повысить вычислительную производительность ЭВМ благодаря использованию графических процессоров видео модуля (видеокарты). Архитектура видеокарты позволяет «распараллелить» обработку данных. Кроме того, скорость обмена между памятью и видеопроцессором получается значительно выше, чем в классической схеме: оперативная память-кэш-центральный процессор. Это происходит за счет распараллеливания данных - в тот момент, когда одни данные в видеокарте начинают обрабатываться одним потоковым процессором, другие данные параллельно загружаются в другой. На финансовом рынке, к примеру, компании Numerix и CompatibL при использовании CUDA в программном продукте, предназначенном для анализа риска контрагентов, достигли ускорения работы в 18 раз. Numerix используется почти 400 финансовыми институтами в мире, включая BNP Paribas в секторе банковских услуг.

CUDA® от NVIDIA - это параллельная вычислительная платформа и модель программирования, которая имеет набор расширений для языков программирования C и С++, позволяющих выражать параллелизм данных и задач на уровне мелких и крупных структурных единиц. Это существенно упрощает использование этой технологии для задач раскроя-упаковки, при этом возможна реализация как точных, так и эвристических алгоритмов при значительном (более чем в 10 раз) сокращении затрат машинного времени на расчеты.

Наиболее простым вариантом для определения оптимального раскроя является одномерный (1D) линейный раскрой (Рис. 3), т.е. материал для раскроя на заготовки заданных размеров поступает в виде одинаковых рулонов (стержней, полос). В этом случае составляется карта всех возможных вариантов раскроя по одному измерению (к примеру, по длине или по ширине материала), причем остаток в каждом варианте должен быть меньше длины (или ширины) заготовки, имеющей наименьшую длину (или ширину). При составлении карты раскроя необходимо учитывать также такие технологические параметры оборудования для резки (штамповки и т.д.), как  толщина реза, ширина боковых кромок и т.п.

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

Далее решается система линейных алгебраических уравнений методом Жордана–Гаусса. Допустимое решение, для которого целевая функция достигнет максимума (или минимума), будет оптимальным решением. Этот алгоритм реализован в программном продукте «C-MES: Управление производством» (далее C-MES). В C-MES при 1D раскрое рулонов предусмотрена также оптимизация смены ножей, т.е. ведется дополнительная обработка найденного решения для достижения минимального количества смен ножей.

Экономический эффект от использования C-MES для линейного раскроя (рулонов, стержней, рельс и т.п.) заключается в следующем:

• повышение выхода готовой продукции (от 2% и выше);
• снижение затрат на наладку оборудования;
• сокращение сроков выполнения производственных заказов (до 10%);
• повышение оперативности составления планов.

Общая экономия в данном случае будет рассчитываться по формуле:

                                    Э = Э_Н + Э_СД,       

где Э_Н - экономия от снижения нормы расхода материальных ресурсов,

Э_СД - экономия по заработной плате работников предприятия и сборам, начисляемым на их зарплату.

На примере расчёта экономической эффективности метода оптимального раскроя для металлообрабатывающих предприятий  следует, что в результате применения метода оптимального раскроя материала, затраты на выпуск продукции в среднем  сокращаются  на 9,32 %.

Значительный интерес представляет задача двумерного (2D) прямоугольного раскроя-упаковки. Это обусловлено обширной областью практического применения данных задач, а также высокой сложностью решаемой задачи. Ввиду сложности этой задачи на практике широко используются эвристические алгоритмы решения. Появление и развитие вероятностных методов локального поиска оптимума привело к разработке алгоритмов, которые служат декодерами в многопроходных алгоритмах.

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

В зависимости от текущих входных данных выбирается тот или иной способ улучшения перебора и также производится предварительная подготовка входных данных под выбранный способ перебора. Указанные операции позволяют сократить время вычислений до приемлемого (экономически) уровня. Условия размещения прямоугольников описываются системой линейных неравенств и таким же числом целочисленных переменных. Полученная система неравенств решается с использованием методов линейного программирования. В данном случае алгоритм, позволяет гарантированно точно (или оптимально) решать задачу прямоугольного раскроя. Результат работы этого алгоритма, реализованного в программном продукте «C-MES: Управление производством» показан на Рис.4.

Также возможна дополнительная оптимизация с целью увеличения площади одного из остатков (Рис. 5).

Экономический эффект от использования C-MES для прямоугольного раскроя складывается из тех же составляющих как и для линейного раскроя. Но повышение выхода готовой продукции при этом может составлять уже до 10%, а оперативность составления планов может возрасти на 50%. Это объясняется тем, что данный вид раскроя является более трудоемкой операцией, и в большинстве случаев результат планирования такой задачи без использования эффективных инструментов будет не оптимальным. Следовательно экономический эффект от внедрения C-MES для 2D раскроя будет более значительным при оптимальной загрузке оборудования, позволяющего производить прямоугольный раскрой (Рис. 6).

При решении задач трёхмерного раскроя (упаковки) (3D) используются, в большинстве случаев, эвристические (приближенные) алгоритмы. Любое приближенное решение предполагает наличие алгоритма, который бы позволил определить, как именно производить трехмерный раскрой или располагать коробки в контейнере. В основном они строятся на декомпозиции - сведению этих задач к задачам меньшей размерности. Применяются различные варианты этой процедуры – к примеру, разбиение на слои и заполнение каждого слоя по индивидуальному алгоритму  или «постройка стены». Существуют алгоритмы, когда после заполнения каждого слоя или «построения стены» производится дополнительная оптимизация.

Количество точных алгоритмов решения трехмерной задачи раскроя-упаковки ограничено по сравнению с числом имеющихся эвристических методов оптимизации. Одна из причин этого заключается в сложности представления вероятной упаковки и введения ограничений из реальных задач. Тем не менее, для решения этой проблемы были разработаны различные методы. К примеру, модель, основанная на декартовой системе координат обеспечивает вертикальную, горизонтальную стабильность и в большинстве случаев позволяет находить оптимальное решение. Теоретически обоснован также метод плоскостей для решения задач 3D раскроя. Вариант направления загрузки трёхмерного ортогонального контейнера, на примере реализации алгоритмов для решения задач ортогональной упаковки объектов,  показан на Рис.7.

В концепции C-MES определение оптимального 3D раскроя используется также как решение задачи упаковки грузов при транспортировке между производственными площадками предприятия.

Таким образом, программа (алгоритм) любого (1D, 2D, 3D) раскроя включает в себя два основных этапа: этап построения карты всех возможных вариантов раскроя и этап расчёта оптимальных вариантов раскроя.

В связи тенденцией на повсеместное использование в последнее время искусственных нейронных сетей (ИНС) представляется возможным и даже перспективным их применение для решения задач 3D раскроя, не смотря на то, что обучение ИНС является сложным и трудоемким процессом.

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

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

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

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

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

C-MES является сложным бизнес-приложением, предназначенным для выполнение таких больших вычислительных задач как задачи раскроя. Экономически целесообразные временные затраты на решение задач 2D и 3D раскроев можно получить только при использовании параллельных вычислений, которые могут реализованы несколькими способами: либо локально (к примеру, хотя и не во всех случаях, с использованием технологии CUDA), либо с использованием центров обработки данных (ЦОД). C-MES может поставляться в обоих вариантах, причем второй вариант (использование ЦОД в модели SaaS) для небольших и средних предприятий является менее затратным, при этом такие компании могут использовать большие вычислительные мощности, чтобы дать возможность всем заинтересованным лицам, подразделениям принимать эффективные решения.