Haliho 1

Kombinatorikus módszerek az ütemezéselméletben

Matematikus diplomamunka Vaik Zsuzsanna^{∗} Témavezető: Jordán Tibor

2003

Kivonat

Ebben a diplomamunkában néhány ütemezéselméleti problémát mutatok be. Olyan párhuzamos, illetve uniform gépekre adott ütemezési feladatokat nézek, melyeknél a munkák halmazán megelőzési feltételek adottak. Azaz a munkák halmazán adott egy irányított aciklikus gráf. Legtöbbször a cél az utolsó munka befejezési idejének minimalizálása, de olvashatunk néhány olyan példát is, melyben a maximális késést szeretnénk minimalizálni. Ezen feladatok általában már megelőzési feltételek nélkül is az 𝒩𝒫-nehéz problémák közé tartoznak. Azonban, ha még további feltételeket adunk a munkákra, vagy a gépekre, (például, hogy a munkák egységnyi idő alatt futnak, vagy a gépek száma meghatározott), abban az esetben polinom időben megoldhatóvá válhatnak. Ebben a dolgozatban a teljesség igénye nélkül bemutatom, hogy milyen sokféle módszert lehet alkalmazni az ütemezési feladatok megoldására: a gráfelmélet problémáitól kezdve a lineáris programozáson át szinte mindent.

∗ELTE TTK, Matematikus V., zsuzska@cs.elte.hu

Tartalomjegyzék

1. Bevezető 4 1.1. Fogalmak, jelölések . . . . . . . . . . . . . . . . . . . . . . . . 5

2. Párhuzamos gépek 8 2.1. P |prec, p_{j} = 1|C_{max} . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2. P |prec|C_{max} . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3. P 2|prec, p_{j} = 1|L_{max} . . . . . . . . . . . . . . . . . . . . . . . 11 2.4. P |tree, p_{j} = 1|C_{max} . . . . . . . . . . . . . . . . . . . . . . . . 13

2.4.1. P |tree, p_{j} = 1|C_{max} . . . . . . . . . . . . . . . . . . . 13 2.4.2. P |tree, p_{j} = 1|L_{max} . . . . . . . . . . . . . . . . . . . 14

2.5. P |outtree, r_{j}, p_{j} = 1| ∑ C_{j} . . . . . . . . . . . . . . . . . . . . 16 2.5.1. P |p_{j} = 1, r_{j}| ∑ C_{j} . . . . . . . . . . . . . . . . . . . . . 17 2.5.2. P n|p_{j} = 1, r_{j}| ∑ C_{j} . . . . . . . . . . . . . . . . . . . . 17

2.6. P |tree, p_{j} = 1|C_{max} és a matroid-fedés probléma . . . . . . . . 18

3. Uniform gépek 22 3.1. Q|prec|C_{max} . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.2. Q|prec|C_{max} mégegyszer . . . . . . . . . . . . . . . . . . . . . 29 3.3. Q|chains|C_{max} . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.4. Q2|chains, p_{j} = 1|C_{max} . . . . . . . . . . . . . . . . . . . . . . 36

3.4.1. Q2|chains, pmtn, p_{j} = 1|C_{max} . . . . . . . . . . . . . . 37 3.4.2. Q2|p_{j} = 1|C_{max} . . . . . . . . . . . . . . . . . . . . . . 37 3.4.3. Q2|chains, p_{j} = 1|C_{max} . . . . . . . . . . . . . . . . . . 38

1. Bevezető

A dolgozat 2. fejezetében olyan feladatokat mutatok be, melyeknél párhuzamos gépek vannak, azaz minden gép azonos tulajdonságú, azonos sebességgel működik, s bármely munkát bármely gépre ütemezhetünk. A fejezet első felében olyan problémákat nézek, melyeknél megelőzési feltételek adottak, és cél az utoljára véget érő munka befejezési idejének minimalizálása. Garey és Johnson [10] belátta, hogy ha nincsenek megelőzési feltételeink, a feladat már akkor is 𝒩𝒫-nehéz. Továbbá azt is belátták, hogy ha minden munka futási ideje egységnyi idejű, a feladat akkor sem lesz könnyebb. Ezt a problémát egy ismert 𝒩𝒫-nehéz gráfelméleti problémára vezették vissza. A következő alfejezetben bemutatom Graham [11] által adott listás ütemezést, amely 2-approximációs algoritmus a P |prec|C_{max} feladatra. A 2.3 fejezetben látható, amennyiben a gépek számára erős megkötést teszünk, (m = 2), akkor a feladat polinomiálisan megoldható, sőt Garey és Johnson algoritmusa [9] az általánosabb L_{max} célfüggvényre is optimális megoldást ad. A 2.5 fejezetben, a P |outtree, r_{j}, p_{j} = 1| ∑ C_{j} feladatban a munkák befejezési idejének összegét szeretnénk minimalizálni. Erre Brucker, Hurink és Knust adott algoritmikus megoldást. Végül a 2.6 fejezetben a P |tree, p_{j} = 1|C_{max} probléma és a matroid bázis fedési problémája közötti, Marcotte és Trotter [17] által bebizonyított összefüggést olvashatjuk. A matroidelmélet alapfogalmait a 1.1 fejezetben leírom, azonban csak érintőlegesen, amennyire a bizonyítás megértéséhez feltétlenül szükséges. Ha ezáltal felkeltettem a kedves olvasó érdeklődését a matroidok iránt, ajánlom figyelmébe Frank jegyzetét [8]. A 3. fejezetben uniform gépeken való ütemezési feladatok olvashatók, azaz a gépek nem feltétlenül azonos sebességűek. Ebben a fejezetben is olyan feladatokkal foglalkozom, ahol a munkák között megelőzési feltételek adottak. Q||C_{max} feladat szintén 𝒩𝒫-nehéz, (hiszen amennyiben minden sebesség egyenlő, visszajutunk a P ||C_{max} feladatra). Azonban erre a feladatra is adható egy 2-approximációs algoritmus, mely egy egyszerű listás ütemezésen alapuló algoritmus. Ennek segítségével könnyen adható a Q|chains|C_{max} esetre egy 2-approximációs algoritmus. Meglepő azonban, hogy a Q|prec|C_{max} feladat megoldására az eddig legjobb ismert approximációs algoritmus faktora 𝒪(\sqrt{log m}). Erre először Chudak és Shmoys adott egy lineáris programozáson alapuló algoritmust [6], majd Bender és Chekuri [1] adott egy másik algoritmust, mely a lineáris programozási feladat helyett a megelőzési gráf egy felbontását használja a munkák a gépekre való kijelöléséhez. Ezeket a bizonyításokat mutatom be a 3.1 ill. a 3.2 alfejezetekben. Végül a Q2|chain, p_{j} = 1|C_{max} feladatra bemutatom Brucker, Hurink és Kubiak [4] polinomiális algoritmusát.

Köszönöm témavezetőmnek, Jordán Tibornak, hogy felkeltette érdeklődésemet a kombinatorikus optimalizálás e területe iránt, és köszönöm, hogy már több, mint egy éve segít felkészülni a dolgozat megírására.

1.1. Fogalmak, jelölések

A szakdolgozatom néhány ütemezési feladatot mutat be. Nézzük hát, mit takar ez a fogalom, hogy ütemezés: Tegyük fel, hogy adva van m gép, jelölje ezeket M_{i}, (i = 1, ..., m), továbbá adott n munka, j, (j = 1, ..., n). Ezen munkákat az adott gépeken kell elvégeznünk. Egy ütemezés nem más, minthogy minden munkát kijelölünk egy vagy több gépre, egy –vagy több– időintervallumban, úgy, hogy egy munka egy időpillanatban csak egy gépen fusson, és egy gépen egyszerre legfeljebb egy munka legyen, s az ütemezés végére minden munkát befejezzük. Egy S ütemezésben jelölje s(j) azt az időpontot, mikor S a j munkát gépre rakta. Mivel ebben a dolgozatban a legtöbb esetben nem engedjük meg, hogy megszakítsuk a munkák végzését és esetlegesen egy másik gépen folytassuk, így s(j) egyértelműen meghatározott. Ha megengedünk megszakításokat, legyen s(j) az első olyan pillanat, mikor j-t gépre raktuk. Minden munkára adott, hogy mennyi ideig tart elvégezni egy egységnyi sebességű gépen, azaz minden j ∈ J munkához adott a p_{j} futási idő. Jelölje C_{j} azt az időpillanatot, mikor a j ∈ J munka befejeződik. Vannak olyan esetek, mikor nem áll azonnal minden munka rendelkezésünkre, ekkor minden munkához adott egy időpillanat, mielőtt nem rakhatjuk gépre, legyen ez r_{j} (j = 1, ..., n). (Ekkor természetesen egy megengedett S ütemezésre s(j) ≥ r_{j}). Előfordul, hogy a munkák halmazán megelőzési feltételek adottak, azaz adott egy antiszimmetrikus reláció a munkák között, j ≺ k azt jelöli, hogy a k munka addig nem kerülhet gépre, míg a j munka be nem fejeződött. A reláció tulajdonságaiból következően ezt egy irányított aciklikus G = (V, A) gráffal is megadhatjuk, ahol a V = {1, ..., n} megfeleltethető a munkák halmazának, és (i, k) ∈ A pontosan akkor, ha i ≺ k. Előfordul, hogy ez a megelőzési gráf egy speciális gráf, pl. ki-, vagy befenyő(k), (akár láncok) uniója. (Ahol egy kifenyő alatt egy olyan irányított gráfot értünk, melynek van egy gyökere, azaz egy olyan pont, melynek a befoka 0 és minden más pont befoka egy. Hasonlóan definiálható a befenyő is). Előfordul, hogy minden j ∈ J munkához adott egy d_{j} nem negatív szám, amely a befejezési határidőt jelöli. Azaz szeretnénk, ha a j munka d_{j} idő előtt befejeződne: C_{j} ≤ d_{j}. Persze ez nem mindig lehetséges, ekkor definiálhatjuk a j munka késését, azaz legyen L_{j} = C_{j} − d_{j}.

Még sok más tulajdonságú feladat lehetséges, azonban e dolgozatnak nem célja az ütemezéselméleti problémák teljes választékát bemutatni. Amennyiben a kedves olvasó kíváncsisága ezzel nem csillapult, még további érdekes feladatot és algoritmust talál Brucker [2] könyvében.

Egy S ütemezés akkor megengedett, ha minden munka minden időpillanatban legfeljebb egy gépen fut, és a munkák feltételei nem sérülnek. Persze többféle megengedett ütemezés létezhet, a célunk megkeresni egy adott célfüggvényre optimális megengedett ütemezést. Ebben a dolgozatban legtöbbször az utoljára véget érő munka befejezési idejét szeretnénk minimalizálni (C_{max} → min), de lesz példa arra, mikor a legnagyobb késés nagyságát minimalizáljuk (L_{max} → min), vagy a befejezési idők összegének a minimumát keressük (∑_{i=1}^{n} C_{i} → min). A megfelelő optimumokat jelölje C_{max}^{∗}, L_{max}^{∗}. Használni fogom az ütemezési problémák rövidebb hivatkozására a α|β|γ jelölést, melyet Graham, Lawler, Lenstra és Rinnooy Kan [12] vezettek be. Az α a gépek tulajdonságát, β az adott munkák tulajdonságát, és végül γ a célfüggvényt jelöli. Ebben a dolgozatban tehát azon esetek fordulnak elő, ahol az α ∈ {P, P 2, P n, Q, Q2}, a β ⊆ {prec, tree, p_{j} = 1, r_{j}, chains} és végül γ ∈ {C_{max}, L_{max}, ∑ C_{j}}. A dolgozatban használni fogok az alábbi fogalmakat:

• Listás ütemezés: tegyük fel, hogy a munkákat valamilyen szempont szerint sorba raktuk; amint szabaddá válik egy gép a listás ütemezés a sorrendben következő elérhető munkát rakja rá.

• LPT-sorrend: a munkákat nem növekvő p_{j}-k szerint rakjuk sorba, azaz p_{1} ≥ p_{2} ≥ ... ≥ p_{n}.

• SPT-sorrend: a munkákat nem csökkenő p_{j}-k szerint rakjuk sorba, azaz p_{1} ≤ p_{2} ≤ ... ≤ p_{n}.

• EDD-sorrend: a munkákat nem növekvő d_{j}-k szerint rakjuk sorba, azaz d_{1} ≥ d_{2} ≥ ... ≥ d_{n}

• Topológikus sorrend: a gráf pontjait úgy rakjuk sorba, hogy egy pontból csak az őt sorrendbe megelőző pontokba vezessen él.

• Matroid: a matroid olyan véges absztrakt struktúra, amely egy (S, ℱ) párral adható meg, ahol A véges halmaz, ℱ pedig az S részhalmazainak olyan rendszere, mely kielégíti a következő axiómákat:

– ∅ ∈ ℱ

– ha X ⊆ Y ∈ ℱ, akkor X ∈ ℱ

– minden X ⊆ S részhalmazra az ℱ tartalmazásra nézve maximális X-ben fekvő tagjai azonos elemszámúak Az ℱ tagjait a matroid független halmazainak nevezzük, a nem független halmazt nevezzük függőnek. A harmadik axióma szerint minden X részhalmazban a tovább már nem bővíthető független halmazok elemszáma azonos, legyen ez a szám az X halmaz rangja, jelöljük ezt r(X)-el. Nyilván minden X ⊆ S halmazra r(X) ≤ |X|. S maximális függetlenjeit nevezzük a matroid bázisainak.

• Transzverzális matroid: Egy G = (S, T; E) páros gráfban S párosítható részhalmazai matroidot alkotnak, s az ilyen matroidot nevezzük transzverzális matroidnak.

