Задача раскроя ({g;gcg jgvtjkx)
Задача раскроя — это NP-полная задача оптимизации, по существу, сводимая к задаче о ранце. Задача является задачей целочисленного линейного программирования. Задача возникает во многих областях промышленности. Представим себе, что вы работаете на целлюлозно-бумажном предприятии, и у вас имеется некоторое количество рулонов бумаги фиксированной ширины, но различным заказчикам нужны различные количества рулонов различной ширины. Как разрезать бумагу, чтобы минимизировать отходы?
Согласно данным Конфедерации европейских производителей бумаги[англ.][1], в 2012 году 1331 бумагоделательная машина в регионе производит в среднем отходов на 56 млн евро (примерно 73 млн долларов США) каждая. Экономии даже 1 % будет очень существенной.
Формулировка задачи и подходы к решению
[править | править код]Стандартная формулировка задачи раскроя (но не единственная) предполагает список m заказов, в каждом заказе требуется кусков. Образуем все возможные комбинации раскроя («карты раскроя») и связываем с каждой картой положительную целую переменную , показывающую, сколько раз карта использовалась. Выпишем задачу линейного программирования:
- , целое
где — сколько раз заказ появляется в карте и — цена (часто потери) карты . Точная природа ограничений может вести к слегка различным математическим характеристикам. Приведённые ограничения являются ограничениями на минимум (по меньшей мере заданное количество должно быть произведено, но не исключается, что будет произведено и больше). Если , требуется минимизировать число разрезаемых кусков исходного материала. Если ограничения с неравенств заменить на равенства, задача называется упаковкой в контейнеры. В более общей формулировке ограничения двухсторонние (и в этом случае решение минимизации потерь может отличаться от решения с минимальным числом кусков исходного материала):
Такая формулировка задачи применима не только к одномерному случаю. Возможно много вариаций, например, цель — не минимизация потерь, а максимизация общего числа произведённого товара.
В целом, число возможных карт растёт экспоненциально от m, числа заказов. При росте числа заказов может оказаться непрактичным перечислять возможные карты раскроя.
В качестве альтернативы можно использовать генерацию столбцов. Этот метод решает задачу раскроя, начиная с нескольких карт. Метод образует новые карты, если они потребуются, в процессе решения. В одномерном случае новые карты появляются при решении дополнительной оптимизационной задачи, задачи о ранце, в которой используется информации о двойственных переменных задачи линейного программирования. Задача о ранце имеет хорошо известные методы её решения, такие как метод ветвей и границ и динамическое программирование. Метод отложенной генерации столбцов может оказаться много эффективнее исходного подхода, особенно при росте размера задачи. Отложенная генерация столбцов в применении к задаче раскроя впервые использована Гилмором и Гомори в серии статей, опубликованных в 1960-х годах[2][3]. Они показали, что этот подход приводит гарантированно к (дробному) оптимальному решению без необходимости перечислять все возможные карты заранее.
Исходный метод Гилмора и Гомори не был целочисленным, так что решение могло содержать дробные составляющие, например, некоторая карта должна была использоваться 3,67 раз. Округление до ближайшего целого часто не работает, в том смысле, что это приводит к подоптимальному решению и недопроизводству или перепроизводству для некоторых заказов (и возможное нарушение ограничений, если они двусторонние). Этот недостаток преодолён в новых алгоритмах, которые позволяют находить оптимальные решения (в смысле нахождения решения с минимальными отходами) очень больших задач (в общем случае больших, чем нужно на практике[4][5]).
Задача раскроя часто является крайне вырожденной, поскольку возможно большое число решений с одним и тем же количеством потерь. Это вырождение возникает из-за возможности переставлять части, создавая новые карты раскроя, но не меняя результирующие потери. Это даёт целую коллекцию сопутствующих задач, удовлетворяющих тем же ограничениям, таких как:
- Задача нахождения минимального числа карт раскроя: найти решение с минимальным числом карт раскроя среди решений с минимальными потерями. Эта задача очень трудна, даже если потери известны[6][7]. Существует гипотеза, что любая ограниченная равенствами одномерная задача раскроя с n заказами, имеет по меньшей мере одно решение на минимум отходов с n + 1 картами раскроя. Верхние границы числа карт раскроя не известны, хотя примеры с n + 5 известны.
- Задача минимального склада: найти последовательность раскроя, чтобы не накапливалось большого числа частично выполненных заказов. Задача была открытой вплоть до 2007 года, когда опубликован эффективный алгоритм, основанный на динамическом программировании[8].
- Задача минимального числа смен ножей (для одномерной задачи раскроя): найти последовательность применения карт раскроя, чтобы минимизировать число перемещений режущих ножей. Данная задача является частным случаем обобщённой задачи коммивояжёра.
Иллюстрация одномерной задачи раскроя
[править | править код]Бумагоделательная машина может производить неограниченное число рулонов (заготовок), каждая 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
Решение
[править | править код]![](http://upload.wikimedia.org/wikipedia/ru/thumb/c/c4/%D0%9E%D0%B4%D0%BD%D0%BE%D0%BC%D0%B5%D1%80%D0%BD%D1%8B%D0%B9_%D1%80%D0%B0%D1%81%D0%BA%D1%80%D0%BE%D0%B9.svg/430px-%D0%9E%D0%B4%D0%BD%D0%BE%D0%BC%D0%B5%D1%80%D0%BD%D1%8B%D0%B9_%D1%80%D0%B0%D1%81%D0%BA%D1%80%D0%BE%D0%B9.svg.png)
Имеется 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 раскроя — резка труб, кабелей и стальных прутков. Двумерные задачи применяются при производстве мебели, одежды и стекла. Существует не так уж много трёхмерных применений раскроя, однако близкие трёхмерные задачи упаковки имеют много промышленных приложений, в частности, распределение объектов в контейнеры для водного транспорта (смотрите, например, Контейнерные перевозки, близкая к ней задача упаковки шаров изучалась с 17-го столетия (Гипотеза Кеплера)).
Задача раскроя в бумажной, плёночной и сталепрокатной промышленностях
[править | править код]Промышленное применение задачи раскроя для предприятий с массовым выпуском продукции возникает, когда основной материал производится в больших рулонах, а затем режется на более мелкие части (см. слиттинг). Это происходит, например, в бумажном производстве и при получении полимерных плёнок, а также при изготовлении плоских металлических (железных или бронзовых) листов. Существует много вариантов и дополнительных ограничений, вызванных особенностями производства или ограничениями процесса, требованиями заказчиков и вопросами качества. Некоторые примеры:
- Двустадийный процесс, когда рулон производится на первой стадии, а затем поступает в обработку ещё раз на другой машине. Например, вся офисная бумага (например, формат A4 в Европе, Letter в США) производится в таком процессе. Трудности появляются ввиду того, что машины для второго процесса уже машин первого. Эффективное использование обеих стадий процесса важно (как с точки зрения экономии материала, так и экономии энергии) и то, что эффективно для первой стадии может оказаться неэфективным для второй, и приходится искать компромисс. Металлизированная плёнка[англ.] (используемая для упаковки продуктов питания) и покрытая пластиком бумага (упаковочный картон для жидкостей[англ.], например, для упаковки соков) — другие примеры таких процессов.
- Мотальные машины ограничивают разрезание физически или логически: общие ограничения возникают из того, что только определённое число ножей допустимо, так что карта раскроя не должна содержать ножей больше некоторой величины. Поскольку мотальные машины не стандартизованы, возникает много дополнительных ограничений.
- В качестве дополнительного ограничения можно привести, например, ограничение на направление разрезания — различные края листа могут иметь большое различие в толщине и некоторые приложения очень чувствительны к этому.
- В качестве примера влияния требований качества можно привести случай, когда основной рулон содержит дефекты, которые следует вырезать. Дорогие материалы с высокими требованиями к качеству материала, такие как фотобумага или тайвек, следует тщательно оптимизировать, чтобы минимизировать отходы.
- Многомашинные задачи возникают, когда заказ можно произвести на более чем одной машине и эти машины имеют различную ширину. В основном, доступность нескольких исходных рулонов с различной шириной уменьшает количество отходов. На практике, однако, приходится учитывать дополнительный порядок разрезания.
- Имеются также задачи, когда результирующие рулоны не обязательно должны быть одного диаметра, а могут быть в пределах некоторого интервала. Иногда эту задачу называют задачей 1½ размерности. Этот вариант появляется, например, при производстве гофрокартона.
- В сталепрокатной промышленности отличительной особенностью является то, что исходные рулоны, в основном, различаются как по ширине, так и по длине. Таким образом, возникает схожесть с многомашинным вариантом, описанным выше. В этом случае отходы могут возникать как по ширине, так и по длине.
Программное обеспечение для решения задач раскроя для бумажной промышленности поставляют 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), которое можно использовать для оптимизации одномерного раскроя. Метод решения основывается на формулировке потока в графе. |
Примечания
[править | править код]- ↑ Key Statistics 2012 . Confederation of Europear Paper Industries. Дата обращения: 3 июля 2013. Архивировано из оригинала 6 октября 2014 года.
- ↑ P. C. Gilmore, R. E. Gomory. A linear programming approach to the cutting-stock problem // Operations Research. — 1961. — № 9. — С. 849—859.
- ↑ P. C. Gilmore, R. E. Gomory. A linear programming approach to the cutting-stock problem - Part II // Operations Research. — 1963. — № 11. — С. 863—888.
- ↑ C. Goulimis. Optimal solutions for the cutting stock problem // European Journal of Operational Research. — 1990. — № 44. — С. 197—208.
- ↑ V. de Carvalho. Exact solution of cutting stock problems using column generation and branch-and-bound // International Transactions in Operational Research. — 1998. — № 5. — С. 35—44.
- ↑ S. Umetani, M. Yagiura, and T. Ibaraki. One dimensional cutting stock problem to minimize the number of different patterns // European Journal of Operational Research. — 2003. — № 146. — С. 388—402.
- ↑ A. Diegel, E. Montocchio, E. Walters, S. van Schalkwyk and S. Naidoo. Setup minimizing conditions in the trim loss problem // European Journal of Operational Research. — 1996. — № 95. — С. 631—640.
- ↑ Maria Garcia de la Banda, P. J. Stuckey. ynamic Programming to Minimize the Maximum Number of Open Stacks // INFORMS Journal on Computing. — 3007. — Т. 19, № 4. — С. 607—617.
- ↑ G. Wäscher, H. Haußner, H. Schumann. An Improved Typology of Cutting and Packing Problems // European Journal of Operational Research. — Т. 183, № 3. — С. 1109—1130.
- ↑ Raffensperger John F. The generalized assortment and best cutting stock length problems // International Transactions in Operational Research. — 2010. — Январь (т. 17, № 1). — С. 35—49. — ISSN 0969-6016. — doi:10.1111/j.1475-3995.2009.00724.x.
- ↑ Л. В. Канторович. Mathematical methods of organizing and planning production. — Leningrad State University.
- ↑ Канторович Л. В., Залгаллер В. А. Рациональный раскрой промышленных материалов. — Новосибирск: Наука, 1971.
Литература
[править | править код]- 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.