Új ütemezési eljárás kifejlesztése erőforrás menedzsment feladatokra

Új ütemezési eljárás kifejlesztése erőforrás menedzsment feladatokra Diplomaterv Készítette Horony Csaba Mérnök Informatikus MSc

Témavezetők: Dr. Oláh András és Tornai Kálmán

Pázmány Péter Katolikus Egyetem Információs Technológiai Kar 2012.

Alulírott Horony Csaba, a Pázmány Péter Katolikus Egyetem Információs Technológiai Karának hallgatója kijelentem, hogy ezt a Diplomatervet meg nem engedett segítség nélkül, saját magam készítettem, és a Diplomatervben csak a megadott forrásokat használtam fel. Minden olyan részt, melyet szó szerint, vagy azonos értelemben, de átfogalmazva más forrásból átvettem, egyértelműen a forrás megadásával megjelöltem. Ezt a Diplomatervet más szakon még nem nyújtottam be.

Tartalomjegyzék Tartalmi kivonat

1

Abstract

2

1 Bevezetés

3

1.1

1.2

Áttekintés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.1.1

Pénzügyi-gazdasági erőforrások . . . . . . . . . . . . . . . . . . . .

3

1.1.2

Kliens-szerver probléma . . . . . . . . . . . . . . . . . . . . . . . .

4

1.1.3

Kommunikáció . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

A dolgozat felépítése . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

2 Ütemezési módszerek 2.1

2.2

6

Knapsack probléma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2.1.1

Részleges Knapsack probléma . . . . . . . . . . . . . . . . . . . . .

7

2.1.2

Integrál Knapsack probléma . . . . . . . . . . . . . . . . . . . . . .

8

2.1.3

Többszörös választásos Knapsack probléma . . . . . . . . . . . . .

9

2.1.4

Többszörös Knapsack probléma . . . . . . . . . . . . . . . . . . . .

9

Round-robin ütemezés . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

2.3. P

roportional fair ütemezés

. . . . . . . . . . . . . . . . . . . . . . .

12

2.4

Maximális átviteli ütemezés . . . . . . . . . . . . . . . . . . . . . . . . . .

13

2.5

Job Shop ütemezés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

2.5.1

Online algoritmus . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

2.5.2

Johnson algoritmusa

. . . . . . . . . . . . . . . . . . . . . . . . .

16

2.6

Total Tardiness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

2.7

Total Weighted Tardiness . . . . . . . . . . . . . . . . . . . . . . . . . . .

18

2.7.1

Earliest Due Date . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

2.7.2

Weighted Shortest Processing Time . . . . . . . . . . . . . . . . .

20

2.7.3

Largest Weighted Process First . . . . . . . . . . . . . . . . . . . .

20

3 Multihop Aperiodic Scheduling 3.1

22

Rendszermodell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22

3.1.1

A WSN modell . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22

3.1.2

Az ütemezés megfogalmazása . . . . . . . . . . . . . . . . . . . . .

25

i

Tartalomjegyzék 3.2

Kvadratikus eszköztár . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

3.2.1

Az ütemezés QP transzformációja . . . . . . . . . . . . . . . . . .

30

3.3

HNN paraméter becslés . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

3.4

Smart Hopfield Neural Network

. . . . . . . . . . . . . . . . . . . . . . .

37

3.5

Perturbed Smart Hopfield Neural Network . . . . . . . . . . . . . . . . . .

38

3.5.1

39

Perturbáció heurisztika . . . . . . . . . . . . . . . . . . . . . . . .

4 Konklúziók és fejlesztési lehetőségek

41

5 Összefoglalás

43

Köszönetnyilvánítás

44

Irodalomjegyzék

45

ii

Tartalmi kivonat Diplomatervemben ütemezési módszerekkel foglalkozom az erőforrás menedzsment témaköréhez kapcsolódóan. Ütemezések optimalizálása az egyik legkézenfekvőbb eszköz az erőforrások hatékony felhasználásához. Minden felhasználási területen szükséges jó ütemezési módszert választani, mint ahogy egy processzor ütemezésben, úgy a kommunikációban vagy gyártási folyamatban is. Általában a felmerülő feladványok megoldása NP-nehéz. Ezért az eljárásainkban különböző heurisztikákat alkalmazunk, melyek legjobban igazodnak a felmerülő problémához. Bemutatok több alapvető ütemezési módszert és ezek megoldására néhány eljárást. A módszerek megismerése segít betekintést nyerni a mögöttes feladványok közötti különbségekre, mint az elvégzendő feladatok és az azokat teljesítő eszközök közötti kapcsolatra, vagy a költségek természetére, azok megjelenésének okaira. A problémákhoz kialakított modellek közötti különbségek főként a különböző korlátozó tényezőkből származtathatóak. Részletezem a Multihop Aperiodic Scheduling (MAS) heurisztikus eljárást, mely egy vezetéknélküli szenzor hálózatban (WSN) történő ütemezési problémára ad polinom idejű megoldást. Ez az új Total Tardiness (TT) alapú ütemezési eljárás speciális tulajdonságai miatt átalakítható kvadratikus optimalizációs feladatra, amit Hopfield Neurális Hálózattal (HNN) oldunk meg. Ennek a módszernek ígéretes eredményei születtek eddig, amik nagy feladatszámú (job) ütemezési problémára is jobb eredményt adtak más alkalmazott eljárásokhoz képest. Ennek az eljárásnak a módosított smart HNN (sHNN), valamit perturbed sHNN (psHNN) változatait vizsgáltam, és a kapott szimulációs eredményeket mutatom be.

1

Abstract In my Diploma I’m dealing with scheduling methods within the topic of resource management. The optimization of the schedulings is one of the most obvious tool towards effective resource utilization. In every area of application it is needed to choose the most fitting scheduling methods as in processor scheduling so in communication or in production processes. Generally the arising tasks are NP-hard. That’s why in our algorithms we need to use different heuristics which fits the most for our problem. I present several basic scheduling problems and some algorithms solving them. Understanding these models helps us to gain insight into the differences of the underlying problems such as the connection between the jobs and the machines or the nature of the costs and the reasons of their appearance. The differences between the models created to fitting the problems can be derived from the different limiting factors. I specify the Multihop Aperiodic Scheduling (MAS) heuristic algorithm which gives a polynomial time solvable solution for a Wireless Sensor Network (WSN) scheduling problem. This novel Total Tardiness (TT) scheduling based algorithm can be transformed to quadratic optimization which is solved by a Hopfield Neural Network (HNN). So far this method has promising results even for scheduling tasks with large number of jobs it gave better results compared to other applied algorithms. I investigated its modified smart HNN (sHNN) and perturbed sHNN (psHNN) methods and I show the obtained results.

2

1 Bevezetés 1.1 Áttekintés Az Erőforrás menedzsment több tudományban is fontos szerepet tölt be, mivel szinte minden erőforrásunk szűkösen áll rendelkezésre egyáltalán fizikai mennyiségében, időben vagy költsége szempontjából. Ezeket az erőforrásokat úgy szeretnénk felhasználni, hogy minél több eredmény, termék, nagyobb hasznosság származzon belőle, vagy másik oldalról tekintve, ugyanazon eredmény eléréséhez minél kevesebbet kelljen felhasználni belőlük. Tehát könnyen tudjuk az erőforrásokat költségként kezelni, ami által egy matematikailag nagyon jó eszközhöz jutunk, mert az optimális erőforrás menedzsmentet, ami az erőforrások felhasználási módját jelenti, a haszon/hasznosság maximalizálásával vagy költségek minimalizálásával érhetjük el. A legfontosabb tervezési és modellalkotási kérdések ezek után az adott költségek és hasznosság valós meghatározását jelentik. A következő példákban bemutatom az erőforrás menedzsment több fontos alkalmazási területét.

1.1.1 Pénzügyi-gazdasági erőforrások Samuelson definíciója szerint: „A közgazdaságtan azokat a szabályokat és törvényszerűségeket igyekszik megfogalmazni, amelyek alapján az egyének és közösségek döntenek a szűkösen rendelkezésre álló, többféle célra alkalmas erőforrások felhasználásáról. A közgazdaságtan a termelési döntések mellett tanulmányozza az elosztás és a fogyasztás során követett elveket is.” Ebben a világban az erőforrások a következőkben foglalhatók össze • természeti erőforrások, mint a nyersanyagok és termények, környezeti értékeink, • humán erőforrások, mint a munkaerő, kreativitás vagy szaktudás és • tőke. Ezek felhasználását pedig a szükségletek és a hasznosság határozzák meg a termelési lehetőségek határának tekintetében. Hasznosnak tekintünk közgazdasági értelemben minden olyan jószágot, amely képes a társadalom valamely tagjának szükségletét kielégíteni. Tehát itt célunk lehet a szükségletek olyan kielégítése, hogy az a lehető leghasznosabb legyen számunkra. A társadalomban, ezt a céloknak megfelelő gazdaságpolitikával lehet befolyásolni. Kisebb méretekben viszont rengeteg konkrét alkalmazási területet találhatunk,

3

1.1 Áttekintés például befektetések terén, ahol egy jobban jövedelmező befektetési portfólió a célunk, vagy gyártási kapacitások jobb kihasználása érdekében megfelelő ütemezés tervezése.

1.1.2 Kliens-szerver probléma Az informatikában széleskörűen ismert feladat, mely modellnek célja, hogy egy igény kielégítésére az erőforrásokat nyújtó szerver a szolgáltatás minőségi követelményeinek megfelelően szolgálja ki a szolgáltatást kérő klienseket. Ez történhet PCI buszon, egy közös elérésű memória vezérlőjében vagy bármely erre a célra kialakított hardver eszközön, vagy számítógépes hálózatokon, mint amilyen az internet. Ezen szolgáltatásokat végző alkalmazásoknak általában van egy harmadik eleme is, melyet alkalmazás szervernek hívnak. Ebben dől el, hogy a kliensek kiszolgálása milyen sorrendben mekkora kapacitással történjen. Ezen problémák elterjedtségüknél fogva rendkívüli figyelmet kaptak. Minden ilyen rendszerben a feladatok/kérések feldolgozásához ütemezési eljárásokat alkalmaznak, melyek gyakran figyelembe veszik a kérések prioritását, súlyozását, határidőket, feldolgozási időket, illetve alkalmazhatnak stabilizáló elemeket is, mint pl. lejárati időt, ami után egy feladatot eldobnak vagy nem szolgálnak ki.

1.1.3 Kommunikáció Vezeték nélküli kommunikáció során az adatátvitel hatékonyságát két eszköz között sok tényező befolyásolja. Ilyenek a távolság, sávszélesség, környezet, esetleges akadályok. Ezek áthidalásához, illetve ezekhez való alkalmazkodáshoz sok hardveres és szoftveres megoldás áll rendelkezésre, melyeket alkalmaznak is a telekommunikációs eszközökben. Olyan esetben, amikor sok eszköz kapcsolódik egymással, felmerülnek olyan újabb problémák is, hogy ezek a berendezések már zavarják egymást, így sok adatunk elveszhet vagy a adatátvitel több erőforrást vesz igénybe, illetve az átfolyó adatmennyiség is erősen lecsökkenhet. Ezek az erőforrások lehetnek közös hozzáférésűek, illetve elosztva minden felhasználónak saját forrásai is. Ezért szükség van olyan eljárásokra, amik optimalizálni tudják a sok eszköz közötti kommunikációt, képesek megfelelő módon szabályozni, illetve ütemezni a túlnyomó részben szűkös erőforrásokat. Az ütemezés egy optimalizációs eljárás bizonyos erőforrások megfelelő allokálása több felhasználó vagy fogyasztó között, adott megszorítások mellett biztosítva a szolgáltatáshoz tartozó QoS követelményeket [24]. Egy döntési folyamatot jelent, melynek a vezeték nélküli vagy vezetékes kommunikáció mellett sok a fentebb említett területeken kívül más ipari, műszaki és szervezési alkalmazása is van. Feladata a meglévő erőforrások lehető legjobb felhasználásának elérése adott feladatok elvégzésé során, vagy legalább lehető

4

