Overzicht
• Inleiding
• Classificatie
• NP compleetheid
• Algoritme van Johnson
• Oplossing via TSP
• Netwerkalgoritme
Job shop scheduling
1
Inleiding Gegeven zijn • Machines: M1, M2, . . . , Mm • Taken: T1, T2, . . . Tn • Per taak Ti de deeltaken: Ti1, Ti2, . . . , Tim • Deeltaak Tij heeft procestijd pij Voer de taken uit als volgt • Per taak Ti maximaal ´ e´ en deeltaak Tij tegelijk. • Per machine Mj maximaal ´ e´ en deeltaak Tij tegelijk. • Deeltaken kunnen niet worden onderbroken Doel Minimaliseer de totale procestijd cmax. Job shop scheduling
2
Voorbeeld GANTT diagram M1 T31 M2 T42 M3 T13 0
T11 T22
T41 T32
T52 T33
T53 5
T21
10
T51 T12 T23 15
T43
t
20 cmax
Machine-volgorde per taak Taak 1: 3,1,2 Taak 2: 2,1,3 Taak 3: 1,2,3 Taak 4: 2,1,3 Taak 5: 3,2,1 Taak-volgorde per machine Machine 1: 3,1,4,2,5 Machine 2: 4,2,3,5,1 Machine 3: 1,5,3,2,4 Job shop scheduling
3
Classificatie
In bepaalde klassen problemen worden machine-volgorden en/of taak-volgorden voorgeschreven. Type Open Shop Job Shop Flow Shop Permutation Shop No Wait Flow Shop
Machine-volgorde Vrij Vast Vast, gelijk Vast, gelijk Vast, gelijk (direct aaneen)
Taak-volgorde Vrij Vrij Vrij Gelijk Vrij (=gelijk)
Notatie O||Cmax J||Cmax F ||Cmax P F ||Cmax N W ||Cmax
Er zijn veel uitbreidingen mogelijk, bijvoorbeeld: • Volgorde relaties tussen taken onderling • Meer deeltaken per taak per machine • Per taak een minimale starttijd / maximale eindtijd Job shop scheduling
4
Complexiteit: Fm||Cmax is NP-compleet voor m ≥ 3 Knapzakprobleem Gegeven positieve gehele getallen a1, a2, . . . aq en b. Bestaat er een deelverzaP meling B ⊂ {1, 2, . . . , q} zodanig dat ai = b? i∈B
Dit is herleidbaar tot F3||Cmax met q + 1 taken, waarbij elke taak drie deeltaken heeft met de volgende procestijden: (0, ai, 0) b, 0,
q P
i=1
M1 M2 M3
ai − b
! 1≤i≤q
q+1
b a1
...
ak
ak+1
... P
aq
ai − b
Uit dit voorbeeld van een produktieschema blijkt: cmax =
t cmax q P
i=1
ai + δ met
δ ≥ 0 en δ = 0 d.e.s.d.a. het knapzakprobleem een oplossing heeft. Job shop scheduling
5
Stelling voor Fm||Cmax Voor een Fm||Cmax probleem bestaat er een optimaal produktieschema waarin de taakvolgorden voor de eerste twee machines gelijk zijn. Bewijs: Stel dat we een optimaal produktieschema hebben, waarin machine 1 taak j direct na taak i behandelt, terwijl machine 2 taak i na taak j behandelt. M1 M2
i
j j
i
t
Wisselen van taak i en taak j op machine 1 geeft een gelijke taakvolgorde voor i en j op de eerste 2 machines! Analoge stelling: Voor een Fm||Cmax bestaat er een optimaal produktieschema waarin de taakvolgorden voor de beide laatste machines gelijk zijn. Gevolg: Als m ≤ 3 dan bestaat er voor elk Fm||Cmax probleem een optimaal produktieschema waarin alle taakvolgorden gelijk zijn (een permutatie produktieschema dus). Job shop scheduling
6
Voor m ≥ 4 is Fm||Cmax 6= P Fm ||Cmax Neewm m = 4 en n = 2 en stel dat de procestijden voor de eerste taak 1,4,4,1 en voor de tweede taak 4,1,1,4 zijn. De twee mogelijke permutatieschema’s zijn: M1 1 M2 M3 M4
2 1
2 1
0 M1 M2 M3 M4
2 1
5 2
2
10
1 2
cmax
1 2
1 2
0
t
1
5
10
t
cmax
Een beter produktieschema met een gelijke machinevolgorde is echter: M1 1 M2 M3 M4 0
Job shop scheduling
2 1
2 2 5
1 2
1 10
t
cmax
7
(P )F2 ||Cmax
Notatie:
(
ai = pi1 bi = pi2
Definitie: i ≺ j ⇔ min(ai, bj ) ≤ min(aj , bi) Merk op dat voor elk tweetal taken geldt i ≺ j of j ≺ i. Lemma Stel dat in een produktieschema voor een P F2||Cmax probleem taak Ti direct na taak Tj wordt uitgevoerd, terwijl i ≺ j. Dan bestaat er een minstens zo goed produktieschema waarin Ti direct voor Tj wordt uitgevoerd. Dit schema ontstaat uit het gegeven schema door Ti en Tj eenvoudig te verwisselen. M1 M2
... ... cmax
Job shop scheduling
t 8
Bewijs van het lemma
M1 M2
aj
ai
j
i
xi j
xj
i
bj
t
bi
Omdat ai + xi = bj + xj geldt ai ≤ bj + xj (*). Wanneer we Ti en Tj wisselen is de situatie als volgt: M1 M2
ai
aj
i
j i
aj + xj
Het schema is toelaatbaar als:
j
t
bi
(
ai ≤ aj + xj ai + aj ≤ aj + xj + bi
Uit i ≺ j volgt min(ai, bj ) ≤ min(aj , bi). Als min(ai, bj ) = ai dan is het nieuwe schema zeker toelaatbaar. Als min(ai , bj ) = bj , dan volgt met (*): ai ≤ bj + xj ≤ aj + xj en ai ≤ bj + xj ≤ bi + xj . Job shop scheduling
9
Algoritme van Johnson voor F2||Cmax Stelling 1. Als min(ai, bi : 1 ≤ i ≤ n) = ak dan is er een optimaal produktieschema waarin Tk het eerst behandeld wordt. 2. Als min(ai, bi : 1 ≤ i ≤ n) = bk dan is er een optimaal produktieschema waarin Tk het laatst behandeld wordt. Algoritme
B := {i : ai < bi}
F := {i : ai ≥ bi}
Orden de taken in B zodanig dat ai niet afneemt en orden de taken in F zodanig dat bi niet toeneemt. Vorm de concatenatie van de geordende verzamelingen B en F . Dit is de optimale taakvolgorde. Voorbeeld
Taak i ai bi
1 6 3
2 2 9
3 4 3
4 1 8
5 7 1
6 4 5
7 7 6
B = {2, 4, 6} en F = {1, 3, 5, 7}. Na ordenen geldt: B = {4, 2, 6} en F = {5, 1, 3, 7}. Een optimale taakvolgorde is dus T4, T2, T6, T5, T1, T3, T7. Job shop scheduling
10
No wait flow shop
In een no-wait flow shop moeten de deeltaken van een taak direct na elkaar worden uitgevoerd. Het oplossen van dit probleem komt neer op het oplossen van een TSP. Dit is als volgt in te zien. Stel dat taak Tj direct na Ti wordt uitgevoerd. De minimale tijd benodigd voor het uitvoeren van taak Tj en Ti in deze volgorde is Pi + cij . Introduceer een dummy taak 0 met alle procestijden van de deeltaken gelijk aan 0 en definieer verder ci0 = 0 en coi = Pi . Dan resteert een TSP met n + 1 taken.
Job shop scheduling
11