• α-approximációs algoritmus: 𝒩𝒫-nehéz optimalizálási (minimalizálási) problémára szeretnénk olyan algoritmust adni, amely polinom időben valamilyen szempontból ,,jó” megoldást ad. Egy algoritmust α-approximációs algoritmusnak nevezünk, amennyiben

– megengedett megoldást ad polinomiális időben

– a megoldás értéke bizonyíthatóan nem több, mint az optimális megoldás α-szorosa.

Ekkor α az algoritmus faktora. Az algoritmus persze annál jobb, minél közelebb van α értéke 1-hez. Az 𝒩𝒫-nehéz minimalizálási feladatok három osztályba sorolhatók:

– bármely α > 1-re létezik α-approximációs algoritmus

– létezik olyan β > 1, melynél kisebb α-ra nem létezik αapproximációs algoritmus (amennyiben feltesszük, hogy 𝒫 ≠ 𝒩𝒫)

– semmilyen konstans α-ra nem létezik α-approximációs algoritmus.

Használni fogom a következő jelölést egy ütemezés ábrázolására, amelyben könnyedén leolvashatjuk a vízszintes tengely mentén, hogy mely időpillanatban mely munkát mely gépre ütemeztük.

M_{3}  j_{1}  j_{2} j_{3}
M_{2}  j_{2}  j_{3}
M_{1} j_{3}  j_{1}
t

2. Párhuzamos gépek

2.1. P |prec, p_{j} = 1|C_{max}

Amennyiben a gépek száma nem fix, a feladat 𝒩𝒫 nehéz, melyet Garey és Johnson [10] látott be, egy ismert 𝒩𝒫-nehéz gráfelméleti problémát visszavezetve a feladatra. Abban az esetben, ha a gépek száma kettő, (m = 2), a feladat polinomiálisan megoldhatóvá válik, melyre a 2.3 fejezetben bemutatjuk Garey és Johnson algoritmusát [9]. Az m fix eset bonyolultsága még nyitott kérdés.

Tétel 2.1. Annak eldöntése, hogy P |prec, p_{j} = 1|C_{max} feladatban létezik-e C_{max} ≤ 3 értékű ütemezés, 𝒩𝒫-teljes probléma.

Bizonyítás: Tekintsük a következő problémát, amelyről tudjuk, hogy 𝒩𝒫-teljes: Legyen adott egy G = (V, E) gráf, és k ∈ ℤ. Kérdés, hogy létezik-e olyan T ⊆ V, mely teljes részgráfot feszít és |T | = k? (Az ilyen részgráfot nevezzük továbbiakban klikk-nek.) Megmutatjuk, hogy ez a kérdés visszavezethető egy P |prec, p_{j} = 1|C_{max} feladatra. Készítsük el a következő ütemezési feladatot: Legyen l := \binom{k}{2}, k′ := |V | − k, l′ := |E| − l, m := max\{k, l + k′, l′\} + 1 Legyenek a munkák a következők: Minden v ∈ V illetve, minden e ∈ E élhez rendeljünk egy-egy j_{v} ill. j_{e} munkát, és ezen kívül legyen adott még három munka-halmaz: X = {x_{1}, x_{2}, ..., x_{m−k}}, Y = {y_{1}, y_{2}, ..., y_{m−k′−l}}, Z = {z_{1}, z_{2}, ..., z_{m−l′}}. Ekkor összesen k + k′ + l′ + l + m − k + m − k′ − l + m − l′ = 3m munkák van. A munkák közötti megelőzési feltételek legyenek a következők: Ha v pont az e él egyik végpontja, akkor legyen j_{v} ≺ j_{e}, illetve minden x ∈ X, y ∈ Y, z ∈ Z-re: x ≺ y ≺ z.

Lemma 2.2. Pontosan akkor létezik olyan ütemezés, melyre C_{max} értéke legfeljebb 3, ha a G gráfban létezik klikk.

Bizonyítás: Elsőnek megmutatjuk, hogy ha a G gráfban létezik klikk (legyen ez T = (V_{T} , E_{T})), akkor létezik olyan ütemezés, melyre a C_{max} legfeljebb 3. (Adunk egy 3 hosszú ütemezést). Ütemezzük az első időegységre az X halmaz munkáit, és még azon pontoknak megfelelő munkákat, melyek benne vannak a klikkben: (j_{v}: v ∈ T). Második időegységre ütemezzük az Y halmaz munkáit, és a gráf azon pontjaihoz tartozó munkákat, melyek még nem voltak, (amelyek nincsenek benne a klikkben), illetve azon élekhez tartozó munkákat, mely élek benne vannak a klikk által feszített részgráfban. A harmadik időegységre ütemezzük a Z halmaz munkáit, és a maradék élekhez tartozó munkákat. Megmutatjuk, hogy ez egy megengedett ütemezés, azaz

• Minden időegységben legfeljebb m munkát ütemeztünk:

– első időegységben: |X| + |V_{T} | = m − k + k = m

– második időegységben:

|Y |+|V \V_{T} |+|E_{T} | = m−k′−l+|V |−k+\binom{k}{2} = m−k′−l+k′+l = m

– harmadik időegységben:

|Z| + |E\E_{T} | = m − l′ + |E| − \binom{k}{2} = m − l′ + l′ = m

• A megelőzési feltételek nem sérülnek: X, Y és Z halmazok munkái között nyilván teljesülnek a feltételek, és a gráf pont és élek közötti összefüggéseiből adódó megelőzési feltételek sem sérültek, ugyanis az összes klikk-élhez tartozó munka a második időegységben kerül a gépekre, s ezidőre a klikk-pontokhoz tartozó munkák már befejeződtek, míg a nem klikk élekhez tartozó munkák a harmadik időegységben kerültek a gépekre, amikorra már az összes olyan munka befejeződött, amely ponthoz lett rendelve.

Tehát az ütemezés megengedett, és C_{max} = 3. Most megmutatjuk, hogy ha adott egy ütemezés, melyre C_{max} ≤ 3, akkor létezik a G gráfban klikk. Tekintsünk egy ilyen S ütemezést. Először tegyünk néhány megfigyelést:

• Az S ütemezés szerint a megelőzési feltételek miatt az X halmaz munkái az első időegységben, az Y halmaz munkái a második időegységben, míg a Z halmaz munkái a harmadik időegységben kell, hogy fussanak a gépeken.

• Mindhárom időegységben minden gép foglalt, mert 3m munka van, és m gép.

• Az első időpillanatban X halmaz munkáin kívül csak pontokhoz tartozó munkák futhatnak. (A megelőzési feltételek miatt egy élhez tartozó munka csak akkor kerülhet gépre, mikor az ő végpontja már végzett, azaz leghamarabb a második időpillanatban.) Ezen munkákhoz tartozó pontok halmaza legyen T. Az előző megfigyelés miatt |T | = k.

Ekkor tegyük fel indirekt, hogy nincs klikk a G gráfban, azaz T nem egy teljes részgráf, így kevesebb, mint \binom{k}{2} = l élt feszít. Ekkor, ha az S az összes nem T - beli ponthoz tartozó munkát a második időegységben ütemezte, akkor is kell, hogy legyen olyan T által nem feszített élhez tartozó munka, mely szintén a második időegységben fut. (Mivel az összes gép foglalt, ugyanakkor a T által feszített élek száma és Y halmaz elemszáma kisebb, mint m a definíció szerint.) Legyen az e ∈ E él olyan, mely nincs benne a T által feszített részgráfban, és a hozzátartozó munka a második időegységben fut. Ekkor e egyik végpontjához tartozó munka biztos nem az első időegységben fut, és ez megsérti a megelőzési feltételeket. Tehát nem lehet az S ütemezés megengedett, azaz ellentmondáshoz jutottunk. Ezzel a tételt bebizonyítottuk.

2.2. P |prec|C_{max}

Láttuk, hogy ez a probléma már a p_{j} = 1 megkötéssel is 𝒩𝒫-nehéz. Graham [11] megmutatta, hogy már egy egyszerű listás ütemezés 2-approximációs megoldását adja a feladatnak. Azaz, ha munkákat valamilyen szempont szerint sorbarendezzük, majd a megelőzési feltételek figyelembevételével a gépekre ütemezzük, akkor egy olyan approximációs algoritmust kapunk, melynek faktora 2. Legyen j munka a t időpillanatban elérhető, ha j minden elődje, azaz minden k ≺ j munka, elkészült már a t időre. Ekkor amennyiben, 𝒞 = {j_{t_{1}}, ..., j_{t_{k}}} egy lánc a részben rendezésben, akkor következő alsó korláthoz jutunk:

C_{max}^{∗} ≥ ∑_{i=1}^{k} p_{t_{i}}

Ezt felhasználva a következő eredményt kapjuk:

Tétel 2.3. A listás ütemezés 2-approximációs algoritmust ad a P |prec|C_{max} feladatra.

Bizonyítás: Legyen j_{1} az a munka, mely utoljára ér véget. Legyen j_{2} a j_{1} elődei közül az utolsónak végződő ... és így tovább, legyen j_{k} az utolsó a sorban, amelynek nincs elődje. Ekkor ezen munkák egy láncot alkotnak, legyen ez: 𝒞 = {j_{1}, j_{2}, ..., j_{k}}. Legyen továbbá A azon időtartam, amíg a 𝒞 lánc valamely munkája épp valamelyik gépen van, s legyen B azon időtartam, mikor egy olyan munka sincs a gépeken, mely 𝒞-hez tartozik. Ekkor

C_{max} = A + B = ∑_{j∈𝒞}p_{j} + \frac{∑ p_{j}}{m} ≤ C_{max}^{∗} + C_{max}^{∗} = 2C_{max}^{∗}

Megjegyzés: B-ben nincs állásidő, különben 𝒞 valamely munkáját a szabad gépre rakhatnánk, hiszen listás ütemezés szerint ütemeztünk.

2.3. P 2|prec, p_{j} = 1|L_{max}

Ha figyelembe vesszük, hogy amennyiben d_{j} = 0, a feladat megegyezik a P 2|prec, p_{j} = 1|C_{max} esettel, ez a probléma magában foglalja az előző feladat egy speciális esetét. (Mikor a gépek száma pontosan 2, ez a megkötés az 𝒩𝒫nehéz feladatot polinomiálisan megoldhatóvá teszi. ) Tehát legyen adva két egyforma gép, J munkák halmaza, melyre minden j ∈ J munkára p_{j} = 1, és a munkák halmazán adott egy irányított aciklikus gráf. Elsőnek adunk egy algoritmust mely ad egy ütemezést, majd megmutatjuk, hogy ez egy optimális ütemezés lesz.

Algoritmus

1. fázis: Számoljuk ki minden j munkára a d′_{j} módosított határidőt a következőképp: Legyen minden i ∈ J munkára

S(i) := {j ∈ J : j elérhető i-ből},

azon munkák halmaza, melyek szigorúan csak i után kerülhetnek sorra. Majd minden r ∈ ℝ-re, legyen

g(i, r) := |{k ∈ S(i) : d′_{k} ≤ r}|,

ekkor legyen

d′_{i} := min \{d_{i}, min\{d′_{j} − ⌈\frac{g(i, d′_{j})}{2}⌉ : j ∈ S(i)\}\} .

Megjegyzés:

• a d′_{i}-k kiszámíthatóak egy topológikus sorrend szerint visszafele.

• a módosított határidők kiszámítására a következő megfigyelés motivál minket: ha minden olyan j munka elkészül d′_{j} határidőre, melyre i ≺ j, akkor az i-edik munkának is el kell készülnie d′_{i} határidőre.

2. fázis Rakjuk d′_{j}-k szerint EDD sorrendbe a munkákat, majd eszerint következzen a listás ütemezés.

Lemma 2.4. Egy megengedett ütemezésben pontosan akkor készül el minden j munka d_{j} határidőre, amennyiben minden i munka elkészül d′_{i} határidőre.

Bizonyítás: Ha minden munka elkészül a módosított határidőkre, akkor nyilván minden munka elkészül az eredeti határidőkre, mivel d′_{i} ≤ d_{i}. Másik irány bizonyításához indirekt tegyük fel, hogy van olyan munka, ami elkészül az eredeti határidőre, de nem készül el a módosított határidőkre. Legyen j olyan munka, amely késik d′_{j}-re, és ezek közül is olyan, melyre S(j) minimális méretű. Nyilván j nem lehet nyelő, mert ha j nyelő, akkor d′_{j} = d_{j}. Így S(j) nem üres. Ha j′ ∈ S(j), akkor S(j′) ⊆ S(j), ezért, a feltevés szerint minden j′ ∈ S(j) elkészül a módosított határidőre nézve, de a d′_{j} definíciója miatt ekkor j is el kell készüljön d′_{j}-re.

Tétel 2.5. Ha létezik olyan ütemezés, amelyben minden munka elkészül a megadott határidőre, akkor az algoritmus ilyet ad.

Bizonyítás: Indirekt tegyük fel, hogy az algoritmus által adott S ütemezésben a j munka késik d_{j}-hez képest. Mivel d′_{j} ≤ d_{j}, ezért j késik a módosított határidőre nézve is. Legyen j olyan munka, mely késik a módosított határidőre nézve és kezdési ideje minimális. Megfigyelés: Bármely t < s(j) időpontban létezik olyan k munka a gépeken, melyre d′_{k} ≤ d′_{j}, (ez következik az algoritmus választási szabályából és a módosított határidők definíciójából). Ekkor két eset lehet:

1. létezik olyan t ≤ s(j) időegység, amelyben pontosan egy olyan k munka kerül a gépre, melyre d′_{k} ≤ d′_{j}. Legyen [t, t + 1] az utolsó ilyen időintervallum. Ekkor igaz lesz a következő két tulajdonság:

(a) [t, t + 1] időben mindig két olyan munka fut a gépeken, melyek módosított határideje legfeljebb d′_{j};