1.2 A dolgozat felépítése legjobb közelítése az optimálisnak az adott cél(ok) tekintetében, amik lehetnek felhasználási, illetve eredmény oldaliak is. A feladatok itt is különböző súlyúak, prioritásúak lehetnek, de persze más egyéb tényezők is befolyásolhatják a kapott eredményt, mivel az erőforrásainkhoz való hozzáférés módja is különbözhet. A vezeték nélküli hálózatokban, de általában véve más kommunikációs közegben is hasonlóan többféle erőforrással kell gazdálkodnunk, melyek mind kifejezhetők költségben, ahogy a rendelkezésre álló technológia és eszközök is. Vezeték nélküli erőforrás menedzsment témában alapvetően a következő négy erőforrással foglalkozunk [13]: i) sávszélesség, ii) adóteljesítmény, iii) antenna, iv) cellák-közötti erőforrás megosztás. A kommunikáció során, ha több adatot küldünk, mint amennyit fogadni képes a fogadó fél, vagy amit nem képes átengedni a közvetítő közeg, akkor azon adatok egy része el fog veszni. Viszont szeretnénk a lehető legtöbb adatott átvinni a legkevesebb erőforrás felhasználásával. A dolgozatban szeretném bemutatni azokat az ütemezési módszereket és problémákat, amelyek alkalmazhatók vezeték nélküli kommunikációban. Célom, hogy egy olyan rendszer kommunikációjára találjak megfelelő ütemezési megoldást, ami egy központi, és több alárendelt eszközből áll, mint például sok elszórt mérőállomás, amik adatokat küldenek a központi eszköznek, akár más közbeeső eszközön keresztül úgy, hogy a rendszer a lehető legkisebb legyen az energiafelhasználása.

1.2 A dolgozat felépítése Az Ütemezési módszerek fejezetben részletesebben foglalkozom ütemezési módszerekkel. Több módszert is bemutatok, főleg kommunikációs vagy feladat kiszolgálási szempontból, de természetesen ezek technológia független problémák. Tehát könnyen adaptálhatóak más területekre is, mint ahogy fenntebb már említettem, pénzügyi, processzor ütemezési, gyártási, logisztikai problémákra is. Egyes esetekben pedig ismert és széleskörűen használt megoldási algoritmusokat is részletezek. Egy WSN kommunikációs problémát és egy azt megoldani szándékozó új ütemezési eljárást mutatok be a Multihop Aperiodic Scheduling fejezetben, mely Hopfield Neurális Hálózatot használ az optimális ütemezés megközelítéséhez. Az ütemezési feladat, Multihop Aperiodic Scheduling (MAS), melyet a [23] cikkben részleteznek, egy egyre gyakrabban felmerülő kihívásra kíván megoldást találni, azaz hogyan tudnunk minél hatékonyabban adatokat gyűjteni egy nagyszámú szenzorhálózat csomópontjaiból. Az ilyen és ehhez hasonló hálózatok elengedhetetlenül szükségesek, amennyiben intelligens otthon vagy egy egészségügyi monitorozó rendszereket akarunk megvalósítani. A leírt ütemezési eljárást implementáltam MatLAB környezetben, és ebben szimulációkat végeztem, összehasonlítva más ütemezési algoritmusokkal. A Konklúziók és fejlesztési lehetőségek fejezetben pedig ennek eredményeit ismertetem.

5

2 Ütemezési módszerek Az ütemezés

(scheduling) egy döntéshozó folyamat, amit rendszeresen alkalmaznak

az ipari és szolgáltató szektorokban [18]. Az ütemezés során döntést kell hozni, hogyan rendeljük optimálisan a rendelkezésre álló erőforrásainkat az elvégzendő feladatokhoz, figyelembe véve egy vagy több célkitűzést. Ezen célok mögött mindig valamilyen szűkös erőforrás lehető legjobb kihasználása vagy minimális felhasználása áll. Az erőforrások sokfélék lehetnek: gépek, eszközök, infrastruktúra, természeti erőforrás, az infokommunikációban pedig a már a bevezetésben említett négy lényeges erőforrás: sávszélesség, adóteljesítmény, antenna és a cellák-közötti erőforrás megosztás. A feladatok igényei pedig az erőforrásokhoz kapcsolódóan a kapacitás kiosztása vagy hozzárendelése, melyek lehetnek: idő, hely, energia, munkafolyamat, számítási teljesítmény vagy frekvencia ablak. Az erőforrások és feladatok természeténél fogva különbözőképpen kell modellezünk a megoldandó problémákat. Sok elterjedt és bevált módszert alkalmazhatunk. Ezek technológia függetlenül megállják a helyüket, melyeket megfelelőség alapján választhatunk és használhatunk fel a konkrét esetekben. Ezt az ütemezési módszer kiválasztást úgy hozzuk meg, hogy figyelembe vesszük, milyen szempontok alapján szeretnénk kielégíteni a feladatok/felhasználók igényeit, hogy azzal valóban azt az optimális felhasználást tudjunk elérni vagy ésszerűen megközelíthessünk azt, ami megfelel kitűzött céljainknak. A megfelelő modell kiválasztása után különböző heurisztikák és algoritmusok állnak rendelkezésre, melyek nagyon körültekintő vizsgálatot igényelnek ahhoz, hogy a legjobb teljesítményt nyújtót alkalmazzuk az ütemezés megvalósításához. A következőekben bemutatok néhány kombinatorikai optimalizációs problémát és megoldási heurisztikákat egyes esetekben.

2.1 Knapsack probléma Ez az egyik első megfogalmazott módszer, ami talán a leggyakrabban van szükség a mindennapokban. Az elnevezés eredete a következőre probléma: egy hátizsákba szeretnénk bepakolni úgy, hogy minél nagyobb értéket tudjunk magunkkal vinni. Az elrakandó tárgyaknak van súlyuk (vagy méretük) és értékük, de a hátizsák miatt van egy súlykorlátunk is, amit nem szabad a zsák tartalmának meghaladnia. A kérdés tehát az, hogy hogyan tudjuk kiválogatni a legértékesebb tárgyakat? Alkalmazása akkor merül fel, amikor ki akarunk választani egy optimális korlátos súlyú

6

2.1 Knapsack probléma részhalmazt egy n elemű halmazból, mely elemek mind rendelkeznek wi súlyokkal, illetve pi profittal/értékkel, ahol (1 ≤ i ≤ n) és a súlyok összege nem léphet túl egy maximális pozitív W értéket. Formálisan a következőképpen fogalmazhatjuk meg: Példa:

Adottak a n, p1 , ..., pn , w1 , ..., wn , e´s W nemnegatív egészek

Feladat:

Találjuk meg az S ⊆ {1, ..., n}halmazt, hogy a X

pj

j∈S

összeg legyen maximális úgy, hogy teljesül a X

wj ≤ W

j∈S

feltétel. A Knapsack problémák komplexitása NP-teljes. Ezért ezt és az ehhez hasonló problémákat NP-nehéznek nevezzük, bár a Knapsack probléma ezek között a „legkönnyebb” [11].

2.1.1 Részleges Knapsack probléma A részleges Knapsack problémát egy kis módosítással kapjuk a fentiekből, azonos példára alkalmazva: Feladat:

Találjuk meg az x1 , ..., xn ∈ [0, 1]számokat, hogy a n X

xi p i

(2.1)

i=1

összeg maximális úgy, hogy teljesül a n X

x i wi ≤ W

i=1

feltétel. Ennek a problémának egy optimális megoldását Dantzig [4] adta meg, melyhez megfelelően kell rendezni az elemeket. 1. Tétel: Legyenek n, p1 , ..., pn , w1 , ..., wn , e´s W nemnegatív egészek a n X

wi ≥ W

i=1

és p2 pn p1 ≥ ≥ ... ≥ w1 w2 wn

7

2.1 Knapsack probléma feltételek mellett, ekkor legyen

k :=

min

j∈{1,...,n}

  j X  wi > W  .

(2.2)

i=1

Akkor a részeges Knapsack probléma adott példájának egy optimális megoldása a következőképpen definiálható: xj := 1, ha j = 1, ..., k − 1 xj :=

Pk−1

W−

j=1

wj

, ha j = k wk xj := 0, ha j = k + 1, ..., n

Ezzel az egyszerű algoritmussal a probléma megoldható O (n log n) időben. Ha kiválasztjuk a két megvalósítható megoldás a {1, ..., k − 1} és {k} közül a jobbikat, akkor az egy kéttényezős közelítési algoritmust jelent a Knapsack problémára O (n) időben. Továbbiakban használjuk a súlyozott medián keresést: Példa:

n természetes szám, z1 , ..., zn ∈ R, w1 , ..., wn ∈ R+ , és W szám 0 ≤ W ≤ P

j∈S

Feladat:

pj megszorítással.

Találjuk meg azt az S ⊆ {1, ..., n} részhalmazt, amire a X

pj

j∈S

kifejezés maximális a X

wj ≤ W

j∈S

megszorítás mellett. A zi = − wpii , i = 1, ..., n helyettesítés alkalmazásával a súlyozott medián probléma a ( 2.1) részleges Knapsack problémára egyszerűsödik, és ebben az esetben helyesen működik O (n) időben, szóval lineáris időben megoldható.

2.1.2 Integrál Knapsack probléma Mint fentebb említettem, a probléma NP-nehéz, de mivel nem erősen NP-nehéz, ezért van esélyünk arra, hogy egy pszeudo-polinomiális algoritmust találjunk [11]. Az 1. Tétel alapján, a

Pk

i=1 pi

egy felső korlát az Integrál Knapsack probléma optimális értékére.

Egyszerű rekurzív formulákra épülő dinamikus programozással kaphatunk egy algoritmust, ami megtalálja az optimális megoldást O (nP ) időben, ahol P =

Pn

i=1 pi ,

de ez

8

2.1 Knapsack probléma nem polinomiális korlát a bemenet méretében. A Knapsack problémának van egy teljesen polinomiális közelítési megoldása. Ahhoz, hogy csökkentsük a dinamikus programozású Knapsack algoritmus futási idejét, kézenfekvő ötlet a p1 , ..., pn számok elosztása h tényezővel: p¯i :=

 pi  h

,de ez pontatlan meg-

oldásokhoz vezethet. Ennek a közelítő eljárásnak a futási ideje O n2 1 -on belüli.

2.1.3 Többszörös választásos Knapsack probléma Sok egyéb variációja van még a Knapsack problémának a részleges(korlátos), integrál és teljesen polinomiális közelítő megoldáson kívül is. A többszörös választásos módszer egy olyan feladatot határoz meg, ahol az elemek az Nj , j = 1, . . . , m halmaz osztályokba tartoznak, és pontosan egy elemet kell kiválasztani minden egyes osztályból. Példa:

Adottak az n, m, p11 , ..., pmn , w11 , ..., wmn , e´s W nemnegatív egészek

Feladat:

Találjuk meg azt az S ⊆ {N1 , ..., Nm } részhalmazt amire következő 

arg max  S

m X X



pji xji 

j=1 i∈Nj

kifejezés értéke maximális úgy, hogy az alábbi feltételek teljesülnek: m X X

wji xji ≤ W

(2.3)

j=1 i∈Nj

és X

xji = 1,

(2.4)

i∈Nj

ahol xji = {0, 1}, ∀j = 1, . . . m-re. Ebben a problémában tehát fel kell tudni osztani a feladatokat olyan csoportokra, hogy azok értéke maximális legyen.

2.1.4 Többszörös Knapsack probléma A többszörös Knapsack annyiban különbözik, az előzőleg leírttól, hogy az elemosztályokhoz külön-külön más korlát tartozhat a súlyozott feltételhez. Formálisan ez a következőt jelenti: Példa:

Adottak az n, m, p11 , ..., pmn , w11 , ..., wmn , e´s W1 , ..., Wm nemnegatív egészek

9

2.2 Round-robin ütemezés Feladat:

Találjuk meg azt az S ⊆ {N1 , ..., Nm } részhalmazt amire következő 

arg max  S

m X X



pij xij 

i=1 j∈Ni

kifejezés értéke maximális úgy, hogy az alábbi feltételek teljesülnek: n X

wji xji ≤ Wj

(2.5)

i=1

és m X

xji = 1

j=1

minden ∀j = 1, . . . , m-re, ahol xji = {0, 1}, ∀i = 1, . . . , n-re. Mint láthatjuk a fenti feltételek közül az első biztosítja, hogy egy adott j osztályba tartozó elemek súlyozott értéke kisebb legyen, mint az adott osztályra vonatkozó Wj korlát. A második feltétel pedig, hasonlóan a ( 2.4) feltételhez biztosítja, hogy egy feladat csak egy eszközhöz legyen hozzárendelve. Vegyük észre, hogy Wi1 = Wi2 , ∀i1 , i2 = 1, . . . , n esetén a W =

Pn

i=1 Wi

korlát alkalmazásával a többszörös választásos Knapsack

problémát kapjuk, és így a ( 2.3) feltétel analóg lesz az ( 2.5) feltétellel.

