Ütemezési problémák Kis Tamás1 1
MTA SZTAKI valamint
ELTE, Operációkutatási Tanszék
˝ ELTE Problémamegoldó Szeminárium, 2012. osz
Kivonat
Alapfogalmak Mit is értünk ütemezésen?
Gépütemezés 1||Lmax 1|rm|Cmax P||Cmax J||Cmax Alkalmazások
Kivonat
Alapfogalmak Mit is értünk ütemezésen?
Gépütemezés 1||Lmax 1|rm|Cmax P||Cmax J||Cmax Alkalmazások
Kivonat
Alapfogalmak Mit is értünk ütemezésen?
Gépütemezés 1||Lmax 1|rm|Cmax P||Cmax J||Cmax Alkalmazások
Mit, Mikor, Hogyan? Adott egy feladathalmaz, amely minden elemének van I eroforrás ˝ igénye, ˝ végrehatási ideje (amely függhet a hozzá rendelt eroforrásoktól), ˝ valamint lehetnek megelozési korlátok a feladatok között. I
˝ A feladatok végrehajtásukhoz eroforrásokat igényelnek. Megkülönböztetünk I megújuló (gépek, munkaero), ˝ és nem megújuló (felhasznált anyagok, energia) ˝ ˝ eroforrásokat. Az egyes eroforrásokból véges mennyiség érheto˝ el ˝ (idoegységenként / összesen). I
Meg kell határoznunk, hogy az egyes feladatokhoz mennyi (esetleg ˝ ˝ milyen) eroforrást rendeljünk, valamint a tevékenységek idozítését, ˝ úgy, hogy az eroforrás korlátokat betartsuk, és egy célfüggvényt minimalizáljunk, vagy maximalizáljunk.
Példák
Egygépes ütemezés 1||Lmax I
Egyetlen gépünk van.
I
A feladhalmaz elemei J1 , . . . , Jn .
I
Minden egyes Jj feladatnak két paramétere van: pj hossz, és dj ˝ határido.
I
Határozzunk meg egy végrehajtási sorrendet a gépünkön úgy, hogy a maximális késés a leheto˝ legkisebb legyen.
Egy S megengedett ütemezés minden Jj muveletnek ˝ megadja az Sj kezdési idejét, és teljesíti a következo˝ feltételeket: I
a muveletek ˝ végrehajtása nem fedi át egymást, azaz Sj + pj ≤ Sj 0 vagy Sj 0 + pj 0 ≤ Sj , minden j 6= j 0 párra.
1||Lmax max. késés
idő max késés
idő
EDD sorrend Jelölések: Jj pj dj Cj (S) Lj (S) = Cj (S) − dj Lmax (S) = max Lj (S)
j. feladat j. feladat hossza j. feladat határideje j. feladat befejezési ideje az S ütemtervben j. feladat késése az S ütemtervben (lehet negatív) maximális késés az S ütemtervben
EDD sorrend: A feladatokat a határido˝ szerint nem csökkeno˝ sorrendben ütemezzük.
Tétel Az EDD sorrend mindig optimális megoldást ad. Biz Tf. van olyan input, amihez az optimális ütemtervben a feladatok nem EDD sorrendben vannak. Legyen S ∗ olyan optimális ütemterv, amiben az inverziók száma minimális az EDD sorrendhez képest. Ekkor van egymás utáni két feladat, Jj , és Jk , S ∗ -ban, amelyek nem ˝ Jk feladatot, de dj > dk . EDD sorrendben vannak, azaz Jj megelozi
EDD sorrend Cj (S ∗ ) = t + pj Ck (S ∗ ) = t + pj + pk Csere után: Cj (S 0 ) = t + pj + pk Ck (S 0 ) = t + pk
Lj (S ∗ ) = t + pj − dj Lk (S ∗ ) = t + pj + pk − dk Lj (S 0 ) = t + pj + pk − dj < Lk (S ∗ ) (dj > dk ) Lk (S 0 ) = t + pk − dk < Lk (S ∗ )
Tehát a csere után Lmax (S 0 ) ≤ Lmax (S ∗ ). Jj
S*
Jk
t
idő
Jk
S' t
Jj idő
Ütemezés anyagkorlátokkal Ebben a problémában a gép mellett van néhány anyag (nem ˝ megújuló eroforrás), amelyek szükségesek (különbözo˝ mennyiségekben) a muveletek ˝ végrehajtásához. I
I
I
Legyen az anyagok száma g, az induló készlet az i-anyagból b0 (i), i = 1, . . . , g. ˝ Adottak beszállítási idopontok 0 < u1 < · · · < uq , és ˝ mennyiségek bt (i) ≥ 0, azaz az ut idopontban bt (i) mennyiség érketik az i-anyagból. A feladathalmaz minden Jj elemének két paramétere van: pj > 0 g hossz, és egy aj ∈ R+ anyagigény vektor.
Egy S megengedett ütemezés minden Jj muveletnek ˝ megadja az Sj kezdési idejét, és teljesíti a következo˝ feltételeket: I a muveletek ˝ végrehajtása nem fedi át egymást, azaz Sj + pj ≤ Sj 0 vagy Sj 0 + pj 0 ≤ Sj , minden j 6= j 0 párra. I
Az anyagigény nem több, mint ami rendelkezésre áll minden P Pt−1 ˝ idopontban, azaz j : Sj
1|rm|Cmax Cél: az utolsónak ütemezett feladat befejezési idejének minimalizálása (Cmax )
0
u1
u2
idő
2-approximáció az 1|rm|Cmax problémára
Elso˝ algoritmus ˝ Ütemezzük a feladatokat az utolsó beszállítási idopont után ˝ tetszoleges sorrendben. Második algoritmus 1. Rendezzük a feladatokat a teljes anyagigényük szerint nem csökkeno˝ sorrendbe. 2. Ütemezzük a feladatokat a fenti sorrend szerint a legkorábbi ˝ idopontba.
Illusztráció
0
u1
u2
0
u1
u2
idő
idő
Az algoritmusok tulajdonságai Tétel ˝ A második algoritmus legalább olyan jó eredményt ad, mint az elso.
Tétel Az elso˝ algoritmus olyan ütemtervet ad, melynek hossza legfeljebb az optimum kétszerese. ∗ Biz Jelölje Cmax az optimális ütemterv hosszát. Vegyük észre, hogy I I
∗ uq < Cmax , és P ∗ pj ≤ Cmax .
Az algoritmus olyan ütemtervet ad, melynek hossza P alg1 Cmax = uq + pj . ˝ következik, hogy Ezekbol X alg1 ∗ Cmax = uq + pj < 2Cmax I
Legrosszabb eset a második algoritmusra Mutatunk egy feladat sereget, amely igazolja, hogy a második algoritmus is csak 2-approximáció. Adatok I
n feladat, mindegyik egységnyi hosszú (pj = 1)
2 anyag n−1 1 I a1 = , aj = , 2 ≤ j ≤ n. 0 n+j −3 n−1 0 I b0 = , bt = , 1 ≤ t ≤ n − 2, 0 n+t −2 n−1 bn−1 = . 2n − 3 Ekkor a feladatok sorrendje 1, . . . , n. I
Optimális megoldás: S1 = n, Sj = j − 1, 2 ≤ j ≤ n. Második algoritmus: S1 = 0, S2 = n − 1, S3 = n, . . . , Sn = 2n − 3. alg2
∗ Tehát Cmax /Cmax = (2n − 3)/(n + 1) → 2, ha n → ∞.
Ütemezés párhuzamos gépeken
Adott m gép, és n feladat: a feladatokat gépekhez kell rendelni úgy. ˝ Adatok: hogy minimalizáljuk a maximális befejezési idot. I
Feladatok száma n, gépek száma m.
I
Minden Jj feladat, 1 ≤ j ≤ n, egyetlen paraméterrel rendelkezik: a feladat hossza, amit pj jelöl. A pj hossz nem függ a feladathoz ˝ választott géptol.
Minden feladatot egy géphez kell rendelni az m gép közül. Az egy ˝ géphez rendelt feladatokat tetszoleges sorrendben lehet végrehajtani. Cél: A maximális befejezési ido˝ minimalizálása.
Listás ütemezés
Tétel A P||Cmax probléma NP-nehéz. Listás ütemezési algoritmus ˝ 1. Helyezzük a feladatokat egy listára tetszoleges sorrendben. 2. A listáról egymás után dolgozzuk fel a feladatokat. A következo˝ ˝ feladatot arra a gépre rakjuk, ahol a leghamarabb elkezdodhet.
A listás ütemezés menete (1)
M1 M2 M3 0
idő
A listás ütemezés menete (2)
M1 M2 M3 0
idő
A listás ütemezés menete (3)
M1 M2 M3 0
idő
A listás ütemezés menete (4)
M1 M2 M3 0
idő
A listás ütemezés menete (5)
M1 M2 M3 0
idő
A listás ütemezés menete (6)
M1 M2 M3 0
idő
A listás ütemezés tulajdonságai Alsó korlátok az optimumra: Pn I C∗ max ≥ j=1 pj /m I
C ∗ max ≥ max pj
Tétel ˝ A listás ütemezés tetszoleges sorrend esetén (2 − 1/m)-approximáció. ˝ o˝ munka. Biz Legyen Jk az utolsóként befejezod A Jk kezdéséig minden gép folyamatosan dolgozik, különben korábban kezdhetnénk. Tehát ha Sk a Jk kezdési ideje, akkor alg
Cmax = Ck = Sk + pk ≤
n X j=1,j6=k
∗ ≤ (2 − 1/m)Cmax
pj /m + pk =
n X j=1
pj /m + (1 − 1/m)pk
A listás ütemezés tulajdonságai (folyt.)
˝ On-line ütemezés: nem ismerjük a feladatokat elore, hanem ahogy jön egy feladat, géphez kell rendelnünk. On-line algoritmus versenyképessége: mennyire tér el az on-line algoritmus eredménye az off-line optimumtól.
Tétel A listás ütemezés olyan on-line algoritmus, aminek a versenyképessége (2 − 1/m). LPT sorrend: hossz szerint nem növekvo˝ sorrendje a feladatoknak.
Tétel A listás ütemezés az LPT sorrend esetén 4/3 approximáció.
Gyakorlati ütemezési problémák
I
Gyártás ütemezés I I
I
diszkrét folytonos (processz)
Processzor ütemezés I I
Operációs rendszer multitasking Szuperszámítógépek (a processzorok térbeli elrendezése, és ˝ szomszédsága is figyelembe veendo)
I
Grid
I
Tudományos mérések (Hubble teleszkóp) programja
I
Sport események ütemezése (Amerikai baseball liga)
