Задача раскроя

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

Согласно данным Конфедерации европейских производителей бумаги, в 2012 году 1331 бумагоделательная машина в регионе производит в среднем отходов на 56 млн евро (примерно 73 млн долларов США) каждая. Экономии даже 1 % будет очень существенной.

Формулировка задачи и подходы к решению

Стандартная формулировка задачи раскроя (но не единственная) предполагает список m заказов, в каждом заказе требуется $q_{j},j=1,\ldots ,m$ кусков. Образуем все возможные комбинации раскроя («карты раскроя») и связываем с каждой картой положительную целую переменную $x_{i}$, показывающую, сколько раз карта использовалась. Выпишем задачу линейного программирования:

$\min \sum _{i=1}^{n}c_{i}x_{i}$

$\sum _{i=1}^{n}a_{ij}x_{i}\geq q_{j},\quad \quad \forall j=1,\dots ,m$

$x_{i}\geq 0$, целое

где $a_{ij}$ — сколько раз заказ $j$ появляется в карте $i$ и $c_{i}$ — цена (часто потери) карты $i$. Точная природа ограничений может вести к слегка различным математическим характеристикам. Приведённые ограничения являются ограничениями на минимум (по меньшей мере заданное количество должно быть произведено, но не исключается, что будет произведено и больше). Если $c_{i}=1$, требуется минимизировать число разрезаемых кусков исходного материала. Если ограничения с неравенств заменить на равенства, задача называется упаковкой в контейнеры. В более общей формулировке ограничения двухсторонние (и в этом случае решение минимизации потерь может отличаться от решения с минимальным числом кусков исходного материала):

$q_{j}\leq \sum _{i=1}^{n}a_{ij}x_{i}\leq Q_{j},\quad \quad \forall j=1,\dots ,m$

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

В целом, число возможных карт растёт экспоненциально от m, числа заказов. При росте числа заказов может оказаться непрактичным перечислять возможные карты раскроя.

В качестве альтернативы можно использовать генерацию столбцов. Этот метод решает задачу раскроя, начиная с нескольких карт. Метод образует новые карты, если они потребуются, в процессе решения. В одномерном случае новые карты появляются при решении дополнительной оптимизационной задачи, задачи о ранце, в которой используется информации о двойственных переменных задачи линейного программирования. Задача о ранце имеет хорошо известные методы её решения, такие как метод ветвей и границ и динамическое программирование. Метод отложенной генерации столбцов может оказаться много эффективнее исходного подхода, особенно при росте размера задачи. Отложенная генерация столбцов в применении к задаче раскроя впервые использована Гилмором и Гомори в серии статей, опубликованных в 1960-х годах. Они показали, что этот подход приводит гарантированно к (дробному) оптимальному решению без необходимости перечислять все возможные карты заранее.

Исходный метод Гилмора и Гомори не был целочисленным, так что решение могло содержать дробные составляющие, например, некоторая карта должна была использоваться 3,67 раз. Округление до ближайшего целого часто не работает, в том смысле, что это приводит к подоптимальному решению и недопроизводству или перепроизводству для некоторых заказов (и возможное нарушение ограничений, если они двусторонние). Этот недостаток преодолён в новых алгоритмах, которые позволяют находить оптимальные решения (в смысле нахождения решения с минимальными отходами) очень больших задач (в общем случае больших, чем нужно на практике).

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

• Задача нахождения минимального числа карт раскроя: найти решение с минимальным числом карт раскроя среди решений с минимальными потерями. Эта задача очень трудна, даже если потери известны. Существует гипотеза, что любая ограниченная равенствами одномерная задача раскроя с n заказами, имеет по меньшей мере одно решение на минимум отходов с n + 1 картами раскроя. Верхние границы числа карт раскроя не известны, хотя примеры с n + 5 известны.

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

• Задача минимального числа смен ножей (для одномерной задачи раскроя): найти последовательность применения карт раскроя, чтобы минимизировать число перемещений режущих ножей. Данная задача является частным случаем обобщённой задачи коммивояжёра.

Иллюстрация одномерной задачи раскроя

Бумагоделательная машина может производить неограниченное число рулонов (заготовок), каждая 5600 мм шириной. Нужно получить следующие 13 конечных рулонов:

Ширина	Рулонов
1380	22
1520	25
1560	12
1710	14
1820	18
1880	18
1930	20
2000	10
2050	12
2100	14
2140	16
2150	18
2200	20

Решение

Решение с минимальными отходами, в котором минимизировано число смен ножей. Смена ножей показана маленькими зелёными кружочками

