České Vysoké Učení Technické v Praze Fakulta Elektrotechnická
Kombinatorická optimalizace
Petr Kubašta Dvojrozměrný řezný problém
Praha, 2012
1
Zadání
Firma zabývající se výrobou dětských hraček řeší problém, jak z polystyrenové desky vyřezat co nejvíce kostiček z jejich sortimentu. Pro zadané množství kostiček je potřeba vytvořit řezný plán, který bude minimalizovat počet použitých desek a tedy odpad. Materiál desky je obráběn cirkulární pilou. Polystyrenová deska má rozměry 100x60 cm. Sortiment kostiček je množina {60x15, 30x15, 15x15, 20x10}.
2
Kategorizace problému
Úloha spadá do úloh o dělení 2D plochy, kde plocha je pravoúhlá, objekty na které se má plocha rozdělit jsou také pravoúhlé a jejich orientace je n π2 , ∀n ∈ Z. Dále se předpokládá, že cirkulární pila provádí řezy přes celou plochu. V anglické literatuře se to často nazývá jako takzvaný „Two-Dimensional bin packing problem“ nebo pro nás důležitější modifikace „Two-Dimensional Cutting Stock Problem“ . Ve dvojrozměrném řezném problému je dána množina n pravoúhlých položek, každá položka má svoji šířku wi a výšku hi i ∈ {1..n} a existuje nekonečné množství pravoúhlých desek s šířkou W a výškou H. Problém je naskládat položky do minimálního počtu desek. Položky se nesmějí překrývat, mají fixní orientaci.
3
Související práce
Úloha je modifikací klasického řezného. Problém lze řešit v různých modifikacích. Do roku 1991 identifikoval Sweeney a Paternoster [4] přes 500 článků zabývajících se nějakou modifikací nebo aplikací tohoto problému. První model pro dvojrozměrný řezný problém navrhl Gilmore a Gomory [2], kteří rozšířili jejich metodu používanou pro 1D variantu, metoda je založena na dynamickém programování. Dvou rozměrný problém je zde řešen jako dvoufázový jednorozměrný problém. Deska je nejprve rozdělena na pruhy a poté jsou pruhy rozděleny na požadované položky. Další významnou prací je práce J. E. Beasleyho [1], který navrhl několik algoritmů založených vesměs na dynamickém programování. Beasley v této práci řeší i rozdělení řezání na různý počet fází (stages). Fáze 1
je charakteristická směrem řezu, ten může být vertikální nebo horizontální. A platí, že každé dvě následující fáze jsou na sebe kolmé, příklad 3 - fázového dělení je na obrázku 1.
Obrázek 1: Ukázka 3- fázového řešení problému [3]
Puchinger a Raidl [3] uvedli dva polynomiálně velké ILP modely pro tří fázový 2D-BPP ( 2D- bin packing problem). Původní a omezený model. Omezený model dává rychle skoro optimální výsledky, zato původní model je časově mnohem náročnější.
4
Popis algoritmů
V následujících odstavcích budou popsány některé heuristické algoritmy, řešící tento problém. Tyto algoritmy umisťují požadované položky na desku, jednu po druhé. Mezi nejpopulárnější algoritmy patří: next-fit, best-fit. Algoritmy přidávají položky z leva do prava, položky jsou přidávány na jednotlivé výškové úrovně. Výška úrovně odpovídá horizontální čáře, která splývá s nejvyšší položkou umístěnou na předchozí úrovni. V 2
popisu algoritmů předpokládejme, že výběr položky pro umístění je realizován podle nerostoucí výšky. Jinými slovy, nejprve umisťujeme položky s vyšší výškou. • Next-Fit (snižující se výška): Položka je zarovnána vlevo, pokud to jde, pokud to nejde, je vytvořena další úroveň a položka je umístěna tam. • Best - Fit (snižující se výška): Položka je zarovnána vlevo, kontrola možnosti zarovnání probíhá od první do poslední úrovně. Pokud je v nějaké úrovni dostatek horizontálního prostoru, položka je do této úrovně umístěna, jinak je vytvořena nová úroveň.
a) Po provedení Next-Fit
b) Po provedení Best-Fit
Obrázek 2: Ukázka výsledků heuristických algoritmů
Obrázek 2, ukazuje výsledné uspořádání po průběhu jednotlivých algoritmů. Výhodou těchto algoritmů je, že z principu splňují omezení, při kterém jsou jednotlivé řezy prováděné od jedné strany materiálu ke druhé (tzv. guillotinable). Nevýhodou může být, že při nevhodném rozložení rozměrů jednotlivých položek nemusí být řešení moc dobré. V další části naznačíme postupy používající lineární programování. V literatuře mlčky předpokládají výchozí Gilmore-Gomoryho model. Tento model lze obecně vyjádřit následovně rovnicemi:
3
Min: P
j∈J0
λ0j
s.a. : M 0λ = 0 M 00 λ ≥ B λ≥0 J0 . . . množina validních řezných vzorů λ0j . . . j-tý řezný vzor přiřazený k první fázi λSj . . . j-tý řezný vzor přiřazený k s-té množině řezných vzorů druhé fáze T λ : (λ01 , . . . , λ11 , . . . , λm 1 , . . .) B : (b1 , . . . , bm )T . . . vektor požadovaného množství jednotlivých elementů M0 , MS . . . submatice možných řezných vzorů pro první fázi a s-tou množinu druhé fáze
Při případném použití Gilmore - Gomoryho modelu, zůstává otevřenou otázkou jaký postup použít pro generování možných řezných vzorů. Tento problém se ještě nepodařilo ideálně vyřešit.
5
Popis implementace
K implementaci byl vybrán algoritmus Best-Fit. Tento algoritmus se z výše zmiňovaných jeví jako rozumná volba. Avšak v extrémních případech se může chovat poměrně neoptimálně, pro částečnou eliminaci těchto případů byla vyvinuta unikátní heuristika, tak zvané statistické rotace a další postupy, které budou uvedeny v následujících odstavcích. 5.1
Heuristika statistické rotace
Problémem základního algoritmu Best-Fit je, že explicitně neřeší natočení obdélníku, které skládá do binu. Skládá pouze obdélníky, za sebou 4
podle nerostoucí výšky. Problém se objeví, pokud algoritmu dodaný bin je silně asymetrický a jeho výška je hodně rozdílná, než výška ostatních binů. Tento jev vystihuje obr 3 a). Jak je vidět, červeně vyznačené plocha, už nebude nikdy použita. Pokud by ovšem byl element 1 otočen o Π2 , žádná nevyužitelná plocha by nevznikla. Výsledek této modifikace ukazuje obrázek 3 b).
a) Bez statistické rotace
b) Se statistickou rotací
Obrázek 3: Ukázka výsledků algoritmu Best-Fit
Tento problém, lze řešit apriorní rotací. Před seřazením elementů podle výšky spočítáme modus M ze všech výšek a všech délek všech instancí jednotlivých elementů. Poté každý jednotlivý element natočíme, tak abychom minimalizovali odchylku od M. Tuto rotaci lze obecně vyjádřit následovně. hi = hi ∧ wi = wi pokud |M − hi | < |M − wi | wi = hi ∧ hi = wi pokud |M − hi | > |M − wi | pro všechny elementy Takto minimalizujeme odchylky od Modu. Jinými slovy, jednotlivé hladiny, budou pravděpodobněji podobně vysoké. 5.2
Modifikovaný algoritmus Best-Fit
Implementovaný modifikovaný algoritmus lze obecně popsat následujícím způsobem: 5
Algoritmus 1: modifikovaný BEST-FIT Vypočítá řezný plán, s minimalizací odpadu. 1: Spočítej modus rozměrů 2: Proveď statistickou rotaci 3: Uspořádej prvky do nerostoucí posloupnosti podle výšky 4: Proveď klasický Best-fit 5: Proveď klasický Best-fit s binem otočeným o π2 6: Vygeneruj řezný plán, pro případ natočení binu, při kterém je odpad menší z řádku 4 a 5
Bylo zjištěno, že velikost výsledného odpadu, záleží v některých případech i na natočení binu, tuto nepříjemnost eliminují řádky 4 a 5 algoritmu 1, které v implementaci běží směle ve dvou vláknech.
6 6.1
Experimenty Měření časové a paměťové náročnosti implementace
V této části se zaměříme především na kvantitativní experimenty týkající se časové a paměťové složitosti. Nutno podotknout, že měření byla prováděna pouze jednou, či-li mají vysokou nejistotu, naměřené hodnoty nebereme tedy jako bernou minci, ale mají spíše informativní charakter o průběhu, který lze aproximovat regresní funkcí. Dále je nutné podotknout, že měření paměti a času probíhalo v samostatných experimentech, ač výsledky budou prezentovány pro přehlednost společně. Cíl experimentu:
Změřit časovou a paměťovou náročnost implementace modifikovaného algoritmu Best-Fit. Schéma experimentu:
V experimentu se bude zvyšovat počet elementů a ke každému počtu elementů bude změřena doba běhu a velikost naalokované paměti. Měření času a paměti probíhá v oddělených bězích, aby se navzájem neovlivňovala.
6
Naměřené výsledky:
Tabulka 6.1 dává základní představu o běhu pro jednotlivé počty instancí. Globální představu pak dávájí grafy na obrázcích 4 a 5. Počet prvků [ks] 1 000 20 000 50 000 100 000 150 000 500 000
Doba běhu [ms] 40 136 1 055 20 525 59 921 806 081
Naalokovaná paměť [kB] 190 1 223 2 885 5 579 8 300 27 541
Tabulka 1: Výsledky měření
Obrázek 4: Změřená časová složitost
Obrázek 5: Změřená paměťová složitost 7
Na grafech je dále patrné, že časová složitost se dá aproximovat kvadratickou regresní fukcí a paměťovou složitost lze aproximovat přímkou. Zhodnocení experimentu:
Měření dokázalo, že Best-Fit má kvadratickou časovou a lineární paměťovou složitost. Konkrétně v našem případě lze v historicky krátkém čase vyřešit instance řádu statisíce kusů. Výsledek pro 500 000 ks lze získat přibližně za 14 minut. Na paměťové limitace jsme nenarazili. 6.2
Měření kvality řešení pro reálné instance - modifikovaná a nemodifikovaná verze
Tento experiment si klade za cíl ověřit kvalitu řešení pro reálné instance problému. Měřítkem kvality řešení bude vyprodukované procento odpadu. porovnáme klasický přístup s modifikovaným přístupem. Cíl experimentu:
Změřit kvalitu řešení, vyprodukované procento odpadu. Porovnat klasický Best-Fit s naším vylepšeným Best-Fitem. Schéma experimentu:
Pro desku s rozměry 100x60 a elementy z množiny {60x15, 30x15, 15x15, 20x10} budeme náhodně generovat množství jednotlivých elementů a vyhodnocovat vzniklý odpad. Množství jednotlivých elementů je v rozmění 1000 - 5000 ks, počty elementů typu 60x15 jsou desetinové. Bude změřeno 10x1000 výpočtů a spočítán průměrný procentuální odpad. Naměřené výsledky: Modifikovaný [%] 0.165
Klasický [%] 2.933
Tabulka 2: Průměrný odpad v %
8
Nejistota měření typu A u modifikovaného algoritmu:ua = 0.0024% Nejistota měření typu A u klasického algoritmu:ua = 0.045%
Zhodnocení experimentu:
Experiment ukázal, že jednoduchá úprava algoritmu, která je prakticky zadarmo zlepší řešení o více než 2.5% odpadu. 6.3
Závěr experimentů:
Experimenty dokázaly, že algoritmus je zhusta použitelný. Naše modifikace zlepšila na požadovaných instancích řešení. Avšak byly provedeny i experimenty s náhodně generovanými rozměry elementů, v těchto experimentech je naše řešení (unikátní heuristika statistické rotace) také lepší, nikoli však tak markantně a v podstatě je srovnatelné s klasickým Best-Fit. Úloha se nám povedla a měření se nám líbilo.
9
Reference [1] Beasley,J.E.: Algorithms for unconstrained two-dimensional guillotine cutting. Journal of the Operational Research Society 36, 1985. [2] Gilmore,P.C.; Gomory,R.E.: Multistage cutting stock problems of two and more dimensions. Operation research 13:94-120, 1965. [3] Puchinger; Raidl: Models and algorithms for three-stage two-dimensional bin packing. European Journal of Operational Research, 127(3):1304-1327, 2007. [4] Sweeney,P.E.; Paternoster,E.R.: Cutting and packing problems: An updated literature review. Working Paper No. 654, University of Michigan, School of Business, 1991.
10