Проблема с обрезкой материала

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

одномерной задачи о

Бумагоделательная машина может производить неограниченное количество мастер-рулонов шириной 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

Границы и проверки

Простую нижнюю границу получают путем деления общего количества продукта на размер каждого рулона мастера. Суммарно необходимое изделие составляет 1380 х 22 + 1520 х 25 +… + 2200 х 20 = 407160 мм. Длина каждого мастер-рулона составляет 5600 мм, поэтому требуется минимум 72,7 рулона, что означает, что потребуется 73 рулона или более.

Решение

Решение с минимальными отходами, разработанное для минимизации замены ножей, показано маленькими белыми кружками.

Для этого небольшого экземпляра существует 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 встречаются при резке труб, кабелей и стальных стержней. Двумерные (2D) задачи встречаются при производстве мебели, одежды и стекла. Когда либо мастер-изделие, либо требуемые детали имеют неправильную форму (ситуация, часто встречающаяся в кожевенной, текстильной и металлургической промышленности), это называется проблемой раскроя .

Известно не так много трехмерных (3D) приложений, включающих резку; однако тесно связанная проблема трехмерной упаковки имеет множество промышленных применений, таких как упаковка объектов в транспортные контейнеры (см., например, контейнеризация : соответствующая проблема упаковки сфер изучается с 17 века ( гипотеза Кеплера )).

Приложения

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

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

Пример разреза гильотиной.

Пример безгильотинного разреза.

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

История

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

и подходы к

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

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

${\text{s.t.}}\sum _{i=1}^{C}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 шаблонами. Впервые эта гипотеза была опровергнута в апреле 2020 года на примере с 9 размерами, для которого требуется 11 шаблонов.
• Проблема минимального стека: она связана с последовательностью паттернов, чтобы в любой момент времени не было слишком много частично выполненных заказов. Это была открытая проблема до 2007 года, когда был опубликован эффективный алгоритм, основанный на динамическом программировании.
• Задача о минимальном количестве смен ножей (для одномерной задачи): она связана с упорядочиванием и перестановкой шаблонов, чтобы свести к минимуму количество перемещений разрезающих ножей. Это частный случай обобщенной задачи коммивояжера .

См. также

• Упаковка в контейнеры с высокой кратностью
• Конфигурация линейной программы

Дальнейшее чтение

• Хватал, В. (1983). Линейное программирование . У. Х. Фриман. ISBN  978-0-7167-1587-0 .
• Хатем Бен Амор, Ж. М. Валерио де Карвальо, «Решение проблем с запасами при создании столбцов», под редакцией Гая Десольнье, Жака Дерозье и Мариуса М. Соломона, Springer, 2005, XVI, ISBN   0-387-25485-4
• М. Делорм, М. Иори, С. Мартелло, Проблемы упаковки контейнеров и резки запасов: математические модели и точные алгоритмы , Европейский журнал операционных исследований, 2016, 255, 1–20, два : 10.1016/j.ejor.2016.04.030