Введение
Математическая задача в исследовании операций
В исследовании операций задача раскроя – это задача раскроя стандартных размеров исходного материала, такого как бумажные рулоны или листовой металл, на детали заданных размеров с целью минимизации отходов материала. Это задача оптимизации в математике, возникающая в различных промышленных приложениях. С точки зрения вычислительной сложности, эта задача является NP-трудной и может быть сведена к задаче о рюкзаке. Задача может быть сформулирована как задача целочисленного линейного программирования.
Границы и проверки
Простая нижняя граница получается путем деления общего количества материала на размер каждого основного рулона. Общее необходимое количество материала составляет 1380 x 22 + 1520 x 25 + 2200 x 20 = 407160 мм. Каждый основной рулон имеет длину 5600 мм, что требует минимум 72,7 рулона, а значит, необходимо 73 рулона или больше.
Классификация
Проблемы раскроя могут быть классифицированы несколькими способами. Один из способов – это размерность раскроя: приведенный выше пример иллюстрирует одномерную (1D) задачу; другие промышленные применения 1D возникают при раскрое труб, кабелей и стальных прутков. Двумерные (2D) задачи встречаются в производстве мебели, одежды и стекла. Если либо исходный материал, либо требуемые детали имеют неправильную форму (ситуация, часто встречающаяся в кожевенной, текстильной и металлургической промышленности), это называется задачей раскладки (или задачей вложения). Известно немного трехмерных (3D) применений, связанных с раскроем; однако тесно связанная с ней задача 3D упаковки имеет множество промышленных применений, например, упаковка грузов в транспортные контейнеры (см., например, контейнеризация: связанная с ней задача упаковки сфер изучается с XVII века (гипотеза Кеплера)).
Приложения
Промышленные применения задач раскроя для больших объемов производства возникают особенно часто, когда исходный материал производится в больших рулонах, которые затем разрезаются на более мелкие единицы (см. продольная резка рулонов). Это применяется, например, в производстве бумаги и пластиковых пленок, а также плоских металлов, таких как сталь или латунь. Существует множество вариантов и дополнительных ограничений, обусловленных специфическими производственными требованиями, ограничениями оборудования и технологических процессов, запросами клиентов и вопросами качества; некоторые примеры: двухступенчатое производство, когда рулоны, полученные на первом этапе, подвергаются дальнейшей обработке на втором. Например, вся офисная канцелярия (например, формат A4 в Европе, Letter в США) производится по такой схеме. Сложность заключается в том, что оборудование на втором этапе обычно уже, чем на первом. Эффективное использование обоих этапов производства важно (с точки зрения энерго- и материалоемкости), и то, что эффективно на первом этапе, может быть неэффективно на втором, что приводит к компромиссам. Металлизированная пленка (используемая в упаковке снеков) и экструзия пластика на бумагу (используемая в упаковке жидкостей, например, соковых пакетов) – дополнительные примеры подобных процессов. Ограничения на намотку, когда процесс резки имеет физические или логические ограничения: распространенным ограничением является ограниченное количество режущих ножей, поэтому допустимые схемы раскроя не должны содержать больше определенного количества рулонов. Поскольку оборудование для намотки не стандартизировано, возникает множество других ограничений. Примером запроса клиента может служить невозможность выполнения конкретного заказа из-за краев листа, которые имеют тенденцию к большим колебаниям толщины, что критично для некоторых применений. Примером проблемы качества является наличие дефектов в исходном рулоне, которые необходимо обрезать. Дорогостоящие материалы с высокими требованиями к качеству, такие как фотобумага или Tyvek, требуют тщательной оптимизации для минимизации отходов. Задачи с использованием нескольких машин возникают, когда заказы могут быть выполнены на нескольких машинах, имеющих разную ширину. Как правило, наличие нескольких вариантов ширины исходного рулона значительно снижает количество отходов; однако на практике необходимо учитывать дополнительные ограничения, связанные с разделением заказов. Существует также полунепрерывная задача, в которой производимые рулоны не обязательно должны иметь одинаковый диаметр, но могут варьироваться в пределах определенного диапазона. Это обычно встречается при выполнении заказов на листы. Этот вариант иногда называют задачей 1½ измерений. Он также встречается в производстве гофрированного картона, где, несколько запутанно, называется задачей планирования производства гофрокартона. Поскольку некоторые бумагоделательные машины относительно узкие по сравнению с требуемыми размерами продукции, некоторые компании инвестировали во вторичный процесс скашивания (также известный как сварка полотна), при котором два рулона (полученные путем продольной резки исходных джамбо-рулонов) соединяются бок о бок (с небольшим перекрытием) для получения более широкого рулона. Производство более узких рулонов на первом этапе приводит к снижению общих отходов. В металлургической промышленности ключевое отличие заключается в том, что исходные рулоны обычно производятся раньше и, как правило, отличаются друг от друга (как по ширине, так и по длине). Поэтому существуют сходства с вышеупомянутой задачей с использованием нескольких машин. Наличие вариаций длины создает задачу в двух измерениях, поскольку отходы могут возникать как по ширине, так и по длине. Задача гильотины – еще одна задача в двух измерениях, заключающаяся в раскрое листов на прямоугольники заданного размера, при этом разрешены только разрезы, проходящие через весь лист. Промышленные применения этой задачи можно найти в стекольной промышленности. Задача раскроя, заключающаяся в определении оптимального размера исходного рулона для удовлетворения заданного спроса (в одномерном случае), известна как задача ассортимента.
Two stage, where the rolls produced in the first stage are then processed a second time. For instance, all office stationery (e. g. A4 size in Europe, Letter size in US) is produced in such a process. The complication arises because the machinery in the second stage is narrower than the primary. Efficient utilisation of both stages of production is important (from an energy or material use perspective) and what is efficient for the primary stage may be inefficient for the secondary, leading to trade offs. Metallised film (used in packaging of snacks), and plastic extrusion on paper (used in liquid packaging, e. g. juice cartons) are further examples of such a process. Winder constraints where the slitting process has physical or logical constraints: a very common constraint is that only a certain number of slitting knives are available, so that feasible patterns should not contain more than a maximum number of rolls. Because winder machinery is not standardised, very many other constraints are encountered. An example of a customer requirement is when a particular order cannot be satisfied from either of the two edge positions: this is because the edges of the sheet tend to have greater variations in thickness and some applications can be very sensitive to these. An example of a quality issue is when the master roll contains defects that have to be cut around. Expensive materials with demanding quality characteristics such as photographic paper or Tyvek have to be carefully optimised so that the wasted area is minimised. Multi machine problems arise when orders can be produced on more than one machine and these machines have different widths. Generally availability of more than one master roll width improves the waste considerably; in practice however additional order splitting constraints may have to be taken into account. There is also a semi continuous problem, where the produced rolls do not have to be of the same diameter, but can vary within a range. This typically occurs with sheet orders. This is sometimes known as a 1½ dimensional problem. This variant also occurs in the production of corrugated fiberboard, where it is called, somewhat confusingly, the corrugator scheduling problem. Because some paper machines are relatively narrow compared to the demanded items, some companies have invested in a skiving (also known as a web welding) secondary process, whereby two reels (produced by slitting the initial jumbo reels) are joined side by side (with a little overlap) to make up a wider roll. Producing narrower reels in the primary process leads to lower overall waste. In the metals industry one key difference is that typically the master rolls are produced earlier and are generally different from each other (both in terms of width and length). Therefore, there are similarities with the multi machine problem mentioned above. The presence of length variations creates a 2 D problem, because waste can occur both width wise and length wise. The guillotine problem is another 2 D problem of cutting sheets into rectangles of specified sizes, however only cuts that continue all the way across each sheet are allowed. Industrial applications of this problem can be found in the glass industry. The cutting stock problem of determining, for the one dimensional case, the best master size that will meet given demand is known as the assortment problem.
История
Проблема раскроя была впервые сформулирована Канторовичем в 1939 году. В 1951 году, до широкого распространения компьютеров, Л. В. Канторович и В. А. Залгаллер предложили решать задачу об экономичном использовании материала на этапе раскроя с помощью линейного программирования. Предложенный метод впоследствии получил название метода генерации столбцов.