REAL

Online erőforrás allokációs problémák = Online resource allocation problems

Imreh, Csanád (2009) Online erőforrás allokációs problémák = Online resource allocation problems. Project Report. OTKA.

[img]
Preview
PDF
48587_ZJ1.pdf

Download (88kB)

Abstract

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. | 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.

Item Type: Monograph (Project Report)
Uncontrolled Keywords: Informatika
Subjects: Q Science / természettudomány > QA Mathematics / matematika > QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány
Depositing User: Mr. Andras Holl
Date Deposited: 07 Sep 2010 14:30
Last Modified: 30 Nov 2010 14:03
URI: http://real.mtak.hu/id/eprint/2238

Actions (login required)

Edit Item Edit Item