Netwerkdiagram voor een project. AON: Activities On Nodes - activiteiten op knooppunten Opmerking vooraf. Een netwerk is een structuur die is opgebouwd met pijlen en knooppunten. Bij het opstellen van een netwerk voor je project kun je op twee verschillende manieren te werk gaan. Bij de ene manier geef je activiteiten weer door pijlen, bij de andere manier geef je activiteiten weer door knooppunten. In de praktijk verschilt het gebruik niet zoveel, maar omdat de opzet natuurlijk wel verschilt, behandel ik beide in een afzonderlijke notitie. Deze notitie gaat over de manier waarbij de activiteiten door knooppunten worden weergegeven. In een netwerkdiagram laat je de afhankelijkheden zien tussen de verschillende activiteiten in een project. Het samenstellen is niet erg moeilijk, maar je hebt er een paar handigheidjes bij nodig. Daarover gaat deze notitie. Je leert hoe je: • een netwerkdiagram opstelt; • het kritieke pad bepaalt; • per activiteit de speling bepaalt. Een netwerkdiagram bestaat uit pijlen en knooppunten. De knooppunten stellen activiteiten voor, de pijlen geven aan welke afhankelijkheden er tussen de activiteiten zijn. Vaste knooppunten in een netwerkdiagram zijn Start (voor het begin) en Finish (voor het eind). Ik zal activiteiten aanduiden met de letters A, B, C, ... en het knooppunt krijgt de letter van de activiteit die het voorstelt. Er zijn bij een netwerk twee belangrijke begrippen: voorganger en opvolger. Als A een voorganger van B is, dan moet A afgerond zijn voordat je aan B kunt beginnen. B is dan de opvolger van A. Een voorganger heet ook wel directe voorganger of verplichte voorganger. Je hebt bepaald welke activiteiten moeten worden uitgevoerd in je project en hoeveel tijd ze vergen. Maak daar een tabel van en zet ze daarin in volgorde. “In volgorde” betekent hier dat je een activiteit die voorgangers heeft, in de tabel onder zijn voorgangers zet. Je ziet een voorbeeld in tabel 1. Activiteit
Voorganger
Tijdsduur (dagen)
A
-
6
B
-
12
C
A
5
D
A
4
E
B en C
8
F
D
8
H
E
9 1
Tabel 1 een eenvoudige activiteitentabel
Afhankelijkheden in kaart brengen. We gaan een netwerk tekenen met pijlen en knooppunten. Je geeft een activiteit weer met een rechthoek. In die rechthoek vermeld je enkele kenmerken omtrent die activiteit. Om te beginnen de naam en de tijdsduur, later voegen we daar andere kenmerken aan toe. Wanneer je een netwerkdiagram op deze manier opbouwt, zeggen we dat de activiteiten staan op de knooppunten. Dat kan ook anders, zie daarvoor de notie over netwerken met activiteiten op de pijlen. De pijlen die de knooppunten verbinden dienen om afhankelijkheden aan te geven tussen voorgangers en opvolgers. Bijzondere knooppunten zijn Start aan het begin en Finish aan het eind van het project. Strikt genomen zijn dat geen activiteiten, maar volledigheidshalve nemen we ze toch maar op. Een knooppunt geef je weer door een rechthoek die is verdeeld in compartimenten. Ieder compartiment bevat een kenmerk. Voorlopig beperken we ons tot de naam (“naam”in figuur 1) en de tijdsduur (“tijd” in figuur 1) van de activiteit die we er mee weergeven.. Zie figuur 1.
Figure 1 Begin met het knooppunt Start te tekenen. Kijk daarna in de tabel welke activiteiten geen voorganger hebben. In tabel 1 zijn dat A en B. Activiteiten zonder voorganger hebben alleen Start als voorganger. Je zet A en B rechts van Start en verbindt Start met A respectievelijk B. Zie figuur 2.
Figure 2 Bij iedere activiteit zie je de naam en de tijdsduur. De pijlen geven aan dat je A en B kunt beginnen bij de start van het project. TIP: laat de tijd in je netwerk zoveel mogelijk van links naar rechts lopen. Zoek daarna de opvolgers van de activiteiten die in Start beginnen. Daarbij zijn er verschillende
2
mogelijkheden. Voor ieder van die mogelijkheden is er een handige manier om ze in het diagram op te nemen. Ik zal de belangrijkste behandelen, ander mogelijkheden kun je dan zelf afleiden. De gemakkelijkste afhankelijkheid is het geval dat een activiteit precies één voorganger heeft. Begin altijd met zoveel mogelijk deze solo-voorgangers te verwerken. Voorbeeld uit tabel 1: activiteit C met voorganger A. Ook activiteit D heeft één voorganger (dat is A) evenals de activiteiten F (met voorganger D) en H (met voorganger E). Begin met een knooppunt te tekenen voor C. Dat knooppunt verbind je met knooppunt A om aan te geven dat C pas kan worden gedaan als A is afgerond. Teken een daarna een knooppunt voor D en verbindt die ook door middel van een pijl met A.. Voor H kun je wel tekenen, maar omdat je E nog niet hebt getekend, kun je die nog niet verbinden. Dan is het handiger een activiteit nog niet te tekenen. Maar als je D hebt getekend, heeft het zin F te tekenen en een pijl van D naar F te trekken. Met F heb je iets bijzonders te pakken. In de tabel kun je zien dat F geen opvolgers heeft. Dat betekent dat F eindigt in knooppunt Finish. Dus kun je nu ook een pijl van F naar Finish trekken. Zie figuur 3.
Figure 3
Een tweede vorm van afhankelijkheid is dat een activiteit twee of meer voorgangers heeft. Dat kun je gemakkelijk weergeven door op de goede manier pijlen te trekken. Een voorbeeld is E met voorgangers B en C. Je tekent het knooppunt E en verbindt B en C met E door middel van twee pijlen. Tenslotte teken je H en verbindt die met E als voorganger en met Finish. Zie figuur 4. Zorg ervoor dat pijlen in een diagram elkaar zo min mogelijk snijden.
Figure 4
3
Het verbinden van activiteiten gaat dus heel simpel. Een stuk simpeler dan wanneer je de activiteiten op de pijlen zet.
De tijd inbrengen. Tot nu toe hebben we alleen maar gekeken naar afhankelijkheden. Nu gaan we de tijd in het schema brengen. Daarvoor gebruik je de verschillende compartimenten in een knooppunt. Zie figuur 5.
Figure 5 Naast Naam en Tijd bevat een knooppunt nog de volgende kenmerken van een activiteit. Het zijn: • Vroegst Mogelijke Start (VS), het tijdstip waarop op zijn vroegst met de activiteit kan worden begonnen; • Vroegst Mogelijke Einde (VE), het tijdstip waarop de activiteit op zijn vroegst kan worden afgerond; • Laatst Mogelijke Start (LS), het uiterste tijdstip waarop de activiteit moet zijn begonnen; • Laatst Mogelijke Einde (LE), het laatst mogelijk tijdstip waarop de activiteit moet zijn afgerond; • Speling (SP), de ruimte die er is tussen vroegst mogelijke start en laatst mogelijke start. De termen Vroegst Mogelijke Start, Laatst Mogelijke Start et cetera zijn nogal omslachtig. Vandaar dat ik liever Vroegste Start, Laatste Start enzovoorts gebruik. Dat is wat versluierend taalgebruik, want een activiteit hoeft natuurlijk niet te starten op het Vroegst Mogelijke tijdstip. Een voorbeeld. Stel je hebt vier activiteiten, A, B, C en D. Activiteit A is voorganger van B en C, B en C zijn voorganger van D. A duurt 5 dagen, B duurt 8 dagen, C duurt 16 dagen en D duurt 3 dagen. A heeft geen voorgangers en begint dus in Start. A is voorganger van B en C en dus beginnen B en C waar A eindigt. B en C hebben D als opvolger. D heeft geen opvolger en eindigt dus in Finish. Het netwerk wordt dan zoals in figuur 6. In de knooppunten zie je de naam en de tijdsduur (midden boven). Trek je nog even niets aan van de andere getallen.
Figure 6 4
Nadat de knooppunten op basis van hun onderlinge afhankelijkheid in het diagram zijn gezet, beginnen we met het bepalen van het Vroegst Mogelijke Start (VS) van iedere activiteit. Daartoe begin je in start en werkt van links naar rechts langs de pijlen. Alle activiteiten die direct zijn verbonden met Start krijgen als VS dag 1. Dat getal zet je linksboven in het knooppunt. Daarna bereken je het Vroegst Mogelijke Einde (VE). Daarvoor geldt de formule VE = VS + tijdsduur -1. De waarde voor VE zet je rechtsboven in het knooppunt. Activiteit A komt direct na Start. De vroegste start is dus dag 1 en het vroegste einde is dag 5. Dat betekent dat je mijlpaal 2 op zijn vroegst kunt afronden op dag 5. Nadat je alle knooppunten die met Start zijn verbonden, hebt afgewerkt, neem je de andere activiteiten. In dit geval zijn dat activiteiten B, C en D. Met D kun je nog even niets, want je moet eerst de waarden bij B en C berekenen. Activiteit B kan beginnen als activiteit A is afgerond. Dus de vroegste start VS van B is op dag 6. B vergt 8 dagen, dus het vroegste einde VE is op dag 13. Net bereken je dat voor activiteit C geldt VS = 6 en VE = 21. Bij activiteit D ligt het complexer. D hangt af van B èn van C. Wat activiteit B betreft, die is op zijn vroegst afgerond op dag 13. Dus lijkt het alsof je D kunt beginnen op dag 14. Maar dat is niet zo, want dan is C nog niet afgerond. Dus D kun je niet eerder beginnen dan op dag 22, want C is op zijn vroegst pas afgerond op dag 21. De tijdsduur van D is 3 dagen, dus VE = 23. Samengevat: De activiteiten die alleen afhangen van Start beginnen op zijn vroegst op dag 1, de andere activiteiten beginnen als alle voorgangers zijn afgerond. Formeel bepaal je de VS als volgt. Kies een activiteit. Bepaal voor alle activiteiten die er direct aan voorafgaan het tijdstip waarop ze op zijn vroegst klaar kunnen zijn. Kies uit de berekende tijdstippen het laatste tijdstip. Dat bepaalt de VS van de activiteit. De VE van het knooppunt bereken je met VE = VS + tijdsduur -1. Als je bij alle knooppunten de VS en VE hebt ingevuld, is het tijd voor de Laatst Mogelijke Start (LS) en het Laatst Mogelijke Einde (LE). Met het Laatst Mogelijke Einde LE geven we het uiterste tijdstip aan waarop een activiteit moet zijn afgerond om je project nog op tijd af te kunnen krijgen. Voor het berekenen van LE rekenen we vanaf Finish terug naar Start. Neem als voorbeeld weer de activiteiten A, B, C en D uit figuur 6. De laatste activiteit is D en die eindigt op dag 19. Dus de Finish van je project is op dag 19. Om die dag te halen moet activiteit D tenminste eindigen op dag 19 (Sorry, dit is wat triviaal, maar dan is het principe tenminste duidelijk). Dat is het Laatst Mogelijke Einde LE van D. Omdat D drie dagen tijd vergt, moet je D dus uiterlijk op dag 16 beginnen. Dat is dus de Laatst Mogelijke Start LS van D. De twee waarden vul je in het knooppunt in: de LE rechtsonder, de LS linksonder. Nu kun je ook de speling invullen. De speling is het verschil tussen de VS en de LS van een activiteit. Voor activiteit D is de speling nul, want VS = LS. Voor alle activiteiten die zijn verbonden met Finish geldt dat de LE gelijk is aan de einddatum van je project. Als je die activiteiten hebt afgewerkt, ga je verder met de andere activiteiten. Daarbij moet je terug rekenen van Finish naar Start in je schema. De activiteiten B en C sluiten aan op D. Activiteit D moet op zijn laatst beginnen op dag 22, dus B moet op zijn laatst klaar zijn op dag 21. Dus bij B geldt LE = 21. Omdat B 8 dagen vergt, moet je dus uiterlijk op dag 14 beginnen. Bij B geldt dus LS = 14. De speling bij B is dan 8 dagen, dat is het verschil tussen VS en LS. Op dezelfde manier bereken je bij C een LE van 21 en een LS van 6. Bij C geeft dat een
5
speling nul. Als je de waarden bij B en C hebt berekend, kun je tenslotte de waarden bij A berekenen. Maar pas op, voor het bepalen van de LE van A moet je kijken naar B èn C. Afgaande op B kun je concluderen dat de LE van A 13 is. Maar dat is niet zo, want als je A pas op dag 13 afrond, kom je bij C tijd tekort. Daarom krijgt de LS van A de waarde 5. Dan kun je op dag 6 beginnen aan C, dat is precies de LS van C. Omdat bij A geldt VS = LS = 1 heb je bij A een speling van nul. Formeel bepaal je de LS en de LE als volgt. Kies een activiteit. Bepaal voor alle activiteiten die er direct op volgen het tijdstip waarop ze op zijn laatst moeten beginnen (de LS dus). Kies uit de berekende tijdstippen het vroegste tijdstip. Dat bepaalt de LE van de activiteit. De LS bereken je dan met LS = LE - tijdsduur +1. De speling is dan het verschil tussen VS en LS. Nu heb je alle waarden bepaald die je nodig hebt om het hele netwerkdiagram te tekenen en in te vullen zoals in figuur 6 is gebeurd. Een opmerking nog over het bepalen van VS, VE, LS en LE. Een activiteit kan niet eerder starten dan dat de voorgaande activiteiten zijn afgerond. Dus de Vroegste Start (VS) sluit aan op de laatste VE van de voorafgaande activiteiten. Voor dat aansluiten kun je twee manieren volgen. Je kunt zeggen dat de VS van een activiteit gelijk is aan de VE van de voorafgaande activiteit. Dan is de VS van activiteit A in figuur 6 dus 0. Maar je kunt ook zeggen dat als een activiteit op een bepaalde dag wordt afgerond, de opvolger pas de volgende dag kan beginnen. Voor beide manieren valt iets te zeggen, ik heb hier de tweede manier gevolgd. Activiteit A heeft dan zijn vroegste start op dag 1. Het vroegste eind bereken je met de formule VE = VS + tijdsduur - 1. Als een activiteit a dagen vereist, en je begint op dag n, dan ben je op zijn vroegst klaar op tijdstip n + a - 1. Als je de VS van een activiteit gelijk stelt aan de VE van de voorgaande activiteit, dan wordt de formule VE = VS + tijdsduur. Bijvoorbeeld krijgt Activiteit A dan VS = 0. De VE bij A blijft 6. Het Laatste Einde (LE) van een activiteit hangt af van de Laatst Mogelijke Start (LS) van de opvolgende activiteit. Een activiteit moet uiterlijk klaar zijn voorafgaand aan de LS de opvolger. Neem als voorbeeld activiteit C in figuur 6. C heeft als opvolger D. D heeft LS = 22. Dat betekent dat activiteit D uiterlijk klaar moet zijn op dag 21, anders kun je niet beginnen aan D op dag 22. Voor activiteit D geldt dus LE = 21. Als je dat weet, dan kun je de LS van D bepalen met de formule LS = LE - tijdsduur - 1. Die formule ligt voor de hand: als D klaar moet zijn op dag 21 en D vergt 16 dagen, dan moet je uiterlijk beginnen op dag 6. Ook hier geldt weer dat als je de andere manier gebruikt, de formule wordt: LS = LE - tijdsduur. Dan zou je dus als Laatste Start voor D dag 5 krijgen.
Het Kritieke Pad. Voor elke activiteit weet je nu op welk tijdstip je die op zijn vroegst kunt afronden (dat is de VE) en wanneer die uiterlijk moet zijn afgerond (dat is de LE). Het verschil tussen LE en VE (of tussen LS en VS) is de speling die je bij die activiteit hebt. In een ingevuld netwerkdiagram kun
6
je daarmee heel gemakkelijk het kritieke pad herkennen. Op het kritieke pad heb je geen speling. In een knooppunt zonder speling zijn VE en LE gelijk aan elkaar. Daarom wordt het kritieke pad gevormd door de lijn die alle activiteiten verbindt waar VE en LE aan elkaar gelijk zijn en waar dus de speling nul is. In figuur 6 is bij de activiteiten A, C en D de speling gelijk aan nul. Dat is dus het kritieke pad. Als een of meer van die activiteiten uitloopt, duurt je project langer. Bij activiteit B heb je wel speling, als B langer duurt dan gepland hoeft dat nog geen verlenging van je project te betekenen. De knooppunten Start en Finish behoren altijd tot het kritieke pad. Houd er rekening mee dat een project meer dan één kritiek pad kan hebben.
7
Als voorbeeld om uit te werken nemen we de activiteiten uit tabel 2. Activiteit
Voorganger
Tijdsduur(dagen)
A
-
6
B
-
12
C
A
5
D
A
4
E
B en C
8
F
C
8
G
F
7
H
E en F
5
I
E
9
J
D
3 Tabel 2
De uitwerking in een netwerkdiagram zie je in figuur 7.
Figure 7
Het kritieke pad loopt langs B - E - I. Dat zie je aan de speling bij die activiteiten, die is gelijk aan nul. Let ook eens op de speling bij andere activiteiten. Bijvoorbeeld de activiteiten A en C. De speling is daar slechts één dag. Dat betekent dat als B iets eerder klaar is dan gepland of als A of
8
C iets langer duren dan gepland, het kritieke pad wel eens langs de weg A - C kan komen te liggen. Reken maar eens na hoe het kritieke pad komt te liggen als de tijdsduur van B 10 dagen is. Het is belangrijk altijd alle warden in te vullen bij elke activiteit. Als je bijvoorbeeld alleen de speling zou invullen bij activiteiten op het kritieke pad, dan mis je misschien andere kritische activiteiten met geringe speling. Let ook eens op het verschil tussen activiteiten C en F. Bij C heb je 1 dag speling, bij F ineens 3 dagen. Dat komt omdat de route F - G 15 dagen nodig heeft en de route E -I 17 dagen. Bij F - G win je dus twee dagen. Houd er overigens wel rekening mee dat wanneer zowel bij F als bij G staat dat de speling drie dagen is, dat niet betekent dat je bij beide activiteiten drie dagen kunt vermorsen. Het betekent dat je op het traject F-G in totaal drie dagen speling hebt. Een netwerkdiagram kan je een hoop leren over waar je problemen kunt verwachten. In tabel 3 zie je de gegevens nog eens per activiteit samengevat. Activiteit
Voorganger
Tijdsduur (dagen)
Vroegste Start
Vroegste Einde
Laatste Start
Laatste Einde
Speling
A
-
6
1
6
2
7
1
B
-
12
1
12
1
12
0
C
A
5
7
11
8
12
1
D
A
4
7
10
23
26
16
E
B en C
8
13
20
13
20
0
F
C
8
12
19
15
22
3
G
F
7
20
26
23
29
3
H
E en F
5
21
25
25
29
4
I
E
9
21
29
21
29
0
J
D
3
11
13
27
29
16
Tabel 3 De uitgebreide activiteitentabel en het netwerkdiagram vullen elkaar goed aan en vormen een goede basis voor controle over en weer. Het is handig in de tabel het kritieke pad te markeren. Eventueel kun je activiteiten die weinig speling hebben ook markeren om aan te geven dat daar het gevaar loert dat ze op het kritieke pad komen te liggen.
Variabele schattingen De schatting van een tijdsduur van een activiteit is altijd een schatting. Soms wordt daar wat meer de nadruk op gelegd door bij een geschatte tijdsduur drie waarden op te geven: een optimistische
9
schatting (O), een meest waarschijnlijke schatting (M) en een pessimistische schatting (P). De Optimistische (O) is de kortst mogelijke tijd, de Meest Waarschijnlijke (M) is wat we denken dat het wordt en de Pessimistische (P) is de langste schatting. In plaats van de berekeningen te doen met de gegeven tijdsduur, gebruik je hier uit van de verwachte tijdsduur. Natuurlijk mag je ook de drie schattingen gebruiken voor het maken van drie verschillende planningen: een optimistische, een meest waarschijnlijke en een pessimistische. De verwachte tijdsduur geef je aan met E(t) en de formule er voor luidt:
De verwachte tijdsduur is dus een gewogen gemiddelde van de drie gegeven schattingen. De coëfficiënten bij O respectievelijk M respectievelijk P heten de gewichten. Als je zou willen, mag je de gewichten veranderen, bijvoorbeeld door de pessimistische schatting wat zwaarder te laten wegen. Houd er rekening mee dat de noemer in de formule de som van de gewichten moet zijn. Bij de verwachte tijdsduur hoort ook een variantie. Het symbool daarvoor is Var(t) en de formule luidt:
De wortel uit de variantie is de standaarddeviatie F (sigma). Voor F geldt dus de formule:
Met verwachte tijdsduur, variantie en standaarddeviatie kun je kansen toekennen aan de tijdsduur van je hele project. Maar dat gaat hier te ver.
10
Bijlage. Voorbeeld Hieronder volgt een tabel met activiteiten, afhankelijkheden en tijdsduren voor een project. Als oefening kun je de volgende opdrachten maken. • Maak een netwerkdiagram voor dit project. • Nummer de knooppunten en bepaal bij ieder de VA en de LA. • Bepaal het kritieke pad en de minimale tijdsduur van het project. • Vul daarna de kolommen “vroegste start” tot en met “speling” in. • Controleer het diagram met de tabel. • Ga na welke activiteiten weinig speling hebben en wat er gebeurt als zo’n activiteit uitloopt in de tijd. Verandert dan het kritieke pad? Activiteit
Hint
directe voorganger(s)
tijd in dagen
A
1
-
8
B
2
-
4
C
3
-
12
D
4
A
7
E
5
A
5
F
8
B en C
3
G
9
B en C
4
H
7
B
5
I
11
F
8
J
13
F en G
5
K
12
G
7
L
10
H
7
M
14
H en I
8
N
15
H, I en J
9
O
16
H, I, J en K
6
P
6
D
3
vroegste start
vroegste einde
laatste start
laatste einde
speling
Hint: In de kolom “Hint” staat de volgorde waarin ik het netwerk heb getekend. Je hoeft die volgorde niet aan te houden, het kan ook ietsje anders. De antwoorden staan op de volgende bladzijden. 11
Tabel met antwoorden Activiteit
Hint
directe voorganger(s)
tijd in dagen
vroegste start
vroegste einde
laatste start
laatste einde
speling
A
1
-
8
1
8
15
22
14
B
2
-
4
1
4
9
12
8
C
3
-
12
1
12
1
12
0
D
4
A
7
9
15
23
29
14
E
5
A
5
9
13
28
32
19
F
8
B en C
3
13
15
13
15
0
G
9
B en C
4
13
16
15
18
2
H
7
B
5
5
9
19
23
14
I
11
F
8
16
23
16
23
0
J
13
F en G
5
17
21
19
23
2
K
12
G
7
17
23
20
26
3
L
10
H
7
10
16
26
32
16
M
14
H en I
8
24
31
25
32
1
N
15
H, I en J
9
24
32
24
32
0
O
16
H, I, J en K
6
24
29
27
32
3
P
6
D
3
16
18
30
32
14
Kritieke pad: C - F - I - N Lengte kritieke pad = 12 + 3 + 8 + 9 = 32 dagen
12
Figure 8 Netwerkdiagram AON
13
