Reálná aplikace online plošného uspořádávání mnohoúhelníků
| Název práce v češtině: | Reálná aplikace online plošného uspořádávání mnohoúhelníků |
|---|---|
| Název v anglickém jazyce: | Real application of online 2D irregullar bin packing |
| Klíčová slova: | bin packing problem|problém naplnění zásobníků|optimalizace|online algoritmus|MaMBA project|2DIBPP |
| Klíčová slova anglicky: | bin packing problem|optimization|online algorithm|MaMBA project|2DIBPP |
| Akademický rok vypsání: | 2020/2021 |
| Typ práce: | bakalářská práce |
| Jazyk práce: | čeština |
| Ústav: | Katedra fyziky kondenzovaných látek (32-KFKL) |
| Vedoucí / školitel: | RNDr. Petr Čermák, Ph.D. |
| Řešitel: | Bc. Damian Wałoszek - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 18.02.2021 |
| Datum zadání: | 18.02.2021 |
| Datum potvrzení stud. oddělením: | 25.08.2021 |
| Datum a čas obhajoby: | 10.09.2021 09:00 |
| Datum odevzdání elektronické podoby: | 23.07.2021 |
| Datum odevzdání tištěné podoby: | 22.07.2021 |
| Datum proběhlé obhajoby: | 10.09.2021 |
| Oponenti: | Mgr. Pavel Veselý, Ph.D. |
| Konzultanti: | Mgr. Martin Koutecký, Ph.D. |
| Zásady pro vypracování |
| Ú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]. |
| Seznam odborné literatury |
| [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/ |
| Předběžná náplň práce |
| Ř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. |