Dvourozměrné řezné problémy
| Název práce: | Dvourozměrné řezné problémy |
|---|---|
| Autor(ka) práce: | Rada, Miroslav |
| Typ práce: | Diplomová práce |
| Vedoucí práce: | Fábry, Jan |
| Oponenti práce: | Jablonský, Josef |
| Jazyk práce: | Česky |
| Abstrakt: | 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. |
| Klíčová slova: | balící problémy; řezné problémy; Best-fit algoritmus |
| Název práce: | Two-dimensional Cutting Problems |
|---|---|
| Autor(ka) práce: | Rada, Miroslav |
| Typ práce: | Diploma thesis |
| Vedoucí práce: | Fábry, Jan |
| Oponenti práce: | Jablonský, Josef |
| Jazyk práce: | Česky |
| Abstrakt: | The thesis first addresses the typology of cutting problems and their relationship to the packing problems. These are categorized (Wascher et al (2005)) according to 5 basic kriteria into the so-called "refined problem types", which is the sufficiently detailed and practical segmentation of cutting problems. The thesis deals with a selected sample of some of the most interesting algorithms from the wide range of those used to solve the cutting problems. The Viswanathan-Bagchi algorithm for the exact solution of constrainted two-dimensional orthogonal Cutting stock probléme with gillotine cuts is briefly described. It enables to process a wide range of additional problem constraints. The body of the thesis concentrates on heuristic algorithms used to solve orthogonal Open dimension problems. The Best-fit algorithm according to Burke et al. (2004) is described in detail. The work introduces two modifications of this algorithm that helped improve the solution in 42 out of the 89 benchmark problems, while a worse solution was achieved only in 10 of them. Moreover, new and more effective data structures and procedures that enable to solve the testing exercise with approx 50 000 rectangles in just about 2,5 seconds have been introduced. |
| Klíčová slova: | Best-fit algorithm; packing problems ; cutting problems |
Informace o studiu
| Studijní program / obor: | Kvantitativní metody v ekonomice/Ekonometrie a operační výzkum |
|---|---|
| Typ studijního programu: | Magisterský studijní program |
| Přidělovaná hodnost: | Ing. |
| Instituce přidělující hodnost: | Vysoká škola ekonomická v Praze |
| Fakulta: | Fakulta informatiky a statistiky |
| Katedra: | Katedra ekonometrie |
Informace o odevzdání a obhajobě
| Datum zadání práce: | 1. 9. 2008 |
|---|---|
| Datum podání práce: | 10. 1. 2009 |
| Datum obhajoby: | 3. 2. 2009 |
| Identifikátor v systému InSIS: | https://insis.vse.cz/zp/13387/podrobnosti |