(b) [t + 1, s(j)] időben minden munka benne van S(k)-ban is. (az algoritmus választási szabálya miatt).

Ekkor (a) és (b) miatt

d′_{k} ≤ d′_{j} − ⌈\frac{g(k, d′_{j})}{2}⌉ ≤ s(k)

így k is késik d′_{k}-re nézve. Ez ellentmondás, hiszen feltettük, hogy j a legkorábban kezdődő olyan munka, mely késik.

2. Minden t < s(j)-hez pontosan két olyan munka létezik, mely a [t, t+1]- ben fut, és amelyeknek a módosított határideje nem nagyobb a j munka módosított határidejénél. Ekkor azonban j tetszőleges ütemezésben késik a módosított határidőre! Így az előző lemma miatt j tetszőleges ütemezésben késik az eredeti határidőre is, tehát ellentmond a tétel feltételének.

Lemma 2.6. Ha a d határidőkhöz a d′ módosított határidők tartoznak, és l ∈ ℝ, akkor a d + l határidőkhöz a d′ + l módosított határidők tartoznak.

Bizonyítás: Nyelőkre nyilvánvaló az állítás, mert ott megegyezik a módosított határidő az eredetivel. Egyébként meg a topológikus sorrendben visszafele vizsgálva következik a módosított határidők definíciójából.

Tétel 2.7. Az algoritmus optimális ütemezést talál a

P 2|prec, p_{j} = 1|L_{max} feladatra.

Bizonyítás: Legyen L_{max}^{∗} az optimum. Pontosan akkor létezik S ütemezés, melyre minden j ∈ J-re C_{j} − d_{j} ≤ L_{max}^{∗}, ha a d_{j} + L_{max}^{∗} határidőre létezik késés nélküli ütemezés. Viszont, ha létezik ilyen ütemezés, akkor tudjuk, hogy az algoritmusunk ilyet talál, és az előző lemma miatt az algoritmusunk ugyanazt az ütemezést adja az eredeti határidőkre is.

2.4. P |tree, p_{j} = 1|C_{max}

A P |prec, p_{j} = 1|C_{max} egy másik speciális esete, mikor a részben rendezés gráfja egy ki-, vagy egy befenyő. Ez a feladat is polinomiálisan megoldható. Sőt, itt is többet igazolunk.

2.4.1. P |tree, p_{j} = 1|C_{max}

Amikor az F fenyő egy s gyökerű befenyő, Hu [13] a következő algoritmust adta:

1. Minden j munkához kiszámoljuk az l(j) ,,szint” értéket, ami legyen az egyértelműen meghatározott j-s út hossza az F fenyőben. [l(s) := 0]

2. a t = 0 időpillanattól kezdve hajtsuk végre a következőket:

Legyen L_{t} az éppen előd-nélküli munkák halmaza (a forrás, illetve az elérhetők), rakjuk őket sorba szintek szerint csökkenően. Ekkor ütemezzük a [t, t + 1] időre az L_{t} halmazból az első min{|L_{t}|, m} munkát.

Tétel 2.8. Az algoritmus optimális ütemezést ad.

Bizonyítás: Legyenek V_{0}, V_{1}, ..., V_{r} a szinthalmazok. Amennyiben j szintje legalább i, akkor

C_{max}^{∗} ≥ i + ⌈\frac{∑_{k=i}^{r} |V_{k}|}{m}⌉

Belátjuk, hogy létezik olyan j munka, melyre i = l(j) választással egyenlőség áll. Legyen j a legkorábban ütemezett olyan munka, amelynek s-től való ,,távolsága” az ütemezésben éppen l(j). (Ilyen munka létezik, pl. s ilyen, tehát vehetjük ezen tulajdonságúak közül a legkorábban ütemezettet). Megfigyelések:

• Mielőtt j-t ütemeztük, az előző időegységben ütemezett munkák egyike sem elődje j-nek. (j választása miatt, ugyanis ha lenne ilyen, akkor az a munka szintje pont eggyel kisebb lenne, mint l(j), és pont eggyel korábban lett ütemezve, tehát azt a munkát választottuk volna j helyett.)

• Mielőtt j-t ütemeztük, az előző időegységben minden gép foglalt és ezen munkák szintje mindig legalább l(j).

• Minden s(j) előtti időegységben foglalt minden gép, és ezen munkák szintje legalább l(j)

A fenti megfigyelésekből következik, hogy i = l(j) választással egyenlőség áll, tehát az algoritmus által adott ütemezésre a C_{max} = i + ⌈^{\frac{∑_{k=i}^{r} |V_{k}|}{m}}⌉, amiből következik az optimalitás. Ez a gondolatmenet átvihető arra az esetre is, mikor a megelőzési feltételek gráfja nem be-, hanem kifenyő, vagy egy be-, vagy kifenyves. Megjegyzendő azonban, hogy amennyiben a gráf kifenyő(k) és befenyő(k) (vegyes)uniója, a feladat ismét 𝒩𝒫-nehézzé válik.

2.4.2. P |tree, p_{j} = 1|L_{max}

Ebben az esetben már nem mindegy, hogy kifenyővel vagy befenyővel adott a megelőzési feltételek gráfja, ugyanis Brucker, Garey és Johnson [3] belátták, hogy a kifenyő eset már 𝒩𝒫-teljes bonyolultságú. Visszavezették a feladatra a pontfedés problémáját. Konstruáltak egy G = (V, E) gráfot, melyben annak eldöntése, hogy létezik-e V -nek egy k-pontú részhalmaza, mely minden élt lefog, ekvivalens azzal, hogy P |outtree, p_{j} = 1|L_{max} problémának létezik-e olyan ütemezése, melyre egy munka sem késik, azaz L_{max} = 0.

Amennyiben a megelőzési feltételek gráfja befenyő, a feladat polinomiálisan megoldható: Tudjuk, hogy amennyiben i ≺ k, akkor s(i) + 1 ≤ s(k) ≤ d_{k} − 1. Ez motiválja következő módosított határidők bevezetését: d′_{i} := min{d_{i}, d_{k} −1}. Ezt könnyedén kiszámolhatjuk minden i munkára a következő algoritmussal:

1. A gyökérre legyen a d′ = d.

2. Legyen j ∈ J olyan, melyre még nem módosítottuk a határidőt, de a rákövetkező j ≺ k munkát már igen. Ekkor, ha nem létezik ilyen munka, akkor készen vagyunk. Ha létezik, akkor:

3. d′_{j} := min{d_{j}, d′_{k} − 1}, majd menjünk a 2. lépésre.

Rakjuk a munkákat nem növekvő d′-k szerint sorba. Amíg tudunk, rendeljünk az időegységekhez munkákat úgy, hogy:

• egy időegységbe legfeljebb m munkát rendeljünk;

• sorba haladva a munkákon mindig azt a munkát rendeljük a gépre, melynek az elődjei már egy korábbi időegységben végeztek.

Ez polinomiálisan megoldható.

Lemma 2.9. Pontosan akkor létezik olyan ütemezés, melyre minden munka elkészül a módosított határidőre, ha létezik olyan ütemezés, melyben az eredeti határidőre is elkészül minden munka.

Bizonyítás: Tegyük fel, hogy az S listás ütemezés szerint valamely munka késik az eredeti határidőre. Mivel pontosan akkor létezik az eredeti d_{j}-kre megengedett ütemezés, ha a módosított határidőkre nézve létezik, ezért S valamelyik módosított határidőre nézve is késik. Legyen i ∈ J a késők közül az S által legkorábban ütemezett. Legyen t_{0} azon legkésőbbi, de ⌊d′_{i}⌋-nél kisebb egész időpillanat, mikor m-nél kevesebb olyan munka fut a gépeken, melynek a módosított határideje nem nagyobb d′_{i}-nél. Ha nem létezik ilyen t_{0}, készen vagyunk, ugyanis legfeljebb m⌊d′_{i}⌋ + 1 munka készülhet el d′_{i} időpontig. Így nincs olyan ütemezés, melyben minden munka elkészül a módosított határidőkre. Tehát feltehető, hogy t_{0} létezik. A listás ütemezés szabályából, illetve i és t_{0} választásából következően minden olyan t_{0} után ütemezett j munkának, melyre d′_{j} ≤ d′_{i}, van egy elődje, mely t_{0} időpontra ütemezett. (Különben t_{0} időpontra ütemeztük volna). Két eset lehetséges:

Amennyiben t_{0} = ⌊d′_{i}⌋ − 1: legyen k ≺ i azon elődje i-nek, mely t_{0} időpontra lett ütemezve. (Ilyen természetesen van, különben i-t is t_{0} időpontra ütemezhettük volna). Mivel k elkészül ⌊d′_{i}⌋ − 1 időpillanatra, és a a módosított határidők definíciója szerint d′_{k} ≤ d′_{i} − 1 < ⌊d′_{i}⌋, ezért k szintén késik a módosított határidejéhez képest, ami ellentmond i választásának.

Amennyiben t_{0} < ⌊d′_{i}⌋−1: t_{0}+1 időpontban pontosan m olyan munka lett ütemezve, amelynek a módosított határideje nem nagyobb d′_{i}-nél, és mindegyiknek van egy t_{0}-ban kezdődő elődje. Ez viszont ellentmond a befenyő struktúrának.

Lemma 2.10. Ha a d határidőkhöz a d′ módosított határidők tartoznak, és l ∈ ℝ, akkor a d + l határidőkhöz a d′ + l módosított határidők tartoznak.

Bizonyítás: A gyökérre nyilvánvaló az állítás, mert ott megegyezik a módosított határidő az eredetivel. A módosított határidők definíciójából indukcióval belátható az állítás.

Tétel 2.11. Az algoritmus optimális ütemezést talál a

P |intree, p_{j} = 1|L_{max} feladatra.

Bizonyítás: Legyen L_{max}^{∗} az optimum. Pontosan akkor létezik S ütemezés, melyre minden j ∈ J-re C_{j} − d_{j} ≤ L_{max}^{∗}, ha a d_{j} + L_{max}^{∗} határidőre létezik késés nélküli ütemezés. Ha létezik ilyen ütemezés, akkor tudjuk, hogy az algoritmusunk ilyet talál, és az előző lemma miatt az algoritmusunk ugyanazt az ütemezést adja az eredeti határidőkre is.

Megjegyzés: Amennyiben az eredeti határidők megegyeznek, a fent bemutatott algoritmus megegyezik az előző, 2.4.1 alfejezetben bemutatott szintalgoritmussal.

2.5. P |outtree, r_{j}, p_{j} = 1| ∑ C_{j}

E feladatra Brucker, Hurink és Knust [5] adtak polinomiális megoldást, mégpedig a feladat két relaxációját vizsgálták, majd ezt felhasználva adtak egy algoritmust az eredeti problémára: Feltesszük, hogy a rendelkezésre álló idők egészek, azaz r_{j} ∈ ℤ^{+} és kompatibilisek a megelőzési relációkkal, azaz r_{i} + 1 ≤ r_{j}, ha i ≺ j. Tekintsük két speciális esetét a problémának: Az egyik, mikor eltekintünk a megelőzési feltételektől, a másik pedig mikor feltesszük, hogy annyi gépünk van, mint munkánk, azaz m = n.

2.5.1. P |p_{j} = 1, r_{j}| ∑ C_{j}

Legyenek r̃_{1} < r̃_{2} < ... < r̃_{k} a különböző rendelkezésre álló idők, és legyen r̃_{k+1} := ∞. Legyen S_{ν} azon munkák halmaza, melyek rendelkezésre álló ideje r̃_{ν}. A probléma optimális ütemezését adja a következő algoritmus:

Algoritmus I.

1. S :=∅ ;

2. ν := 1-től k-ig hajtsuk végre:

• t := r̃_{ν}; S := S ∪ S_{ν};

• Amíg t < r̃_{ν+1} és S ≠∅ legyen:

– m_{t} := min{m, |S|};

– ütemezzünk m_{t} darab S_{t} ⊆ S munkát t időpontra;

– S := S\S_{t}; t := t + 1;

Megjegyzés: minden olyan pillanatban, mikor m_{t} nem definiált, legyen m_{t} := 0.

2.5.2. P n|p_{j} = 1, r_{j}| ∑ C_{j}

Ebben az esetben minden S_{ν}-beli munkát a megjelenési időpontjában, azaz r̃_{ν} időpontban (ν = 1, ..., k), gépre rakhatunk. Ez az ütemezés megengedett, (mivel feltettük, hogy a rendelkezésre álló időpontok kompatibilisek a megelőzési feltételekkel), és természetesen optimális is lesz.

Az eredeti feladat megoldása Legyen