2.2 Round-robin ütemezés A Round-robin (RR) kifejezés eredete egy módszer, amit régebben egy dokumentum vagy petíció aláírásánál alkalmaztak. Ahhoz, hogy ne lehessen felismerni, ki volt az első aláírója vagy vezetője a petíciónak, a neveiket hierarchia nélkül egy körön írták alá, mint ahogy egy kerek asztalnál ülő emberek közül sincs senki aki az asztalfőnél ülne. Ehhez hasonlóan az alap RR ütemező minden aktív felhasználó, fogyasztó számára egyenlő mértékben, prioritás mentesen ad hozzáférést az erőforrásokhoz, más szóval ciklikus ütemező. Egyenlő időszeleteket ad, megnézi minden felhasználó igényeit, és annak megfelelő erőforrással látja el, amennyiben a feladat teljesítése nem nyúlik túl a kapott időablakon, ellenkező esetben megszakítja a hozzáférést. Ez az egyik legegyszerűbben megvalósítható ütemező, minimális a számítási kapacitással. Hátránya, hogy nem tesz különbséget a különböző felhasználók különböző Quality of Service (QoS) feltételei, és a különböző átviteli igények között. Tehát megtörténhet, hogy egy adott felhasználó szám felett csak bizonyos szolgáltatások teljesíthetőek. Az optimalizálás célja a kommunikációban a maximális adatátvitel elérése. A probléma formális megfogalmazása: Példa:

Adottak az J = {J1 , . . . , Jn } feladatok, M = {M1 , . . . , Mm } eszközök és az X halmaz, mely az összes feladatoknak az eszközökhöz való hozzárendelése úgy, hogy minden feladatot csak egyszer végzünk el az eszközökön.

10

2.2 Round-robin ütemezés Feladat:

Találjuk meg azt az x ∈ X = n × m, xij = {0, 1}, i ∈ {1, . . . , n} , j ∈ {1, . . . , m} hozzárendelést, amire az arg max yij

n X m X

yij ρij

(2.6)

i=1 j=1

érték a legnagyobb, ha y = x, ahol y ∈ X , és ρij ≥ 0 az adatátviteli mennyiség és a n X m X

xij ≤ m

(2.7)

i=1 j=1

és m X

xij =

j=1

m X

x i2 j

(2.8)

j=1

feltételek teljesülnek. A ( 2.7) feltétel biztosítja, hogy hogy ne szolgáljunk ki több feladatot, mint ahány eszköz van, vagy vezetéknélküli kommunikáció esetében: ne allokáljunk egynél több adót egy csatornához. A ( 2.8) feltétel pedig azt hivatott biztosítani, hogy a feladatok/felhasználók egyenlő mértékben legyenek kiszolgálva. Kommunikáció megvalósítása során a ρij értékek az átviteli teljesítmény és a csatorna minőségének függvénye. Tehát a ρij = ρ (rij , γij ), ahol a rij az átviteli teljesítmény és γij a csatorna minősége Mj vivő Ji felhasználóhoz való hozzárendelése esetén. Ebben az esetben a kibővített probléma a következő módon fogalmazható meg, az átvitel maximalizálásának függvényében: arg max yij

n X m X

yij ρ (rij , γij )

(2.9)

i=1 j=1

és ekkor szükség van még két feltételre: n X m X

rij ≤ rTx

i=1 j=1

valamint m X j=1

rij =

m X

ri2 j ,

j=1

ahol rTx érték az összes átviteli teljesítmény összegét jelöli. Láthatjuk, hogy a ( 2.9) módosított függvény a ( 2.6) célfüggvénytől csak a kibővített paraméterezésben különbözik, viszont a feltételek már az átviteli teljesítmény szemszögéből jelentenek korlátozást, de az eredeti feladattal analóg módon, az összteljesítményre, illetve a teljesítmény egyenlő

11

2.3 P

roportional fair ütemezés

elosztására szorítanak.

2.3.

P

roportional fair ütemezés

A proportional fair (PF) ütemezésnek a megfogalmazása sokban hasonlít az előbbi RR ütemezéséhez. A PF ütemezés célja az, hogy a felhasználók között úgy ossza el az erőforrásokat, hogy egy „fair” felosztást kíván megvalósítani az elérhető erőforrásokból, mint a teljesítmény és csatorna hozzáférés. Például, ha van két felhasználónk, és az egyik nagyon közel van, a másik pedig távolabb, akkor a távolabbi felhasználó számára sokkal nagyobb energiát használ fel, ezért a felhasználók egyenlő energia mennyiséget kapnak. Ez a felosztás nem feltétlen fair olyan szempontból, hogy a távolabbi, nagyobb energia igényű felhasználók számára kevesebb energia jut, mint amennyire szüksége volna. A Round-robin ütemezőhöz hasonlóan a PF optimalizációs probléma megfogalmazható az adatátvitel összegének maximalizációjával: Példa:

M = {M1 , . . . , Mn } vivők, J = {J1 , . . . , Jk } felhasználók, és az X halmaz, mely az összes felhasználónak a vivőkhöz való hozzárendelése úgy, hogy minden felhasználót csak egy vivőhöz rendeljük hozzá.

Feladat:

Találjuk meg azt az x ∈ X = n × m, xij = {0, 1}, i ∈ {1, . . . , n} , j ∈ {1, . . . , m} hozzárendelést, amire a arg max yij

n X m X

yij ρ (rij , γij )

i=1 j=1

maximális értékű y = x, és ahol az alábbi feltételeknek kell teljesülnie: m n X X

rij ≤ rTx

i=1 j=1

és m X

rij =

j=1

m X

ri2 j ,

(2.10)

j=1

valamint n X m X

xij ≤ m

i=1 j=1

és m X

xij ρ (rij , γij ) > rimin , ∀Ji ∈ J − re.

(2.11)

j=1

12

2.4 Maximális átviteli ütemezés feltételeknek, ahol az rimin a Ji felhasználó vagy szolgáltatás minimálisan megkövetelt adatátviteli sebessége. A ( 2.10) összefüggéssel egyenlő mértékű hozzáférést biztosítunk az energiából a felhasználóknak, viszont a ( 2.11) alapján biztosítani kell a minimális adatátviteli sebességet a felhasználók számára, így a nagy energiaigényű kommunikáció számára is biztosítanunk kell egy minimális adatátvitelt. Tehát a PF ütemező megvalósít valamilyen „fair” hozzáférést az erőforrásokhoz, de figyelembe veszi a csatorna kapacitást is, de ezzel még „éheztetheti” a távol lévő felhasználót, illetve számos felhasználó számára ronthatja a felhasználói élményt.

2.4 Maximális átviteli ütemezés A maximális átviteli

(Maximal throughput) ütemezésnek is az a célja, hogy a lehető

legnagyobb adat folyjon át a rendszeren, de itt nem a felhasználók felől közelítjük meg a problémát, hanem a rendelkezésre álló erőforrás tekintetében. Tehát úgy akarjuk azt felosztani, hogy a lehető legnagyobb adatforgalmat generáljuk az ütemezés által. Azok a felhasználók előnyben részesülnek, akiknek jobb minőségű az adatátvitelük, és így azonos energiafelhasználással több adatot tudnak küldeni, ez által bizonyos szempontból ellentéte a RR ütemezésnek. Formálisan megfogalmazva: Példa:

M = {M1 , . . . , Mm } vivők, J = {J1 , . . . , Jn } felhasználók, és az X halmaz, mely az összes felhasználónak a vivőkhöz való hozzárendelése úgy, hogy minden felhasználót csak egy vivőhöz rendeljük hozzá.

Feladat:

Találjuk meg azt az x ∈ X = n × m, xij = {0, 1} ,i ∈ {1, . . . , n} , j ∈ {1, . . . , m} hozzárendelést, amire a arg max pij

n X m X

yij ρ (pij , γij )

(2.12)

i=1 j=1

maximális értékű y = x, és ahol teljesülnek az alábbi feltételek: n X m X

pij ≤ pTx

i=1 j=1 n X m X

xij ≤ n

i=1 j=1

és m X

xij ρ (pij , γij ) > pmin , ∀Ji ∈ J − re. i

j=1

A fenti feltételekkel az ütemező biztosítja a minimális adatátvitelt a felhasználók számára

13

2.5 Job Shop ütemezés az rimin alapján, és ezen felül pedig a maximális adatmennyiség elérése érdekében biztosít a felhasználóknak hozzáférést az erőforrásokhoz. A PF ütemezéshez hasonlóan a távolabb lévő vagy rosszabb átviteli minőségű csatornával rendelkező felhasználók nem kapnak feltétlen megfelelő hozzáférést.

2.5 Job Shop ütemezés A Job Shop ütemezés (JSS) egy nehezen megoldható optimalizációs feladat, ahol bizonyos időn belül adott eszköznek el kell végeznie szintén adott mennyiségű feladat műveleteit a lehető leghamarabb vagy legkisebb költséggel, ami számos féle lehet, akár az eszközökkel kapcsolatos is, mivel költségfüggvény határozza meg a egy adott feladat költségét az ütemezésben, nagy szabadsággal lehet meghatározni költségeket befolyásoló körülményeket, eseteket. Minden feladat több műveletből állhat, amiket adott eszközökön tudunk elvégezni. A műveleteket a megadott sorrendben kell elvégezni. Ezeknek költsége vagy ideje van, ezért nem mindegy, hogy a milyen sorrendben rendeljük a feladatok műveleteit az eszközökhöz. Ezen kívül minden egyes eszköz egyszerre csak egy műveletet képes elvégezni, és minden egyes feladat egyszerre csak egy eszközön végezhető. A teljes ütemezésnek akkor van vége, ha minden feladat minden műveletével végeztünk. Tehát azt az ütemezést keressük, amit a legrövidebb idő alatt tudunk elvégezni. A probléma formális leírása: Példa:

Adottak az M = {M1 , . . . , Mm } eszközök, J = {J1 , . . . , Jn } feladatok és az O = {Oik |i = 1, . . . , n, k = 1, . . . , µi } halmaz, mely a feladatok eszközökön elvégzendő műveletei, ahol µi a Ji feladat műveleteinek száma. Kik -val indexelhetjük az Oik műveletet az eszközökhöz. Legyen µ = maxi µi és tik a Ji feladat Oik műveletének műveletideje az Mj eszközön, ahol j = Kik . Az ütemezések halmaza X tartalmazza az összes lehetséges ütemezést, ami a feladatok műveleteinek az eszközökön végzett sorozata.

Feladat:

Találjuk meg azt az x ∈ X ütemezést, amire a C (x)idő-költség függvény a legkisebb.

Más szóval, találjuk meg a feladatok műveleteinek egy olyan x hozzárendelését az eszközökhöz, hogy a C (x) idő-költség függvény minimális legyen, tehát nem létezik olyan, y ∈ X hozzárendelés, ami rövidebb ideig tart, azaz C (y) < C (x). Könnyen adhatunk két egyszerű alsó becslést az optimális ütemezés idő-költség függvényének értékére. Az egyik, hogy az összes feladat elvégzése nem tarthat kevesebb ideig, mint a leghosszabb feladat elvégzése, azaz a teljes ütemezés legalább olyan hosszú ideig tart C (x) ≥ TJ = max Ji

X

tik

k

ez a korlát a maximális feladat hossza. A másik korlát abból következik, hogy az eszkö-

14

2.5 Job Shop ütemezés zöknek minden műveletet el kell végezniük, tehát C (x) ≥ TM = max Mj

X

tik ,

Kik =j

ez korlát a maximális eszköz terhelés. A JSS egy speciális esete a jól ismert utazó ügynök probléma (traveling salesman problem - TSP), ahol m = 1 az egyedüli „eszköz” az ügynök, és a feladatok a városoknak felelnek meg, amiket az ügynöknek meg kell látogatnia úgy, hogy minél hamarabb végezzen vele, vagy minél rövidebb út során tegye meg. Tehát ebben az esetben a megteendő út hossza vagy az idő jelenti a költséget.

2.5.1 Online algoritmus A JSS az egyik legismertebb probléma, amit online algoritmussal megoldhatunk. Az algoritmusnak döntenie kell az éppen számba vett feladatról, mielőtt a következős vizsgálná. Tehát a feladatokat sorban értékeli ki, és rendeli hozzá az eszközökhöz, nem ismerve a még következő feladatokat, tehát nincs is szüksége jövőbeli információhoz a döntéshez. Ennek ellentéte az offline algoritmus, ami során már az elején ismerjük az összes feladatot, és úgy kapjuk meg a kimenetet Mivel nem ismerünk minden bemenetet, az online algoritmus olyan kimenetet is adhat, ami utólag az összes feladatra vetítve nem optimális. Formálisan az online algoritmus az x kérések sorozatát kapja: x = x (1) , . . . , x (k) ∈ X , mely műveleteket a felmerülés pillanatában kell kiosztani. A x (t) kiszolgálásakor, nem ismerjük azokat a x (τ ) műveleteket, amikre τ > t. A műveletek kiszolgálása idő-költséghez kötött, és ennek az összköltségnek a minimalizálása a célunk. Az Alg online algoritmus hatékonyságát az az úgynevezett kompetitív analízissel vizsgáljuk, amiben az Opt optimális offline algoritmuséhoz hasonlíthatjuk a teljesítményét, ami az egész bemenet ismeretében hozza meg az optimális döntést. Jelöljék az Alg (x) és Opt (x)értékek az adott x = x (1) , . . . , x (k) bemeneti sorozatra az Alg és Opt algoritmusok eredményeként kapott idő-költségét értékét. Azt mondjuk, hogy az online algoritmus c − competit´ıv, ha létezik olyan b, amire igaz, hogy Alg (x) ≤ c · Opt (x) + b minden x sorozatra. A b konstansnak függetlennek kell lennie az x bemenettől. A kompetitív analízis egy erős mérték a legrosszabb teljesítményére esetére.

