Two-dimensional Cutting Problems
| Thesis title: | Dvourozměrné řezné problémy |
|---|---|
| Author: | Rada, Miroslav |
| Thesis type: | Diplomová práce |
| Supervisor: | Fábry, Jan |
| Opponents: | Jablonský, Josef |
| Thesis language: | Česky |
| Abstract: | 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. |
| Keywords: | balící problémy; řezné problémy; Best-fit algoritmus |
| Thesis title: | Two-dimensional Cutting Problems |
|---|---|
| Author: | Rada, Miroslav |
| Thesis type: | Diploma thesis |
| Supervisor: | Fábry, Jan |
| Opponents: | Jablonský, Josef |
| Thesis language: | Česky |
| Abstract: | 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. |
| Keywords: | Best-fit algorithm; packing problems ; cutting problems |
Information about study
| Study programme: | Kvantitativní metody v ekonomice/Ekonometrie a operační výzkum |
|---|---|
| Type of study programme: | Magisterský studijní program |
| Assigned degree: | Ing. |
| Institutions assigning academic degree: | Vysoká škola ekonomická v Praze |
| Faculty: | Faculty of Informatics and Statistics |
| Department: | Department of Econometrics |
Information on submission and defense
| Date of assignment: | 1. 9. 2008 |
|---|---|
| Date of submission: | 10. 1. 2009 |
| Date of defense: | 3. 2. 2009 |
| Identifier in the InSIS system: | https://insis.vse.cz/zp/13387/podrobnosti |