Řezací úkol

Problém vnoření  je NP-úplný optimalizační problém , v podstatě redukovatelný na problém batohu . Problém je celočíselný problém lineárního programování . Problém nastává v mnoha oblastech průmyslu. Představte si, že pracujete v celulózce a papírně a máte řadu rolí papíru s pevnou šířkou, ale různí zákazníci potřebují různé počty rolí různých šířek. Jak řezat papír, abyste minimalizovali odpad?

Podle Konfederace evropských výrobců papíru [1] v roce 2012 vyprodukovalo 1 331 papírenských strojů v regionu průměrný odpad každý ve výši 56 milionů eur (přibližně 73 milionů amerických dolarů). Úspora i 1 % bude velmi významná.

Formulace problému a přístupy k řešení

Standardní formulace problému vnoření (ale ne jediná) předpokládá seznam m zakázek, každá zakázka vyžaduje kusů. Vytvoříme všechny možné kombinace vnoření („řezací mapy“) a ke každé mapě přiřadíme kladnou celočíselnou proměnnou označující, kolikrát byla mapa použita. Zapišme si problém lineárního programování:

kde  - kolikrát se objednávka objeví na kartě a  - cena (často ztracená) karty . Přesná povaha omezení může vést k mírně odlišným matematickým charakteristikám. Uvedené limity jsou minimální limity ( musí být vyrobeno alespoň dané množství, ale není vyloučeno, že se bude vyrábět více). Pokud , je nutné minimalizovat počet nařezaných kusů výchozího materiálu. Pokud jsou omezení z nerovností nahrazena rovností, problém se nazývá kontejnerizace . V obecnější formulaci jsou omezení oboustranná (a v tomto případě se řešení minimalizace ztrát může lišit od řešení s minimálním počtem kusů zdrojového materiálu):

Tato formulace problému je aplikovatelná nejen na jednorozměrný případ. Je možných mnoho variací, cílem například není minimalizovat odpad, ale maximalizovat celkový počet vyrobeného zboží.

Obecně počet možných karet roste exponenciálně s m , počtem objednávek. S rostoucím počtem objednávek nemusí být praktické vypisovat možné vzory vnoření.

Alternativně lze použít postgeneraci . Tato metoda řeší problém vnoření tím, že začíná s několika kartami. Metoda generuje nové mapy, pokud je to potřeba, během procesu řešení. V jednorozměrném případě se nové mapy objevují při řešení dalšího optimalizačního problému, problému batohu , který využívá informace o duálních proměnných problému lineárního programování . Problém batohu má dobře známé metody pro jeho řešení, jako je metoda větví a vazeb a dynamické programování . Generování líných sloupců může být mnohem efektivnější než původní přístup, zvláště když velikost úlohy roste. Zpožděné generování sloupců , jak je aplikováno na problém hnízdění, bylo poprvé použito Gilmourem a Gomorym v sérii prací publikovaných v 60. letech [2] [3] . Ukázali, že tento přístup zaručeně povede k (částečně) optimálnímu řešení, aniž by bylo nutné předem vyjmenovat všechny možné mapy.

Původní metoda Gilmoura a Gomoryho nebyla celočíselná, takže řešení mohlo obsahovat zlomkové složky, například určitá mapa musela být použita 3,67krát. Zaokrouhlení na nejbližší celé číslo často nefunguje v tom smyslu, že má za následek neoptimální řešení a podprodukci nebo nadprodukci u některých zakázek (a možné porušení omezení, pokud jsou oboustranné). Tento nedostatek je překonán novými algoritmy, které umožňují nalézt optimální řešení (ve smyslu hledání řešení s minimálním odpadem) velmi rozsáhlých problémů (obecně větších, než je v praxi potřeba [4] [5] ).

Problém hnízdění je často extrémně degenerovaný, protože je možné velké množství řešení se stejným množstvím ztrát. Tato degenerace vzniká ze schopnosti přeskupovat části, vytvářet nové vzory vnoření, ale neměnit výsledné ztráty. To poskytuje celou kolekci souvisejících úkolů, které splňují stejná omezení, jako například:

• Úkol najít minimální počet hnízdních map: najít řešení s minimálním počtem hnízdních map mezi řešeními s minimálními ztrátami. Tento úkol je velmi obtížný, i když jsou ztráty známé [6] [7] . Existuje domněnka , že jakýkoli rovnicí omezený jednorozměrný problém vnoření s n řády má alespoň jedno řešení minimálního odpadu s n + 1 vnořovacími mapami. Horní hranice počtu vnořených grafů nejsou známy, i když příklady s n + 5 jsou známy.

