Problém s řezáním materiálu - Cutting stock problem
![]() | tento článek potřebuje další citace pro ověření.Dubna 2015) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) ( |
v operační výzkum, problém řezných zásob je problém řezání kusů standardní velikosti skladem materiál, jako jsou papírové role nebo plech, na kusy specifikovaných velikostí při minimalizaci plýtvání materiálem. Je to optimalizační problém v matematika který vychází z aplikací v průmyslu. Ve smyslu výpočetní složitost, problém je NP-tvrdé problém redukovatelný na batoh problém. Problém lze formulovat jako celočíselné lineární programování problém.
Ilustrace problému jednorozměrného řezného materiálu
Papírenský stroj může vyrábět neomezený počet hlavních (jumbo) rolí, každý o šířce 5600 mm. V tabulce níže je třeba vyjmout následujících 13 položek.
Důležité na tomto druhu problému je, že ze stejného hlavního role lze vyrobit mnoho různých produktových jednotek a počet možných kombinací je sám o sobě velmi velký a není výčet nijak triviální.
Úkolem tedy je najít optimální sadu vzorů pro výrobu rolí produktu z hlavní role, aby byla uspokojena poptávka a minimalizován odpad.
Šířka # Položky 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
Hranice a kontroly
Jednoduchá dolní mez se získá vydělením celkového množství produktu velikostí každé hlavní role. Celkový požadovaný produkt je 1380 x 22 + 1520 x 25 + ... + 2200 x 20 = 407160 mm. Každá hlavní role je 5600 mm, což vyžaduje minimálně 72,7 rolí, což znamená, že je zapotřebí 73 rolí nebo více.
Řešení

Pro tuto malou instanci existuje 308 možných vzorů. Optimální odpověď vyžaduje 73 hlavních rolí a má 0,401% odpadu; lze výpočetně ukázat, že v tomto případě je minimální počet vzorů s touto úrovní odpadu 10. Lze také vypočítat, že existuje 19 různých takových řešení, každé s 10 vzory a plýtváním 0,401%, z toho jedno takové řešení je zobrazen níže a na obrázku:
Opakování Obsah 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
Klasifikace
Problémy s rozřezáním zásob lze klasifikovat několika způsoby.[1] Jedním ze způsobů je rozměrnost řezání: výše uvedený příklad ilustruje jednorozměrný (1D) problém; k dalším průmyslovým aplikacím 1D dochází při řezání trubek, kabelů a ocelových tyčí. Při výrobě nábytku, oděvů a skla se setkáváme s dvojrozměrnými (2D) problémy. Pokud je hlavní předmět nebo požadované součásti nepravidelného tvaru (situace, se kterou se často setkáváme v kožedělném, textilním a kovodělném průmyslu), označuje se to jako hnízdění problém.
Není známo mnoho trojrozměrných (3D) aplikací zahrnujících řezání; úzce související 3D problém s balením má mnoho průmyslových aplikací, jako je balení předmětů do přepravních kontejnerů (viz např. kontejnerizace: související koule balení problém byl studován od 17. století (Keplerova domněnka )).
Problém střihových zásob v papírenském, filmovém a kovodělném průmyslu
Průmyslové aplikace problémů s řezáním pro velké objemy výroby vznikají zejména tehdy, když se základní materiál vyrábí ve velkých rolích, které se dále krájí na menší jednotky (viz řezání rolí ). To se děje např. v papírenském a plastovém průmyslu, ale také ve výrobě plochých kovů, jako je ocel nebo mosaz. Existuje mnoho variant a dalších omezení vyplývajících ze speciálních omezení výroby kvůli omezením strojů a procesů, požadavkům zákazníků a problémům s kvalitou; některé příklady jsou:
- Dvoustupňový, kde se válce vyrobené v prvním stupni zpracovávají podruhé. Například všechny kancelářské potřeby (např. A4 velikost v Evropě, Velikost dopisu v USA) se vyrábí tímto způsobem. Komplikace nastává, protože strojní zařízení ve druhé fázi je užší než primární. Efektivní využití obou fází výroby je důležité (z hlediska využití energie nebo materiálu) a to, co je efektivní pro primární fázi, může být pro sekundární neefektivní, což vede k kompromisům. Metalizovaný film (používá se při balení svačinek) a vytlačování plastů na papír (používá se v tekuté obaly, např. džusové kartony) jsou dalšími příklady takového procesu.
- Omezení navíječe, kde proces řezání má fyzická nebo logická omezení: velmi častým omezením je, že je k dispozici pouze určitý počet řezacích nožů, takže proveditelné vzory by neměly obsahovat více než maximální počet rolí. Protože navíjecí stroj není standardizován, dochází k mnoha dalším omezením.
- Příkladem požadavku zákazníka je situace, kdy nelze konkrétní objednávku uspokojit z jedné ze dvou poloh hran: je to proto, že hrany listu mají tendenci mít větší rozdíly v tloušťce a některé aplikace na ně mohou být velmi citlivé.
- Příkladem problému s kvalitou je, když hlavní role obsahuje vady, které je třeba oříznout. Drahé materiály s náročnými kvalitativními charakteristikami jako např fotografický papír nebo Tyvek musí být pečlivě optimalizovány tak, aby byla minimalizována zbytečná oblast.
- Problémy s více stroji vznikají, když lze objednávky vyrábět na více než jednom stroji a tyto stroje mají různé šířky. Obecně dostupnost více než jedné šířky hlavního válce podstatně zvyšuje odpad; v praxi však bude možná třeba vzít v úvahu další omezení rozdělení objednávek.
- Existuje také polokontinuální problém, kdy vyráběné válce nemusí mít stejný průměr, ale mohou se měnit v určitém rozmezí. K tomu obvykle dochází u objednávek listů. Toto je někdy známé jako 1½ dimenzionální problém. Tato varianta se vyskytuje také při výrobě vlnité dřevovláknité desky, kde se to poněkud matoucím způsobem nazývá problém s rozvrhováním vlnité lepenky.
- Protože některé papírenské stroje jsou relativně úzké ve srovnání s požadovanými položkami, některé společnosti investovaly do a bruslení (také známý jako svařování webem) sekundární proces, při kterém jsou dva kotouče (vyrobené rozřezáním počátečních jumbo kotoučů) spojeny vedle sebe (s malým překrytím), aby se vytvořil širší válec. Produkce užších kotoučů v primárním procesu vede ke snížení celkového odpadu.[2]
- V kovozpracujícím průmyslu je jedním zásadním rozdílem to, že hlavní válce se obvykle vyrábějí dříve a obecně se navzájem liší (co se týče šířky i délky). Existují tedy podobnosti s výše uvedeným problémem s více stroji. Přítomnost délkových variací vytváří 2-D problém, protože k odpadu může dojít jak po šířce, tak po délce.[Citace je zapotřebí ]
Problém střihu ve sklářském průmyslu
The gilotinový problém je problém řezání plechů sklenka do obdélníků specifikovaných velikostí, pouze s použitím řezů, které pokračují po celém listu.


Problém se sortimentem
Související problém stanovení, pro jednorozměrný případ, nejlepší velikosti předlohy, která bude splňovat danou poptávku, je známá jako sortiment problém.[3]
Dějiny
Problém řezného materiálu nejprve formuloval Kantorovich v roce 1939.[4] V roce 1951, než byly počítače široce dostupné, L. V. Kantorovich a V. A. Zalgaller navrhl[5] řešení problému ekonomického využití materiálu ve fázi řezání pomocí lineárního programování. Navrhovaná technika byla později nazývána metoda generování sloupců.
Matematická formulace a přístupy řešení
Standardní formulace problému řezného materiálu (ale není jediná) začíná seznamem m objednávky, každá vyžaduje kousky, kde . Poté sestavíme seznam všech možných kombinací řezů (často nazývaných „vzory“). Nechat být počet těchto vzorů. S každým vzorem spojujeme kladnou celočíselnou proměnnou , představující kolikrát vzor se má použít, kde . Program lineárního celého čísla je pak:
- , celé číslo
kde je počet objednávek se objeví ve vzoru a je cena (často plýtvání) vzoru . Přesná povaha omezení množství může vést k jemně odlišným matematickým charakteristikám. Omezení množství výše uvedené formulace jsou minimální omezení (musí být vyrobeno alespoň dané množství každé objednávky, ale možná i více). Když cíl minimalizuje počet použitých hlavních položek a pokud je omezení množství, které má být vyrobeno, nahrazeno rovností, nazývá se to problém s balením koše. Nejobecnější formulace má dvoustranná omezení (a v tomto případě může řešení s minimálním odpadem spotřebovat více než minimální počet hlavních položek):
Tato formulace se netýká pouze jednorozměrných problémů. Je možné mnoho variací, včetně těch, kde cílem není minimalizovat plýtvání, ale maximalizovat celkovou hodnotu vyráběných položek, což umožňuje každé objednávce mít jinou hodnotu.
Obecně počet možných vzorů exponenciálně roste jako funkce m, počet objednávek. Jak se počet objednávek zvyšuje, může být proto nepraktické vyčíslovat možné vzory řezání.
Používá alternativní přístup zpožděné generování sloupců. Tato metoda řeší problém řezného materiálu tím, že začíná jen s několika vzory. V případě potřeby generuje další vzory. Pro jednorozměrný případ jsou nové vzory zavedeny řešením problému pomocné optimalizace zvaného batoh problém, používající informace o dvojí proměnné z lineární program. Problém s batohem má dobře známé metody jeho řešení, jako např větev a svázaný a dynamické programování. Metoda generování zpožděných sloupců může být mnohem efektivnější než původní přístup, zejména s tím, jak se zvětšuje velikost problému. The generování sloupců přístup aplikovaný na problém řezného materiálu byl propagován Gilmorem a Gomorym v řadě článků publikovaných v 60. letech.[6][7] Gilmore a Gomory ukázali, že tento přístup zaručeně konverguje k (zlomkovému) optimálnímu řešení, aniž by bylo nutné předem vyjmenovat všechny možné vzorce.
Omezení původní metody Gilmore a Gomory spočívá v tom, že nezpracovává integritu, takže řešení může obsahovat zlomky, např. konkrétní vzor by měl být vyroben 3,67krát. Zaokrouhlování na nejbližší celé číslo často nefunguje v tom smyslu, že by to mohlo vést k suboptimálnímu řešení a / nebo nedostatečné nebo nadprodukci některých objednávek (a možné neproveditelnosti za přítomnosti oboustranných omezení poptávky) ). Toto omezení je překonáno v moderních algoritmech, které dokážou k optimitě (ve smyslu hledání řešení s minimálním plýtváním) vyřešit velmi velké instance problému (obecně větší, než se v praxi vyskytují)[8][9]).
Problém stájového skladu je často velmi zvrhlý, protože je možné více řešení se stejným množstvím odpadu. K této degeneraci dochází, protože je možné přesouvat předměty a vytvářet nové vzory, aniž by to ovlivnilo množství odpadu. To vede k celé řadě souvisejících problémů, které se týkají některých dalších kritérií, například následujících:
- Problém s minimálním počtem vzorů: najít řešení s minimálním počtem vzorků mezi řešeními s minimálním množstvím odpadu. To je velmi těžký problém, i když je o odpadu známo.[10][11][12] Tady je dohad že jakákoli jednorozměrná instance omezená na rovnost s n objednávky má alespoň jedno minimální řešení odpadu s maximálně n + 1 vzory. Tato domněnka byla poprvé vyvrácena v dubnu 2020 na příkladu s 9 velikostmi, které vyžadují 11 vzorů.[13]
- Problém s minimálním zásobníkem: jedná se o řazení vzorů, aby nebylo možné mít kdykoli příliš mnoho částečně dokončených objednávek. To byl otevřený problém až do roku 2007, kdy byl zveřejněn efektivní algoritmus založený na dynamickém programování.[14]
- Problém s minimálním počtem změn nože (pro jednorozměrný problém): jedná se o sekvenování a permutaci vzorů, aby se minimalizoval počet případů, kdy je třeba řezací nože přesunout. Toto je zvláštní případ generalizovaného problém obchodního cestujícího.
Reference
- ^ Wäscher, G .; Haußner, H .; Schumann, H. Vylepšená typologie problémů s řezáním a balením. European Journal of Operational Research Volume 183, Issue 3, 1109-1130
- ^ M.P. Johnson, C. Rennick a E. Zak (1997), Přídavek bruslení k problému řezného materiálu v papírenském průmyslu, SIAM Review, 472-483
- ^ Raffensperger, J. F. (2010). "Zobecněný sortiment a nejlepší problémy s délkou řezaného materiálu". Mezinárodní transakce v operačním výzkumu. 17: 35–49. doi:10.1111 / j.1475-3995.2009.00724.x.
- ^ L. V. Kantorovich Matematické metody organizace a plánování produkce. Leningradská státní univerzita. 1939
- ^ Kantorovich L. V. a Zalgaller V. A.. (1951). Výpočet racionálního dělení zásob. Lenizdat, Leningrad.
- ^ Gilmore P. C., R. E. Gomory (1961). Přístup lineárního programování k problému řezného materiálu. Operations Research 9: 849-859
- ^ Gilmore P. C., R. E. Gomory (1963). Přístup lineárního programování k problému řezných zásob - část II. Operations Research 11: 863-888
- ^ Goulimis C (1990). Optimální řešení problému řezného materiálu. European Journal of Operational Research 44: 197-208
- ^ de Carvalho V (1998). Přesné řešení problémů s řezáním materiálu pomocí generování sloupců a rozvětvování. Mezinárodní transakce v operačním výzkumu 5: 35–44
- ^ S. Umetani, M. Yagiura a T. Ibaraki (2003). Jednorozměrný problém řezného materiálu k minimalizaci počtu různých vzorů. European Journal of Operational Research 146, 388–402
- ^ A. Diegel, E. Montocchio, E. Walters, S. van Schalkwyk a S. Naidoo (1996). Nastavení minimalizace podmínek v problému se ztrátou trimu. European Journal of Operational Research 95: 631-640
- ^ C. McDiarmid (1999). Minimalizace vzorů při problémech s řezáním materiálu. Diskrétní aplikovaná matematika, 121-130
- ^ Constantine Goulimis. Protiklady v CSP. arXiv: 2004.01937
- ^ Maria Garcia de la Banda, P. J. Stuckey. Dynamické programování k minimalizaci maximálního počtu otevřených zásobníků. INFORMS Journal on Computing, roč. 19, č. 4, podzim 2007, 607-617.
Další čtení
- Chvátal, V. (1983). Lineární programování. W.H. Freemane. ISBN 978-0-7167-1587-0.
- Hatem Ben Amor, J.M.Valério de Carvalho, Problémy s řezáním zásob in Column Generation, editace Guy Desaulniers, Jacques Desrosiers a Marius M. Solomon, Springer, 2005, XVI, ISBN 0-387-25485-4
- M. Delorme, M. Iori, S. Martello, Problémy s balením a řezáním zásob: Matematické modely a přesné algoritmy, European Journal of Operational Research 2016, 255, 1–20, doi:10.1016 / j.ejor.2016.04.030