m̂_{t} := \{ \begin{matrix}|S_{ν}| & ha t = r̃_{ν}, \\ 0 & különben. \end{matrix}

1. futassuk le az I. algoritmust,

2. majd toljuk balról jobbra a munkákat következőképpen: A következő két feltétel végig igaz lesz:

(a) a megelőzési feltételek nem romlanak el

(b) ∑_{ν≤τ} m̂_{ν} ≥ ∑_{ν≤τ} m_{ν} minden τ időpillanatban.

Kezdetben mindkét feltétel igaz. Tegyük fel, hogy valamely ν -re m̂_{ν} < m_{ν}. Ugyanis, ha nincs ilyen ν érték, akkor n = ∑ m̂_{ν} ≥ ∑ m_{ν} = n, azaz minden ν-re m̂_{ν} = m_{ν} és ezzel készen vagyunk. Legyen t a legkisebb olyan index, melyre m̂_{t} < m_{t} ≤ m. Ekkor (b) miatt létezik t′ < t, melyre m̂_{t′} > m_{t′} és m̂_{τ} = m_{τ} minden t′ < τ < t-re. Sőt, m_{t} definíciója miatt m_{τ} = m minden t′ < τ < t, ezért m̂_{t′} ≥ m̂_{t′+1} = m̂_{t′+2} = ... = m̂_{t−1} > m̂_{t}. Eltolhatunk egy munkát [τ − 1, τ]-ból, [τ, τ +1]-be, minden τ = t, t−1, ..., t′+1-re úgy, hogy (a) igaz maradjon, mivel [τ −1, τ]-ben maximum egy munkával van több, mint [τ, τ +1]-ben és minden munkának csak egy elődje van. Tehát mindig található előd nélküli munka [τ, τ +1]-ben, amit elrakhatunk. Tehát (b) teljesül, mert ∑_{ν<t′} m̂_{ν} ≥ ∑_{ν<t′} m_{ν} és m̂_{ν} > m_{ν}. Ebből következik, hogy miután egy munkát elmozdítottunk [t′, t′ + 1]-ból [t′ + 1, t′ + 2]-be, (b)-ben az egyenlőtlenség még mindig igaz marad τ = t′-re, és τ > t′-re szintén, mivel ν > t′-re a m̂_{ν} változatlan maradt.

Egy lépésben a max{0, m_{ν} −m̂_{ν}} értéke ν = t-re 1-gyel nő, illetve a többi ν-re nem változik, azaz a ∑_{ν} max{0, m_{ν} −m̂_{ν}} minden lépésben eggyel nő. Mivel az elején ∑_{ν} max{0, m_{ν} −m̂_{ν}} ≤ ∑_{ν} m_{ν} = n, ezért legfeljebb n iteráció után elérjük az eredeti probléma optimális értékét. Mivel minden iteráció 𝒪(n) időben lefuttatható, a problémánk megoldható 𝒪(n^{2}) időben.

2.6. P |tree, p_{j} = 1|C_{max} és a matroid-fedés probléma

Már láttuk a 2.4.1 fejezetben erre a feladatra Hu szintalgoritmusát. Legyen J_{l} := {i ∈ J : l(i) ≤ l} és l^{∗} legyen a maximális szint. Ekkor Hu [13] a következő minimax tételt látta be:

max_{0≤l≤l^{∗}} ⌈\frac{|J_{l}|}{D − l}⌉ = \{ a szükséges min. gépszám, hogy D időre minden munka elkészüljön\}

Megjegyezzük, hogy D > l^{∗}, különben a probléma nem megoldható. Edmonds [7] a matroid bázisfedési-problémára adott egy teljesen hasonló minimax tételt:

max_{∅≠S⊆E} ⌈\frac{|S|}{r(S)}⌉ = \{min. bázis, melyeknek uniója E\},

ahol r a matroid rangfügvénye. Marcotte és Trotter [17] megmutatta, hogy e hasonlóság nem véletlen, azaz ez a két minimax-tétel egymásból levezethető.

Elsőnek nézzük meg, miként vezethető le Hu állításából a matroid bázisfedésére adott minimax-tétel. Ehhez definiáljunk egy transzverzális matroidot: Egy megengedett ütemezésben egy gép legfeljebb D − l munkát teljesíthet azon munkák közül, melyeknek szintje legalább l. Ugyanis amennyiben egy gépen legalább D − l munka fut a J_{l} munkahalmazból, akkor van olyan l-szintű munka, mely D − l idő után kerül a gépre, ami azt eredményezi, hogy a befenyő gyökere – a 0-szintű munka – D idő után kerül csak a gépekre. Nevezzük a munkák egy S halmazát megengedett gépelőzménynek, ha |S ∩ J_{l}| ≤ D − l, minden 0 ≤ l ≤ l^{∗}-re. Ezek lesznek majd a transzverzális matroid függetlenjei. Hogy ezt megmutassuk, definiáljunk egy páros gráfot a következőképp: G := (J ∪ T; E), ahol J = {1, ..., n}, azaz minden munkának megfeleltetünk egy pontot a gráfban, és hasonlóan minden időegységhez is rendeljünk egy pontot: T = {1, ..., D}. A gráf élhalmaza legyen: E = {(i, t) : D − l(i) ≥ t}.

Tétel 2.12. A megengedett gépelőzmények ennek a transzverzális matroidnak a függetlenjeit adják.

Bizonyítás: Definíció szerint egy megengedett gépelőzmény kijelöl néhány l^{∗}-szintű munkát az 1, ..., D − l^{∗} időintervallumokba, majd kijelöl néhány l^{∗} illetve l^{∗} − 1 szintű munkát a 1, ..., D − l^{∗} + 1 időintervallumokba, ... és így tovább. Ezen munkák időintervallumokba való beosztása a G gráf egy párosítását adja, melynél a párosításbeli J-pontok pont a megengedett gépelőzmény pontjai. Fordítva, egy párosítás J-pontjai meghatároznak egy munkahalmazt, melyben legfeljebb D − l^{∗} darab l^{∗} szintű munka szerepel, legfeljebb D − l^{∗} + 1 darab munka szerepel l^{∗} és l^{∗} − 1 szintekből, ... és így tovább. így a munkák egy megengedett gépelőzményt alkotnak.

Jelöljük J_{l} J-re vett komplementerét J̄_{l}-lel. A matroid rangfüggvény tulajdonságából és a gráf definíciójából könnyen belátható az alábbi két egyenlőtlenség:

r(S) ≤ |S|,
r(S) ≤ |S ∩ J̄_{l}| + D − l,

Innen

r(S) ≤ min{|S|; |S ∩ J̄_{l}| + D − l; l = 1, ..., l^{∗}}  (1)

Sőt, ez egyenlőséggel teljesül, s hogy ezt belássuk, tekintsük a következő definíciót: Legyen l, (0 ≤ l ≤ l^{∗}), S-re nézve kritikus index, amennyiben létezik olyan S megengedett gépelőzmény, melyre |S ∩ J_{l}| = D − l, azaz az 1, 2, ..., D − lidőpontoknak megfelelő T -pontok szintén bepárosíthatók S ∩ J_{l}-be.

Lemma 2.13. Ha nem létezik kritikus index, akkor r(S) = |S|, ha létezik, akkor legyen k minimális kritikus index. Ekkor r(S) = |S ∩ J̄_{k}| + D − k azaz S ∩ J_{k}-ból (D − k) pont bepárosítható 1, ..., (D − k)-ba.

Bizonyítás: Amennyiben nem létezik S-re nézve kritikus index, akkor l^{∗} sem kritikus. Mivel S megengedett gépelőzmény, a S ∩ J_{l^{∗}}-beli J-pontok bepárosíthatók a 1, ..., |S ∩ J_{l^{∗}}| pontokba, ahol |S ∩ J_{l^{∗}}| < D − l^{∗}. Mivel l^{∗} − 1 sem kritikus, ezért S ∩ (J_{l^{∗}−1}\J_{l^{∗}})-beli J-pontok (azaz az l^{∗} − 1 szintű pontok), |S ∩ J_{l^{∗}}| + 1, ..., |S ∩ J_{l^{∗}−1}| T -pontokba párosíthatók, (ahol |S ∩ J_{l^{∗}−1}| < D − l^{∗} + 1). Folytatva ezt a gondolatmenetet, J-pontok egy párosítását kapjuk, melyek mind S-beliek, tehát r(S) = |S|. Most tegyük fel, hogy létezik kritikus index. Mivel k kritikus, tudjuk, hogy D − k darab J-pont az S ∩ J_{k} halmazból bepárosítható az 1, ..., D − k ponthalmazba. Ha k = 0, akkor J̄_{k} =∅, tehát r(S) = D − k. Ha k > 0, akkor 0, ..., k − 1 nem kritikus, akkor a fenti gondolatmenet szerint S ∩ J̄_{k} ponthalmaz bepárosítható D − k + 1, ..., D pontokba, tehát r(S) = |S ∩ J̄_{k}| + D − k. Ezzel igazoltuk a lemma állítását.

Tehát a megengedett gépelőzmények egyenlőséggel teljesítik (1)-t, így valóban a matroid függetlenjeit adják. Innen már könnyen beláthatjuk a fentebb kimondott minimax egyenlőtlenséget. Legyen ∅ ≠ S ⊆ J, ekkor vagy nem létezik kritikus index, s ekkor

\frac{|S|}{r(S)} = \frac{|S|}{|S|} = 1 ≤ ⌈\frac{J_{l}}{r(J_{l})}⌉

illetve, ha létezik, akkor

\frac{|S|}{r(S)} = \frac{|S ∩ J̄_{l}| + |S ∩ J_{l}|}{|S ∩ J̄_{l}| + D − l} ≤ \frac{|S ∩ J_{l}|}{D − l} ≤ \frac{|J_{l}|}{D − l} ≤ \frac{|J_{l}|}{r(J_{l})}

Tehát innen kapjuk, hogy

max_{0≤l≤l^{∗}} ⌈\frac{|J_{l}|}{D − l}⌉ = \{min. gépelőzmények száma, melynek uniója J\}

A fordított levezetéshez legyen

M = max_{0≤l≤l^{∗}}⌈|J_{l}|/(D − l^{∗})⌉,

majd Hu által adott szint-algoritmust használva jelöljük ki a munkákat M gépre: amint egy gép szabad lesz, a megmaradó munkák közül azt ütemezzük rá, melynek a szintje legnagyobb. Megmutatjuk, hogy így az összes J_{l}-beli munka D − l időre elkészül, (minden l = l^{∗}, l^{∗} − 1, ..., 0). Az l = 0 eset adja majd a kérdéses mini-max tételt. A bizonyításunk induktív lesz. Mivel M ≥ ⌈|J_{l^{∗}}|/(D − l^{∗})⌉, következik, hogy M(D − l^{∗}) ≥ |J_{l^{∗}}|, tehát minden l^{∗} szintű munka elkészül D − l^{∗} időre. Legyen l^{∗} > l ≥ 0, és tegyük fel, hogy minden J_{l+1} szintű munka elkészül D − (l + 1) időre. Tegyük fel, hogy van olyan l szintű munka, mondjuk j, mely D − l idő után kerül a gépekre. Mivel M(D − l) ≥ |J_{l}|, s j csak később kerül a gépekre, ezért egy [t − 1, t] időben (0 < t ≤ D − l) van munka nélküli gép, vagy van olyan munka a gépeken, melynek szintje kisebb, mint l(j). Mivel J_{l+1} munkái elkészülnek D − l − 1 időre, és j munka D − l idő után lett ütemezve, a szint-algoritmus M darab l-szintű munkát ütemez a [D − l − 1, D − l] időintervallumba. Azaz t < D−l. A szint-algoritmus választási szabálya szerint minden olyan l-szintű munkának, mely [D − l − 1, D − l] alatt fut, van egy elődje a korábbi [t − 1, t] időintervallumban. De ebben az időben legfeljebb M − 1 munka lehet l-nél nagyobb szintű. Azaz M darab l szintű munkának, melyek mindegyikének van elődje, összesen legfeljebb M − 1 darab elődje van. Ez ellentmond a megelőzési gráfunk befenyő szerkezetének. Tehát minden l-re igaz az állítás, így l = 0-ra is, így beláttuk Hu minimax tételét.

3. Uniform gépek

3.1. Q|prec|C_{max}

Láttuk, hogy ha azonos sebességű gépeink vannak, akkor egy egyszerű listás ütemezés 2-approximációs algoritmust ad, és a mai napig nincs ennél jobb faktorú algoritmus. Uniform gépek esetén sokáig a legjobb ismert algoritmus egy 𝒪(\sqrt{m})-approximációs algoritmus volt [14], majd Chudak és Shmoys adtak 𝒪(log m)-approximációs algoritmust [6]: A párhuzamos gépeken való listás ütemezés azért volt célrevezető, mert találtunk a munkáknak egy olyan láncát, melyre csak akkor volt szabad gép, ha abban az időpillanatban a lánc valamely munkája éppen valamely gépen futott. S ez két alsó korlátot is szolgáltatott a célfüggvényünkre. Adná magát az ötlet, hogy az uniform gépek esetében is valami hasonlóval próbálkozzunk, azonban sajnos a lánc összfutási idejéből adódó alsó korlát nem marad igaz, csak abban az esetben, ha a leggyorsabb gépre ütemeznénk az összes munkáját, ami persze nem biztosított. Ellenben, ha tudnánk előre, hogy mely munkát milyen sebességű gépre ütemezzünk, akkor pedig nem lehetünk biztosak abban, hogy minden gép foglalt lesz, így a második alsó korlát nem lesz igaz. Azonban, ha megengedjük, hogy némely gép munka nélkül legyen, s helyette feltesszük, hogy legalább egy adott sebességgel futó összes gép foglalt, egy egész jó becsléshez juthatunk.

Legyen m_{k} azon gépek száma, melyek s̄_{k} sebességgel futnak, ahol k = 1, ..., K; legyen továbbá s̄_{1} > s̄_{2} > ... > s̄_{K}. Tegyük fel, hogy minden j ∈ J munkához adott azon gép – k(j)) – indexe, amelyre ütemezzük. Ekkor az s̄_{k} sebességű gépek összműködési ideje:

D_{k} = \frac{1}{m_{k}} ∑_{j:k(j)=k} \frac{p_{j}}{s̄_{k}} .

Legyen

C = max_{𝒞 lánc} ∑_{j∈𝒞} \frac{p_{j}}{s̄_{k(j)}} .

Legyen a sebességen alapuló listás ütemezésben a munkák rendre 1, 2, ..., n sorba rendezve. Amint egy munka befejeződik, mindazon gépekre ütemezzünk munkát, ahol épp nincsen. A munka nélküli gépeket sorba rakjuk. Egy s̄_{k} sebességű gépre elsőnek azon még nem szerepelt j munkát választjuk, amelyre k(j) = k, és amelynek már az összes elődje végzett. Ha ilyen munka nem létezik, akkor a gép egészen addig munka nélkül marad, amíg a következő munka nem végez.

