Проблема сокращения запасов

Для проверки этой статьи нужны дополнительные цитаты . Помогите улучшить эту статью , добавив ссылки на надежные источники . Не имеющие источников материалы могут быть оспорены и удалены. Найти источники:  «Проблема сокращения запасов» – новости  · газеты  · книги  · ученый  · JSTOR ( апрель 2015 г. ) ( Узнайте, как и когда удалять это сообщение )

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

Бумагоделательная машина может производить неограниченное количество рулонов мастер-бумаги (jumbo), каждый шириной 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 x 22 + 1520 x 25 + ... + 2200 x 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

Задачи раскроя можно классифицировать несколькими способами. ^[1] Один из способов — это размерность резки: приведенный выше пример иллюстрирует одномерную (1D) задачу; другие промышленные применения 1D возникают при резке труб, кабелей и стальных стержней. Двумерные (2D) задачи встречаются в производстве мебели, одежды и стекла. Когда либо основной элемент, либо требуемые детали имеют неправильную форму (ситуация, часто встречающаяся в кожевенной, текстильной, металлургической промышленности), это называется проблемой вложенности .

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

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

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

• Задача раскроя заготовки, заключающаяся в определении (в одномерном случае) наилучшего размера заготовки, который будет соответствовать заданному спросу, известна как задача ассортимента . ^[3]

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

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

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

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

${\displaystyle x_{i}\geq 0}$, целое число

где — количество раз, когда заказ появляется в шаблоне , а — стоимость (часто отходы) шаблона . Точная природа количественных ограничений может привести к слегка отличающимся математическим характеристикам. Количественные ограничения приведенной выше формулировки являются минимальными ограничениями (по крайней мере, должно быть произведено заданное количество каждого заказа, но возможно и больше). ${\displaystyle a_{ij}}$${\displaystyle j}$${\displaystyle я}$${\displaystyle c_{i}}$${\displaystyle я}$

Когда цель минимизирует количество используемых основных элементов, и если ограничение на количество производимых изделий заменяется равенством, это называется задачей упаковки в контейнеры . ${\displaystyle c_{i}=1}$

Наиболее общая формулировка имеет двусторонние ограничения (и в этом случае решение с минимальными отходами может потреблять больше, чем минимальное количество основных элементов):

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

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

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

Альтернативный подход использует отложенную генерацию столбцов . Этот метод решает задачу раскроя, начиная всего с нескольких шаблонов. Он генерирует дополнительные шаблоны, когда они необходимы. Для одномерного случая новые шаблоны вводятся путем решения вспомогательной задачи оптимизации, называемой задачей о рюкзаке , с использованием информации о двойной переменной из линейной программы . Задача о рюкзаке имеет хорошо известные методы ее решения, такие как ветвь и граница и динамическое программирование . Метод отложенной генерации столбцов может быть намного эффективнее исходного подхода, особенно по мере роста размера задачи. Подход генерации столбцов , применяемый к задаче раскроя, был впервые предложен Гилмором и Гомори в серии статей, опубликованных в 1960-х годах. ^{[6] [7]} Гилмор и Гомори показали, что этот подход гарантированно сходится к (дробному) оптимальному решению без необходимости предварительного перечисления всех возможных шаблонов.

Ограничением оригинального метода Гилмора и Гомори является то, что он не обрабатывает целочисленность, поэтому решение может содержать дроби, например, определенный шаблон должен быть произведен 3,67 раза. Округление до ближайшего целого часто не работает, в том смысле, что это может привести к неоптимальному решению и/или недо- или перепроизводству некоторых заказов (и возможной неосуществимости при наличии двусторонних ограничений спроса). Это ограничение преодолевается в современных алгоритмах, которые могут решать с оптимальностью (в смысле нахождения решений с минимальными отходами) очень большие экземпляры задачи (обычно большие, чем встречаются на практике ^{[8] [9]} ).

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

• Проблема минимального количества шаблонов: найти решение с минимальным количеством шаблонов среди решений с минимальными отходами. Это очень сложная задача, даже если известны отходы. ^{[10] [11] [12]} Существует гипотеза , что любой одномерный экземпляр с ограничением равенства и размерами n имеет по крайней мере одно решение с минимальными отходами с не более чем n + 1 шаблоном. Эта гипотеза была впервые опровергнута в апреле 2020 года на примере с 9 размерами, для которого требуется 11 шаблонов. ^[13]
• Проблема минимального стека: она касается последовательности шаблонов, чтобы не иметь слишком много частично выполненных заказов в любой момент времени. Это была открытая проблема до 2007 года, когда был опубликован эффективный алгоритм, основанный на динамическом программировании. ^[14]
• Задача о минимальном количестве смен ножей (для одномерной задачи): она связана с упорядочиванием и перестановкой шаблонов, чтобы минимизировать количество перемещений режущих ножей. Это частный случай обобщенной задачи коммивояжера .

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

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