15

2.6 Total Tardiness

2.5.2 Johnson algoritmusa Ez az S.M. Johnson által leírt heurisztikus algoritmus [10], mely alkalmas egy két eszközből és n feladatból álló probléma optimális megoldására, így jól alkalmazható bizonyos Job shop ütemezés megvalósítására is. Algoritmus leírása: Adottak az M1 és M2 eszközök, J1 , . . . , Jn ∈ J feladatok. Minden Ji feladatnak van két, ti1 és ti2 hosszúságú művelete van, melyeket M1 , M2 eszközökön kell elvégezni. 1. lépés: Készítsünk három listát, A = {1, . . . , N } az összes művelet listája, L1 = {} és L2 = {} listák, melyek kezdetben üresek. 2. lépés: keressük meg a minimális t idejű műveletet, ha a minimum ideje tk1 -be tartozik, akkor tegyük a K műveletet az L1 = {}-be, ha tk2 -be tartozik, akkor tegyük az L2 = {}-be. 3. lépés: Ismételjük a 2. lépést, amíg A nem üres. 4. lépés: Fűzzük össze L1 -et és L2 -t, ez lesz az optimális sorozat. Az algoritmus csak két eszközre ad optimális megoldást, de mivel nagyon egyszerű és gyors, ezért alkalmazzák több eszközre is, ahol ezért m > 2. Ilyenkor az eszközök M = {M1 , . . . , Mm } halmazát két képzeletbeli csoportba osztjuk, és úgy hajtjuk végre az algoritmust, majd a csoportokat tovább osztjuk, és így alkalmazzuk a 2-3. lépéseket, amíg nem rendeltük a műveleteket egyenként az őket végrehajtó eszközökhöz, ezek után következik a 4. lépés. Végül pedig megkapjuk a kívánt eredményt, tehát az algoritmus akár több eszközre is képes optimális megoldást nyújtani.

2.6 Total Tardiness A Total Tardiness (TT) ütemezésben n feladatot kell rendezni, ahol minden Ji , i = 1, ..., n feladatnak van pi feldolgozási ideje, illetve di esedékességi időpontja. Adott σ ütemezési sorrend, amiben a Ji feladat befejezési időpontja Fi és Ti a késedelmessége (tardiness). Amennyiben egy ütemezésben Fi > di , akkor a feladat késedelmes és késedelmessége pozitív, egyébként 0. Az optimális ütemezés elérése érdekében ezen értékek minden Ji feladatra vonatkozó összegének minimalizálására törekszünk. A továbbiakban bemutatom a problémának az egy, illetve több azonos eszközre való megfogalmazását. 1.

Egy eszközön megvalósított TT ütemezés formális leírása a következőképpen adható meg:

Példa:

Adott a J = {J1 , . . . , Jn } feladatok halmaza. Minden Ji feladathoz tartozik egy Ti (σ) érték mely az alábbi módon számítható: 

Ti (σ) = max 0,

i X



pj − di  ,

j=1

16

2.6 Total Tardiness ahol di a Ji feladathoz tartozó esedékességi időpont, a pj , j = 1, ..., i értékek pedig az alkalmazott ütemezési sorrendben a Ji -t megelőző feladatok feldolgozási ideje. (A Ti (σ) érték az adott σ ütemezéstől függő költség, a Ji feladat késedelmessége a σ ütemezésben.) Feladat:

Találjuk meg azt a σ = (1, ..., n) ütemezési sorrendet, amivel minimalizáljuk a teljes ütemezésre vonatkozó T (σ) késedelmességet. Tehát a következő kifejezés értéke legyen minimális: n X

T (σ) = min

!

Ti (σ)

(2.13)

i=1

másképpen: n X

T (σ) = min

!

max (0, Fi (σ) − di ) ,

i=1

ahol Fi (σ) a Ji feladat befejezési ideje adott σ ütemezésben. Vagy minimalizáljuk az átlagos késedelmességet, ami ( 2.13)-ből adódik:  Pn

i=1 Ti (σ)

T (σ) = min 2.

n



.

Párhuzamos, több azonos eszközön való feldolgozásnál, a feladatok nincsenek eszközhöz kötve. Ebben az esetben a Ji feladatokat az M = {M1 , . . . , Mm } eszközhalmaz bármelyikéhez lehet rendelni. Ebben az esetben már két dolog felől is kell dönteni, egyik, hogy melyik eszközhöz rendelünk egy adott feladatot, illetve az adott eszközön milyen sorrendben ütemezzük a hozzárendelt feladatokat. Ebből eredő nehézsége miatt a parallel feldolgozású ütemezés rengeteg vizsgálat tárgya mind a mai napig. A probléma a következő módon fogalmazható meg:

Példa:

Adottak az M = {M1 , . . . , Mm } gépek/eszközök és a J = {J1 , . . . , Jn } feladatok halmaza. Minden Ji feladathoz tartozik egy Ti (σ) ütemezés függő érték, mely az alábbi módon számítható: Ti (σ) = max (0, Fi (σ) − di ) , ahol di a Ji feladathoz tartozó esedékességi időpont, a Fi (σ) értékek pedig az adott ütemezési sorrendben a Ji feladat befejezési ideje. Az Mk ∈ M eszközhöz tartozó feladatok késedelmessége: Γk (σ) =

X

Ti (σ)

i, Ji ∈Mk (σ)

Feladat:

Keressük azt a Σ = (σ1 , ..., σm ) ütemezést, ahol σk , k = (1, ..., m) az Mk

17

2.7 Total Weighted Tardiness eszközhöz tartozó feladatok ütemezési sorrendjét jelöli, és amire az ütemezés késedelmessége minimális lesz, azaz: m X

T (Σ) = min

!

Γk (Σ) .

k=1

Láthatjuk, hogy azzal, hogy választhatunk a rendelkezésre álló eszközök közül, jóval komplexebb feladatot kapunk, hiszen a teljes problémára vonatkozó Σ ütemezés az eszközökhöz tartozó σk részütemezésekből áll össze, amikben szereplő feladatok nem kötöttek, átkerülhetnek más eszközhöz is. A problémára [5] bebizonyította, hogy már m = 1 gép/eszköz számra NP-nehéz, azaz nem oldható meg polinom időben, következésképpen m > 1 esetben is az. Ezért szükségesek a megoldásukhoz megfelelő heurisztikát alkalmazni, amikre több megoldás is született [12], optimális megoldást először [2] adott.

2.7 Total Weighted Tardiness A TT ütemezéshez képest, a

Total Weighted Tardiness (TWT) ütemezés esetén a

feladatok súlyozottak, azaz minden Ji feladathoz létezik egy wi ≥ 1 súly. Ez annyiban módosítja a problémát, hogy a késedelmesség súlyozva van, így pl. két feladat késedelmessége nem azonos súlyú költséget jelent. A súlyok értéke lehet egész vagy valós szám is, ez függ a felmerülő probléma jellegétől, vagy a rendelkezésre álló megoldási módszerektől. Általában a súlyok meghatározása nehéz és időigényes, és ez alapjaiban határozza meg a kapott megoldás hatékonyságát [20]. A súlyok időnként arányosak lehetnek a feladatok feldolgozási idejével, hiszen azok jól reprezentálhatják azok értékét [1][21]. Abban az esetben, amikor minden feladatokhoz egységsúlyokat rendelünk, kapjuk a TT ütemezést. Ilyen szempontból a TWT a TT egy speciális esetének tekinthető. Ennek a két problémának a vizsgálata nagyon szorosan összefonódott az elmúlt évtizedekben [19]. Tehát a TWT a TT ütemezéssel analóg módon, súlyok alkalmazásával a következőképpen fogalmazható meg: 1.

Egy eszközön való feldolgozás esetén:

Példa:

Adott a J = {J1 , . . . , Jn } feladatok halmaza, és a hozzájuk tartozó {w1 , . . . , wn } súlyok. Minden Ji feladathoz számítható egy Ti (σ) érték az alábbi módon: 



Ti (σ) = max 0, wi 

i X



pj − di  ,

j=1

ahol di a Ji feladathoz tartozó esedékességi időpont, a pj , ∀j = 1, ..., i értékek pedig az alkalmazott ütemezési sorrendben a Ji -t megelőző feladatok feldolgozási ideje. (A Ti (σ) érték az adott σ ütemezéstől függő költség, a Ji feladat késedelmessége a σ ütemezésben.)

18

2.7 Total Weighted Tardiness Feladat:

Találjuk meg azt a σ = (1, ..., n) ütemezési sorrendet, amivel minimalizáljuk a teljes ütemezésre vonatkozó T (σ) késedelmességet. Tehát a következő kifejezés értéke legyen minimális: n X

T (σ) = min

!

Ti (σ)

(2.14)

i=1

másképpen: n X

T (σ) = min

!

max (0, wi (Fi (σ) − di )) ,

i=1

ahol Fi (σ) a Ji feladat befejezési ideje adott σ ütemezésben. Vagy minimalizáljuk az átlagos súlyozott késedelmességet:  Pn

i=1 Ti (σ)

T (σ) = min 2.



n

.

Párhuzamos feldolgozással, azonos eszközökre szintén a TT-vel analóg módon a következő probléma fogalmazható meg:

Példa:

Adottak az M = {M1 , . . . , Mm } gépek/eszközök és a J = {J1 , . . . , Jn } feladatok halmaza a hozzájuk tartozó {w1 , . . . , wn } súlyokkal. A Ji feladat késedelmessége a σ ütemezési sorrend esetén: Ti (σ) = max (0, wi (Fi (σ) − di )) , ahol di a Ji feladathoz tartozó esedékességi időpont, a Fi (σ) pedig az adott ütemezési sorrendben a Ji feladat befejezési ideje. Az Mk ∈ M eszközhöz tartozó feladatok késedelmessége minden k = (1, . . . , m) esetén: X

Γk (σ) =

Ti (σ)

i, Ji ∈Mk (σ)

Feladat:

Keressük azt a Σ = (σ1 , ..., σm ) ütemezést, ahol σk , k = (1, ..., m) az Mk eszközhöz tartozó feladatok ütemezési sorrendjét jelöli, és amire az ütemezés késedelmessége minimális lesz, azaz: T (Σ) = min

m X

!

Γk (Σ) .

k=1

2.7.1 Earliest Due Date Az

Earliest Due Date (EDD) heurisztika a feladatokat az esedékességi idejük

alapján rendezi sorba csökkenő sorrendben a legkorábbitól kezdve a legkésőbbi határidő-

19

2.7 Total Weighted Tardiness vel rendelkezővel bezárólag. Formálisan annyit jelent, hogy a Ji feladatok σ ütemezési sorrendjének teljesítenie kell a következő egyenlőtlenséget: d1 ≥ d2 ≥ . . . ≥ dn−1 ≥ dn . A feladatokat végrehajtása tehát ez szerinte történik. Parallel eszközökön az első m feladatot végezzük, majd amint egy befejeződik az egyik eszközön, akkor az m + 1-ik feladatot végezzük azon, és így tovább. Ez a módszer optimális eredményt ad egy eszközön megvalósított TT ütemezésre. De TWT ütemezés során, mivel nem veszi figyelembe a feladatok súlyozását, nem biztosít minden esetben optimális megoldást.

2.7.2 Weighted Shortest Processing Time A

Weighted Shortest Processing Time

(WSPT) a széleskörűen használt és

ismert Shortest Processing Time (SPT) [14] ütemezési heurisztika módosított változata. Az SPT heurisztika optimális megoldást ad egy gépen való ütemezésen, ha a cél az átlagos folyamat idő minimalizálása, olyan rendszerekben, amikben az új feladatok nem ismertek előre, hanem folyamatosan érkeznek. Az SPT a fentebb bemutatott EDD -vel analóg módon a következő rendezést valósítja meg az adott σ ütemezésben a Ji feladatok között: p1 ≤ p2 ≤ . . . ≤ pn−1 ≤ pn .