Tétel 3.1. Ha minden munkára meghatározott a k(j) index, (j = 1, ..., n), akkor a sebességen alapuló listás ütemezési algoritmus megoldására

C_{max} ≤ C + ∑_{k=1}^{K} D_{k}.

Bizonyítás: A tétel bizonyítása általánosítása Graham [11] bizonyításának. Felosztjuk a [0, C_{max}] időintervallumot K + 1 darab τ_{k} téglára, (k = 0, 1, ..., K): Legyen j_{1} az a munka, ami C_{max} időre készül el. Készítsük el a következő láncot, amely j_{1} munkával ér véget: minden t = 1, ..., n-re legyen j_{t+1} a j_{t} azon elődje, amely az ütemezésben legkésőbb ér véget. Ha j_{t}-nek nincs elődje, akkor 𝒞 lánc teljes. Legyen τ_{0} azon időintervallum, ami alatt 𝒞 munkái futnak. Jelöljük τ_{k(j)}-vel azt az intervallumot, ami akkor végződik, mikor a j ∈ 𝒞 munka kezdődik. Így felosztottuk az időintervallumot 0-tól C_{max}-ig téglákra. Elsőnek is figyeljük meg, hogy τ_{0} hossza maximum C, mivel az algoritmusunk minden j munkát egy s̄_{k(j)} sebességű gépre ütemez, (j = 1, ..., n). Megfigyelhetjük azt is, hogy nincs s̄_{k} sebességű álló gép a τ_{k} intervallumban. Ha τ_{k} intervalllum hossza t_{k}, akkor ez idő alatt s̄_{k}m_{k}t_{k} egységnyi munkát kell teljesítenie ezeken a gépeken, sőt összesen csak ∑_{j:k(j)=k} p_{j} egységet kell teljesítenie az s̄_{k} sebességű gépeknek, ezért

t_{k} ≤ \frac{1}{m_{k}s̄_{k}} ∑_{j:k(j)=k} p_{j} = D_{k}, k = 1, ..., K.

Ezzel bebizonyítottuk a tétel állítását.

Szeretnénk kijelölni a munkákat a gépekhez oly módon, hogy a felső korlát, C + ∑_{k=1}^{K} D_{k} ne legyen túl nagy. Bemutatjuk a feladatunk egy relaxációját, amely kiszámolja, hogy mely munkát milyen sebességű gépre ütemezzünk, hogy az összidő D legyen. Vezessük be a következő változókat: legyen x_{kj} értéke 1, ha j munka egy s̄_{k} sebességű gépen fut, és 0, ha nem, (k = 1, ..., K és j = 1, ..., n) továbbá jelölje C_{j} változó értéke azt az időpillanatot, mikor a j munka véget ér,(j = 1, ..., n). Ez utóbbiak természetesen nem feltétlenül egészek. Ekkor a következők teljesülnek a változókra:

• minden munka fut valamely gépen, ezért (2)

• bármely s̄_{k}-ra, az azonos sebességű gépek összemunkaideje nem haladhatja meg D-t, ezért (3)

• egyetlen munka sem fejeződhet be az átfutási idejénél hamarabb (4)

• minden j′ ≺ j relációra, C_{j} −C_{j′} érték nem lehet kisebb, mint a j futási ideje, így kapjuk (5)-t

• amennyiben az ütemezés hossza D, úgy minden munka véget ér addigra, innen kapjuk (6)-t

• s végül (7) biztosítja majd a megfelelő változók egészértékűségét.

Tehát:

∑_{k=1}^{K} x_{kj} = 1, j = 1, ..., n,  (2)

\frac{1}{m_{k}s̄_{k}} ∑_{j=1}^{n} p_{j}x_{kj} ≤ D, k = 1, ..., K,  (3)

∑_{k=1}^{K} \frac{p_{j}}{s̄_{k}} x_{kj} ≤ C_{j}, j = 1, ..., n,  (4)

∑_{k=1}^{K} \frac{p_{j}}{s̄_{k}} x_{kj} ≤ C_{j} − C_{j′}, ha j′ ≺ j  (5)

C_{j} ≤ D, j = 1, ..., n,  (6)
x_{kj} ∈ {0, 1}, k = 1, ..., K, j = 1, ..., n.  (7)

Ekkor a relaxáció a következő: Minimalizáljuk D-t, a fenti (2)-(7) feltétellel. Ezen vegyes-egészértékű lineáris programozási feladat optimális megoldása alsó korlát lesz az optimális ütemezés hosszára, C_{max}^{∗}-ra. A feladat minden megoldására a sebességen alapuló listás ütemezés egy (K + 1)D hosszúságú megoldást ad: (5) és (6) feltételek következtében minden lánc hossza legfeljebb D, és a (3) feltétel miatt minden k-ra, az s̄_{k} sebességű gépek D_{k} összműködési ideje legfeljebb D, (k = 1, ..., K). Valójában 3.1 tétel többet állít: ezen korlát eléréséhez nem szükséges, hogy olyan egészértékű megoldásokat kapjunk, ami (3)-t kielégíti; legyen igaz a következő:

∑_{k=1}^{K} \frac{1}{m_{k}s̄_{k}} ∑_{j=1}^{n} p_{j}x_{kj} ≤ KD  (8)

Az algoritmusunk felhasználja azt a tényt, hogy ez a gyengébb egyenlőtlenség elegendő lesz. Helyettesítsük a (7)-es feltételünket a következővel:

x_{kj} ≥ 0, k = 1, ..., K, j = 1, ..., n.  (9)

A lineáris programozási feladat a következő lesz: minimalizáljuk D-t az (2), (3), (4), (5), (6) és (9) feltételek mellett. Jelöljük ezt a feladatot LP -vel. Ez a feladat polinom időben megoldható, legyen az optimális megoldás x̄_{kj} (k = 1, ..., K, j = 1, ..., n), és C̄_{j} (j = 1, ..., n), és az optimum D̄, ami természetesen alsó korlátja lesz C_{max}^{∗}-nak. Az LP optimális megoldását használjuk fel, hogy kijelöljük a munkákat a gépekre. Minden j munkára, (j = 1, ..., n), kiszámoljuk az –átlagos– p̄_{j} futási idejét az LP által kijelölt gépeken:

p̄_{j} = ∑_{k=1}^{K}(p_{j}/s̄_{k})x_{kj}, j = 1, ..., n.

Legyen továbbá B_{j} azon (rossz) gépek indexhalmaza, melyek túl lassúak a j munkához:

B_{j} = \{k : p_{j}/s̄_{k} > (\sqrt{K} + 1)p̄_{j}\}.

Minden j munkára, (j = 1, ..., n), legyen k(j) az a k ∉ B_{j} index, melyre p_{j}/(s̄_{k}m_{k}) minimális, azaz melyre s̄_{k}m_{k} a legnagyobb. Megmutatjuk, hogy ezt a k(j)-t használva C + ∑_{k=1}^{K} D_{k} ≤ 2(K + 1)D̄ lesz. S mivel D̄ ≤ C_{max}^{∗}, ezért a sebességen alapuló listás ütemezésünk egy 2(K + 1)-approximációs algoritmust ad.

Lemma 3.2. Az algoritmus által kijelölt k(j) értékekre, (j = 1, ..., n), és bármely 𝒞 láncra

∑_{j∈𝒞}p_{j}/s̄_{kj} ≤ (\sqrt{K} + 1)D̄.

Bizonyítás: Legyen 𝒞 lánc a következő: j_{1} ≺ j_{2} ≺ ... ≺ j_{r}. Elsőnek belátjuk, hogy

∑_{j∈𝒞} p̄_{j} ≤ D̄.  (10)

S mivel minden j munkához úgy választottuk a k(j) indexet, hogy legfeljebb (\sqrt{K} + 1)p̄_{j} időegység alatt fut a gépen, ez elég is lesz a lemma állításához. Mivel x̄ kielégíti (4)-t, p̄_{j1} ≤ C̄_{j1}. Továbbá, x̄ kielégíti (5)-t is, és így, mivel j_{i−1} ≺ j_{i}, i = 2, ..., r, ezért p̄_{j} ≤ C̄j_{i} − C̄_{j_{i−1}}, (i = 2, ..., r.). Ha összeadjuk ezeket a feltételeket, kapjuk, hogy

∑_{j∈𝒞} p̄_{j} ≤ C̄_{j_{r}}.

Végül (6) miatt C̄_{j_{r}} ≤ D̄, és ezért (10) teljesül.

Lemma 3.3. Legyen x̂_{kj} = 1 ha k = k(j), (j = 1, ..., n) és legyen x̂_{kj} = 0 különben. Ekkor

∑_{k=1}^{K} \frac{1}{m_{k}s̄_{k}} ∑_{j=1}^{n} p_{j}x̂_{kj} ≤ \frac{\sqrt{K} + 1}{\sqrt{K}}D̄.

Bizonyítás: Tekintsük a problémát egy szimplex felett:

min ∑_{j=1}^{N} c_{j}y_{j}

∑_{j=1}^{N} h_{j} = 1, y_{j} ≥ 0, j = 1, ..., N.

Ebben az esetben könnyen ellenőrizhető, hogy létezik egy optimális y^{∗} megoldás, ami egészértékű: legyen c_{j^{∗}} = min_{j} c_{j} és legyen y_{j^{∗}}^{∗} = 1, és összes többi komponense 0. Hasonlóan, x̂ optimális megoldása a következő lineáris programnak:

min ∑_{k=1}^{K} \frac{1}{m_{k}s̄_{k}} ∑_{j=1}^{n} p_{j}x_{kj}  (11)

∑_{k=1}^{K} x_{kj} = 1, j = 1, ..., n,  (12)

x_{kj} = 0, ha k ∈ B_{j}, j = 1, ..., n,  (13)
x_{kj} ≥ 0, k = 1, ..., K, j = 1, ..., n.  (14)

Célunk egy olyan x̃ megengedett megoldást előállítani, melynél a célfüggvény értéke legfeljebb \frac{\sqrt{K}+1}{\sqrt{K}} D̄. Lin és Vitter [16] technikáját használva kapjuk LP optimális x̄ megoldását. Ekkor legyen α_{j} := ∑_{k∉B_{j}} x̄_{kj},

(α_{j} > \frac{\sqrt{K}}{\sqrt{K}+1}). Majd legyen

