Project Management (H 9.8 + H 22 op CD-ROM) CPM (Critical Path Method) Activiteiten met afhankelijkheden en vaste duur zijn gegeven. CPM bepaalt de minimale doorlooptijd van het project. PERT (Program Evaluation and Review Technique) Houdt rekening met onzekerheden in duur. Met PERT kunnen bv. kansen op tijdoverschrijding worden berekend. Beide methoden zijn van eind 1950.
Representatie van een project als netwerk kan als Activity On Arc (AOA) netwerk Een activiteit correspondeert met een tak. Activity On Node (AON) netwerk Een activiteit correspondeert met een knoop.
AON
AOA
Beide netwerken modelleren de afhankelijkheden: B na A, D na B, C na B, E na C en D, F na A, G na C en F, H na E en G. Een projectnetwerk is op beide manieren te representeren. Eventueel zijn dummy takken (gestippeld) nodig om de juiste afhankelijkheden te krijgen.
Voorbeeld: Reliable Construction Co. (8.9)
Bouwproject als AON netwerk
CPM methode
Forward sweep: Bepaal de Earliest Start Times (ES) en Earliest Finish Times (EF) van Start naar Finish Backward sweep: Bepaal Latest Start Times (LS) en Latest Finish Times (LF) van Finish naar Start
Resultaat van het CPM algoritme:
Activiteiten met ES = LS liggen op het kritieke pad. Zo’n pad bepaalt de minimale tijdsduur van een project. Activiteiten op het kritieke pad moeten op een vast tijdstip beginnen en als zo’n activiteit uitloopt, loopt het project uit. Kritieke pad is in dit voorbeeld: ABCEFJLN Alle paden door het project moeten toelaatbaar zijn, dus ook het langste. Een kritiek pad is dus automatisch een langste pad in het netwerk van Start naar Finish. Er kunnen meer kritieke paden zijn.
Crashen van projecten
Alle mogelijke paden door het project
Het verkorten van een taak met kosten
Verkorten van 44 naar 40 weken kan door per week de goedkoopste taak in het kritieke pad te crashen:
Dit levert: Activiteit J en F beide met 2 weken verkorten. Kosten zijn dan $140.000
Als je nóg een week wil verkorten moet je drie kritieke paden verkorten: ABCDGHM, ABCEFJLN en ABCIJLN. Dit kan door één taak te verkorten: B is dan het goedkoopst, kosten $50.000 Als crashen van B en C $100.000 zou kosten, dan kun je B of C verkorten ($100.000), maar beter L en (D of G) ($50.000 + $40.000). Het hoeft dus niet optimaal te zijn om telkens één activiteit te crashen
Project na crashen van 2 weken J en 2 weken F, nu met 3 kritieke paden.
Crashen met lineair programmeren xj is de reductie in tijd van activiteit j. yj is de starttijd van activiteit j. F is de opvolger van E (F na E) De duur van E na reductie met xE is 4 – xE. F komt na E: Maximale crashduur: Project moet binnen 40 weken: Niet-negativiteit:
yF ≥ yE + (4 – xE) xj ≤ xj, max yfinish ≤ 40 xj, yj ≥ 0
Minimaliseer de crashkosten: Min Z = 100xA + 50xB + … + 60xN B
Alle voorwaarden zijn lineair, dus dit is een LP model.
De LP formulering levert als oplossing: xF = xJ = 2, rest = 0,
Z = $140.000
Nadeel van de LP aanpak t.o.v. CPM is dat er één oplossing uit komt en het langste pad niet gevonden kan worden. Een kritiek pad kan worden gevonden m.b.v. het duale probleem. Voorbeeld:
5 activiteiten op de takken met benodigde tijd t12, t13, t23, t24, t34 Tijdstippen waarop je in de knopen bent: x1, x2, x3, x4 Min z.d.d.
en
x4 – x 1 x2 – x1 ≥ t12 x3 – x2 ≥ t23 x3 – x1 ≥ t13 x4 – x2 ≥ t24 x4 – x3 ≥ t34 xj ≥ 0
-1 0 -1 0 0
1 -1 0 -1 0
0 1 1 0 -1
0 0 0 1 1
Duale probleem (schaduwprijzen x12, x23, x13, x24, x34): Max z.d.d.
en
t12x12 + t23x23 + t13x13 + t24x24 + t34x34 – x12 – x13 ≤ –1 -1 0 -1 1 -1 0 x12 – x23 – x34 ≤ 0 x23 + x13 – x34 ≤ 0 0 1 1 0 0 0 x24 + x34 ≤ 1 xij ≥ 0
0 -1 0 1
0 0 -1 1
Tel alle ongelijkheden op: 0 ≤ 0. Dit betekent dat alle ongelijkheden gelijkheden moeten zijn:
Max z.d.d.
en
t12x12 + t23x23 + t13x13 + t24x24 + t34x34 – x12 – x13 = –1 x12 – x23 – x34 = 0 x23 + x13 – x34 = 0 x23 +x13 – x34 = 0 x24 + x34 = 1 xij ≥ 0
Dit is een netwerkstromingsprobleem in het bovenstaande netwerk, waarbij xij over tak i→j stroomt, 1 eenheid in knoop 1 in gaat en bij knoop 4 eruit komt. Vanwege de geheeltalligheidseigenschap (coëfficiëntmatrix is unimodulair) is er een binaire optimale oplossing, dat is een pad van 1 naar 4. Gemaximaliseerd wordt de totale tijdsduur langs dit pad. De optimale oplossing is dus een langste pad. De schaduwprijzen xij geven aan of tak i→j in dit langste pad zit (1) of niet (0). Je vindt zo één mogelijk kritiek pad. Voordeel van de LP aanpak is dat het altijd werkt en je niet hoeft na te denken over hoe je moet crashen, en dat je niet telkens alle langste paden hoeft te bepalen.
CPM Methode met Excel Solver
PERT Tijdsduren worden geschat met drie parameters: o = optimistische (minimale) schatting voor tijdsduur m = meest waarschijnlijke tijdsduur p = pessimistische schatting Er wordt uitgegaan van een Betaverdeling:
Verwachtingswaarde:
μ=
o + 4m + p 6
⎛ p−o⎞ σ =⎜ ⎟ 6 ⎝ ⎠
2
2
Variantie:
De verwachte tijdsduur is een gewogen gemiddelde van m, o en p, waarin de meest waarschijnlijke waarde m (top van de verdeling) het zwaarst telt.
Met de meest pessimistische schatting duurt het project 69 weken, i.p.v. 44.
Aangenomen dat de activiteiten op het kritieke pad onafhankelijk zijn kun je de variantie van de doorlooptijd berekenen als som van de varianties van de onderdelen. Met de aanname dat de projectduur normaal verdeeld is (wet van de “grote” aantallen) kun je de kans schatten dat het project binnen de deadline van 47 weken blijft:
De afwijking is 1 standaarddeviatie. De kans om hoogstens één standaarddeviatie boven het gemiddelde te zitten is: P(T ≤ d) = P(standaard normaal ≤ μ + 1⋅σ) = = 1 – P(standaard normaal > μ + 1⋅σ) = = 1 – 0,1587 = 0,8413
Bandbreedte in de kosten tijdens het doorlopen van het project als gevolg van taken die kunnen schuiven
