Plánování job-shopu (pokračování)
11. dubna 2023
Q Matematické programování a job shop
Q Metoda větví a mezí pro job shop
Q Posunování kritického místa (shifting bottleneck)
Disjunktivní programování
9 Formulace disjunktivního programování
• nejčastěji používaná formulace matematického programování pro job shop bez recirkulace
(bez recirkulace: úlohy prováděny na stroji nejvýše jednou)
• vychází z disjunktivní grafové reprezentace
• Disjunktivní programování
• jedná se o matematické programování
• omezení rozděleny do množin konjunktivních omezení
• všechna tato omezení musí být splněna
• standardní matematické programování: všechna omezení konjuktivní a jedné nebo více množin disjunktivních omezení
• z každé množiny disjunktivních omezení musí být alespoň jedno omezení splněno
Hana Rudová, Fl MU: Plánování job-shopu (pokračování)
2
11. dubna 2023
Disjunktivní programování a job shop
yij značí startovní čas operace (ij) úlohy j na stroji / Minimalizace Cmax za předpokladu
Ykj	-y<j	>
r	-y*	>
	-yn	>
	yij	>
V(/',i) ^ (k,j) e A V(/,i) e N
yij > Pij  V(/, /), :
i = 1... m
y (i, j) e N
9 Tato formulace ale nezajišťuje existenci standardní řešící procedury • Problém velmi obtížný
9 Ukážeme další přístupy: enumerační procedury (BB), heuristiky (posunování kritického místa)
Hana Rudová, Fl MU: Plánování job-shopu (pokračování) 3 11. dubna 2023
Typy rozvrhů
o Rozvrh je bez zdržení (nondelay), pokud žádný stroj nečeká, když existuje dostupná operace
• Rozvrh je aktivní, pokud nemůže být žádná operace rozvrhována dříve změnou posloupnosti úloh na stroji bez pozdějšího naplánování jiné operace
• redukce makespan aktivního rozvrhu je možná pouze zvýšením startovního času alespoň jedné operace
• optimální rozvrh je aktivní rozvrh
Hana Rudová, Fl MU: Plánování job-shopu (pokračování)
4
11. dubna 2023
Příklad: aktivní vs. neaktivní rozvrh
Neaktivní rozvrh M1
M2 M3
0
T
5
T"
10
T"
15
Aktivní rozvrh
M1 M2
	□		-HH
			1       . 1
		i-i                     r                 y - n I             I > '-1-1-1-^~*r	
Hana Rudová, Fl MU: Plánování job-shopu (pokračování)
11. dubna 2023
Aplikace metody větví a mezí na job shop
• Víme: optimální rozvrh je aktivní rozvrh 9 Metoda řešení
• generování množiny aktivních rozvrhů
• výběr nejlepšího rozvrhu
• Zlepšení
• použití metody větví a mezí při generování 9 Důsledek
• potřebujeme algoritmus pro generování všech aktivních rozvrhů
• Značení
• Q: množina všech operací, jejichž předchůdci už jsou narozvrhováni
• r,j\ nejdřívější startovní čas operace (ij) £ Q
• může být spočítáno pomocí výpočtu nejdelší cesty fi': podmnožina Q
Hana Rudová, Fl MU: Plánování job-shopu (pokračování)
6
11. dubna 2023
Generování množiny všech aktivních rozvrhů
O Inicializace
• Q := {první operace každé úlohy}
• r,j := 0 pro všechna (ij) G Q
O Výběr stroje
spočítej pro současný částečný rozvrh
ř(Q) := ™ÍnAru+Pij}
tj. kdy nejdříve může nějaká úloha z Q skončit
• /* := stroj, na němž bylo dosaženo minima O Větvení
• O.' := {(i*,j)\n.j < t(S2)}
• pro všechna (/*,./) G Q7
přidej do rozvrhu (i*J) jako další operaci na stroji / smaž (/*,./) z Q
přidej následníky úlohy (/*,./) do Q běž na krok 2
Hana Rudová, Fl MU: Plánování job-shopu (pokračování) 7 11. dubna 2023
*
Příklad: generování aktivních rozvrhů
• Úlohy: JI : (3,1)     (2,1) -> (1,1)
J2: (1,2) ->(3,2)
J3 : (2,3)     (1,3) ->■ (3,3)
• Částečný rozvrh:
• neřešíme od začátku, začneme řešit už s tímto rozvrhem aby byl postup demonštratívni
• Q = {(1,1), (3,2), (1,3)}
• pil = 1, p32 = 3, pl3 = 4    rll = 6, r32 = 4, r 13 = 3
• t(fi) = min(6 + 1,4 + 3, 3 + 4) = 7    např. /'* = Ml
• íľ = {(l,l),(l,3)}
• Rozšířené částečné rozvrhy:
M1^^^| O M1
M2        I       I       I M2
M3 I . M3
0 5 0
Hana Rudová, Fl MU: Plánování job-shopu (pokračování)
8
11. dubna 2023
Disjunkce vybrané při větvení
• Větvení algoritmu volí disjunkce
• Předpokládejme větvení ft' = {(/*,./), (/*, /)}
—>» výběr při větvení
přidání disjunkce (/*,./) —^ (/*, /c) pro všechny dosud nenarozvrhované operace (/*, /c)
—>» výběr (/*, /) při větvení
přidání disjunkce (/*, /) —>* (/*, /c) pro všechny dosud nenarozvrhované operace (/*, /c)
• Důsledek:
• každý uzel stromu je charakterizován množinou D' vybraných disjukcí
Hana Rudová, Fl MU: Plánování job-shopu (pokračování)
9
11. dubna 2023
Výpočet dolní hranice
Předpokládejme uzel V s vybranými disjukcemi D' 9 Jednoduchá dolní hranice
• spočítej kritickou cestu v G(D') dolní hranice LB{V)
• Vylepšená dolní hranice
• uvažuj stroj /
• povolíme překrývání operací na všech strojích kromě /
• vyřeš problém na stroji /
Hana Rudová, Fl MU: Plánování job-shopu (pokračování)
10
11. dubna 2023
Podproblém: 1 n L
max
• Vypočítej nejdřívější startovní čas r,y všech operací (ij) na stroji /
• nejdelší cesta ze zdroje v G(D!)
9 Vypočítej minimální množství času A,y mezi: startem operace (ij) (tj. rjj) a
koncem rozvrhu (nejdelší cesta v G(D') z uzlu do stoku)
• Získáme termíny dokončení cf,y = LB(V) — A,y + p,y
Pij
tdij
LB(V)|
time
• Vyřeš výsledný problém: l|r/|Z.max • viz dříve
Hana Rudová, Fl MU: Plánování job-shopu (pokračování)
11
11. dubna 2023
Vylepšená dolní hranice
Vyřeš 1 rj Lmax pro všechny stroje
Výsledek: Li,..., L
m
LB
new
(V) = LB(V)+ max L;
i=l...m
tj. výsledné řešení nemůže mít lepší kvalitu než nejlepší možné řešení pro každý stroj zvlášť, a proto zahrneme do dolní hranice nejhorší (největší) spočítané zpoždění
9 Poznámky:
je NP-úplný problém
• experimentálni výsledky přesto ukazují, že se vyplatí řešit m NP-úplných problémů pro každý uzel stromu
• 20 x 20 instance jsou už obtížně řešitelné metodou větví a mezí
Hana Rudová, Fl MU: Plánování job-shopu (pokračování)
12
11. dubna 2023
Příklad: dolní hranice
Částečný rozvrh
Odpovídající graf
M2 M3
0
T
5
pár disjuktivních dosud nevybraných hran vybrané disjunktivní hrany ^ konjuktivní hra
hrany G(D')
Hana Rudová, Fl MU: Plánování job-shopu (pokračování)
13
11. dubna 2023
Příklad: dolní hranice
Graf G(D') s dobami provádění:
4a, 2
Le(V) = /(íy,(l,2),(l,3),(3,3), V) = 8
Data pro úlohy na stroji Ml
modrá	zelená	červená
Al2 = 0	ri3 = 3	rn = 6
Ai2 = 8	Ai3 = 5	An = l
efo = 3	dis = 7	du = 8
(víme: d;j = LB(V) - A,y + p,y)
Optimální řešení: Z.max = 0, LBnewt(V)
M1
Hana Rudová, Fl MU: Plánování job-shopu (pokračování)
= 8
■_ ■
7 8
14
11. dubna 2023
Příklad: dolní hranice
Změna pil z 1 na 2
2<^> 4
LB(V) = I(U, (1,2), (1,3), (3,3), V)
= I(U,(3,1),(2,1),(1,1), V/) = 8
Data pro úlohy na stroji Ml
modrá	zelená	červená
Al2 = 0	13 = 3	rn = 6
Ai2 = 8	Ai3 = 5	An = 2
^12 = 3	dí3 = 7	dn = 8
Optimální řešení: Lmax = 1, LBnew{V) = 9
M1
0
■
7
Hana Rudová, Fl MU: Plánování job-shopu (pokračování)
15
11. dubna 2023
Posunování kritického místa
(shifting bottleneck)
• Úspěšná heuristika
při řešení problému minimalizace makespan pro job shop
• Základní popis
• iterativní heuristika
• v každé iteraci je určen rozvrh pro jeden další stroj
• používána re-optimalizace pro změnu už narozvrhovaných strojů
• Rozšiřitelnost: metoda lze rozšířit na obecnější job shop problémy
• další objektivní funkce
• flexible flow shop
(paralelní stroj místo samostatných strojů)
• nastavovací doba stroje
Hana Rudová, Fl MU: Plánování job-shopu (pokračování)
16
11. dubna 2023
Princip algoritmu
• Značení
• M je množina všech strojů 9 Dáno
• určen rozvrh pro podmnožinu Mq C M strojů
• tj. je určen výběr disjunktivních hran
o Akce při jedné iteraci
O výběr stroje k, pro který ještě neexistuje rozvrh
• tj. stroj z M\M0
O určení rozvrhu (výběru disjunktivních hran) pro stroj k na základě daných (zafixovaných) rozvrhů pro stroje z Mq
O nové rozvrhování (= přeplánování) všech strojů z Mq na základě ostatních daných (zafixovaných) rozvrhů, tj. přeplánujeme jeden stroj po druhém
Hana Rudová, Fl MU: Plánování job-shopu (pokračování)
17
11. dubna 2023
Princip výběru stroje a určení jeho rozvrhu
• Myšlenka:
• výběr ještě nerozvrženého stroje, který působí nejvíce problémů, tzv. kritický (bottleneck) stroj
9 Realizace:
• spočítej pro každou operaci na nenarozvrhovaném stroji
• nejdřívější možný startovní čas a
• minimální zdržení mezi koncem operace a koncem úplného rozvrhu založeného na
• zafixovaných rozvrzích strojů v Mq a
• pořadí úloh
• spočítej pro každý nenarozvrhovaný stroj rozvrh respektující tyto nejdřívější termíny dostupnosti a zdržení
9 vyber stroj s maximálním koncovým časem a zafixuj rozvrh na tomto stroji
Hana Rudová, Fl MU: Plánování job-shopu (pokračování)
18
11. dubna 2023
Princip přeplánování strojů
• Myšlenka:
• snaha redukovat makespan rozvrhu pro stroje v Mq
• Popis:
• uvažuj stroje z Mq jeden po druhém
• smaž rozvrh vybraného stroje a spočítej nový rozvrh na základě
• nejdřívějšího startovního času a
• zdržení
vyplývající z
• ostatních strojů v Mo a
• pořadí úloh
Hana Rudová, Fl MU: Plánování job-shopu (pokračování)
19
11. dubna 2023
Plánování job-shopu: shrnutí
Modelování a reprezentace o disjunktivní grafová reprezentace
• matematické programování a job shop (+ řešení)
Řešení
• metoda větví a mezí pro job shop
• heuristika: posunování kritického místa
Hana Rudová, Fl MU: Plánování job-shopu (pokračování)
20
11. dubna 2023