Plánování úloh (na jednom stroji)
4. dubna 2023
1 Řídící pravidla
2 Metoda větví a mezí
3 Paprskové prohledávání
4 Matematické programování
Jeden stroj a paralelní stroj
Dekompoziční problémy pro složité (flexible) job shop problémy
používají
jeden stroj
paralelní stroj
jako podproblémy při řešení
Metody řešení:
řídící pravidla
metoda větví & mezí
paprskové prohledávání
Hana Rudová, FI MU: Plánování úloh (na jednom stroji) 2 4. dubna 2023
Řídící pravidla pro jeden stroj: přehled
Cmax a rj = 0, dj = ∞ (snadné: nezávisí na rozvrhu)
wj Cj a rj = 0, dj = ∞
vážená nejkratší doba provádění (WSPT) je optimální
rozvrhuje úlohy v klesajícím pořadí podle wj /pj
Lmax a rj = 0
nejdřívější termín dokončení (EDD) je optimální
rozvrhuje úlohy ve vzrůstající velikosti dj
minimální rezerva (MS)
pravidlo příbuzné EDD ale dynamické
max(dj − pj − t, 0), kde je t aktuální čas
Lmax a rozdílné rj
NP-těžký problém
základní podproblém v rámci známé heuristiky posouvání kritického
místa
řešen pomocí metody větví a mezí nebo dynamického programování
Tj , wj Tj
mnohem obtížnější na optimalizaci
kompozitní řídící pravidlo apparent tardiness cost (ATC) využívající
kombinaci WSPT a MS
Hana Rudová, FI MU: Plánování úloh (na jednom stroji) 3 4. dubna 2023
Řídící pravidla a paralelní stroj: přehled
Cmax : důležité kritérium při balancování zátěže strojů
NP-těžký
nejdelší doba provádění (LPT)
kratší úlohy odloženy, protože je snadnější je narozvrhovat
nalezne řešení s garancí rozsahu 33% optima
Cj a rj = 0
nepreemptivní nejkratší doba provádění (SPT)
nepreemptivní SPT minimalizuje Cj
nepreemptivní SPT zůstává optimální i při povolených přerušeních
wj Cj a rj = 0
NP-těžký
WSPT grarantuje řešení v rámci 22% optima
wj Tj
ještě obtížnější problém
lze použít ATC (apparent tardiness cost), ale kvalita řešení nemusí být
dobrá
Hana Rudová, FI MU: Plánování úloh (na jednom stroji) 4 4. dubna 2023
Vážený součet koncových časů pro jeden stroj
Řídící pravidlo vážená nejkratší doba trvání
(weighted shortest processing time, WSPT)
je optimální pro 1|| wj Cj .
WSPT rozvrhuje úlohy v klesajícím pořadí podle wj /pj
Důkaz:
předpokládejme, že to není pravda a že S je optimální
pak existují dvě sousední úlohy, např. úloha j následovaná úlohou k
takové, že
wj
pj
<
wk
pk
, tj.pkwj < pjwk
po provedení párové výměny máme rozvrh S
j kt+p +p
j k
t+p +p
j k
k j
... ...
... ...
S:
S’:
Příspěvky do účelové funkce pro j a k:
S : (t + pj )wj + (t + pj + pk )wk = twj + pj wj + twk + pjwk + pk wk
S : (t + pk )wk + (t + pk + pj )wj = twk + pk wk + twj + pkwj + pj wj
wj Cj pro S < wj Cj pro S spor s optimalitou S
Hana Rudová, FI MU: Plánování úloh (na jednom stroji) 5 4. dubna 2023
Zpoždění pro jeden stroj
EDD optimální pro 1||Lmax
Rozdílné termíny dostupnosti rj , tj. problém 1|rj |Lmax : NP-úplný
problém
Proč je tento problém tak obtížný?
Hana Rudová, FI MU: Plánování úloh (na jednom stroji) 6 4. dubna 2023
1|rj|Lmax
Úlohy 1 2 3
pj 4 6 5
rj 0 3 5
dj 8 14 10Rozvrh pomocí EDD:
r3
r2r1 d1 d3 d2
1
10 1550
32
Lmax = max(L1, L2, L3) =
= max(C1 − d1, C2 − d2, C3 − d3) =
= max(4 − 8, 10 − 14, 15 − 10) =
= max(−4, −4, 5) = 5
Existuje lepší řešení?
Hana Rudová, FI MU: Plánování úloh (na jednom stroji) 7 4. dubna 2023
Rozvrh se zdržením pro 1|rj|Lmax
Pozdržíme provádění úloh:
r3
r2r1 d1 d3 d2
21
10 1550
3 2
Lmax = max(L1, L2, L3) =
= max(C1 − d1, C2 − d2, C3 − d3) =
= max(4 − 8, 16 − 14, 10 − 10) =
= max(−4, 2, 0) = 2
Problém je obtížný, protože
optimální rozvrh není nutně bez zdržení
Hana Rudová, FI MU: Plánování úloh (na jednom stroji) 8 4. dubna 2023
1|rj, prmp|Lmax
Preemptivní úlohy: je možné přerušit jejich provádění
Preemptivní verze řídících pravidel:
nečekáme až na dokončení prováděné úlohy
pro výběr další úlohy k provádění
v každém časovém okamžiku je nutné zvážit, zda není k dispozici
jiná prioritnější úloha (např. vzhledem k jejímu rj )
pokud existuje prioritnější úloha,
přerušíme aktuální úlohu a spustíme prioritnější úlohu
Cvičení: aplikujte preemptivní EDD na předchozí příklad
Preemptivní EDD pravidlo je optimální pro preemptivní verzi problému
1|rj , prmp|Lmax
Preemptivní EDD je optimální pro předchozí příklad
Hana Rudová, FI MU: Plánování úloh (na jednom stroji) 9 4. dubna 2023
Metoda větví a mezí
Prohledávací prostor se rychle zvětšuje se zvětšujícím počtem
proměnných
Metoda větví a mezí (Branch & Bound search, BB)
založena na myšlence postupného dělení prohledávacího prostoru
S
SS
SS S
. . .
. . .
. . .
12 13
1 2 n
S = S1 ∪ S2 ∪ · · · ∪ Sn S1 ∩ S2 ∩ · · · ∩ Sn = ∅
potřebujeme spočítat hranici/mez na cenu řešení
části stavového prostoru, které dávají řešení horší než tato mez
nemusíme prohledávat
Hana Rudová, FI MU: Plánování úloh (na jednom stroji) 10 4. dubna 2023
Výpočet dolní hranice řešení
Typický způsob, jak zjistit hranice je
relaxovat (zjednodušit) původní problém
(např. odstraněním některých požadavků)
na snadno řešitelný problém
jestliže neexistuje řešení pro relaxovaný problém,
pak neexistuje řešení pro původní problém
(větev lze smazat)
jestliže je optimální řešení relaxovaného problému zároveň řešením
původního problému,
pak je pro něj také optimální
jestliže optimální řešení není řešením původního problému, pak dává
hranici na jeho řešení
(původní problém nebude mít zcela jistě lepší řešení)
Hana Rudová, FI MU: Plánování úloh (na jednom stroji) 11 4. dubna 2023
Pravidla větvení pro 1|rj|Lmax
*,*,*,*
1,3,*,*1,2,*,*
2,*,*,*1,*,*,* n,*,*,*
. . .
. . .
. . .
Uroven 2
Uroven 1
Uroven 0
Rozvrh je konstruován od času t = 0
Úroveň 1:
n větví, ve kterých je každá z n úloh rozvrhována první
Úroveň k − 1:
úlohy j1, . . . , jk−1 jsou rozvrhovány v pořadí 1, . . . , k − 1
Úlohu c uvažujeme na úrovni k (a odpovídající větvení) pokud:
rc < minl∈J (max(t, rl ) + pl ) = PS
J množina dosud nerozvržených úloh
t čas, kdy je skončena jk−1 a lze rozvrhovat další úlohu
pokud je rc ≥ PS, pak je třeba rozvrhovat úlohu minimalizující PS
na pozici k a úlohu c na pozici k + 1 (nebo i později)
(toto uspořádání úloh stejně vůbec neovlivní čas dokončení c)
Hana Rudová, FI MU: Plánování úloh (na jednom stroji) 12 4. dubna 2023
Dolní hranice pro 1|rj|Lmax
Relaxace problému 1|rj |Lmax je problém 1|rj , prmp|Lmax
neumožnění přerušení je omezení pouze v původním problému 1|rj |Lmax
Preemptivní EDD pravidlo je optimální pro 1|rj , prmp|Lmax
⇒ Preemptivní rozvrh (rozvrh bez zdržení) určitě nebude mít Lmax větší
než ne-preemptivní rozvrh (rozvrh potenciálně se zdržením)
⇒ Dolní hranice na úrovni k − 1 může být založena na rozvrhu
zbývajících úloh podle preemptivního EDD pravidla
+ Jestliže preemptivní EDD dává nepreemptivní rozvrh,
pak můžeme všechny uzly s větší dolní hranicí zrušit
Hana Rudová, FI MU: Plánování úloh (na jednom stroji) 13 4. dubna 2023
Příklad: BB pro 1|rj|Lmax
Úlohy 1 2 3 4
pj 4 2 6 5
rj 0 1 3 5
dj 8 12 11 10
2,*,*,* 4,*,*,*
1,3,*,*
1,3,4,2
3,*,*,*
uloha 2 muže být
prováděna před ulohou 3
uloha 1 muže být
prováděna před ulohou 4
*,*,*,*
1,2,*,*
1,*,*,*
LB=5
LB=6 LB=5
LB=7
1,4,*,* nemá smysl prozkoumávat,
protože už v 1,3,*,* máme šanci na řešení s minimání LB=5
Hana Rudová, FI MU: Plánování úloh (na jednom stroji) 14 4. dubna 2023
Příklad: dolní hranice BB pro 1|rj|Lmax
Úlohy 1 2 3 4
pj 4 2 6 5
rj 0 1 3 5
dj 8 12 11 10
(3,*,*,*)
uloha 2 muže
být prováděna
před ulohou 3
(4,*,*,*)
uloha 1 i 2 muže
být prováděna
před ulohou 3
(*,*,*,*)
(1,2,*,*)
1 [0,4] L =−4
2 [4,6] L =−6
4 [6,11] L =1
3 [11,17] L =6
2
1
3
4
(1,3,*,*)
1 [0,4] L =−4
3 [4,10] L =−1
4 [10,15] L =5
2 [15,17] L =52
4
3
1 Rozvrh: (1,3,4,2)
4
2
1
2 [1,3] L =−9
(2,*,*,*)
1 [3,7] L =−1
4 [7,12] L =2
3 [12,18] L =73
(1,*,*,*)
3 [4,5]
2 [15,17] L = 5
1 [0,4] L =−41
2
3
4
3 [10,15] L = 4
4 [5,10] L =0
Hana Rudová, FI MU: Plánování úloh (na jednom stroji) 15 4. dubna 2023
Paprskové prohledávání
Metoda větví a mezí
uvažuje každý uzel
pro n úloh:
na první úrovni n uzlů, na druhé úrovni n(n − 1) uzlů,
na třetí úrovni n(n − 1)(n − 2) uzlů, . . .
⇒ n! uzlů na n-té úrovni
garantuje optimum
obvykle příliš pomalá
Paprskové prohledávání (Beam Search, BS)
uvažuje pouze slibné uzly
šířka paprsku (beam width)
udává, u kolika uzlů budeme na každé úrovni pokračovat v prohledávání
negarantuje optimální řešení
mnohem rychlejší
Hana Rudová, FI MU: Plánování úloh (na jednom stroji) 16 4. dubna 2023
Větvení
Kriterium: 1|| j wj Tj
Problém:
Úlohy 1 2 3 4
pj 10 10 13 4
rj 4 2 1 12
dj 14 12 1 12
Šířka paprsku 2:
2,*,*,* 4,*,*,*3,*,*,*
*,*,*,*
1,*,*,*
(1,4,2,3) (2,4,1,3) (3,4,1,2) (4,1,2,3)
ATC pravidlo
408 436 814 440
Hana Rudová, FI MU: Plánování úloh (na jednom stroji) 17 4. dubna 2023
Paprskové prohledávání
2,*,*,*
2,4,*,*1,4,*,*
4,*,*,*3,*,*,*
2,1,*,*
2,4,1,3 2,4,3,11,4,3,2
1,2,*,*
1,4,2,3
*,*,*,*
1,*,*,*
2,3,*,*1,3,*,*
Hana Rudová, FI MU: Plánování úloh (na jednom stroji) 18 4. dubna 2023
Diskuse
Kompromisy při implementaci:
podrobná evaluace uzlů (kvůli přesnosti)
odhad evaluace uzlu (kvůli rychlosti)
Dvoufázová procedura
odhad evaluace
je prováděn pro všechny uzly na úrovni k
podrobná evaluace
šířka filtru > šířka paprsku
prováděna pro počet uzlů odpovídající šířce filtru
Hana Rudová, FI MU: Plánování úloh (na jednom stroji) 19 4. dubna 2023
Matematické programování (opakování)
Celočíselný program
minimalizace
n
j=1
cj xj
za předpokladu:
n
j=1
aij xj ≥ bi ∀i : 1 ≤ i ≤ m
xj ≥ 0 ∀j : 1 ≤ j ≤ n
xj ∈ Z ∀j : 1 ≤ j ≤ n
Hana Rudová, FI MU: Plánování úloh (na jednom stroji) 20 4. dubna 2023
Model problému 1| | n
j=1 wjCj
Proměnné xjt = 1 jestliže úloha j začne v čase t
= 0 jinak
Formulace celočíselného programu
Minimalizace
n
j=1
Cmax −1
t=0
wj (t + pj )xjt tj.
n
j=1
wj Cj
za předpokladu
xjt ∈ 0, 1 ∀j, t
každá úloha právě jednou začne:
Cmax −1
t=0 xjt = 1 ∀j
v každém čase běží právě jedna úloha:
n
j=1
t−1
s=max(t−pj ,0) xjs = 1 ∀t
(pro každé t běží v intervalu t − 1, t) právě jedna úloha)
Hana Rudová, FI MU: Plánování úloh (na jednom stroji) 21 4. dubna 2023
V každém čase jedna úloha
Proměnné xjt = 1 jestliže úloha j začne v čase t
V každém čase, tj. v každém intervalu t − 1, t ,
běží právě jedna úloha:
n
j=1
t−1
s=max(t−pj ,0)
xjs = 1 ∀t
Hana Rudová, FI MU: Plánování úloh (na jednom stroji) 22 4. dubna 2023
Plánování job-shopu
4. dubna 2023
5 Disjunktivní grafová reprezentace
Multi-operační rozvrhování:
job shop s minimalizací makespan
n úloh
m strojů
operace (i, j): provádění úlohy j na stroji i
Pořadí operací úlohy je stanoveno:
(i, j) → (k, j) specifikuje, že úloha j má být prováděna na stroji i dříve
než na stroji k
pij : trvání operace (i, j)
Cíl: rozvrhovat úlohy na strojích
bez překrytí na strojích
bez překrytí v rámci úlohy
minimalizace makespan Cmax
Hana Rudová, FI MU: Plánování job-shopu 24 4. dubna 2023
Příklad: job shop problém
Data:
stroje: M1, M2, M3
úlohy: J1 : (3, 1) → (2, 1) → (1, 1)
J2 : (1, 2) → (3, 2)
J3 : (2, 3) → (1, 3) → (3, 3)
doby trvání: p31 = 4, p21 = 2, p11 = 1
p12 = 3, p32 = 3
p23 = 2, p13 = 4, p33 = 1
Řešení:
105 12
M3
M2
M1
0
Hana Rudová, FI MU: Plánování job-shopu 25 4. dubna 2023
Disjunktivní grafová reprezentace
Graf G = (N, A ∪ B ∪ P)
uzly odpovídají operacím N = {(i, j)|(i, j) je operace} ∪ {U, V }
dva pomocné uzly U a V reprezentující zdroj a stok
konjunktivní hrany A reprezentují pořadí operací úlohy
(i, j) → (k, j) ∈ A ⇐⇒ operace (i, j) předchází (k, j)
disjunktivní hrany B reprezentují konflikty na strojích
dvě operace (i, j) a (i, l) jsou spojeny dvěma opačně orientovanými
hranami
pomocné hrany P
hrany z U ke všem prvním operacím úlohy
hrany ze všech posledních operací úlohy do V
3,1 2,1 1,1
1,2 3,2
2,3 1,3 3,3
U V
Hana Rudová, FI MU: Plánování job-shopu 26 4. dubna 2023
Výběr hran
Pojmy:
Podmnožina D ⊂ B je nazývána výběr, jestliže obsahuje z každého
páru disjuktivních hran právě jednu
Výběr D je splnitelný, jestliže výsledný orientovaný graf
G(D) = (N, A ∪ D ∪ P) je acyklický
jedná se o graf s pomocnými, konjunktivními hranami
a vybranými disjunktními hranami
Poznámky:
splnitelný výběr určuje posloupnost, ve které jsou operace prováděny
na strojích
vztah splnitelného výběru a (konzistentního) rozvrhu?
každý (konzistentní) rozvrh jednoznačně určuje splnitelný výběr
každý splnitelný výběr jednoznačně určuje (konzistentní) rozvrh
Hana Rudová, FI MU: Plánování job-shopu 27 4. dubna 2023
Příklad: nesplnitelný výběr
3,1 2,1 1,1
1,2 3,2
2,3 1,3 3,3
U V
V grafu existuje v důsledku nevhodného výběru hran cyklus:
(1, 2) → (3, 2)
(3, 2) → (3, 1) → (2, 1) → (1, 1) → (1, 2)
⇒ nelze splnit (k tomuto výběru neexistuje rozvrh)
Hana Rudová, FI MU: Plánování job-shopu 28 4. dubna 2023
Příklad: výběr pro daný rozvrh
Nalezněte (splnitelný) výběr hran pro daný rozvrh:
105 12
M3
M2
M1
0
Konstrukce odpovídajícího výběru:
vybereme (jeden stroj po druhém) disjunktivní hrany,
které odpovídají uspořádání operací na stroji v daném rozvrhu:
3,1 2,1 1,1
1,2 3,2
2,3 1,3 3,3
U V
Hana Rudová, FI MU: Plánování job-shopu 29 4. dubna 2023
Příklad: rozvrh pro daný splnitelný výběr
Jakým způsobem nalézt rozvrh pro daný splnitelný výběr?
3,1 2,1 1,1
1,2 3,2
2,3 1,3 3,3
U V
Tedy: jakým způsobem lze nalézt tento odpovídající rozvrh:
105
M3
M2
M1
0 15 20
Hana Rudová, FI MU: Plánování job-shopu 30 4. dubna 2023
Výpočet rozvrhu pro výběr
Metoda: výpočet nejdelších cest z U do dalších uzlů v G(D)
obdoba dopředného zpracování z metody kritické cesty
pro plánování projektu
Technický popis:
uzly (i, j) mají ohodnocení pij , uzel U má váhu 0
délka cesty i1, i2, . . . , ir je součet ohodnocení uzlů i1, i2, . . . , ir−1
spočítej délku lij nejdelší cesty z U do (i, j) a V
1 lU = 0 a pro každý uzel (i, j) s jediným předchůdcem U: lij = 0
2 vypočítej postupně pro všechny zbývající uzly (i, j) (a pro uzel V):
lij = max
∀(k,l):(k,l)→(i,j)
(lkl + pkl )
tj. projdeme všechny předchůdce (k, l) uzlu (i, j)
délka cesty do (i, j) přes (k, l) je lkl + pkl
zahaj operaci (i, j) v čase lij
délka nejdelší cesty z U do V je rovna makespan
tato cesta je kritická cesta
Hana Rudová, FI MU: Plánování job-shopu 31 4. dubna 2023
Výpočet rozvrhu pro výběr
3,1 2,1 1,1
1,2 3,2
2,3 1,3 3,3
U V
2 4 1
124
33
Výpočet lij :
uzel (3,1) (1,2) (2,3) (2,1) (3,2) (1,1) (1,3) (3,3) V
délka 0 0 0 4 4 6 7 11 12
Hana Rudová, FI MU: Plánování job-shopu 32 4. dubna 2023