x̃_{kj} := \{ \begin{matrix}0 & ha k ∈ B_{j}, \\ \frac{x̄_{kj}}{α_{j}} & különben. \end{matrix}

Könnyen ellenőrizhető, hogy x̃ megengedett megoldása a (12)-(14)-nek. Továbbá x̃_{kj} ≤ \frac{\sqrt{K}+1}{\sqrt{K}} x̄_{kj}, (minden k = 1, ..., K, j = 1, ..., n). Tehát (3)-ből kapjuk, hogy

\frac{1}{m_{k}s̄_{k}} ∑_{j=1}^{n} p_{j}x̃_{kj} ≤ \frac{\sqrt{K} + 1}{\sqrt{K}}D̄, k = 1, ..., K.  (15)

Ebből következik, hogy x̃ megengedett megoldáshoz tartozó célfüggvény értéke, (11), legfeljebb \frac{\sqrt{K}+1}{\sqrt{K}}KD̄. Mivel x̂ optimális megoldás, ezért a

hozzátartozó célfüggvényérték szintén legfeljebb \frac{\sqrt{K}+1}{\sqrt{K}}KD̄.

Kombinálva ezt a lemmát a 3.1-es tétellel, kapjuk a következő eredményt:

Tétel 3.4. A kijelölő algoritmust kombinálva a sebességen alapuló listás ütemezéssel egy (K+2\sqrt{K}+1)-approximációs algoritmust kapunk a Q|prec|C_{max} problémára, ahol K a különböző gépsebességek számát jelöli.

Következmény 3.5. A kijelölő algoritmus a sebességen alapuló listás ütemezéssel kombinálva egy olyan megoldást ad, melyre a C_{max} értéke D̄, az LP lineáris programozási feladatnak optimális megoldásának (K + 2\sqrt{K} + 1) hányadán belül marad.

Megmutatjuk, hogy az általános problémát hogyan vezessük vissza arra az esetre, mikor legfeljebb log m különböző sebességű gép van (azaz K = log m). Közben az LP feladat optimuma legfeljebb a négyszeresére változhat, s így a 3.5-os következmény értelmében egy 𝒪(log m)-approximációs algoritmust kapunk. Feltehetjük, hogy az m gép sebessége s_{i}, (i = 1, ..., m), K különböző sebességből áll, ahol 1 = s̄_{1} > s̄_{2} > ... > s̄_{K} (természetesen a K = m legrosszabb eset is előfordulhat). Ekkor az algoritmus két lépésből áll:

• Elsőnek kiszórjuk azokat a gépeket, melyek a sebessége a leggyorsabb gép sebességéhez viszonyítva legalább c(m)-szer lassabbak, ahol c(m) egy m-től függő konstans.

• Minden megmaradt gép sebességét lekerekítjük a legközelebbi 1/2 hatványig. (Vagy tetszés szerinti (1/α) hatványig). Így egyik gép sem lesz gyorsabb, mint eredetileg volt.

Legyen k_{0} az a legkisebb index, ami nem nagyobb 1/m-nél, azaz, s̄_{k} ≤ 1/m, (k = k_{0} + 1, ..., K). Nevezzünk ,,gyorsnak” egy gépet, ha sebessége nagyobb, mint 1/m, a többi gép legyen ,,lassú”. Bármely munka, mely lassú gépre van ütemezve, ütemezhető egy gyors gépre is: Ugyanis nem több, mint m lassú gép van, ezért a lassú gépek összsebessége kevesebb, mint 1, ami épp s_{1}. Ez azt jelenti, hogy bármely 1 sebességű gép legfeljebb kétszer annyi idő alatt elvégezheti a lassú gépek munkáját is. Azaz LP feladatunk bármely megengedett x̄_{kj}, (k = 1, ..., K; j = 1, ..., n), C̄_{j}, (j = 1, ..., n), és D̄ megoldásához konstruálhatunk egy x̃ megengedett megoldást, melynek célfüggvény értéke legfeljebb 2D̄, és csak a gyors gépeket használja. Legyen D̃ = 2D̄, és minden j munkára, (j = 1, ..., n), legyen

x̃_{1j} = x̄_{1j} + ∑_{k_{0}}^{K} x̄_{kj},

x̃_{kj} = x̄_{kj}, (k = 2, ..., k_{0}), és C̃_{j} = C̄_{j}.

Ez egy olyan megengedett megoldása lesz az LP feladatnak, mely csak a gyors gépeket használja. Tehát feltehetjük, hogy bármely gépsebességre: s̄_{k} ∈ (1/m, 1]. Minden i gépre, kerekítsük le a sebességét a legközelebbi 1/2 hatványig; azaz minden gépet, melynek sebessége s̄_{i} ∈ (2^{−k}, 2^{−k+1}] helyettesítsük egy olyan géppel, melynek sebessége 2^{−k}. Ekkor a x̃_{kj}, (k = 1, ..., k_{0}; j = 1, ..., n), 2C̃_{j}, (j = 1, ..., n) és 2D̃ = 4D̄ megengedett megoldása lesz ennek a lekerekített LP feladatnak. Kerekítés után legfeljebb log m különböző sebesség lesz, tehát egy 4(log m + 2\sqrt{log m} + 1) approximációs algoritmust kaptunk a Q|prec|C_{max} feladatra. Megjegyzés: Persze tovább optimalizálhatunk, amennyiben megkeressük a legjobb c(m) konstans, ill. azt a hatványt, melyre a meghagyott gépek a sebességét érdemes kerekíteni. Azaz például, ha az 1/(βm)-nél lassabb gépeket elhagyjuk, és minden más sebességet a (α^{−k}, α^{−k+1}] intervallumban lekerekítünk α^{−k}-ra, (ahol α > 1, és β ≥ 1), abban az esetben a különböző sebességek száma legfeljebb log_{α}(βm), és a kerekítés az LP feladatunk célfüggvényértékét legfeljebb α(1 + 1/β)-szeresére növelhette. Azaz a legjobb α és β választás mellett a következő tételt kapjuk:

Tétel 3.6. Ha K a különböző gépsebességek száma, akkor létezik egy min\{K + 2\sqrt{K} + 1, 1.89 log m + Θ(\sqrt{log m})\}-approximációs algoritmus a Q|prec|C_{max} feladatra.

3.2. Q|prec|C_{max} mégegyszer

Fentebb bemutattunk a problémára egy lineáris programozással kombinált algoritmust, most nézzük meg Bender és Chekuri [1] által adott algoritmust, mely szintén 𝒪(log m)-approximációs, ellenben a lineáris programozási feladat helyett kombinatorikus módszert használ. Az előző részhez hasonlóan hagyjuk el azokat a gépeket, melyeknek sebessége legfeljebb 1/m-szerese a leggyorsabb gépnek, majd kerekítsük le a többi gép sebességét a legközelebbi 1/2 hatványig. Használni fogjuk a követező fogalmakat: Legyen a részben rendezett halmaz egy 𝒫 = (P_{1}, P_{2}, ...P_{r}) sorba rendezett láncokból álló partíciója láncfelbontás. Egy maximális láncfelbontás olyan, melyre P_{1} a leghosszabb lánc, és (P_{2}, ...P_{r}) egy maximális láncfelbontás a maradék munkahalmazon. Megjegyzendő, hogy a maximális láncfelbontásnál nem mindegy a láncok sorrendje, használni fogjuk azt a tényt, hogy |P_{1}| ≥ |P_{2}| ≥ ... ≥ |P_{r}|. Legyen 𝒫 = (P_{1}, P_{2}, ..., P_{r}) egy láncfelbontása a munkáknak. Legyen a 𝒫-hez és s_{1} ≥ s_{2} ≥ ... ≥ s_{m} gépsebességekhez tartozó L_{𝒫} mennyiség a következőképp adva:

L_{𝒫} = max_{1≤j≤min\{r,m\}} \frac{∑_{i=1}^{j} |P_{i}|}{∑_{i=1}^{j} s_{i}}.

A definíció nevezőjében szereplő szumma nem a sebesség osztályokra megy, hanem a gépekre. Egy adott j ≤ m-re a \frac{∑_{i=1}^{j} |P_{i}|}{∑_{i=1}^{j} s_{i}} mennyiség a 𝒫 felbontás első j láncának a j leggyorsabb gépen történő átlagos futási idejét jelöli.

Tétel 3.7. Legyen 𝒫 = (P_{1}, P_{2}, ..., P_{r}) a munkák megelőzési gráfjának egy láncfelbontása (gyakorlatban egy maximális láncfelbontása). Legyen AL = (∑_{j=1}^{n} p_{j})/(∑_{i=1}^{m} s_{i}) az átlagos futási idő. Ekkor

C_{max}^{∗} ≥ max{AL, L_{𝒫}}.

Sőt ez az alsó korlát azon ütemezésre is érvényes, mikor megszakításokat is megengedünk.

Bizonyítás: A maximális mennyiség, amit a gépek egységnyi idő alatt el tudnak végezni, legfeljebb ∑_{i=1}^{m} s_{i}, mit pontosan akkor érünk el, ha minden gép foglalt. Ebből következik, hogy az összidő legalább AL = (∑_{j=1}^{n} p_{j})/(∑_{i=1}^{m} s_{i}), azaz: C_{max}^{∗} ≥ AL. Megmutatjuk, hogy minden 1 ≤ j ≤ m-re:

C_{max}^{∗} ≥ \frac{∑_{i=1}^{j} |P_{i}|}{∑_{i=1}^{j} s_{i}}.

Tekintsük az első j láncot. Tegyük fel, hogy úgy módosítjuk a bemenő adatainkat, hogy csak az első j lánc munkái adottak. Könnyen ellenőrizhető, hogy e módosított feladat egy alsó korlátja, alsó korlát lesz az eredeti feladatra is. Mivel egy láncból egyszerre csak egy munka lehet a gépeken, ezért a módosított feladatra csak a leggyorsabb j gép lesz érdekes. A (∑_{i=1}^{j} |P_{i}|)/(∑_{i=1}^{j} s_{i}) kifejezés, a módosított feladat átlagos futási ideje, amint az már megmutattuk alsó korlát lesz. Tehát a tételt ezzel bebizonyítottuk. Mivel az átlagos futási idő abban az esetben is alsó korlát lesz, mikor megszakításokat is megengedünk, ezért a tételünk ebben az esetben is igaz lesz.

Tétel 3.8. A maximális lánc-kompozíció 𝒪(n^{3}) időben kiszámítható.

Bizonyítás: Elsőként készítsük el a gráf tranzitív-lezártját: minden pontjából futassunk le egy szélességi-keresést. (Ez összesen 𝒪(n^{3}) időben megtehető.) Majd keressük meg a leghosszabb láncot ebben a pontsúlyozott irányított gráfban, erre létezik 𝒪(n^{2}) időben futó algoritmus, melyet legfeljebb n-szer kell meghívnunk. Ebből már következik a feladat állítása.

Megjegyzendő, hogy amennyiben minden p_{j} azonos, akkor a futási idő 𝒪(n^{2}\sqrt{n}).

Az approximációs algoritmus

Az approximációs algoritmus, melyet itt bemutatunk, a maximális láncfelbontáson alapul majd. Az algoritmus minden munkára megmondja, melyik gépen fusson, majd alkalmazzuk a sebességen alapuló listás ütemezést, amint azt az előző megoldásban is tettük.

ALGORITMUS

1. Számoljuk ki a munkák egy maximális lánc-kompozicióját, legyen ez 𝒫 = (P_{1}, ..., P_{r}).

2. Legyen B = max{AL, L_{𝒫}}.

3. Legyen l = 1.

4. i = 1-től K-ig hajtsuk végre:

(a) Legyen t ≤ r az a maximális index, mire

∑_{l≤j≤t} |P_{j}|/(m_{i}s̄_{i}) ≤ 4B.

(b) Jelöljük ki a P_{l}, ...P_{t} láncok munkáit az s_{i} sebességű gépre.

(c) Legyen l = t + 1. Amennyiben l > r, akkor Leállunk.

5. Leállunk

Lemma 3.9. Legyen P_{l(u)}, ..., P_{r}azon láncok, melyek a 4-es lépésben visszamaradtak, mikor az u-sebességű gépet vettük. Ekkor

1. |P_{l(u)}|/s̄_{u} ≤ 2B, és

2. minden P_{l(u)}, ..., P_{r} az u sebességre van kijelölve, vagy D_{u} > 2B.

Bizonyítás: A fenti állításokat u-ra vett indukcióval bizonyítjuk. Tekintsük azt az esetet, mikor u = 1 és l(1) = 1. Ekkor L_{𝒫} definíciójából adódóan |P_{1}|/s̄_{q} ≤ B. Mivel P_{1} a leghosszabb lánc, ezért az is következik ebből, hogy |P_{j}|/s̄_{1} ≤ B, (1 ≤ j ≤ r). Legyen t a legnagyobb olyan index, melyre P_{t} az s̄_{1} sebességű gépre van kijelölve. Ha t = r, akkor készen vagyunk. Ha t < r, akkor amennyiben P_{t+1}-et a s̄_{1} gépre jelölnénk, az átlagos futási időt annyival növelné, hogy az több lenne, mint 4B. Mivel |P_{t+1}|/s̄_{1} ≤ B, kapjuk, hogy D_{1} = ∑_{j=1}^{t} |P_{j}|/m_{1}s̄_{1} = ∑_{j=1}^{t+1} |P_{j}|/m_{1}s̄_{1} −|P_{t+1}|/m_{1}s̄_{1} > (4−1/m_{1})B > 2B. Tegyük fel, hogy a lemma két állítása igaz, minden s̄_{1}, ...s̄_{u−1} sebességre. Tekintsük s̄_{u}-t. Feltehetjük, hogy l(u) < r, különben már minden lánccal végeztünk, azaz nem maradt lánc, mit s̄_{u}-ra jelölnénk, és ekkor a lemma állításai igazak az indukciós feltevés miatt. Megfigyelhetjük, hogy a második állítás következik az elsőből, hasonlóan végiggondolva, mint az előbb. Sőt, ha a gondolatmenetet tovább vinnénk, megfigyelheténk, hogy az életben nincs olyan, hogy valami ne lenne sörnyitó. Ezen felismerés bebizonyítását a kedves olvasóra bízom. Visszatérve a lemmára, látható, hogy elegendő az első állítást igazolni. Azt is megfigyelhetjük, hogy a két állításból következik, hogy ha D_{k} > 2B, akkor legalább m_{k} láncot jelölünk az s̄_{k} sebességű gépekre. Tegyük fel, hogy |P_{l(u)}|/s̄_{u} > 2B. Legyen M^{v} = ∑_{k=1}^{v} m_{k}. Legyen j = l(u) és legyen v azon index, amelyre M^{v−1} < j ≤ M^{v}. Ha j > m, nem létezik ilyen v index, ekkor legyen v = K (azaz a leglassabb gépsebesség). Ha j ≤ m, feltehetjük, hogy j = M^{v}, (egyszerűen törölhetjük a többi s̄_{v} sebességű gépet). P_{l(u)−1} az utolsó olyan lánc, melyet az s̄_{u−1} sebességű gépre jelöltünk. Azt állítjuk, hogy l(u) − 1 ≥ M^{u−1}, mivel minden k < u-ra, D_{k} > 2B, és ezért legalább m_{k} darab láncot jelöltünk az s̄_{k} sebességű gépekre. Ezért j = l(u) > M^{u−1}, és innen v definíciójából következik, hogy v ≥ u. L_{𝒫}, AL, és B definíciójából kapjuk, hogy ha j ≤ m, akkor L_{𝒫} ≥ (∑_{i=1}^{j} |P_{i}|)/(∑_{k=1}^{v} m_{k}s̄_{k}). Illetve, ha j > m, akkor AL ≥ (∑_{i=1}^{j} |P_{i}|)/(∑_{k=1}^{K} m_{k}s̄_{k}). Kombinálva a két egyenlőséget, kapjuk, hogy

\frac{∑_{i=1}^{j} |P_{i}|}{∑_{k=1}^{v} m_{k}s̄_{k}} ≤ max\{L_{𝒫}, AL\} = B.  (16)

Mivel |P_{j}|/s̄_{u} > 2B, ezért minden M^{u−1} < i ≤ j-re |P_{i}|/s̄_{u} > 2B. Ebből következik, hogy

∑_{M^{u−1}<i}^{j} |P_{i}| > 2B(j − M^{u−1})s̄_{u} ≥ 2B ∑_{k=u}^{v} m_{k}s̄_{k}.

Amennyiben a baloldalon több láncot számolunk az egyenlőtlenség továbbra is igaz marad:

∑_{i=1}^{j} |P_{i}| > 2B ∑_{k=u}^{v} m_{k}s̄_{k}.  (17)

Az indukciós feltevés szerint s̄_{1}, ...s̄_{u−1} sebességű gépek átlagos futási ideje nagyobb, mint 2B. Ekkor kapjuk, hogy:

∑_{i=1}^{j−1} |P_{i}| > 2B ∑_{k=1}^{u−1} m_{k}s̄_{k}.

Baloldalt ismét növelve kapjuk, hogy:

∑_{i=1}^{j} |P_{i}| > 2B ∑_{k=1}^{u−1} m_{k}s̄_{k}.  (18)

Kombinálva a (17) és (18)- os egyenlőtlenségeket

\begin{aligned}2 ∑_{i=1}^{j} |P_{i}| & > 2B ∑_{k=1}^{u−1} m_{k}s̄_{k} + 2B ∑_{k=u}^{v} m_{k}s̄_{k} \\ & > 2B ∑_{k=1}^{v} m_{k}s̄_{k}. \end{aligned}  (19)

Ez pedig ellentmond a (16)-os egyenlőtlenségnek.

Következmény 3.10. Ha P_{j} lánc az i sebességű gépre lett kijelölve, akkor \frac{|P_{j}|}{s̄_{i}} ≤ 2B.

Következmény 3.11. Az algoritmusunk minden láncot kijelöl egy gépre.

Bizonyítás: Tegyük fel, hogy néhány lánc megmarad, miután az utolsó s̄_{K} sebességet is megvizsgálta az algoritmus. Ekkor az 3.9-es lemma szerint D_{i} > 2B minden 1 ≤ i ≤ K. Ebből következik, hogy ∑_{j=1}^{n} p_{j} ≥ 2B ∑_{k=1}^{K} m_{k}s̄_{k}, ami megsérti a B ≥ AL = (∑_{j=1}^{n} p_{j})/(∑_{k=1}^{K} m_{k}s̄_{k}) feltételt.

Lemma 3.12. Minden 1 ≤ k ≤ K-ra, D_{k} ≤ 4C_{max}^{∗}.

Bizonyítás: Mivel B ≤ C_{max}^{∗}, és az algoritmus szabályából következően egy gép átlagos futási ideje nem több, mint 4B, azonnal következik a korlát.

Lemma 3.13. Az algoritmus által adott futási időre: C ≤ 2KC_{max}^{∗}.

Bizonyítás: Legyen P egy lánc. Megmutatjuk, hogy ∑_{j∈P} p_{j}/s̄_{k(j)} ≤ 2KC_{mx}^{∗}, ahol k(j) az a sebesség, melyre az algoritmusunk j-t kijelölte. Legyen A_{i} a P azon munkáinak halmaza, melyeket s̄_{i}-re jelöltünk ki. Legyen P_{l_{i}} a leghosszabb lánc, melyet s̄_{i}-re jelölt az algoritmusunk. Ekkor |P_{l_{i}}| ≥ ∑_{j∈A_{i}} p_{i}. Ez igaz, mivel A_{i} munkái láncot alkotnak, mikor a P_{l_{i}} a leghosszab lánc egy maximális lánckompozicióban. Ekkor az 3.10-es következmény szerint |P_{l_{i}}|/s̄_{i} ≤ 2B ≤ 2C_{max}^{∗}. Ekkor

∑_{j∈P} \frac{p_{j}}{s̄_{k(j)}} = ∑_{i=1}^{K} \frac{∑_{j∈A_{i}} p_{j}}{s̄_{i}} ≤ ∑_{i=1}^{K} |P_{l_{i}}|/s̄_{i} ≤ 2KC_{max}^{∗}.

Tétel 3.14. Használva a sebességen alapuló listás ütezemést az Algoritmusunk egy 6K aproximációs algoritmus ad, ahol K a különböző sebességek száma. Sőt, az Algoritmusunk 𝒪(n^{3}) időben fut. Amennyiben minden p_{j} egyenlő, a futási idő 𝒪(n^{2}\sqrt{n}).

Bizonyítás: 3.12-es lemmából kapjuk, hogy D_{k} ≤ 4C_{max}^{∗} minden 1 ≤ k ≤ K-ra, és 3.13-as lemmából pedig, hogy C ≤ 2KC_{max}^{∗}. Ezeket összerakva a 3.1-es tétel felső korlátjával:

C_{max} ≤ C + ∑_{k=1}^{K} D_{k} ≤ 2KC_{max}^{∗} + 4KC_{max}^{∗} ≤ 6KC_{max}^{∗}.

A sebességen alapuló listás ütemezés 𝒪(n log n) idő alatt futattható. Ezért a domináns idő az, mikor a maximális láncfelbontást kiszámoljuk, azaz 3.8-as tétel adja a tételben szereplő korlátot.

3.3. Q|chains|C_{max}

Amennyiben a megelőzési gráf láncok uniója, Woeginger [18] adott egy 2-approximációs algoritmust a feladatra. Ehhez azonban felhasználja, hogy a Q||C_{max} feladatra – mely szintén 𝒩𝒫-nehéz – az LPT-sorrend szerinti listás ütemezés 2-approximációs megoldást ad. Nézzük tehát ezt a bizonyítást:

A Q|pmtn|C_{max} feladat optimuma polinom időben elérhető, Labetoulle, Lawler, Lenstra, Rinnooy Kan [15] adtak rá egy algoritmust. Legyen ez az optimum C_{p}^{∗}. Ekkor a Q||C_{max} feladat egy megengedett megoldását adó algoritmus legyen a következő:

1. Rakjuk LPT sorrendbe a munkákat, (p_{1} ≥ p_{2} ≥ ... ≥ p_{n}).

2. Sorrendbe haladva a következő munkát mindig arra a gépre rakjuk, amelyiken a leghamarabb befejeződik.

Tétel 3.15. Az algoritmus mindig olyan ütemezést ad, melyre

C_{max} ≤ (2 − \frac{1}{m}) C_{p}^{∗}.

Bizonyítás: Indirekt tegyük fel, hogy nem igaz, vegyünk egy olyan ellenpéldát, melyre m minimális és erre nézve n minimális. Megfigyelés:

• n ≥ m, ugyanis, ha n < m, akkor a leglassabb gépet elhagyva sem C_{max}, sem C_{p}^{∗} nem változik, így kisebb elemszámú ellenpéldához jutnánk.

• Az utolsó munka rontja el a tétel állításában szereplő egyenlőtlenséget, azaz j_{n} nélkül: C_{max} ≤ C_{p}^{∗}.

Ekkor legyen L_{i} az i-dik gépre kerülő munkák összmegmunkálási ideje j_{n} nélkül, s legyen ekkor L = ∑_{i=1}^{m} L_{i} + p_{n}. Ekkor bármelyik gépre is kerülne a j-dik munka, azon a gépen a munkaidő nagyobb lesz, mint C_{p}^{∗}(2 − \frac{1}{m}), azaz:

(2 − \frac{1}{m}) C_{p}^{∗} < \frac{L_{i} + p_{n}}{s_{i}} , minden 1 ≤ i ≤ m,

azaz

s_{i} (2 − \frac{1}{m}) C_{p}^{∗} < L_{i} + p_{n}, minden 1 ≤ i ≤ m.

Ezeket összeadva minden i = 1, ..., m-ig:

(2 − \frac{1}{m}) C_{p}^{∗} ∑_{i=1}^{m} s_{i} < ∑_{i=1}^{m} L_{i} + mp_{n} = L + (m − 1)p_{n}.

Másrészt

(∑_{i=1}^{m} s_{i}) C_{p}^{∗} ≥ L,

Az utolsó két egyenlőtlenséget összegezve:

(2 − \frac{1}{m}) L < L + (m − 1)p_{n},

majd rendezve:

L < mp_{n}.  (20)

Mivel a munkákat LPT sorrend szerint ütemeztük, így nyilván

L ≥ np_{n}.

Az első megfigyelés szerint n ≥ m, így

L ≥ mp_{n}.  (21)

Ez viszont ellentmond az (20) egyenlőtlenségnek.

Következmény 3.16. A fent bemutatott algoritmus 2-approximációs megoldást ad a Q||C_{max} feladatra.

Bizonyítás: Ez következik abból, hogy C_{p}^{∗} alsó korlátja lesz az optimumnak.

Tekintsük most a Q|chains|C_{max} feladatot: Legyen ennek az optimális megoldása C_{max}^{∗}. Definiálunk egy olyan feladatot, melyekben nincsenek megelőzési feltételek: legyen minden L lánchoz rendelve egy j_{L} munka, melynek futási ideje legyen p_{j_{L}} = ∑_{i∈L} p_{i}. Az új feladat egy megengedett megoldásához meghatározhatunk az eredeti feladat egy megengedett megoldását, mégpedig az egyes lánc munkáit egymás után ütemezzük arra a gépre, melyre a módosított feladatunk a láncnak megfelelő munkát rakta. Tehát az új feladat optimuma – C_{N}^{∗} – felső korlátja lesz C_{max}^{∗}-nak. Továbbá, tekintsük ismét a Q|pmtn|C_{max} feladatot, az eredeti feladatunk munkáival – ami ugyanaz, mintha láncoknak megfeleltetett j_{L} munkáival néznénk – s legyen ennek az optimuma C_{p′}^{∗}. Ekkor egyrészről az eredeti feladat bármely megoldása megengedett megoldása lesz a Q|pmtn|C_{max} - feladatnak, így C_{p′}^{∗} alsó korlátja lesz C_{max}^{∗}-nek, másrészről a 3.15 tétel szerint

C_{N}^{∗} ≤ (2 − \frac{1}{m}) C_{p′}^{∗},

így

C_{p′}^{∗} ≤ C_{max}^{∗} ≤ (2 − \frac{1}{m}) C_{p′}^{∗},

azaz ez a relaxált feladat egy 2-approximációs megoldását adja a Q|chains|C_{max} feladatnak.

3.4. Q2|chains, p_{j} = 1|C_{max}

Adva van két gép, melyek sebessége különböző: legyen M_{2} gép gyorsabb, mint M_{1}, azaz az egységnyi munkát a második gép végezze el p_{2} = p idő alatt, melyre p < p_{1} = 1, és feltehetjük, hogy p ∈ ℚ. Legyen adva továbbá a munkák halmazán egy részben rendezés, melynek gráfja k láncból áll, melyeken rendre n_{1} ≤ n_{2} ≤ ... ≤ n_{k} munka van. Így n = ∑ n_{j}. Feladat a következő: ütemezzük az n munkát a két gépre úgy, hogy egy munka csak akkor kerülhet gépre, amikor az elődje – ha van – már végzett. Ezen feltételek mellett minimalizáljuk az utoljára végződő munka időpontját. Brucker, Hurink és Kubiak [4] úgy oldották meg a feladatot, hogy elsőnek nézték a feladat két speciális esetének – egyszerű – megoldását, majd ezek segítségével adtak egy megoldást a fenti problémára. Az egyik eset, mikor megengedett, hogy megszakítsuk a munkák végzését. Nyilván, ha ezen feladatra létezik optimális megoldás, melyben nem szakítunk meg egy munkát sem, az optimális lesz az eredeti feladatra is. A másik speciális eset, mikor eltekintünk a megelőzési feltételektől.

3.4.1. Q2|chains, pmtn, p_{j} = 1|C_{max}

Megjegyzendő, hogy legfeljebb két alkalommal szükséges a munkákat megszakítani, így, ha a megszakított munkát töröljük az M_{1} gépről és átrakjuk M_{2} végére, akkor olyan ütemezést kapunk, ami legfeljebb 2p-vel tér el az eredeti feladatunk optimális megoldásától. Három eset lehetséges aszerint, hogy az első lánc hossza és a többi lánc között milyen összefüggés áll fenn, melyek a következők lehetnek [Egyszerűség kedvéért használjuk az ábrát].

1. n_{1} ≤ p(n − n_{1}):

- 1 - - 1 - - 2 - - 2 - 3
3 4 - 5 - 6 - 7 - 8 - 9 -

Ütemezzük ekkor az első lánc munkáit M_{1}-re, a többi lánc munkáit sorba az M_{1}-re, illetve M_{2}-re, illetve azon lánc munkáit melyek mindkét gépen futnak, értelemszerűen sorbarendezhetjük.

2. pn_{1} ≥ n − n_{1}:

2 - 2 - 2 - 3 - 3 - 3 - 4 - .
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Ekkor ütemezzük az első lánc munkáit a második gépre, az összes többi lánc munkáit pedig az elsőre.

3. p(n − n_{1}) < n_{1} < (n − n_{1})/p:

1 - 1 - 1 - 2 - 2 - 2 - 2 -
. 3 3 4 4 4 4 1 1 1 1 1 1 1

Ekkor ütemezzük úgy a munkákat, hogy minden pillanatban legyen (1) láncbeli munka valamelyik gépen. A másik gépen pedig sorban a többi láncbeli munkák fussanak.

3.4.2. Q2|p_{j} = 1|C_{max}

Amennyiben y munkát ütemezünk az M_{2} gépre, (azaz n − y munkát az M_{1} gépre), a célfüggvényértéke

max{py, n − y}.  (22)

Keressük azt az egész y-t, (0 ≤ y ≤ n), mely minimalizálja (22)-t. Ez kiszámítható, ha megoldjuk a py = n − y egyenletet, majd le- vagy felkerekítjük a ȳ = \frac{n}{p+1} megoldást, attól függően, hogy mely kerekített érték minimalizálja a (22)-t.

Azaz az optimális y^{∗} megoldás:

y^{∗} := \{ \begin{matrix}⌈\frac{n}{p+1}⌉ & ha n − ⌊\frac{n}{p+1}⌋ ≥ p ⌈\frac{n}{p+1}⌉, \\ ⌊\frac{n}{p+1}⌋ & különben. \end{matrix}

A hozzátartozó célfüggvényérték C̄ = py^{∗}, ha y^{∗} = ⌈\frac{n}{p+1}⌉ és C̄ = n − ⌊\frac{n}{p+1}⌋ különben. Könnyen látható, hogy y^{∗} és C̄ konstans időben kiszámítható.

3.4.3. Q2|chains, p_{j} = 1|C_{max}

Az ötlet a következő: Elsőnek oldjuk meg azon relaxációját a feladatnak, mikor eltekintünk a megelőzési feltételektől. Legyen a k lánc munkák szerint csökkenően sorba rakva, azaz (1), ..., (k), melyre n_{1} ≥ n_{2} ≥ ... ≥ n_{k}, és n = ∑_{j=1}^{k} n_{j}. Legyen továbbá m_{1} (m_{2}) az M_{1} (M_{2}) gépre ütemezett munkák száma egy optimális megoldásban. Feltehetjük, hogy pn_{1} < C̄, mivel ellenkező esetben ütemezzük az (1) lánc munkáit sorba M_{2}-re, míg az összes többi munkát M_{1}-re, és ez optimális ütemezés lesz! Legyen x_{1} ≤ n_{1} olyan maximális egész szám, melyre x_{1} + p(n_{1} − x_{1}) ≤ C̄ (x_{1} = ⌊\frac{C̄−pn_{1}}{1−p} ⌋) . Ha x_{1} = n_{1}: ütemezzük az (1) lánc munkáit M_{1}-re és utána sorba a többi, (2), (3), ... lánc munkáit, amíg m_{1} munka nincs M_{1} gépre rakva, majd ha az (i) lánc munkái voltak az utolsók M_{1}-en, ütemezzük (i) további munkáit M_{2}-re, majd az (i + 1), (i + 2) ..., (k) láncok munkáit is sorba M_{2}-re. Ezek után (i) lánc munkáit rendezzük úgy át, hogy a megelőzési feltételek teljesüljenek. Ekkor az ütemezés megengedett lesz, és optimális is, mivel a célfüggvény értéke C̄. Amennyiben 0 ≤ x_{1} ≤ n_{1}: Ekkor az ábra jelöléseit használva, a rés az (1) lánc M_{1}-re ütemezett utolsó munkája (ami x_{1} időpontban ér véget) és az M_{2}-re ütemezett első munkája között legyen Δ, melyre Δ < 1 − p < 1.

M_{1}  (1)
M_{2}  (1)
0  x_{1}  x_{1} + Δ  \overline{C}

Ekkor két eset lehetséges: Amennyiben n_{k} < m_{1} − x_{1}: A (k)-adik láncot ütemezzük M_{1}-re, rögtön (1) lánc munkái után, majd sorba a következő m_{1} − (x_{1} + n_{k}) helyre ütemezzük a többi munkát M_{1}-re, és m_{2} − (n_{1} − x_{1}) munkát az M_{2} gépre az (1) lánc munkái elé. Mivel az első gépen futó (k) lánc első munkája lefedi a rést x_{1} és x_{1} + Δ között, e megengedett megoldás célfüggvényértéke C̄ lesz.

M_{1}  (1)  (k)
M_{2}  (1)
0 x_{1} x_{1} + Δ \overline{C}

Amennyiben n_{k} > m_{1} − x_{1}: Elsőnek ütemezzünk x_{k} := m_{1} − x_{1} munkát a (k)-adik láncból M_{1}-re jobbról balra, majd a maradék n_{k} − x_{k} (k)-láncbeli munkát M_{2} elejére. Ekkor ismételten két eset lehetséges: 1.eset: (k)-lánc munkái nem fedik át egymást a két gépen, ekkor a maradék munkákat gond nélkül ütemezhetjük M_{2}-re sorba a (k)-dik lánc és (1)-lánc munkái között. Mivel (k) lánc munkái nem fedik egymást, a kapott ütemezés megengedett lesz C̄ értékkel.

M_{1}  (1)  (k)
M_{2}  (k)  (1)
0  x_{1}  x_{1} + Δ  \overline{C}

2.eset: Van olyan pillanat, mikor mindkét gépen (k)-láncbeli munka fut. Ekkor, mivel (k) lánc munkái fedik egymást, biztos, hogy x_{k} ≥ 1. Bontsuk két esetre ismét a bizonyítást: első eset, mikor a második lánc munkái fedik egymást, azaz k = 2, második eset, mikor k ≥ 3.

M_{1}  (1)  (k)
M_{2}  (k)  (1)
0  x_{1}  x_{1} + Δ  \overline{C}

a) Amennyiben összesen két láncunk van (k = 2): A fenti - nem megengedett - ütemezésből kiindulva adunk megoldást a feladatra. Bemutatunk három megendegett ütemezését az (1) és (2) láncoknak, melyekre biztosított, hogy bármely optimális megoldás esetén az egyik fennáll. Ezek a következők:

• S1 ütemezésben

C_{max}(S_{1}) = x_{2} + (n_{2} − x_{2})p.

M_{1}  (1)  (2)
M_{2}  (2)  (1)
0  x_{1}  t_{1}  \overline{C} C_{max}(S_{1})

Ekkor az S1 ütemezés legalább olyan jó, mint bármely olyan ütemezés, mely x_{2} munkát ütemez a (2)-es láncból M_{1} gépre.

• S2 ütemezésben

C_{max}(S_{2}) = x_{1} + 1 + (n_{1} − x_{1} − 1)p.

M_{1}  (1)  (2)
M_{2}  (2)  (1)
0  t_{2}  x_{1} + 1  \overline{C} C_{max}(S_{2})

S2 ütemezés megengedett, mivel

t_{2} = t_{1} + p ≤ x_{1} + Δ + p < x_{1} + 1 − p + p = x_{1} + 1,

tehát S2 ütemezés legalább olyan jó, mint bármely olyan ütemezés, mely legalább x_{1} + 1 munkát ütemez az (1) láncból M_{1} gépre.

• S3 ütemezésben

C_{max}(S_{3}) = (m_{2} + 1)p.

M_{1}  (1)  (2)
M_{2}  (2)  (1)
0  x_{1}  t_{2}  \overline{C} C_{max}(S_{3})

S3 ütemezés megengedett, mivel

x_{2} − 1 ≤ C̄ − (x_{1} + 1) < C̄ − (x_{1} + Δ) = p(n_{1} − x_{1}).

Tehát S3 ütemezés legalább olyan jó, mint bármely olyan ütemezés, mely legalább m_{2} + 1 munkát ütemez M_{2}-re.

Lemma 3.17. Az S1, S2, és S3 ütemezések legjobbika optimális ütemezést ad.

Bizonyítás: Legyen S egy tetszőleges megengedett ütemezés, és legyen x̃_{1}, (illetve x̃_{2}) az a szám, ahány munkát ütemezünk az M_{1} gépre az (1) (illetve (2)) láncból. Ha x̃_{1} ≥ x_{1} + 1, akkor az S2 ütemezés optimálisabb, ha x̃_{2} ≥ x_{2}, akkor meg az S1 ütemezés jobb S-nél. Amennyiben x̃_{1} ≤ x_{1} vagy x̃_{2} ≤ x_{2} − 1, akkor x̃_{1} + x̃_{2} ≤ x_{1} + x_{2} − 1 = m_{1} − 1, és ezért legalább m_{2} + 1 munka fut az M_{2} gépen S ütemezésben. Azaz S3 lesz az optimálisabb. Tehát bármely megengedett ütemezéshez találhatunk olyan S1, S2, vagy S3 ütemezést, mely nála jobb, tehát e három ütemezés közül az egyik optimális.

b) Amennyiben k ≥ 3, ismét két esetre bontjuk a feladatot, attól függően, hogy az (1) lánc munkái M_{1}-en mennyi ideig futnak.

