LÁDAPAKOLÁSI ÉS ÜTEMEZÉSI FELADATOK ELMÉLETI, ÉS SZÁMÍTÓGÉPPEL SEGÍTETT VIZSGÁLATA
Doktori (PhD) értekezés tézisei
Szerz½o: Benk½o Attila
Témavezet½o: Dr. Dósa György
PANNON EGYETEM
Matematika Tanszék Informatikai Tudományok Doktori Iskola
2014.
1
1.
Tartalmi összefoglaló
A doktori értekezés els½o része egy új, kombinált NP -nehéz feladatot tartalmaz, amely egyrészt ládapakolással van kapcsolatban, másrészt pedig szállítási, vagy ütemezési feladat is egyben. Az értekezés tartalmazza az új feladathoz tartozó o- ine (el½ore ismert az L lista, amely szerint a tárgyak érkeznek) optimum meghatározásával kapcsolatos állításokat; lényegében azt, hogy az o- ine feladatot hatékonyan meg lehet oldani, ha az összes tárgy mérete egy adott méretnél kisebb, másrészt a feladat nem approximálható jól az általános esetben (vagyis APTAS nem létezik a feladatra). Az új feladat online változatának jó és gyors megoldására egy új módszert, az Algoritmusok evolúcióját javasoljuk. Egy új, rugalmas algoritmus-család (a Mask meta-algoritmus) az új módszer felhasználásával olyan online algoritmust tud készíteni, amely a korábbi klasszikus algoritmusoknál (a stratégiai paraméterek szimulált h½utéssel történ½o beállítása miatt) jobb megoldást ad.
A doktori értekezés második része egy új, félig online ütemezési feladattal foglalkozik: két hasonló gép nonpreemptív ütemezésér½ol van szó, amikor az ütemezés végén korlátos átrendezés lehetséges, vagyis legfeljebb K
1 számú munka ütemezhet½o újra az L lista megérkezése és a munkák ideiglenes üte-
mezése után. Két speciális esetben korábban sikerült már olyan algoritmusokat konstruálnunk, amelyek optimálisak. Ezek a speciális esetek az alábbiak: Ha: s aránya: Ha: 1
2 és K s+2 s+1
s
1, akkor az LC (= Largest Change) algoritmus optimális és versenyképességi
(ahol az M1 gép sebessége 1 és az M2 gép sebessége pedig s). 2 és K
versenyképességi aránya:
2, akkor az SMF (= Small Machine First) algoritmus optimális és (s+1)2 s2 +s+1 ,
p
ha: s 2 [1; 1+2 5 ); illetve
Az el½obbi két speciális eset minden esetet lefed, kivéve, ha 1
s2 s2 s+1 ,
s
p
ha: s 2 [ 1+2 5 ; 2). 2 és K = 1. Ezzel a harmadik
esettel foglalkozunk részletesebben a doktori dolgozatban. A korábban megadott algoritmus nem optimális. Az erre az esetre megadott (és a doktori értekezésben tárgyalt) JO (= the slow machine Just Overloaded) algoritmus a korábbinál jobb versenyképességi aránnyal rendelkezik, az alábbiak szerint: Ha: s 2 [1; 2] és K = 1, akkor a javított algoritmus versenyképességi aránya: p s+2 és s+1 , ha: s 2 [ 2; 2].
2
2(s+1) s+2 ,
p ha: s 2 [1; 2];
2.
Bevezet½o
Az alábbiakban bevezetjük azokat a fogalmakat, amelyek nélkülözhetetlenek a tézisfüzetben szerepl½o állítások kimondásához. Ládapakolás-nak nevezzük azt a klasszikus feladatot, amikor adott pi (ahol i = 1; :::; n) méret½u tárgyakat kell pakolnunk minimális számú ládákba úgy, hogy a ládákba pakolt tárgyak összmérete nem lehet nagyobb, mint a ládák kapacitása, amit egységnyinek veszünk. Ládafedés során a ládát fedettnek tekintjük, ha a ládába pakolt tárgyak összmérete legalább akkora, mint a láda kapacitása. A nemrég de…niált új, ládaszállítási feladat [1] esetén a fedett ládát azonnal szállítjuk (több tárgy ebbe a szállított ládába már nem pakolható). A szállított ládák után kapott haszon a G : f1; :::; Kg ! < haszonfüggvény által adott, ahol 1
k
K a fedett láda szállításakor az egyszerre megnyitott ládák
száma. A G(k) függvényr½ol feltesszük, hogy pozitív, monoton nem növekv½o függvény. Ilyen célfüggvény például a G(k) = 10:1
0:1 k függvény, ami K = 3 esetén: G(1) = 10; G(2) = 9:9; G(3) = 9:8, vagyis
itt a fedett láda után kapott haszon egy kicsit csökken, ahogy a nyitott ládák száma n½o. A feladatban az összes hasznot maximalizáljuk, ha G konstans, akkor a klasszikus ládafedési feladatot kapjuk vissza. A feladat o- ine modelljében el½ore ismerjük a bemenetre vonatkozó összes információt, de a tárgyakat az adott L lista szerinti sorrendben kell a ládákba pakolnunk. Természetesen o- ine optimális megoldásnak léteznie kell. A feladat online modelljében nem ismerjük el½ore a bemenetre vonatkozó információkat. Közismert tény, hogy mind a ládapakolási, mind a ládafedési feladat megoldása NP nehéz [10]. Partíciós problémának nevezzük azt a feladatot, amikor el kell dönteni, hogy lehetséges-e az, hogy egy adott pozitív számokból álló véges halmaz két részre osztható-e úgy, hogy az els½o halmazban lév½o számok összege egyenl½o a második halmazban lév½o számok összegével. A partíciós problémának általánosítása a ládapakolási probléma. Ütemezés [9] esetén adott valahány, általában m-mel jelölt számú gép, amelyeken adott n számú munkát kell elvégezni úgy, hogy közben valamilyen célfüggvényérték minimumát, vagy maximumát keressük. Ezen gépek mindegyike valamilyen tulajdonsággal rendelkezhet. A dolgozatban tárgyalt modellben a munkák száma n, a munkák végrehajtási ideje pedig pi (ahol 1
i
n).
A gépeken a munkák megszakítása nem megengedett, tehát ha egy gép egy munkát már elkezdett végrehajtani, akkor annak a végrehajtását már nem szakíthatja félbe. A munkákat ütemezzük, ezen azt értjük, hogy szétosztjuk a munkákat a gépek között (minden gépnek végre kell hajtania a hozzá rendelt munkákat és csakis azokat, amelyek hozzá lettek rendelve). Ha egy gép végzett egy munkával, akkor
3
azonnal elkezd a következ½o munkán dolgozni (ha van még elvégzend½o munkája), vagyis nincs várakozási id½o. Az átlapolást nem engedjük meg, vagyis nem dolgozhat egyetlen munkán egyszerre több gép. Egy géphez hozzárendelt munkák végrehajtási idejének összegét a gép terhelésének nevezzük. Minden munkának van kezdési és befejezési id½opontja. Mivel nincs várakozási id½o, ezért egy gép terhelése egyenl½o a gépen végrehajtott utolsó munka befejezési idejével (ezt az id½opontot a gép átfutási idejének is hívjuk). A gépek átfutási idejeinek maximuma egyenl½o az ütemezés teljes átfutási idejével. A Cmax célfüggvény esetén a teljes átfutási id½ot minimalizáljuk. Hasonló gépek esetén a gépek párhuzamosan m½uködnek, minden gépnek van egy saját munkavégzési sebessége, ami eltérhet a többi gép munkavégzési sebességét½ol. Az i-edik gép munkavégzési sebességét si -vel jelöljük. A j-edik munka elvégzéséhez szükséges id½o az i-edik gépen:
pj si .
Ha az ütemezend½o munkákról minden információ adott már az ütemezés megkezdése el½ott, akkor az ütemezési feladatot o- ine-nak hívjuk. Az online esetben pedig egy adott L lista szerinti sorrendben érkeznek a munkák, és amikor egy munka megérkezik, akkor még semmit nem tudunk arról, hogy jön-e még további munka, (és ha igen, akkor az milyen). Valamely félig online (semi online) modell esetén pedig vagy részleges információnk van az inputról, vagy valamilyen algoritmikus könnyítés lehetséges. A dolgozatban tárgyalt modellben az ütemezés elvégzése után néhány munka ütemezését át szabad rendezni. Az online (vagy félig online) algoritmusok hatékonyságát versenyképességi analízissel mérik a következ½oképpen: Legyen A egy online algoritmus, jelölje CA az A algoritmus által kapott ütemezés teljes átfutási idejét és legyen COP T az optimum értéke (az o- ine ütemezés esetén). El½oször tekintsük azt az esetet, amikor a feladat célfüggvénye minimalizálandó. Ekkor az A algoritmus versenyképességi aránya a legkisebb olyan C valós szám, amelyre CA
CCOP T teljesül a munkák
tetsz½oleges sorozata esetén. Másrészt egy online (vagy félig online) feladatnak a
konstans alsó kor-
látja, ha nem létezik olyan online algoritmus, amelynek a versenyképességi aránya ennél kisebb lenne. Továbbá egy online (vagy félig online) algoritmust optimálisnak nevezünk, ha a versenyképességi aránya megegyezik a feladat alsó korlátjával. Maximalizálandó célfüggvény esetén pedig a következ½oképpen de…niáljuk a fogalmakat: Az A algoritmus versenyképességi aránya a legnagyobb olyan C valós szám, amelyre CA tetsz½oleges sorozata esetén. Ekkor a feladatnak a
CCOP T teljesül a munkák
konstans fels½o korlátja, ha nem létezik olyan online
algoritmus, amelynek a versenyképességi aránya ennél nagyobb lenne, és az online (vagy félig online) algoritmus optimális, ha a versenyképességi aránya megegyezik a feladat fels½o korlátjával.
4
3.
Új tudományos eredmények
A doktori értekezés új tudományos eredményeit két alfejezetben foglaljuk össze, a vizsgált két modellnek megfelel½oen. A bizonyításokat itt nem közöljük, azok megtalálhatóak a doktori értekezésben.
3.1.
Ládafedés szállítással
Az els½o tézispontban összefoglaljuk az általunk de…niált új feladattal, "ládafedés szállítással", kapcsolatos eredményeinket. Ládafedés szállítással -nak nevezzük az új feladatot, amivel a disszertációban foglalkozunk. Ez a feladat a ládafedési feladat általánosítása. Ebben az új feladatban nem csupán a ládák pakolásának jósága alapján min½osítjük a feladatot megoldó algoritmusokat, hanem az a célunk, hogy a szállított ládák után kapott haszon maximális legyen. A feladat pontos de…níciója a következ½o: Adott a pakolandó tárgyak halmaza (online esetben listája). Ezek mindegyikének mérete legfeljebb 1. Ezeket a tárgyakat ládákba pakoljuk. Egyszerre legfeljebb csak K darab láda lehet nyitva. Adott továbbá egy G : f1; :::; Kg ! R, monoton csökken½o haszonfüggvény is. Amint fedünk egy ládát (tehát a ládába pakolt tárgyak összmérete legalább 1 lesz), akkor a ládát azonnal elszállítjuk. Ha 1
k
K darab láda van nyitva abban a pillanatban, amikor valamely nyitott
láda fedetté válik, akkor G(k) hasznot kapunk a fedetté vált láda zárása és szállítása után. A cél az, hogy maximalizáljuk az összes hasznot. Ha a tárgyak nem sorba rendezetten helyezkednek el az L tárgylistában, akkor az o- ine optimum értékének kiszámítása még mindig NP nehéz, hiszen a feladat a klasszikus ládafedési feladat általánosítása. Az alábbi tételek segítségével azonban elég pontosan jellemezhet½o az általunk de…niált [3] ládafedés szállítással feladat.
I. TÉZIS (i) A ládafedés szállítással o- ine változata esetén bebizonyítjuk, hogy a feladat polinomiális idej½u algoritmussal optimálisan megoldható, feltéve ha a tárgyméretek egy pozitív számmal alulról korlátozhatók. Ha még ezen kívül az is igaz, hogy véges sok tárgyméret van, akkor lineáris id½oben is megoldható a feladat, (lásd 1. tétel.) (ii) Az ládafedés szállítással o- ine változat általános esetében (tetsz½oleges tárgyméretek esetén) pedig bizonyítjuk, hogy nem közelíthet½o polinomiális idej½u algoritmusokkal jól az optimális megoldás, vagyis nem létezik asszimptotikus polinomiális idej½u approximációs séma (angol rövidítése: AP T AS). Ennek egyszer½u következménye az, hogy polinomiális idej½u approximációs séma sem létezik (P T AS sem lehetséges) a feladatra (2. tétel, 3. állítás), feltéve hogy P 6= N P . 5
Az I. TÉZIS részletesebb kifejtése alább következik. 1. tétel: Legyenek K és b adott egészek, G : f1; :::; Kg ! <+ tetsz½oleges haszonfüggvény és c > 0 adott valós konstans. Ekkor: (i) Ha az input összes elemére teljesül az, hogy az elemek mérete legalább c, akkor bármely adott L listára az o- ine optimum értéke polinomiális id½oben meghatározható. (ii) Továbbá ha az inputra még az is igaz, hogy legfeljebb b különböz½o méret½u elem van benne és egyik elem mérete sem kisebb mint c, akkor bármely adott L lista esetén az o- ine optimum lineáris id½oben is meghatározható. 2. tétel: Legyen K
2 tetsz½oleges rögzített egész. Ekkor kell½oen megválasztott G haszonfüggvény
esetén létezik olyan L lista, amely esetén nem létezik olyan polinomiális idej½u algoritmus, ami
6 7 -nél
jobb
(abszolút vagy aszimptotikus) approximációs aránnyal rendelkezik, feltéve hogy P 6= N P . 3. állítás: Legyen K
2 rögzített egész. Ekkor kell½oen megválasztott G haszonfüggvény esetén
létezik olyan L lista (inputok olyan osztálya), amelyre nem létezik olyan polinomiális idej½u algoritmus, ami jobb abszolút versenyképességi hányadossal rendelkezik, mint
1 2,
feltéve hogy P 6= N P .
II. TÉZIS A második tézispontban a ládafedéses feladat szállítással kombinált változatának online modelljére mondunk ki állításokat. (i) Klasszikus algoritmusok (Dual Next Fit, Harmonic(K)) megfelel½oen módosított változatai hatékonyságát vizsgálva, azokra elméleti, illetve számítógépes tesztek alapján kapott eredményeket állapítunk meg, lásd 4.-6. Lemmák és 7. Megállapítás.) (ii) Egy új, rugalmas algoritmuscsaládot (lásd alább: MASK) de…niáltunk, amely a paramétereinek megfelel½o beállítása esetén az el½oz½o algoritmusoknál hatékonyabb, ezt számítógépes tesztekkel támasztottuk alá. (iii) Egy újfajta metaheurisztikát vezettünk be (lásd alább: EoA metaheurisztika), amely egy paraméter tanuló algoritmus, a paraméterek tanulását szimulált h½utés alkalmazásával éri el. A metaheurisztika képesnek bizonyult ara, hogy a MASK algoritmus megfelel½o paramétereit megtalálja, amelyekkel hatékonyan tudja megoldani a ládafedéseses feladat szállítással kombinált online változatának feladatát. A II. TÉZIS-hez tartozó eredmények részletes kifejtése alább következik. 4. lemma: Legyen K
2 és tegyük fel, hogy G(k) = 0 bármely 2
k
K esetén. Ebben az esetben
a DN F (dual next …t) algoritmus optimális. Továbbá a DN F optimális abban az esetben is, ha a tárgyméretek majdnem egyformák, és a versenyképességi aránya sohasem kisebb mint 12 , a következ½o állítások szerint: 6
5. lemma: Tegyük fel, hogy
1 m
< pi <
1 m 1
teljesül minden tárgyméretre, ahol m
2 rögzített egész
szám. Ekkor a DN F algoritmus optimális. 6. lemma: A DN F algoritmus versenyképességi aránya (DN F )
1 2,
tetsz½oleges G haszonfüggvény
esetén. 7. megállapítás: Ezután a következ½o klasszikus algoritmussal, a Harmonic(k) algoritmussal, (röviden H( )) és ennek egy általunk módosított "ügyes" változatával, a Smart Harmonic( ) algoritmussal (röviden SH(k)) végeztünk vizsgálatokat. Számítógépes vizsgálatok alapján meg…gyelhet½o, hogy az SH(k) algoritmus jobb eredményeket ért el, mint a korábbi DN F vagy a H(k) algoritmus. Ezek után egy új, rugalmas algoritmus-családot de…niáltunk, ez a Mask( ; ; K) meta-algoritmus, amely a stratégiai paramétereinek a beállításával éri el azt, hogy a korábbi algoritmusok bármelyikével sikeresen vegye fel a versenyt. Az algoritmus egy elfogadás-elutasítás politikát folytat: a következ½o tárgyat elfogadja, és valamely ládába pakolja, ha a ládába pakolt tárgyak (az aktuális tárgy méretével) megnövelt összmérete az "elfogadó" tartományba kerül, egyébként pedig elutasítja a tárgynak a ládába történ½o pakolását. A k-adik láda elfogadó tartománya: [0; 1 pedig: (1
k ; 1)
[ (1 +
k ; 1),
ahol 1 a ládaméret, és 0
k] k;
k
[ [1; 1 +
k ],
az elutasító tartomány
1 a stratégiai paraméterek.
Mask Algoritmus: 1. Ha a következ½o tárgy lefedi valamelyik ládát az elfogadó-tartományban, akkor pakoljuk a tárgyat abba a ládába, amelyik ezen ládák közül a legkisebb telítettség½u. Szállítsuk el a ládát és menjünk az 5-ös pontra. 2. Ha a következ½o tárgy pakolható valamelyik ládába (az elfogadó-tartományban, de a láda még nem lesz fedett), akkor pakoljuk azt egy ilyen ládába. Menjünk az 5-ös pontra. 3. Ha k < K, akkor nyissunk egy új ládát, az aktuális tárgy ebbe a ládába kerül, és menjünk az 5-ös pontra. 4. Ha k = K, akkor pakoljuk az aktuális tárgyat a legkisebb telítettség½u ládába. Ha a láda fedett lesz, szállítsuk el. Menjünk az 5-ös pontra. 5. Ha nincs több tárgy, az algoritmus megáll, különben menjünk az 1-es pontra.
Számítógépes vizsgálatok során megállapítottuk, hogy az új Mask algoritmus a paraméterek megfelel½o beállítása esetén nagyobb hasznot ért el, mint az el½oz½o algoritmusok bármelyike. Meg…gyelhet½o, hogy minden feladatosztály esetén van olyan Mask algoritmus (létezik olyan paraméterbeállítás), amelyik 7
1 2 3 4 5 6
Act 100.2% 101.1% 106% 106.6% 103.5% 114%
LS 100.6% 101.1% 106.2% 108.7% 103.6% 116.9%
EoA 101% 101.7% 106.9% 109.6% 104.7% 116.9%
1. táblázat. Az eddigi legjobb eredmények (Act), a lokális keresés (angolul: local search, röviden: LS) és az Algoritmusok Evolúciója módszerek összehasonlítása. versenyképes a korábbi legjobb algoritmussal, s½ot legy½ozi azt. Paraméter tanuló online algoritmusokkal foglalkoznak például a következ½o cikkek: [11, 14]. Ezek után megadtunk egy új módszert a paraméterek megfelel½o beállítására. Az EoA metaheurisztika: Új [5] online feladat megoldó módszer az Algoritmusok evolúciója (angolul evolution of algorithm, röviden EoA) módszer esetén a megengedett megoldások helyett az algoritmusokon lépkedünk: meghatározunk egy kell½oen rugalmas algoritmus-családot valamely online feladat megoldására, az algoritmusok között egy szomszédsági struktúrát de…niálunk, ezután egy lokális keres½o módszer segítségével kiválasztjuk az algoritmusok legjobbikát. Az általunk megadott módszer (angolul: evolution of algorithm, rövidítve: EoA) nem azonos az evolúciós algoritmusokkal (angolul: evolutionary algorithm, rövidítve: EA). Amint az alábbi táblázatból látható, az EoA módszerünk az adott feladat esetén tényleg m½uködik, vagyis alkalmas arra, hogy a feladatot hatékonyan megoldó algoritmust konstruáljon. A más algoritmusok által kapott megoldásokat helyenként lényegesen sikerült javítani. (Az adott esetekhez tartozó korábbi legjobb eredményeket, vagyis a DN F , H(k), SH(k) eredményei közül a legjobbat, a táblázat Act oszlopába válogattuk össze.) A lokális keresés (LS ) is sok esetben hatékonynak bizonyul, de ahogy várható volt ennél az EoA (a szimulált h½utés alkalmazása miatt) még hatékonyabb.
3.2.
Korlátos átrendezéssel kapcsolatos eredmények
Ebben az alfejezetben két hasonló gép nem-megszakítható ütemezési feladatát vizsgáljuk arra a félig online esetre, ha K = 1 számú munka átrendezését engedjük meg a munkasorozat el½ozetes ütemezése után, a teljes átfutási id½ot minimalizálva (tehát el½oször az összes munkát ütemezzük, és amint a sorozat végetért, az el½ozetes ütemezés elvégzése után K számú munkát átütemezhetünk más gépre).
III. TÉZIS Korábban a Chen, Lan, Benk½o, Dósa és Han 2011-es cikkében [6] tisztáztuk azokat az eseteket, amikor s
2, illetve ha 1
s
2 és K
2. Hátramaradt annak az esetnek a vizsgálata, amikor 1 8
s
2,
és az ütemezés végén csak egyetlen átrendezés megengedett, vagyis K = 1. Ezzel az esettel foglalkozik a dolgozat befejez½o része, az eredményeket [15] cikkünk tartalmazza. A III. Tézis is ezzel a feladattal kapcsolatos. (i) Két hasonló gép ütemezési feladatával foglalkozunk, ahol 1
s
2, és az ütemezés végén csak
egyetlen átrendezés megengedett, vagyis K = 1. Erre az esetre megadtunk egy javított versenyképességi aránnyal rendelkez½o algoritmust (JO algoritmus). Az algoritmus versenyképességi arányáról szól a 8. tétel megállapítása. A III Tézishez tartozó eredményeket alább részletesebben ismertetjük. p 2 esetén a [13] cikkben, Abban az esetben ha 1 s 2 és K = 1, a korábbi legjobb eredmény s p illetve s 2 esetén a [6] cikkben található. Ezek a korábbi legjobb eredmények:
0
ahol s
0
(s) =
8 < :
(s+1)2 s+2 ; s+2 s+1 ;
1 p
s< 2
p
s
2; 2
(s) jelüli a korábbi legjobb algoritmus(ok) versenyképességi arányát. Megjegyezzük, hogy a
2 intervallumra a [13] cikk a viszonylag gyenge
s+1 s
p
2<
fels½o korlátot adták meg.
Ezen a korábbi legjobb eredményen a [15] cikkben az 1
s<
p
2 intervallumon sikerült javítani. A
javított versenyképességi arány:
(s) =
8 < :
2(s+1) s+2 ; s+2 s+1 ;
1 p
s 2<s
p
2; 2
A korábbi és a javított versenyképességi arányok görbéit az alábbi ábrán mutatjuk be. Megjegyezzük, p hogy 2 < s 2 esetén ugyan nem javítottunk a korábbi arányon, de az új algoritmusunk nem azonos a korábbi algoritmussal (ezen az intervallumon sem). Az algoritmus leírása az alábbi: adott két fázis, az els½o fázis az ütemezés, a második pedig az újrarendezés fázisa. Az ötlet az, hogy az ütemezési fázisban a gyors gépet végig alulterheltnek ütemezzük, és ha muszáj, akkor a lassú gépet terheljük túl. Az újrarendezési fázisban pedig a legnagyobb munkát áthelyezzük a lassú gépr½ol a gyors gépre, de csak akkor, ha ez szükséges, vagyis ezáltal javul a teljes átfutási id½o. Az algoritmust JO algoritmusnak nevezzük, ami a "the slow machine Just Overloaded’ rövidítése.
9
1. ábra. A vastag görbék jelentik a javított fels½o korlátokat K = 1 esetén.
JO Algoritmus: Ütemezési fázis: amikor a pt méret½u jt munka megérkezik: 1. Frissítjük a 2. Legyen
t
alsó korlátot.
a már korábban az M1 géphez rendelt legnagyobb munka mérete. Ha pt + L1t
maxf ; pt g
(s)
1
t , akkor a jt munka az M1 gépre kerül, (vagyis más szóval ez azt jelenti
hogy ezt e lépést akkor hajtjuk végre, ha a jt munkának az M1 gépre ütemezésével, és eztán az M1 gépr½ol legfeljebb egy munkát áthelyezve az M2 gépre az M1 gép alulterhelt marad illetve azzá válik). 3. Minden más esetben a jt munkát az M2 gépre ütemezzük. Újrarendezési fázis: ha az input végetért. 1. Helyezzük át a legnagyobb munkát az M1 gépr½ol az M2 gépre, feltéve, ha ez szükséges (vagyis, ha a munka áthelyezésével csökken a teljes átfutási id½o).
tétel: A JO algoritmus versenyképességi aránya 1 p versenyképességi arány 2 < s 2 esetén s+2 s+1 . 8.
s
p
2 esetén
2(s+1) s+2 ,
valamint a
A doktori értekezés témájához kapcsolódik a következ½o két SCI folyóiratcikk [3, 15], egy magyar nyelv½u cikk [2], valamint a következ½o két konferencia kiadvány: [5, 8], és a [4] kézirat. Ezen publikációkon kívül az alábbi két SCI folyóirat publikáció, és konferencia kiadvány is megjelent: [6, 7, 12]. Felsoroljuk a publikációinkra eddig kapott független hivatkozásokat is.
10
Hivatkozások [1] Gy. Dósa, Zs. Tuza, Bin Packing/Covering with Delivery: some variations, theoretical results and e¢ cient o- ine algorithms. arXiv: 1207.5672v1, 2011. [2] A. Benk½o, Gy. Dósa, Egy új feladat: Ládafedés szállítással, és ennek megoldása algoritmusok evolúciójával, Alkalmazott Matematikai Lapok 27 (2010), 1-12. [3] A. Benk½o, Gy. Dósa, Zs. Tuza, Bin Covering with a general pro…t function: approximability results, Central European Journal of Operations Research, 21()4, (2013), 805-816. Impact factor: 0.484 [4] A. Benk½o, Gy. Dósa, Zs. Tuza, A new tool "Evolution of Algorithms", for solving the hard combinatorial problem Bin Packing with Delivery, submitted, 2013. [5] A. Benk½o, Gy. Dósa, Zsolt Tuza, Bin Packing/Covering with Delivery, Solved with the Evolution of Algorithms, Proceedings 2010 IEEE 5th International Conference on Bio-Inspired Computing: Theories and Applications, BIC-TA 2010, art. no. 5645312, (2011), 298-302. [6] X. Chen, Y. Lan, A. Benk½o, G. Dósa, X. Han Optimal algorithms for online scheduling with bounded rearrangement at the end. Theoretical Computer Science, 412(45) (2011), 6269-6278. Impact factor: 0.838 [7] X. Chen, Gy. Dósa, X. Han, C. Zhou, A. Benk½o, 2D Knapsack: Packing Squares, FAW-AAIM 2011 Conference, LNCS 6681 (2011), 176-184. [8] Gy. Dósa, A. Benk½o, X. Han, Reassignment models on two related machines, Proc. Conf. MAPSP 2011, 256-258, 10th Workshop on Models and Algorithms for Planning and Scheduling Problems, Nymburk, Chech Republic, 2011 July 19-24, Institute of Theoretical Computer Science, Charles University. [9] Gy. Dósa, Cs. Imreh, Online algoritmusok, Elektronikus jegyzet, Typotex kiadó, 2011. [10] M. Garey, J. David, A Guide to the Theory of NP-Completeness, Computers and Intractability, New York, 1979. [11] Cs. Imreh, T. Németh, Parameter learning in online scheduling algorithms, Proc. Conf. MAPSP 2011, 10th Workshop on Models and Algorithms for Planning and Scheduling Problems, Nymburk, Chech Republic, 2011 July 19-24, Institute of Theoretical Computer Science, Charles University. [12] Y. Lan, Gy. Dósa, X. Han, C. Zhou, A. Benk½o, 2D knapsack: Packing squares, Theoretical Computer Science, 508 (2013), 35-40. Impact factor: 0.489 11
[13] M. Liu, Y. Xu, C. Chu, F. Zheng, Online scheduling on two uniform machines to minimize the makespan, Theoretical Computer Science, 410(21-23) (2009), 2099-2109. [14] T. Németh, Cs. Imreh, Parameter Learning Online Algorithm for Multiprocessor Scheduling with Rejection, Acta Cybernetica 19 (2009) 125–133. [15] Y. Wang, A. Benk½o, X. Chen, Gy. Dósa, H. Guo, X. Han, C. Sik Lanyi, Online scheduling with one rearrangement at the end: Revisited. Inform. Process. Lett. 112(2012), 641-645. Impact factor: 0.612
A [5] cikkre hivatkozik: 1. Gergely A. Sik, Salem G. Nehme, Cecilia Sik-Lanyi, The optimization of the self-compecting concrete (SCC) production scheduling-specially the e¤ect of the …ne aggregate, IACSIT International Journal of Engineering and Technology, 4(4), August 2012. 2. Cecilia Sik-Lanyi, Balazs Kocsi, Erika Laszlo, Towards a user friendly rehabilitation game-A case study, IACSIT International Journal of Engineering and Technology, 4(4), August 2012. A [6] a cikkre hivatkozik: 1. S Albers, M Hellwig, on the value of job migration in online makespan minimization, LNCS 7501, ESA 2012, 7501, 2012, 84-95
12
