Department of Computer Algorithms and Artificial Intelligence (University of Szeged)
Starting date
2005-01-01
Closing date
2009-12-31
Funding (in million HUF)
1.944
FTE (full time equivalent)
1.44
state
closed project
Final report
Results in Hungarian
Jellemző probléma, hogy korlátozott mennyiségű erőforrást kell szétosztani a felmerülő igények között. Számos esetben a probléma online, azaz a probléma inputját csak részenként ismerjük meg és döntéseinket a már megkapott információk alapján a további adatok ismerete nélkül kell meghoznunk. A kutatásaink során ilyen, online erőforrás allokációs problémákkal foglalkoztunk az alábbi részterületeken.
Az ütemezés elméletében olyan problémákat vizsgáltunk, amelyekben az ütemezésen kívül más döntéseket is meg kell hozni az algoritmusnak, speciálisan a gépköltséges (a gépek száma nem adott paraméter, hanem meg kell őket vásárolni) és visszautasítható munkák modelljeit tanulmányoztuk. Ládapakolás és ládafedés esetén azon modelleket vizsgáltuk, amelyekben a ládák tartalmára a megkövetelt összsúlyon kívül további korlát is adott (pl a ládában szereplő elemek számára, vagy az elemek fajtáinak számára). Egy további modellt is vizsgáltunk, ahol a ládák száma adott és a cél a minimális összsúllyal lefedni az összes ládát. A nyugtázási probléma során előrenéző algoritmusokat vizsgáltunk, amelyek csak félig online algoritmusok, mert a döntés időpontjában az input egy további részéről (de nem az egészről) is rendelkeznek információval.
A vizsgált modellek megoldására új algoritmusokat fejlesztettünk ki, azokat a versenyképességi elemzés alapján megvizsgáltuk. Néhány esetben, ahol a versenyképességi elemzés nem volt releváns empirikus elemzést hajtottunk végre.
Results in English
In optimization problems it often happens that we have to allocate some bounded resources.
In some cases these problems are online, which means that we receive the input part by part, and we have to make the decision without any information about the further parts. In the project we analysed such problems.
In scheduling the we considered the problem of scheduling with machine cost (the number of machines is not part of the input, we have to buy it) and scheduling where the jobs can be rejected. In bin packing and covering we considered the problems where extra condition is given for the bins (the number of items, or the number of items of different types). Furthermore we investigated a model, where the number of bins is given, and the goal is to minimize the total size of items which cover them. In data acknowledgment we considered the time lookahead version, where the algorithm has some partial extra information about the further part of the input.
In each model we developed new algorithms and analysed them by competitive analysis. In some cases where competitive analysis was not useful we used empirical analysis.
Imreh Cs.: On the generalized models of on-line scheduling with machine cost, Proceedings of MAPSP (7-th Workshop on Models and Algorithms for Planning and Scheduling Problems), 151-152, 2005
T. Bartók, Cs. Imreh: A mixed multidimensional bin packing problem, VOCAL 2008 konferencia, 2008
Cs. Imreh,: Online bin covering with cardinality constraints, VOCAL 2006 konferencia (L. Epstein, A. Levin-el bővitett változat közlésre benyújtva), 2006
Imreh Cs., Németh T.: On time lookahead algorithms for the online data acknowledment problem, Proceedings of 32nd International Symposium on Mathematical Foundations of Computer Science Springer, LNCS 4708, 288-297, 2007
Nagy-György J., Imreh Cs.,: Online scheduling with machine cost and rejection, Discrete Applied Mathematics 155, 2546--2554, 2007
Cs. Imreh, T Németh: Parameter learning algorithm for online data acknowledgement, VOCAL 2008 konferencia, 2008
Cs. Imreh, T. Németh: On empirical analysis for online algorithms for the data acknowledgment problem, Proceedings of of microCAD 2008, International Scientific Conference, Mathematics and Computer Science section 2-6, 2008
Imreh Cs.: On-line scheduling with general machine cost functions, Discrete Applied Mathematics, online first, DOI: 10.1016/j.dam.2007.10.014, 2009
L. Epstein, Cs. Imreh, A. Levin: Class constrained bin covering, Theory of Computing Systems, online first, DOI: 10.1007/s00224-008-9129-7, 2009
T. Németh, Cs. Imreh: Parameter Learning Algorithms in Online Scheduling, The Sixth Conference of PhD Students in Computer Science, Szeged, 2008 (folyóirat cikk benyújtva, Acta Cybernetica minor revisions), 2008
Events of the project
2013-01-25 11:08:58
Kutatóhely váltás
A kutatás helye megváltozott. Korábbi kutatóhely: Informatikai Tanszékcsoport (Szegedi Tudományegyetem), Új kutatóhely: Számítógépes Algoritmusok és Mesterséges Intelligencia Tanszék (Szegedi Tudományegyetem).