• x_{1} ≥ 1 Mikor eltekintünk a megelőzési feltételektől, (2), ..., (k − 1) láncok munkáit betehetjük az M_{2} gépre a (k) és (1) lánc közötti résbe. Mivel a rés nem nagyobb Δ < 1-nél, így mivel n_{2}p ≥ n_{k}p ≥ x_{1} ≥ 1, ellentmondásra jutottunk, azaz ez az eset nem fordulhat elő.

• x_{1} = 0 A következőkben bemutatunk két ütemezést S4-t és S5-t. S4 ütemezés legyen az, mikor az (1) lánc munkáit az M_{2} gépen rögtön az 0-dik időpillanattól elkezdjük. Ekkor az ütemezés értéke C_{max}(S4) = np. Az S5 ütemezés legyen a következő:

1. Ütemezzünk egy munkát a (k) láncból az M_{!} gépre az 0-dik pillanatra.

2. A többi (k)-beli munkát és az (1)-beli munkákat ütemezzük M_{2}-re a végére úgy, hogy az (1)-es lánc munkái előbb legyenek, mint a (k) munkái.

3. A maradék (2), ..., (k −1) lánc munkáit ütemezzük a tetszőlegesen megmaradt m_{1} −1 helyre M_{1}-en és m_{2} −(n_{1} +n_{k} −1) helyre M_{2}-n.