(2.15)

WSPT-ben ( 2.15)-hez képest a feladatokhoz tartozó wi súlyokkal korrigálva kialakított sorrend alapján történik az ütemezés: p1 p2 pn−1 pn ≤ ≤ ... ≤ ≤ . w1 w2 wn−1 wn

(2.16)

Tehát a súlyozás figyelembevételével úgy módosul a sorrend, hogy a nagyobb súlyú feladatok, amik akár tovább tartanak, mégis megelőzhetik a kisebb súllyal rendelkezőket.

2.7.3 Largest Weighted Process First Az

Largest Weighted Process First (LWPF) heurisztika azonos a [6] cikkben

bemutatottal. A feladatokat a hozzájuk rendelt súlyok alapján rendezi sorba úgy, hogy először a legnagyobb súlyú feladatokat végezzük el. Tehát a sorbarendezésnek az alábbi egyenlőtlenségnek kell megfelelnie a σ ütemezés feladataira: w1 ≥ w2 ≥ ... ≥ wn−1 ≥ wn . Így egy olyan ütemezést kapunk, ami egyszerűen csak a feladatok súlya alapján a legfontosabbakat veszi előre, de nem veszi figyelembe a feladatok határidejét. Ezzel látszólag

20

2.7 Total Weighted Tardiness nem veszi figyelembe a késedelmességet, de a szimulációk alapján jó eredményeket ad. Az ütemezés a Maximum Weight Opportunistic Scheduling heurisztikával megegyező elven működik, mely algoritmus bizonyítottan optimális áteresztőképesség szempontjából [16], emellett elfogadott és jelentős módszer is, mert képes stabilizálni a hálózatot [22].

21

3 Multihop Aperiodic Scheduling Ebben a fejezetben bemutatok egy létező kommunikáció modellt [23], melynek kiindulópontja egy WSN hálózat, amiben csomag továbbítási igények merülnek fel. A hálózat csomópontjaiban lévő eszközök generálhatnak és továbbküldhetnek hozzájuk beérkező csomagokat, melyeknek bizonyos időn meg kell érkezniük a gyűjtő eszközhöz. TDMA ütemezésre épül, kihasználja a Contention Based Protocol (CBP) előnyeit, ami így versenyképes ütemezési módszert ad. Célja, hogy a jelenleg széles körben alkalmazásban lévő MAC protokollokkal szemben úgy érjen el energia hatékony működést az adatcsomagok továbbítása során, hogy a késleltetés a lehető legkisebb legyen. Ezt úgy éri el, hogy optimalizálja az alapul szolgáló TDMA ütemezést az által, hogy minimalizálja a hálózat csomópontjainak/eszközeinek készenléti állapotba vagy ébrenlétbe való kapcsolásának számát. Az ütemezést optimalizálását kvadratikus alakra hozzák, melyet aztán egy Hopfield hálózattal oldanak meg polinom időben, és így valósítják meg az energia hatékony ütemezést.

3.1 Rendszermodell Mivel WSN hálózatról van szó, amiben több tucat vagy akár száz eszközből is állhat a teljes hálózat, az adatokat, amik lehetnek szenzor értékek vagy üzenetek, el kell juttatnia a bázisállomás(ok)hoz. Az eszközöknek van egy hierarchiája, amely alapján fogad adatokat bizonyos eszközöktől, illetve küldi az adatokat a saját „szülője felé”. Ahhoz, hogy az eszközök minél tovább működőképesek maradjanak, ki kell egyenlíteni az átmenő adatforgalmat közöttük, így ez a hierarchia megadott szempontok alapján módosulhat is a működés során, figyelembe véve az eszközök állapotát.

3.1.1 A WSN modell A hálózatnak N statikus csomópontból/eszközből áll, melyek képesek küldeni és fogadni is adatcsomagokat, és vannak olyan eszközök, amelyek más szenzor eszközök által küldött adatot is továbbítanak. Ez a hálózat egy G = (V, E) gráffal reprezentálható, ahol V = {v1 , v2 , . . . , vN , } az eszközök halmaza, az E pedig az élek halmaza. Két vi , vj ⊆ V csomópont között csak akkor van e = (vi , vj ) ∈ E él, ha vj csomópont a vi átviteli tartományán belül található, azaz amennyiben a vi által küldött csomagok elérnek hozzá.

22

3.1 Rendszermodell A G gráfhoz definiáltak egy AN ×N szomszédossági mátrixot: A = [Aij ]i,j=1,...,N , ahol Aij = 1, ha e = (vi , vj ) ∈ E. Ebből következik, hogy minden eszköz hatótávolsága azonos, és nincsenek veszteséges kapcsolatok, illetve a szomszédosság miatt az A mátrix szimmetrikus. Egy ilyen hálózatra mutat példát a 3.1. ábra. Ezen látható, hogy mindazon, számmal jelölt eszközök össze vannak kötve egymással, amik elérhető távolságra vannak. Például a 8-as r környezetében vannak a 3, 7, 9 e´s 10 számmal jelzett eszközök. Az A szomszédsági mátrixban ennek megfelelően helyezkednek el az 1-esek:              A=            

0 1 1 0 0 0 0 0 0 0 0

 

1 0 0 1 1 1 0 0 0 0 0    1 0 0 0 0 0 1 1 0 1 0   0 1 0 0 1 0 0 0 0 0 0  0 1 0 1 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1 0 1 1 0 0 1 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 1 1 0

                 

(3.1)

3.1. ábra. Egy WSN hálózat tagjainak szomszédossága

23

3.1 Rendszermodell Az adatfolyam modellezéséhez az A mátrix alapján definiálhatunk egy R irányítási fát, ami leírja, hogy az adatcsomagoknak, mely eszközökön keresztül kell eljutniuk a bázisállomásig, amennyiben nincsenek vele közvetlen szomszédságban az A mátrix alapján. A fa az elosztott Bellmann-Ford algoritmus által épül fel. A statikus irányítási fa reprezentálható az RN ×N irányítási mátrixszal: R = [Rij ]i,j=1,...,N ,

(3.2)

ahol Rij = 1, ha a vj csomópont a „szülője” a vi eszköznek (azaz, a vi a vj felé továbbítja az adatcsomagokat). A 3.2. ábra mutat példát az irányítási fa felépülésére. Hasonlóan a ( 3.1) mátrixhoz kaphatjuk meg a ( 3.2) elemeit.

3.2. ábra. Az eszközök hierarchiája Vezeték nélküli kommunikáció lévén el kell kerülni a csomagütközéseket illetve az interferenciát. Kétféle interferenciát különböztethetünk meg. Elsődleges interferenciának nevezzük, ha egy adott eszköz akkor küld csomagot, amikor egy másik eszköztől egyidejűleg fogadnia kéne. A másodlagos interferenciának azt mondjuk, ha egy másik, parallel kommunikáció zavarja a csomagküldést, ilyen esetben egy másik küldő és fogadó fél között ugyanabban az időben jön létre adatátvitel, mely a fizikai közelsége miatt zavarja a kommunikációt. Az itt bemutatott megközelítésben, a szerzők igyekeznek elkerülni az interferencia mindkét típusát a [7] cikkben bemutatott protokoll interferencia modellel. Ebben minden vi eszköznek fix d átviteli távolsága és D interferencia hatóköre van, az egyszerűség kedvéért, legyen d = D. A szomszédossági mátrix alapján definiálták a következő interferencia mátrixot: F = A2 + A − diag A2 + A . 



(3.3)

24

3.1 Rendszermodell Ez abból következik, hogy a kapcsolatok a következő módon vannak definiálva: F = [Fij ]i,j=1,...,N , ahol Fij = 1, ha a vj eszköz nem küldhet a vi eszközzel párhuzamosan. A 3.3. ábrán láthatjuk, hogy példánkban ez milyen párhuzamos kommunikációkat jelent. A ( 3.3) mátrixból látható, hogy az F mátrix átlója 0, mely azt reprezentálja, hogy egy csomópont nem zavarhatja saját magát, illetve a mátrix szimmetrikus, ami a szomszédossági mátrix szimmetrikusságából következik.

3.3. ábra. Párhuzamosan engedélyezett kommunikációk

3.1.2 Az ütemezés megfogalmazása A MAS ütemezés TT alapú, de a 2.6. fejezetben bemutatott nem-preeptív modellhez képest itt preemptív ütemezést valósítunk meg. Tehát a feladatok hosszabbak lehetnek mint az ütemezési ciklusok, és ezért megszakíthatóak is [3], viszont egyszerre csak egy gépen lehet dolgozni egy feladaton. Értelmezhető úgy is, hogy egy adott feladat p feldolgozási ideje egy egész szám, és értéke megegyezik az elvégzéséhez szükséges ütemezési ciklusokkal. Ennek eredményeképpen egy feladaton egymás után több gép is dolgozhat. Ennek a problémának a megfogalmazása a következő: Példa:

Adott m ∈ N darab eszköz és J1 , . . . , JN feladat és ezen feladatok p = {p1 , ..., pn } ∈ Nn

25

3.1 Rendszermodell mérete/feldolgozási ideje. Preemptív ütemezés lévén a feladatok megszabadítóak, és más eszközökhöz is allokálhatóak. A feladatokhoz tartoznak d = {d1 , ..., dN } ∈ Nn esedékességi időpontok, amin belül a feladatokat el kell végezni, illetve w = {w1 , ..., wn } ∈ Rn súlyok, amikre a wi ≥ 0, ∀i = 1, . . . , n feltétel teljesül. Ezen felül a feladatokhoz definiáljuk a késedelmességi értéket, mely egy adott σ ütemezés függvénye: Ti (σ) = max (0, Fi (σ) − di ) , ahol az Fi (σ) pedig az adott ütemezési sorrendben a Ji feladat befejezési ideje. Feladat:

Találjuk meg azt az optimális ütemezést, amiben a feladatok összesített késedelmessége minimális lesz: min

N X

Ti (σ)

(3.4)

i=1

Ahhoz, hogy ebben a TT problémában alkalmazható legyen a fenntebb vázolt WSN modell, az ütemezést más módon kell ábrázolnunk. Egy C bináris mátrix reprezentálja az ütemezést: C ∈ {0, 1}N ×L , ahol: • N a sorok száma, megegyezik a feladatok számával, • L az oszlopok pedig az időréseket/ütemezési ciklusokat reprezentálja, így ez jelöli az időrések számát. Az ütemezésnek ezen belül kell lezajlania. • A feladatok adott ütemezési ciklusban való feldolgozását az ütemezési mátrixban lévő 1-esek jelzik, tehát Cjk = 1, ha a vj eszköz csomagot küld a fogadó félnek a k időpontban, egyébként 0. Az egy oszlopban lévő 1-esek száma nem lehet nagyobb m-nél, mivel legfeljebb ennyi eszköz küldhet csomagot, illetve az i-ik sorban lévő 1-esek számának meg kell egyeznie pi -vel, azaz nem maradhat befejezetlen feladat. Ebben a reprezentációban a ( 3.4) probléma az alábbi módon fejezhető ki:

26

3.1 Rendszermodell Feladat:

Találjuk meg a következő optimális ütemezési mátrixot: Cotp := arg min C

N X

wi Ti (σ) ,

(3.5)

i=1

amely minimális késedelmességű, és teljesíti a következő L X

Ci,j = pi , ∀i = 1, . . . , N

(3.6)

Ci,j ≤ m, ∀j = 1, . . . , L

(3.7)

j=1

és N X i=1

feltételeket. A fenti ( 3.6) egyenlet biztosítja, hogy ne maradjon befejezetlen feladat, és a ( 3.7) feltétel pedig azt, hogy egy időben legfeljebb m feladat kiszolgálása történhet, azaz legfeljebb ennyi eszköz küldhessen csomagot a WSN modell felőli megközelítés szempontjából. ×L mátrix A cél tehát, hogy megközelítsük azt az optimális ütemezést, melyet a CN opt

reprezentál, ami garantálja az interferencia mentes adatátvitelt a modell szerkezetéből kifolyólag, illetve minimalizálja a tétlen felébredést, ezzel csökkentve az energiafogyasztást. Amennyiben az L túl nagy, felbontható az ütemezés több, K részre, ekkor így módosul az időrések összessége: L=

K X

L (l) ,

l=1

ahol az L (l) a l-ik ütemezési részprobléma. A fentiekből következően, egy vezeték nélküli szenzor hálózat definiálható a AN ×N szomszédossági, RN ×N irányítási, FN ×N interferencia és a CN ×L(l) ütemezési mátrixokkal. Ennek a hálózatnak a jó működéséhez több feltételt is megfogalmaztak, melyeket most bemutatok. Az első feltétel, hogy minimalizálható legyen a kommunikáció során a csomagütközések száma. Tehát minimális legyen mind az elsődleges, mind a másodlagos interferenciák száma. Ehhez természetesen fel kell használni az interferencia mátrixot. A minimalizálási feltétel a következőképpen néz ki:

