Reálná aplikace online plošného uspořádávání mnohoúhelníků
| Thesis title in Czech: | Reálná aplikace online plošného uspořádávání mnohoúhelníků |
|---|---|
| Thesis title in English: | Real application of online 2D irregullar bin packing |
| Key words: | bin packing problem|problém naplnění zásobníků|optimalizace|online algoritmus|MaMBA project|2DIBPP |
| English key words: | bin packing problem|optimization|online algorithm|MaMBA project|2DIBPP |
| Academic year of topic announcement: | 2020/2021 |
| Thesis type: | Bachelor's thesis |
| Thesis language: | čeština |
| Department: | Department of Condensed Matter Physics (32-KFKL) |
| Supervisor: | RNDr. Petr Čermák, Ph.D. |
| Author: | Bc. Damian Wałoszek - assigned and confirmed by the Study Dept. |
| Date of registration: | 18.02.2021 |
| Date of assignment: | 18.02.2021 |
| Confirmed by Study dept. on: | 25.08.2021 |
| Date and time of defence: | 10.09.2021 09:00 |
| Date of electronic submission: | 23.07.2021 |
| Date of submission of printed version: | 22.07.2021 |
| Date of proceeded defence: | 10.09.2021 |
| Opponents: | Mgr. Pavel Veselý, Ph.D. |
| Advisors: | Mgr. Martin Koutecký, Ph.D. |
| Guidelines |
| Úkolem práce je provést reálnou aplikaci online NP problému pro co nejefektivnější uspořádávání polygonů na ploše s omezeným počtem rotací (online irregular 2D bin packing problem). Řešitel zjistí kompetitivní poměr mezi jeho algoritmem a dostupnými offline algoritmy používanými v praxi [1-3]. Teoretické řešení zjednodušené úlohy pro obdélníky popisuje Epsteinová [4]. Výsledný algoritmus bude použit v zařízení ALSA na uspořádávání krystalů, který je na MFF vyvíjen v rámci projektu MaMBA [5]. |
| References |
| [1] D. Dalalah, S. Khrais, K. Bataineh. Waste minimization in irregular stock cutting. Journal of Manufacturing Systems 33 (2014) 27-40. DOI: 10.1016/j.jmsy.2013.11.003
[2] R.P. Abeysooriya, J.A. Bennell, A. Martinez-Sykora. Jostle heuristics for the 2D-irregular shapes bin packing problems with free rotation. International Journal of Production Economics 195 (2018) 12-26. DOI: 10.1016/j.ijpe.2017.09.014 [3] Q. Liu, Zeng J., H. Zhang, L. Wei. A Heuristic for the Two-Dimensional Irregular Bin Packing Problem with Limited Rotations. Lecture Notes in Computer Science 12144 (2020) 268-279. DOI: 10.1007/978-3-030-55789-8_24 [4] L. Epstein. A lower bound for online rectangle packing. J Comb Optim 38 (2019) 846–866. DOI:10.1007/s10878-019-00423-z [5] https://mambaproject.cz/ |
| Preliminary scope of work |
| Řešitel se bude zabývat problematikou dvojdimenzionálního online packing problému a jeho reálnou aplikací. Offline varianta tohoto problému je často řešena ve výrobě, kde například minimalizuje množství látky nutné ušití šatů. Na katedře fyziky kondenzovaných látek je momentálně vyvíjen difraktometr umožňující automatické uspořádávání plochých krystalů. Použití offline algoritmu je však technicky komplikované, a je proto žádoucí ukázat, o kolik horší bude použití online algoritmu (tedy umísťování tvarů bez znalosti tvarů dalších).
Bakalářská práce bude kombinovat praktický a teoretický přístup k problému. V rámci teorie vznikne nový algoritmus a bude diskutována jeho časová složitost. Praktická část bude obsahovat samotnou implementaci a experimentální vyhodnocování efektivity algoritmu a porovnávání s nejlepšími dostupnými online i offline algoritmy. |