Eötvös Loránd Tudományegyetem Természettudományi Kar
Bodó Alexandra
Algoritmusok többgépes ütemezési feladatokra BSc Elemz® Matematikus Szakdolgozat
Témavezet®:
Jordán Tibor
Operációkutatási Tanszék
Budapest, 2015
Köszönetnyilvánítás
Ezúton szeretnék köszönetet mondani konzulensemnek Jordán Tibornak, aki felkeltette az érdekl®désem a téma iránt, munkám során végig segített és motivált. Emellett szeretném megköszönni családomnak és barátaimnak a sok biztatást, kitartást és érdekl®dést, amely nélkül nem jöhetett volna létre ez a szakdolgozat.
2
Tartalomjegyzék
1. Bevezetés
4
1.1.
Alapfogalmak
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.2.
Történet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2. Párhuzamos gépes ütemezések 2.1.
2.2.
P ||Cmax
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
2.1.1.
Listás ütemezés . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
2.1.2.
Knuth-Kleitman Algoritmus . . . . . . . . . . . . . . . . . . . . . .
9
P 2|prec, pj = 1|Cmax 2.2.1.
2.3.
9
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
Coman és Graham algoritmusa . . . . . . . . . . . . . . . . . . . .
11
P |pj = 1, ri |Lmax
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3. Uniform gépes ütemezések 3.1.
Q|pmtn|Cmax
3.2.
Q|pmtn, ri |Lmax . . . . . . . . . P Q|| Ci . . . . . . . . . . . . . P Q|pmtn| Ci . . . . . . . . . . P Q|pi = 1| fi és Q|pi = 1|fmax
3.3. 3.4. 3.5.
21
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
. . . . . . . . . . . . . . . . . . . . . . . .
25
. . . . . . . . . . . . . . . . . . . . . . . .
28
. . . . . . . . . . . . . . . . . . . . . . . .
29
. . . . . . . . . . . . . . . . . . . . . . . .
31
4. Független gépes ütemezések 4.1.
17
33
R|pmtn|Cmax , R|pmtn|Lmax , R|pmtn, ri |Lmax
3
. . . . . . . . . . . . . . . . .
33
1. fejezet
Bevezetés
Egy matematikai probléma megoldásában van valami élvezetes. Az ember szembetalálja magát egy problémával, aminek még nem ismeri a nyitját, de tisztában van vele, hogy vannak bizonyos szabályok, amelyeket követhet, és bizonyos megközelítésmódok, amelyeket alkalmazhat, és bár az eljárás során a közbens® lépcs®fokok gyakran még bonyolultabbak a kiindulási helyzetnél, a végeredmény már annál egyszer¶bb. Az ember bizony örömét leli abban, ahogyan végighalad ezen az úton. - Malcolm Gladwell
1.1.
Alapfogalmak
1.1.1. De níció. (Ütemezés)
Bizonyos tevékenységek elvégzésére olyan id®beosztást ta-
lálni, ami gyelembe veszi a rendelkezésre álló er®forrásokat, és valamilyen szempont szerint optimális.
1.1.2. De níció. a gépek
Munkákat végzünk gépeken. Adottak a munkák,
M = {M1 , M2 , . . . , Mm }.
J = {j1 , j2 , . . . , jn }
és
Minden munkához adott a megmunkálási ideje, az az
id® amely alatt a munka elvégezhet®
{p1 , p2 , . . . , pn }.
A gépek fajtái: •
Egygépes ütemezés: egy darab gépünk van. Jelölése:
•
Párhuzamos gépes ütemezés: m db egyforma gépünk van. Jelölése:
•
Uniform gépes ütemezés: m db különböz® sebesség¶ gépünk van (s1 , s2 , . . . , sm sebességek). Jelölése:
•
P
Q
Független gépes ütemezés: m db gépünk van és
j -edik
1
munka megmunkálási idejei). Jelölése:
Feltételek fajtái: 4
R
pi,j -k
adottak (az
i-edik
gépen a
•
pmtn : a munkák megszakíthatóak
•
prec : a munkákhoz adottak megel®zési feltételek, azaz például a
j munkát az i munka
el®tt kell elvégezni
• rj :
rendelkezésre állási id®, azaz a
• dj :
határid®, azaz
• wj :
súly, a
j
j
munka
munkát
wj
dj
j
munka csak
rj
után kezdhet® el
ideig be kell fejezni
súllyal számít
Célfüggvények fajtái: • Cmax : •
P
Cj :
max Cj : j
P
teljes átfutási id® minimalizálása
Cj → min:
befejezési id®k összegének minimalizálása
j
• Lmax : •
P
Uj :
max Lj : j
P
maximális késést minimalizálni
Uj → min:
a késések számának az összegének a minimalizálása
j
• fmax : •
P
fj :
max fj (Cj ) → min: i
P
fj → min:
az
j.
munka maximális büntetésének minimalizálása
a büntetések összegének minimalizálása
j
1.1.3. Megjegyzés. Lj := Ci − di késés 1 ha m késik Uj = 0 ha m nem késik 1.2.
Történet
A történet Ronald L. Graham t®l származik ([11]).
1.1. ábra. Részmunkaid®k A dolgok nem mentek túl jól az Acme kerékpárgyártó cég összeszerelési részlegén. Sosem sikerült az el®írt kvótát teljesíteni. Így kineveztek egy új csoportvezet®t a részlegen, és
5
elmondták neki, hogy mi a probléma és a feladata, hogy ezt orvosolja. Az új csoportvezet® rájött, hogy neki ez egy jó lehet®ség, hogy a felettesei fel gyeljenek rá, ezért mindent alaposan tanulmányozni kezdett. Az els® dolog amit megtanult, hogy a kerékpár összeszerelési folyamata több kisebb munkára bomlik.
Részmunkák megnevezése, jelölése •
FP: a váz el®készítése
•
FW: az elüls® kerék összeszerelése és egyenesbe állítása
•
BW: a hátsó kerék összeszerelése és egyenesbe állítása
•
DE: a váltó hozzákapcsolása a vázhoz
•
GC: a fogaskerekek felszerelése
•
CW: a lánc hozzákapcsolása a fogantyúhoz
•
CR: a fogantyú és a lánc hozzákapcsolása a vázhoz
•
RP: a jobb pedál összeszerelése
•
LW: a bal pedál összeszerelése
•
FA: utolsó simítások, a kormány, az ülés, a fékek összeszerelése és szabályozása
A következ® dolog amit tanulmányozott, hogy meddig tart képzett szakembereknek ezen részmunkák elvégzése (1.1 ábra). Ezt a korábbi információkból tudta összeszedni.
1.2. ábra. Részmunka-sorrend A hely és a felszerelés miatt a osztva;
10
20
csoport mindegyikében
szerel®, akik a részlegen dolgoztak, csoportokba voltak
2
ember, és minden csapat
1
biciklit szerelhet egy id®-
ben. Egy gyors számolás alapján kaphatjuk, hogy egy bicikli összeszerelési ideje összesen
64 perc, ami azt jelentené, hogy egy csapatnak ezt 32 perc alatt kéne elvégeznie. Ekkor egy 8 órás munkanap alatt minden csapat 15 biciklit tudna összeszerelni, azaz naponta 150 kerékpár lenne készen. A csoportvezet® lelkesedése csökkent amikor rájött, hogy a kerékpárhoz tartozó részmunkákat nem végezheti tetsz®leges sorrendben. Bizonyos munkákat másik munkák el®tt kell elvégezni. A csoportvezet® hosszas megbeszélés után, elkészítette az alábbi táblázatot (1.2 ábra).
6
1.3. ábra. Általános kerékpár-szerelési sorrend
Ezen felül két szabály van, amit a munkaid® alatt be kell tartani, a helyi menedzsment el®írása szerint.
•
Els® szabály: Egyik szerel® sem pihenhet, ha van mit csináljon.
•
Második szabály: Ha egy szerel® elkezdett egy részmunkát, akkor folytatnia kell amíg nem végez vele.
1.4. ábra. Csökkentett idej¶ részmunkák ütemezése Az általános kerékpár-szerelési sorrendet a 1.3 ábra mutatja. Az ütemezés megmutatja: mindkét szerel® a csapatban egyszerre kezd a és a befejezési id®t, ami itt
34.
0 id®pontban, az egész szerelési folyamatot,
Bár ez az ütemezés teljesíti az összes szükséges feltételt
(amik adottak), minden csapat naponta majdnem mint a
150
14 kerékpárt szerel össze. Ami kevesebb
db-os kvóta.
Miután a csoportvezet® rengeteget próbálkozott különféle ütemezésekkel, de nem járt sikerrel, úgy döntött, hogy minden szerel®t ellát kölcsönzött elektromos eszközökkel. Ez
54 perc. Arra gondolt, 18 biciki/csapat darabszámot naponta. Az els® hét végén, mikor a bérelt használták, a gyártás lecsökkent 14 biciklire naponta. El®ször nem értette,
minden részmunka idejét 1 perccel csökkenti, így az összid® csak hogy így elérheti a eszközöket
hogy lehetséges ez, majd elkezdett újra számolni. Minden ütemezésnek, ami teljesíti a szabályokat legalább
35
percre van szüksége (1.4 ábra).
A csoportvezet® csalódott volt, és visszaadta a bérelt elektromos eszközöket. Ezután kétségbeesetten úgy döntött, hogy felvesz
10 szerel®t, és minden csoport háromf®s lesz. Tudta,
hogy így a munkaer®költség jelent®sen megn®, de úgy gondolta, hogy ha ezzel eléri a kvótát, akkor ez nem lesz probléma. Ám két nap sem telt el, hogy rájöjjön, ez az ötlet sem
7
1.5. ábra. A három f®s csoportok ütemezése
eredményes. A kerékpárgyártás leesett
13
darab/napra. Vonakodva megint áttekintette
a különböz® ütemezéseket. Ekkor azt fedezte fel, hogy az új csapatokkal való ütemezés legalább
37
percet vesz igénybe (1.5 ábra). A következ® pár napot azzal töltötte, hogy
gondolkozott hol rontotta el, majd megérkezett a felmondása. Ez a történet megmutatja, hogy mennyire nem egyszer¶ megoldani egy ütemezési feladatot, és minden ütemezési feladattípusnak más-más a megoldása. Ilyen feladatmegoldásokat fogok a továbbiakban bemutatni.
8
2. fejezet
Párhuzamos gépes ütemezések
2.1.
P ||Cmax
2.1.1. Listás ütemezés 2.1.1. Algoritmus.
Legyen
L
a munkák valamilyen listája, és ütemezzük a munkákat a
következ®képpen: Amikor egy gép szabaddá válik, ütemezzük ezen a gépen az
L
listából
a soron következ®t.
2.1.2. Knuth-Kleitman Algoritmus 2.1.2. Algoritmus. [5]).Válasszuk ki a
k
®ket optimálisan az
A következ® algoritmus Knuth és Kleitman dolgozta ki (Graham leghosszabb munkát, valamely
m
gépen. A megmaradó
n−k
k≥0
egész számra, majd ütemezzük
munkát pedig listásan ütemezzük.
A listás ütemezésb®l következik, ha van olyan gép amely szabad, akkor a következ® munka nem várhat, hanem a gépre kerül. Adhatunk két alsó korlátot az optimális ütemezés hosszára:
νk = ν∗ ≥
a kiválasztott P pj m
k
munka el®ütemezésének az optimuma
2.1.3. De níció. ν(k) = az algoritmus által kapott ütemezés értéke 2.1.4. Tétel.
Jelöljük
ν ∗ -gal
az optimális ütemezés értékét. Ekkor:
1 − m1 ν(k) ≤1+ k ν∗ 1 + bm c
9
(2.1)
Bizonyítás.
ν(k) > νk és n > k . Legyen p∗ = maxk+1≤j≤n (pj ). Látható, ∗ szabad a ν(k) − p -t megel®z®en, a listás ütemezés miatt.
Feltehetjük, hogy
hogy nincs olyan gép, amely Így:
X
pj ≥ (ν(k) − p∗ ) · m + p∗
(2.2)
j De
∗
p∗ 1 pj ≥ (ν(k) − p∗ ) + = ν(k) − p∗ 1 − m m m
P
ν ≥
(2.3)
∗ munkánk amelyek megmunkálási ideje nem kevesebb mint p , és néhány gép, k k+1 amelynek dolgoznia kell legalább 1 + b c (vagyis d e) ilyen munkán. Így: m m
Van
k+1
ν∗ ≥ 1 + b p∗ ≤
k ∗ c ·p m
, amib®l (2.4)
ν∗ k 1 + bm c
Így (2.3) alapján:
ν(k) ≤ ν ∗ + p∗ 1 − ν(k) ≤ ν ∗ + ν ∗
Így a bizonyítás kész.
2.1.5. Megjegyzés.
1 m
és ebb®l (2.4) miatt
1 − m1 1 − m1 ∗ = ν 1 + k k 1 + bm 1 + bm c c
(2.5)
2 − m1
P ||Cmax -ra. Emiatt a KKA minden esetben jobb, mint a listás ütemezés. Viszont azt láthatjuk, hogy ahogy a k n®, úgy ez a korlát egyre közelebb lesz az 1-hez. Sajnos ez nem bír nagy jelent®séggel, mivel egy optimális ütemezést adni az els® k munkára, már önmagában egy nehéz probléma. 3 eset: Ha
1+
m−1 m+1
k=m
KKA: Ha
k = 1, k = m, k = 2m
k=1
KKA: Ha
Tudjuk, hogy a listás ütemezés
3 2
−
1 2m
k = 2m
KKA:
1+
m−1 3m
10
közelít® a
P 2|prec, pj = 1|Cmax
2.2.
2.2.1. Coman és Graham algoritmusa 2.2.1. De níció. (Lexikogra kus sorrend) l = (n01 , n02 , . . . , n0k0 ) valós számsorok, ahol 0 kusan kisebb mint l , hogyha: 0
1.
∃j (1 ≤ j ≤ k ),
2.
k < k0
és
2.2.2. Példa.
amely
ni = n0i
Legyen
0
k, k ≥ 1.
∀i-re (1 ≤ i < j )
l = (n1 , n2 , . . . , nk )
és
Ekkor azt mondjuk, hogy
teljesíti, hogy
ni = n0i
l
lexikogra-
nj < n0j .
de
vagy
∀i-re (1 ≤ i ≤ k ).
Például: legyen
l = (3, 4, 6, 2)
és
l0 = (3, 4, 3, 1),
ekkor
l0
lexikogra kusan > l30 .
kisebb mint l , mivel az els® két elemük megegyezik, de a harmadik elemnél l3 Másik példa: legyen
f,
f
mivel
f = (1, 4, 6, 7)
f 0 = (1, 4, 6), ekkor f 0 lexikogra kusan kisebb mint 0 mint f elemeinek száma, és el®tte minden elemük
és
elemeinek száma több,
megegyezik.
2.2.3. Algoritmus.
A következ® algoritmus Coman-tól és Graham-t®l származik (Co-
man [6]). Adott a
•
G
irányított gráfunk.
Els® lépés. Végezzünk tranzitív redukciót a G irányított gráfunkon. Ezzel a módés
G éleinek számát úgy, hogy ne változzanak a megel®zési j -b®l l-be men® él G-ben, és ∃k 6= j, l munka amelyre teljesül, k − l út G-ben, akkor töröljük a j − l élt G-b®l.
Második lépés.
Osszuk a munkákat csoportokra a következ®képpen: az els® cso-
szerrrel csökkenthetjük a feltételek. Ha van hogy van
•
j−k
portban legyenek azok a munkák, amelyeknek a ki-foka legyenek azok a munkák, amelyeknek a ki-foka
0-vá
0,
a második csoportban
válik, ha kitöröljük az els® cso-
1-t®l + 1-t®l kp -ig),
portban lév® munkákat, és így tovább. Majd az els® csoport tagjait címkézzük
k1 -ig.
Ha már ismerjük a
p-edik
csoport tagjainak a címkézését (kp−1
p+1-edik csoport pontjait az alábbi módon címkézzük. El®ször minden ilyen mellé felírjuk a bel®le elérhet® p-ik csoportban lév® pontok címkéjét csökken®
akkor a pont
sorrendben. Ezután a címkék sorozatából kapott számsorozatokat lexikogra kus sorrend szerint rendezzük és megkapjuk, hogy melyik pont kapja a
kp +1, kp +2, . . . , kp+1
címkéket. (A lexikogra kusan nagyobb kapja a nagyobb címkét.)
•
Harmadik lépés. Mikor minden munka címkézett, ütemezzünk listásan a munkákat, hogy a munkák/csúcsok csökken® sorrendben vannak a címkék szerint.
2.2.4. Példa.
A 2.1 ábrán láthatjuk, hogy m¶ködik az algoritmus második lépése, ho-
gyan alakulnak ki a csoportok, végül a csúcsok címkézését is. A csúcsok felett láthatóak
11
2.1. ábra. Példa a Coman-Graham algoritmusra
2.2. ábra. Példa megoldása
a bel®lük elérhet® élek (csökken® sorrendben), ami alapján meg tudjuk állapítani (lexikogra kus sorrend alapján) a címkéket. Majd a 2.2 ábrán az algoritmus harmadik lépését láthatjuk, magát az ütemezést. Egy id®ben nem végezhet® együtt olyan munka, amelyre igaz, hogy az egyikb®l elérhet® a másik (például a
15
és a
14),
így ezt gyelembe véve, listásan ütemezzük a munkákat
csökken® címke szerint.
2.2.5. Példa.
Tekintsük a 2.3 ábrán látható gráfot. Láthatjuk, hogy ez nem tranzitív
redukált, hiszen a a
4-essel
8−5−4
út biztosítja a
8−4
is. Ha lefuttatjuk az algoritmust (2.5 ábra), akkor
tranzitív redukáltját nézzük, akkor
8-as csúcs össze van kötve Cmax = 5, míg ha a G gráf
utat, de a
Cmax = 4 (2.4 ábra). Emiatt láthatjuk, hogy a tranzitív
redukált kiszámítása, nem elhanyagolható az algoritmusban.
2.2.6. Megjegyzés.
Megmutathatjuk, hogy az algoritmus nem m¶ködik
m = 3-ra.
Hi-
szen tudunk mutatni jobb megoldást, mint amit az algoritmusunk ad (2.6 ábra). Az algoritmus által kapott eredmény Tehát
m = 2-re
Cmax = 5,
a következ® tétel adható.
12
míg az optimális ütemezésben
Cmax = 4.
2.3. ábra. G gráf, ami nem tranzitív redukált
2.4. ábra. G gráf tranzitív redukáltja
2.2.7. Tétel.
A Coman-Graham algoritmus ([4]) helyesen megoldja a
P 2 | prec, pj =
1 | Cmax -ot.
Bizonyítás.
A bizonyítást megel®z®en de niálnunk kell pár fogalmat.
2.2.8. Jelölés. J ≺ J 0
azt jelenti, hogy
J J 0 -nek
az ®se, és
J 0 J -nek
a utódja, ahol
0
J, J ∈ G.
2.2.9. De níció. ®se
J 0 -nek
és
J0
Ha nem létezik olyan
közvetlen utódja
2.2.10. Jelölés. J
J 00 ∈ G,
amelyre
J ≺ J 00 ≺ J 0 ,
J -nek.
közvetlen utódainak halmazát jelöljük
13
S(J)-vel.
akkor
J
közvetlen
2.5. ábra. Példa megoldása
2.6. ábra. Példa megoldása
2.2.11. Megjegyzés.
A közvetlen utódok halmaza, megegyezik a ki-szomszédok halma-
zával a tranzitív redukció miatt.
2.2.12. Jelölés. L = (J1 , J2 , . . . , Jr ) jelölje a G-ben lév® munkák valamilyen permutációját.
2.2.13. De níció. munkákat, az
L
Legyen
Jelölje
2.2.15. Jelölés.
Jelöljük a
2.2.16. De níció. J ∈G
az az id®, ami szükséges, hogy végrehajtsuk a
G-ben
lév®
listát felhasználva (az L lista által kapott maximális befejezési id®).
2.2.14. Jelölés.
a
ω(L)
kezd®dik a
2.2.17. Lemma.
r
a munkák számát
J
G-ben, illetve L∗
munka címkéjét
a címkézésb®l kapott listát.
α(J)-vel.
τ (J) egy nemnegatív egész szám, ami azt az id®t jelöli, amikor ∗ megfelel® L szerinti ütemezésben. Legyen
Ha
J M1 -en
van ütemezve, és
τ (J) ≤ τ (J 0 ) (J 6= J 0 ),
akkor
α(J) >
0
α(J ). Tegyük fel, hogy a
G-beli
munkákat
vallumon, azt mondjuk, hogy
M2 ∅
L∗
szerint ütemezzük. Ha
M2
üres feladatot hajt végre és ekkor
14
[t, t + 1] α(∅) = 0.
szabad
inter-
2.2.18. De níció.
De niáljuk rekurzívan
Vi -t
és
Wi -t
a következ®képpen:
τ (V0 ) = ω(L∗ ) − 1 (tehát ® az utolsó munka M1 -n). W0 pedig legyen az a munka, ami M2 -n van ütemezve és τ (W0 ) = ω(L∗ ) − 1 (tehát ® az utolsó munka M2 -n).
1. Legyen
V0
2. Általában, és
τ (J)
az a munka, ami
M1 -n
k ≥ 1-re Wk
J
az a
van ütemezve és
maximális. A 2.2.17 lemmából
munka, ami
M1 -n
fut és
α(J) < α(Vk−1 ), τ (J) < τ (Vk−1 ) következik, hogy Wk az M2 -n fut. Vk az a
munka, amelyre
τ (Vk ) = τ (Wk ).
2.7. ábra. Példa a
Vi -re, Wi -re
és
χi -re
ω(L∗ ) − 1 id® el®tt, és így L∗ nyilvánvalóan optimális lesz. Így feltehetjük, hogy W1 (és így V1 ) is létezik. Tegyük fel, hogy csak Wi -t 0 ≤ i ≤ m tudjuk de niálni. Legyen χi azon J munkáknak a halmaza, amelyek kielégítik a τ (Vi+1 ) < τ (J) ≤ τ (Vi )-t, de J 6= Wi , 0 ≤ i ≤ m. Mivel Vm+1 nem létezik, ezért χm azon J munkák halmaza, amelyekre τ (J) ≤ τ (Vm ) és T 6= Wm . Jegyezzük meg, hogy minden χk számossága páratlan, így megadhatjuk |χk | = 2nk − 1 pozitív egész nk -ra, ahol 0 ≤ k ≤ m.
Ha
W1
nem létezik, akkor nincs olyan gép, ami állna a
2.2.19. Lemma.
Ha
J ∈ χk , J 0 ∈ χk+1 0 ≤ k ≤ m-re,
akkor
J0 ≺ J.
τ (J)-re és τ (J 0 )-re. A χk α(J) ≥ α(Vk ) és τ (J) ≤ τ (Vk ).
A következ®ekben bebizonyítjuk ezt a kett®s indukciót ójából tudjuk, hogy a El®ször is, legyen
nk + 1 .
J ∈ χk
X ∈ χk ,
azt jelenti, hogy
úgy hogy
τ (X)
minimális, így
de níci-
τ (X) = τ (Vk+1 ) + 1 = τ (Vk ) −
Mivel:
α(Vk+1 ) > α(X) ≥ α(Vk ) > α(Wk+1 )
kellett volna ütemezni a τ (Vk+1 ) id®ben, de nem lett ütemezve. Így 0 ebben az id®pillanatban valamennyi X -nek (X -nek az ®sei közül) még nem ütemezettnek 0 0 kell lenni. Emiatt τ (X ) ≥ τ (Vk+1 ). De ez azt jelenti, hogy α(X ) > α(X) az algoritmus 0 de níciója miatt. X a τ (X) id®ben van ütemezve, X -t az X el®tt kell ütemezni és ezért
X -et
(2.6)
az
M2 -n
τ (X 0 ) = τ (X) − 1 = τ (Vk+1 ), 15
(2.7)
τ (X 0 ) = τ (Vk+1 ) és α(X 0 ) > α(Wk+1 ). 0 nevezetesen X = Vk+1 . Így Vk+1 ≺ X . így
Tegyük fel, hogy egy x
τ (Vk ) − nk + j , nk + j + 1 .
j -re,
Csak egyetlen lehetséges megoldás van
1 ≤ j < nk hogy Vk+1 ≺ X .
amire
ami azt jelenti,
megmutattuk, hogy X 0 Legyen X ∈ χk amire
X 0 -re,
∈ χk és τ (X) ≤ τ (X 0 ) = τ (Vk ) −
Mivel
α(Vk+1 ) > α(X 0 ) ≥ α(Vk ) > α(Wk + 1) ezért, mint korábban
X 0 -t
az
M2 -n
kéne ütemezni a
τ (Vk+1 )
(2.8)
id®ben, de nem áll készen,
hogy ütemezve legyen (azaz még vannak ®sei amik nincsenek ütemezve). Így valamennyien X 00 az X 0 ®sei közül, a τ (Vk+1 ) ideig még nem lettek ütemezve, és így kell hogy τ (X 00 ) ≥ τ (Vk+1 ) = τ (Vk ) − nk . Mivel X 00 ≺ X 0 ezért τ (X 00 ) ≤ τ (X 0 ) − 1 = τ (Vk ) − nk + j . 00 00 0 00 Ha τ (X ) = τ (Vk ) − nk , és α(X ) > α(X ) ≥ α(Vk ) > α(Wk+1 ), akkor X = Vk+1 0 00 és megkaptuk hogy Vk+1 ≺ X . Emiatt feltehetjük, hogy τ (X ) ≥ τ (Vk ) − nk + 1. Az indukciós feltevés miatt:
τ (Vk ) − nk + 1 ≤ τ (X 00 ) ≤ τ (Vk ) − nk + j
(2.9)
00 látjuk, hogy X ∈ χk és Vk+1 ≺ X 00 . Így a ≺ tranzitivitása miatt, megkapjuk, hogy 0 Vk+1 ≺ X és az els® indukciós lépés kész. Ez megmutatja, hogy
Vk+1 ≺ X Jelöljük
X
minden
X ∈ χk
(2.10)
Ik -val azon χk -beli munkák halmazát, amelyeknek nincs ®se χk -ban. Mivel Vk+1 ≺ X ∈ χk -ra, így nem nehéz látni, hogy S(Vk+1 ) ∩ χk = Ik .
minden
j -re amire 0 ≤ j ≤ nk+1 − 2 megmutattuk, hogy ha J ∈ χk+1 , τ (Vk+1 ) − j ≤ τ (J) ≤ τ (Vk+1 ) akkor J ≺ X minden X ∈ χk -re. Legyen X 0 ∈ χk+1 amire τ (X 0 ) = τ (Vk+1 ) − j − 1. Mivel X 0 ∈ χk+1 ezért α(X 0 ) > α(Vk+1 ). Így teljesülni kell annak, 0 0 hogy N (X ) ≥ N (Vk+1 ), ahol N (X ) úgy jön létre, hogy vesszük az α értékek csökken® 0 00 0 sorrendjét az X közvetlen utódaiból. Ha létezik X ∈ S(X ) ∩ χk+1 , akkor az indukciós 00 0 00 feltevés miatt, mivel τ (X ) > τ (X ) = τ (Vk+1 ) − j − 1, vagyis τ (X ) ≥ τ (Vk+1 ) − j , 00 0 ezért X ≺ X minden X ∈ χk . Így a tranzitivitás miatt, X ≺ X minden X ∈ χk -ra. 0 Emiatt feltehetjük, hogy S(X ) ∩ χk+1 üres. A 2.2.17 lemma miatt, α(J) < α(Vk ) ha τ (J) > τ (Vk ). Szintén, látjuk, hogy α(Wk ) < α(Vk ). Az algoritmus de níciója alapján: N (X 0 ) ≥ N (Vk+1 ) és X 0 -nek nincs utódja χk+1 -ben, ekkor S(X 0 ) ∩ χk = Ik . Ez viszont 0 azt jelenti, hogy X ≺ X minden X ∈ χk munkára. Ez teljessé teszi az indukciós lépést 0 0 és a bizonyítását annak, hogy ha T ∈ χk és T ∈ χk+1 (0 ≤ k ≤ m), akkor T ≺ T . Tegyük fel, valamilyen
Innen már csak egy rövid lépés, hogy bebizonyítsuk a tételt. Egy tetsz®leges
χk+1 -beli munkának be kell fejez®dnie Mivel χk+1 2nk+1 − 1 munkából áll, ezért
minden
miel®tt bármelyik
dik.
ez legalább
16
nk+1
χk -beli
L
listára,
munka elkezd®-
id®egységet igényel. Így,
ahhoz hogy minden milyen
L
G-beli munkát elvégezzünk legalább
listát használtunk. Mivel
ω(L∗ ) =
m P
m P
nk
id®egység kell, nem számít
k=0
nk
és megmutattuk, hogy
ω(L) ≥ ω(L∗ )
k=0 így a bizonyítás kész.
2.3.
P |pj = 1, ri|Lmax
Legyenek a munkák az alábbi módon indexelve:
r1 ≤ r2 ≤ . . . ≤ rn .
A feladat megoldása
egyszer¶, ha a rendelkezésre állási id®k egész számok. Ebben az esetben optimális ütemezést kapunk, ha nemcsökken® határid® szerint rendezzük az elérhet® munkákat. Pontosab-
t id®pillanatban nem minden gép foglalt, és van egy Ji nem ütemezett ri ≤ t rendelkezésre állási id®vel, akkor azt az ehhez hasonló tulajdonságú munkát ütemezzük, amelynek kisebb a határideje. A következ® algoritmus a P |pj = 1, ri ∈ Z|Lmax megoldását adja, ahol K a legkisebb index¶ szabad gép indexe t-ben; m a gépek száma; M azon munkák halmaza, amelyek még nincsenek ütemezve, de elérhet®ek t-ben; és j az
ban, ha egy adott munka
ütemezett munkák számlálója.
2.3.1. Algoritmus. P |pj = 1, ri ∈ Z|Lmax 1.
j := 1, K := 1; j ≤ n DO
2. WHILE 3.
BEGIN
4.
K := 1; t := rj ; M := {Ji | ri ≤ t}; WHILE M 6= ∅ DO
5. 6.
BEGIN
7.
11.
Ji munkát a legkisebb határid®vel M -ben M := M \{Ji }; Ütemezzük Ji -t a t id®ben az MK gépre j := j + 1; IF K + 1 ≤ m THEN K := K + 1
12.
ELSE
Keressünk
8. 9. 10.
13.
BEGIN
14. 16.
t := t + 1; K := 1; M := M ∪ {Ji | ri ≤ t}
17.
END
15.
18.
END
20.
END
2.3.2. Példa.
Példa a
P |pj = 1, ri ∈ Z|Lmax -ra: = 1, K = 1), akkor el®ször t = 0 és M = {J1 , J2 }, munka, M = {J2 }. J1 -et ütemezzük t = 0-ban az M1
Ha elkezdjük az algoritmust futtatni (j így
J1
lesz a legkisebb határidej¶
17
j = 2, K = 2. Mivel M nem üres, megint megnézzük melyik a legkisebb határidej¶ munka, ami a J2 , ezt ütemezzük t = 0-ban az M2 gépen, j = 3, de mivel 3 2, ezért belépünk az ELSE részbe, t = 0 + 1 = 1, K = 1, M = {J3 }. Így J3 -mat ütemezzük t = 1ben az M1 gépen, j = 4, K = 2, viszont így M = ∅, így visszamegyünk a 2. lépésig. Itt K = 1, t = 2 és M = {J4 , J5 }. Itt keressük a legkisebb határidej¶ munkát, de egyenl®ek, ezért bármelyiket választhatjuk. Ütemezzük J4 -et t = 2-ben az M1 gépen, így M = {J5 }, j = 5, K = 2. Végül ütemezzük J5 -öt t = 2-ben az M2 gépen. gépen,
2.8. ábra. Példa az algoritmus m¶ködésére
P |pj = 1, ri ∈ Z|Lmax
A bels® WHILE ciklus olyan munkablokkokat alkot, amelyek állási id® nélkül vannak ütemezve a gépeken, az ütemezett munkák között. Miután egy ilyen blokk befejez®dik, a jelenlegi
rj
érték a kezd® id® a következ® blokkban.
Az algoritmus helyességét a következ®képpen bizonyíthatjuk. Legyen S az algoritmus által ∗ konstruált ütemezés és jelöljük S -gal az optimális ütemezést a következ® tulajdonságokkal:
•
az els® S ∗ -ban
• r−1
r−1
munka, ami
S -ben
ütemezve van, ugyanakkor van ütemezve
S -ben
és
maximális
munka ütemezve van S -ben, valamilyen t id®ben, míg Jr valamilyen kés®bbi ∗ ∗ id®ben van ütemezve S -ban (hiszen r − 1 maximális). Ha van olyan gép S -ban amelyen Így, a
Jr
t id®ben állási id® van, Jr áthelyezhet® arra a gépre a t id®be. Másrészt, létezik egy munka, Jk dr ≤ dk határid®vel, amelyet S ∗ -ban a t id®ben ütemeztünk, de S -ben nem. Ekkor ∗ ∗ cseréljük ki Jk -t és Jr -t S -ban. Mindkét esetben S optimális marad, ami ellentmond r − 1 maximalitásának.
2.3.3. Megjegyzés.
Ha a rendelkezésre állási id®k nem egészek (hanem például racio-
nálisak), akkor ez az algoritmus nem ad optimális ütemezést. Ezt a 2.9 példával szemléltethetjük.
A következ®ekben megnézzük, hogy mi történik, ha a rendelkezésre állási id®k valós számok. A jelölés egyszer¶sítése érdekében jelöljük a munkákat
1, 2 . . . , n-el
helyett. El®ször is bevezetünk egy jelölést a listás ütemezésre. A lista egy
18
J1 , J2 , . . . , Jn π permutáció:
a
2.9. ábra. Példa az algoritmus helytelenségére racionális rendelkezésre állási id®kkel
π(1), π(2), . . . , π(n)
minden munkára. A ciklikus listás ütemezés megadható a következ®
algoritmussal. Az algoritmus a gépeket pontját jelöljük
t(j)
j.
jelölje a
x(i)-vel;
1. FOR
h(i)
jelölje azt a gépet, amelyen az
i.
i.
munka kezdési id®-
munka ütemezve van; és
A ciklikus listás ütemezés algoritmusa
j := 1 TO m DO t(j) := 0; i := 1 TO n DO
3.
BEGIN
4. 6.
i. munkát a h(i) = i x(i) := max{t(h(i)), ri )} id®ben t(h(i)) := x(i) + 1
7.
END
5.
számozza. Az
gépen az utolsó munka befejezési idejét.
2.3.4. Algoritmus. 2. FOR
a
0-tól m − 1-ig
Ütemezzük az
(mod
m)
gépen
A következ® lemma megmutatja, hogy elegend® csak a ciklikus listás ütemezést vizsgálni, ha a probléma
P |pi = 1, ri , di |f
2.3.5. Lemma.
alakú az
f
reguláris célfüggvénnyel.
Legyen f egy reguláris célfüggvény, és tegyük fel, hogy
P |pi = 1, ri , di |f -
nek van egy megengedett megoldása. Ekkor mindig létezik ciklikus listás ütemezés ami optimális.
Bizonyítás.
Meg kell mutatnunk, hogy bármely megengedett megoldást
(x(i), h(i))
át
lehet alakítani egy lehetséges ciklikus listás ütemezéssé, anélkül, hogy növelnénk a célfüggvény értékét. Egy ilyen transzformáció két lépésben végrehajtható. Az els® lépésben meg kell cserélnünk a gépeket, amelyeken a munkák a következ®képpen vannak ütemezve. Tekintsük a
π
permutációt
x(π(1)) ≤ x(π(2)) ≤ . . . ≤ x(π(n))
19
Ütemezzük a
π(k)
munkát a
k
(mod
m)
gépen. A megfelel® ütemezésben nincs átfedés
azonos gépeken lév® munkákon. Ez a következ®kb®l látszik. Feltételezzük, hogy két munka
π(i0 )
ahol io = jm + k és i1 = lm + k (l > j) átfed egy I intervallumot. x(π(i0 )) ≤ x(π(i)) ≤ x(π(i1 )) minden io ≤ i ≤ i1 -re és a megmunkálási id® minden munkára egyenl® 1-el. Ezért minden π(i) munka (io ≤ i ≤ i1 ) ütemezve van az I intervallumon. Ez ellentmond az (x(i), h(i)) megengedettségének, mert van legalább m + 1 π(i) munka (io ≤ i ≤ i1 ). és
π(i1 ),
Tudjuk, hogy
A második lépésben az új ütemezést átalakítjuk egy listás ütemezéssé, amely ellentmond a
π -nek,
úgy hogy csökkentjük az összes munka kezdési idejét
célfüggvény nem n® a transzformáció során.
20
x(π(i))-t.
Ezért a reguláris
3. fejezet
Uniform gépes ütemezések
Q|pmtn|Cmax
3.1.
El®ször egy
ω
alsó korlátot adunk a probléma célfüggvény értékére. Majd a második
lépésben egy olyan algoritmust adunk, amely
Pi = p 1 + . . . + p i minden
i = 1, . . . , n
és
j = 1, . . . , m-re.
és
ω
hosszú ütemezést ad. Legyen
Sj = s1 + . . . + sj
Tegyük fel, hogy
n ≥ m.
n leggyorsabb gépet kell gyelembe vennünk. Ahhoz, hogy [0, T ] intervallumban a következ® szükséges feltétel adható:
az a
Hogyha
n < m
csak
összes munkát ütemezzük
Pn = p1 + . . . + pn ≤ s1 T + . . . + sm T = Sm T vagy
Pn /Sm ≤ T Hasonlóan,
Pj /Sj ≤ T -nek
is teljesülnie kell minden
J1 , . . . , Jj
alacsonyabb korlát az ütemezés hosszára, a
j = 1, . . . , m-re,
mivel
Pj /Sj
munkákra nézve. Így
m
ω := max{max Pj /Sj , Pn /Sm }
(3.1)
j=1
az alsó korlát a
Cmax
egy
értékére.
A következ®ekben egy olyan ütemezést hozunk létre, ami teljesíti ezt a korlátot. A megfelel® algoritmust level algoritmusnak nevezzük, amely kiszámolja a fennmaradó megmunkálási id®ket és beosztja a munkákat. Adjunk egy részütemezést a fennmaradó megmunkálási id® jelöli, az mezve
t
el®tt. A
t
i
munka
t
id®re, a
pi
t
ideig; a
a
azt a részét ami nincs üte-
id®ben a level algoritmus a folyamatot úgy hívja, hogy assign(t), ami
beosztja a munkákat a gépekhez. A gépek ezzel a beosztással futnak, amíg beosztás kész
pi (t)
s-ben,
és a folyamat megismétl®dik.
21
s > t.
Az új
Id®intervallumonként különböz® munkacsoportokat rendelünk a gépekhez, amit a következ®képpen tehetünk meg:
3.1.1. Algoritmus. 1. 2.
Assign(t) algoritmus
J := {i|pi (t) > 0}; M := {M1 , . . . , Mm }; J -ben
3. Állítsuk be minden munkát
M -ben
és minden gépet
nem beosztottnak;
4. WHILE vannak nembeosztott munkák és gépek DO 5.
BEGIN
6.
Keressük meg azt az
7.
aminek a legnagyobb a fennmaradó megmunkálási ideje;
8.
12.
r := min{|M |, |I|}; Osszuk be az I -ben lév® munkákat együttesen r leggyorsabb gépre J := J \I ; Távolítsuk el az r leggyorsabb gépet M -b®l;
13.
END
9. 10. 11.
I⊆J
halmazát a munkáknak
ütemezve az
M -ben
lév®
Ha az Assign(t) lefutott, akkor egyrészt meg kell adjuk, hogyan számolható ki a fennmaradó megmunkálási id® másrészt, hogy meddig áll fenn ez a csoportbeosztás. Tegyük fel, hogy a a
b
j
id®pillanatig (és
munka az
a
Md , Md+1 , . . . , Md+u
gépeken fut, egy
egy tetsz®leges id®pont még a
b
(b − a) ·
k
elem¶ csoportban
el®tt), ekkor:
d+u P
si
i=d
pj (b) = pj (a) −
(3.2)
k
képlettel számolható a fennmaradó megmunkálási id®. A csoportok addig az els®
•
vagy valamelyik
•
vagy
Ekkor
∃j, l
s-nél
j -re
munkapár:
s a
id®pillanatig futnak együtt, amíg:
pj (s) = 0
lesz
pj (t) > pl (t)
lezárjuk a csoportokat, és
de a
s-nél
pl (s) = pj (s) újrakezdjük a beosztást (ha még van pozitív
fennmaradó megmunkálási idej¶ munka). A csoportok létrejötte után, a konkrét ütemezést kell elkészíteni. Ha egy vallumban
k
munka van egy csoportban, akkor ezt az intervallumot
k
[a, b]
id®inter-
részre felosztva a
munkákat lépcs®sen elhelyezve, kapjuk meg az ütemezést.
3.1.2. Példa. Legyen
A következ® példán keresztül fogom szemléltetni az algoritmus m¶ködését.
n = 6, m = 2, p(0) = [24, 20, 12, 10, 5, 4]
Ekkor az algoritmus el®ször a pedig a
J2 -t,
J1
és
s = [4, 1].
munkát fogja kiválasztani, berakja az els® gépre, majd
amit pedig a második gépre, ®k két külön csoportot alkotnak. Tudjuk, hogy
22
addig tart ez a csoport, amíg az egyik
0
nem lesz, vagy pedig az egyik utoléri a mási-
kat. Lesz egy olyan pont, ahol a gyorsabb gépen lév® munka fennmaradó megmunkálási ideje egyenl® lesz a lassabb gépen futó munkáéval. Ezt az id®pontot a következ®képpen számolhatjuk ki:
24 − 4x = 20 − x 4 x= 3 4 id®pillanatig fut ez a két csoport, majd új csoportokat kell kiszámolnunk (3.1 3 ábra). Ekkor p(4/3) = [56/3, 56/3, 12, 10, 5, 4]. Ezután az algoritmus a J1 -et és J2 -®t fogja
Tehát
egy csoportba választani (hiszen ®k a két legnagyobb fennmaradó megmunkálási id®vel rendelkez® munkák). Addig futhatnak, amíg az egyik nem lesz
0, vagy nem érnek utol egy
másik munkát. Az utóbbi fog bekövetkezni. Ekkor azt kell kiszámolnunk, hogy mi ez az id®pillanat amikor ez bekövetkezik. Ezt pedig a (3.2) képlettel számolhatjuk ki.
3.1. ábra. Csoportok létrehozása
56 (b − 34 ) · 5 − = 12 3 2 12 b= =4 3 4 id®pillanatig fut együtt. És így tovább minden csoportot kiszámolunk. p(4) = [12, 12, 12, 10, 5, 4], p(26/5) = [10, 10, 10, 10, 5, 4], p(46/5) = [5, 5, 5, 5, 5, 4], p(51/5) = [4, 4, 4, 4, 4, 4]
Tehát ez a csoport a
Végül kiszámoljuk, mikor válnak
0-vá,
4−
azaz fejez®dnek be a munkák.
(b −
51 ) 5
·5
6
=0
b=
75 = 15 5
Már csak az marad hátra, hogy elkészítsük az ütemezést, ez pedig a 3.2 ábrán látható.
23
3.2. ábra. Ütemezés a létrehozott csoportokkal
3.1.3. Tétel. Bizonyítás.
A level algoritmus optimális megoldást ad a
Mivel
Q|pmtn|Cmax
feladatra.
m
ω := max{max Pj /Sj , Pn /Sm } j=1
egy alsó korlátja az ütemezés hosszának, elég megmutatni, hogy ez az ütemezés eléri ezt a korlátot. Tegyük fel, hogy a level algoritmus elején
p1 (0) ≥ p2 (0) ≥ . . . ≥ pn (0).
Ez a sorrend nem
változtat meg semmit az algoritmus futása alatt, így:
p1 (t) ≥ p2 (t) . . . ≥ pn (t)
minden
t-re
(3.3)
Tegyük fel, hogy az algoritmus mindig ebben a sorrendben osztja be a munkákat a gépekhez. Ahhoz, hogy bizonyítsuk a kívánt tulajdonságot, el®ször fel kell tennünk, hogy nincs olyan gép ami áll, miel®tt minden munka befejez®dne, mondjuk ezt
T (s1 + . . . + sm ) = p1 + p2 + . . . + pn Így az algoritmussal elértük a
ω
vagy
T
id®nek. Ekkor:
T = Pn /Sm
korlátot.
Ha van egy gép, ami áll miel®tt az utolsó munka befejez®dne, akkor az id®kre az
M1 , . . . , Mm
gépeken:
f1 ≥ f2 ≥ . . . ≥ fm Ha
f1 , . . . , fm befejezési
(3.4)
fi < fi+1 valamilyen 1 ≤ i ≤ m − 1-re, az utolsó munka szintje Mi -n van ütemezve fi − id®ben, ahol > 0 kell®en kicsi, kisebb szintje van, mint az utolsó Mi+1 -
valamilyen
en lév® munka szintje ugyanabban az id®ben. Ez egy ellentmondás, mivel azt mondtuk, hogy az algoritmus mindig a (3.3) alapján ossza be a munkákat. Ráadásul (3.4)-ben van legalább egy szigorú egyenl®tlenség.
T := f1 = f2 = . . . = fj > fj+1 ahol j < m. Figyeljük meg, hogy ez a j leghosszabb munka végig az r leggyorsabb gépen fut (esetleg más csoportokon), mert ha nem így lenne, akkor az egyik megel®zné a másikat, ami tudjuk, hogy nem lehetséges.
Tegyük fel, hogy
24
Q|pmtn, ri|Lmax
3.2.
Az alábbi algoritmus A. Federgruen és G. Groenevelt munkája ([9]). El®ször azt kell látnunk, hogy a legjobb megoldás a feladatra, egy olyan ütemezés, ahol minden id®,
di
i
munka az
[ri , di ]
intervallumon van megmunkálva, ahol
ri
a rendelkezésre állási
pedig a határid®. Az ilyen ütemezéseket megengedettnek nevezzük az
[ri , di ]-re
vonatkozólag. A második lépésben, bináris keresést alkalmazunk, hogy megoldjuk az általános problémát.
3.3. ábra. Hálózat
3.4. ábra. Hálózat b
25
3.5. ábra. Hálózat a
A megengedettségi problémát úgy oldjuk meg, hogy visszavezetjük egy hálózati folyam feladatra. Legyen:
t1 < t2 < . . . < tr a különböz®
rj
di értékek rendezett sorozata, és de niáljuk IK := [tK−1 , tK ], ahol K = 2, . . . , r-re. Majd terjesszük ki a hálózatot (3.3 ábra), a következ®
és
TK = tK − tK−1 módon. Legyen IK egy tetsz®leges invervallum csomópont, mint az 3.3 ábrán, és jelöljük Ji1 , Ji2 , . . . , Jis -sel az IK csomópont el®deit. Ekkor kicseréljük az alhálózatot (3.5 ábra), amit IK , Ji1 , Ji2 , . . . , Jis -sel de niáltunk, a kiterjesztett hálózatra, ami a 3.4 ábrán látszik. Tegyük fel, hogy a gépek nemnövekv® sorrendben vannak a sebességük szerint.
s1 ≥ s2 ≥ . . . ≥ sm Továbbá legyen
sm+1 = 0.
A kiterjesztett alhálózat úgy épül fel, hogy hozzávesszük az
IK , Ji1 , Ji2 , . . . , Jis csúcsokhoz a (K, 1), (K, 2), . . . , (K, m) csúcsokat. Minden j = 1, . . . , mre megy él (K, j)-b®l IK -ba, j(sj − sj+1 )TK kapacitással. Emellett minden ν = 1, . . . , s-re és j = 1, . . . , m-re megy él Jiν -b®l (K, j)-be, (sj − sj+1 )TK kapacitással. Minden IK -ra van ilyen kiterjesztés. Továbbá fenntartjuk az éleket s-b®l Ji -be pi kapacitással, és az éleket IK -ból t-be mTK kapacitással. Az így kapott hálózatot nevezzük kiterjesztett hálózatnak. A következ® tétel megmutatja, hogy letudjuk ellen®rizni a megengedettséget azzal, hogy megoldjuk a maximális folyam feladatot a kiterjesztett hálózatra.
3.2.1. Tétel.
A következ® tulajdonságok ekvivalensek
(a)
Létezik megengedett ütemezés.
(b)
A kiterjesztett hálózatban létezik
s-b®l t-be
folyam
n P i=1
26
pi
értékkel.
Bizonyítás. b⇒a Tekintsünk egy folyamot
n P
pi
értékkel a kiterjesztett hálózatra. Jelöljük
i=1 folyamot ami
Ji -t®l IK -ig megy. Ekkor
minden egyes részhalmaz
A⊆
n P r P
xiK =
i=1 K=2 {1, . . . , n}-re:
X
n P
xiK -val az egész
pi . Elegend® megmutatni azt, hogy
i=1
xiK ≤ TK h(A)
i∈A Ahol:
h(A) =
S|A| Sm
ha
|A| ≤ m
különben
Ez azt jelenti, hogy a 3.2.1 tétel fennáll, és a futási követelményeket tudjuk
x1K , . . . , xnK
ütemezni
IK -ban (K = 2, . . . , r).
Tekintsük a kiterjesztett hálózatban azt az alhálózatot, ami A által indukált, illetve a megfelel® részfolyamot. A részfolyam min{j(sj
(K, j)-n
átmen® részére a következ® korlát adható:
− sj+1 )TK , |A|(sj − sj+1 )TK } = TK (sj − sj+1 )min{j, |A|}
Így:
X i∈A
xiK ≤ TK
m X
(sj − sj+1 )min{j, |A|} = TK h(A)
Az el®z® egyenl®tlenség a következ®képpen látható. Ha
m X
min{j, |A|}(sj
(3.5)
j=1
|A| > m
akkor:
− sj+1 ) = s1 − s2 + 2s2 − 2s3 + . . . + msm − msm+1 = Sm = h(A)
j=1
Különben:
m X
min{j, |A|}(sj
− sj+1 ) =
j=1
= s1 − s2 + 2s2 − 2s3 + . . . + (|A| − 1)s|A|−1 − (|A| − 1)s|A| + +(|A|)(s|A| − s|A|+1 + s|A|+1 − . . . − sm + sm − sm+1 ) = = S|A| = h(A) a⇒b 27
Tegyük fel, hogy létezik megengedett megoldás. Legyen
xiK
az a munkamennyiség, amelyet
i munka teljesít az IK intervallumban, a megengedett megoldás szerint (i = 1, . . . , n és K = 2, . . . , r). Ekkor minden K = 2, . . . , r-ra és tetsz®leges A ⊆ {1, . . . , n} halmazokra,
az
az egyenl®tlenség fennáll:
X
xiK ≤ TK h(A)
(3.6)
i∈A
i = 1, . . . , n-re pi =
r P
xiK , hiszen xiK az IK intervallumban teljesített munka. K=2 Az maradt hátra, hogy megmutassuk, hogy lehetséges olyan folyamot létrehozni a kiTovábbá,
IK -ba (i = 1, . . . , n és K = 2, . . . , r). Egy elégséges feltétel az ilyen folyam létezésére, hogy tetsz®leges A ⊆ {1, . . . , n} r P halmazra és K = 2, . . . , r -ra az xiK értéke korlátolt az alhálózatban lév® folyam miterjesztett hálózatba, amelynek értéke
nimális vágásával (ahol a forrás
K=2 Ji (i
Tk
m X
xiK ,
∈ A)
és
Ji -b®l
és a nyel®
min{j, |A|}(sj
megy
IK ).
Ez az érték:
− sj+1 )
j=1 Felhasználva a (3.6) egyenletet és az (3.5) egyenl®tlenség jobb oldalát, ezt kapjuk:
X
xiK ≤ TK h(A) = Tk
m X
min{j, |A|}(sj
− sj+1 )
j=1
i∈A ami teljesíti az egyenl®tlenséget.
Mivel a maximális folyam a kiterjesztett hálózatban
O(mn3 )
id®ben számolható, így a
megengedettség vizsgálata is hasonló id®ben végezhet®. Ahhoz hogy megoldjuk a felada3 tunkat bináris keresést kell végeznünk. Ez egy -közelít® algoritmust ad, ami O(mn (logn+ id®ben megoldható, mivel Lmax korlátja: n · max pi , ha s1 = 1. i i Mivel az (3.6) fenáll minden K -ra, a részmunkákat az xiK 1futási követelménnyel1 üte-
log(1/) + log(max pi ))
IK -n egy ismert algorimussal. A Q|P M T N, ri |Cmax speciális esete a Q|P M T N, ri |Lmax -nak, így biztosan megtudjuk oldani, de Labetoulle, Lawler, Lenstra és Rinnoy Kan kifejlesztettek egy O(nlogm + mn)-algoritmust erre a speciális esetre.
mezni tudjuk az
3.3.
Q||
P
Tegyük fel, hogy
Ci
i1 , i2 , . . . , ir
azon munkák sorrendje, amelyek az
mezve. Ekkor ezen munkák hozzájárulása a célfüggvényhez az
pi1
r−1 1 r + p i2 + . . . + pir sj sj sj 28
Mj
Mj
gépen vannak üte-
gépen:
Ez azt jelenti, hogy egy optimális ütemezésben a munkák az
Mj
gépen
pi
szerint nem-
csökken® sorrendben vannak rendezve. Ahhoz, hogy találjuk egy optimális megoldást a következ®ket kell tennünk.
1 1 , . . . , s1m , Legyen t1 , . . . , tn nemcsökken® sorrendje az n legkisebb számnak amiket az { , s1 s2 2 2 , , . . . , s2m , s31 , . . .} halmazból választunk. Ha ti = skj akkor ütemezzük az i munkát az s1 s2 Mj gépen, úgy mint a k. utolsó munka, mivel feltesszük, hogy p1 ≥ p2 ≥ . . . ≥ pn . Ezek
Πj -vel azon (j = 1, . . . , m).
az ötletek a következ® algoritmushoz vezetnek, jelöljük
Mj gépen P Q|| Ci
amelyek jelenleg ütemezve vannak az
3.3.1. Algoritmus. 1. FOR 2. 3. FOR
j=1
Algoritmus
m DO BEGIN Πj := ∅; wj := i := 1 TO n DO
munkák sorrendjét,
TO
1 END; sj
4.
BEGIN
5.
Keressük meg a legnagyobb
6. 7.
Πj := i ◦ Πj ; wj := wj + s1j
8.
END
m
Az algoritmus befejeztével kapott
Πj
j
indexet amelyre
wj := min wν ; ν=1
sorozatok megmutatják, hogy melyik gépen milyen
sorrendben kell a munkákat ütemezni. Ezáltal könnyen elkészíthetjük az ütemezést.
w érték kiszámítható O(logn) lépésben ha használjuk O(nlogm) id®ben számolhatjuk, ha a pi -k rendezve vannak.
Minden minimális Így, az egész
3.3.2. Példa.
a priority sort.
A 3.6 ábrán látható feladatot vizsgáljuk. Az algoritmus els® két lépésében a
Πj -ket üressé tesszük, hiszen kezdetben egyik munka sincs ütemezve. Emellett kiszámoljuk a wj értékeket, ami w1 = 2, w2 = 1, w3 = 1/2. Ezután belépünk a második FOR ciklusba. El®ször i = 1 (a munkák a megmunkálási id® alapján nemnövekv® sorrendben vannak), m
j = 3 lesz a legnagyobb olyan index amelyre wj := min wν teljesül. Ekkor Π3 = 1 és ν=1 w3 = 1. Ezután j = 2-re ugyanezt megnézzük; itt szintén j = 3 lesz a jó, ezért Π3 = 2,1 és w3 = 1.5. Majd i = 3-ra j = 2 lesz a megfelel®, így Π2 = 3 és w2 = 2. Ezt követ®en i = 4-re j = 3, tehát Π3 = 4,2,1, w3 = 2. Végül i = 5-re is a j = 3 lesz a megfelel®, így az utolsó munka is a helyére kerül: Π3 = 5,4,2,1 (az ütemezés 3.6 ábrán megtekinthet®).
a
3.4.
Q|pmtn|
P
A következ® algoritmus
Ci
4
ember nevéhez kapcsolódik: J. Labetoulle, E.L. Lawler, J.K.
Lenstra, A.H.G. Rinnooy Kan ([7]). Ahhoz, hogy megoldjuk ezt a feladatot, az SPT szabály egy változatát kell alkalmaznunk. Rendezzük a munkákat
pi
szerint nemcsökken® sorrendbe, és ütemezzük minden egyes
29
3.6. ábra. Példa
Q||
P
Ci
n M1 gépen, addig amíg t1 = pn /s1 . Majd ütemezzük az n−1 munkát els®ként az M2 gépen t1 -ig, majd az M1 gépen t1 -t®l t2 ≥ t1 amíg kész nem lesz. Az n − 2 munkát ütemezzük az M3 gépen t1 majd az M2 gépen t2 − t1 -ig, és M1 gépen t2 -t®l t3 ≥ t2 -ig amíg kész nem lesz, stb. Vegyük észre a példában a lépcs®s mintát (3.7). munkát megszakításokkal, hogy minimalizáljuk a befejezési id®t. Azaz, ütemezzük az munkát a leggyorsabb
3.4.1. Példa. m = 3 s1 = 3 s2 = 2 s3 = 1 n P= 4 p1 = 10 p2 = 8 p3 = 8 p4 = 3 Cj = 14
Q|pmtn|
3.7. ábra. Példa
P
Ci
A fenti leírás a következ® algoritmust adja, ami egyidej¶leg tölti fel a gépeket egyik periódus után a másikat.
3.4.2. Algoritmus. 1.
Algoritmus
Q|pmtn|
Ci
a := 0;
2. WHILE
p1 > 0
DO
3.
BEGIN
4.
Keressük meg a legnagyobb
5.
∆t := pi /s1 ; FOR ν := i DOWN
6.
P
7.
BEGIN
8.
Ütemezzük a
ν
TO
i
indexet,
pi > 0;
k := max{1, i − m + 1}
munkát az
M1+i−ν 30
DO
gépen az
[a, a + ∆t]
intervallumban;
9.
pν := pν − ∆t · s1+i−ν
10.
END
11.
a := a + ∆t
12.
END
3.5.
Q|pi = 1|
P
fi
és
Q|pi = 1|fmax
A következ® algoritmus Graham, Lawler, Lenstra, Rinnooy Kan munkássága ([10]). Ebben a részben, azt a problémát gondoljuk meg, amikor munkát ütemezünk
m
n
n
egység megmunkálási idej¶ n P uniform gépen, s1 , s2 , . . . , sm sebeséggel. A célfüggvény fi (Ci ) i=1
ahol fi (Ci ) monoton nemcsökken® függvény, ami az i. munka i=1 idejét®l függ. Ez a két probléma megoldható polinomális id®ben.
és
max fi (Ci ),
Ci
befejezési
El®ször is gyeljük meg, hogy létezik optimális megoldás, amelyben a munkák id®intervallumokban fejez®dnek be, az fejezési id®ket (j
O(n · logn)
= 1, . . . , m)
n
legkorábbi lehetséges befejezési id®kkel. Ezeket a be-
id®ben generálhatjuk. Készítsünk egy növekv® sorozatot
befejezési id®kkel és általános lépésként, töröljük a legkisebb befejezési
id®t a sorból. Ha a legkisebb befejezési id® a Ezáltal megkapjuk az
3.5.1. Példa.
1/sj
n
k/sj
akkor
(k + 1)/sj -t
beszúrjuk a sorba.
legkorábbi lehetséges befejezési id®ket.
5 db egységnyi idej¶ munkánk van, és 4 db gépünk (s1
= 2, s2 = 1/2, s3 =
1, s4 = 3) sebességekkel. Ekkor beírjuk minden gépre, a lehetséges befejezési id®ket, ahogy 1/sj (j = 1, . . . , m)
a 3.8 ábrán látszik. Majdpedig az algoritmus alapján, kiszámoljuk az
értékeket. Ez 1/3, 1/2, 1, 2 (növekv® sorrendben). Ekkor töröljük a legkisebbet (1/3) és betesszük a sorba a 2/3-ot. A következ® legkisebb az 1/2, helyére jön az 1. A következ® legkisebb a 2/3, helyére jön az 1. Most már 1, 1, 1, 2 a sorunk. Ekkor eldönthetjük, hogy melyik egyes kerüljön ki. Így megkaptuk az 5 legkorábbi lehetséges befejezési id®t.
3.8. ábra. Példa
Legyen
t1 , . . . , tn
az
n
Q|pi = 1|
P
fi (Ci )
legkisebb befejezési id® nemcsökken® sorrendben.
31
A
Q|pi = 1|
P
fi egy optimális megoldását úgy kaphatjuk meg, ha megoldunk egy n×n-es súlyú teljes párosítás feladatot, ahol az élek súlya cik = fi (tk ) (i, k = 1, . . . , n).
minimális 3 Ez O(n ) id®ben megoldható. Ahhoz hogy megoldjuk a
Q|pi = 1|fmax
feladatot ([10]), a következ® algoritmust használ-
hatjuk.
3.5.2. Algoritmus. 1.
Algoritmus
J := {1, . . . , n} i := n DOWN
2. FOR 3.
Q|pi = 1|fmax
TO 1 DO
BEGIN
4.
Keressük meg azt a
5.
Ütemezzük a
6.
J := J \{j}
7.
END
j
j∈J
munkát, amelyre
fj (ti ) minimális; ti -ben;
munkát, hogy befejez®djön a
P Q|pi = 1| wi Ci megoldható úgy, hogy hozzárendeljük a k . legnagyobb súlyú munkát a tk -hoz. A Q|pi = 1|Lmax pedig megoldható egy párosítással, hogy a k . legkisebb határid®t rendeljük a tk hoz. Ezek megoldhatóak O(n · logn) id®ben.
Van pár speciális eset, amit gyorsabban meg tudunk oldani. Például a
32
4. fejezet
Független gépes ütemezések
4.1. Az
R|pmtn|Cmax, R|pmtn|Lmax, R|pmtn, ri|Lmax
R|pmtn|Cmax
feladatot két lépésben oldjuk meg. Az els® lépésben megfogalmazunk
egy lineáris programozási feladatot, hogy kiszámoljuk minden id®k összegét
tij -t,
ami az
i
munka a
j
i
munkára és
j
gépre, az
gépen töltött ideje egy optimális ütemezésben. A
második lépésben konstruáljuk a megfelel® ütemezést.
R|pmtn|Cmax meghatározott a pij nm darab van, és megmutatja az i munka teljes megmunkálási idejét az Mj gépen. Legyen tij az i munka megmunkálási idejének azon része, amelyet Mj n ütemezünk. Ekkor tij /pij az a részid®, amelyet az i munka a j gépen tölt, és a következ® egyenl®ségnek fenn kell állnia, annak érdekében, hogy az i munka befejez®djön. El®ször adjuk meg a lineáris programozási formulát. Az egész számokkal amib®l
m X tij =1 p ij i=1 Így megkapjuk az LP feladatunkat:
minCmax m X
tij = 1, pij
i = 1, . . . , n
(4.1)
tij ≤ Cmax ,
i = 1, . . . , n
(4.2)
tij ≤ Cmax ,
j = 1, . . . , m
(4.3)
tij ≥ 0,
i = 1, . . . , n;
i=1 m X j=1 m X i=1
33
j = 1, . . . , m.
Az (4.2) baloldala azt mondja meg, hogy az gépen. Az (4.3) bal oldala az
Mj
i
munka mennyi id®t töltött el az összes
gépen ütemezett munkák megmunkálási idejének összegét
mutatja meg. Jegyezzük meg, hogy egy optimális megoldás erre a lineáris programozási feladatra:
n
Cmax = max{max i=1
m X
m
tij , max
j=1
n X
j=1
tij }
(4.4)
i=1
Megtalálni egy megfelel® ütemezést, ekvivalens azzal, hogy megtaláljuk a megoldását, egy
O|pmtn|Cmax
4.1.1. Tétel.
feladatnak, a
Az
megmunkálási id®kkel (i
O|pmtn|Cmax
4.1.2. Következmény. R|pmtn|Cmax
tij
= 1, . . . , n, j = 1, . . . , m).
megoldható polinomiális algoritmussal.
Az 4.1.1 tétel alapján, és a korábbi megjegyzésünk miatt az
is megoldható polinomiális id®ben.
Hasonlóan oldjuk meg az hogy minimalizáljuk
R|pmtn|Lmax -ot. Megadunk egy lineáris programozási feladatot,
Lmax -ot.
Tegyük fel, hogy a munkák nemcsökken® határid® szerint
vannak rendezve:
d1 ≤ d2 ≤ . . . ≤ dn (1)
gép az i munkával tölt, az I1 = [0, d1 + Lmax ] (k) intervallumon. Továbbá, k = 2, . . . , n, legyen tij az az összes id®, amelyet Mj gép az i munkával tölt, az Ik = [dk−1 + Lmax , dk + Lmax ] intervallumon. Ekkor a következ® LP-
Legyen
tij
az az összes id®, amelyet
Mj
feladatot kell megoldanunk:
minLmax (k) m X i X tij i=1 k=1 m X
pij
= 1,
i = 1, . . . , n
(1)
i = 1, . . . , n
(k)
i = 1, . . . , n;
(1)
j = 1, . . . , m
(k)
j = 1, . . . , m;
(k)
i, k = 1, . . . , n;
tij ≤ d1 + Lmax ,
j=1 m X
tij ≤ dk − dk−1 ,
k = 2, . . . , n
j=1 n X
tij ≤ d1 + Lmax ,
i=1 n X
tij ≤ dk − dk−1 ,
k = 2, . . . , n
i=k
tij ≥ 0,
34
j = 1, . . . , m.
Lmax -optimális ütemezése kapható azáltal, hogy minden id®intervallumra Ik (k = 1, . . . , n) egy megfelel® ütemezést konstruálunk (k) az adatokkal, amelyeket a Tk = (tij ) mátrix ad. Tehát ez a feladat is polinomiális id®ben Az LP-feladatra egy optimális megoldást adva, az
megoldható. Hasonló módon oldhatjuk meg a
R|pmtn, ri |Lmax
feladatot, ami a következ® ember nevé-
hez f¶z®dik: E.L. Lawler, J. Labetoulle ([8]). Legyenek a
[tk , tk+1 ]
intervallumok, ahol
t1 < t2 < . . . < tr rendezett sorrendje az ri és di + Lmax értékeknek. Ebben az esetben, a változók (k) Lmax , ahol tij az i munka Mj gépen töltött ideje a [tk , tk+1 ] intervallumon.
35
(k)
tij
és
Irodalomjegyzék
[1] R.Gary Parker, Deterministic scheduling theory, Chapman & Hall, 1995, 83-87 és 112-116 [2] Jordán Tibor, Recski András, Szeszlér Dávid, Rendszeroptimalizálás, Typotex, 2004 [3] Peter Brucker Scheduling Algorithms, Springer, 1995, 103-106. oldal [4] E.G. Coman, Jr. and R.L. Graham, Optimal Scheduling for Two-Processor Systems, Acta Informatica, 1972, 200-2013 [5] R.L. Graham, Bounds on multiprocessing timing anomalies, 1969, 263-269 [6] Coman, Jr., E.G. (ed.) Computer & Job/Shop Scheduling Theory, 1976 [7] J. Labetoulle, E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan Preemptive scheduling
of uniform machines subject to release dates, in Progress in combinatorial optimization, Academic Press, 1984, 245-261 [8] E.L. Lawler, J. Labetoulle On preemptive scheduling of unrelated parallel processors
by linear programming, 1978 [9] A. Federgruen, G. Groenevelt Preemptive scheduling of uniform machines by ordinary
network ow techniques, Management Sci., 1986, 341-349 [10] R.L. Graham, E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan Optimization and
approximation in deterministic sequencing and scheduling, 1979, 287-326 [11] R.L. Graham Combinatorial scheduling theory, Springer, 1978
36