L(l)

min C

X

C (k) FCT (k) ,

(3.8)

k=1

ahol, a C (k) az ütemezési mátrix k-ik oszlopát jelöli, a C (k) FCT (k) kvadratikus alak pedig az ütközések számát adja meg a k időpontban.

27

3.1 Rendszermodell Ahhoz, hogy minden csomag a megadott korlátokon belül megérkezzen a bázisállomáshoz, teljesülnie kell, hogy az L (l) ütemezés idején túl ne maradjon csomag a hálózatban. Legyen xj ≥ 0 a vj eszköz által generált csomagok száma, az általa továbbítandó csomagok száma pedig legyen sj ≥ xj . A továbbítandó csomagok száma minden eszközre kiszámolhatók. Formálisan, L(l)

∀vj ∈ V :

X

cj (k) = sj ,

(3.9)

k=1

azaz vj eszközre vonatkozóan a továbbítandó csomagok számának meg kell egyeznie az ütemezési részproblémában lévő küldések számával. Ahhoz, hogy valóban teljesüljön a ( 3.9) feltétel, a követező formában kell minimalizálni:

min C

N X



L(l)

sj −

X

j=1

2

cj (k) .

(3.10)

k=1

Tehát a továbbítandó csomagok és a továbbított csomagok számának különbségének minimálisnak, optimális esetben 0-nak kell lennie. Túl rövid L (l) esetén ( 3.10) eredménye nagyobb is lehet 0-nál, ekkor a következő L (l + 1) részütemezésbe kerül át a továbbítandó csomag. Továbbá ahhoz, hogy ne maradjon csomag a hálózatban, az összes küldött (és nem elveszett), illetve fogadott csomagok számának egyenlőnek kell lennie. Legyen z (k)egy puffer vektor, a k időpontban, a következő időpontban a vektor így számolható: z (k + 1) = z (k) + CT (k) R. Az r fogadott vektor, ami a fogadott csomagok számát reprezentálja, a fentiekből számolható: z (k + 1) − z (k) = CT (k) R. Ebből következik, hogy a k időpontban beérkező csomagok száma a vi eszközbe: N X

cj (k) R (j, i) .

(3.11)

j=1

Valamint a vi által küldött csomagok száma: L(l)

X

ci (k) .

(3.12)

k=1

A megfogalmazott feltétel, hogy a küldött és a fogadott csomagok számának meg kell egyeznie, a ( 3.11) és ( 3.12) összegzések felhasználásával a következő minimalizációval

28

3.2 Kvadratikus eszköztár érhető el:

min C

N X





xi + 

i=1

L(l) N XX





L(l)

cj (k) R (j, i) − 

X

k=1 j=1

2

ci (k) .

(3.13)

k=1

Ez azt jelenti, hogy a vi eszközökben minimalizáljuk a ott generált xi , valamint az oda érkezett csomagok és az elküldöttek különbségéből kapott értékek összegét. Az eddigi feltételek biztosították, hogy a eszközök által generált csomagok interferencia nélkül érjenek el a bázisállomáshoz, most a tétlen felébredések minimalizálásához szükséges feltételt mutatom be. ∀vi ∈ V, ∀f = 1, . . . , L (l)-re az eszközöknek csak akkor kell felébredniük, ha van továbbítandó csomagjuk, azaz: f X



N X

 k=1



cj (k) R (j, i) =

j=1

f X

ci (k)

k=1

minden k időpontban érvényes. Ez minimalizálva:

min C

N X



f X

 i=1

k=1



N X





cj (k) R (j, i) −

j=1

f X

2

ci (k)

(3.14)

k=1

A teljes célfüggvény a megkötésekkel együtt olyan ütemezési mátrixot ad, ami alapján • az ütemezés hossza L • minden adatcsomag eljut a bázisállomáshoz • az ütemezés elkerüli az interferenciát, és csomagütközéseket • az eszközök csak akkor ébrednek fel, ha van mit küldeniük. Tehát azt várjuk, hogy a ( 3.10), ( 3.8), ( 3.13), ( 3.14) költségfüggvények együttesen egy megvalósítható, energia hatékony C ütemezési mátrixot hoznak létre.

3.2 Kvadratikus eszköztár A megoldandó feladatok növekedésével az optimális megoldás kimerítő keresésének komp 

lexitása O 2N L , tehát erősen exponenciális idejű megoldást adna. Ezért szükség van egy polinom idejű approximációs eljárásra, hogy a módszer alkalmazható lehessen a gyakorlatban is. Ezért a következő alfejezetben az előzőleg kialakított optimalizálási feladatok kvadratikus alakra hozását mutatom be, hasonlóan ahogy a [6, 23, 15] cikkekben is megtalálhatjuk Legyen a WN ×N szimmetrikus mátrix és b1×N hosszú vektor. Keressük azt az y1×N vektort, ami minimalizálja a következő kvadratikus függvényt [17]: 1 f (y) = yT Wy + bT y, 2

(3.15)

29

3.2 Kvadratikus eszköztár az alábbiakhoz hasonló megszorítások mentén: Ay ≤ v, By = u A kvadratikus programozás egy gyakori heurisztikus algoritmusa a Hopfield Neurális Hálózat (HNN), melyet az alábbi állapotátmenet szabállyal írhatunk le: 

yi (k + 1) = sgn 

N X



Wi,j yj (k) − bi  , i = modN k.

(3.16)

j=1

Ezt állapotátmenet szabályt módosítjuk a következő helyettesítésekkel: d = −diag (W) , c = −W − diag (d) , W

ˆ = b − 1 d. b 2 Ezen módosításokkal ( 3.16) szabályból kapott 

yi (k + 1) = −sgn 

N X

 ci,j y(k)j − ˆ W bi  , i = modN k.

(3.17)

j=1

állapotátmeneti szabályt alkalmazzuk a továbbiakban. Hopfield megmutatta [9] cikkében, hogy a Ljapunov módszerrel a HNN a fixpontjához konvergál, ennek következtében a HNN minimalizálja a kvadratikus Ljapunov függvényt: L(y) := −

N X N N X 1 c 1X ci,j yi yj + ˆT y yiˆbi = − yT Wy W +b 2 i=1 j=1 2 i=1

(3.18)

Ezért a HNN polinom időben képes megoldani kvadratikus optimalizációs problémákat. Mivel ez a módszer nem biztosít globális szélsőértéket, hanem csak azt, hogy fixponthoz konvergál, ezért lehetnek jobb megoldások is, mint amit találunk. Ezért szükséges találnunk olyan heurisztikákat, amik segítségével a HNN úgy paraméterezhető, hogy azzal, lehetőleg globális minimumot találjunk, ezzel megtalálva a lehető legjobb megoldást.

3.2.1 Az ütemezés QP transzformációja Ahhoz, hogy az előbb részletezett megoldást alkalmazni tudjuk, az ütemezés kvadratikus alakba hozását kell megvalósítani. Először egy vektort képzünk a C ütemezési mátrixból, oly módon, hogy oszloponként kiolvassuk egy oszlopvektorba:

30

3.2 Kvadratikus eszköztár

C1,1

C1,2

···

C1,L



  C2,1  C= .  .. 

C2,2 .. .

··· .. .

C2,L .. .

   →  

CN,1 CN,2 · · ·

CN,L



y = (C1,1 , C2,1 , . . . , CN,1 , C1,2 , . . . , CN,2 , . . . , C1,L , . . . , CN,L )T .

(3.19)

Továbbá, az ütemezés átalakításához a célfüggvényét ( 3.5) is át kell alakítani, melyben először kifejtve a késedelmességet a következőt kapjuk: min C

N X







wi max 0, arg max {Ci,j = 1} − dj j

i=1

.

(3.20)

Láthatjuk, hogy a mátrix reprezentáció miatt, szükséges megtalálnunk az adott j sor utolsó 1-esét, ami a feladat végét jelenti, és ebből számoljuk a késedelmességet. Az ütemezés ciklikussága miatt ez ekvivalens a következővel:

min C

N X



wi 

L X



Ci,j  .

(3.21)

j=di +1

i=1

A célfüggvénynek tehát (3.21)-ből a következőt kapjuk: Cotp := arg min C

L N X X

2 wi Ci,j .

(3.22)

i=1 j=di +1

Most vegyük a két ( 3.6) és ( 3.7) feltételeket és a célfüggvényhez hasonlóan a fenti lépésekkel azonos módon alakítsuk át őket. A ( 3.6) így a következő lesz:

∀i :

L X

Ci,j = pi ,

(3.23)

j=1

ebből:

min C

N X



L X

 i=1



2

Ci,j  − pi  .

(3.24)

j=1

Ennek a feltételnek a szerepe, hogy ne dolgozzunk egy feladaton többet, mint amennyit kell, tehát összeszámoljuk a C adott sorában lévő 1-esek számát, és a hozzá tartozó feldolgozási idővel képzett különbségének négyzetösszegét minimalizáljuk. Ezzel persze büntetjük azt s, ha egy adott feladatot nem fejezünk be.

31

3.2 Kvadratikus eszköztár Hasonlóan a ( 3.7) feltétel esetében a következő átalakítást végezzük el: ∀j :

N X

Ci,j ≤ m,

(3.25)

i=1

amiből: min C

L X

N X

j=1

i=1

!2

!

−m

Ci,j

.

(3.26)

Tehát az oszloponkénti 1-esek számának és a rendszer kapacitás különbségének négyzetének minimalizálásával szeretnénk elérni, hogy lehetőleg maximális kapacitás kihasználtsággal működjön a rendszerünk, de azt is, hogy ne ütemezzünk a kapacitáson felül. Most, hogy az optimalizálandó függvény, és mindkét feltétel rendelkezésünkre áll mátrixos alakban, ezek összeillesztésével a teljes, optimalizálandó célfüggvényt kapjuk:

min E(C) = arg min α C

+γ

L N X X

2 wi Ci,j +β

i=1 j=di +1

L X

N X

j=1

i=1



L X

 i=1



2

Ci,j  − pi  +

j=1

!2

!

Ci,j

N X

−m

.

(3.27)

Az α, β, γ értékek a célfüggvény tagjainak súlyozására szolgálnak. A paraméterekre vonatkozó helyes relatív beállítás rendkívül fontos a megfelelő eredmény érdekében. Ehhez kapcsolatos vizsgálatokat és szimulációs eredményeket még a későbbiekben tárgyalni fogok. Most pedig kvadratikus alakba kell hoznunk a (3.27) célfüggvényt, annak érdekében, hogy alkalmazni tudjuk rajta a HNN módszert. A (3.22) leképezése tehát a következő: L N X X

1 2 wi Ci,j = − yT WA y − bTA y, 2 i=1 j=d +1

(3.28)

i

ennek a megoldása pedig: bA = 0N L×1 , 

D1



WA = −2   0

0

···

D2 · · ·

0

0

···

0

 

0  

DN

ahol Dj =

0dj ×dj

0dj ×(L−dj )

0(L−dj )×dj

wj · I(L−dj )×(L−dj )

!

∈ RL×L .

32

3.2 Kvadratikus eszköztár A fenti mátrixban nehézséget jelent, hogy csakis főátlós elemeket tartalmaz. Azonban a következő átalakítással javítható, mivel a Cjl pozitív, 0 vagy 1 ezért elhagyható a (3.28) egyenlet bal oldalán a négyzetre emelés. N X L X

1 = − yT WA y − bTA y, 2

wi Cij

i=1 j=di

(3.29)

Ennek megoldása pedig:





bA = 0p1 ×1 , w1L−p1 ×1 , 0K2 ×1 , w2L−p2 ×1 . . . 0pJ ×1 , wNL−pJ ×1 ,

(3.30)

WA = 0N L×N L

(3.31)

A (3.24) feltétel kvadratikus alakba való leképezése a következő: N X



2



L X

1 Ci,j  − pi  = − yT WB y − bTB y, 2 j=1

(3.32)

 i=1

ennek megoldása pedig: bB = 2



X11×L



X21×L

1L×L

   WB = −2   

0 .. . 0

···

XJ1×L



···

0



1L×L · · · .. .. . .

0 .. .

     

0

0

···

(3.33)

(3.34)

1L×L

A második, (3.26) feltétel leképezése kvadratikus alakba: L X

N X

j=1

i=1

!2

!

Ci,j

−m

1 = − yT WC y − bTC y 2

(3.35)

