Задачи о раскрое материалов

Некоторые задачи линейного программирования, возникающие из-за комбинаторных задач, становятся неразрешимыми из-за большого количества задействованных переменных. Обычно каждая переменная представляет некоторую активность, и сложность заключается в том, что существует слишком много возможных конкурирующих действий, удовлетворяющих комбинаторным ограничениям задачи. Примером этого является задача о разделке запасов, описанная ниже в форме, аналогичной той, которую использовал автор [1].
В исследованиях операций задача раскроя заготовок - это задача разрезания заготовок стандартного размера, таких как рулоны бумаги или листовой металл, на заготовки заданных размеров с минимальными потерями материала. Это математическая задача оптимизации, которая возникает в результате применения в промышленности. С точки зрения вычислительной сложности, эта задача является NP-сложной задачей, которую можно свести к задаче о рюкзаке. Задача может быть сформулирована как задача целочисленного линейного программирования.
Иллюстрация одномерной задачи о заготовке может быть следующее: бумагоделательная машина может выпускать неограниченное количество рулонов бумаги шириной 5600 мм каждый. Необходимо разрезать 13 изделий.
Важной особенностью такого рода задач является то, что из одного и того же рулона может быть изготовлено множество различных единиц продукции, а количество возможных комбинаций само по себе, как правило, очень велико, и перечислить их непросто.
Таким образом, проблема заключается в поиске оптимального набора схем изготовления рулонов продукции из основного рулона, чтобы удовлетворить спрос и свести к минимуму отходы.
Простая нижняя граница получается путем деления общего количества продукта на размер каждого основного рулона. Общий размер требуемого изделия составляет 1380 x 22 + 1520 x 25 + ... + 2200 x 20 = 407160 мм. Длина каждого основного рулона составляет 5600 мм, что требует минимум 72,7 рулона, что означает, что требуется 73 рулона или более.
Решение с минимальными затратами, разработанное таким образом, чтобы свести к минимуму замену ножей, показано маленькими белыми кружочками.
Для этого небольшого примера существует 308 возможных шаблонов. Оптимальный вариант ответа требует 73 основных рулона и содержит 0,401% отходов; с помощью вычислений можно показать, что в этом случае минимальное количество шаблонов с таким уровнем отходов равно 10. Также можно подсчитать, что существует 19 различных таких решений, каждое из которых содержит 10 шаблонов и расходует 0,401% отходов.
Проблемы, связанные с разделкой заготовок, могут быть классифицированы несколькими способами.[1] Одним из них является размерность резки: приведенный выше пример иллюстрирует одномерную (1D) проблему; другие промышленные применения 1D встречаются при резке труб, кабелей и стальных прутков. Двумерные (2D) проблемы возникают при производстве мебели, одежды и стекла. Когда исходное изделие или необходимые детали имеют неправильную форму (ситуация, часто встречающаяся в кожевенной, текстильной и металлургической промышленности), это называется проблемой вложенности.
Известно не так много трехмерных (3D) приложений, связанных с резкой; однако тесно связанная с этим проблема трехмерной упаковки имеет множество промышленных применений, таких как упаковка предметов в транспортные контейнеры (см., например, контейнеризация: связанная с ней проблема упаковки в сферу изучалась с 17 века (гипотеза Кеплера)).
Проблемы с заготовками в промышленности при больших объемах производства возникают, в частности, при производстве основного материала в больших рулонах, которые затем разрезаются на более мелкие. Это применяется, например, в бумажной промышленности и производстве пластиковых пленок, а также при производстве листового металла, такого как сталь или латунь. Существует множество вариантов и дополнительных ограничений, возникающих из-за особых производственных ограничений, связанных с оборудованием и технологическими процессами, требованиями заказчика и проблемами качества; вот некоторые примеры:
Цель данной работы – провести литературный анализ, а также показать на реальных примерах, что эта трудность может быть преодолена с помощью метода, в основном идентичного идее, которая может быть реализована симплекс-методом.
Задача о заготовке для резки была впервые сформулирована Канторовичем в 1939 году.[4] В 1951 году, еще до того, как компьютеры стали широко доступны, Л. В. Канторович и В. А. Залгаллер предложили [5] решить проблему экономичного использования материала на этапе резки с помощью линейного программирования. Предложенный метод позже был назван методом генерации столбцов.
Задача определения заготовок для одномерного случая наилучшего размера заготовки, который будет соответствовать заданному спросу, известна как задача сортимента.[3] Двухэтапный случай, при котором рулоны, изготовленные на первом этапе, затем обрабатываются во второй раз. Например, таким способом изготавливаются все канцелярские товары для офиса (например, формат A4 в Европе, формат Letter в США). Сложность возникает из-за того, что оборудование на втором этапе уже, чем на основном. Важно эффективное использование обоих этапов производства (с точки зрения использования энергии или материалов), и то, что эффективно на первом этапе, может оказаться неэффективным на втором, что приводит к компромиссам. Металлизированная пленка (используется для упаковки закусок) и экструзия пластика на бумагу (используется для упаковки жидкостей, например, картонных коробок из-под сока) являются еще одними примерами такого процесса.
Ограничения на моталку, когда процесс продольной резки имеет физические или логические ограничения: очень распространенным ограничением является то, что доступно только определенное количество ножей для продольной резки, поэтому допустимые модели не должны содержать более максимального количества рулонов. Поскольку оборудование для намотки не стандартизировано, возникает очень много других ограничений.
Примером требования заказчика может служить ситуация, когда конкретный заказ не может быть выполнен ни в одном из двух положений кромок: это происходит из-за того, что кромки листа имеют тенденцию к большим различиям в толщине, и некоторые области применения могут быть очень чувствительны к этому.
Примером проблемы с качеством может служить наличие дефектов на рулоне, которые необходимо устранить. Дорогостоящие материалы с высокими характеристиками качества, такие как фотобумага, требуют тщательной оптимизации, чтобы свести к минимуму потери площади.
Проблемы с использованием нескольких станков возникают, когда заказы могут быть изготовлены на нескольких станках, и эти станки имеют разную ширину. Как правило, наличие нескольких основных валков значительно сокращает количество отходов; однако на практике, возможно, придется учитывать дополнительные ограничения при разделении заказов.
Существует также проблема полунепрерывного производства, когда производимые рулоны не обязательно должны быть одинакового диаметра, но могут варьироваться в пределах диапазона. Обычно это происходит при заказе листов. Иногда это называют проблемой размеров 1½. Этот вариант также встречается при производстве гофрированных древесноволокнистых плит, где его несколько путано называют проблемой планирования работы гофрокартона.
Поскольку некоторые бумагоделательные машины относительно компактны по сравнению с требуемыми моделями, некоторые компании инвестировали во вторичный процесс скручивания (также известный как сварка полотна), при котором две катушки (изготовленные путем разрезания исходных больших катушек) соединяются бок о бок (с небольшим нахлестом) для получения более широкий рулон. Изготовление более узких рулонов в первичном процессе приводит к снижению общего количества отходов.[2]
В металлургической промышленности одно из ключевых отличий заключается в том, что, как правило, заготовительные валки изготавливаются раньше и, как правило, отличаются друг от друга (как по ширине, так и по длине). Таким образом, существует сходство с проблемой использования нескольких станков, упомянутой выше. Наличие различий в длине создает двумерную проблему, поскольку отходы могут образовываться как по ширине, так и по длине.[требуется цитирование]
Задача о гильотине - это еще одна двумерная задача о разрезании листов на прямоугольники заданных размеров, однако разрешены только те разрезы, которые продолжаются по всей длине каждого листа. Промышленное применение этой задачи можно найти в стекольной промышленности.