07-07-2023
Задача раскроя — это NP-полная задача задача оптимизации, по существу, сводимая к задаче о ранце. Задача является задачей целочисленного линейного программирования. Задача возникает во многих областях промышленности. Представим себе, что вы работаете на целлюлозно-бумажном предприятии и у вас имеется некоторое количество рулонов бумаги фиксированной ширины, но различным заказчикам нужны различные количества рулонов различной ширины. Как разрезать бумагу, чтобы минимизировать отходы?
Согласно данным конфедерации европейских производителей бумаги[en],[1] в 2012 году 1.331 бумагоделательных машин в регионе производят в среднем отходов на €56 миллиона (примерно US$73 миллиона) каждая. Экономии даже 1% будет очень существенной.
Стандартная формулировка задачи раскроя (но не единственная) предполагает список m заказов, в каждом заказе требуется кусков. Образуем все возможные комбинации раскроя ("карты раскроя") и связываем с каждой картой положительную целую переменную , показывающую, сколько раз карта использовалась. Выпишем задачу линейного программирования:
где — сколько раз заказ появляется в карте и — цена (часто потери) карты . Точная природа ограничений может вести к слегка различным математическим характеристикам. Приведённые ограничения являются ограничениями на минимум (по меньшей мере заданное количество должно быть произведено, но не исключается, что будет произведено и больше). Если , требуется минимизировать число разрезаемых кусков исходного материала. Если ограничения с неравенств заменить на равенства, задача называется упаковкой в контейнеры. В более общей формулировке ограничения двухсторонние (и в этом случае решение минимизации потерь может отличаться от решения с минимальным числом кусков исходного материала):
Такая формулировка задачи применима не только к одномерному случаю. Возможно много вариаций, например, цель — не минимизация потерь, а максимизация общего числа произведённого товара.
В целом, число возможных карт растёт экспоненциально от m, числа заказов. При росте числа заказов может оказаться непрактичным перечислять возможные карты раскроя.
В качестве альтернативы можно использовать генерация столбцов. Этот метод решает задачу раскроя, начиная с нескольких карт. Метод образует новые карты, если они потребуются, в процессе решения. В одномерном случае новые карты появляются при решении дополнительной оптимизационной задачи, задачи о ранце, в которой используется информации о двойственных переменных задачи линейного программирования. Задача о ранце имеет хорошо известные методы её решения, такие как метод ветвей и границ и динамическое программирование. Метод отложенной генерации столбцов может оказаться много эффективнее исходного подхода, особенно при росте размера задачи. Отложенная генерация столбцов в применении к задаче раскроя впервые была использована Гилмором и Гомори (Gilmore, Gomory) в серии статей, опубликованных в 1960-х годах.[2][3] Гилмор и Гомори показали, что этот подход приводит гарантированно к (дробному) оптимальному решению без необходимости перечислять все возможные карты заранее.
Исходный метод Гилмора и Гомори не был целочисленным, так что решение могло содержать дробные составляющие, например, некоторая карта должна была использоваться 3,67 раз. Округление до ближайшего целого часто не работает, в том смысле, что это приводит к подоптимальному решению и недопроизводству или перепроизводству для некоторых заказов (и возможное нарушение ограничений, если они двусторонние). Этот недостаток преодолён в новых алгоритмах, которые позволяют находить оптимальные решения (в смысле нахождения решения с минимальными отходами) очень больших задач (в общем случае больших, чем нужно на практике [4][5]).
Задача раскроя часто является крайне вырожденной, поскольку возможно большое число решений с одним и тем же количеством потерь. Это вырождение возникает из-за возможности переставлять части, создавая новые карты раскроя, но не меняя результирующие потери. Это даёт целую коллекцию сопутствующих задач, удовлетворяющих тем же ограничениям, таких как:
Бумагоделательная машина может производить неограниченное число рулонов (заготовок) , каждая 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 |
Задачи раскроя можно классифицировать различными способами.[9] Один путь — размерность раскроя: выше приведённый пример иллюстрирует одномерный раскрой (1D). Другие промышленные применения 1D раскроя — резка труб, кабелей и стальных прутков. Двумерные (2D) задачи применяются при производстве мебели, одежды и стекла. Существует не так уж много трёхмерных (3D) применений раскроя, однако близкие 3D задачи упаковки[en] имеют много промышленных приложений, в частности, распределение объектов в контейнеры для водного транспорта (смотрите, например, Контейнерные перевозки, близкая к ней задача упаковки шаров изучалась с 17-го столетия (Гипотеза Кеплера)).
Промышленное применение задачи раскроя для предприятий с массовым выпуском продукции возникает, когда основной материал производится в больших рулонах, а затем режется на более мелкие части (смотрите слиттинг). Это происходит, например в бумажном производстве и при получении полимерных плёнок, а также при изготовлении плоских металлических (железных или бронзовых) листов. Существует много вариантов и дополнительных ограничений, вызванных особенностями производства или ограничениями процесса, требованиями заказчиков и вопросами качества. Некоторые примеры:
Программное обеспечение для решения задач раскроя для бумажной промышленности поставляют ABB Group, Greycon, Honeywell и Tieto.
Алгоритм раскроя для сталепрокатной промышленности было сформулирован Робертом Гонгорра (Robert Gongorra) в 1998 и S.O.N.S (Steel Optimization Nesting Software) разработал программное обеспечение для улучшения использования стального листа и уменьшения отходов.
Задача гильотинного раскроя — это задача резки листов стекла на прямоугольники определённых размеров, используя только разрезы, проходящие по всей длине (или ширине) листа.
Связанная задача определения (для одномерного случая) наилучшего размера исходного рулона, который удовлетворяет требованиям, известна как задача ассортимента.[10]
Задача раскроя впервые была сформулирована Канторовичем в 1939.[11] В 1951, ещё до того, как компьютеры стали широко дотупны, Л.В. Канторович и В.А. Залгаллер предложили[12] способ решения задачи экономного использования материала при раскрое с помощью линейного программирования. Предложенная техника позднее получила название Метод генерации столбцов.
Название | Лицензия | Короткое описание |
---|---|---|
VPSolver | GPL | Свободное программное обеспечение «Vector Packing Solver» (VPSolver), которое можно использовать для оптимизации одномерного раскроя. Метод решения основывается на формулировке потока в графе. |
Задача раскроя.