Задача за рязане
Проблемът с влаганетое NP-пълен оптимизационен проблем, по същество свеждащ се до проблем с раница. Проблемът е целочислен проблем с линейно програмиране. Проблемът възниква в много сфери на индустрията. Представете си, че работите в фабрика за целулоза и хартия и имате няколко хартиени ролки с фиксирана ширина, но различните клиенти се нуждаят от различен брой ролки с различна ширина. Как да режем хартия, за да минимизираме отпадъците?
Според Конфедерацията на европейските производители на хартия [en] [1] през 2012 г. 1331 хартиени машини в региона генерират отпадъци средно от 56 милиона евро (приблизително 73 милиона щатски долара) всяка. Спестяването дори на 1% ще бъде много значително.
Съдържание
Тази постановка на проблема е приложима не само в едномерния случай. Възможни са много вариации, например целта не е да се минимизират отпадъците, а да се увеличи максимално общият брой произведени стоки.
Като цяло, броят на възможните карти нараства експоненциално отm, броя на поръчките. Тъй като броят на поръчките се увеличава, може да не е практично да се изброяват възможните модели на влагане.
Оригиналният метод на Гилмор и Гомори не беше цяло число, така че решението можеше да съдържа дробни компоненти, например определена карта трябваше да се използва 3,67 пъти. Закръгляването до най-близкото цяло число често не работи в смисъл, че води до неоптимално решение и недостатъчно или свръхпроизводство за някои поръчки (и възможно нарушение на ограничението, ако е двустранно). Този недостатък е преодолян в нови алгоритми, които позволяват намирането на оптимални решения (в смисъл на намиране на решение с минимални отпадъци) на много големи проблеми (обикновено по-големи от необходимото на практика [4] [5] ).
Задача за рязанечесто е изключително изродено, тъй като са възможни голям брой решения с еднакво количество загуби. Тази дегенерация възниква от способността да се пренареждат части, създавайки нови модели на влагане, но не променяйки произтичащите загуби. Това дава цяла колекция от свързани задачи, които отговарят на същите ограничения, като например:
Хартиената машина може да произвежда неограничен брой ролки (заготовки), всяка с ширина 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 |
Има 338 възможни модела на влагане за тази малка задача. Оптималното решение изисква 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 |
Задачите за влагане могат да бъдат класифицирани по различни начини [9] . Един от начините е вмъкване на размери: горният пример илюстрира едномерно влагане (1D). Други промишлени приложения за 1D разкрояване са рязане на тръби, кабели и стоманени пръти. Двумерните (2D) задачи се използват в производството на мебели, облекло и стъкло. Няма много 3D приложения на гнездене, но свързаните с тях проблеми с 3D опаковане имат много промишлени приложения, по-специално разпределението на обекти в контейнери за воден транспорт (вижте например Контейнерно корабоплаване, свързан проблем с опаковане на топки е изследван от 17-ти век (хипотезата на Кеплер)).
Индустриално приложение на проблема с гнездото в заводи за масово производство възниква, когато основният материал се произвежда на големи ролки и след това се нарязва на по-малки парчета (вижте нарязване). Това се случва например при производството на хартия и полимерни филми, както и при производството на плоски метални (желязо или бронз) листове. Има много вариации и допълнителни ограничения, дължащи се на производствени или производствени ограничения, изисквания на клиента и проблеми с качеството. Няколко примера:
- Двуетапен процес, при който ролката се произвежда на първия етап и след това се обработва отново на друга машина. Така например цялата офис хартия (например A4 в Европа, Letter в САЩ) се произвежда в този процес. Трудностите възникват, защото машините за втория процес са по-тесни от машините за първия. Ефективно използване на двата етапапроцесът е важен (както от гледна точка на икономии на материали, така и на енергия) и това, което е ефективно за първия етап, може да не е ефективно за втория и трябва да се намери компромис. Метализирано фолио [en] (използвано за опаковане на храни) и хартия с пластмасово покритие (картон за опаковане на течности [en] , например опаковка за сокове) са други примери за такива процеси.
- Навивките ограничават рязането физически или логически: общите ограничения произтичат от факта, че са разрешени само определен брой ножове, така че диаграмата за рязане не трябва да съдържа повече от определен брой ножове. Тъй като намотките не са стандартизирани, има много допълнителни ограничения.
- Като допълнително ограничение може да се даде например ограничение за посоката на рязане - различните ръбове на листа могат да имат голяма разлика в дебелината и някои приложения са много чувствителни към това.
- Пример за въздействието на изискванията за качество е, когато основната ролка съдържа дефекти, които трябва да бъдат изрязани. Скъпите материали с високи изисквания за качество, като фотохартия или Tyvek, трябва да бъдат внимателно оптимизирани, за да се сведат до минимум отпадъците.
- Задачи с много машини възникват, когато една поръчка може да бъде произведена на повече от една машина и тези машини имат различна ширина. По принцип наличието на ролки с множество източници с различна ширина намалява отпадъците. На практика обаче трябва да се вземе предвид допълнителен ред на рязане.
- Проблеми има и когато получените ролки не е задължително да са с еднакъв диаметър, а може да са в определен интервал. Понякога тази задача се извиквапроблем1½ от измерението. Този вариант се появява например при производството на велпапе.
- В промишлеността за валцуване на стомана отличителна черта е, че оригиналните намотки се различават главно както по ширина, така и по дължина. По този начин има сходство с многомашинния вариант, описан по-горе. В този случай отпадъците могат да възникнат както по ширина, така и по дължина.
Софтуерът за разкрояване за хартиената индустрия се доставя от ABB Group, Greycon, Honeywell и Tieto.
Алгоритъмът за вмъкване за стоманодобивната промишленост е формулиран от Робърт Гонгора през 1998 г. и S.O.N.S (Steel Optimization Nesting Software) разработи софтуер за подобряване на използването на стоманени плочи и намаляване на отпадъците.
Задачата за рязане с гилотина е задачата за рязане на листове стъкло на правоъгълници с определени размери, като се използват само разрези, които се простират по цялата дължина (или ширина) на листа.
Свързаният проблем за определяне (за едномерния случай) на най-добрия размер на оригиналната ролка, който отговаря на изискванията; известен като проблем сасортимента[10] .
Проблемът за разрязване е формулиран за първи път от Канторович през 1939 г. [11] . През 1951 г., дори преди компютрите да станат широко достъпни, Л. В. Канторович и В. А. Залгалер предложиха [12] метод за решаване на проблема с икономичното използване на материала по време на рязане с помощта на линейно програмиране. Предложената техника по-късно беше нареченаМетод за генериране на колони.