Имеется 308 возможных карт раскроя для этой маленькой задачи. Оптимальное решение требует 73 исходных рулона и имеет 0,401 % отходов. Можно показать, что минимальное число карт раскроя для такого количества отходов равно 10. Можно также вычислить, что существует 19 таких различных решений, каждое с 10 картами раскроя и 0,401 % отходов. Одно из таких решений показано ниже и на рисунке:

Число карт	Разрезы
2	1820 + 1820 + 1820
3	1380 + 2150 + 1930
12	1380 + 2150 + 2050
7	1380 + 2100 + 2100
12	2200 + 1820 + 1560
8	2200 + 1520 + 1880
1	1520 + 1930 + 2150
16	1520 + 1930 + 2140
10	1710 + 2000 + 1880
2	1710 + 1710 + 2150
73

Классификация

Задачи раскроя можно классифицировать различными способами. Один путь — размерность раскроя: выше приведённый пример иллюстрирует одномерный раскрой (1D). Другие промышленные применения 1D раскроя — резка труб, кабелей и стальных прутков. Двумерные задачи применяются при производстве мебели, одежды и стекла. Существует не так уж много трёхмерных применений раскроя, однако близкие трёхмерные задачи упаковки имеют много промышленных приложений, в частности, распределение объектов в контейнеры для водного транспорта (смотрите, например, Контейнерные перевозки, близкая к ней задача упаковки шаров изучалась с 17-го столетия (Гипотеза Кеплера)).

Задача раскроя в бумажной, плёночной и сталепрокатной промышленностях

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

• Двустадийный процесс, когда рулон производится на первой стадии, а затем поступает в обработку ещё раз на другой машине. Например, вся офисная бумага (например, формат A4 в Европе, Letter в США) производится в таком процессе. Трудности появляются ввиду того, что машины для второго процесса уже машин первого. Эффективное использование обеих стадий процесса важно (как с точки зрения экономии материала, так и экономии энергии) и то, что эффективно для первой стадии может оказаться неэфективным для второй, и приходится искать компромисс. Металлизированная плёнка (используемая для упаковки продуктов питания) и покрытая пластиком бумага (упаковочный картон для жидкостей, например, для упаковки соков) — другие примеры таких процессов.

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

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

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

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

• Имеются также задачи, когда результирующие рулоны не обязательно должны быть одного диаметра, а могут быть в пределах некоторого интервала. Иногда эту задачу называют задачей 1½ размерности. Этот вариант появляется, например, при производстве гофрокартона.

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

Программное обеспечение для решения задач раскроя для бумажной промышленности поставляют ABB Group, Greycon, Honeywell и Tieto.

Алгоритм раскроя для сталепрокатной промышленности сформулирован Робертом Гонгорра (Robert Gongorra) в 1998 году и S.O.N.S (Steel Optimization Nesting Software) разработал программное обеспечение для улучшения использования стального листа и уменьшения отходов.

Задача раскроя для стекольной промышленности

Задача гильотинного раскроя — это задача резки листов стекла на прямоугольники определённых размеров, используя только разрезы, проходящие по всей длине (или ширине) листа.

Задача ассортимента

Связанная задача определения (для одномерного случая) наилучшего размера исходного рулона, который удовлетворяет требованиям; известна как задача ассортимента.

История

Задача раскроя впервые сформулирована Канторовичем в 1939 году. В 1951 году, ещё до того, как компьютеры стали широко доступны, Л. В. Канторович и В. А. Залгаллер предложили способ решения задачи экономного использования материала при раскрое с помощью линейного программирования. Предложенная техника позднее получила название Метод генерации столбцов.

Программное обеспечение

Название	Лицензия	Короткое описание
VPSolver	GPL	Свободное программное обеспечение «Vector Packing Solver» (VPSolver), которое можно использовать для оптимизации одномерного раскроя. Метод решения основывается на формулировке потока в графе.

Литература

• Linear Programming. — W. H. Freeman, 1983. — ISBN 978-0-7167-1587-0.
• Hatem Ben Amor, J.M. Valério de Carvalho. Column Generation // Cutting Stock Problems in Column Generation / Guy Desaulniers, Jacques Desrosiers and Marius M. Solomon. — Springer, 2005. — Т. XVI. — ISBN 0-387-25485-4.

Ссылки

• European Special Interest Group on Cutting & Packing
• A rudimentary brute-force algorithm for cutting stock
• Bin Packing and Cutting Stock Solver Algorithm