témavezető: Dósa György
helyszín (magyar oldal): Pannon Egyetem, Matematika Tanszék helyszín rövidítés: PE
A kutatási téma leírása:
A ládapakolás mint önálló tudományág körülbelül 40 éves, az ütemezéselmélet ennél valamivel régebbi. E két tudományág területén belül alakultak ki az azóta más területeken is alkalmazott approximációs algoritmusok, illetve ezek hatékonyságbecslései. Sok, és jelentős cikket publikálnak ezeken a területeken. A ládapakolás is és az ütemezés is számos ponton kapcsolódik a gyakorlathoz, ipari feladatokhoz. Bizonyos feladatok, illetve algoritmusok ma már klasszikusnak számítanak, ezen algoritmusok megfelelő variánsait a megfelelő módosítással új feladatok megoldására is alkalmazzák. A terület más tudományterületekhez is szervesen kapcsolódik, például gráfelmélethez, játékelmélethez, a téma tehát rendkívül szerteágazó. A megoldási módszerek között szerepelnek úgynevezett egzakt algoritmusok, approximációs algoritmusok, heurisztikus módszerek, meta-heurisztikák. Ezáltal elméleti és számítógépes vizsgálatok végzése is érdekes lehet.
A leendő PhD hallgató feladata az ütemezéselmélet vagy ládapakolás valamely változatának a vizsgálata, feldolgozni a már létező eredményeket, új (elméleti és/vagy számítógépes) vizsgálatokat végezni, új eredményeket elérni, azokat publikálni.
A kutatási téma előzményei:
J. Balogh, J. Békési, G. Dosa, J. Sgall, R. van Stee, The optimal absolute ratio for online bin packing, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on
Discrete Algorithms (SODA), San Diego, 2015 (January), pp. 1425-1438
J. Balogh, J. Bekesi, G. Dosa, L. Epstein, H. Kellerer, Zs. Tuza, Online Results for Black and White Bin Packing, Theory of Computing Systems, 2015, Vol 56, Iss 1, 137-155.
G. Dosa, First Fit Algorithm for Bin Packing, Reference Work Entry, Encyclopedia of Algorithms, 1-5, 12 November 2014
G. Dosa, Z. Tan, Zs. Tuza, Y. Yan, C. Sik Lányi, Improved Bounds for Batch Scheduling with Non-identical Job Sizes, Naval Research Logistics, 61(5), 351–358, 2014.
G. Dosa, L. Epstein, Preemptive scheduling on a small number of hierarchical machines, Information and Computation, 206 (5), 602-619, 2008.
Dósa Gy., Imreh Cs., Online algoritmusok, Elektronikus jegyzet, Typotex Kiadó, 2011.
felvehető hallgatók száma: 1
Jelentkezési határidő: 2020-02-28
2024. IV. 17. ODT ülés Az ODT következő ülésére 2024. június 14-én, pénteken 10.00 órakor kerül sor a Semmelweis Egyetem Szenátusi termében (Bp. Üllői út 26. I. emelet).
Bejelentkezés
