NETWERKPLANNING VOLGENS DE METHODE EXTENDED MPM
door ir.
J.A.G.M. Kerbosah
en
H.J. SaheZZ
Rapport KS - 1 februari 19?2
AfdeZing der Bedrijfskunde i.o. Groep OperationeZe Researah Teahnisahe HogesahooZ Eindhoven
Dit rapport is versahenen in het apriZnummer 19?2 van het maandhZad INFORMATIE.
-1-
Inhoud pag. 2
Inleiding
2
MPM
2
2.1
Historie van MPM
2
2.2
Beknopte beschrijving van MPM
3
2.2.1
Aktiviteit is balk
3
2.2.2
Relatie is pijl
3
2.2.3
Negatieve pijlen
4
2.2.4
Negatieve cycli
5
2.3 2.4 3
Omzetting van een MPM balkendiagram In een gerichte graaf
7
Praktisch bezwaar tegen MPM
7
Extended MPM
8
3.1
Uitbreiding toegestane relaties
8
3.1.1
De begin-begin relatie
8
3.1.2
De begin-eind relatie
8
3.1.3
De eind-begin relatie
9
3.1.4
De eind-eind relatie
9
3.1.5
De procentsrelatie
9
3.1.6
Vergelijking relaties bij Precedence en EMPM
3.2
9
Omzetting van een EMPM balkendiagram In een gerichte graaf
3.2.1
Eerste methode
10 onaantastbare
aktiviteitsduur
10·
3.2.2
Tweede methode: variabele aktiviteitsduur
11
3.2.3
Verschil tussen de beide methoden gedemonsteerd aan de hand van een voorbeeld
3.3
EMPM in de praktijk
12 14
4
Eindkonklusie
14
5
Literatuur
15
-21
InZeiding
De METRA - potentiaal - methode (MPM) is, evenals Precedence, een netwerkplanningsmethode van het type "aktiviteit is knooppunt". {4} MPM biedt enige belangrijke voordelen t.o.v. andere methoden van netwerkplanning. Er zijn echter tegen MPM enkele bezwaren aan te voeren 1. De geringe praktische bruikbaarheid. In de originele versie van MPM zijn slechts relaties toegestaan van het type "begin-begin". 2. Het ontbreken van een goed algorithme (efficient en goede foutdetectie) om de netwerkberekeningen uit t-evoeren.
In dit artikel wordt een uitgebreide
vers~e
van MPM voorgesteld,
die we "Extended MPM", kortweg EMPM, hebben genoemd. Deze uitbreiding van MPM is betrekkelijk eenvoudig te implementeren. Ze bestaat hieruit, dat in EMPM aIle relaties die in Precedence voorkomen, ook worden toegestaan. Het MPM - concept van de "negatieve pijl" en de "negatieve cyclus" zijn daarbij in EMPM gehandhaafd. Hierdoor kan men in EMPM een aantal relaties weergeven, die
~n
Precedence niet zijn geoorloofd. Deze extra mogelijkheden van EMPM algorithme.
vere~sen
een wezenlijk ander
De gepubliceerde algorithmen {3,11,12}, allen gebaseerd
op {2}, hebben een sterk i teratief karakter. In {7} zal een algorithme besproken worden, dat bij het ontbreken van cycli slechts een iteratie vergt bij aanwezigheid van (negatieve) cycli slechts een gering aantal iteraties vergt.
2
MPM
2. 1
Histone van MPM
MPM werd in 1958 In Frankrijk ontwikkeld door het adviesburo BEMA {11}. De methode werd voor het eerst toegepast bij de bouw van kern2nergiecentrales aan de Loire.
I
-3-
De naam METRA is afkomstig van de gelijknamige groep van adviesburo's (waarvan o.a. SEMA deeluitmaakt) die zijn klanten MPM als planningsmethode aanbiedt. De aanduiding potentiaal methode is ontstaan d90rdat de methode, mathematisch gezien, analogie vertoont met een potentialensysteem in een elektrisch netwerk.
2.2
Beknopte besohrijving Van MPM Zoals in de inleiding reeds werd gezegd, is MPM een netwerkplanningsmethode van het type "aktiviteit is knooppunt". We kunnen echter beter van "aktiviteit is balk" spreken aangez1en we 1n een balkendiagram de aktiviteiten niet door punten maar door balken voorstellen.
2.2.1
Aktiviteit is balk De aktiviteiten waaruit een projekt 1S samengesteld, worden 1n MPM gerepresenteerd door balken. Een voorbeeld :
aktiviteit I
2.2.2 Relatie is pijZ Teneinde de verdere beschrijving te vergemakkelijken, zullen we eerst enkele definities geven: I
en J zijn twee aktiviteiten
B(I) is het moment waarop aktiviteit I begint L(I,J) is de tijdsduur van de relatie tussen I en J.
M.a.w. de
lengte van de pijl tussen I en J. In MPM zijn alleen relaties toegestaan tussen de beginmomenten van aktiviteiten. In bovengedefinieerde terminologie betekent dit, dat we relaties tussen B{I) en B(J) kunnen weergeven. Een voorbeeld van zo'n relatie is : "Jmag starten 10 tijdseenheden nadat I gestart is".
-4-
In formule luidt deze relatie : B(J) ~ B(I) + 10. In een MPM balkendiagram tekenen we deze relatie als voIgt
I .....
'"
10
J
Deze tekenwijze kunnen we als voIgt formaliseren. De relatie wordt geschreven in de vorm B(J)
~
B(I) + L(I,J).
Links van het > teken staat dan de aktiviteit waar de pijl heenwijst (de "sink" van de pijl), rechts van het > teken staat de aktiviteit waar de pijl vandaan komt (de "source" van de pijl), gevolgd door de lengte van de pijl. B.2.3
Negatieve pijZen Stel dat we de volgende relatie zouden willen weergeven
"J moet starten binnen 12 tijdseenheden nadat I gestart is". In formule kunnen we dit als voIgt noteren :
B(Jl En
~
B(Il + 12
de~e
B(I)
~
formule kunnen we omwerken tot
B(J) - 12.
Waarna we 4e relatie op de
~n
2.2.2 beschreven manler
~n
een netwerk
kunnen tekenen.
~_II ,-------12--------iI
1
J
Met het toestaan van dit soort relaties onderscheidt MPM zich wezenlijk van aIle andere bekende netwerkmethoden.
Ze geven de MPM gebruiker de
mogelijkheid een meer realistisch model van een projekt te formuleren. In de praktijk komen n.l. geregeld relaties voor van de soort starten binnen zoveel dagen na B", datum", etc.
"e
"A moet
moet starten voor een bepaalde
-5-
Bij het gebruik van andere netwerkplanningsmethoden, kunnen dit soort relaties niet in het model (=balkendiagram) worden opgenomen. Het behoeft geen betoog dat dergelijke ommissies in het model kunnen leiden tot routieve resultaten en beslissingen.
2.2.4
Negatieve ayaZi In MPM zijn ook kombinaties toegestaan van de onder 2.2.2 en 2.2.3 beschreven relaties. Bijv. : "J moet starten tussen de 10-de en de 12-de tijdseenheid na de start van I". In formule :B(J)
>
B(J) B(I)
~
en
~
B(I) + 10 B(I) + 12, hetgeen we omwerken tot B(J) - 12.
r
r---
it)
J
-12
.1-
We spreken in zoln geval van een
~cyclus"
(Ius, loop,
~~OPl
Onder de lengte van een cycle verstaan we de som van de lengtes van de pijlen die de cycle vormen. In bovenstaand voorbeeld is de lengte van de cycle dus 10 - 12 = -2. De lengte van een cycle moet kleiner dan of gelijk aan 0 zijn. Is
aan deze voorwaarde niet voldaan, dan hebben we te maken met
een soort "vicieuze cirkel":
~
I LO
-8
J
Dit betekent dat - J moet starten binnen
8 tijdseenheden na de start van I,
- J mag starten minimaal 10 tijdseenheden na de start van I.
-6-
Deze tweerelaties zijn met elkaar in tegenspraak. In een netwerk vormen ze een "positieve cycle". In de praktijk van de netwerkplanning kunnen we op velerlei
man~eren
gebruik maken van de mogelijkheid van het gebruik van negatieve cycli. Zo kunnen we bijv. de relatie "J moet starten precies 5 tijdseenheElen na de start van I" als voIgt
~n
een MPM balkendiagram weergeven.
r
r--
5
J
-5
-12. Bijv.
1(
6
I 5
J
-
.3
J
of
I
.J,
k
8 -J5
6
2
,1
L
Dikwijls zullen in de praktijk de cycli vrij eenvoudig zijn. Ret algorithme en het rekenprogramma dienen echter bestand te z~Jn tegen de meest complexe cycli. mathematisch zo interessant.
Juist dit laatste maakt het probleem
-7-
2.3
Ornzetting Van een MPM baZkendiagram in een geriahte graa[ Nadat een projekt is opgesplitst
~n
aktiviteiten en de relaties
tussen de aktiviteiten zijn vastgelegd. moet het verkregen balkendiagram worden doorgerekend. D.w.z. planningsgegevens zoals "vroegst mogelijke start", "laatst toegestane einde" etc. dienen te worden bepaald. Voordat deze berekeningen kunnen beginnen. moet het balkendiagram omgezet worden in een gerichte graaf. (netwerk) Ditzelfde geldt overigens ook voor Precedence. Deze omzetting kan een onderdeel van het programma
z~Jn.
De omzetting is noodzakelijk, omdat er geen "balkendiagram-theorie", echter weI een grafentheorie bestaat. Deze grafentheorie levert ons o.a. begrippen, stellingen en algorithmen. De omzetting is bij MPM zeer eenvoudig. doordat aIleen relaties toegestaan zijn tussen de beginmomenten van aktiviteiten. De beginmomenten worden beschouwd als de knooppunten van de graaf, de relaties als de pijlen.
2.4
~akti8ah
bezwaar tegen MPM
Als planningsmethode is MPM moeilijk hanteerbaar. De reden hiervan is, dat slecht relaties tussen de beginmomenten van aktiviteiten zijn toegestaan. Willen we bijv. de relatie : "aktiviteit J mag pas starten als aktiviteit I gereed is" aangeven, dan dient dit als voIgt te gebeuren :
I 10
J'
Waarbij we als lengte van de pijl de duur van aktiviteit I nemen. Dit is voor de opsteller van een balkendiagram erg omslachtig. Bovendien moet men, als bij voortgangskontrole de aktiviteitsduur . van I wordt gewijzigd,. de lengte van de pijl wijzigeaoDe kans op fouten wordt zeer groot.
-8-
Als we dezelfde relatie in Precedence willen aangeven, dan vinden we
Q-,
J
I
Deze weergave is veel logischer en direkter.
3
Extended MPM
3.1
Uitbreiding toegestane reZaties Bovengenoemd bezwaar tegen MPM is In EMPM op eenvoudige wijze opgeheven. In EMPM zijn n.l. de volgende soorten relaties toegestaan :
3.1.1
De begin-begin reZatie Deze is van de vorm : "aktiviteit J mag pas beginnen p tijdseenheden na het begin van aktiviteit I". In tekening :
I
i
P 3.1.2
I
J
De begin-eind reZatie "aktiviteit J mag pas eindigen p tijdseenheden na het begin van aktiviteit I". In tekening :
;:r
r p
-9-
3.1.3 De eind-begin
~eZatie
"aktiviteit J mag pas 'beginnen p tijdseenheden na het eind van aktiviteit I". In tekening :
I 3.1.4 De eind-eind
f
~__J_I
~eZatie
"aktiviteit J mag pas eindigen p tijdseenheden na het eind van aktiviteit I". ~n,_.teke!1.i~g
:
I
."
J 3.1.5 De prooentsreZatie "aktiviteit J mag pas starten als de aktiviteitsduur van I
voo~
r % is
verstreken". In tekening
I P9'o
3.1.6
J
VergeZijking reZaties bij Preaedenae en EMPM De behandelde relaties zijn analoog aan de relaties zoals ze voorkomen In de methode Precedence. De begin-eind relatie komt bij Precedence niet voor.
-10Toch heeft deze relatie praktische betekenis. Als voorbeeld nemen We de relatie : "aktiviteit J moet beginnen tussen de 2-de en de 4-de tijdseenheid na het einde van aktiviteit I". Dit kunnen we in EMPM als voigt weergeven
k'---~4-->I__
___ I __
De pijl van J naar I met lengte
3.2
J_ _""",
-4
lS
een begin-eind relatie.
omzetting van een EMPM baZkendiagram in een geriahte graaf In het geval van een EMPM balkendiagram is deze omzetting iets gekompliceerder. We hebben dan twee mogelijkheden, die we achtereenvolgens zullen bespreken.
3.2.1
Eerste methode: onaantastbare aktiviteitsduur Deze eerste mogelijkheid veronderstelt, dat de geschatte tijdsduur van een aktiviteit een onaantastbaar gegeven is. We zullen laten zien dat de omzetting van een EMPM balkendiagram 1n een gerichte graaf in dit geval op analoge wijze kan geschieden als in het geval van een MPM balkendiagram. Hiertoe definieren we :
I en J zijn twee aktiviteiten D(I) lS de aktiviteitsduur van I B(I) lS het beginmoment van I E(I) is het eindmoment van I Omdat d.e aktiviteitsduur onaantastbaar wordt beschouwd, geldt
E(I) = B(I) + D(I) en E(J) = B(J) + D(J) Met behulp van deze twee betrekkingen kunnen de onder 3.1.2 tim
3.1.5
genoemde relaties eenvoudig worden omgewerkt tot relaties
van het type begin-begin. (3.1.1) Alsvoorbeeld nemen we de eind-eind relatie.
-11-
In formule
E(J) ::.. E(I} + p
oftewel
B(J) + D(J) ~ B(Il + D(I) + P en dit werken we om tot B(J) ~ B(I) + D(I) - D(J) + p.
We hebben dan een begin-begin relatie gevormd, met als relatieduur
D(I) - D(J) + p. Nadat aIle relaties In een EMPM balkendiagram tot begin-begin relaties zijn omgewerkt, hebben we in feite een MPM netwerk verkregen. In 2.3 hebben we reeds laten zien hoe we dit kunnen interpreteren als een gerichte graaf.
3.2.2 TWeede methode: variabeZe aktiviteitsduur Bij deze methode wordt verondersteld, dat de duur van een aktiviteit enigermate variabel is. Dit heeft aIleen zin wanneer men de aktiviteit kan onderbreken de uitvoering kan vertragen door bijv. minder produktiemiddelen. In te schakelen. Als ondergrens van de aktiviteitsduur wordt de "normale" duur genomen. Dit betekent het aantal tijdseenheden dat uitvoering zou vergen bij inzet van "normale" kapaci teit, "normaal" werktempo, etc. Anders gezegd, de aktiviteitsduur die gekozen zou zijn als we de eerste methode (3.2.1) zouden gebruiken. Als bovengrens van de aktiviteitsduur dient te worden genomen het aantal tijdseenheden dat de uitvoering zou vergen bij minimale kapaciteit of bij onderbreking. Voorbeeld : Een aktiviteit A kan door 5 mensen worden uitgevoerd in 3 dagen, of door 1 man in 18 dagen.
Ook aIle tussenliggende mogelijkheden zijn toegestaan.
De ondergrens van de aktiviteitsduur zouden we dus 3 kunnen nemen, de bovengrens 18.
Dus 3 sP(A)~ 18.
Een dergelijk balkendiagram kunnen we als voIgt omzetten In een gerichte graaf : als knooppunten nemen we de begin- resp. eindpunten van de aktiviteiten als pijlen nemen we de relaties, aangevuld met een paar pijlen per aktiviteit, die het begin- resp. eindpunt van de aktiviteit verbinden. De bovengenoemde aktiviteit A kunnen we in een graaf dan als voIgt representeren.
-123 B(A)
E(A)
-18 Merk 0ps dat in het geval ondergrens=bovengrens s we te maken hebben met een aktiviteit met een onaantastbare aktiviteitsduur. Bijv. een aktiviteit die exact-5 tijdseenheden duurt :
5 B( •
E(. )
-5
De methode die onder 3.2.1 beschreven staats zouden we als een bijzonder geval kunnen beschouwen van de hier beschreven aanpak;
met dien
verstande dat de procentsrelatie bij variabele aktiviteitsduur niet lS toegestaan. Merk op dat de relaties niet meer omgezet behoeven te worden 1n begin-begin relaties •
• 2.3
VerschiZ tussen beide methodes gedemonstreerd aan de hand Van een voorbeeZd Om het verschil tussen de beide beschreven methoden (vaste en variabele aktiviteitsduur) duidelijk te laten uitkomen s zullen we dit demonstreren aan de hand van een klein voorbeeld. Een projekt bestaat uit de volgende drie aktiviteiten : (elektrische leidingen aanleggen) met een duur van 5 dagen s J (stukadoorswerk) met een duur van 3 dagen s
I
K (schilderswerk) met een duur van 4 dagen. De drie aktiviteiten kunnen parallel worden uitgevoerd s met de
~estriktie
dat de elektriciens minstens een dag bezig moeten zlJn voordat de stukadoors kunnen beginnen s terwijl het stukadoorswerk niet gereed mag komen voordat de elektriciens gereed zlJn. Dezelfde beperkingen gelden voor de schilderswerkzaamheden t.o.v. de stukadoorswerkzaamheden.
-13-
We kunnen de relaties ala volgt In formules noteren : B(J) 2:.. B(I) + 1. $(J) _~ E(I) en SeX) ~ Be,]) ... 1, E(K) .~ E\(J)
J.fj
te:~~n1 ttlg
0
I
0
.T
:1
t
.-
Nemen we aan dat I.,J en K
k
als~
duur exact resp. 5, 3 en 4 dagen zullen
hebben, en dat we werken volgens methode 1. Ret resultaat van de berekeningen geven we weer via een GAntt-chart.
eZektr. Zeidingen
Is tukadoors I soki lderswerk
~
De totale projektduur zal dus 7 dagen zijn. Voor toepassing van de tweede methode nemen we aan, dat aktiviteit Jverlengd kan worden tot een duur van maximaal bijv. 10 dagen. Dit zou kunnen gebeuren door de aktiviteit te laten uitvoerendoor minder stukadoors. Ret resultaat van de tweede methode zal dan zijn
e
[ stukQdoors
)
lsahi'tderswerk
1
-14-
Met een totale projektduur van
6 dagen.
De winst van een dag wordt bereikt, door J op dag 2 te laten aanvangen en de duur met een dag te verlengen tot
4 dagen.
Dit betekent dat J In een gematigder tempo moet worden uitgevoerd.
Dit klinkt paradoxaal
een
aktiviteit wordt in uitvoering
vertraagd, waardoor de totale projektduur wordt verkort. De verklaring is te vinden in het feit, dat de drie aktiviteiten dan gedurende een grotere tijdsperiode parallel kunnen lopeno Eerder beginnen en kalmer aan werken kan soms tijdwinst opleveren.
3.3
EMPM in de praktijk Voor de verwerking van EMPM netwerken lS een komputerprogramma 6ntwikkeld, dat de naam ANNETTE heeft gekregen (Activity on Node Networkanalysis TH
~indhoven).
{8}
De term "verwerking" moet zeer rUlm worden opgevat. We verstaan hieronder niet alleen de omzetting tot een graaf en het doorrekenen van het netwerk, maar tevens de gehele administratieve afhandeling, zoals bestandsmanipulatie, rapportering, etc. Hierdoor is het programma niet aIleen geschikt voor de planning vooraf, maar kan het ook gebruikt worden voor de begeleiding (voortgangskontrole) van het projekt. Voor de omzetting tot een graaf wordt voorlopig gebruik gemaakt van de onder 3.2.1 beschreven methode. De praktische konsekwenties van de methode die onder 3.2.2 wordt beschreven worden nog onderzocht. De planning en·voortgangskontrole met EMPM van enkele projekten in de bouwsfeer is en wordt in de praktijk beproefd. De tot nu toe bereikte resultaten stemmen tot tevredenheid.
4
EindkonkZusie EMPM is een netwerkplanningsmethode, die de voordelen van MPM en Precedence in zich verenigt. Als voordeel van EMPM voor de gebruiker kunnen we noemen : de diversiteit van relaties die Precedence hanteerbaar maken de mogelijkheid een reeeler model van de werkelijkheid konstrueren, die MPM te bieden heeft.
te
-15-
5
Lite:r>atuu:r> I
1
Dibon M.L. . Ordonnancement et potentiels , Methode MPM Herman, Paris (1970)
2
and D.R. Fulkerson Flows in networks Princeton, New Jersey (1962)
3
GewaJ.d K. und· D. Sau1.er Ein ALGOL-programm fur die METRA-potentiaJ. methode
FordL.R~
Ablaut, planung und forschung 7(1966) H4, pag.199
4
Houten F.J. van, G.M. Nijssen en J.G~ Tromp Hebben PERT en CPM niet teveel belangstelling? Informatie jrg. 10, nr. 2 (1968), page 20
5
Houten F.J. van, G.M. Nijssen en J.G. Tromp Netwerkplanning volgens de Precedence methode Samson n.v. Alphen aId Rijn-Brussel (1970)
6
Kerbosch J.A.G.M. en H.J. Schell Reactie van lezers Informatie jrg. 13, nr. 12 (1971). page 593
7
Kerbosch J.A~G~M~ en H.J. Schell Een algorithme voor netwerkplanning volgens de Metra-potentiaaJ. methode Technisch Rapport KS-2 ;,Technische Hogeschool Eindhoven
8
Kerbosch J.A.G.M. en H.J. Schell Gebruikershandleiding bij het netwerkprogramma ANNE'l'TE Technisch Rapport KS-3 ,Technische Hogeschool Eindhoven
-16-
9
Nabben J.P.J.
De Metra-potentiaal methode Mededelingen operationele research, dec. 1967, page 325 10
Nijssen
G.M~
Project planning met netwerkmethodes In:t'ormatie jrg. 13, nr. 9 (1971), pag. 384 11 . Roy B. Graphes et ordonnancements Revue Francaise de recherche operationelle
nr. 25,6 (1962.10), page 323 12
Wille· H., ·K. Gewald md
H.D~
Weber
Netzplantechnik, Methoden zur planung und uberwachung von projekten Band I. Zeitplanung, Oldenbourgh, Munchen (1966)