Vegyük észre, hogy ez az egyenlőség nem feltétlen lesz releváns az ütemezési mátrix utolsó oszlopaira, mivel az ütemezés végén ritkán marad pont annyi feldolgozandó feladat, hogy minden feldolgozási kapacitás ki legyen használva, azaz minden bizonnyal

PN

i=1 Ci,j

< m.

Ezért nem szabad, hogy ezt a kapacitás kihasználatlanságot költségként számítsuk. Az

33

3.2 Kvadratikus eszköztár ütemezés teljes hossza a következő módon számolható: ˜= L

&P

N i

pi

'

,

m

(3.36)

Ez egy alsó közelítés, ha azt vesszük, hogy minden ütemezési ciklusban maximális kapa˜ citás kihasználtsággal dolgozzuk fel a feladatokat, akkor az ütemezésnek minimálisan L hosszúnak kell lennie. Másik becslésünk az alsó korlátra a leghosszabb feladatot feldolgozási ideje, mivel egy feladatot legfeljebb egy eszköz szolgálhat ki, ezért hogy az egész feladatot elvégezzük, legalább a feladat hosszával megegyező hosszúságú ütemezésre van szükség. Harmadik alsó korlát pedig a legkésőbbi esedékességi időpont. Ezekből számítva az ütemezés teljes hossza: 



˜ max pi , max di . L = max L, i

(3.37)

i

A teljes kapacitás kihasználtságú ütemezési ciklusok száma a következő: 



M = max 1, max pi − L + 1 .

(3.38)

i

Figyelembe véve (3.38)-t a (3.35) feltétel a következőképpen módosul: M X

N X

j=1

i=1

!2

!

Ci,j

−m

1 = − yT WC y − bTC y 2

(3.39)

Ennek az egyenletnek a megoldása pedig a következő: h

i

bC = VM ×1 , 0(L−M )×1 , VM ×1 , 0(L−M )×1 , . . . , VM ×1 , 0(L−M )×1 ,



D



··· .. .

D .. .

   ,  

D D ···

D

D D ···

  D D  WC = −2  . ..  .. . 

(3.40)

(3.41)

ahol D=

IM ×M

0(L−M )×1

0(L−M )×1 I(L−M )×(L−M )

!

.

Összesítve a (3.29),(3.32) és (3.39) egyenletek jobb oldalán szereplő mátrixokat és vektorokat kapjuk a következőket: W = αWA + βWB + γWC ∈ RN L×N L

34

3.3 HNN paraméter becslés és b = αbA + βbB + γbC ∈ RN L×1 . Az előzőleg meghatározott példa olyan HNN-re igaz, ahol a neuronok kimenete 0 . . . 1, ezt át kell transzformálni, ahhoz hogy a konvergencia és a stabilitás igaz legyen a −1, +1 tartományra. Ehhez a meglévő min yT Wy − 2bT y y

kvadratikus alak helyett az alábbit írjuk fel: c y − 2b ˆT y min y ˆT Wˆ ˆ ˆ y

Ahol az y ˆ = 2 (y − 1) Amennyiben az eredeti alakba szeretnénk ezt behelyettesíteni: y ˆ+1 y= kapjuk a következőt: 2 !

min ˆ y

y ˆT + 1 c W 2

y ˆT + 1 2

!

ˆT

− 2b

y ˆT + 1 2

!

ˆ és 1 W konstans tagokat elhagyva (amely a minimalizációt Ezt transzformálva illetve a b 4 nem befolyásolja) az alábbi eredményt kapjuk: 1c 1 1 min y ˆ Wˆ y−2 − W+ b y ˆ ˆ y 4 4 2 T





Ebből következik, hogy a transzformáció után a súly-mátrix és bias vektor az alábbi lesz: c = 1W W 4

és ˆ = − 1 WN L×N L + 1 b. b 4 2 Az így kapott formulán már alkalmazhatjuk a HNN polinom idejű közelítő megoldását az optimális ütemezésre.

3.3 HNN paraméter becslés Mint már említettem, rendkívül fontos a (3.27) célfüggvény megfelelő paraméterezése, mert ezzel tudjuk befolyásolni azt, hogy milyen súlya legyen a szükséges megkötéseknek és az optimalizációs függvénynek az ütemezés során. A [6][23] cikkek szerzői által heurisztikusan megadott α, β, γ paraméterek vizsgálatával foglalkoztam, kimerítő kere-

35

3.3 HNN paraméter becslés séssel egy relatíve széles tartományban változtattam egymástól függetlenül, külön-külön mindhárom paramétert, hogy meg tudjuk vizsgálni, hogy milyen hatással vannak az eredményre a célfüggvény tagjainak különböző súlyozása. Ennek további vizsgálatával sokkal nagyobb volumenű mintán, javítható lehetne a paraméterekre vonatkozó heurisztika, és ezzel jobb eredményt érhetnénk el az ütemezés teljesítményében. A feltevésünk az, hogy az α paraméter értékének kisebbnek kell lennie, mint a másik kettőnek, a β, γ paraméterek viszont egyenlő súllyal rendelkezzenek.

250 eredmény hiba

HNN eredménye

200

150

100

50

0

10

20

30

40

50

α értéke

60

70

80

90

100

3.4. ábra. Az α paraméter változtatásának hatása 5 véletlenszerű esetben A szimulációkat saját laptopomon végeztem 64 bites MatLab R2010a verziójával. A gépben kétmagos Intel Core2 Duo P7350, 2.00GHz teljesítményű processzor van és 4 GB RAM memóriával rendelkezik. Minden egyes számítás során véletlenszerű bemenetet adtam. A paraméter értékeit nem homogén eloszlásban változtattam. A kiinduló érték mindhárom paraméter esetében a 10-10 volt tehát amikor az egyik paraméter értéke változott, addig a többi fixen 10 maradt. Mivel nagyobb a relevanciája az azonos nagyságrendű beállításnak, ezért 10 körüli értékek sűrűbben változnak, mindhárom paraméter esetében. Összesen több, mint 1000 különböző pontban vizsgáltam mindhárom paramétert. Öt, különböző paraméterekkel indított iterációt futtattam, és minden iterációban pontonként 50 ciklus átlagát jelenítettem meg. A [6][23] cikkekben a modell többnyire jobb eredményt adott más protokollokkal szemben. Az tapasztalatokkal alátámasztott paraméter beállítással, akár még jobb átlagos eredményt is el lehetne érni. A 3.4. ábrán az α paraméter változásának hatása látható. Az y tengelyen az ütemezés hosszát láthatjuk. A C mátrix oszlopai az ütemezésen belül az időszeletek súlyozott összegét jelöli k időpontban. A grafikonon öt iteráció eredménye látható, melyek öt különböző, véletlenszerű bemenetet takarnak. Az ütemezésekben 20 feladatot kellett

36

3.4 Smart Hopfield Neural Network

250 eredmény hiba

HNN eredménye

200

150

100

50

0

10

20

30

40

50

β értéke

60

70

80

90

100

3.5. ábra. A β paraméter változtatásának hatása 5 véletlenszerű esetben. kiszolgálni. A felső görbék a szimuláció eredményét jelölik, az alsó görbék pedig a hibát. Látható, hogy az α növelésével csökken a szimulációban a számítás értéke, viszont a hiba növekszik, ami végül egy 50 alatti értékhez konvergál. A 3.5. ábrán megfigyelhetjük a β paraméter változásának hatását az eredményre. Az α és γ paraméterek 10 értékéhez képest az ahhoz közeli tartományban láthatunk érdekes változást a kimenetre vonatkozóan. Mely egy nagy meredekségű növekedést mutat 20 feletti értékig, majd lassan csökken a kimenet értéke. A hiba értéke viszont az α paraméternél megfigyelttől eltérően csökken a β esetében annak súlyának növelése során. A 3.6. ábrán a harmadik γ paraméter változásának hatása látható. Az ábrán látható, hogy bizonyos iterációk görbéje a ∼ 20 körüli értéknél javulást mutat, ez nagyon érdekes eredmény, melynek hátterében egyenlőre nem tudjuk, hogy mi áll. Ezen szimulációkhoz tartozó hibák ellentétesen változnak a többi iterációban szereplőkhöz. Érdemes lesz a jövőben további szimulációkat folytatni ennek a paraméternek a vizsgálatára.

3.4 Smart Hopfield Neural Network A

Smart Hopfield Neural Network (sHNN) egy továbbfejlesztett változata a HNN

eljárásnak. Mivel a Ljapunov függvény minimalizálása során könnyen tud lokális minimumba jutni, ahogy ezt már fenntebb említettem, ezért a keresést az LWPF algoritmus kimenetén indítjuk el. Így a HNN eljárást az ütemezés megvalósítására már előre feldolgozott ütemezési mátrixon valósítjuk meg, melynek elején a legnagyobb súlyozású feladatok lesznek. Az a sejtésünk, hogy azzal, hogy egy rendezett ütemezésből indulunk

37

3.5 Perturbed Smart Hopfield Neural Network

300 eredmény hiba

HNN eredménye

250

200

150

100

50

0

10

20

30

40

50

γ értéke

60

70

80

90

100

3.6. ábra. A γ paraméter változtatásának hatása 5 véletlenszerű esetben. ki, akkor a HNN abból nagyobb valószínűséggel fog az optimálishoz közelebbi eredményt adni, legalábbis nem lesz rosszabb az eredménye, mint amilyet az LWPF metódussal kapunk. A kapott eredmény viszont ezt nem igazolta. A 3.7. ábrán jól látszik, hogy az LWPF-hez képest a HNN hasonlóan, nagyobb méretű probléma esetén pedig enyhén rosszabban teljesített. A [6] cikkben bemutatott szimulációkban a HNN eljárás enyhén jobb eredményeket adott mint az olyan hagyományosnak mondható eljárások, mint az LWPF, EDD, WSPT. Bár kisebb méretű problémákon igazolni tudtam az eredményeket. Sajnos korlátozott számítási kapacitásaim miatt nem tudtam olyan kimerítő keresést végezni az sHNN és psHNN algoritmusokkal, azaz 500 véletlenszerűen generált probléma helyett a szimulációs eredményeimet mindössze 3 véletlenszerűen generált probléma legjobb eredményének átlagából számítottam minden egyes probléma méretre. Ebből kiindulva viszont nincs meglepő különbség a két eredmény között. A HNN eredményéhez képest az sHNN jóval rosszabban teljesített. Tehát nem kaptam jobb eredményt a fenti módszerrel, mely sajnos így nem támasztotta alá azt a várakozásunkat, hogy a módszerrel segíteni tudjuk a HNN algoritmus eredményességét.

3.5 Perturbed Smart Hopfield Neural Network Ebben a alfejezetben bemutatott ütemezés az sHNN módosított változata. A

Per-

turbed Smart Hopfield Neural Network (psHNN) eljárással szeretnénk az sHNN eredményességét növelni.

38

3.5 Perturbed Smart Hopfield Neural Network

HNN, sHNN, LWPF eredménye

2500

2000

1500 sHNN LWPF HNN 1000

500

0

10

20

30

40

50

60

70

Feladatok száma

3.7. ábra. Az LWPF, HNN és sHNN ütemezések eredménye

3.5.1 Perturbáció heurisztika Az LWPF kimeneteként kapott ütemezést permutálom, vagyis a C ütemezési mátrix oszlopait véletlenszerűen felcserélem. Ennek célja, hogy az így módosított ütemezési mátrixban megjelenjenek egyértelműen rossz ütemezések, amiket a HNN eljárás javít. Feltételezésünk, hogy ezzel szintén elkerülhető, hogy az eljárás egy lokális optimumot találjon. A szimulációk során azt vizsgáltam, hogy mekkora arányú perturbációt kell végezni ahhoz, hogy amennyiben eredményes ez a módszer, akkor a lehető legjobb eredményt adja. Ezért az ütemezés méretével arányosan különböző mennyiségű perturbációt végeztem el. Ennek eredménye látható a 3.8. ábrán. A szimulációban 5 különböző próbát csináltam. A perturbációkat az ütemezés hosszához igazítottam, ami azt jelenti, hogy az ütemezés hosszához képest hány véletlenszerű perturbációt végzünk. Ezek szerint az 5 próbában az ütemezési mátrix méretéhez képest, ami legyen N összesen N/5 , N/4, N/3, N/2, illetve N/1 permutációt végeztem. Ezen permutációk véletlenszerűek, tehát nincs kizárva, hogy egy oszlopot többször is felcserélünk egy valamely másik oszloppal. A psHNN stabilan jobb eredményt adott az sHNN-nél. Érdekes, hogy amennyiben az ütemezési mátrix méretével megegyező permutációt végeztem, akkor is jobb eredményt kaptam az sHNN-nél. De minél kisebb arányú volt a permutációk száma, annál nagyobb javulást lehetett elérni. Összességében tehát a psHNN ígéretes módszernek tűnik, viszont további eredmények várhatók megfelelő HNN paraméter heurisztikáktól, amikkel modell specifikusan lehetne javítani a módszer eredményességén.