Ebben az ütemezésben a (2), ..., (k − 1) lánc munkái nem fedik majd egymást, mivel ezen láncok az M_{1}-en az 1 időpillanatban kezdődnek, míg M_{2}-n az utolsó munkák t_{3} időpillanatban érnek véget, melyre

t_{3} = p(m_{2}−(n_{1}+n_{k}−1)) = m_{2}p−(n_{1}+n_{k}−1)p ≤ C̄−n_{1}p−(n_{k}−1) ≤ C̄−n_{1}p < 1

Ezért amennyiben (k) lánc munkáit nem kezdjük el az M_{2}-n 1-nél hamarabb, az S5 ütemezés megengedett lesz. Kétféle eset lehet ekkor is, melyeket a következő ábrák mutatnak:

M_{1}  (k)  ...
M_{2} ...  (1)  (k)
0  t_{3}  1  \overline{C} C_{max}(S_{5})

M_{1}  (k)  ...
M_{2} ...  (1)  (k)
0  t_{3}  1  \overline{C}

Az első esetben (k) lánc határozza meg az ütemezés értékét, azaz C_{max}(S_{5}) = 1 + (n_{k} − 1)p. Mivel (k) a legrövidebb lánc, minden olyan ütemezés értéke, mely legalább egy munkát M_{1}-re rak, nagyobb vagy egyenlő, mint C_{max}(S_{5}). A második esetben S5 ütemezés értéke C̄, azért S5 optimális. Tehát S5 legalább olyan jó, mint bármely ütemezés, mely legalább egy munkát ütemez M_{1}-re. Ezért S4 és S5 közül a jobbik biztos optimális lesz.

Összegezve, a feladatot a következőképp oldhatjuk meg:

• Meghatározzuk a munkák számát, n-t, a leghosszabb lánc hosszát, n_{1}-t, illetve a legrövidebb lánc hosszát, n_{k}-t. (Ezt 𝒪(k) időben megtehetjük.)

• Megoldjuk a megelőzési feltételek nélkül a feladatot (konstans időben).

• Konstans időben végignézzük az eset szétválasztást, és kiválasztjuk a

megfelelő ütemezést. Tehát a feladat megoldható 𝒪(k) időben, de ha n, n_{1}, illetve n_{k} ismertek, abban az esetben konstans időben lefut az algoritmusunk. Ez a megoldás akkor is működik, ha p valós szám.

Hivatkozások

[1] M. Bender, C. Chekuri [2001]: An Efficient Approximation Algorithm for Minimizing Makespan on Uniform Related Machines

[2] P. Brucker [1995]: Scheduling Algorithms, Springer

[3] P. Brucker,M.R. Garey, D.S. Johnson [1977]: Scheduling equallength tasks under tree-like precedence contraints to minimize maximum lateness, Mathematics of Operations Research 2, 275-284

[4] P. Brucker, J. Hurink, W. Kubiak [1999]: Scheduling identical jobs with chain precedence constraints on two uniform machines, Mathematical Methods of Operations Research

[5] P. Brucker, J. Hurink, S. Knust [2001]: A polynomial algorithm for P |p_{j} = 1, r_{j}, outtree| ∑ C_{j}, Osnabrücker Schriften zur Mathematik, Reihe P, Heft 227

[6] F.A. Chudak, D.B. Shmoys [1997]: Approximation algorithms for precedence-constrained scheduling problems on parallel machines that run at different speeds,Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 581-590

[7] J. Edmonds [1965]: Minimum partition of a matroid into independent subsets, Journal of Research of the National Bureau of Standards 69B 67-72

[8] A. Frank: ELTE elektronikus jegyzet a Matroidelmélet c. sávelőadáshoz www.cs.elte.hu/ frank/jegyzet/jegyzet.html

[9] M.R.Garey, D.S. Johnson [1976]: Scheduling tasks with nonuniform deadlines on two processors, Journal of the Associaton for Computing Machinery 23, 461/467

[10] M.R.Garey, D.S. Johnson [1978]: Strong NP- completeness results: motivaton, examples and implications, Journal of the Association for Computing Machinery 25, 499-508

[11] R.L. Graham [1966]: Bounds of certain multiprocessing anomalies, Bell System Tech. J. 45 1563-1581

[12] R.L. Graham, E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan [1979]: Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics 5, 287-326.

[13] T.C. Hu [1961]: Parallel sequencing and assembly line problems, Operation Research 9, 841-848

[14] J. Jaffe [1980]: Efficient scheduling of tasks without full use of processor resources, Theoretical Computer Science 26,1-17

[15] J. Labetoulle, E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan [1984] Preemptive scheduling of uniform machines subject to release dates, W.R. Pulleyblank: Progress in combinatorial optimization, Academic Press, New York, 245-261.

[16] J.H. Lin, J.S. Vitter [1992]: ϵ-approximation with minimum packing constraint violation, Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 771-782

[17] O. Marcotte, L.E. Trotter, Jr. [1984]: An application of Matroid Polyhedral Theory to Unit-Execution Time, Tree-Precedence Job Scheduling, Progress In Combinatorial Optimization 263

[18] G.J. Woeginger [2000]: A comment on scheduling on uniform machines under chain-type precedence constraints,Operations Research Letters 26, no. 3, 107–109.