témavezető: Imreh Csanád
helyszín (magyar oldal): SZTE TTIK Matematika- és Számítástudományok Doktori Iskola 6720 Szeged, Aradi vértanúk tere 1. helyszín rövidítés: MatDI
A kutatási téma leírása:
Online problémának nevezzük azokat a feladatokat, amelyekben a probléma inputját csak részenként ismerjük meg és a döntéseket mindig csak a már megismert információk alapján kell meghoznunk. Számos ilyen probléma merül fel az operációkutatás és az elméleti számítástudomány különböző területein. Az erőforrás allokációs problémák többnyire az ütemezés és a ládapakolás témaköréhez tartoznak, de néhány új, a számítógépes hálózatok témaköréhez tartozó modell is ismert.
Az on-line algoritmusok elemzésének legismertebb módszere a versenyképességi analízis (amely során korlátokat adunk az optimális off-line és az on-line algoritmus által kapott megoldások célfüggvényértékeinek hányadosára), a kifejlesztett algoritmusokat ezzel a módszerrel tervezzük elemezni. Az ütemezés témakörében a kutatás főleg olyan modellek vizsgálatát tartalmazza, ahol az ütemezésen kívül az algoritmusnak egyéb döntéseket is meg kell hoznia (munkák visszautasítása, gépek vásárlása). A pakolási problémák területén olyan modellek vizsgálata a kutatások tárgya, amelyekben az egyes ládák tartalmára extra feltételek is elő vannak írva.
Előzmények rövid összefoglalása: Az on-line algoritmusok elemzésére a versenyképességi elemzés az 1980-as évek végére terjedt el. Az elemzési módszer számos, ma már klasszikus alkalmazása mind az ütemezés mind pedig a ládapakolási problémák területéhez kapcsolódóan megtalálható a [1] könyvben és a [2] könyvfejezetben. A kiírt témán belül mind a gépköltséges mind pedig a visszautasításos ütemezési modellben több eredmény született. A visszautasításos modellre vonatkozó eredmények összefoglalása megtalálható a [3] cikkben, amely dolgozat egy olyan ütemezési modellt vizsgál, amely a visszautasításos modell egy általánosításaként interpretálható. A visszautasításos modell mellett a gépvásárlásos modellre vonatkozó eredmények összefoglalása pedig a [4] cikkben található meg, amely cikk azt az ütemezési modellt vizsgálja, ahol mind a munkák visszautasítása mind pedig a gépek vásárlása megengedett. A ládapakolási problémák összefoglalása megtalálható az [5] cikkben. A leggyakrabban használt megszorítás az, hogy korlátozzuk az egy ládába pakolható elemek számát. A kapcsolódó eredmények megtalálhatóak az [6] cikkben.
[1] A. Borodin, R. El-Yaniv, Online Computation and Competitive Analysis, Cambridge University Press, 1998.
[2] Imreh Cs., Versenyképességi elemzés, Informatikai Algoritmusok II, szerk. Iványi A., ELTE Eötvös Kiadó, 2005, 1350--1383.
[3] Cs. Imreh, Scheduling problems on two sets of identical machines, Computing, 70, (2003), 277--294.
[4] J. Nagy-György, Cs. Imreh, On-line scheduling with machine cost and rejection, közlésre benyújtva, (http://www.inf.u-szeged.hu/~cimreh˛/F047587t2.pdf)
[5] J. Csirik, G. Woeginger, On line packing and covering problems, in Online algorithms: The State of the Art (LNCS 1442) szerk. A. Fiat, and G. J. Woeginger, Springer-Verlag Berlin, Heidelberg, 1998, 147—177.
[6] L. Epstein, On-line bin packing with cardinality constraints, Proceedings of ESA 2005,
(LNCS 3669), 604-615
Bejelentkezés