39

3.5 Perturbed Smart Hopfield Neural Network

1800

psHNN perturbációk eredménye

1600 LWPF EDD sHNN 5 psHNN 4 psHNN 3 psHNN 2 psHNN 1 psHNN

1400 1200 1000 800 600 400 200 0

10

20

30

40

50

60

70

Feladatok száma

3.8. ábra. Különböző perturbációk eredménye

40

4 Konklúziók és fejlesztési lehetőségek A kapott eredményeim alapján nem tudtam alátámasztani, hogy a HNN eljárással megvalósított ütemezés általános esetben jobb eredményt adhat egy olyan parallel feldolgozású preemptív ütemezési problémára, mint amelyet a Multihop Aperiodic Scheduling fejezetben bemutattam. Sikerült igazolni viszont, hogy az sHNN és psHNN algoritmusok tartósan jobb eredményt adnak, mint a HNN algoritmus, ahogy ez a 3.7. és 3.8. ábrákból következik. Kisebb probléma méreteknél viszont a vizsgált módszerek jobbnak viszonyultak a hagyományos, LWPF, EDD, WSPT módszereknél. Az eredményeim gyengéi közé tartozik, hogy nem volt lehetőségem nagyobb mennyiségű szimulációt végezni, hogy azok eredményét felhasználhassam a minél pontosabb paraméterbecsléshez, illetve perturbáció heurisztikához. A 4.1. ábrán átható eredmény mutatja, hogy a kitapasztalt heurisztikákkal a psHNN algoritmus jelentős javulást jelent az sHNN módszerhez képest. Viszont az ábrán látható két másik módszer eredménye ezeknél is jobb. Ennek ellenére kisebb probléma méret esetén, ahol N < ∼ 35 a psHNN stabilan jobb eredményt mutat, így ilyen esetekben érdemes alkalmazni.

2000 psHNN sHNN LWPF EDD

1800

psHNN,sHNN eredménye

1600 1400 1200 1000 800 600 400 200 0

10

20

30

40

50

60

70

Feladatok száma

4.1. ábra. A psHNN, sHNN, LWPF, valamint az EDDalgoritmusok eredménye. A HNN algoritmusok közül a legegyszerűbb implementációt alkalmaztam, ennél jobb eredményt adhatnak fejlettebb megvalósítások, mint pl. folytonos HNN [8] vagy adaptív

41

Konklúziók és fejlesztési lehetőségek HNN [25]. Mélyebb vizsgálatokat igényelnek még ezen felül a modellspecifikus paraméterek, tehát az α, β, γ megfelelő beállítása. Ezek hatása jelentősen befolyásolhatja az kapott ütemezést, hiszen az általuk szabályozott megszorítások a célfüggvényben hatással vannak a kialakított ütemezés költségére. További vizsgálatok tárgya lehet még olyan módosítása az algoritmusnak, mellyel lehetővé válna az ütemezés során felmerülő újabb feladat beillesztésére, azaz az ütemezés ezzel „élővé” válhatna. Preemptív módszer lévén, erre bármelyik ütemezési ciklusban lehetőség volna. A dolgozatban leírt modell, bár WSN alapú, technológia független, így az alkalmazott ütemezési eljárás nem csak WSN környezetben implementálható. A bevezetésben említett területek bármelyikében találhatunk olyan problémát, illetve igazíthatjuk a modellt, hogy a módszerünk alkalmazható legyen. Tehát a feladatok lehetnek akár gyártási feladatok és az eszközök az ezeket elvégző gépek, az ütemezés költsége pedig a termék árával súlyozott leszállítási késedelme. Más példában a feladatok lehetnek befektetési termékek, az eszközök pedig a rendelkezésre álló forrásokat, tehát pénzt vagy egyéb forgóeszköz állományt reprezentálnak. A költség vagy haszon pedig a befektetésen elért valós hozam az maximálisan elérhetőhöz képest. A módszer legfőbb hátránya a HNN nagy számítási igénye. Bár egyre több eszközben nem jelent gondot a megfelelő számítási kapacitás megléte, ezt a korlátozó tényezőt szükséges figyelembe venni. A hagyományos ütemezési módszerek és a bemutatott eljárás között ebből a szempontból akár két nagyságrendű különbség is lehet. Viszont épp ezért sokmagos GPU vagy kiloprocesszor tömbök ideális hardveres hátteret jelentenek, amiken alkalmazva ez a hátránya jelentősen csökkenhet. Ennek jövőbeli vizsgálata, az ilyen eszközök egyre nagyobb elterjedése miatt a módszer versenyképességének növekedését hozhatja magával.

42

5 Összefoglalás Dolgozatomban bemutattam, hogy az erőforrás menedzsment milyen széleskörűen vizsgált kérdés, mellyel nem csak informatikai vagy ipari, de gazdasági és humán területeken is foglalkoznak. Ezen belül az ütemezési módszerek alkalmazása önmagukban is külön tudományterületet határoznak meg. Azonos matematikai eszközökkel leírtam a legfontosabb ütemezési módszereket, érintve azon problémákat, amik modellezhetők általuk, kiemelve a köztük lévő különbségeket. Bemutattam egy új WSN problémám alapuló ütemezési módszert, mely egy Hopfield neurális hálózattal megoldható kvadratikus optimalizációs feladat jelent. Ezzel az NP-nehéz problémára kaphatunk egy polinom idejű megoldást. Vizsgáltam a HNN irányított alkalmazását, melyet smart HNN-nek hívnak illetve ennek egy módosítását a perturbed sHNN-t, mellyel jobb eredményeket értem el. A bemutatott módszer könnyen adaptálható más technológiai környezetbe, mert a WSN független modell egyaránt szűkíthető és bővíthető. A kapott eredmények pedig egyértelműen jobbak kis és közepes méretű ütemezési problémákra, mint más bevett eljárások. Hátránya viszont a nagy számítási kapacitás igénye, mely csökkenthető pontosított paraméter heurisztikák alkalmazásával, illetve GPU vagy kiloprocesszor tömbökön való implementálásával.

43

Köszönetnyilvánítás Ezúton szeretném megköszönni az áldozatos segítséget, és a folyamatos biztatást konzulenseimnek Dr. Oláh Andrásnak és Tornai Kálmánnak. Mindenekelőtt pedig hálával tartozom szüleimnek és testvéreimnek, akik támogatásával ezt a szakot elvégezhettem.

44

Irodalomjegyzék [1] E. M. Arkin and R. O. Roundy, „Weighted-tardiness scheduling on parallel machines with proportional weights,” Oper. Res., vol. 39, no. 1, pp. 64–81, Feb. 1991. [Online]. Available: http://dx.doi.org/10.1287/opre.39.1.64 18 [2] M. Azizoglu and O. Kirca, „Tardiness minimization on parallel machines,” International Journal of Production Economics, vol. 55, no. 2, pp. 163 – 168, 1998. [Online]. Available: http://www.sciencedirect.com/science/article/pii/ S0925527398000346 18 [3] P. Brucker, Scheduling Algorithms.

Springer, 2007. [Online]. Available: http:

//www.google.hu/books?id=FrUytMqlCv8C 25 [4] G. B. Dantzig, „Discrete-variable extremum problems,” Operations Research, vol. 5, no. 2, pp. 266–277, April 1957. [Online]. Available: http://www.jstor.org/stable/ 167356 7 [5] J. Du and J. Y. T. Leung, „Minimizing total tardiness on one machine is np-hard,” Mathematics of Operations Research, vol. 15, no. 3, pp. 483–495, 1990. [Online]. Available: http://mor.journal.informs.org/cgi/doi/10.1287/moor.15.3.483 18 [6] N. Fogarasi, K. Tornai, and J. Levendovszky, „A novel hopfield neural network approach for minimizing total weighted tardiness of jobs scheduled on identical machines,” Acta Univ. Sapientiae, Informatica, vol. 4, 2012. 20, 29, 35, 36, 38 [7] P. Gupta, P.; Kumar, „The capacity of wireless networks,” Information Theory, IEEE Transactions on, vol. 46, pp. 388 – 404, Mar 2000. 24 [8] S. Haykin, Neural Networks:

A Comprehensive Foundation, ser. Prentice

Hall International Editions Series.

Prentice Hall, 1999. [Online]. Available:

http://books.google.hu/books?id=M5abQgAACAAJ 41 [9] J. Hopfield, „Neural networks and physical systems with emergent collective computational abilities.” Proc Natl Acad Sci, vol. 79, pp. 2554–8., Apr 1982. 30 [10] S. M. Johnson, „Optimal two- and three-stage production schedules with setup times included,” Naval Research Logistics Quarterly, vol. 1, no. 1, pp. 61–68, 1954. [Online]. Available: http://dx.doi.org/10.1002/nav.3800010110 16 [11] B. Korte and J. Vygen, „The knapsack problem,” in Combinatorial Optimization, 4th ed., ser. Algorithms and Combinatorics.

45

Springer Berlin Heidelberg,

Irodalomjegyzék 2008, vol. 21, pp. 439–448. [Online]. Available:

http://dx.doi.org/10.1007/

978-3-540-71844-4_17 7, 8 [12] C. Koulamas, „Polynomially solvable total tardiness problems:

Review and

extensions,” Omega, vol. 25, no. 2, pp. 235 – 239, 1997. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0305048396000643 18 [13] B. Lee, D. Park, and H. Seo, Wireless Communications Resource Management. John Wiley & Sons, 2009. [Online]. Available: http://eu.wiley.com/WileyCDA/ WileyTitle/productCd-0470823577.html 5 [14] I.-S. Lee, „A worst-case performance of the shortest-processing-time heuristic for single machine scheduling,” The Journal of the Operational Research Society,

vol. 42,

no. 10,

pp. 895–901,

Oct. 1991. [Online]. Available:

http://www.jstor.org/stable/2583417 20 [15] J. Levendovszky, E. Laszlo, K. Tornai, and G. Treplan, Optimal pricing based resource management, 2010, p. 169. 29 [16] M. Neely, „Delay analysis for max weight opportunistic scheduling in wireless systems,” in Communication, Control, and Computing, 2008 46th Annual Allerton Conference on, sept. 2008, pp. 683 –691. 21 [17] J. Nocedal and S. J. Wright, Numerical Optimization, 2nd ed. New York: Springer, 2006. 29 [18] M. L. Pinedo, Scheduling: Theory, Algorithms, and Systems, 4th ed.

Springer,

2012. [Online]. Available: http://books.google.hu/books?id=EkpDak9kEs0C 6 [19] T. Sen, J. M. Sulek, and P. Dileepan, „Static scheduling research to minimize weighted and unweighted tardiness:

A state-of-the-art survey,” International

Journal of Production Economics, vol. 83, no. 1, pp. 1 – 12, 2003. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0925527302002657 18 [20] H. Sun and G. Wang, „Parallel machine earliness and tardiness scheduling with proportional weights,” Comput. Oper. Res., vol. 30, no. 5, pp. 801–808, Apr. 2003. [Online]. Available: http://dx.doi.org/10.1016/S0305-0548(02)00055-2 18 [21] W. Szwarc and J. J. Liu, „Weighted tardiness single machine scheduling with proportional weights,” Manage. Sci., vol. 39, no. 5, pp. 626–632, May 1993. [Online]. Available: http://dx.doi.org/10.1287/mnsc.39.5.626 18 [22] L. Tassiulas and A. Ephremides,

„Dynamic server allocation to parallel

queues with randomly varying connectivity,” IEEE Transactions on Information Theory,

vol. 39,

no. 2,

pp. 466–478,

1993. [Online]. Available:

http:

//ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=212277 21 [23] G. Treplán, K. Tornai, and J. Levendovszky, „Quadratic programming for tdma scheduling in wireless sensor networks,” International Journal of Distributed

46

Irodalomjegyzék Sensor Networks, vol. 2011, p. 17, 29 June 2011, 107062. [Online]. Available: http://www.hindawi.com/journals/ijdsn/2011/107062/cta/ 5, 22, 29, 35, 36 [24] T.-Y. Tsai, Y.-L. Chung, and Z. Tsai, „Introduction to packet scheduling algorithms for communication networks,” in Communications and Networking, J. Peng, Ed.

Sciyo, September 2010, ch. 13, p. 434. [Online]. Available:

http://www.intechopen.com/books/communications-and-networking 4 [25] B. Widrow and M. Lehr, „30 years of adaptive neural networks: perceptron, madaline, and backpropagation,” Proceedings of the IEEE, vol. 78, no. 9, pp. 1415 – 1442, Sept 1990. 42

47