• Úkol minimálního skladu: najít sekvenci řezání tak, aby se nehromadilo velké množství částečně dokončených zakázek. Problém byl otevřený až do roku 2007, kdy byl publikován účinný algoritmus založený na dynamickém programování [8] .

• Problém minimálního počtu výměn nožů (pro problém jednorozměrného vnoření): najděte posloupnost použití map vnoření, aby se minimalizoval počet pohybů řezacích nožů. Tento problém je zvláštním případem obecného problému obchodního cestujícího .

Ilustrace jednorozměrného problému řezání

Papírenský stroj dokáže vyrobit neomezený počet rolí (přířezů), každý o šířce 5600 mm. Potřebujete získat následujících 13 finálních hodů:

Řešení

Pro tento malý úkol existuje 308 možných vzorů vnoření. Optimální řešení vyžaduje 73 originálních rolí a má 0,401 % odpadu. Lze prokázat, že minimální počet hnízd pro toto množství odpadu je 10. Lze také vypočítat, že existuje 19 takových různých řešení, každé s 10 hnízdy a 0,401 % odpadu. Jedno takové řešení je znázorněno níže a na obrázku:

Klasifikace

Úlohy hnízdění lze klasifikovat různými způsoby [9] . Jedním ze způsobů je vnoření rozměrů: výše uvedený příklad ilustruje jednorozměrné vnoření (1D). Další průmyslové využití pro 1D hnízdění je řezání trubek, kabelů a ocelových tyčí. Dvourozměrné problémy se používají při výrobě nábytku, oděvů a skla. Není mnoho aplikací 3D vnořování, ale související problémy s 3D balením mají mnoho průmyslových aplikací, zejména distribuci předmětů do přepravních kontejnerů ( viz např. Keplerova hypotéza .

Úkol řezání v papírenském, filmovém a ocelářském průmyslu

Průmyslová aplikace problému hnízdění v závodech hromadné výroby nastává, když se základní materiál vyrábí ve velkých rolích a poté se řeže na menší kusy (viz řezání ). K tomu dochází například při výrobě papírových a polymerních fólií a také při výrobě plochých kovových (železných nebo bronzových) plechů. Existuje mnoho variant a dodatečných omezení v důsledku výrobních nebo procesních omezení, požadavků zákazníků a problémů s kvalitou. Nějaké příklady:

• Dvoustupňový proces, kdy se role vyrábí v první fázi a poté se znovu zpracovává na jiném stroji. Tímto procesem se vyrábí například veškerý kancelářský papír (např . A4 v Evropě, Letter v USA). Potíže vznikají, protože stroje pro druhý proces jsou užší než stroje pro první. Efektivní využití obou procesních kroků je důležité (jak z hlediska úspory materiálu, tak úspory energie) a co funguje pro první krok, nemusí fungovat pro druhý a je třeba najít kompromis. Dalšími příklady takových procesů jsou metalizovaná fólie (používaná pro balení potravin) a papír potažený plastem ( karta na balení kapalin , například balení šťáv).

• Navíječe omezují řezání fyzicky nebo logicky: obecná omezení vyplývají ze skutečnosti, že je povolen pouze určitý počet nožů, takže tabulka řezání by neměla obsahovat více než určitý počet nožů. Vzhledem k tomu, že navíječky nejsou standardizovány, existuje mnoho dalších omezení.

• Jako další omezení lze uvést například omezení směru řezání - různé okraje plechu mohou mít velký rozdíl v tloušťce a některé aplikace jsou na to velmi citlivé.

• Příkladem dopadu požadavků na kvalitu je, když hlavní role obsahuje vady, které by měly být vyříznuty. Drahé materiály s vysokými požadavky na kvalitu materiálu, jako je fotografický papír nebo Tyvek , by měly být pečlivě optimalizovány, aby se minimalizoval odpad.

• Úlohy s více stroji vznikají, když lze zakázku vyrobit na více strojích a tyto stroje mají různé šířky. V zásadě dostupnost více zdrojových rolí s různými šířkami snižuje odpad. V praxi se však musí počítat s dodatečnou zakázkou řezání.

• Existují také problémy, kdy výsledné role nemusí mít stejný průměr, ale mohou být v určitém intervalu. Někdy se tento problém nazývá problém 1½ rozměru . Tato varianta se objevuje například při výrobě vlnité lepenky .

• V průmyslu válcování oceli je charakteristickým rysem to, že původní svitky se liší hlavně šířkou a délkou. Existuje tedy podobnost s výše popsanou vícestrojovou variantou. V tomto případě může dojít k odpadu jak na šířku, tak na délku.

Nesting software pro papírenský průmysl dodává ABB Group , Greycon , Honeywell a Tieto .

Vnořovací algoritmus pro ocelářský průmysl formuloval Robert Gongorra v roce 1998 a SONS (Steel Optimization Nesting Software) vyvinul software pro zlepšení využití ocelových plechů a snížení odpadu.

Problém řezání pro sklářský průmysl

Úkolem řezání gilotinou  je řezání tabulí skla na obdélníky konkrétních rozměrů pouze pomocí řezů, které probíhají po celé délce (nebo šířce) tabule.

Problém se sortimentem

Související problém určení (pro jednorozměrný případ) nejlepší velikosti původní role, která splňuje požadavky; známý jako problém sortimentu [10] .

Historie

Problém řezání poprvé formuloval Kantorovich v roce 1939 [11] . V roce 1951, ještě předtím, než se počítače staly široce dostupnými, L. V. Kantorovich a V. A. Zalgaller navrhli [12] metodu řešení problému hospodárného využití materiálu při řezání pomocí lineárního programování. Navrhovaná technika byla později nazývána metodou generování sloupců .

Software

Poznámky

1. ↑ Klíčové statistiky 2012 (nedostupný odkaz) . Konfederace evropského papírenského průmyslu. Získáno 3. července 2013. Archivováno z originálu dne 6. října 2014. (neurčitý) 
2. ↑ PC Gilmore, RE Gomory. Přístup lineárního programování k problému řezného materiálu // Operační výzkum. - 1961. - č. 9 . - S. 849-859 .
3. ↑ PC Gilmore, RE Gomory. Přístup lineárního programování k problému řezného materiálu - Část II // Operační výzkum. - 1963. - č. 11 . - S. 863-888 .
4. ↑ C. Goulimis. Optimální řešení problému řezného materiálu // European Journal of Operational Research. - 1990. - č. 44 . - S. 197-208 .
5. ↑ V. de Carvalho. Přesné řešení problémů obrábění pomocí generování sloupců a větvené // Mezinárodní transakce v operačním výzkumu. - 1998. - č. 5 . - S. 35-44 .
6. ↑ S. Umetani, M. Yagiura a T. Ibaraki. Problém jednorozměrného řezného materiálu pro minimalizaci počtu různých vzorů // European Journal of Operational Research. - 2003. - č. 146 . - S. 388-402 .
7. ↑ A. Diegel, E. Montocchio, E. Walters, S. van Schalkwyk a S. Naidoo. Nastavte podmínky pro minimalizaci problému ztráty seřízení // European Journal of Operational Research. - 1996. - č. 95 . - S. 631-640 .
8. ↑ Maria Garcia de la Banda, PJ Stuckey. dynamické programování pro minimalizaci maximálního počtu otevřených zásobníků // INFORMUJE žurnál o počítačích. - 3007. - T. 19 , č. 4 . - S. 607-617 .
9. ↑ G. Wäscher, H. Haußner, H. Schumann. Vylepšená typologie problémů s řezáním a balením // European Journal of Operational Research. - T. 183 , č. 3 . - S. 1109-1130 .
10. ↑ Raffensperger John F. Zobecněný sortiment a problémy s nejlepší délkou řezného materiálu  // International Transactions in Operational Research. - 2010. - Leden ( roč. 17 , č. 1 ). - S. 35-49 . — ISSN 0969-6016 . - doi : 10.1111/j.1475-3995.2009.00724.x .
11. ↑ L. V. Kantorovič. Matematické metody organizace a plánování výroby. – Leningradská státní univerzita.
12. ↑ Kantorovich L. V., Zalgaller V. A. Racionální řezání průmyslových materiálů. - Novosibirsk: Nauka, 1971.

Literatura

• lineární programování. - W. H. Freeman, 1983. - ISBN 978-0-7167-1587-0 .
• Hatem Ben Amor, JM Valério de Carvalho. Generace sloupů // Problémy s řezáním zásob v generaci sloupců / Guy Desaulniers, Jacques Desrosiers a Marius M. Solomon. - Springer, 2005. - T. XVI. — ISBN 0-387-25485-4 .

Odkazy

• Evropská zvláštní zájmová skupina pro řezání a balení
• Základní algoritmus hrubé síly pro řezání materiálu
• Algoritmus řešení bin Packing and Cutting Stock Solver