|
|
Dvourozměrné řezné problémy
Rada, Miroslav ; Fábry, Jan (vedoucí práce) ; Jablonský, Josef (oponent)
Práce se v úvodu zabývá typologií řezných problémů a jejich vztahem k problémům balícím. Tyto problémy jsou roztříděny podle Wascher a kol. (2005) pomocí pěti základních kritérií do tzv. "upřesněných typů problémů", které představují dostatečně podrobné a prakticky použitelné členění řezných úloh. Z široké palety algoritmů pro řešení řezných úloh se práce zabývá vybranými zajímavými reprezentanty. Stručně je popsán algoritmus Viswanathan-Bagchi (1991) pro exaktní řešení omezených dvojrozměrných ortogonálních úloh dělení materiálu gilotinovými řezy, jenž umožňuje zpracovat širokou škálu různých typů dodatečných omezení úlohy. Hlavní část práce se zabývá heuristickými algoritmy pro řešení ortogonálních úloh neomezeného rozměru. Podrobně je popsán algoritmus Best-fit podle Burke a kol (2004). V práci jsou zavedeny dvě modifikace tohoto algoritmu, které ve 42 z 89 testovacích úloh umožnily vylepšit řešení oproti původní verzi algoritmu, přičemž pouze v 10 případech bylo dosažené řešení horší. Při implementaci algoritmu jsou též zavedeny nové, efektivnější datové struktury a postupy, které umožnily vyřešit testovací úlohu s cca 50 000 obdélníky zhruba za 2,5 vteřiny.
|
host ::
RSS.