Введение
Процесс изготовления небольших прямоугольных изделий фиксированных размеров
Гильотинорезка — это процесс изготовления небольших прямоугольных изделий фиксированных размеров из заданного большого прямоугольного листа с использованием только гильотинных разрезов. Гильотинный разрез (также называемый резкой от края до края) — это прямая линия, делящая существующий прямоугольник от одного края до противоположного, аналогично работе бумажного гильотина. Гильотинорезка особенно распространена в стекольной промышленности. Стеклянные листы надрезают по горизонтальным и вертикальным линиям, а затем разбивают по этим линиям для получения более мелких панелей. Она также полезна для резки стальных листов, распила деревянных листов для изготовления мебели и резки картона для изготовления коробок. Существует множество задач оптимизации, связанных с гильотинорезкой, таких как: максимизация общей площади или общей стоимости полученных деталей; минимизация количества отходов (неиспользованных частей) большого листа или общего количества листов. Эти задачи изучаются в комбинаторной геометрии, исследовании операций и промышленной инженерии. Связанной, но отличной задачей является гильотинное разбиение. В этой задаче размеры маленьких прямоугольников не заданы заранее. Сложность заключается в том, что исходный лист может быть не прямоугольным, а любым прямоугольным многоугольником. В частности, он может содержать отверстия (представляющие дефекты в исходном материале). Цель оптимизации обычно состоит в минимизации количества небольших прямоугольников или минимизации общей длины разрезов.
Алгоритмы оптимизации
Особый случай, когда существует только один тип (т.е. все целевые прямоугольники идентичны и имеют одинаковую ориентацию), называется задачей гильотинного раскроя на паллетах. Тарновский, Терно и Шейтауэр представили алгоритм полиномиального времени для её решения. Однако, когда имеется два или более типов, все задачи оптимизации, связанные с гильотинным раскроем, являются NP-трудными. Ввиду практической значимости, были разработаны различные точные и приближенные алгоритмы. Гилмор и Гомори представили рекурсию динамического программирования как для ступенчатого, так и для неступенчатого гильотинного раскроя. Однако позже были представлены процедуры поиска с возвратом для неступенчатого гильотинного раскроя. Масден и Ван предложили эвристические алгоритмы. Хиффи, М’Халлах и Саади предлагают алгоритм для двумерно ограниченной задачи гильотинного раскроя. Это алгоритм ветвей и границ, использующий поиск в ширину. Клаутио, Жугле и Мокрим предлагают точный алгоритм для задачи принятия решений. Их алгоритм использует компактное представление классов шаблонов гильотинного раскроя, используя ориентированный граф, который они называют гильотинным графом. Каждая дуга в этом графе окрашена одним из двух цветов: «горизонтальный» или «вертикальный». Каждый монохромный ориентированный цикл в этом графе соответствует сборке. Повторное сжатие монохромных циклов позволяет восстановить рекурсивную последовательность сборок, представляющую класс шаблонов раскроя. Каждый гильотинный граф содержит от m до 2m² дуг. Особый вид гильотинных графов, называемый нормальными гильотинными графами, обладает интересным свойством – содержать единственную гамильтонову цепь. Сортировка вершин в соответствии с этой цепью делает граф хорошо упорядоченным нормальным гильотинным графом; существует взаимно однозначное соответствие между такими графами и классами шаблонов раскроя. Затем они решают задачу оптимизации, используя программирование с ограничениями в пространстве хорошо упорядоченных нормальных гильотинных графов. Руссо, Бочча, Сфорца и Стерле проанализировали более 90 работ, посвященных неступенчатому ограниченному гильотинному раскрою (с верхними ограничениями на количество), как взвешенному, так и невзвешенному. Существует два основных подхода к точным решениям: динамическое программирование и поиск с возвратом (ветви и границы). Подходы поиска с возвратом далее классифицируются как восходящие (начиная с отдельных прямоугольников и используя сборки для построения всего листа) или нисходящие. Во всех подходах важно находить хорошие нижние и верхние оценки, чтобы эффективно сокращать пространство поиска. Эти оценки часто получаются из решений связанных вариантов, например, неограниченных, ступенчатых и негильотинных вариантов. Абу Мсаба, Слиман и Ахмед Риад Баба Али. «Новая эвристика размещения гильотины в сочетании с улучшенным генетическим алгоритмом для задачи ортогонального раскроя». 2011 IEEE International Conference on Industrial Engineering and Engineering Management. IEEE, 2011. Абу Мсаба, Слиман, Ахмед Риад Баба Али и Басма Сагер. «Генетический алгоритм контролируемой стабильности с новой эвристикой BLF2G для размещения гильотины в задаче ортогонального раскроя». International Journal of Cognitive Informatics and Natural Intelligence (IJCINI) 13, No. 4 (2019): 91–111.
Реализация
МакХейл и Шах написали программу на Prolog, реализующую алгоритм с возможностью прерывания: она генерирует приблизительно оптимальные решения за заданное время и затем улучшает их, если пользователю выделено больше времени. Программа была использована специализированным производителем бумаги и позволила сократить время, необходимое для раскроя листов, а также уменьшить количество отходов.