Plánování projektu
28. března 2023
1 Úvod
2 Reprezentace projektu
3 Neomezené zdroje
4 Variabilní doba trvání
5 Přidání pracovní síly
Problémy plánování projektu
Zprostředkování, instalace a testování
rozsáhlého počítačového systému
projekt zahrnuje
evaluace a výběr hardware, vývoj software, nábor a školení lidí,
testování a ladění systému, . . .
precedenční vztahy
některé úlohy mohou být prováděny paralelně
úloha musí být realizována až po dokončení jiných úloh
cíl: minimalizovat čas na realizaci celého projektu
Příklady dalších problémů
stavba nemovitostí, konstrukce center elektráren, vojenský průmysl
Hana Rudová, FI MU: Plánování projektu 2 28. března 2023
Plánování projektu
Základní problém plánování projektu
precedenční podmínky
paralelní stroj s neomezeným počtem strojů
minimalizace maximálního času konce úloh (makespan)
relativně jednoduché na řešení
21 4 6
3 5 7
Rozšíření
variabilní doba trvání (spojena s cenou provádění)
optimalizace: kompromis mezi cenou na ukončení projektu a cenou za
zkrácení délky úloh
pracovní síla (skupiny operátorů s odlišnou specializací)
při sdílení omezeného množství operátorů nutno uvažovat disjunktivní
hrany
⇒ komplexní problém, jehož řešení je velmi obtížné
Hana Rudová, FI MU: Plánování projektu 3 28. března 2023
Reprezentace projektu: úloha jako uzel
Reprezentace: úloha jako uzel
hrany reprezentují precedenční podmínky
síť neobsahuje žádné orientované cykly
Úloha Doba Předchůdci
trvání
1 2 –
2 3 1
3 1 1
4 4 2
5 2 3
6 1 4,5
7 3 4,5
21 4 6
3 5 7
Hana Rudová, FI MU: Plánování projektu 4 28. března 2023
Výhodnější reprezentace
Běžně používana reprezentace úloha jako hrana
Výhodnější ale úloha jako uzel
nejsou nutné redundantní hrany (pomocné úlohy) pro korektní
vyjádření precedencí
úloha jako uzel lze převést na úloha jako obdelník
horizontální strany obdelníku použity jako časové osy odpovídající době
provádění úlohy
uloha j
uloha k
Hana Rudová, FI MU: Plánování projektu 5 28. března 2023
Popis problému
Popis problému
m paralelně zapojených strojů
n úloh s precedenčními omezeními
doba provádění pj
objektivní funkce: minimalizace maximálního času konce úloh
(makespan)
P∞|prec|Cmax (a m ≥ n) polynomiální složitost, metoda kritické cesty
Pm|prec|Cmax 2 ≤ m < n NP úplný problém
Značení
Sj nejdřívější startovní čas úlohy j
Cj = Sj + pj nejdřívější koncový úlohy j
Sj nejpozdější startovní čas úlohy j
Cj nejpozdější koncový čas úlohy j
Precj (přímí) předchůdci úlohy j
∀k ∈ Precj všechny úlohy k, které předcházejí úlohu j
∀j : k ∈ Precj všechny úlohy j, které následují úlohu k
Hana Rudová, FI MU: Plánování projektu 6 28. března 2023
Metoda kritické cesty
Popis algoritmu pro nalezení kritické cesty
dopředná procedura
start v čase 0
výpočet nejdřívějšího startovního času každé úlohy
čas dokončení poslední úlohy je makespan
zpětná procedura
start v čase rovném makespan
výpočet nejpozdějšího startovního času, aby byl realizován tento
makespan
Úloha s rezervou (slack job)
její startovní čas může být odložen aniž je navýšen makespan
úloha, jejichž nejdřívější startovní čas je menší než nejpozdější startovní čas
Kritická úloha
úloha, která nesmí být odložena
úlohy, jejichž nejdřívější startovní čas je roven nejpozdějšímu startovnímu čas
Kritická cesta
řetěz úloh začínající v čase 0 a končící v čase Cmax
v grafu může existovat více kritických cest
kritické cesty se mohou částečně překrývat
graf kritických cest GCP : podgraf daný množinou kritických úloh a kritických cest
Hana Rudová, FI MU: Plánování projektu 7 28. března 2023
Kritická cesta: zadání příkladu
j 1 2 3 4 5 6 7 8 9 10 11 12 13 14
pj 5 6 9 12 7 12 10 6 10 9 7 8 7 5
2 7
10
12 14
4
1
3
6 9
5 8
1311
Hana Rudová, FI MU: Plánování projektu 8 28. března 2023
Příklad: dopředná procedura
2 7
10
14
4
1
3
6 9
5 8
1311
12
j
legenda
j j jS’ + p = C’
0+5=5
5+6=11
5+9=14
11+12=23
14+12=26
14+7=21
26+6=32
23+10=33
26+10=36
36+7=43
33+9=42
43+8=51
43+7=50
51+5=56
j 1 2 3 4 5 6 7 8 9 10 11 12 13 14
pj 5 6 9 12 7 12 10 6 10 9 7 8 7 5
Hana Rudová, FI MU: Plánování projektu 9 28. března 2023
Příklad: zpětná procedura
2 7
10
14
4
1
3
6
5 8
1311
12
9
legenda
j j j
j
C’’ − p = S’’
56−5=5151−8=43
51−7=44
43−9=34
43−7=36
34−10=24
36−6=30
36−10=26
24−12=12
26−7=19
26−12=14
14−9=5
12−6=6
5−5=0
j 1 2 3 4 5 6 7 8 9 10 11 12 13 14
pj 5 6 9 12 7 12 10 6 10 9 7 8 7 5
Hana Rudová, FI MU: Plánování projektu 10 28. března 2023
Kritická cesta
2 7
10
12 14
4
1
3
6 9
5 8
1311
maxC = 56
Hana Rudová, FI MU: Plánování projektu 11 28. března 2023
Algoritmus pro nalezení kritické cesty
1 Dopředná procedura
1 t = 0
2 pro všechny úlohy j bez předchůdce: Sj = 0, Cj = pj
3 vypočítej postupně pro všechny zbývající úlohy j:
k1
jk2
k3
Sj = max
∀k∈Precj
Ck , Cj = Sj + pj
4 optimální makespan je Cmax = max(C1, . . . , Cn)
2 Zpětná procedura
t = Cmax
pro všechny úlohy j bez následníka: Cj = Cmax , Sj = Cmax − pj
vypočítej postupně pro všechny zbývající úlohy j:
k3
j
k1
k2 Cj = min
∀k:j∈Preck
Sk , Sj = Cj − pj
ověř, že 0 = min(S1 , . . . , Sn )
Hana Rudová, FI MU: Plánování projektu 12 28. března 2023
Kompromis mezi časem a cenou
Lze uvažovat variabilní dobu trvání úloh
za předpokladu vyšší ceny lze zkrátit dobu provádění
Lineární cena
Doba trvání pmin
j ≤ pj ≤ pmax
j
Marginální cena: cena za zkrácení doby trvání úlohy o 1 časovou
jednotku
cj =
ca
j − cb
j
pmax
j − pmin
j
cj
a
cj
b
pj
min pj
max
doba provádění
prostředky (peníze)
př. pmin
j = 10, pmax
j = 15, cb
j = 10, ca
j = 20, cj = 2
⇒ cena provádění úlohy j po dobu pj : cb
j + cj (pmax
j − pj )
Hana Rudová, FI MU: Plánování projektu 13 28. března 2023
Cena za provádění projektu
Fixní režijní náklady c0 celkem: Cmaxc0
na časovou jednotku doby provádění projektu
Cena F(pj ) za provádění projektu
při době provádění úloh pj
určena jako součet
ceny za provádění všech úloh
fixních režijních nákladů
F(pj ) = Cmaxc0 +
j
cb
j + cj (pmax
j − pj )
Cíl: ∀j nalézt pj a Sj tak, aby byla F(pj ) minimální
cj
a
cj
b
pj
min pj
max
doba provádění
prostředky (peníze)
Hana Rudová, FI MU: Plánování projektu 14 28. března 2023
Variabilní doba trvání: metody řešení
Objektivní funkce: minimální cena projektu
Kompromisní heuristika mezi časem a cenou
dobrá kvalita rozvrhu
použitené i pro nelineární cenu
Formulace lineárního programování
optimální rozvrh
nelineární verze obtížně řešitelné
Hana Rudová, FI MU: Plánování projektu 15 28. března 2023
Opakování: Řez, minimální řez
Orientovaný graf G = (V , E)
Počáteční uzel: zdroj s ∈ V
Koncový uzel: stok t ∈ V
Řez: ... také mluvíme o vrcholovém řezu
množina uzlů V , jejíž smazáním z grafu se rozpojí zdroj a stok
E množina hran incidentních s V
tj. v G’=(V-V’,E-E’) neexistuje orientovaná cesta z s to t
Minimální řez: řez U takový, že neexistuje řez W ⊂ U
tj. vrácení libovolného uzlu z U do grafu znovu spojí zdroj a stok
řez
zdroj stok
minimální řez
Hana Rudová, FI MU: Plánování projektu 16 28. března 2023
Řez, minimální řez II.
Uvažujme orientovaný graf G0 = (V0, E0)
Do grafu přidáme zdroj:
nový vrchol s a
hrany S vedoucí z s do všech vrcholů G0 bez předchůdců
Do grafu přidáme stok:
nový vrchol t a
hrany T vedoucí ze všech vrcholů G0 bez následníků do t
Nový graf G = (V , E): V = V0 ∪ {s, t}, E = E0 ∪ S ∪ T
Budeme hledat řezy a minimální řezy z s do t v G
řez
zdroj stok
minimální řez
př. graf má 4 minimální řezy
Hana Rudová, FI MU: Plánování projektu 17 28. března 2023
Kompromisní heuristika: příklad
j 1 2 3 4 5 6 7 8 9 10 11 12 13 14
pmax
j 5 6 9 12 7 12 10 6 10 9 7 8 7 5
pmin
j 3 5 7 9 5 9 8 3 7 5 4 5 5 2
cb
j 20 25 20 15 30 40 35 25 30 20 25 35 20 10
cj 7 2 4 3 4 3 4 4 4 5 2 2 4 8
fixní režijní náklady na časovou jednotku c0=6
Hana Rudová, FI MU: Plánování projektu 18 28. března 2023
Příklad (pokračování): maximální doba provádění
2 7
10
12 14
4
1
3
6 9
5 8
1311
maxC = 56
Hana Rudová, FI MU: Plánování projektu 19 28. března 2023
Kompromisní heuristika: příklad
c0=6
j 1 2 3 4 5 6 7 8 9 10 11 12 13 14
pmax
j 5 6 9 12 7 12 10 6 10 9 7 8 7 5
pmin
j 3 5 7 9 5 9 8 3 7 5 4 5 5 2
cb
j 20 25 20 15 30 40 35 25 30 20 25 35 20 10
cj 7 2 4 3 4 3 4 4 4 5 2 2 4 8
Náklady na provedení projektu při maximální době trvání úloh
F(pmax
j ) = Cmaxc0 + j cb
j + cj (pmax
j − pmax
j ) =
= Cmaxc0 + j cb
j =
= 56 × 6 + 20 + 25 + 20 + 15 + 30 + 40 + 35 + 25+
+30 + 20 + 25 + 35 + 20 + 10 =
= 336 + 350 = 686
Hana Rudová, FI MU: Plánování projektu 20 28. března 2023
Podgraf s kritickou cestou (GCP)
Kandidáti na redukci: uzel 11 a uzel 12, vybereme uzel 12
12 141
3
6 9
11
c = 36 c = 49
c = 212 c = 814c = 71
c = 43
Rezy: {1},{3},{6},{9}
{11},{12},{14}
c = 211
minimální řez
s nejnižší cenou
³
ulohy 12 z 8 na 7
redukce doby provádení
Fixní režijní náklady se redukují z 56 × 6 na 55 × 6 = 330
Cena za provádění úloh naroste o c12 = 2, tj. 350 + 2 = 352
Celková cena klesla z 686 na 330 + 352 = 682
Hana Rudová, FI MU: Plánování projektu 21 28. března 2023
Podgraf s kritickou cestou (GCP)
12 141
3
6 9
1311
c = 36 c = 49
c = 413
c = 212 c = 814c = 71
c = 211c = 43
Rezy: {1},{3},{6},{9}
{11},{12,13},{14}
minimální řez
s nejnižší cenou
¬
5
9 12 10
7 7
77 na 6
redukce doby trvání ulohy 11 ze 7 na 6
Fixní režijní náklady se redukují z 55 × 6 na 54 × 6 = 324
Cena za provádění úloh naroste o c11 = 2, tj. 352 + 2 = 354
Celková cena klesla z 682 na 324 + 354 = 678
Hana Rudová, FI MU: Plánování projektu 22 28. března 2023
Podgraf s kritickou cestou (GCP)
12 141
3
6 9
1311
C = 36 C = 49
C = 413
C = 212 C = 814
C = 211C = 43
2 7
10
12 141
3
6 9
1311
C = 71
C = 22 C = 47C = 34
C = 510
4
5−2
10−7
5−3
6−5
12−9 10−8
9−5
7−5
12−9
9−7
8−5
další redukce: pro uzel 2 na 5 a pro uzel 11 na 5, ...
7−4
Fixní režijní náklady se redukují z 54 × 6 na 53 × 6 = 318
Cena za provádění úloh naroste o c2 + c11 = 2 + 2, tj. 354 + 4 = 358
Celková cena klesla z 678 na 318 + 358 = 676
Hana Rudová, FI MU: Plánování projektu 23 28. března 2023
Algoritmus kompromisní heuristiky
1 Nastav doby provádění na jejich maximum: pj = pmax
j
Urči všechny kritické cesty s těmito dobami provádění
Zkonstruuj graf GCP kritických cest
2 Urči všechny minimální řezy v GCP
pozn. pokud zkrátíme dobu provádění všech úloh v minimálním řezu,
podaří se nám i zkrátit dobu provádění projektu!
Najdi řezy, jejichž doba provádění je větší než jejich minimum:
pj > pmin
j ∀j ∈ GCP
Pokud takový řez neexistuje STOP, jinak běž na krok 3
3 Pro každý minimální řez: spočítej cenu redukující všechny doby
provádění o 1 časovou jednotku
Vyber minimální řez s nejnižší cenou
pozn. abychom za snížení zaplatili co nejnižší cenu
Jestliže je cena řezu menší než fixní režijní náklady c0 za časovou
jednotku běž na krok 4, jinak STOP
4 Redukuj všechny doby provádění v minimálním řezu o 1 časovou
jednotku
Urči novou množinu kritických cest
Reviduj graf GCP a běž na krok 2
Hana Rudová, FI MU: Plánování projektu 24 28. března 2023
Lineární program
Heuristika negarantuje nalezení optima
Celková cena je lineární
c0Cmax +
n
j=1
cb
j + cj (pmax
j − pj )
všimněte si: stejná účelová funkce jako cena za provádění projektu
Lineární program: cb
j a cj pmax
j
minimalizace: c0Cmax −
n
j=1
cj pj se nemění
za předpokladu:
xk − pj − xj ≥ 0 ∀j ∈ Preck
pj ≤ pmax
j ∀j
pj ≥ pmin
j ∀j
xj ≥ 0 ∀j
Cmax − xj − pj ≥ 0 ∀j
kde xj je nejdřívější možný startovní čas úlohy j
Hana Rudová, FI MU: Plánování projektu 25 28. března 2023
Přidání pracovní síly
Pracovní síla = operátor = zdroj
Problém popsán v literatuře jako
problém plánování projektu s omezenými zdroji
resource-constrained project scheduling problem (RCPSP)
n úloh
N zdrojů
Ri kapacita zdroje i
pj doba provádění úlohy j
Rij požadavek úlohy j na zdroj i
Precj (přímí) předchůdci úlohy j
Hana Rudová, FI MU: Plánování projektu 26 28. března 2023
Formulace celočíselného programování
Pomocná úloha n + 1 jako stok, pn+1 = 0
xjt = 1 úloha j je dokončena v čase t
xjt = 0 jinak
Kapacita zdroje i, který potřebuje úloha j
v intervalu [t − 1, t]: Rij
t+pj −1
u=t
xju tt−1
pjj
t+pj −1
u=t
xju . . . počítá, zda úloha j běží v čase [t − 1, t]
př. úloha s Sj = 2, pj = 2 a t = 2, 3, 4, 5 (xj4 = 1, pro t = 3, 4 úloha započítána)
H jako horní hranice makespan: H =
n
j=1
pj
Koncový čas úlohy j: Cj =
H
t=1
t xjt
Makespan: Cmax =
H
t=1
t xn+1,t koncový čas stoku
Hana Rudová, FI MU: Plánování projektu 27 28. března 2023
Celočíselný program
Minimalizace
H
t=1
t xn+1,t minimalizace makespan
za předpokladu
jestliže j je předchůdce k, pak Cj ≤ Sk , tj. Cj ≤ Ck − pk , tj. Cj + pk − Ck ≤ 0
H
t=1
t xjt + pk −
H
t=1
t xkt ≤ 0 ∀j ∈ Preck
pro každý čas t: požadavek na zdroj i nepřeroste kapacitu i
n
j=1

Rij
t+pj −1
u=t
xju

 ≤ Ri ∀i ∀t
každá úloha j skončí právě jednou
H
t=1
xjt = 1 ∀j
Hana Rudová, FI MU: Plánování projektu 28 28. března 2023
Diskuse
Řešení celočíselného programu obtížné
Při velkém počtu úloh a dlouhém časovém horizontu
použití heuristik
Lze použít programování s omezujícími podmínkami
kumulativní zdroje
precedenční podmínky
Probírané speciální případy problému
job shop + makespan
timetabling
Hana Rudová, FI MU: Plánování projektu 29 28. března 2023
Plánování projektu: shrnutí
Základní problém s neomezenými zdroji
metoda kritické cesty
Neomezené zdroje + variabilní doba trvání (lineární)
kompromisní heuristika mezi časem a cenou
lineární programování
Problém plánování projektu s omezenými zdroji
celočíselné programování
heuristiky
programování s omezujícími podmínkami
Hana Rudová, FI MU: Plánování projektu 30 28. března 2023