UNIVERSITEIT GENT FACULTEIT ECONOMIE EN BEDRIJFSKUNDE ACADEMIEJAAR 2002-2003
Fasetransities in projectplanning: morfologische en hulpmiddelen gerelateerde maatstaven
Scriptie voorgedragen tot het bekomen van de graad van: Licentiaat in de toegepaste economische wetenschappen
Ines Crabbe onder leiding van Prof. Dr. Mario Vanhoucke
II
Inhoudsopgave
I.
ALGEMENE INLEIDING.............................................................................................. 1
II. projectplanning ................................................................................................................. 3 1. Het ontstaan........................................................................................................................ 5 2. Netwerkplanning................................................................................................................. 7 2.1. PERT............................................................................................................................ 8 2.2 Methode van het kritieke pad (CPM) ......................................................................... 10 2.3 Vergelijking tussen beide methodes ........................................................................... 11 3. Projectplanning onder hulpmiddelenbeperkingen (RCPS)............................................... 13 3.1. Optimalisatie .............................................................................................................. 17 3.1.1. Lineair programmeren...............................................................................................18 3.1.2. Integer programmeren...............................................................................................18
3.2. Heuristieken............................................................................................................... 19 3.2.1. Meta-heuristieken .....................................................................................................19
3.2.1.1. Genetische algoritmes.................................................................................... 20 3.2.1.2. Tabu Search................................................................................................... 20 3.2.1.3. Simulated annealing....................................................................................... 20 3.2.2. Op prioriteitsregel(s) gebaseerde heuristieken.............................................................21
3.2.2.1. Serie en parallel plannen................................................................................ 21 3.2.2.2. Prioriteitsregels .............................................................................................. 24 4. Hulpmiddelennivellering .................................................................................................. 29 5. Primavera vs. andere projectmanagement software ......................................................... 32 5.1. Indeling projectmanagement software....................................................................... 32 5.2. Vergelijkende studie .................................................................................................. 34 III. Fasetrantsities in projectplanning ................................................................................. 40 1. Morfologie van netwerken................................................................................................ 41 1.1. Coëfficiënt van netwerk complexiteit (CNC)............................................................ 41 1.2. Ordekracht (OS)......................................................................................................... 42 1.3. Complexiteitsindex (CI) ............................................................................................ 42 1.4. Morfologische indicatoren I1 tot I6 . ........................................................................... 42
III 2. Topologische maatstaven en RCPSP................................................................................ 46 3. Hulpmiddelen gerelateerde maatstaven............................................................................ 48 3.1. Hulpmiddelenfactor (RF)........................................................................................... 48 3.2. Hulpmiddelenkracht (RS).......................................................................................... 48 3.3. Hulpmiddelenrestrictiviteit (RC)............................................................................... 49 4. Op hulpmiddelen gebaseerde parameters en RCPSP ....................................................... 50 5. impact van hulpmiddelengerelateerde en morfologische maatstaven op projectmanagement software. ............................................................................................... 52 6. Netwerkgeneratoren.......................................................................................................... 58 IV. Onderzoek....................................................................................................................... 62 1. Hulpmiddelennivellering in Primavera 3.1 (P3)............................................................... 63 2. Netwerkgeneratie met behulp van RanGen 2 ................................................................... 68 3. De onderzochte prioriteitsregels ....................................................................................... 72 4. Impact van de morfologische indicatoren......................................................................... 74 V.
besluit ............................................................................................................................... 76
III
Lijst met figuren
Figuur 1. 1: Gantt-kaart ......................................................................................................... 5 Figuur 1. 2: start-start relatie, start-einde relatie, einde-start relatie en einde-einde relatie .. 7 Figuur 1. 3: pijlenvoorstelling................................................................................................ 8 Figuur 1. 4: Bètaverdeling ..................................................................................................... 9 Figuur 1. 5: PERT, Primavera Project Planner 3.1.............................................................. 10 Figuur 1. 6: netwerk diagram............................................................................................... 11 Figuur 1. 7: knooppuntenvoorstelling.................................................................................. 13 Figuur 1. 8: serie planningsschema ..................................................................................... 22 Figuur 1. 9: parallel planningsschema ................................................................................. 22 Figuur 1. 10: combinaties planningsschema’s en prioriteitsregels...................................... 23 Figuur 1. 11: vergelijking tussen optimale en heuristische oplossingen voor RCPSP........ 26 Figuur 1. 12: relatieve prestatie van acht prioriteitsregels................................................... 27 Figuur 1. 13: hulpmiddelenhistogram.................................................................................. 33 Figuur 1. 14: types projectmanagement softwarepakketten................................................ 34 Figuur 1. 15: technische gegevens van vijf verschillende softwarepakketten..................... 37 Figuur 1. 16: gebruikt projectmanagement softwarepakket in de bouwnijverheid ............. 38 Figuur 1. 17: relatie tussen gebruikt softwarepakket en aantal gebruikte analytische technieken voor de bouwnijverheid ............................................................................. 39
Figuur 2. 1: gemakkelijke-hard-gemakkelijk complexiteitspatroon, CPU-tijd in funtie van RS en RC ..................................................................................................................... 50 Figuur 2. 2: niveaus van systematisch gegenereerde probleemparameters ......................... 53 Figuur 2. 3: gemiddelde en standaardafwijking van het percentage afwijking bekomen door zeven projectmanagement softwarepakketten............................................................. 54 Figuur 2. 4: significantieniveaus voor parametrische en niet-parametrische testen, het effect van onafhankelijke parameters op projectmanagement software................................ 55 Figuur 2. 5: performatieklasses van projectmanagement softwarepakketten...................... 56 Figuur 2. 6: gemiddelde afwijking van duurtijd (%) voor verschillende waarden van RS . 57 Figuur 2. 7: gemiddelde afwijking van duurtijd (%) voor verschillende waarden van RF en CNC............................................................................................................................. 57 Figuur 2. 8: netwerkgeneratoren in de literatuur ................................................................. 59
IV
Figuur 3. 1: opties voor hulpmiddelennivellering in Primavera 3.1.................................... 63 Figuur 3. 2: prioriteitsregels in Primavera 3.1..................................................................... 65 Figuur 3. 3: gebruikte parametersettings netwerkgenerator RanGen 2 ............................... 68 Figuur 3. 4: relatie tussen I2 en overige morfologische indicatoren.................................... 69 Figuur 3. 5: relaties tussen morfologische indicatoren........................................................ 70 Figuur 3. 6: algemene prestaties van de 11 onderzochte prioriteitsregelsFout! Bladwijzer niet gedefinieerd. Figuur 3. 7: impact van I2 ............................................. Fout! Bladwijzer niet gedefinieerd. Figuur 3. 8: impact van I3 , I5 en RC ............................. Fout! Bladwijzer niet gedefinieerd.
V
Ondergetekende Ines Crabbe bevestigt hierbij dat onderhavige scriptie mag worden geraadpleegd en vrij mag worden gefotokopieerd. Bij het citeren moet steeds de titel en de auteur van de scriptie worden vermeld.
Mijn bijzondere dank gaat uit naar: Prof. Dr. Mario Vanhoucke om te willen optreden als promotor. Prof. Dr. Roland Paemeleire en Prof. Dr. Ir. Ann Vereecke om dit werkstuk te willen beoordelen als commissarissen. De heer Onno Kors van Primavera, voor de bereidwilligheid deze scriptie te ondersteunen en het verschaffen van Primavera Project Planner 3.1. Alle professors en assistenten uit de opleiding TEW, voor de vier jaar kennisverschaffing. Mijn ouders, vrienden en medestudenten voor de morele steun. Zonder deze mensen was dit werk nooit tot stand gekomen.
Crabbe Ines, 2 mei 2003
1
I.
ALGEMENE INLEIDING
Toepassingen van projectplanning komen in veel verscheide contexten voor, zoals bouwkunde, softwareontwikkeling, R&D projecten en dergelijke meer. Overschrijding van de toegekende budgetten en de geplande duur en toegevingen op de voorgeschreven werkinhoud blijken echter een gemeenschappelijk kenmerk van de meeste projecten, niet zelden ondanks het gebruik van gespecialiseerde software.
Dergelijke softwarepakketten, die steeds meer toepassing vinden in zowat alle industrieën, steunen op één of meerdere prioriteitsregels om de activiteiten van het project te plannen ingeval volgordebeperkingen en om hulpmiddelen aan de activiteiten toe te kennen ingeval hulpmiddelenbeperkingen. Toch valt de bekomen totale projectduur vaak nog hoger uit dan de optimale, zoals berekend met de methode van het kritieke pad. Bedoeling van deze scriptie is de prestaties van een aantal van deze prioriteitsregels, zowel enkele opgenomen in het softwarepakket Primavera Project Planner 3.1 als enkele sterk aanbevolen uit de literatuur, te analyseren. Daartoe werd de netwerkgenerator RanGen 2 gebruikt zodat de impact van zowel morfologische als hulpmiddelen gerelateerde indicatoren van netwerken kan nagegaan worden.
Verschillende
auteurs
wezen
reeds
op
de
inconsistentie
van
gebruikte
termen
in
projectmanagement. Vertalingen leiden maar al te vaak tot verwarring en foutieve opvattingen. Dit is de reden waarom het Project Management Instituut een gids uitgegeven heeft, de PMBOK1 , waarin alle algemeen aanvaarde termen voorkomen. Vandaar dat in deze scriptie ook her en der deze termen of afkortingen zullen gebruikt worden. Desalniettemin zal ook steeds de Nederlandstalige term en beschrijving gegeven worden.
In een eerste deel van dit werk wordt nader ingegaan op de initiële stap in projectplanning, namelijk netwerkplanning. Twee belangrijke methodes worden besproken en vergeleken, met name PERT en CPM (methode van het kritieke pad). Vervolgens wordt het planningprobleem onder hulpmiddelenbeperkingen (RCPSP) besproken. Om dit probleem op te lossen werden veelvuldig 1
Project Management Body Of Knowledge
2 zowel exacte als heuristische procedures voorgesteld. De exacte methodes hebben tot nu toe de weg naar de softwarepakketten niet gevonden wegens de te grote complexiteit en oplossingstijd. Naast dit probleem wordt ook dat van hulpmiddelennivellering besproken, waarbij gestreefd wordt naar reductie van variabiliteit in hoeveelheid hulpmiddelengebruik. Het eerste deel wordt afgesloten met een indeling en vergelijking van de verschillende projectmanagement softwarepakketten.
Problemen in projectplanning kunnen fasetransities ondergaan, wat er op neer komt dat de berekeningscomplexiteit van het probleem varieert naargelang de fase waarin het zich bevindt. Deze fasetransities worden bepaald door de morfologische en hulpmiddelengerelateerde parameters van netwerken. Deze verschillende parameters en hun relatie met het planningsprobleem onder hulpmiddelenbeperkingen wordt uitvoerig besproken.
Het onderzoek en de resultaten ervan worden weergegeven in deel III. Vooreerst werden netwerken gegenereerd met behulp van de netwerkgenerator RanGen 2. Dit werd gedaan voor dertig activiteiten en 4 hulpmiddelen. De parametersettings van de zes gebruikte morfologische indicatoren en hulpmiddelenrestricitiviteit zijn terug te vinden onder punt twee. De relaties tussen deze verschillende indicatoren worden uitvoerig beschreven. Voor elke setting werden telkens 50000 netwerken gegenereerd. Vervolgens werden elf prioriteitsregels geprogrammeerd om de gecreëerde probleeminstanties op te lossen. Het normale en maximale hulpmiddelengebruik dient vooraf ingesteld te worden. Dit zal gedaan worden voor verschillende intervallen om de invloed daarvan na te gaan. Daarnaast zijn twee opties beschikbaar wanneer hulpmiddelenbeperkingen zich voordoen. Enerzijds kan de hulpmiddelenbeschikbaarheid stijgen van het normale niveau tot het maximale. Anderzijds kan de normale beschikbaarheid stijgen met 10% van het verschil tussen de normale en maximale hoeveelheid. Ook de impact van deze twee opties zal geanalyseerd worden. Tenslotte wordt ook nog nagegaan welk effect de hulpmiddelenrestricitiviteit heeft op de oplossingskracht.
“Plans are nothing, planning is everything” Dwight Eisenhower
Deel I
II.
3
Projectplanning
PROJECTPLANNING
Een project kan gedefinieerd worden als een uniek proces, bestaande uit een verzameling gecoördineerde en gecontroleerde activiteiten met start- en eindtijdstippen, die worden uitgevoerd met het oog op het realiseren van een doelstelling binnen voorgeschreven tijds-, hulpmiddelen- en kostenbeperkingen (Demeulemeester E. en Herroelen W., 2000). Projectmanagement is dan het plannen, coördineren, beheren en opvolgen van de uitvoering van de projectactiviteiten (De Reyck B. en Herroelen W., 1999). Commerciële projectmanagement softwarepakketten ondersteunen het plannen van een project, het implementeren van het plan en het opvolgen van de vooruitgang van het project.
Een project uitvoeren gebeurt in drie fasen, namelijk projectplanning, project ‘scheduling’ 2 en project opvolging. In de eerste fase zal men de activiteiten kiezen die nodig zijn om de vooraf bepaalde doelstellingen te bereiken. Zo bekomt men als het ware een deels geordende opeenvolging van activiteiten die verder kunnen opgesplitst worden tot meer gedetailleerde taken. De eerste fase betekent dus een globaal plan opstellen voor het project. In de tweede fase, project ‘scheduling’, zal men het projectplan meer in detail gaan bekijken. Dit is de fase waarin tijdelijke technische beperkingen zullen geanalyseerd worden en waarin hulpmiddelen zullen toegewezen worden in die mate dat het project kan uitgevoerd worden. Bovendien worden de start- en eindtijdsstippen van de activiteiten nauwkeurig vastgelegd (Tormos et al., 2002). Het onderwerp van deze scriptie zal zich vooral op dit niveau situeren. In de laatste fase tenslotte, de projectopvolging, probeert men het project te controleren en te beheersen. Daarbij worden de gebeurlijke verschillen tussen plan en realiteit geanalyseerd. Eventueel moeten correctieve aanpassingen gebeuren.
Projectmanagementsoftware, wat tot de sterkste klimmers in de softwaremarkt behoort, werd ontwikkeld om de projectmanager te ondersteunen bij het opstellen, controleren en herzien van het projectplan. Deze pakketten automatiseren hulpmiddelenplanning en enkele wiskundige
2
In het Nederlands zouden deze twee termen gelijk vertaald worden naar ‘projectplanning’. Vandaar dat hier de meer genuanceerde Engelstalige term gebruikt wordt.
Deel I
4
Projectplanning
berekeningen, die voorheen met methodes zoals PERT en CPM manueel dienden te gebeuren. Ze bieden bovendien een grote flexibiliteit bij het rapporteren van projectplannen.
Deel I
5
Projectplanning
1. Het ontstaan
Het prille begin van projectmanagement situeert zich al in het begin van de 20ste eeuw. Henry Gantt was de persoon die tussen de jaren 1920 en 1940 de nu reeds zeer gekende Gantt-kaarten ontwikkelde. Daarbij worden de uit te voeren activiteiten voorgesteld op de verticale as en hun overeenkomstige duur op de horizontale as. De horizontale blokken met variërende lengte stellen de opeenvolging, het begintijdstip en de tijdsspanne van elke activiteit voor. De Gantt-kaart in de projectmanagement softwarepakketten laat de gebruiker toe interactieve wijzigingen aan te brengen.
Figuur 1. 1: Gantt-kaart
In de jaren die volgden werden ten gevolge van het Manhattan project voor het eerst planningstechnieken in gebruik genomen. De jaren 1950 werden gekenmerkt door de ontwikkeling van netwerkmodellen die tijdsbeheersing van projecten tot doel hadden. Meer bepaald gaat het hier over het ontstaan van de methodes PERT en CPM (zie later). In het daaropvolgende decennium werden deze methodes ter tijdsplanninganalyse verder uitgebreid. Tussen 1970 en 1990 geschiedde de grote doorbraak wanneer de eigenlijke projectmanagement softwarepakketten op de markt kwamen en wanneer meer en meer aandacht uitging naar hulpmiddelenallocatie. In de meest recente jaren staan ontwikkeling van diverse nieuwe instrumenten, zoals koppeling van het softwarepakket met MRPsystemen, en uitgebreider onderzoek naar hulpmiddelenallocatie voorop.
Tot de jaren 70 was projectmanagement software enkel toepasselijk voor grote bedrijven, enorm kostelijk en enkel beschikbaar op grote computers. Door de grote technologische vooruitgang, de
Deel I
6
Projectplanning
lagere kost van de pc en het grootschalig gebruik van internet zijn vele projectmanagement softwarepakketten nu beschikbaar variërend van enkele honderden tot duizenden euro’s.
Deel I
7
Projectplanning
2. Netwerkplanning Het basisprobleem in projectplanning is de kritieke activiteiten weten te vinden en de optimale starttijden van activiteiten in een activiteitennetwerk te determineren. Dit netwerk is een deels geordende set van activiteiten met voorgeschreven duurtijden die samen een niet cyclische grafiek vormen. Vanzelfsprekend is ook het bepalen van de vroegste eindtijd van het project van uiterst belang.
De traditionele netwerkplanningsmethoden, zoals PERT (‘Program Evaluation and Review Technique’) en de methode van het kritieke pad (‘Critical Path Method’ of CPM), maken het mogelijk om plannen voor projecten te vinden met minimale duurtijd. Deze technieken gaan er echter van uit dat de verscheidene hulpmiddelen, die nodig zijn voor de voltooiing van het project, onbeperkt zijn, wat nogal vaak strookt met de werkelijkheid. Vandaar dat deze veronderstelling in de loop der jaren afgezwakt werd en steeds meer rekening gehouden wordt met hulpmiddelenbeperkingen. In de literatuur worden deze hulpmiddelenbeperkingen bij het plannen van een project bestudeerd in het domein van ‘resource-constrained project scheduling’ of kortweg RCPS. De volgorderelaties in CPM en PERT veronderstellen dat activiteiten pas kunnen beginnen wanneer de vorige beëindigd werden. Elmaghraby en Kamburowski (1992) hebben deze volgorderelaties uitgebreid tot vier types, namelijk start-start (SS), start-einde (SF), einde-start (FS) en einde-einde (FF) relaties.
Figuur 1. 2: start-start relatie, start-einde relatie, einde-start relatie en einde-einde relatie
Deze veralgemeende volgorderelaties maken het mogelijk een minimale of maximale tijdsspeling tussen een paar activiteiten vast te leggen. Een minimale tijdsspeling veronderstelt dat een activiteit slechts kan gestart (beëindigd) worden wanneer de voorgaande activiteit reeds enige tijd gestart (beëindigd) werd. Een maximale tijdsspeling daarentegen veronderstelt dat een activiteit ten laatste gestart (beëindigd) zou moeten worden na een bepaalde tijdsperiode van een andere activiteit.
Deel I
8
Projectplanning
2.1. PERT3
PERT werd aan het eind van de jaren 1950 door de zeemacht ontwikkeld voor het Polaris raket programma. Men realiseerde zich al gauw dat de beheersing en coördinatie van de beschikbare hulpmiddelen voor dit enorme project, met maar liefst 250 hoofdaannemers en 9000 onderaannemers, het grote struikelblok zou zijn. Daarom werd, in samenwerking met het consultancybedrijf van Booz, Allen en Hamilton, het ‘Program Evaluation and Review Technique’ of kortweg PERT ontwikkeld. Dit is een instrument dat planning, beheersing, rapportering en communicatie van projecten toelaat (Focken, 2002).
De PERT-methode maakt gebruik van een pijlenvoorstelling, waarbij de pijlen staan voor activiteiten. De zeshoeken aan het begin en uiteinde van de pijl worden knooppunten genoemd en geven het start –en eindpunt aan van iedere taak of activiteit. Deze pijlenvoorstelling werd later in vraag gesteld. Algemeen wordt nu de knooppuntvoorstelling aanvaard, zoals die ook van toepassing is in alle projectmanagement softwarepakketten (zie later).
Figuur 1. 3: pijlenvoorstelling
Gewoonlijk veronderstelt men bij het plannen dat de duur van de activiteiten precies gekend is. In realiteit is dit echter zelden het geval. Wanneer het plan opgemaakt wordt, is meestal nog geen gedetailleerde informatie beschikbaar over de methodes en hulpmiddelen die nodig zijn voor de realisatie van de activiteiten. Chanas et al. (2002) stelden bovendien dat zelfs wanneer de duurtijden van activiteiten onafhankelijk willekeurige variabelen waren, de totale projectduur nog niet na te gaan valt, tengevolge van de afhankelijkheden geïntroduceerd door de morfologie van een netwerk4 . Dit probleem werd al gauw opgemerkt door de ontwikkelaars van PERT. Zij stelden dan ook voor de duur van de activiteiten te bepalen aan de hand van waarschijnlijkheidsverdelingen. Zo poogden ze het gemiddelde en de standaardafwijking van de vroegste starttijden van activiteiten te evalueren. 3
Program Evaluation and Review Technique
Deel I
9
Projectplanning
PERT wordt dus voornamelijk gebruikt wanneer de tijdsduur van de activiteiten alleen geschat kan worden. De verwachte tijd, nodig voor voltooiing van een project, wordt dan ook meestal berekend als het gewogen gemiddelde van (Focken T., 2002):
-
de optimistische tijd (To),
-
de pessimistische tijd (Tp),
-
meest waarschijnlijke tijd (Tw),
To +4Tw+Tp volgens de vergelijking: Tv = ––––––––––––– ,waarbij men uitgaat van een bèta-verdeling. 6
Figuur 1. 4: Bètaverdeling
De PERT-methode is net zoals de Gantt-kaart een grafisch hulpmiddel voor het opstellen van een planning en deze te schematiseren. Daarbij worden de taken, hun duur en hun afhankelijkheidsinformatie weergegeven. Wanneer de volgorderelaties belangrijker zijn dan het plan op zich wordt PERT geprefereerd boven de Gantt-kaart. Figuur 1.5 toont een voorbeeld van zo’n PERT-schema uit Primavera Project Planner 3.1.
4
Op de relatie tussen morfologie van een netwerk en oplossingsmogelijkheid van planningsproblemen wordt in deel II dieper ingegaan.
Deel I
10
Projectplanning
Figuur 1. 5: PERT, Primavera Project Planner 3.1
2.2 Methode van het kritieke pad (CPM)
Het bedrijf Du Pont liet in 1956 een geautomatiseerd systeem ontwikkelen om het plannen en rapporteren van hun engineering programma’s te verbeteren. Het resultaat van deze opdracht is de netwerkbenadering die we kennen onder de naam, CPM, of ‘Critical Path Method’ (focken T., 2002).
Net zoals de Gantt-kaarten helpt CPM bij het bepalen van de lay-out van de projectactiviteiten. Deze methode speelt dus een belangrijke rol bij het opmaken van het plan en bij het plannen van de hulpmiddelen. Bovendien kan aan de hand van het kritieke pad nagegaan worden of de projectdoelen bereikt worden of in welke mate men er van afwijkt. Het voordeel dat CPM biedt ten opzichte van de Gantt-kaart is dat het toelaat activiteiten te identificeren die op tijd moeten voleindigd worden zodat het volledige project tijdig kan afgewerkt worden. CPM identificeert ook welke activiteiten voor enige tijd kunnen uitgesteld worden wanneer hulpmiddelen opnieuw moeten toegewezen worden. Activiteiten kunnen immers verschoven worden binnen hun spelingruimte, vaak aangeduid met de meer gekende benaming ‘slack’. De relatie tussen activiteiten en tijd is wel niet zo zichtbaarder zoals dit het geval is bij de Gantt-kaart. Het grootste voordeel van CPM is dat het de mogelijkheid biedt de minimale tijdsduur van een project te bepalen.
De methode van het kritieke pad zal, net zoals PERT, het project in een netwerk voorstellen. Een projectnetwerk toont alle activiteiten met hun opeenvolging en afhankelijkheidsrelaties. Eens de activiteiten toegewezen werden aan de verantwoordelijke persoon, kan de duur van de activiteiten geschat worden, wat mogelijk maakt het kritieke pad te determineren. Dit is de opeenvolging van
Deel I
11
Projectplanning
de kritieke activiteiten, het pad doorheen het netwerk van begin tot einde, met de grootste duur. De kritieke activiteiten bepalen de duur van het totale project. Netwerkanalyse stelt dat een activiteit kritiek is als en slechts als de vroegste en laatste starttijd samenvallen. Wanneer de kritieke activiteiten een vertraging oplopen, dan zal ook de einddatum van het project mee verschuiven, gezien deze kritieke activiteiten geen speling of ‘slack’ kennen, dit in tegenstelling tot de nietkritieke activiteiten. Wanneer de duurtijden van de activiteiten echter niet precies gekend zijn, kan de methode van het kritieke pad niet meer toegepast worden (Chanas et al., 2002).
Figuur 1. 6: netwerkdiagram (Bron: Focken T., 2002)
Het kritieke pad in figuur 8 doorloopt de activiteiten 12,9,7,5,4 en 1. deze kritieke activiteiten bepalen de totale projectduur, in dit voorbeeld gelijk aan 40 dagen.
2.3 Vergelijking tussen beide methodes
PERT wordt geprefereerd voor het plannen van projecten wanneer de tijdsschatting onzeker is. De bètaverdeling helpt dan om de duur beter in te schatten en statistische instrumenten kunnen de drietijdenschatting gebruiken om de verwachte duur en de mogelijkheid van het plan te voorspellen. De kracht van deze methode ligt dus in het gebruik van kansschatting voor de activiteitsduur. Voorkeur gaat naar CPM wanneer het vertrouwen in de tijdsschatting voor elke activiteit groter is. De sterkte van deze methode is de mogelijkheid van tijd-kost inruil. Algemeen staat vast dat CPM een betere basis vormt voor budgetbeheersing en dat PERT een kortere projectduur oplevert (Focken T., 2002).
Deel I
12
Projectplanning
PERT en CPM blijken echter enkel nuttig te zijn wanneer de projectdeadline niet vast staat en de hulpmiddelen niet beperkt zijn, noch door beschikbaarheid, noch door tijd. Dit is echter slechts zelden het geval in realiteit. Het planningprobleem onder hulpmiddelenbeperkingen (zie later) meer bekend als ‘resourceconstrained project scheduling problem’ (RCPSP) vormt dan ook een enorm belangrijk studiegebied in projectmanagement 5 .
Het wordt al gauw duidelijk dat netwerken plannen en veranderen volgens de traditionele methodes enorm moeilijk wordt en vooral veel tijd in beslag neemt wanneer het aantal activiteiten stijgt. Als de volgorde of de duur van activiteiten zou moeten veranderd worden, moet het volledige proces opnieuw doorlopen worden. Projectmanagement software biedt dan ook het voordeel deze methodes geautomatiseerd te hebben. Veranderingen kunnen daardoor herhaaldelijk plaatsgrijpen en zonder veel moeilijkheden berekend worden door de computer. Gevolg van dit alles is dus de mogelijkheid van een ‘wat als’ analyse. Verschillende scenario’s kunnen vergeleken worden, wat de gebruiker van de software een beter inzicht in het probleem kan verschaffen.
Waar de Gantt-kaart, de CPM-methode en de PERT-methode falen om rekening te houden met hulpmiddelenconflicten, melden de softwarepakketten wanneer deze overdadig ingezet worden. Zij zullen dan ook automatisch het projectplan aanpassen (Corder S. en Ruby Jr. R., 1993). De softwarepakketten incalculeren dus het RCPS probleem.
5
In overeenstemming met de vakliteratuur en om eventuele misverstanden te vermijden zal verder de Engelstalige afkorting RCPS gebruikt worden.
Deel I
13
Projectplanning
3. Projectplanning onder hulpmiddelenbeperkingen (RCPS) Wanneer hulpmiddelen beperkt zijn, wat nogal vaak het geval is in realiteit, komt het er op aan de activiteiten zodanig te verschuiven totdat de hulpmiddelenvereisten de beschikbare hulpmiddelen niet overtreffen. Zodoende wordt een minimale duurtijd van het project bekomen. RCPS houdt dus het rangschikken van projectactiviteiten in, rekening houdend met volgorde- en hulpmiddelenbeperkingen, teneinde het vooraf bepaalde doel te bereiken, wat nogal vaak een zo kort mogelijke projectduur is.
Het klassieke RCPS-probleem is gebaseerd op enkele veronderstellingen (Demeulemeester en Herroelen, 1996): §
Het project bestaat uit meerdere activiteiten die uitgedrukt worden in een knooppuntvoorstelling 6 . Dit is een gerichte, niet cyclische grafiek waarin de activiteiten voorgesteld worden door knooppunten (de zeshoeken) en waarbij de pijlen de symbolische weergave vormen van een volgorderelatie. Er worden twee dummyvariabelen geïntroduceerd, namelijk de begin- en eindactiviteit.
Figuur 1. 7: knooppuntenvoorstelling
§
De activiteiten zijn gerelateerd door een reeks einde-start volgorderelaties met tijdsinterval nul. Een activiteit kan dus pas gestart worden wanneer de voorgaande activiteit volledig beëindigd werd.
§
Er wordt voor geen enkele activiteit een einddatum of vervaldatum vooropgesteld.
§
Elke activiteit heeft een constante duur.
§
Elke activiteit vereist een constante hoeveelheid eenheden hernieuwbare hulpmiddelen.
§
De beschikbaarheid van de hernieuwbare hulpmiddelen is een constante doorheen het project.
6
Dit in tegenstelling tot CPM en PERT die een pijlenvoorstelling hanteren.
Deel I
14
Projectplanning
§
Eens gestart, kan een activiteit niet onderbroken worden.
§
De bedoeling is om het project zo snel mogelijk te beëindigen, zonder de hulpmiddelen- of volgorderelaties te schenden.
Een andere mogelijkheid om netwerken voor te stellen is de pijlenvoorstelling, zoals gebruikt bij PERT en CPM, maar deze methode is echter geen aanrader. Daarbij wordt elke activiteit voorgesteld door een pijl en elke gebeurtenis door een knoop. De volgorderelaties tussen twee activiteiten wordt dan weergegeven door het eindknooppunt van de ene pijl, die de eerste activiteit voorstelt, te laten samenvallen met het beginknooppunt van de pijl die de activiteit voorstelt die pas na afloop van de eerste activiteit kan worden gestart. Het grote nadeel van deze methode is dat men genoodzaakt is om schijnactiviteiten te gaan gebruiken om een juiste voorstelling van het project te bekomen, wat voor een serieuze ballast zorgt bij de netwerkvoorstelling. Als men bovendien van deze schijnactiviteiten een verschillend aantal gebruikt of als men deze een andere plaatsing toekent, kan hetzelfde project op verschillende wijzen worden voorgesteld. De meeste planningspakketten voor projectmanagement zijn daarom ook op de knooppuntenvoorstelling gebaseerd.
Klein (2000) benadrukt dat het klassieke planningsprobleem onder hulpmiddelenbeperkingen (RCPSP) in de praktijk eerder zelden toegepast kan worden om planningsproblemen op te lossen, wat hij aantoont aan de hand van drie voorbeelden:
1. Wanneer geproduceerd wordt op order, is het mogelijk dat een werkstuk op de ene machine moet afgewerkt worden alvorens overgebracht te worden naar de volgende. Dit kan gemodelleerd worden als twee activiteiten met een algemene volgorderelatie. Er ontstaat echter een moeilijkheid wanneer de tweede machine een voorbereidingstijd nodig heeft die onafhankelijk is van de vooruitgang en die de uitvoering van het werkstuk op de eerste machine kan overlappen. Wanneer deze voorbereidingstijd opgenomen wordt in de uitvoeringstijd van de tweede machine terwijl de volgorderelaties behouden blijven, zal dit tot onnodige onbenutte tijd leiden omdat het voorbereidingsproces niet zal starten voor het werkstuk de eerste machine verlaat.
2. Het kan in bepaalde periodes gebeuren dat slechts een deel van alle werknemers of machines beschikbaar zijn. Dit bijvoorbeeld door verlof of onderhoud van machines. De beschikbaarheid van hulpmiddelen is in de praktijk dus zelden of nooit constant doorheen
Deel I
15
Projectplanning
het project. Er dient rekening gehouden te worden met voorspelbare schommelingen. De hulpmiddelenbeperkingen zouden bijgevolg moeten aangepast worden om het RCPSprobleem op te lossen.
3. Het kan nodig zijn een latere datum vast te leggen wanneer de benodigde hulpmiddelen niet onmiddellijk beschikbaar zijn. Bovendien worden ten gevolge van contractuele overeenkomsten ook vaak een vaste datum in de toekomst vooropgesteld voor het uitvoeren van enkele activiteiten. Het is dus mogelijk dat tijdsintervallen bestaan gedurende dewelke activiteiten moeten uitgevoerd worden.
Als gevolg van deze beperkte toepassing van RCPSP, werden de planningsproblemen in de literatuur vaak uitgebreid. Yang en Geunes (2001) geven een overzicht van de verschillende modellen in RCPS. Een onderscheid kan bijvoorbeeld gemaakt worden tussen het enkelvoudige en meervoudige planningsprobleem onder hulpmiddelenbeperkingen. Enkelvoudige problemen veronderstellen dat elk project en elke activiteit slechte één enkele uitvoeringswijze kent. Zowel de duurtijd van de activiteiten en hun hulpmiddelenvereisten worden vast verondersteld. Daarbij bestaan twee soorten volgorderelaties. Gevallen waarbij een activiteit op eender welk moment kan starten na de beëindiging van de voorgaande activiteit en gevallen waarbij een activiteit moet starten binnen een tijdsinterval na de beëindiging van de vorige activiteit. Deze laatste worden de algemene volgorderelaties genoemd. Bovendien kan de hulpmiddelenbeschikbaarheid voor een bepaald hulpmiddel kan dezelfde zijn voor alle periodes of kan variëren. Dit geldt ook voor het hulpmiddelengebruik. Deze laatste kan constant zijn of variëren over de verschillende periodes. Tenslotte kunnen ook gevallen beschouwd worden waarbij de activiteiten moeten volbracht worden eens ze gestart zijn of gevallen waarvoor de activiteiten mogen onderbroken worden. Voor het meervoudige RCPS-probleem zijn meerdere uitvoeringswijzen beschikbaar. Elke realisatiewijze is gekenmerkt door haar uitvoeringstijd en een hoeveelheid van een specifiek hulpmiddelentype om de activiteit uit te voeren. Hulpmiddelen kunnen wel of niet hernieuwbaar zijn. De niet hernieuwbare hulpmiddelen zijn uitgeput na een bepaald aantal periodes, terwijl de hernieuwbare hulpmiddelen steeds een zelfde beschikbaarheid hebben in elke periode.
Yang en Geunes (2001) onderscheiden bovendien RCPS-problemen met reguliere en niet reguliere doelfuncties. In het geval van een reguliere doelfunctie wordt de doelfunctie nooit slechter door de uitvoeringstijd van een taak in te korten zonder deze van een andere taak te verhogen. In het geval van niet reguliere doelfuncties gebeurt dit wel. Tot de specifieke probleemtypes behoren:
Deel I
16
§
het probleem van hulpmiddelennivellering
§
het probleem van maximale netto geactualiseerde waarde
§
het probleem van verdisconteerde kasstroom
Projectplanning
Naast de enkelvoudige, meervoudige en RCPS-problemen met niet reguliere doelfuncties erkennen de eerder vermelde auteurs het stochastische RCPSP. Daarbij is de uitvoeringstijd van elke activiteit een willekeurige variabele die een waarschijnlijkheidsverdeling volgt. Het meest voorkomende doel bij dit probleem is dit keer de ‘verwachte’ projectduur te minimaliseren. Hoewel deze veronderstelling realistischer is, gaat het gepaard met een veel grotere analysecomplexiteit.
Wat betreft de tot nu reeds besproken vormen van RCPS, kunnen projecten of taken kiezen tussen verschillende hulpmiddelen maar slechts één operatie is vereist voor elke job. Een taak in een multi RCPSP daarentegen kan een set van operaties vereisen of een set van opeenvolgende hulpmiddelen (Yang en Geunes, 2001). Zo is het mogelijk dat de hulpmiddelen in serie moeten aangewend worden. Wanneer bepaalde hulpmiddelen echter parallel zijn, dan kan eender welk van deze hulpmiddelen gekozen worden. Deze problemen worden vaak machineplanningsproblemen genoemd gezien in de verwerkende nijverheid machines en werkstations vaak zowel in serie als in parallel opgesteld worden.
Ook Brucker et al. (1999) maakten een overzicht van de verschillende RCPS-problemen en poogden de kloof tussen productieplanning en projectplanning te dichten wat betreft het notatie – en classificatieschema. Zij onderscheiden vier basis RCPS-problemen:
1. PS ¦ prec¦ Cmax: Dit model is het meest klassieke probleem, zoals beschreven door Demeulemeester en Herroelen (1996). Het houdt in dat volgorderelaties en hulpmiddelenbeperkingen moeten in rekening gebracht worden terwijl gepoogd wordt de projectduur minimaal te houden. 2. MPS ¦ temp¦ Cmax: Deze modellen behandelen de inruil tussen tijd en hulpmiddelen en tussen hulpmiddelen onderling in een multiprojectomgeving. Dit weerspiegelt dus meer wat in realiteit gebeurt in project management.
Deel I
17
Projectplanning
3. PS ¦ temp¦ Cmax: Voor veel toepassingen doet zich niet alleen een minimaal tijdsverloop tussen de activiteiten voor maar ook een maximaal start-start tijdsverloop. Dit probleem is sterk NPhard. 4. PS ¦ temp¦ ? ck f (rk (S,t)): Dit model wordt toegepast wanneer de beschikbaarheid van hernieuwbare hulpmiddelen beperkt is en wanneer het hulpmiddelengebruik moet genivelleerd worden doorheen het project. ck staat voor de kost per hulpmiddel k en rk (S,t)) voor de consumptie van hulpmiddel k van plan S op tijdstip t. f (rk (S,t)) bepaalt bijgevolg de doelfunctie.
Om het planningsprobleem onder hulpmiddelenbeperkingen (RCPSP) op te lossen werden in de literatuur zowel exacte procedures als heuristische procedures voorgesteld (Gemmill D.D. en Edwards M.L., 1999). Lineaire en integer programmeren zijn voorbeelden van benaderingen die leiden tot optimale oplossingen. Deze zijn echter niet eenvoudig berekenbaar en vereisen een nogal hoge CPU-tijd, vooral voor grotere projectnetwerken. Farrington et al (1999) stellen dat, zelfs wanneer optimalisatie initieel haalbaar zou zijn, deze methodes toch nog het nadeel hebben zich als een zwarte doos te gedragen. Wanneer immers verandering zou optreden in het project, zou het probleem moeten geherformuleerd worden en een nieuwe optimale oplossing gezocht worden. Gezien verandering eigen is aan projectplanning en gezien de lange berekeningstijden wordt in de praktijk gebruik gemaakt van heuristische beslissingsregels. Deze hebben het voordeel eenvoudig begrijpbaar en aanwendbaar te zijn en goedkoop om te gebruiken in computer programma’s. Heuristieken leveren echter wel een variërende doelmatigheid wanneer ze gebruikt worden in verschillende netwerken. Bovendien is het aantal heuristieken, waaruit een keuze moet gemaakt worden, enorm groot.
3.1. Optimalisatie
Een optimaal projectplan bekomen zou vanzelfsprekend de beste oplossing zijn voor de projectmanager. Wiskundig programmeren is een techniek waarbij gezocht wordt naar de enige optimale uitkomst. East et al. (1993) beschrijven twee methodes, namelijk lineair programmeren en integer programmeren.
Deel I
18
Projectplanning
3.1.1. Lineair programmeren
Lineair programmeren is een wiskundige beslissingstechniek waarbij het probleem voorgesteld wordt als een stelsel van drie vergelijkingen of ongelijkheden, die lineaire combinaties zijn van de beslissingsvariabelen. Een eerste vergelijking beschrijft het gedrag van het systeem. Daarbij dient een set beslissingsvariabelen gedefinieerd te worden die ingezet zullen worden om de mogelijke oplossingen te beschouwen. De beperkingen vormen de tweede vergelijking. Deze zijn nodig om de beslissingsvariabelen te beperken tot waarden die realistisch zijn voor een specifiek probleem. Een laatste vergelijkingstype is de doelfunctie. Deze bepalen de kost die gepaard gaat met de beslissingsvariabelen en de richting van het doel, minimalisatie of maximalisatie. Lineaire programmeringsmodellen weerspiegelen echter zelden de ware problemen waarmee een projectmanager geconfronteerd wordt. Toepassingen van lineair programmeren zijn vooral terug te vinden in het domein van weg- en waterbouwkunde. Voor bouwkunde wordt lineair programmeren het vaakst toegepast om tegemoet te komen aan het tijd-kost inruil probleem.
3.1.2. Integer ‘programming’
Wanneer beslissingsvariabelen geen onderling verband vertonen, wordt vaak integer programmeren geprefereerd. Deze methode kan gebruikt worden voor meerdere planningsproblemen, zoals hulpmiddelenallocatie, hulpmiddelennivellering en het tijd-kost inruil probleem. Er bestaan echter enkele problemen bij het modelleren van problemen met behulp van integer programmeren. De gebruikte modellen zijn statisch. Ze werden ontwikkeld om een complete oplossing te vinden voor een volledige set van beperkingen. Wanneer deze modellen dus veranderd worden, kan dit leiden tot een continue herziening van het model zonder ooit echt in gebruik genomen te worden. Een tweede probleem is de moeilijkheid om conflicterende doelen, bijvoorbeeld het tegelijk nastreven van minimalisatie van hulpmiddelengebruik en kost, voor te stellen. Het model zal schending van enkele beperkingen, zodat de globale oplossing beter wordt, niet toestaan. Een andere tekortkoming van deze techniek is dat het stelsel van vergelijkingen convex moet zijn. Daardoor kunnen vergelijkingen die als stapfuncties of waardefuncties moeten gemodelleerd worden moeilijk omgezet worden in integer programmeringsformuleringen.
Een methode om integer programmeren op te lossen en die optimaliteit garandeert is de zoektechniek, meer bekend als Branch&Bound. Deze methode vertrekt van deelplannen die
Deel I
19
Projectplanning
geassocieerd zijn met de top van de enumeratie boomdiagram (Brucker et al., 1999). Het vertakkingproces bestaat uit het uitbreiden van het deelplan op verschillende manieren. Dominantieregels, ondergrenzen en directe selectie laten toe het aantal alternatieven tot deze uitbreiding te verlagen. De Branch&Bound procedure van Demeulemeester en Herroelen (1992) wordt tot op heden als de meest performante beschouwd. In het slechtste geval kan voor het bekomen van een optimale oplossing aan de hand van de Branch&Bound-procedure een evaluatie nodig zijn van alle combinaties van beslissingsvariabelen. Het oplossen van zo’n probleem vereist exponentieel meer tijd dan het aantal beperkingtoenames. Zo’n type probleem wordt ook wel een NP-probleem genoemd.
3.2. Heuristieken
Tijdens het plannen komt het er op aan behoorlijk snel activiteiten te plannen en hulpmiddelen toe te wijzen aan de specifieke activiteiten. Aangezien integer programmeringmodellen niet in staat zijn om optimale resultaten te leveren voor de ware praktijkproblemen, zijn vele onderzoekers overgegaan tot het formuleren van vuistregels of heuristieken om prioriteit toe te kennen aan activiteiten wanneer deze gekenmerkt worden door hulpmiddelenbeperkingen. Het zou dus uiterst nuttig zijn de heuristieken te kennen die leiden tot een minimale duurtijd van het project en een maximale benutting van de hulpmiddelen.
Een onderscheid dient gemaakt te worden tussen prioriteitsgebaseerde heuristieken en metaheuristieken. De meta-heuristieken kunnen gezien worden als een algemene strategie om heuristieken te leiden zodat betere oplossingen kunnen gevonden worden dan de lokale optimale oplossingen.
3.2.1. Meta-heuristieken
De drie belangrijkste meta-heuristieken worden hieronder besproken. Het betreft de genetische algoritmes, ‘tabu search’ en ‘simulated annealing’.
Deel I
20
Projectplanning
3.2.1.1. Genetische algoritmes
De genetische algoritmes splitsen een probleem op in strengen waaruit nieuwe potentiële oplossingen worden ontwikkeld. Deze benadering levert een groot aantal mogelijke alternatieve oplossingen die allen getest worden op hun bekwaamheid. Aan de hand van een iteratieprocedure worden aan die oplossingen die beter presteren een hogere frequentie toegekend. Er wordt gebruik gemaakt van gespecialiseerde operatoren om de bestaande alternatieven te permuteren zodat de oplossingen niet beperkt blijven tot de initiële set alternatieven (East et al., 1993). Sommige auteurs zijn van mening dat deze genetische algoritmes minder belastend zijn qua berekening voor het zoeken van NP-complete oplossingsmogelijkheden. Een ander erkend voordeel is dat systemen die deze evolutionaire benadering toepassen verandering van de systeemparameters of toevoeging van nieuwe parameters schijnen te aanvaarden zonder dat de globale prestaties van de genetische algoritmes verlagen.
3.2.1.2. Tabu Search
Deze methode is eigenlijk een uitbreiding van de gebruikelijke lokale zoekmethodes. Deze laatste worden toegepast om een initiële oplossing te verbeteren7 . Dit gebeurt aan de hand van opeenvolgende bewerkingen die een oplossing omzetten in een andere. Terwijl de traditionele lokale zoekmethodes enkel toelaten naar een betere oplossing te evolueren, vermijden de meer gesofisticeerde methodes vast te lopen in een lokaal optimum door intermediaire achteruitgang toe te laten. De methode tabu search vermijdt in een cyclische spiraal terecht te komen door enkele ontwikkelingen te verbieden, steunend op informatie over de zoekgeschiedenis. Voor een uitgebreid overzicht rond Tabu search verwijs ik graag naar Klein (2000).
3.2.1.3. Simulated annealing
Simulated annealing, of letterlijk “stochastisch koelen”, is eveneens een methode om tot een suboptimale oplossing van een probleem te komen. Kirkpatrick et al. (1983) onderzochten dit probleem aan de hand van het handelsreizigersprobleem (‘TSP: travelling salesman problem’). Dit probleem stelt dat de reiziger de kortste weg moet zien te vinden om een aantal steden te bezoeken en uiteindelijk terug op de initiële plaats terecht te komen.
Deel I
21
Projectplanning
Simulated annealing is een Monte Carlo berekening die een globaal minimaliserend algoritme implementeert dat werkt voor willekeurige functies (Kirkpatrick et al., 1983). Simpele minimaliserende algoritmes vinden enkel lokale minima. Simulated annealing daarentegen kan zo’n lokaal minimum verlaten. Dit gebeurt echter met een dalende probabiliteit. Deze procedure is analoog aan de processen in de natuur. Het komt er op aan het minimum op langzame wijze te bereiken. De stochastische koeling moet dus in kleine stapjes plaatsvinden.
3.2.2. Op prioriteitsregel(s) gebaseerde heuristieken
De meest voorkomende heuristische benadering voor RCPS is het gebruik van prioriteitsregels. De op prioriteitsregel gebaseerde methodes bestaan uit twee componenten, namelijk één of meerdere planningsschema’s en één of meerdere prioriteitsregels (Schirmer, 1998).
3.2.2.1. Serie en parallel plannen
Er bestaan twee varianten van het planningsschema, namelijk seriële en parallelle schema’s. Een planningsschema bepaalt hoe een plan wordt opgebouwd. Door deelplannen, die enkel een deel van de activiteiten beslaan, stapsgewijze te verhogen, wordt een mogelijk volledig plan bekomen, die alle activiteiten bevatten (Hartmann en Kolisch, 2000). Tijdens elke fase bepaalt het plan de set van activiteiten die in aanmerking komen om gepland te worden. De prioriteitsregels dienen dan om voorrang te verlenen aan een bepaalde activiteit wanneer meerdere tegelijkertijd klaar zijn om gepland te worden. De
seriemethode
rangschikt
activiteiten
om
gepland
te
worden
alvorens
de
hulpmiddelenbeperkingen in rekening te nemen. De activiteiten worden zodanig genummerd dat geen enkele activiteit een lager nummer krijgt dan één van de voorgaande. Vervolgens wordt het plan opgemaakt door de activiteiten in volgorde te beschouwen en hen één voor één te plannen voor de vroegste mogelijke uitvoering, rekening houdend met de beperkingen. Het serieel planningsschema verdeelt de activiteiten in drie disjuncte klasses: gepland, geschikt en niet geschikt. Een activiteit die zich reeds in het deelplan bevindt, is gepland. Een activiteit waarvan al zijn voorgangers gepland zijn, komt in aanmerking om gepland te worden (geschikt). Tijdens elke fase wordt een activiteit geselecteerd, gebruik makend van een prioriteitsregel als meer dan één activiteit geschikt is, en gepland voor de vroegst mogelijke starttijd. In de volgende fase worden 7
Bijvoorbeeld een oplossing die reeds bekomen werd met behulp van een prioriteitsregel.
Deel I
22
Projectplanning
sommige eerder niet geschikte activiteiten nu geschikt gezien al hun voorgangers gepland zijn. Het schema eindigt met de laatste fase wanneer alle activiteiten gepland zijn.
Figuur 1. 8: serie planningsschema
Figuur 1. 9: parallel planningsschema
(Bron: East et al., 1993)
In tegenstelling tot de seriële methode, zal de parallelle methode de set activiteiten herordenen wanneer de hulpmiddelenbeperkingen geëvalueerd werden. Het parallel planningsschema deelt de activiteiten in vier disjuncte classes in: actief, beëindigd, geschikt en niet geschikt. Een geplande activiteit is actief tijdens zijn uitvoering, daarna wordt die ‘beëindigd’. In tegenstelling tot het seriële schema, wordt een activiteit wanneer het noch actief is, noch beëindigd werd, geschikt genoemd als het kan gepland worden rekening houdend met de volgorderelaties EN hulpmiddelenbeperkingen. Is dit niet het geval dan worden ze niet geschikt genoemd. Het deelplan bestaat dus uit alle actieve en beëindigde activiteiten. Geschikte activiteiten worden geselecteerd, gebruik makend van een prioriteitsregel wanneer meerdere geschikt zijn, en worden gepland. Wanneer geen activiteiten meer geschikt zijn, wordt de planningstijd verhoogd. De verhoogde planningstijd wordt ingesteld op het minimum van de eindtijd van alle activiteiten. Door deze aanpassing worden activiteiten geschikt die dit voordien niet waren. Het schema stopt wanneer elke activiteit gepland werd, i.e. ofwel actief is, ofwel beëindigd werd.
Deel I
23
Projectplanning
Zowel Kolisch (1996) als Klein (2000) kwamen tot de conclusie dat gemiddeld genomen het parallelle planningsschema tot betere resultaten leidt dan het seriële planningsschema. Klein (2000) onderzocht de prestaties van verschillende combinaties van planningsschema’s en prioriteitsregels. Zo kwam hij tot de bevestiging van wat Kolisch (1996) reeds stelde: het parallel planningsschema presteert, algemeen beschouwd, beter dan het seriële. Wanneer eenzelfde prioriteitsregel gebruikt wordt, presteert de parallelle methode steeds beter wat betreft gemiddelde afwijking. Dit geldt evenzeer voor de maximale afwijking, met uitzondering van de prioriteitsregel ‘vroegste starttijd’, wat blijkt uit onderstaande tabel:
Serieel planningsschema Prioriteitsregel
gem.
max.
afw.
afw.
meest totale opvolgers
15.33
46.00
20
11.66
32.26
19
grootste rangplaats gewicht
14.17
54.26
19
11.60
30.33
19
vroegste starttijd
19.31
46.88
7
16.11
49.23
11
vroegste eindtijd
22.59
60.87
2
16.82
49.23
6
dynamische vroegste starttijd
18.65
53.85
10
14.90
49.23
14
dynamische vroegste eindtijd
21.09
56.10
5
18.91
56.92
5
laatste starttijd
14.39
39.82
19
11.70
32.31
14
laatste eindtijd
14.94
44.05
36
11.31
30.12
28
minimale spelingruimte
21.73
59.15
15
16.13
46.43
14
dynamische min. Spelingruimte
22.36
59.15
14
11.70
32.31
14
grootste hulpmiddelenvraag
21.92
53.75
4
18.15
46.84
6
slechtste geval laatste starttijd
12.65
33.72
22
-
-
-
slechtste geval spelingruimte
-
-
-
10.93
30.12
25
24.82
61.29
2
18.76
51.32
4
willekeurig
# opt.
Parallel planningsschema gem. afw
max.
# opt.
afw.
Figuur 1. 10: combinaties planningsschema’s en prioriteitsregels (Bron: Klein, 2000)
Uit de tabel kan afgeleid worden dat de seriële methode enkel qua aantal optimale oplossingen erin slaag om de parallelle methode te evenaren of zelfs te overstijgen. Dit wijst er op dat het seriële
Deel I
24
Projectplanning
planningsschema oplossingen levert die ofwel zeer goed zijn, ofwel behoorlijk slecht. Het parallelle planningsschema daarentegen levert oplossingen met slechts kleine afwijkingen. De twee prioriteitsregels die ontworpen zijn voor een specifiek planningsschema, namelijk ‘slechtste geval spelingruimte’ en ‘slechtste geval laatste starttijd’ scoren best wat betreft gemiddelde en maximale relatieve afwijking. De prioriteitsregel ‘laatste eindtijd’ behaalde echter het maximaal aantal optimale oplossingen, om het even welk planningsschema toegepast werd.
3.2.2.2. Prioriteitsregels
Bij het toewijzen van hulpmiddelen in netwerken zal men dus de activiteiten rangschikken volgens één of meerdere prioriteitsregels. Traditioneel worden tijdsgebaseerde prioriteitsregels gebruikt. Daarna wordt een simulatieproces toegepast om de hulpmiddelen toe te wijzen en de activiteiten te plannen. De activiteit met de hoogste prioriteit komt als eerste in aanmerking voor hulpmiddelenallocatie. Als de vraag naar hulpmiddelen van de activiteit met de hoogste prioriteit de beschikbare hulpmiddelen overtreft, moet deze activiteit en al deze met een lagere prioriteit wachten om gepland te worden.
Kolisch (1996) geeft drie redenen aan voor de nood aan goed presterende prioriteitsregels. Een eerste is dat ze de kern vormen van nieuwe, efficiënte heuristieken die gebaseerd zijn op de lokale zoekmethode. Kolisch bewees in 1995 al dat de prestaties van steekproefgebaseerde heuristieken afhankelijk zijn van de deugdzaamheid van de gekozen prioriteitsregels. Een tweede reden waarom goed presterende prioriteitsregels van belang zijn, is het gebruik ervan in de commerciële projectmanagement softwarepakketten om snel projectplannen op te stellen, rekening houdend met de eventuele beperkingen. Bovendien zijn de prestaties van de prioriteitsregels van groot belang omdat ze dienen ingezet te worden wanneer grote problemen met meer dan duizend activiteiten snel moeten opgelost worden.
Alle
commerciële
softwarepakketten
wijzen
hulpmiddelen
toe
met
behulp
van
een
oplossingsmethodologie gebaseerd op prioriteitsregels (Kolish, 1999). Tot op heden is men er nog niet in geslaagd om op een objectieve manier een passende heuristiek te selecteren om hulpmiddelenbeperkte projecten in te delen en er bestaan geen echte richtlijnen bij het selecteren van de beste prioriteitsregel voor een gegeven netwerk (Hegazy, 1999). Het komt er dus op neer dat de gebruiker van de projectmanagement softwarepakketten zelf de gepaste prioriteitsregel moet gaan selecteren. Een uitvoerige beschrijving van deze regels ontbreekt echter nogal vaak in de
Deel I
25
Projectplanning
handleiding van deze pakketten (De Wit en Herroelen, 1990). Veelal kan een meervoudig prioriteitsbeleid geïmplementeerd worden, wat het selectieproces moeilijk en verscheiden maakt (Khamooshi 1996).
Davis en Patterson (1975) waren de eersten die de doeltreffendheid van prioriteitsregels vergeleken met een optimale oplossing. Hun experiment bestond erin 83 problemen op te lossen, eerst met de exacte procedure ‘bindende enumeratie 8 ’, vervolgens met acht verschillende prioriteitsregels. Voor de testproblemen werden 57 verschillende computergegenereerde netwerken gebruikt. De acht geteste prioriteitsregels worden hieronder beschreven:
§
Minimale speling van de activiteit (MINSLK) Deze wordt berekend als het verschil tussen de late start tijd (LST) en de vroege start tijd (EST), beide bepaald door CPM.
§
Hulpmiddelenplanningsmethode (RSM) Dit is de minimale waarde van de stijging van de projectduur tengevolge van twee opeenvolgende activiteiten.
§
Minimale late eindtijd (LFT)
§
Grootste hulpmiddelenvraag (GRD) Deze regel wijst prioriteit toe aan activiteiten op basis van de totale vereiste aan hulpmiddelen voor alle types, met een hogere prioriteit voor grotere hulpmiddelenvraag.
§
Grootste hulpmiddelengebruik (GRU) Prioriteit wordt gegeven aan die combinatie van activiteiten die resulteert in een maximaal hulpmiddelengebruik voor elke planningsinterval.
§
Grootst aantal mogelijke activiteiten (MJP) Prioriteit komt toe aan die combinatie activiteiten die resulteert in het grootste aantal activiteiten gepland in om het even welk interval.
§
Activiteiten willekeurig selecteren (RAN) Concurrerende activiteiten worden prioriteit toegewezen op volkomen willekeurige basis.
8
Voor een beschrijving van deze procedure verwijs ik graag naar Davis E.W. en Heidorn G.E (1971)
Deel I
26
Projectplanning
Alle 83 testproblemen werden optimaal opgelost met de exacte procedure en tien ervan hadden een optimale oplossing wanneer de prioriteitsregels gebruikt werden. De optimale duur, bekomen door de bindende enumeratieprocedure, werd verder als basis genomen voor de vergelijking met de bekomen duur ten gevolge van de prioriteitsregels.
Prioriteitsregels MINSLK
RSM
LFT
RAN
GRU
GRD
SIO
MJP
5.6
6.8
6.7
11.4
13.1
13.1
15.3
16.0
Aantal problemen waarvoor optimale oplossing gevonden 24
12
17
4
2
11
1
2
Gemiddelde procentuele stijging boven het optimum
Figuur 1. 11: vergelijking tussen optimale en heuristische oplossingen voor RCPSP (Bron: Davis en Patterson, 1975)
MINSLK, RSM en LFT leveren globaal genomen betere resultaten dan de andere vijf prioriteitsregels. Ze kennen elk een aanzienlijk lagere stijging boven het gevonden optimum. Bovendien kwamen David en Patterson tot de conclusie dat RSM de laagste standaardafwijking leverde. Wanneer de vijf minder performante prioriteitsregels beschouwd worden, dan valt op dat de prioriteitsregel die activiteiten willekeurig selecteert (RAN) doorgaans beter scoort dan de andere vier. Davis en Patterson geloven echter wel, ook al werd dit niet onderzocht in hun artikel, dat een ervaren projectplanner een betere procedure zou kunnen bekomen dan diegene die activiteiten willekeurig selecteert. Hun experiment toont wel duidelijk aan dat de laatste vier prioriteitsregels (GRU, GRD, SIO, MJP) slechts povere resultaten levert wat betreft het minimaliseren van de projectduur met meerdere hulpmiddelenproblemen. Het onderzoek van Davis en Patterson laat ook toe de verschillende prioriteitsregels onderling te vergelijken (zie figuur 1.12). De prioriteitsregel MINSLK bereikte het meest een kortste (unieke) duurtijd en het minst een (unieke) langste. De prioriteitsregels LFT en RSM volgen deze best presterende heuristiek. De resultaten uit hun onderzoek ondersteunen de eerdere observatie dat elke heuristiek variërende resultaten kan opleveren en illustreren het voordeel om bepaalde problemen op te lossen aan de hand van meer dan één heuristiek wanneer minimalisatie van de projectduur van groot belang is en wanneer berekening van het optimum onmogelijk is. Davis en Patterson wijzen bovendien op het feit dat de prestaties van heuristieken afhankelijk zijn van project- en hulpmiddelenkarakteristieken. Zo werd bijvoorbeeld gevonden dat de prestaties van
Deel I
27
Projectplanning
heuristieken in het algemeen lager zijn voor deze problemen met een hoge ratio gemiddelde hulpmiddelenvereiste per activiteit tot de beschikbare hoeveelheid. De MINSLK regel blijkt meer beïnvloed te zijn door deze ratio dan de overige prioriteitsregels. Andere regels presteren dan weer beter voor deze problemen waarvoor de gemiddelde slack ratio 9 laag is. Omgekeerd, bekomt de GRD prioriteitsregel zijn beste prestatie wanneer deze factor hoog is.
Prioriteitsregels MINSLK
RSM
LFT
RAN
GRU
GRD
SIO
MJP
50
38
28
15
13
6
4
3
Aantal maal unieke kortste duurtijd bereikt
15
5
5
4
5
0
1
1
Aantal maal langste duurtijd bereikt
2
4
2
20
14
14
30
33
Aantal maal unieke langste duurtijd bereikt
1
0
2
11
8
1
14
18
Aantal maal kortste duurtijd van plan bereikt
Figuur 1. 12: relatieve prestatie van acht prioriteitsregels (Bron: David en Patterson, 1975)
Khamooshi (1996) stelde een heuristische procedure voor waarbij men niet verplicht is één enkel beleid te volgen gedurende de projectlevenscyclus. De dynamische prioriteitsplanningsmethode (‘dynamic priority scheduling method of DPSM’) stelt dat het project in een aantal secties kan onderverdeeld worden. Telkens wordt voor elke sectie de meest geschikte prioriteitsregels toegepast. Dit onderzoek is een poging om de kloof te dichten tussen theorie en praktijk omdat men zich dan de vraag niet meer hoeft te stellen welke prioriteitsregel te gebruiken voor welk projectdeel. Uit zijn onderzoek blijkt dat DPSM beter presteert dan de traditionele prioriteitsregels. Hierbij moet echter wel opgemerkt worden dat geen rekening gehouden wordt met enige interactie tussen de verschillende secties en deze methode aldus niet vanzelfsprekend leidt tot een optimalisatie van het gehele systeem.
McCray et al. (2002) waarschuwen voor de mogelijke negatieve impact van het gebruik van niet gekende heuristieken. Deze zouden immers het beslissingsproces binnen het project enorm kunnen beïnvloeden. Deze vertekeningen anticiperen en neutraliseren zou volgens hen enorme voordelen kunnen opleveren, zoals:
9
Ratio van gemiddelde totale slack per activiteit tot de lengte van het kritieke pad
Deel I
28
Projectplanning
§
minder over- of onderschatting van de benodigde hulpmiddelen voor een gegeven project
§
een verbeterde allocatie van hulpmiddelen doorheen meerdere projecten
§
verbeterde identificatie van doeltreffende en niet doeltreffende projectmanagement technieken
§
betere mentale veerkracht binnen de projectteams
§
een meer stabiele projectomgeving, wat tot een kwaliteitsvoller resultaat zal leiden
Zij wezen er bovendien op dat het gebruik van heuristieken wel bijzonder duidelijk mag zijn in de initiatie- en planningsfase van het project, maar dat de positieve invloed van heuristieken tijdens de uitvoerings-, controle en eindfase niet mag verwaarloosd worden.
Deel I
29
Projectplanning
4. Hulpmiddelennivellering
We spreken van hulpmiddelenallocatie en RCPS wanneer beperkingen optreden in de beschikbaarheid van hulpmiddelen. In dit geval worden zowel de kritische als niet-kritische activiteiten verschoven. Daarbij wordt gestreefd naar een zo laag mogelijke stijging van de projectduur boven de oorspronkelijke duur berekend door middel van de kritieke pad methode, die uitgaat van onbeperkte hulpmiddelen. Wanneer onvoldoende hulpmiddelen beschikbaar zijn, moet de activiteit opnieuw gepland worden zodanig dat de benodigde hulpmiddelen kunnen vrijkomen. Wanneer twee activiteiten tegelijkertijd dezelfde hulpmiddelen vereisen en die zijn onvoldoende aanwezig, dan zal de activiteit met de hoogste prioriteit voorrang krijgen. Naast dit probleem ten gevolge van een te beperkte beschikbaarheid van hulpmiddelen kent de projectmanager nog een ander probleem, namelijk het reduceren van schommelingen in hulpmiddelengebruik doorheen het project. Dit probleem wordt hulpmiddelennivellering genoemd.
Hulpmiddelennivellering10 wordt dus toegepast wanneer voldoende hulpmiddelen voorhanden zijn maar wanneer de schommelingen in hulpmiddelengebruik afgevlakt moeten worden. Er wordt geen limiet gelegd op het hulpmiddelengebruik, wel op de projectduur (De Reyck en Herroelen, 1999). Tijdens dit proces worden de niet kritieke activiteiten verschoven binnen hun ‘float’. Dit laatste betreft de speelruimte waarbinnen de activiteit kan verschoven worden zonder dat de totale projectduur aangetast wordt. Deze procedure maakt het mogelijk dat werknemers beginnen aan een taak, deze afwerken en vervolgens overgaan tot een nieuwe taak (East et al., 1993). Het hoofddoel van hulpmiddelennivellering is dus de variatie hulpmiddelengebruik, wat vaak nogal kostelijk is, te beperken. Het spreekt voor zich dat gedurende een project een werknemer niet zomaar kan aangenomen, afgedankt en terug aangenomen worden wanneer dat het beste uitkomt voor de uitvoering van het project. Het resultaat van dit proces is dat de geplande starttijd van vele activiteiten samenvalt met hun late eindtijden, wat nogal vaak de totale projectduur verhoogt.
Yang en Geunes (2001) stelden dit probleem mathematisch voor. Veronderstel een set K hulpmiddelen. Ck staat voor de kost per eenheid van hulpmiddel k en Rk (S,t) voor het totaal gebruik van hulpmiddel k op tijdstip t onder een bepaald plan S. De doelfunctie kan dan volgens hen geschreven worden als:
10
Meer bekend onder de Engelstalige naam ‘Resource levelling’.
Deel I
30
Projectplanning
Minimize ? Ck f (R (S,t) ) k∈K
Neumann en Zimmermann (1999) stellen dat men, behalve met hulpmiddelenbeperkingen, ook rekening moet houden met maximale en minimale tijdsvertragingen en een vooropgestelde, maximale projectduur wanneer hulpmiddelen genivelleerd worden. Zij stellen dat het maximaal tijdsverloop in het bijzonder enorm belangrijk is in de praktijk. Ze worden immers ingesteld om praktische eisen te modelleren, zoals deadlines voor deelprojecten of individuele activiteiten, gelijktijdige of niet vertraagde uitvoering van meerdere activiteiten, gedeeltelijke of volledige overlapping
van
activiteiten,
tijdvariërende
hulpmiddelenvereistes,
tijdsintervallen
voor
hulpmiddelen en plannen van productie op order.
De meeste projectmanagement softwarepakketten gaan om met hulpmiddelplanning en -nivellering op een simplistische manier. Vaak steunen ze op nogal onduidelijke heuristieken, waarvan de details meestal niet voldoende uitgelegd werden in de handleiding (De wit, Herroelen, 1990). Bovendien worden beide problemen, RCPSP en hulpmiddelennivellering, vaak met één en dezelfde term ‘levelling’ aangeduid (De Reyck en Herroelen, 1999).
Neumann en Zimmermann (1999) stelden polynome heuristische procedures voor om verschillende types problemen van hulpmiddelennivellering op te lossen voor projecten met minimaal en maximaal tijdsverloop tussen de activiteiten. Dit werd gedaan voor problemen zowel met als zonder hulpmiddelenbeperkingen. Tot de publicatie van hun onderzoek werden nog geen exacte of heuristische
procedures
hulpmiddelenbeperkingen.
voor Zij
hulpmiddelennivellering stelden
zelfs
dat
alle
voorgesteld bestaande
die
uitgaan
heuristieken
van voor
hulpmiddelennivellering enkel pseudopolynome algoritmes betreffen. Ze gebruikten de netwerkgenerator ProGen/Max (Schwindt, 1996) en genereerden zo enkele duizenden probleeminstanties voor 500 activiteiten en vijf hulpmiddelen. Hun onderzoek toonde aan dat hun heuristieken goed presteren om een grote variëteit moeilijke nivelleringproblemen op te lossen.
East et al. (1993) stellen dat de heuristiek van het minimale moment misschien wel de voornaamste is voor hulpmiddelennivellering. Deze heuristiek is gebaseerd op de evaluatie van het hulpmiddelenhistogram, waarvan de vertikale as het aantal vereiste hulpmiddelen per werkperiode weergeeft en de horizontale as de werkperiodes. Deze heuristiek zal hulpmiddelen toewijzen aan activiteiten zodanig dat een minimale schommeling in hulpmiddelengebruik voorkomt. De gewenste vorm van een volledig genivelleerd plan is een rechthoek. Groepen activiteiten worden
Deel I
31
Projectplanning
geëvalueerd, lang verschillende paden, om te bepalen hoe de veranderingen in geplande starttijden de vorm van het hulpmiddelenhistogram zullen beïnvloeden. Deze vormverandering wordt gekwantificeerd in een verbeteringsfactor en de activiteit met het grootste verbeteringspotentieel wordt verschoven binnen haar spelingruimte. De heuristiek van het minimale moment zal, in tegenstelling tot de meeste heuristieken voor hulpmiddelennivellering, activiteiten evalueren beginnend van het einde van het plan tot het begin. Eens dit gebeurd is, worden de activiteiten opnieuw geëvalueerd, ditmaal beginnend van de start van de activiteiten.
Deel I
32
Projectplanning
5. Primavera vs. andere projectmanagement software Wegens de lage efficiëntie en de vele moeilijkheden om veelsoortige systemen te managen, hebben vele bedrijven in het verleden beroep gedaan op ERP-systemen11 om de traditionele ‘back office’ functies volledig te automatiseren en integreren. Dit leidde ertoe dat deze bedrijven terug op gelijke voet geraakten met de concurrenten, maar maakte het niet mogelijk hun proces te analyseren of te verbeteren. Vandaar de nood aan een systeem om een project te plannen, analyseren, ontwerpen, implementeren en onderhouden.
Bedoeling hier is een overzicht te geven van de belangrijkste softwarepakketten voor projectmanagement en de onderlinge verschillen tussen deze pakketten te bespreken. Na deze vergelijkende studie zou moeten duidelijk worden waarom Primavera gekozen werd om het onderzoek van deze thesis te ondersteunen.
5.1. Indeling projectmanagement software
De Reyck en Herroelen (1999) maakten een onderscheid in de verschillende soorten projectmanagement software. De eenvoudige planningspakketten (‘low-end’) zijn vooral gericht op tijdsplanning. Ze bieden dan ook de mogelijkheid het project voor te stellen door middel van een Gantt-kaart. Voorbeelden van dergelijke pakketten zijn FastTrackSchedule (AEC Software Inc.) en Plan & Track en MacSchedule (Mainstay). De totale kostprijs van zo’n pakket bedraagt maximaal 500 euro.
Planningspakketten met uitgebreide functionaliteit (‘middle-end’) laten zowel tijd- als hulpmiddelenplanning toe. Daarom worden naast Gannt-kaarten en projectnetwerken eveneens hulpmiddelenhistogrammen (figuur 1.13) aangeboden, waardoor hulpmiddelenconflicten zichtbaar worden. Deze laatste kunnen interactief opgelost worden of men kan beroep doen op de heuristieken die standaard in de pakketten vervat zitten. In het voorbeeld in figuur 1.13 blijkt duidelijk dat voor de simultane uitvoering van activiteiten 4,5 en 6 meer hulpmiddelen nodig zijn dan er beschikbaar zijn. Om dit hulpmiddelenconflict op te lossen kunnen bepaalde activiteiten uitgesteld worden. Dit kan echter wel de projectduur verhogen.
11
Enterprise Resource Planning
Deel I
33
Projectplanning
Figuur 1. 13: hulpmiddelenhistogram (Bron: Business Logistics, 04/1999, p. 23)
Deze ‘middle-end pakketten’ zijn autonome pakketten waarvan de totale kostprijs schommelt tussen 500 en 2500 euro. Aanvullende functionaliteiten, zoals work breakdown structuur of WBS, risicoanalyse, links met spreadsheet programma’s en simulatiemogelijkheden zijn mogelijk binnen deze klasse projectmanagement software. Het gebruik van deze pakketten blijft vrij eenvoudig, maar vereist toch een korte opleiding. Voorbeelden van dergelijke pakketten zijn Harvard Project Manager (Software Publishing Corp.), MacProject Pro (Claris Corp.), Microsoft Project (Microsoft Corp.), Panorama (SQL Systems), Project Manager Workbench (Cap Volmac), Project Scheduler (Scitor Corp.), SuperProject (Computer Associates), SureTrack (Primavera Systems), Texim Project (Welcome Software Technology) en Timeline (Symantec).
De geïntegreerde administratie- en planningspakketten (‘high-end’) maken, naast tijd- en hulpmiddelenanalyse, een koppeling mogelijk met MRPI12 -systemen, MRPII13 -systemen, ERP14 systemen en databasesystemen. Met behulp van deze pakketten kunnen verschillende simultane projecten gelijktijdig worden gepland (multi-project). Dit soort software wordt meestal gebruikt in een netwerkomgeving en dienen dus voor meerdere gebruikers (multi-user). Het gebruik van dergelijke pakketten is behoorlijk ingewikkeld en vereist een grondige opleiding. De totale kostprijs van zo’n pakket schommelt tussen de 2 500 en 10 000 euro. Enkele voorbeelden zijn 12 13
Materials Requirement Planning Manufacturing Resources Planning
Deel I
34
Projectplanning
Artemis (Lucas Management Systems), Intelligent Planner (Planview Inc.) en Primavera Project Planner (Primavera systems). soort software
beschrijving
kostprijs
‘Low-end’
tijdplanning
max. 500 €
‘Middle-end’
Tijd- en hulpmiddelenplanning
tussen 500 en 2500 €
tijd- en hulpmiddelenplanning ‘High-end’
+ koppeling met MRP-en
tussen 2500 en 10 000 €
databasesystemen.
Figuur 1. 14: types projectmanagement softwarepakketten
Projectmanagement softwarepakketten stellen de structuur van het project op een geaggregeerd niveau voor als een ‘work breakdown’ structuur (WBS) en op een meer gedetailleerd niveau als een knooppuntenvoorstelling (Kolisch, 1999). Een work breakdown structuur wordt in de PMBOK15 (2000) gedefinieerd als “een geörienteerde groepering van projectelementen die het volledig bereik van een project definiëren en organiseren”. Daarbij worden de hoofdtaken of deelprojecten verder opgedeeld in werkpakketten, waaraan specifieke doelstellingen worden toegekend in termen van tijd, kosten en kwaliteit. Deze werkpakketten worden dan nogmaals verder opgesplitst tot activiteiten. Op dit niveau zal men de volgorderelaties, de vereiste hulpmiddelen, de werkmethode en de activiteitsduur bepalen.
5.2. Vergelijkende studie
Er bestaan slechts weinig publicaties omtrent de beoordeling van commerciële projectmanagement softwarepakketten. Deze betreffen meestal algemene evaluaties en in meer recentere jaren evaluaties van mogelijkheden tot hulpmiddelenallocatie. De Wit en Herroelen (1990) stelden dat vele van deze software-evaluaties vooral lange opsommingen zijn van technische gegevens en kostprijs. Ze bestempelden deze besprekingen bovendien als onkritisch, zelf overenthousiast.
14
Enterprise Resources Planning ‘Project Management Body Of Knowledge’: bevat algemeen aanvaarde definities en beschrijvingen van termen gebruikt in projectmanagement. 15
Deel I
35
Projectplanning
De Wit en Herroelen (1990) maakten een grondige evaluatie de tien bekendste commerciële softwarepakketten uit die tijd. Bedoeling was eigenlijk om de leden van het ‘Belgian Building Research Institute’ of BBRI te voorzien van technische en praktische richtlijnen bij het selecteren van een projectmanagement softwarepakket. De resultaten kunnen desalniettemin voor elke potentiële toekomstige softwaregebruiker dienen. De tien onderzochte pakketten zijn: §
Harvard Total Project Manager 2.0
§
Primavera 3.1
§
Hornet 5000, versie 0587
§
Promis 2.1
§
Microsoft Project 3.0
§
Superproject Plus 2.0
§
Pertmaster Advance 1.12
§
Superproject Expert 1.00
§
Plantrac 4B
§
Time Line 2.0
De Wit en Herroelen concludeerden dat geen enkele van deze pakketten tijd-kost inruil mogelijkheden biedt en dat de meeste pakketten omgaan met hulpmiddelenplanning en –nivellering op een nogal simplistische manier, waarbij gesteund wordt op onduidelijke heuristieken waarvan de uitleg zelden weergegeven wordt in de handleiding. Voor de meeste pakketten is het aan te raden een geheugen van 640K RAM beschikbaar te hebben. Sommige pakketten, zoals Plantrac Primavera en Promis, dienen op de harde schijf geïnstalleerd te worden. Alle onderzochte pakketten werken op IBM compatibele pc’s. Slechts Microsoft Project 3.0 bood de mogelijkheid niet om activiteiten te plotten. Hornet, Pertmaster Advance en Plantrac zijn de enige pakketten die het gebruik van meer dan één kalender per project toelaten en Primavera is het enigste pakket dat de link legt tussen werkdagen en kalenderdagen. De software varieert nogal wat betreft volgorderelaties. MS Project is het enige pakket dat gelimiteerd is tot einde-start relaties, wat noodzaakt sommige activiteiten op te splitsen wil men dezelfde projectduur bekomen als de vele pakketten die einde-einde, start-start en einde-start relaties aanbieden. Enkel Pertmaster Advance biedt de vier mogelijkheden, dus ook start-einde relaties. Opmerkelijk blijken enkele pakketten een serieus nadeel te kennen wat betreft de Ganttkaarten. Deze zouden foute laatste starttijden vertonen wanneer activiteiten gerelateerd worden door start-start en einde-einde relaties. Dit tijdsverschil is te wijten aan de berekeningswijze door de software wanneer overlappende netwerkactiviteiten plaatsvinden. Kostopvolging werd als behoorlijk zwak geëvalueerd door De Wit en Herroelen. De software verschilt in aantal, type en lay-out van rapporten voor kostopvolging. De invoer- en uitvoermogelijkheden van data in bepaalde pakketten zijn behoorlijk effectief, maar betrekkelijk complex. Voor Hornet, Plantrac en Primavera bijvoorbeeld is een praktische kennis van verwante databasesystemen vereist.
Deel I
36
Projectplanning
Er bestaat nogal een groot verschil tussen de verscheidene pakketten in mogelijkheden tot hulpmiddelenplanning. Het aantal hulpmiddelentypes dat kan gespecificeerd worden varieert bijzonder. De Wit en Herroelen wijzen erop dat de methode om hulpmiddelen op te volgen vaak niet alleen primitief maar ook misleidend is. Waar De Wit en Herroelen veel aandacht aan vestigen is het feit dat de softwarepakketten meestal falen om een gedetailleerde verklaring te geven van de heuristieken die gebruikt worden voor de kostopvolging en hulpmiddelenplanning.
Mellentien en Trautmann (2001) hebben de hulpmiddelenallocatie mogelijkheden van vijf softwarepakketten onder de loep genomen, namelijk:
§
Acos Plus.1 8.2
§
CA SuperProject 5.0a
§
CS Project Professional 3.0
§
MS Project 2000
§
Scitor Project Scheduler
Hun tests zijn gebaseerd op 1560 voorrangs- en hulpmiddelen beperkte problemen. Eerst werden de hardware vereisten en interfaces van de verschillende pakketten vergeleken. Elk pakket kan gebruikt worden op een pc met Microsoft Windows. Tabel 1.15 biedt een overzicht van de technische gegevens.
Geen enkel pakket had meer dan zestig seconden CPU-tijd nodig voor de hulpmiddelenallocatie van een enkel project. Maar geen enkel softwarepakket bood ook een beter resultaat dan degene tot nu toe gekend voor de 1560 instanties. Enkel CA SuperProject en Project Scheduler ondersteunen geen start-einde volgorderelaties. Alle pakketten voorzien echter wel verschillende soorten kalenders en instrumenten om hulpmiddelengerelateerde kosten te managen. Mellentien
en
Trautmann
concluderen
dat
geen
enkel
onderzochte
methode
tot
hulpmiddelenallocatie competitief is met de beste state-of-the-art algoritmes uit de literatuur. Vooral voor levensechte projecten met honderden activiteiten bestaat er nog een enorme performatiekloof tussen de gebruikte algoritmes en de moderne state-of-the-art heuristieken uit de literatuur. Geen enkel pakket biedt echter een exacte oplossing. Allen steunen op snelle
Deel I
37
Projectplanning
heuristische methodes. De heuristische methodes van Acos Plus.1 8.2 en Scitor Project Scheduler 8.0.1 stijgen in kwaliteit ver uit boven die van hun concurrenten.
Ook de invloed van de verschillende parameters van de 1560 probleeminstanties werd onderzocht. Daarvoor verwijs ik echter naar punt 3.5.
CA SuperProject 5.0a 002
Acos Plus. 1 8.2 CPU Operatiesysteem
CS Project Professional 3.0
MS Project 2000
Project Scheduler 8.0.1
486
486/25
386
P75
P120
Win 9x
Win 9x, OS/2,
Win 9x
Win 9x
Win NT 4.0
Win 2000,
Win 9x, Win ME
Win 2000
Win 2000
Win NT4.0
Win NT4.0
Win NT4.0
Win 2000 Win NT4.0
RAM
16 MB
16 MB
4 MB
24 MB
8 MB
HD
20 MB
10 MB
11 MB
35 MB
40 MB
Max. act.
32 000
8
n.a.
1 miljoen
99 999
Max. hulpmid.
32 000
8
n.a.
1 miljoen
20 000
Geg. Uitwisseling
ODBC, OLE,
ODBC, OLE,
ODBC, DDE
DDE, SQL
DDE, DAO
ODBC, OLE, DDE
ODBC, OLE, DDE, FTP
Import/export formaten
MPX, CSV, ASCII, Arriba, DBF, HTML
MPX, XLS, CSV, TXT, dBaseIII, WK1, Sylk
MPX, P3, CSV
MPX, XLS, CSV, MDB, TXT
MPX, SAP R/3
Figuur 1. 15: technische gegevens van vijf verschillende softwarepakketten (Bron: Resource Allocation with project management software, OR Spektrum, 2001, vol 23, p. 385)
Liberatore et al (2001) realiseerden voor het Project Management Instituut (PMI) een empirisch onderzoek bij projectmanagement professionelen in de bouwnijverheid. Dit onderzoek had een 35% antwoordgraad, wat uiteindelijk neerkwam op 240 antwoorden, waaronder 42 uit de bouwnijverheid. Deze studie toonde aan dat bouwdeskundigen andere karakteristieken, behoeftes en voorkeuren hebben in vergelijking met de volledige steekproef. Zij zouden aan minder projecten met meer activiteiten werken en zouden hevige gebruikers zijn van CPM en hulpmiddelenplanning. In de bouwsector zou men opvallend meer gebruik maken van Primavera dan van Microsoft Project.
Deel I
38
Projectplanning
De voorbije vijf jaar zijn gekenmerkt door een significante stijging in gebruik van projectmanagement software. Bijna alle respondenten uit de bouwnijverheid gebruiken deze software en het aantal die het gebruiken voor al hun projecten is bijna verdubbeld. Tot de jaren tachtig kende dit softwaregebruik een trage groei maar met de introductie van de pc echter steeg dit gebruik, dit tot de verzadiging in 1992.
De reden voor de bouwdeskundigen om Primavera al dan niet te gebruiken is vooral de projectcomplexiteit. Ook de software mogelijkheden, de grootte van projecten en vereisten van klanten spelen een belangrijke rol. Opleiding en ondersteuning blijken echter geen beïnvloedende factor te zijn.
MS Project
Primavera
andere
Bouwnijverheid (37a)
9 (24.3%)
19 (51.4%)
9 (24.3%)
Volledige steekproef (208b )
102 (49%)
44 (21.2%)
62 (29.8%)
a
vijf onderzoeken (11.9% van 42) werden niet beantwoord
b
32 onderzoeken (13.3% van 240) werden niet beantwoord
Figuur 1. 16: gebruikt projectmanagement softwarepakket in de bouwnijverheid (Bron: Liberatore et al., 2001)
Wanneer men het gebruik van de software nagaat voor de laatste twaalf maanden, dan kan toch een opmerkelijk verschil genoteerd worden tussen gebruikers uit de bouwnijverheid en de rest. Voor de volledige steekproef verklaarde ongeveer de helft MS Project frequent te gebruiken. Primavera volgt op minder dan een kwart van de totale tijd. Microsoft Project is een pakket dat niet echt duur is en gericht op de massamarkt. Primavera daarentegen is eerder duur maar is kwalitatief hoogstaand. In tegenstelling tot de volledige steekproef is Primavera het meest gebruikte softwarepakket bij de bouwrespondenten. MS Project wordt door minder dan een kwart van hen gebruikt.
Liberatore et al. (2001) illustreerden ook dat personen uit de steekproef die vaak analytische technieken toepassen vooral Primavera gebruikers zijn. Het omgekeerde geldt voor Microsoft Project. De middengroep, zij die niet veel doch ook niet weinig analytische technieken gebruiken, is verdeeld over beide softwarepakketten. Deze vaststelling blijkt uit onderstaande tabel:
Deel I
39
Aantal analytische instrumenten gebruikt
MS Project
Primavera
Projectplanning
Andere
Totaal voor bouwnijverheid
0 , 1 of 2
4 (50.0%)
1 (12.5%)
3 (37.5%)
8 (100%)
3 , 4 of 5
4 (28.6%)
7 (50%)
3 (21.4%)
14 (100%)
6 tot 14
1 (6.7%)
11 (73.3%)
3 (20%)
15 (100%)
totaal bouwnijverheid
9 (24.3%)
19 (51.4%)
9 (24.3%)
37a (100%)
a
vijf onderzoeken (11.9% van 42) werden niet beantwoord Figuur 1. 17: relatie tussen gebruikt softwarepakket en aantal gebruikte analytische technieken voor de bouwnijverheid (Bron: Liberatore et al., 2001)
Primavera Project Planner behoort dus tot de meer geavanceerde projectmanagement softwarepakketten, wat ook blijkt uit de studie van Kolisch (1999), waarvoor ik verwijs naar figuur 2.5 op p. 53. Een dergelijk pakket zal gebruikt worden wanneer projecten complexer worden, zoals bijvoorbeeld in de bouwkunde. 10 000 activiteiten kunnen gepland worden met dit pakket, wat vaak veel meer is dan bij de andere pakketten. Bovendien biedt Primavera de gebruiker de mogelijkheid te kiezen tussen behoorlijk wat prioriteitsregels, wat vaak lang niet het geval is voor de andere softwarepakketten. De hoogstaande kwaliteit van Primavera Project Planner is dan ook de reden waarom geopteerd werd voor dit pakket voor het onderzoek in deze scriptie.
Deel II
III.
40
Fasetransities in projectplanning
FASETRANTSITIES IN PROJECTPLANNING
Aan de hand van de complexiteitstheorie kan bepaald worden of berekeningsproblemen ‘gemakkelijk’ al dan niet ‘moeilijk’ oplosbaar zijn, respectievelijk P of NP-hard (NP-compleet) zijn. Onderzoekers in het domein van artificiële intelligentie hebben recentelijk aangetoond dat veel NP-harde problemen fasetransities vertonen. Herroelen en De Reyck (1998) waren de eersten om aan te tonen dat gelijkaardige fasetransities bestaan voor NP-harde problemen in het domein van RCPSP.
Een fasetransitie van een complex systeem is een plotse verandering van een systeemeigenschap wanneer een ordeparameter een kritisch waarde overschrijdt (Herroelen en De Reyck, 1998).
Vele NP-complete problemen vertonen zogenoemde fasetransities, die resulteren in een plotse en opvallende verandering in de berekeningscomplexiteit. Zo variëren probleeminstanties vaak van gemakkelijk naar moeilijk oplosbaar en terug naar gemakkelijk oplosbaar wanneer hun karakteristieken gewijzigd worden. Het zijn de ordeparameters, kenmerkend voor het gehele systeem, die deze transities bepalen.
Zowel morfologische als hulpmiddelen gerelateerde maatstaven dienen als ordeparameters. Terwijl de morfologische maatstaven continue gemakkelijk-moeilijk of continue moeilijk-gemakkelijk fasetransities vertonen, is gemakkelijk-moeilijk-gemakkelijk transitiegedrag vooral het gevolg van hulpmiddelen gerelateerde maatstaven.
Al sinds midden de jaren zestig ontstond de interesse in activiteitennetwerken en de effecten van een probleemstructuur op de prestatie van algoritmes. Indien een maatstaf bestond voor netwerkcomplexiteit dan zou dit de keuze tussen de algoritmes of de efficiëntiebepaling van een welbepaald algoritme enorm vergemakkelijken. Vandaar dat in de literatuur reeds vele maatstaven voorgesteld werden. Deze proberen vooral informatie te vatten betreffende de grootte van het projectnetwerk, de topologische structuur (morfologie) van het projectnetwerk en de beschikbaarheid in relatie tot de vereiste van de verschillende types hulpmiddelen.
Deel II
41
Fasetransities in projectplanning
1. Morfologie van netwerken Tavarez (1999) stelt dat de morfologie of vorm van een projectnetwerk drie basiskenmerken bevat: §
De grafische voorstelling van het netwerk, aan de hand van een knooppuntenvoorstelling.
§
Het aantal niet overbodige, directe volgorderelaties, D. Normaliter is een netwerk met een hoger aantal van deze relaties complexer.
§
De lengte, L, van de niet overbodige, directe volgorderelaties van het netwerk.
Om de morfologische structuur van een netwerk te beschrijven, wil ik mij niet beperken tot de drie meest gekende complexiteitsmaatstaven, namelijk de coëfficiënt van netwerk complexiteit (CNC), de ordekracht (order strength: OS) en de complexiteitsindex (CI). Tot nu toe hebben onderzoekers zich vooral op data met één van deze complexiteitsmaatstaven gericht tijdens het ontwikkelen van efficiënte oplossingsprocedures. Onlangs werden echter nog zes morfologische indicatoren voorgesteld door Vanhoucke et al. (2003), die deels gebaseerd zijn op die van Tavares et al. (1989). Ook deze indicatoren zullen hier besproken worden en zullen in deel III gebruikt worden voor het onderzoek.
1.1. Coëfficiënt van netwerkcomplexiteit (CNC)
Deze meeteenheid voor de morfologische structuur van een netwerk in pijlenvoorstelling is wellicht de bekendste complexiteitsmaatstaf. Pascoë definieerde deze meeteenheid in 1966 als de ratio van het aantal volgorderelaties (pijlen) over het aantal activiteiten (knooppunten). Davis (1975) heeft de CNC aangepast voor de knooppuntenvoorstelling van netwerken. De maatstaf stelde nu het aantal directe volgorderelaties (pijlen) over het aantal activiteiten (knooppunten) voor. Kolisch et al (1995) zijn van mening dat, voor een gegeven aantal activiteiten in een knooppuntenvoorstelling, een groter aantal volgorderelaties en dus een grotere verbondenheid zal leiden tot een hogere complexiteit.
Verscheidene literatuurstudies, onder andere die van Kolish e.a.(1995), komen tot de vaststelling dat problemen gemakkelijker oplosbaar zijn naarmate de waarde van de CNC stijgt (Herroelen en De Reyck, 1999).
Deel II
42
Fasetransities in projectplanning
1.2. Ordekracht (OS)16
Mastor (1970) definieerde deze meeteenheid voor de topologische structuur van een knooppuntenvoorstelling als het aantal volgorderelaties (uitgezonderd deze voor de dummy starten eindactiviteit) gedeeld door het theoretische maximale aantal volgorderelaties n(n-1)/2, waar n staat voor het aantal niet-dummy activiteiten in het netwerk. Herroelen en De Reyck (1999) kwamen tot de conclusie dat verschillende maatstaven uit de literatuur, OS, densiteit, restrictiviteit, en 1- flexibiliteitratio, één en dezelfde complexiteitsmaatstaf vormen.
1.3. Complexiteitsindex (CI)
Deze maatstaf werd oorspronkelijk door Bein et al (1992) gedefinieerd als ‘reductiecomplexiteit’ voor een niet cyclische pijlenvoorstelling met twee uiteinden. Ze komt overeen met het minimale aantal reducties van knooppunten die voldoende zijn om een niet cyclisch netwerk met twee uiteinden te reduceren tot een enkelvoudig uiteinde. De complexiteitsindex meet dus in welke mate een netwerk in serie of in parallel is opgebouwd. In tegenstelling tot de CNC, werd deze maatstaf niet aangepast voor de knooppuntenvoorstelling.
1.4. Morfologische indicatoren I1 tot I6.
Vanhoucke et al. (2003) stellen acht complexiteitsparameters voor die de morfologische structuur van een netwerk beschrijven. Zes van de maatstaven ontleenden zij aan Tavares et al. (1999), waarna zij deze geheel of gedeeltelijk aanpasten. In aanvulling op deze zes indicatoren kozen zij voor de ordekracht OS, voorgesteld door Mastor (1970) en de coëfficiënt voor netwerkcomplexiteit CNC (Pascoë 1966; Davis 1975). De zes indicatoren en OS integreerden zij in hun netwerkgenerator RanGen 2. Daarop zal in deel III tijdens het onderzoek dieper op ingegaan worden.
16
Deze term is meer bekend onder de Engelstalige benaming, nl. order strenght (OS). In overeenstemming met de literatuur zal verder dan ook deze afkorting gebruikt worden.
Deel II
43
Fasetransities in projectplanning
I1
: probleemgrootte
Aantal activiteiten (n)
I2
: serie/parallel indicator
Meet de dichtheid van een netwerk tot een serie/parallel grafiek voor knooppuntnetwerken
I3
: activiteitsdistributie
Beschrijving verdeling van activiteiten doorheen netwerk
I4
: korte, directe voorrangsrelatie
Meet het aantal korte, onmiddellijk voorgaande relaties (l = 1)
I5
: lange, direct voorrangsrelatie
Meet het aantal lange, onmiddellijk voorgaande relatie (l > 1)
I6
: morfologische slack
Bepaalt morfologische slack voor elke activiteit
OS
: Ordekracht
Zie 1.2.
CNC : coëfficiënt voor netwerkcomplexiteit
Zie 1.1.
Voor de verklaring van deze indicatoren wordt uitgegaan van netwerken in knooppuntvoorstelling. De notatie Pi wordt gebruikt om de set van onmiddellijke voorgangers van activiteit i aan te duiden, Si voor de onmiddellijke opvolgers. P’i en S’i stellen dan de set van alle directe en indirecte voorgangers en opvolgers voor. Tavares et al. (1999) definieerden het progressief niveau PLi en het regressieve niveau RLi voor elke activiteit i ∈ N: Pi = Ø ⇒ 1 PLi =
Pi & Ø ⇒ max PLj + 1 j ? Si
Si = Ø ⇒ m RLi =
Si & Ø ⇒ min. RLj – 1 j ? Si
I2 meet net zoals CI de dichtheid van een netwerk tot een serie-parallel gerichte grafiek. In tegenstelling tot CI, die toepasselijk is voor de pijlenvoorstelling, gebeurt dit voor I2 voor de knooppuntvoorstelling. Parameter m staat voor het maximale progressieve niveau voor alle activiteiten. Indicator I2 kan als volgt voorgesteld worden: n=1 ⇒ 1 I2 =
n>1 ⇒ m–1 n–1
Deel II
44
Fasetransities in projectplanning
I2 varieert tussen 0 en 1. Wanneer alle activiteiten in het netwerk in serie voorkomen dan is m = n en I2 = 1. Wanneer ze echter in parallel voorkomen is m gelijk aan 1 en I2 gelijk aan nul.
Indicator I3 is gebaseerd op standaardafwijkingen. I3 is gelijk aan nul wanneer ook de s gelijk is aan nul. Dit is het geval bij een uniforme verdeling. I3 is daarentegen gelijk aan 1 bij een extreme verdeling. De formule voor I3 gaat als volgt:
I3
std.afw. (s ) van de breedte (w) – verdeling over de PN’s s = –––––––––––––––––––––––––––––––––––––––––––––––––––––– = ––––––– smax
max. std.afw. mogelijk voor gegeven m en n
De maximale standaardafwijking voor gegeven n en m komt overeen met een verdeling met (m–1) progressieve niveaus met w=1 en één progressief niveau met w = n – (m–1). Deze formule voor I3 geldt wanneer m ∈ ]1,n[, zoniet is I3 = 0.
De maximale morfologische lengte van een netwerk is gelijk aan m – 1, gezien de lengte van een onmiddellijk voorgaande relatie (i,j) gedetermineerd wordt door het verschil tussen het progressieve niveau van het eindknooppunt (activiteit) j en het beginknooppunt i. Vanhoucke et al. (2003) stelden n’ voor als een parameter voor de structuur van voorgaande relaties, die gedefinieerd wordt als: n’ l = # {(i,j) ∈ A| PLj – PLi = l}, waarbij A staat voor de set van volgorderelaties, n voor het aantal activiteiten en n’ l voor het aantal volgorderelaties met lengte l. Indicator I , de indicator de de aanwezigheid van korte onmiddellijk voorafgaande volgorderelaties meet wordt als volgt gedetermineerd: D = n – w1 I4 =
D > n – w1 ⇒ n’l – n + w1 D – n + w1
I varieert wederom tussen 0 en 1. D vormt het maximaal aantal korte voorgaande relaties in een netwerk voor een gegeven breedte van elk niveau: m-1
D=
∑ wa ∗ wa+1 a=1
Deel II
45
Fasetransities in projectplanning
Indicator I5 is sterk gerelateerd met de vorige indicator. Deze indicator houdt ook rekening met de lange onmiddellijke volgorderelaties, deze met een lengte groter dan 1. Als het aantal volgorderelaties met een lente groter dan 1 stijgt, daalt de waarde voor deze indicator. Ook deze indicator varieert van 0 tot 1. Het totaal aantal directe volgorderelaties met lengte groter dan 1 wordt voorgesteld door TDP. I5 kan dan als volgt voorgesteld worden:
TDP = n – w 1 ⇒ 1 m-1
I5 =
∑ n’l l – m + 1 + n’1 – n + w 1 l=2 2–m TDP > n – w 1 ⇒ –––––––––––––––––––––––––––– TDP – n + w1
Indicator I6 tenslotte is een indicator die niet door Tavarez et al. (1999) opgenomen werd. Deze Indicator, die rekening houdt met de morfologische spelingruimte van elke activiteit, kan berekend worden als het verschil tussen het regressieve en progressieve niveau. I6 is gelijk aan 1 wanneer geen enkele activiteit spelingruimte heeft en gelijk aan nul wanneer alle activiteiten, uitgezonderd diegene die zich op het kritieke pad bevinden, een maximale waarde hebben voor de spelingruimte. Deze indicator kan als volgt worden voorgesteld:
m ∈ {1,n} ⇒ 1 n
I6 =
(m – 1)(n – m) + ∑ (PLi – RLi ) i=1
m ∉{1,n} ⇒ ––––––––––––––––––––––––––––– (m –1)(n – m)
Naast deze zes indicatoren gaven Vanhoucke et al. (2003) de voorkeur aan OS en CNC om de morfologie van een netwerk te beschrijven. Voor de beschrijving van deze indicatoren verwijs ik naar punt 1.1. en 1.2.
Deel II
46
Fasetransities in projectplanning
2. Topologische maatstaven en RCPSP
RCPSP, het probleem om een project te plannen wanneer hulpmiddelen beperkt zijn, is een NPhard probleem. Recente berekeningen bieden meer inzicht in de invloed van de topologische maatstaven op de hardheid van dit probleem. De maatstaven voor netwerkstructuur, zoals OS, CNC en CI, vertonen typisch een ononderbroken hard-gemakkelijk complexiteitspatroon.Idealiter zouden zulke maatstaven de hardheid van problemen, zoals gemeten aan de hand van de CPU-tijd, moeten voorspellen. Desalniettemin zijn meerdere onderzoekers tot de conclusie gekomen dat deze maatstaven niet altijd tot een correcte inschatting komen van de complexiteit van een netwerk.
Elmaghraby en Herroelen (1980) bijvoorbeeld hebben het nut van de coëfficiënt van netwerkcomplexiteit (CNC) in vraag getrokken gezien het perfect mogelijk is netwerken op te bouwen met een zelfde CNC-waarde maar met een verschillende graad van complexiteit. De coëfficiënt voor netwerkcomplexiteit op zich slaagt er niet in een onderscheid te maken tussen gemakkelijke en moeilijke problemen en kan bijgevolg niet dienen als een goede maatstaf om de impact te beschrijven van de netwerkstructuur op de hardheid van een project planningsprobleem.
Kolisch et al (1995) kwamen tot de conclusie dat RCPS-problemen gemakkelijker oplosbaar worden naarmate de waarden van de CNC stijgen, zonder rekening te houden met de complexiteitsindex (CI). De Reyck en Herroelen (1996) daarentegen vinden het dubbelzinnig om een probleem enkel en alleen met de CNC te verklaren. Zij geloven in een positieve correlatie tussen de CNC en de CI. Deze laatste zou volgens hen dus wel belangrijk zijn om de vereiste berekeningsinspanning te voorspellen om een RCPS-probleem op te lossen. Wanneer de CPU-tijd dan uitgezet wordt in functie van de complexiteitsindex, komt een nogal continu hard-gemakkelijkhard complexiteitspatroon te voorschijn. Hoe hoger dus de CI, hoe gemakkelijker het RCPSprobleem.
Volgens De Reyck (1998) is de ordekracht (OS), naast de CI, een goed maatstaf voor netwerkcomplexiteit. Wanneer hij de CPU-tijd uitzette ten opzichte van deze parameter, verkreeg hij een lineaire hard-gemakkelijk complexiteitstransitie. De Reyck kwam in 1998 zelfs tot het besluit dat de OS de krachtigste maatstaf was om variaties in de CPU-tijd te verklaren. De Reyck en
Herroelen
(1996)
bewezen
dat
de
complexiteitsindex
(CI)
de
coëfficiënt
van
Deel II
47
Fasetransities in projectplanning
netwerkcomplexiteit (CNC) overtreft. Daarenboven concludeerden zij dat de ordekracht (OS) de CI overtreft.
Deel II
48
Fasetransities in projectplanning
3. Hulpmiddelen gerelateerde maatstaven
Opnieuw worden hier de drie belangrijkste maatstaven voor hulpmiddelenbeschikbaarheid besproken,
namelijk
de
hulpmiddelenfactor
(RF),
de
hulpmiddelenkracht
(RS)
en
om
de
hulpmiddelenrestrictiviteit (RC).
3.1. Hulpmiddelenfactor (RF)17
De
hulpmiddelenfactor
vormt
één
van
de
meest
gekende
parameters
hulpmiddelenbeschikbaarheid te beschrijven. Deze term werd geïntroduceerd door Pascoë (1966). Deze maatstaf bepaalt de gemiddeld benodigde hoeveelheid hulpmiddelen per activiteit:
1 n K RF = –––– Σ Σ nK i=1 k=1
1, als rik >0 0, anders
Wanneer deze factor gelijk is aan 1, dan zijn alle hulpmiddelen nodig voor elke activiteit. Wanneer deze factor echter nul bedraagt, vereist enkele activiteit geen enkel hulpmiddel
3.2. Hulpmiddelenkracht (RS)18
Deze maatstaf voor determinatie van hulpmiddelenbeschikbaarheid werd oorspronkelijk bedacht door Cooper (1976), maar werd hergedefinieerd door Kolisch et al. (1995) als:
a k – r k min RSk = –––––––––––––– r k max – r k min
17 18
RF staat voor resource factor, de meest gebruikte term voor hulpmiddelenfactor. RS staat voor resource strength, de beter bekende benaming voor hulpmiddelenkracht.
Deel II
49
Fasetransities in projectplanning
waarbij a k staat voor de totale beschikbaarheid van hernieuwbare hulpmiddelen van type k, r k
min
max
de
gelijk is aan max r
ik (i=1,...,n)
(max. hulpmiddelenvereiste voor elk hulpmiddelentype) en r k
piekvraag voorstelt voor hulpmiddel type k. Dus, voor tenminste één hulpmiddel, verkrijgen we de kleinst mogelijke hulpmiddelenbeschikbaarheid wanneer de hulpmiddelenkracht gelijk is aan nul. Wanneer RS echter 1 bedraagt, dan hebben we niet meer te maken met een hulpmiddelenbeperkt probleem (RCPSP).
3.3. Hulpmiddelenrestrictiviteit (RC)19
Deze maatstaf werd ingevoerd door Patterson (1976):
pk ––––––
ak
waarbij pk staat voor de gemiddelde gevraagde hoeveelheid van hulpmiddel k en ak voor de beschikbaarheid van hulpmiddelen van type k.
Voor de hulpmiddelen gerelateerde maatstaven moet echter wel opgemerkt worden dat tot op heden nog geen volledig ondubbelzinnige maatstaf voor hulpmiddelenbeschikbaarheid bestaat. Dit vormt dus zeker nog een belangrijk thema voor verder onderzoek.
19
RC staat voor resource constrainedness, de meest gebruikte term voor hulpmiddelenrestrictiviteit.
Deel II
50
Fasetransities in projectplanning
4. Op hulpmiddelen gebaseerde parameters en RCPSP Elmaghraby en Herroelen (1980) waren de eersten die veronderstelden dat de relatie tussen de complexiteit van een RCPSP en de hulpmiddelenbeschikbaarheid varieerden volgens een klokvormige curve. Wanneer hulpmiddelen enkel in kleine hoeveelheden beschikbaar zijn, bestaat er behoorlijk weinig vrijheid om activiteiten te plannen. Vandaar dat het overeenkomende RCPSP relatief gemakkelijk oplosbaar is. Wanneer hulpmiddelen overvloedig beschikbaar zijn, kunnen de activiteiten parallel gepland worden waardoor de projectduur zal samenvallen met de lengte van het kritieke pad. Wederom zal slechts een kleine berekeningsinspanning nodig zijn. Met gebruik van de netwerkgenerator ProGen (zie later) ontdekten De Reyck en Herroelen (1996) bijvoorbeeld dat de vereiste CPU-tijd in functie van de hulpmiddelenkracht (RS) inderdaad volgens een klokvormig gemakkelijk-hard-gemakkelijk complexiteitspatroon evolueert. Ze observeerden
Berekeningscomplexiteit (CPU)
dezelfde relatie tussen de CPU-tijd en de hulpmiddelen restrictiviteit (RC).
Figuur 2. 1: gemakkelijke-hard-gemakkelijk complexiteitspatroon, CPU-tijd in funtie van RS en RC (Bron: Herroelen en De Reyck, 1999, p. 13)
Hierboven werd de CPU-tijd uitgezet in functie van de RS (van nul tot 1) en RC (van nul tot 100%). De figuur toont een behoorlijk scherpe ‘gemakkelijk-hard-gemakkelijk’ fasetransitie. Wanneer RS klein is, zal de waarde van RC hoog zijn. Er moet echter wel opgemerkt worden dat de overeenstemming tussen RC en RS niet precies is, maar slechts als illustratie dient. Wanneer de
Deel II
51
Fasetransities in projectplanning
waarde van RS nu groter of gelijk is aan 1 dan zijn de hulpmiddelen niet langer beperkt en kan het probleem relatief eenvoudig opgelost worden door middel van het kritieke pad. Echter, wanneer de waarde van RS nul benadert, is het probleem zeer moeilijk op te lossen en wanneer de waarde van RS negatief wordt, komt het er op aan te controleren of de hulpmiddelenvereisten de beschikbaarheden overtreffen. Is dit het geval dan is het probleem onuitvoerbaar.
Kolisch et al (1995) zijn van mening dat de hulpmiddelenkracht (RS) het meest impact heeft op oplossingstijden. De gemiddelde oplossingstijd stijgt ononderbroken bij een dalende RS. Anderen zijn dan weer van mening dat de hulpmiddelen restrictiviteit (RC) beter dient dan RS als hulpmiddelen
gerelateerde
hulpmiddelenbeschikbaarheid
parameter wegens
het
omdat niet
RC
een
incorporeren
pure van
maatstaf informatie
is
van
over
de
voorrangsstructuur van een netwerk. Bovendien kan de RS soms geen onderscheid meer maken tussen gemakkelijke en moeilijk oplosbare instanties, terwijl dat wel nog mogelijk is voor de RC.
De hulpmiddelen gerelateerde parameters vertonen typisch een gemakkelijk-hard-gemakkelijk complexiteitspatroon voor het RCPSP. Er moet wel onderlijnd worden dat sommige problemen in het harde gebied toch niet zo moeilijk oplosbaar zijn.
Tot op heden werd nog geen optimale hulpmiddelen gerelateerde maatstaf gevonden. Maar zoals Herroelen en De Reyck (1999, p. 14) opmerken: “Zelfs wanneer de ordeparameters om eventuele fasetransities te evalueren nog steeds niet perfect zijn, toch is het uiterst nuttig te weten waar zich de ware harde projectplanningsproblemen bevinden”.
Deel II
52
Fasetransities in projectplanning
5. impact van hulpmiddelen gerelateerde en morfologische maatstaven op projectmanagement software.
Tavares (1999) merkt op dat ondertussen zowat alle projectmanagement softwarepakketten de studie van projectnetwerken incorporeren maar dat sommige belangrijke thema’s nog steeds verwaarloosd worden, zoals: §
analyse en indeling van de morfologie van elke projectnetwerk.
§
automatische aanmaak van gemakkelijk te interpreteren grafieken van netwerken om een beter zicht te krijgen in de morfologie van een netwerk.
§
De relatie tussen de morfologie en de onzekerheid omtrent de totale duur van het project. Een groter inzicht in deze relatie zou de projectmanager immers in staat stellen de moeilijkheidsgraad te bepalen om het project tijdig te beëindigen in termen van het projectnetwerk.
Niettegenstaande dat weinig softwarepakketten de invloed van hulpmiddelen gerelateerde en morfologische karakteristieken in rekening brengen, werd in de literatuur toch enig onderzoek daaromtrent uitgevoerd. Kolisch (1999) bijvoorbeeld bestudeerde de kwaliteit van zeven commerciële projectmanagement softwarepakketten wat betreft hulpmiddelenallocatie. De onderzochte pakketten zijn:
§
Artemis Scheduler Publisher 4.1
§
Project Manager Workbench 1.1.02w
§
CA SuperProject 3.0 C
§
Project Scheduler 6.0 1.02
§
Microsoft Project 4.0
§
Time Line 6.0.0
§
Primavera Project Planner 1.0
Projecten zijn gekenmerkt door verschillende niveaus van probleemparameters. Kolisch meent dat het type probleem, dat uitgedrukt wordt door deze niveaus, de oplosbaarheid beïnvloedt. De verschillende probleemparameters om projecten te rangschikken werden gehaald uit het onderzoek van Kolisch et al. (1995):
Deel II
53
J
: aantal activiteiten
R
: aantal beperkte hulpmiddelen
CNC
: coëfficiënt voor netwerkcomplexiteit
RF
: hulpmiddelenfactor
RS
: hulpmiddelenkracht
Fasetransities in projectplanning
Onderstaande tabel toont de verschillende niveaus van de systematisch gevarieerde probleemparameters die gebruikt werden voor dit onderzoek:
Parameter
Niveaus
J
R
RS
RF
CNC
10
2
0.2
0.5
1.5
20
3
0.5
1
2
30
4
0.7
Figuur 2. 2: niveaus van systematisch gegenereerde probleemparameters (Bron: Kolisch, 1999)
Het onderzoek werd uitgevoerd op 160 problemen en de Branch&Bound procedure ontwikkeld door Demeulemeester en Herroelen (1992) werd toegepast om een optimaal referentiepunt te bekomen. Met een tijdslimiet van 3 600 CPU-seconden voor elk probleem op een pc met 40 MHz heeft de methode een optimale oplossing bereikt voor 153 problemen. Voor de overige 7 problemen werd een bovenste grens van de optimale duurtijd gevonden. Vervolgens werden deze 160 problemen opgelost met alle zeven softwarepakketten. Voor de 1 120 antwoordwaarden (160 problemen voor alle 7 pakketten) is de mediaan 3.57%, het gemiddelde 5.79%, de standaardafwijking 7.51% en de draagwijdte varieert van nul tot 51.85%. Gemiddeld genomen kwamen de pakketten voor 45% van de problemen tot een optimale oplossing. Onderstaande tabel toont het gemiddelde en standaardafwijking voor elke van de zeven onderzochte softwarepakketten. Daaruit blijken duidelijk de goede resultaten voor CA SuperProject, Primavera en Timeline. Wanneer projecten niet behoorlijk kunnen gerangschikt worden, biedt deze tabel de mogelijkheid om de kwaliteit van verschillende pakketten te vergelijken.
Deel II
54
softwarepakket
Fasetransities in projectplanning
gemiddelde
standaardafwijking
Artemis Schedule Publisher
9.76
9.82
CA SuperProject
4.41
6.02
Microsoft Project
5.35
6.53
Primavera Project Planner
4.39
6.04
Project Manager Workbench
6.69
8.60
Project Scheduler 6
5.43
7.98
Time Line
4.49
5.09
Figuur 2. 3: gemiddelde en standaardafwijking van het percentage afwijking bekomen door zeven projectmanagement softwarepakketten (Bron: Kolisch, 1999)
Kolisch onderzocht de invloed van de verschillende parameters (N, R, RS, RF, CNC) op het percentage afwijking van het optimale referentiepunt. Tabellen met de resultaten van deze bevindingen zijn terug te vinden in bijlage 1.1. Tijdens dit onderzoek kwam hij onder andere tot de conclusie dat de kwaliteit van de oplossing achteruit gaat naarmate het aantal activiteiten (N) stijgt. Artemis Schedule Publisher vormt daar enige uitzondering gezien er voor dertig activiteiten betere resultaten bekomen werden dan voor twintig. Alle zeven onderzochte pakketten vertonen slechtere resultaten voor drie beperkte hulpmiddelen dan voor slechts één. Drie pakketten, namelijk MS Project, Project Manager Workbench en Time Line, vertonen steeds slechtere resultaten wanneer het aantal beperkte hulpmiddelen toeneemt. Drie andere pakketten, namelijk CA SuperProject, Primavera Project Planner en Project Scheduler 6 kennen kleine verbeteringen wanneer het aantal onbeperkte hulpmiddelen stijgt van twee tot drie. Wanneer de capaciteit van hulpmiddelen daalt, dus wanneer de hulpmiddelenkracht (RS) daalt, verslechteren de planningsresultaten van alle pakketten aanhoudend. Het omgekeerde geldt voor de hulpmiddelenfactor (RF). Een stijgend aantal vereiste hulpmiddelen leidt tot een lagere kwaliteit van oplossingen. Een softwarepakket zal echter betere resultaten behalen wanneer meer volgorderelaties aanwezig zijn, dus wanneer een hoge waarde voor de coëfficiënt van netwerkcomplexiteit (CNC).
Deel II
55
Fasetransities in projectplanning
Conclusie van dit alles is dat de besproken probleemparameters wel degelijk een invloed hebben op de prestaties van projectmanagement softwarepakketten. Kolisch heeft bovendien de significantie van deze invloed nagegaan met behulp van de ANOVA-, de Mann & Whitney- en de Kruskal en Wallis test. De resultaten kunnen gevonden worden in onderstaande tabel:
R KW
Artemis Scheduler Publisher
N
ANOVA
KW
NC
ANOVA MW
RF
ANOVA MW
RS
ANOVA KW
ANOVA
2.69
0.92
20.47
30.33
74.19
88.34
0.50
2.30
0.04
0.06
4.07
15.98
0.07
0.37
10.24
23.25
0.00
0.01
0.00
0.00
MS Project
7.56
2.49
0.07
0.25
32.69
36.01
0.00
0.00
0.02
0.00
Primavera Project Planner
19.65
23.36
37.53
67.83
26.01
39.15
0.78
4.56
0.00
0.00
9.81
6.18
21.71
39.26
91.34
63.22
0.90
0.63
0.00
0.00
3.46
2.78
0.67
0.77
54.99
83.29
0.00
0.00
0.00
0.00
3.78
3.58
0.16
0.45
98.86
86.50
0.96
1.76
39.78
11.43
CA SuperProject
Project Manager Workbench Project Scheduler 6 Time Line
Figuur 2. 4: significantieniveaus voor parametrische en niet-parametrische testen, het effect van onafhankelijke parameters op projectmanagement software (onderlijnde waarden aan 5% confidentie-niveau)
Het aantal vereiste beperkte hulpmiddelen, bepaald door RF, heeft een zeer sterke invloed op de prestaties van de softwarepakketten. Hetzelfde geldt voor de zeldzaamheid van de hulpmiddelen, gemeten door RS. Time Line vormt hier echter wel een uitzondering op. Parameter R, het aantal beperkte hulpmiddelen, beïnvloedt vooral Artemis Scheduler Publisher, Project Scheduler 6 en Time Line. Het aantal activiteiten, voorgesteld door N, heeft een significante invloed op CA SuperProject, MS Project, Project Scheduler 6 en Time Line. CNC, de coëfficient voor netwerkcomplexiteit, is de enige parameter die geen significante invloed uitoefent op eender welk softwarepakket.
Kolisch kwam dus tot de conclusie dat de geteste softwarepakketten verschillend presteren bij het oplossen van verschillende types problemen. Welk pakket best is, hangt dus af van de probleemparameters. Om de gemiddelde prestaties van de verschillende pakketten te kennen heeft Kolisch de Friedmann-test en de Wilcoxon-test toegepast. Dit toonde aan dat slechts vijf paar softwarepakketten blijk geven van geen significant verschil in resultaat. Dit is het geval voor
Deel II
56
Fasetransities in projectplanning
Primavera en CA SuperProject, Project Scheduler 6 en MS Project, Time Line en CA SuperProject, Time Line en Primavera, en Time Line en Project Scheduler 6. De verschillende onderzochte softwarepakketten en hun kwalitatieve rangschikking worden hieronder grafisch weergegeven. Wat betreft de mogelijkheden tot hulpmiddelenallocatie kunnen vier grote klasses onderscheiden worden. Tot de eerste klasse behoren Primavera Project Planner, CA SuperProject en Time Line. De volgende klasse wordt ingenomen door Time Line, Project Scheduler 6 en Microsoft Project. De derde en vierde klasse bevatten softwarepakketten die eerder zwakke resultaten leveren, namelijk Project Manager Workbench en Artemis Scheduler.
Figuur 2. 5: performatieklasses van projectmanagement softwarepakketten (pakketten zonder statistisch significant verschil behoren tot dezelfde ellips) (Bron: Kolisch, 1999)
Ook in het experiment van Mellentien en Trautmann (zie p. 34) werd de invloed van de parameters van de probleeminstanties onderzocht. Het gaat meer bepaald over:
N
: het aantal activiteiten
RS
: hulpmiddelenkracht
RF
: hulpmiddelenfactor
CNC
: coëfficiënt voor netwerkcomplexiteit
Bedoeling van dit onderzoek is de mogelijkheden tot hulpmiddelenallocatie voor verschillende complexiteitsscenario’s te evalueren. Dit gebeurt door het gemiddeld aantal gebruikte hulpmiddelen (RF), de schaarste aan hulpmiddelen (RS) en het aantal volgorderelaties (CNC) te veranderen. De testset bevat tien instanties voor elke combinatie van de parameters RS, RF en CNC. De optimale oplossing voor de instanties met N=30, N=60 en N=90 werden als referentiepunt genomen. De analyse is gebaseerd op 600 instanties met 120 activiteiten.
Deel II
57
Fasetransities in projectplanning
Figuur 2.6 toont de gemiddelde afwijking van de projectduurtijd in functie van de hulpmiddelenkracht. Merk op dat de afwijking voor alle vijf pakketten merkbaar toeneemt naarmate de hulpmiddelen schaarser worden, dus naarmate RS stijgt.
RS
0.5
0.4
0.3
0.2
0.1
Acos Plus 1
2.17
6.06
9.58
13.45
17.21
SuperProject
6.07
10.28
13.67
17.21
22.74
CS Project
6.13
11.46
14.47
17.07
19.36
MS Project
4.60
9.12
12.97
18.28
25.12
Scitor PS
3.35
7.56
10.76
15.42
18.67
Figuur 2. 6: gemiddelde afwijking van duurtijd (%) voor verschillende waarden van RS (N=120) (Bron: Mellentien en Trautmann, 2001)
Wat betreft de hulpmiddelenfactor kon, opnieuw voor alle onderzochte pakketten, aangetoond worden dat wanneer activiteiten slechts één hulpmiddel gebruiken, de gemiddelde afwijking projectduur veel kleiner is dan in het geval van twee of meer hulpmiddelen. Het aantal volgorderelaties (CNC) daarentegen beïnvloed de hulpmiddelenallocatie van geen enkel onderzocht softwarepakket. Deze bevindingen zijn terug te vinden in figuur 2.7.
RF 0.25
CNC
0.5
0.75
1
1.5
1.8
2.1
Acos Plus 1
5.69
11.34
11.39
10.35
8.92
9.5
10.67
Super Project
6.27
16.98
18.70
14.02
13.81
13.84
14.33
CS Project
8.17
15.80
16.63
14.20
13.15
13.67
14.27
MS Project
8.37
16.53
16.80
14.37
13.47
13.90
14.68
Scitor PS
6.30
13.06
13.34
11.90
10.63
10.85
11.98
Figuur 2. 7: gemiddelde afwijking van duurtijd (%) voor verschillende waarden van RF en CNC (N=120)
Deel II
58
Fasetransities in projectplanning
6. Netwerkgeneratoren
Onderzoekers maken gebruik van activiteitsnetwerken om projecten te visualiseren. De nood aan netwerkinstanties om de reeds talrijke optimale en heuristische methodes te testen en te vergelijken, leidde tot de ontwikkeling van verschillende netwerkgeneratoren. Bedoeling van deze softwarepakketten is om te komen tot willekeurige netwerken die voldoen aan vooropgestelde waarden van de parameters die de hardheid van een probleem beheersen.
Wanneer men projectmanagment softwarepakketten wil analyseren en een uitspraak doen over hun prestaties dan moet men twee zaken in rekening houden. Eerst en vooral moet men beschikken over een set van maatstaven voor doeltreffendheid voor de verscheidene doelstellingen van de analyse. Het
spreekt
voor
zich
dat
als
men
bijvoorbeeld
de
functie
van
het
probleem
‘hulpmiddelennivellering’ beschouwt, men dit ook zal moeten toetsen aan een criterium dat geschikt is voor zo’n soort probleem. Meestal kan tussen verschillende criteria gekozen worden. Zo kunnen de prestaties van hulpmiddelennivellering zowel aan de hand van gemiddelde absolute afwijking van het gemiddelde getoetst worden als aan de hand van maximale absolute afwijking van het gemiddelde (Agrawal et al., 1996). Bovendien moet het veld van proefneming de software correct testen. Als men dus meerdere pakketten vergelijkt, moeten die uiteraard allen getest worden met dezelfde projectparameters. Vandaar de nood aan een standaardset van testproblemen.
De 110 referentie instanties van Patterson (1984) werden lange tijd als standaard beschouwd. Patterson vergeleek drie exacte procedures voor minimalisatie van het RCPS probleem aan de hand van deze 110 instanties. Zijn set van instanties wordt echter niet langer als referentiepunt aanvaard wegens een drietal tekortkomingen (Kolisch et al., 1995). Gezien zijn testset problemen bevat van verschillende bronnen uit de literatuur, ontbreekt deze een beheerste opbouw van verschillende parameters. Bovendien is zijn testset slechts bruikbaar voor planningsproblemen bij enkelvoudige projecten met hulpmiddelenbeperkingen. Zijn methode biedt aldus geen oplossing voor ‘multiproject’ problemen. De misschien wel belangrijkste reden voor het verdwijnen van Pattersons testset als standaardset, is dat deze enkele jaren terug bestempeld werd als eerder ‘gemakkelijk’. Gezien er instanties bestaan voor hetzelfde aantal activiteiten met hogere waarde voor de hulpmiddelenfactor en een lagere waarde voor de hulpmiddelenkracht, kan de Patterson testset niet langer beschouwd worden als referentiepunt.
Deel II
59
Fasetransities in projectplanning
Onderstaande tabel toont een overzicht van de belangrijkste bijdragen uit de literatuur wat betreft netwerkgeneratoren.
Jaar van publicatie
Auteur(s)
1993
Demeulemeester, dodin en Herroelen
1995
Kolisch, Sprecher en
netwerkgenerator
pijlenvoorstelling
ProGen
Drexl 1995
Schwindt
ProGen/Max
1996
Agrawal, Elmaghraby en Herroelen
DAGEN
Vanhoucke, Demeulemeester en Herroelen
RanGen 1
Vanhoucke, Coelho en Tavares
RanGen 2
2002
2003
beschrijving
topologisch + hulpmiddelen
Pijlenvoorstelling CI knooppuntenvoorstelling Knooppuntenvoorstelling
Figuur 2. 8: netwerkgeneratoren in de literatuur
Demeulemeester et al. (1993) presenteerden als eersten in de literatuur een netwerkgenerator voor projectplanningsproblemen. Het betreft een generator van willekeurige netwerken in pijlenvoorstelling. Deze netwerken kunnen sterk willekeurig genoemd worden omdat ze ad randum kunnen gegenereerd worden uit alle mogelijke netwerken met precies omschreven knooppunten en pijlen. Elke netwerkstructuur heeft dus exact dezelfde waarschijnlijkheid om gecreëerd te worden. Door de specifieke methode die nodig is voor deze willekeurigheid kunnen andere netwerkmaatstaven, zoals overtolligheid, niet geobserveerd worden (Schwindt, 1996).
Zowel Kolish et al. (1995) als Vanhoucke et al. (2002) zien twee grote nadelen aan deze netwerkgenerator. Naast het aantal activiteiten en volgorderelaties kunnen immers geen andere karakteristieken omschreven worden om de morfologische structuur van een netwerk te beschrijven. Bovendien zijn zowel het aantal hernieuwbare hulpmiddelentypes als de hulpmiddelenbeschikbaarheid en -vereisten constant of geput uit vooraf gecodeerde distributies. Beiden hebben dan ook een andere netwerkgenerator voorgesteld, die zowel rekening houdt met morfologische als met hulpmiddelen gerelateerde maatstaven.
Deel II
60
Fasetransities in projectplanning
ProGen (Kolisch et al., 1995), een netwerkgenerator voor netwerken in knooppuntenvoorstelling, is geschikt voor de meervoudige RCPS-problemen. Drie concepten, namelijk de morfologische structuur, de hulpmiddelenfactor (RF) en de hulpmiddelenkracht (RS), worden in achting genomen. Deze drie parameters laten toe gemakkelijk en moeilijk oplosbare problemen van elkaar te onderscheiden. De gegenereerde instanties worden opgelost door middel van de geavanceerde Branch&Bound procedure. De resultaten weerspiegelen de sterke impact van de gebruikte parameters en de mogelijkheid om gemakkelijk en moeilijk oplosbare problemen van elkaar te onderscheiden. Kolisch et al. (1995) ontdekten dat, in het algemeen, de belovende resultaten uit vroegere gepubliceerde studies niet meer geldden. Zelfs de kleinste probleeminstanties blijken onoplosbaar met de optimale oplossingsalgoritmes uit de literatuur.
Schwindt (1996) heeft deze netwerkgenerator uitgebreid tot ProGen/Max dat drie verschillende types RCPS problemen aankan met minimale en maximale tijdspeling. Wat betreft het genereren van gegevens en construeren van niet cyclische netwerkstructeren hanteert ProGen/Max dezelfde methode als ProGen. Het genereren van vraag naar en beschikbaarheid van hulpmiddelen wordt bijna zonder enige aanpassing overgenomen van ProGen.
Agrawal et al. (1996) legden de nadruk op de complexiteitsindex (CI) als meeteenheid voor de netwerkcomplexiteit. Als gevolg ontwikkelden zij DAGEN, een netwerkgenerator gebaseerd op de pijlenvoorstelling, waarbij de meeteenheid van complexiteit op voorhand dient ingesteld worden. CI is een meeteenheid van de niet-conformiteit van een netwerk tot de serie/parallel topologie. Agrawal et al. Geloven dat de CI een belangrijke parameter is die een dimensie toevoegt aan de maatstaf voor de hardheid van een netwerk. Dit werd reeds bevestigd door De Reyck en Herroelen (1993). DAGEN volgt een methode in drie stappen (Herroelen en Demeulemeester, 1996). Eerst wordt het zogenoemde skeletnetwerk gegenereerd voor de gespecifieerde complexiteitsindex (CI). Vervolgens worden modules voor extra knopen en pijlen (activiteiten en volgorderelaties) achtereenvolgens in het skelet of in het laatste netwerk gevoegd zodat de CI van het resulterende netwerk ongewijzigd blijft. Uiteindelijk worden dan de waarden voor de verschillende parameters toegevoegd, zoals duurtijd en hernieuwbare of niet hernieuwbare hulpmiddelen.
Demeulemeester et al. (2002) menen dat zowel ProGen, ProGen/Max als DAGEN niet sterk willekeurig kunnen worden genoemd. Deze netwerkgeneratoren garanderen immers niet dat de
Deel II
61
Fasetransities in projectplanning
morfologische structuur een willekeurige selectie betreft van de ruimte van alle mogelijke netwerken die voldoen aan de vooraf omschreven inputparameters. Zij stelden dan ook een nieuwe knooppunt netwerkgenerator voor, namelijk RanGen 1. Deze bevat een betrouwbare set van complexiteitsmaatstaven (CNC), die in sterke relatie staan met de hardheid van verschillende planningsproblemen. Deze generator garandeert netwerken met vooraf bepaalde ordekracht (OS). Ze slaagden er bovendien in een willekeurige knooppuntnetwerkgenerator te creëren met vooraf gespecificeerde waarden voor de complexiteitsindex (CI).
Vanhoucke et al. (2002) ontwikkelden RanGen 2, gebaseerd op acht complexiteitsmaatstaven die de morfologische structuur van een netwerk beschrijven. Zes daarvan werden ontleend aan Tavares et al; (1999), maar werden deels of volledig aangepast. Het betreft de volgende maatstaven:
I1
: probleemgrootte
Aantal activiteiten (n)
I2
: serie/parallel indicator
Meet de dichtheid van een netwerk tot een serie/parallel grafiek voor knooppuntnetwerken
I3
: activiteitsdistributie
Beschrijving verdeling van activiteiten doorheen netwerk
I4
: korte, directe voorrangsrelatie
Meet het aantal korte, onmiddellijk voorgaande relaties (l = 1)
I5
: lange, direct voorrangsrelatie
Meet het aantal lange, onmiddellijk voorgaande relatie (l > 1)
I6
: morfologische slack
Bepaalt morfologische slack voor elke activiteit
OS
: Ordekracht
Zie 1.2.
CNC : coëfficiënt voor netwerkcomplexiteit
Zie 1.1.
Het ontwikkelingsproces van RanGen 1 steunt op vooraf gespecificeerde waarden voor I1 en OS. Voor RanGen 2 geldt dit voor I1 en I 2 . Beide netwerkgeneratoren volgen dezelfde logica, namelijk het verwijderen van volgorderelaties om netwerken te genereren. Het fundamentele verschil is dat RanGen 2, wanneer reeds een netwerk gevonden werd met vooropgestelde waarden voor I1 en I 2 , deze verwijdering nog een tijdje blijft doorvoeren waardoor netwerken gegenereerd worden met zelfde waarden voor I1 en I 2 maar met een andere morfologische structuur.
Deel III
62
Onderzoek
IV. ONDERZOEK
Bedoeling hier is de prestaties van enkele prioriteitsregels, zowel enkele opgenomen in het projectmanagement softwarepakket Primavera Project Planner 3.1 als enkele sterk aanbevolen in de literatuur, te onderzoeken. Bovendien zal ook de impact van de zes eerder besproken morfologische indicatoren nagegaan worden. In een eerste sectie wordt een beschrijving gegeven van de werking van en opties in Primavera Project Planner 3.1. Onder meer de opties ingeval van hulpmiddelenbeperkingen en de verschillende aangeboden prioriteitsregels worden besproken. Vooreerst werd een testset van 3040 problemen gegenereerd met behulp van de netwerkgenerator RanGen 2. De gebruikte parametersettings worden weergegeven in sectie 2. De geprogrammeerde prioriteitsregels werden vervolgens toegepast om de gegenereerde probleeminstanties op te lossen. De optimale oplossing werd berekend aan de hand van de branch&Bound-procedure van Demeulemeester en Herroelen (1992) De normale en maximale hulpmiddelenbeschikbaarheid dient vooraf ingesteld te worden. Dit wordt voorgesteld door het interval k, waarbij k=0 de normale beschikbaarheid betreft en k=1 de maximale. Dit zal gedaan worden voor verschillende waarden om de invloed daarvan na te gaan. Bovendien wordt ook de impact nagegaan van de hulpmiddelenrestricitiviteit. Voor het onderzoek werd een Intel PC Pentium II gebruikt, onder het operatiesysteem Windows 1998.
MS
Deel III
63
Onderzoek
1. Hulpmiddelennivellering in Primavera 3.1
Primavera genereert een plan gebaseerd op de berekeningen van het kritieke pad en wijst prioriteiten toe aan de projectactiviteiten op basis van deze CP-berekeningen. Deze berekeningen op basis van het kritieke pad werden gemaakt in de veronderstelling dat hulpmiddelen ongelimiteerd beschikbaar zijn. Primavera start dus met plannen, zal daarna het kritieke pad berekenen en zal uiteindelijk overgaan tot hulpmiddelennivellering.
Primavera heeft een aantal gegevens nodig om een project te nivelleren, namelijk startdata, einddata in geval van een project met een vastgelegd einde, normaal en maximaal hulpmiddelengebruik en hulpmiddelengebruik voor elke activiteit. Primavera bevat echter niet de mogelijkheid het minimaal hulpmiddelengebruik te specifiëren. Bijgevolg wordt daarmee ook geen rekening gehouden bij het nivelleren, wat kan leiden tot een hogere projectduur dan nodig. Primavera biedt verschillende opties bij het nivelleren van een project (Primavera Reference Manual, 1999):
Figuur 3. 1: opties voor hulpmiddelennivellering in Primavera 3.1
§
Voorwaarts nivelleren/achterwaarts nivelleren (‘forward / backward level’)
Deel III
64
Onderzoek
Wanneer gepland wordt, gebruik makend van de vroege data, spreekt men over voorwaarts nivelleren. Voorgaande activiteiten worden genivelleerd voor hun opvolgers. Primavera nivelleert van de eerste activiteit in het netwerk zonder voorgaande activiteiten tot de laatste zonder opvolgers. Bij Achterwaarts nivelleren wordt het project gepland aan de hand van late data. Het nivelleren start met de laatste activiteit zonder opvolgers en eindigt aan het begin van het netwerk. Primavera benoemt deze handeling als ‘nivelleren’, in realiteit komt deze actie neer op wat gekend is als het oplossen van het RCPS-probleem.
§
Smoothing20 Bedoeling van deze optie is een meer uniform profiel van hulpmiddelengebruik te bekomen. Primavera controleert tijdens het nivelleren of de hulpmiddelenvereisten de normale limiet overschrijden. Indien dit het geval is dan zal Primavera in normale omstandigheden de activiteit uitstellen zolang positieve ‘float’ 21 aanwezig is. Wanneer men wil nivelleren zal men echter het aantal hulpmiddelen aanpassen. Hier biedt het softwarepakket drie opties:
1) None: Primavera zal de maximale hulpmiddelenbeschikbaarheid veronderstellen. 2) Non-time constrained: Primavera veronderstelt een stijging van de hulpmiddelenbeschikbaarheid van 10% van het verschil tussen de normale en maximale limiet. 3) Time constrained: Primavera
veronderstelt
het
dubbel
van
het
maximum
van
de
hulpmiddelenbeschikbaarheid.
Men kan zich echter wel de vraag stellen in welke mate er genivelleerd wordt tijdens dit proces. Wanneer immers geen spelingruimte meer beschikbaar is, zal de hulpmiddelenbeschikbaarheid verhoogd worden, volgens één van de drie methodes. Gezien deze evaluatie per activiteit gebeurt is de kans klein
20 21
Letterlijk: het effenen, glad maken van het hulpmiddelenprofiel spelingruimte
Deel III
§
65
Onderzoek
Prioritizering Tijdens het plannen stelt Primavera een lijst op van activiteiten in topologische volgorde. Wanneer twee of meer activiteiten terzelfdertijd kunnen gepland worden, zal beroep gedaan worden op een prioriteitsregel om een activiteit voorrang te geven. Die activiteit met de hoogste waarde voor de prioriteitsregel kan als eerste gepland worden. Primavera biedt keuze tussen meerdere prioriteitsregels (Figuur 3.2). Wanneer de gebruiker echter van deze mogelijkheid geen gebruik maakt, nivelleert Primavera automatisch aan de hand van ‘late start’. Wanneer twee activiteiten tezelfdertijd kunnen gepland worden, gebruikt Primavera ‘total float’ om te beslissen welke activiteit voorrang krijgt om gepland te worden.
Figuur 3. 2: prioriteitsregels in Primavera 3.1
Bij figuur 3.2 dient echter wel opgemerkt worden dat vele van deze prioriteitsregels niet geschikt zijn voor het nivelleringsproces. Vele slaan niet zozeer op het plannen zelf, maar eerder op de uitvoering. Een voorbeeld van zo’n prioriteitsregel is ‘remaining duration’. Maar zoals McCray et al. stellen: “De impact van heuristieken mag dan enorm zichtbaar zijn in de initiatie- en
Deel III
66
Onderzoek
planningsfase, de positieve invloed van deze heuristieken mag niet onderschat worden in de uitvoerings-, controle- en eindfase”.
Tijdens het plannen van hulpmiddelen plan Primavera enkel activiteiten wanneer de hulpmiddelenvereisten kunnen voldaan worden. Om dit te bereiken is het mogelijk activiteiten uit te stellen of naar voren te brengen. Dit proces gebeurt door middel van de voorwaartse procedure. De gebruiker kan echter ook opteren voor de achterwaartse methode. Primavera maakt gebruik van een algoritme om dit proces door te voeren. In een eerste stap worden de activiteiten zonder conflicten gesorteerd. Indien deze tegelijkertijd klaar zijn om gepland te worden, wordt een prioriteitsregel toegepast. Wanneer deze laatste nog steeds een gelijke situatie oplevert, geeft Primavera voorrang aan de hand van het activiteitsnummer. Initieel worden de normale hulpmiddelen beschouwd (stap 2). Hulpmiddelen die gebruikt worden door de bezige activiteiten worden uit de beschikbare hulpmiddelenpool gehaald. Vervolgens wordt gecontroleerd of er voldoende reserves hulpmiddelen aanwezig zijn voor de volledige duur van de activiteiten (stap 3). Indien dit het geval is, wordt de activiteit gepland en wordt terug overgegaan naar de eerste stap van het algoritme. Zoniet wordt nagegaan of de activiteit enige spelingruimte kent. Zo kan de start van de activiteit immers uitgesteld worden met één werkperiode, waarna de hulpmiddelenbeschikbaarheid opnieuw dient nagegaan worden Is die voldoende kan terug overgegaan worden naar stap 1. Is dit niet het geval wordt stap 4 herhaald. Wanneer de activiteiten geen of niet voldoende spelingruimte bevatten zal men overgaan tot het verhogen van de van de hulpmiddelenbeschikbaarheid. Hoe hoog die wordt ingesteld hangt af van de gekozen ‘smoothing’ optie. Daarna kan terug overgegaan worden naar stap 3. Indien stap 5 bereikt wordt en deze reeds eerder bereikt werd wordt onmiddellijk overgegaan tot stap 6. Het blijkt niet mogelijk te zijn de activiteit te plannen binnen de spelingruimte, zelfs niet met maximale hulpmiddelenbeschikbaarheid. De activiteit wordt dus uitgesteld voorbij de spelingruimte, vanaf het moment dat voldoende hulpmiddelen voorhanden zijn. Wanneer echter nooit voldoende hulpmiddelen gevonden werden, wordt de activiteit gepland op de oorspronkelijke vroege startdatum en komt een waarschuwingsboodschap met de melding dat de activiteit niet kon gepland worden.
Kathab en Søyland (1998) toonden aan dat de standaard procedure gevolgd door Primavera bij het nivelleren van projectactiviteiten in het geval van beperkte hulpmiddelen niet steeds de beste oplossing biedt. Zij onderzochten dit aan de hand van vier bouwprojecten, elk met een
Deel III
67
Onderzoek
verschillende grootte, complexiteit en hulpmiddelenbeschikbaarheid. Elk van de projecten werd genivelleerd op basis van ‘algemeen arbeidsinspanning’. Als resultaat vonden zij dat hun gebruikte prioriteitsregel significant beter scoorde dan de op CPMgebaseerde standaard prioriteitsregel uit Primavera. Voor één van hun projecten, met een hulpmiddelenniveau van vijf man, was het met hun prioriteitsregel bijvoorbeeld mogelijk het project 18 dagen eerder te voltooien dan met de standaard prioriteitsregel uit Primavera. Voor een hulpmiddelenniveau van zes man bedroeg dit 30 dagen. Kathab en Søyland concludeerden dan ook dat projecten niet zouden mogen genivelleerd worden op basis van de standaard aangeboden prioriteitsregels in Primavera. De resultaten hangen sterk af van de gekozen prioriteitsregels en bijgevolg van de ervaring van de projectplanner
Deel III
68
Onderzoek
2. Netwerkgeneratie met behulp van RanGen 2
De netwerkgenerator RanGen 2 werd gebruikt om testinstanties te genereren die dan later in het onderzoek zullen gebruikt worden om onder andere de prioriteitsregels uit Primavera te testen. Het aantal activiteiten (I1 ) werd vast gelegd op 30 en het aantal hulpmiddelen bedraagt vier. De impact van de hulpmiddelenrestricitiviteit (RC) werd nagegaan door deze te laten variëren tussen 0.25, 0.5 en 0.75. RanGen 2 vereist de input van I1 en I2 , waarna de andere indicatoren, I3 tot I6 veranderd kunnen worden. In bijlage 1.2. kan een lijst gevonden worden van combinaties van indicatoren en RC waarvoor geen netwerken konden gegenereerd worden. In onderstaande tabel zijn de gekozen parametersettings voor het onderzoek opgenomen. Per setting werden telkens 50 000 netwerkinstanties gegenereerd.
Hulpmiddelen restricititeit (RC)
0.25; 0.5; 0.75
I1
30
I2
0.25; 0.5; 0.75
I3
[0-0.25]; [0.26-0.5]; [0.51-0.75]; [0.76-1]
I4
[0-0.25]; [0.26-0.5]; [0.51-0.75]; [0.76-1]
I5
[0-0.25]; [0.26-0.5]; [0.51-0.75]; [0.76-1]
I6
[0-0.25]; [0.26-0.5]; [0.51-0.75]; [0.76-1]
Figuur 3. 3: gebruikte parametersettings netwerkgenerator RanGen 2
2304 mogelijke combinaties (32 *44 ) werden aldus onderzocht. Telkens werden tien netwerken bewaard. Uiteindelijk werden 3040 testinstanties bekomen. Een schematisch voorbeeld van zo’n gecreëerd netwerk is te vinden in bijlage 1.3.
Er wordt aldus een groot aantal netwerken gegenereerd met verschillende combinaties van indicatoren. Dit onderzoek illustreert de relaties en afhankelijkheden van de verscheidene indicatoren. De resultaten kunnen best besproken worden aan de hand van spreidingscurves. Deze geven de spreiding van de netwerken weer voor alle mogelijke combinaties van twee indicatoren.
Vanhoucke et al. (2003) wijzen op het belang rekening te houden met de sterke willekeurigheid tijdens het interepreteren van dergelijke resultaten. Een sterk willekeurig netwerkgenerator kan willekeurig netwerken genereren uit de ruimte van alle mogelijke netwerken met een
Deel III
69
Onderzoek
gespecificeerd aantal activiteiten en volgorderelaties. Als de gegenereerde netwerken slechts en klein deel van deze gehele ruimte bedekken kan slechts een zeer beperkt aantal mogelijke netwerken gegenereerd worden. Bijgevolg slaagt de netwerkgenerator er niet in sterk willekeurig op te treden. Vandaar dat hoe meer de spreidingcurves het domein bedekken, hoe efficiënter de netwerkgenerator is.
Er moet echter wel opgemerkt worden dat de resultaten ietwat vertekend kunnen zijn ten gevolge van de gekozen settings van dit experiment. Dit is bijvoorbeeld het geval wanneer I2 wordt uitgezet in functie van een andere indicator. Zoals eerder vermeld werden enkel netwerken gegenereerd met I2 -waarden in stappen van 0.25. Desalniettemin kunnen ook tussen deze waarden netwerken gegenereerd worden en zou de grafiek dus als een vollere zwarte figuur moeten gezien worden die zo goed als het gehele domein van mogelijke netwerken beslaat.
I2 vs I3 I2 vs I4 1
1
0,8
0,8 0,6
I4
I3 0,4
0,6 0,4 0,2
0,2
0
0 0
0,25
0,5
0,75
0
1
0,25
I2 vs I5
0,75
1
0,75
1
I2 vs I6 1
1 0,8
I5
0,5 I2
I2
0,8
0,6
I6
0,4
0,6 0,4 0,2
0,2 0
0 0
0,25
0,5
0,75
I2
1
0
0,25
0,5
I2
Figuur 3. 4: relatie tussen I2 en overige morfologische indicatoren
Voor een lage waarde van I2 en een hoge waarde van I3 konden geen netwerken gevonden worden. Als I2 groter wordt, kan dit wel. Hetzelfde geldt voor I4 . Inderdaad, wanneer de meerderheid van activiteiten in parallel voorkomt (lage I2 -waarde, worden die ook gekenmerkt door korte (l=1) directe volgorderelaties (lage I4 -waarde). Wat betreft I5 en I6 bedekt RanGen 2 zowat het gehele domein. Merk op dat de lijnen het gevolg zijn van de gekozen parametersettings voor het onderzoek. Netwerken met activiteiten vooral in
Deel III
70
Onderzoek
serie en netwerken met activiteiten vooral in parallel kunnen dus zowel met veel als met weinig lange voorgaande relaties (l>1) gegenereerd worden. Netwerken waarin alle activiteiten een maximale waarde behaalden voor de morfologische spelingruimte (lage I6 -waarde) daarentegen konden niet gegenereerd worden.
I3 vs I4
I3 vs I5
1
I4
1
I5
0,5
0,5
0
0 0
0,2
0,4
0,6
0,8
0
1
0,4
I3
I3
I3 vs I6
I4 vs I5
1
0,6
0,8
1
0,6
0,8
1
0,6
0,8
1
1
0,8
I6
0,2
0,8
0,6
I5
0,4 0,2
0,6 0,4 0,2
0
0 0
0,2
0,4
0,6
0,8
1
0
0,2
0,4
I3
I4
I4 vs I6
I5 vs I6
1
1
0,8
I6
0,6
I6
0,5
0,4 0,2
0
0
0
0
0,2
0,4
0,6
0,8
0,2
0,4
1
I5
I4
Figuur 3. 5: relaties tussen morfologische indicatoren
RanGen 2 vertoont duidelijk een driehoek wanneer de relatie tussen I4 en I5 grafisch voorgesteld wordt. Het is niet mogelijk netwerken te genereren met hoge waarden voor I4 en lage waarden voor I5 . Dit komt omdat een groot aantal lange volgorderelaties (lage I5 -waarde) leidt tot een klein aantal korte volgorderelaties (hoge I4 -waarde). Ook voor de relatie tussen I4 en I6 kan een driehoek terug gevonden worden. Netwerken met een klein aantal korte volgorderelaties (hoge I4 -waarde) kunnen immers enkel gegenereerd worden wanneer deze gepaard gaan met veel activiteiten zonder morfologische spelingruimte (hoge I6 -
Deel III
71
Onderzoek
waarde). Wat betreft de relatie tussen I5 en I6 , kunnen we zien dat RanGen 2 bijna het gehele domein van mogelijke netwerken bedekt. Merk echter op dat de netwerken voor de drie laatste grafieken slechts in stappen van 0.1 uitgezet werden. Deze grafieken dienden dus als meer doorlopend beschouwd te worden.
Deel III
72
Onderzoek
3. De onderzochte prioriteitsregels
Eerder werd reeds opgemerkt dat vele beschikbare prioriteitsregels uit Primavera niet geschikt zijn voor het RCPS-probleem. Vele dienen ook ingezet te worden tijdens uitvoering en controle van het project. Om deze reden werden enkel de meest relevante prioriteitsregels uit dit softwarepakket geselecteerd. Ze werden vervolgens aangevuld door enkele prioriteitsregels waarvan we uit de literatuur weten dat ze bij de best presterende behoren. In totaal werden 11 verschillende prioriteitsregels toegepast om de activiteiten te plannen:
P1.
: laagste duurtijd eerst
P2.
: hoogste duurtijd eerst
P3.
: hoogste hulpmiddelenvraag eerst
P4.
: laagste hulpmiddelenvraag eerst
P5.
: laatste starttijd eerst
P6.
: laatste eindtijd eerst
P7.
: willekeurig
P8.
: laagste totale spelingruimte (‘float’) eerst
P9.
: meest totale (direct+indirect) voorafgaande activiteiten eerst
P10.
: meest totale direct voorafgaande activiteiten eerst
P11.
: grootste gewicht van positie in rangschikking eerst
De werking en voorbeelden van prioriteitsregels tijdens het plannen werden reeds uitvoerig beschreven in deel II. Ik verwijs dan ook graag naar dit deel voor enkele analyses van prioriteitsregels voorgesteld in de literatuur. Voor een overzicht van de meest gebruikte en beste prioriteitsregels voorgesteld in de literatuur verwijs ik naar Kolisch (1996).
Vooreerst werden de algemene prestaties van de elf prioriteitsregels nagegaan. Zowel het aantal bereikte oplossingen en de gemiddelde afwijking van de optimale oplossing werden onderzocht wanneer de hulpmiddelenbeschikbaarheid ingesteld wordt op maximaal ingeval van conflict (none) en met k tussen 0 en 1. Telkens wordt een onderscheid gemaakt tussen de prestatie van de prioriteitsregels voor de voorwaartse procedure en de achterwaartse (FH en BH). De resultaten blijken uit onderstaande grafieken.
Deel III
73
Onderzoek
Uit deze grafieken blijkt dat doorgaans de voorwaartse prioriteitsregels (FH) beter scoren dan de achterwaartse. Slechts drie prioriteitsregels vormen daar een uitzondering op. De zevende prioriteitsregel die gebaseerd is op willekeurigheid levert geen groot verschil tussen beide procedures. De negende en elfde prioriteitsregel scoren echter klaarblijkelijk beter voor de achterwaartse procedure. In bijlage 1.4 is een rangschikking van de prestaties van de 11 heuristieken terug te vinden. Daaruit blijkt dat, algemeen beschouwd, de prioriteitsregel ‘laagste duurtijd eerst’ de meest optimale is. Deze levert zowel voor de voorwaartse als achterwaartse prioriteitsregel de kleinste afwijking van de optimale oplossing, berekend aan de hand van de Branch&Bound procedure van Demeulemeester en Herroelen (1992). Deze prioriteitsregel bereikte voor 861 van de 3040 een optimale oplossing voor de voorwaartste procedure. Wat betreft de achterwaartse komt deze prioriteitsregel slechts op de tweede plaats. Daar neemt prioriteitsregel 9, gebaseerd op het totaal aantal volgorderelaties, de eerste plaats in. Plannen aan de hand van de hoogste duurtijd eerst blijkt in voor geen enkel geval een goede keuze te zijn.
Deel III
74
Onderzoek
4. Impact van de morfologische indicatoren Zoals eerder gezien heeft de morfologische structuur van een netwerk invloed op de oplossingsmogelijkheden van het RCPS-probleem. In dit onderzoek werd de impact van vijf morfologische indicatoren en de hulpmiddelenrestricitiviteit onderzocht. Voor elke indicator werd telkens de gemiddelde afwijking van het optimum en het percentage optimale oplossingen onderzocht voor de verschillende waarden van die indicator. De cijfergegevens bevinden zich in bijlage.
Voor k=[0,1] en optie ‘none’, bereikt I2 percentueel het meest aantal oplossingen wanneer die ingesteld is op 0.25, zowel voor de voorwaartse als de achterwaartse procedure. Hetzelfde geldt voor de gemiddelde afwijking van het optimum. Hoe groter de waarde van I2 , hoe minder optimale oplossingen gevonden werden en hoe groter de afwijking van het optimum wordt.
I3 bereikt eveneens het meest aantal optimale oplossingen en de kleinste gemiddelde afwijking van het optimum voor een kleine waarde (<0.25), zowel voor de voorwaartse als de achterwaartse procedure. Dezelfde conclusies kunnen getrokken voor I4 en I6. I5 daarentegen biedt percentueel het meest aantal optimale oplossingen voor waarden binnen het interval [0.26,0.5] wat betreft de voorwaartse procedure en voor waarden binnen het interval [0.51,0.75] wat betreft de achterwaartse. Ook voor de gemiddelde afwijking van het optimum bekomt I5 de beste oplossing wanneer die zich tussen 0.25 en 0.5 bevindt.
In tegenstelling tot I2 kent de hulpmiddelenrestricitiviteit de kleinst gemiddelde afwijking van het optimum voor een hoge waarde (0.75), dit voor beide procedures. Het meest aantal optimale oplossing voor de voorwaartse procedure worden eveneens gevonden wanneer RC=0.75. Voor de achterwaartse procedure is dit echter het geval wanneer RC=0.25.
In een tweede fase van het onderzoek werd de impact van k, de parameter die de hulpmiddelenbeschikbaarheid bepaalt, nagegaan. De gemiddelde afwijking van het optimum werd nagegaan voor zowel een lage waarde voor k (<0.5) als een hoge waarde voor k (>0.5). De cijfergegevens zijn terug te vinden in bijlage. De hulpmiddelenrestrictiviteit presteert wederom het best voor een hoge waarde, 0.75. Voor de voorwaartse prioriteitsregel werd daar een gemiddelde afwijking van het optimum gevonden van 13.48. Voor de achterwaartse is die gelijk aan 13.02. Het valt op dat deze cijfers serieus hoger
Deel III
75
Onderzoek
liggen dan het geval was voor k ∈[0,1]. Dit is een logisch resultaat. Hoe minder hulpmiddelen beschikbaar, hoe moeilijker het plannen en hoe groter de projectduur. De gemiddelde afwijking van het optimum is dan ook voor alle indicatoren hoger dan de vorige bekomen resultaten voor k ∈[0,1].
I2 wordt duidelijk beïnvloed door de hulpmiddelenbeschikbaarheid. Wanneer weinig hulpmiddelen beschikbaar zijn, biedt deze parameter de beste oplossing voor een hoge waarde, 0.75. Het omgekeerde geldt wanneer veel hulpmiddelen beschikbaar zijn. Dan is de gemiddelde afwijking van het optimum het kleinst wanneer I2 waarde 0.25 aanneemt. I3 toont toch een verschil met wat aangetoond kon worden voor het algemeen beeld. Daar werden de beste resultaten behaald voor I3 <0.25. Wanneer k een grote waarde heeft, dus hoger dan 0.5, bereikt I3 de kleinste gemiddelde afwijking van het gemiddelde wanneer die tussen 0.51 en 0.75 bedraagt. In overeenstemming met het algemeen beeld (k ∈ [0,1]) bereikt I4 de kleinste gemiddelde afwijking van het optimum voor waarden lager dan 0.25.Voor een lage waarde van k is er een onderscheid tussen de prestaties voor de voorwaartse en achterwaartse prioriteitsregels. De voorwaartse presteren best voor een waarde van I4 groter dan 0.75, de achterwaartse voor waarden van I4 tussen 0.5 en 0.75. Eveneens in overeenstemming met de resultaten voor een waarde van k tussen 0 en 1, bereikt I5 de kleinste gemiddelde afwijking van het optimum voor een waarde van I5 tussen 0.25 en 0.5 voor hoge waarden van k. Voor lage waarden van k is dit het geval voor waarden van I5 tussen 0.25 en 0.5. I tenslotte presteert goed voor hoge waarden (>0.75) wanneer veel hulpmiddelen beschikbaar zijn en voor lage waarden wanneer weinig hulpmiddelen voorhanden zijn.
Voor elke van de indicatoren dient opgemerkt te worden dat de gemiddelde afwijking van het optimum een stuk hoger ligt wanneer weinig hulpmiddelen beschikbaar zijn dan wanneer die overvloedig aanwezig zijn.
76
V.
Besluit
BESLUIT
Projectmanagement is geen recent fenomeen, doch gekenmerkt door een enorme evolutie. Reeds in de jaren 1950 werden methodes ontwikkeld om planning van projecten te ondersteunen zoals PERT en de methode van het kritieke pad. Deze laatste is een techniek waarbij het langst mogelijke pad in het activiteitennetwerk gezocht wordt. Deze activiteiten worden kritisch genoemd en kennen geen spelingruimte. Zij vormen samen aldus de kortst mogelijke projectduur. PERT daarentegen veronderstelt onzekere tijdsduur van activiteiten en zal dus aan de hand van een drietijdenschatting, namelijk de pessimistische, verwachte, en optimistische tijdsduur, een planning opstellen. Nadeel van deze twee methodes is echter dat beide uitgaan van onbeperkte hulpmiddelen, wat nogal vaak strookt met de realiteit. Vandaar dat steeds meer aandacht uitgaat naar wat men in de literatuur benoemt als RCPSP 22 , het probleem van plannen onder hulpmiddelenbeperkingen.
RCPS houdt het rangschikken van projectactiviteiten in, rekening houdend met volgorde- en hulpmiddelenbeperkingen, teneinde het vooraf bepaalde doel te bereiken, wat nogal vaak een zo kort mogelijke projectduur is. Het klassieke RCPS-probleem is gekenmerkt door een constante beschikbaarheid van hernieuwbare hulpmiddelen, een constante activiteitsduur eind-start volgorderelaties zonder tijdsintervallen. Daarbij wordt het activiteitennetwerk voorgesteld in de knooppuntvoorstelling waarbij activiteiten gevormd worden door knooppunten en de volgorderelaties voorgesteld worden door pijlen. Er zijn echter reeds vele varianten op dit probleem ontwikkeld. Zo kan men onderscheid maken tussen enkelvoudige en meervoudige RCPSproblemen, wat bepaald wordt door het al dan niet op meer dan één manier uitvoerbaar zijn. Daarenboven kunnen verschillende soorten volgorderelaties bestaan, namelijk start-start, starteinde, einde-start en einde-einde relaties. Bovendien kan het tijdsinterval tussen het begin (einde) van de ene activiteit en het einde (begin) van de volgende activiteit verschillen. Ook de beschikbaarheid en het gebruik van hulpmiddelen kunnen variëren. Tenslotte kan nog een onderscheid gemaakt worden tussen activiteiten die al dan niet kunnen onderbroken worden. Wanneer dit probleem nog eens nagegaan wordt voor een groep van projecten dan leidt dit vanzelfsprekend tot een waaier van varianten.
Voor het oplossen van dit probleem werden reeds meerdere procedures voorgesteld. Enerzijds exacte procedures die leiden tot optimaliteit maar eerder complex zijn en een omvangrijke 22
‘resource constrained project scheduling problem’
77
Besluit
oplossingstijd vergen, anderzijds heuristische procedures die leiden tot suboptimale oplossingen maar gemakkelijk en vlot toepasbaar zijn. Voorbeelden van de eerste zijn lineair en integer programmeren, beide wiskundige beslissingstechnieken. Wat betreft de heuristische procedures moet een onderscheid gemaakt worden tussen meta-heuristieken en heuristieken gebaseerd op prioriteitsregels. De genetische algoritmes, ‘Tabu Search’ en ‘Simulated Annealing’ behoren tot de meta-heuristieken en zijn varianten op de lokale zoekmethodes, die toegepast worden om initële oplossingen te verbeteren. Dit gebeurt aan de hand van opeenvolgende bewerkingen die een oplossing omzetten in een andere. De focus van deze scriptie ligt echter op de heuristieken die gebaseerd zijn op prioriteitsregels, wat ook de meest voorkomende zijn.
De heuristische procedures gebaseerd op prioriteitsregels bestaan uit twee componenten, het (de) planningsschema(s) en de prioriteitsregel(s). Een planningsschema bepaalt hoe een plan wordt opgebouwd en vertrekt van een deelplan dat stapsgewijze wordt verhoogd. Tijdens elke fase bepaalt het plan de set van activiteiten die in aanmerking komen om gepland te worden. Het parallelle planningsschema zal, in tegenstelling tot het seriële, de set activiteiten herordenen wanneer hulpmiddelenbeperkingen geëvalueerd worden. Het zijn de prioriteitsregels die vervolgens voorrang verlenen aan een bepaalde activiteit wanneer meerdere tegelijk klaar zijn om gepland te worden. Uit meerdere studies bleek dat het parallelle planningsschema tot betere resultaten leidt dan het seriële.
Vanzelfsprekend dient bij het plannen van activiteiten rekening gehouden worden met bepaalde volgorderelaties. Bepaalde activiteiten vereisen immers soms andere, voorbereidende activiteiten. Wanneer activiteiten terzelfdertijd kunnen gepland worden maar niet voldoende hulpmiddelen aanwezig zijn, dient beroep gedaan te worden op prioriteitsregels. In de literatuur werden deze reeds uitvoerig geanalyseerd. Minimale spelingruimte, late eindtijd en vroege starttijd van activiteiten zijn voorbeelden van vaak toegepaste en goed presterende prioriteitsregels. Alle commerciële projectmanagement softwarepakketten wijzen hulpmiddelen toe met behulp van een oplossingmethodologie gebaseerd op prioriteitsregels. Men is er echter tot op heden nog niet in geslaagd om op een objectieve manier een passende prioriteitsregel te selecteren om hulpmiddelenbeperkte projecten in te delen en er bestaan geen echte richtlijnen bij het selecteren van de beste prioriteitsregel voor een gegeven netwerk.
Naast het RCPS-probleem werd ook het probleem van hulpmiddelennivellering besproken. Hulpmiddelennivellering doet zich voor wanneer voldoende hulpmiddelen voorhanden zijn maar wanneer de schommelingen in het gebruik ervan afgevalkt dienen te worden. De meeste
78
Besluit
softwarepakketten gaan om met hulpmiddelennivellering en –planning op een simplistische manier. Vaak steunen ze op nogal onduidelijke heuristieken waarvan de details meestal niet voldoende uitgelegd worden in de handleiding.
Dit werk bevat een indeling en enkele vergelijkende studies van de verschillende projectmanagement softwarepakketten. De eenvoudige planningspakketten zijn vooral gericht op tijdplanning. De meer uitgebreide gaan ook dieper in op hulpmiddelenplanning en bevatten enkele aanvullende functionaliteiten, zoals risicoanalyse, links met spreadsheet programma’s en simulatiemogelijkheden.
De
meest
geavanceerde
pakketten
maken
naast
tijd-
en
hulpmiddelenplanning een koppeling mogelijk met MRP- en ERP-systemen. Uit de vergelijkende studies bleek dat het softwarepakket Primavera Project Planner tot de best presterende behoort, vandaar ook de keuze voor dit pakket voor het onderzoek van deze scriptie.
Deel III van deze scriptie gaat dieper in op de mogelijke fasetransities in projectplanning. De berekeningscomplexiteit van bepaalde problemen, zoals het RCPSP, kunnen variëren. Het zijn de ordeparameters van het netwerk die deze transities bepalen. Zowel morfologische als hulpmiddelen gerelateerde maatstaven dienen als ordeparameters. De eerste vertonen doorgaans continue ‘gemakkelijk-moeilijk oplosbaar’-fasetransities. De hulpmiddelen gerelateerde vertonen doorgaans ‘gemakkelijk-moeilijk-gemakkelijk oplosbaar’ fasetransities. Activiteitennetwerken en effecten van een probleemstructuur hebben een aanzienlijke invloed op de prestaties van algoritmes. Indien een maatstaf bestond voor de netwerkcomplexiteit zou dit de keuze tussen de algoritmes enorm vergemakkelijken. Vandaar dat in de literatuur reeds vele maatstaven voorgesteld werden. Deze proberen vooral informatie te verzamelen betreffende de grootte en morfologische structuur van het projectnetwerk en de beschikbaarheid van de verschillende types hulpmiddelen in relaties tot de vereiste hoeveelheid. Voorbeelden van de voorgestelde morfologische parameters zijn de coëfficiënt van de netwerkcomplexiteit, de ordekracht, en de complexiteitsindex. Wat betreft de invloed van deze parameters op het RCPS-probleem nemen auteurs soms een verschillende mening in. Voorbeelden van hulpmiddelen gerelateerde parameters zijn de hulpmiddelenfactor, de hulpmiddelenkracht en de hulpmiddelenrestricitiviteit. Opnieuw werd de impact weergegeven op het planningsprobleem onder hulpmiddelenbeperkingen.
Meerdere auteurs gingen de impact na van deze morfologische en hulpmiddelengerelateerde maatstaven op verschillende projectmanagement softwarepakketten. De resultaten van enkele van deze studies werden geïntegreerd in deze scriptie. Gezien de nogal uiteenlopende resultaten verwijs ik dan ook graag naar punt 5, deel III. Het onderzoek binnen deze scriptie gaat eveneens de impact
79
Besluit
na van enkele morfologische parameters, die uitvoerig beschreven worden in punt 1, deel III. Daartoe werden eerst probleeminstanties gegenereerd met behulp van de netwerkgenerator RanGen 2. Op die manier konden de waarden voor zes verschillende morfologische parameters en de hulpmiddelenrestricitiviteit ingesteld worden. Vervolgens werden elf prioriteitsregels, enkele uit Primavera Project Planner 3.1 en enkele voorgesteld in de literatuur, geprogrammeerd om deze probleeminstanties op te lossen.
Het onderzoek werd gevoerd voor de optie ‘none’ uit Primavera. Deze optie houdt in dat overgegaan wordt van normale naar maximale hoeveelheid hulpmiddelen wanneer zich conflicten voordoen. Eerst werd een globaal beeld geschetst van de prestaties van de elf prioriteitsregels. Daaruit bleek dat de prioriteitsregel ‘laagste duurtijd eerst’ zowel voor aantal optimale oplossingen als voor de gemiddelde afwijking van het minimum best scoorde. Deze heuristiek kwam echter op de tweede plaats qua aantal optimale oplossingen aan de hand van de achterwaartse procedure en werd voorgegaan door de prioriteitsregel gebaseerd op het aantal totale volgorderelaties.
Daarenboven werd de impact van de morfologische indicatoren nagegaan. Eerst gebeurde dit voor waarden van k, een parameter voor hulpmiddelenbeschikbaarheid, tussen 0 en 1. Daarbij zagen we dat voor I2 , I3 , I4 en I6 de beste resultaten behaald werden voor een lage waarde van deze indicatoren. I scoort het best voor waarden tussen 0.25 en 0.5. In tegenstelling tot de vijf morfologische indicatoren bereikte de hulpmiddelenrestrictiviteit het meest aantal optimale oplossingen en de kleinste gemiddelde afwijking van het optimum voor een hoge waarde (0.75).
Wanneer een vergelijking uitgevoerd werd tussen de resultaten voor lage en hoge waarden voor k, werd duidelijk dat naarmate k kleiner wordt, de probleeminstanties moeilijker op te lossen zijn. Er werden veel minder optimale oplossingen bereikt en de kleinste gemiddelde afwijking van het optimum ligt behoorlijk hoger wanneer weinig hulpmiddelen beschikbaar zijn. Voor de exacte resultaten verwijs ik graag naar deel III en de bijlages.
80
Bijlagen
Bijlage
81
Referenties
Bijlage 1. 1: Invloed van morfologische en hulpmiddelen gerelateerde parameters op zeven projectmanagement softwarepakketten (Kolisch, 1995)
# act.
CA Super Project 1.83
MS Project
10
Artemis Schedule Publisher 7.79
2.36
Primavera Project Planner 3.67
Project Manager Workbench 5.21
Project Time Scheduler Line 6 2.17 2.60
20
10.73
4.85
6.08
4.59
6.88
6.10
4.52
30
9.79
6.11
6.91
4.73
7.79
7.34
6.30
Percentuele afwijking in functie van het aantal activiteiten
# hulpm.
CA Super Project 2.93
MS Project
1
Artemis Schedule Publisher 6.84
3.02
Primavera Project Planner 3.01
Project Manager Workbench 4.45
Project Time Scheduler Line 6 2.52 2.75
2
12.08
5.17
5.82
4.99
6.67
6.48
4.86
3
8.04
4.37
6.74
4.59
8.97
6.23
5.47
Percentuele afwijking in functie van het aantal hulpmiddelen
RS
CA Super Project 8.25
MS Project
0.2
Artemis Schedule Publisher 14.71
9.76
Primavera Project Planner 8.31
Project Manager Workbench 12.40
Project Time Scheduler Line 6 11.67 5.86
0.5
8.63
3.83
4.43
3.76
5.54
4.15
4.25
0.7
7.07
1.73
2.79
1.75
3.27
1.75
3.59
Percentuele afwijking in functie van hulpmiddelenkracht (RS)
82
RF
CA Super Project 2.60
MS Project
0.5
Artemis Schedule Publisher 8.00
2.89
Primavera Project Planner 3.44
Project Manager Workbench 4.85
Project Time Scheduler Line 6 2.29 3.53
1
11.52
6.22
7.82
5.35
8.53
8.57
5.44
Percentuele afwijking in functie van de hulpmiddelenfactor (RF)
CNC
CA Super Project 4.98
MS Project
1.5
Artemis Schedule Publisher 9.87
5.83
Primavera Project Planner 4.80
Project Manager Workbench 7.01
Project Time Scheduler Line 6 5.56 4.55
2
9.65
3.84
4.88
3.98
6.36
5.29
Percentuele afwijking in functie van de netwerkcomplexiteit (CNC)
4.42
83
Bijlage
Bijlage 1. 2: combinaties van morfologische indicatoren waarvoor geen netwerken konden gegenereerd worden (RanGen2)
I2 = 0,25
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1 I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1 8 I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1 2 I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,750,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,750,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1 3 I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,750,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
84
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
RC
I2
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,750,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1 2 I3 I4 I5 I6
bijlage
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
RC
I2
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1 I3
I4
I5
I6
85
0,25 0,5 0,75
0,25 0,5 0,75
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
RC 0,25 0,5 0,75
RC 0,25 0,5 0,75
bijlage
0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,750,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1 3 I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,750,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
0,25 0,5 0,75
0,25 0,5 0,75
0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,750,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,750,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1 4
86
bijlage
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,750,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,750,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,750,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1 8 I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,750,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I2 = 0,5 RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
87
bijlage
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,750,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,750,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,750,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1 3 I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,750,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,750,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1 2 I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1 2
88
bijlage
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,750,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1 1 I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,750,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,750,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,750,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1 6
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
89
bijlage
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,750,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,750,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1 8 I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
I2 = 0,75 RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,750,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,750,51 - 0,75
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75
90
0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
0,76 - 1
0,76 - 1 2 I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,750,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
bijlage
0,76 - 1
0,76 - 1
0,76 - 1
0,76 - 1
0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,750,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1 2
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,750,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1 4 I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,750,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1 1 I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,750,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
91
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
RC
I2
bijlage
1 I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,750,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1 5 I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,750,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1 3
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,750,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1 9 I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,750,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1 7 I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,750,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1 I3
I4
I5
I6
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC
I2
I3
I4
I5
I6
92
bijlage
0,25 0,5 0,75
0,25 0,5 0,75
0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,750,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
0,25 0,5 0,75
0,25 0,5 0,75
0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,750,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1 3
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,750,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,750,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,750,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
RC 0,25 0,5
I2 0,25 0,5
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5
RC 0,25 0,5
I2 0,25 0,5
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1 4 I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1 1 I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5
93
bijlage
0,75
0,75
0,51 - 0,75 0,51 - 0,75 0,51 - 0,750,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
0,75
0,75
0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,750,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,750,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1 2 I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,750,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,750,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1 1
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
94
bijlage
RC 0,25 0,5 0,75
I2 0,25 0,5 0,75
I3 I4 I5 I6 0 - 0,25 0 - 0,25 0 - 0,25 0 - 0,25 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,26 - 0,5 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,51 - 0,75 0,76 - 1 0,76 - 1 0,76 - 1 0,76 - 1
95
Bijlage
Bijlage 1. 3: aantal bereikte optimale oplossingen en gemiddelde afwijking van de optimum voor de elf onderzochte prioriteitsregels. (none, k=[0,1])
H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11
afw FH OPT rank FH afw BH OPT rank BH 4,58 1 5,03 1 6,19 11 6,64 11 5,05 2 5,69 6 5,44 7 5,69 7 5,24 5 5,99 8 5,06 3 6,23 9 5,53 8 5,41 3 5,08 4 6,25 10 5,66 9 5,22 2 5,40 6 5,55 5 6,00 10 5,45 4 # opt FH
H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11
rank FH # opt BH rank BH 861 1 663 2 395 8 272 11 761 2 530 6 5,44 11 450 7 599 6 379 8 745 3 326 9 559 7 567 5 725 4 294 10 390 9 669 1 634 5 585 4 349 10 610 3
96
Bijlage
Bijlage 1. 4: impact van I2
H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11
#opt FH I2 0,25 #opt 51% 39% 45% 39% 44% 41% 38% 39% 31% 47% 35%
gem.
41%
GA FH 0,25 H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11
2,08 3,08 2,51 2,71 2,34 2,70 2,83 2,85 2,94 2,60 2,74
gem.
2,67
BH #opt FH I2 0,5 #opt 41% 11% 22% 13% 32% 28% 32% 14% 27% 25% 29% 23% 37% 16% 26% 23% 48% 13% 38% 21% 45% 13% 34%
18%
BH #opt I2 0,75 #opt BH 24% 22% 21% 10% 3% 4% 12% 15% 15% 10% 11% 11% 9% 7% 9% 10% 19% 4% 11% 12% 16% 8% 19% 4% 12% 5% 18% 11% 11% 17% 11% 2% 16% 12%
11%
GA BH GA FH 0,5 GA BH GA FH 0,75 GA BH 2,53 4,55 5,54 5,57 4,55 5,75 6,46 7,65 3,2 4,31 5,86 6,47 3 5,46 6,02 6,5 3,43 4,46 6,12 6,83 3,39 4,86 6,07 6,1 2,77 5,52 5,72 6,59 3,42 4,89 6,06 6,06 2,1 5,14 5,85 7,02 2,83 5,05 6,14 6,69 2,36 5,27 6,05 7,7 3,05
5,02
5,99
6,65
12%
5,67 7,52 6,53 6,51 6,89 7,4 6,22 7,43 6,04 6,23 6,27 6,61
97
bijlage
Bijlage 1. 5: impact van RC
H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 gem.
H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 gem.
#opt RC FH 0,25 BH #opt 29,51% 22,94% 12,25% 8,82% 25,20% 18,53% 15,98% 15,69% 18,73% 12,35% 23,92% 10,98% 17,25% 17,84% 23,14% 10,88% 11,57% 22,45% 20,59% 19,90% 10,20% 20,49% 18,94% gem. afw. 0,25 BH 4,72 6,44 5,34 5,62 5,58 5,28 5,73 5,35 5,96 5,60 6,39 5,64
16,44%
RC 0,5 BH #opt RC 0,75 BH 27,94% 19,51% 27,10% 22,70% 12,94% 9,71% 13,70% 8,30% 24,51% 15,39% 25,00% 18,10% 17,16% 14,12% 17,90% 14,20% 18,63% 12,75% 21,40% 12,20% 25,88% 10,59% 23,60% 10,50% 17,94% 18,04% 19,70% 19,80% 25,20% 8,63% 23,10% 9,30% 12,65% 19,90% 13,90% 23,20% 19,61% 18,63% 22,00% 19,00% 10,98% 18,24% 13,20% 21,20% 19,40%
GA 0,5
15,04% BH
20,05%
16,23%
5,07 6,70 5,78 5,61 6,06 6,33 5,46 6,24 5,27 5,59 5,48
4,68 6,30 5,19 5,57 5,32 5,18 5,67 5,14 5,76 5,58 6,15
GA 0,75 BH 5,25 4,34 6,80 5,81 5,93 4,61 5,89 5,13 6,17 4,83 6,37 4,72 5,50 5,17 6,45 4,75 5,40 5,24 5,70 5,01 5,61 5,46
4,76 6,36 5,29 5,52 5,69 5,94 5,21 6,00 4,95 5,30 5,20
5,78
5,51
5,91
5,47
5,01
98
bijlage
Bijlage 1. 6: impact van I3
H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 gem.
H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 gem.
#opt FH I3-1 31,59% 18,41% 26,10% 22,07% 22,07% 27,68% 21,95% 25,85% 15,24% 26,83% 14,88%
BH #opt I3-2 25,00% 29,84% 10,61% 13,11% 18,29% 25,66% 16,95% 17,62% 14,02% 20,90% 15,61% 24,67% 20,37% 20,00% 15,12% 24,18% 25,00% 14,26% 22,20% 21,15% 23,05% 12,05%
BH #opt I3-3 23,28% 23,58% 9,84% 10,45% 18,44% 26,12% 16,23% 13,28% 13,11% 21,19% 10,90% 21,34% 20,49% 15,37% 9,43% 21,49% 24,43% 11,94% 20,74% 16,72% 22,05% 10,60%
BH #opt I3-4 16,42% 24,24% 7,76% 4,24% 15,37% 17,88% 11,19% 10,30% 11,79% 6,36% 8,21% 22,42% 13,88% 9,70% 6,72% 22,42% 16,57% 3,33% 15,22% 13,33% 15,22% 2,73%
BH 19,39% 3,94% 15,15% 10,91% 7,88% 3,03% 16,67% 2,73% 15,76% 14,55% 14,55%
22,97%
18,75%
20,31%
17,18%
17,46%
12,58%
12,45%
11,32%
gem. afw. I3-1 4,05 5,80 4,97 4,81 4,93 4,80 5,10 4,88 5,15 4,78 5,62
BH 4,72 6,62 5,61 5,29 6,01 6,07 5,37 6,01 4,87 5,25 5,12
GA-2 4,56 6,19 5,06 5,39 5,16 5,09 5,50 5,12 5,63 5,45 5,99
BH 4,96 6,51 5,62 5,58 5,90 6,15 5,13 6,20 4,98 5,35 5,23
GA 3 4,87 6,24 4,70 5,77 5,05 5,10 5,64 5,05 5,67 5,53 5,93
BH 5,33 6,57 5,70 6,05 5,93 6,23 5,76 6,28 5,71 5,83 5,85
GA 4 5,39 7,03 5,92 6,55 6,73 5,54 6,48 5,51 7,01 6,48 7,15
BH 5,45 7,13 5,96 6,21 6,27 6,78 5,66 6,79 5,85 6,27 6,12
4,99
5,54
5,38
5,60
5,41
5,93
6,35
6,23
Opm.: I3-1: I3<0.25 I3-2: I3 ∈ [0.26-0.5] I3-3: I3 ∈ [0.51-0.75] I3-4: I3 ∈ [0.76-1]
GA = gemiddelde afwijking
99
bijlage
Bijlage 1. 7: impact van I4
H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 gem.
H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 gem.
#opt FH I4-1 29,69% 14,66% 26,82% 18,65% 22,06% 26,05% 19,37% 25,34% 14,17% 22,65% 13,54%
BH #opt I4-2 21,93% 25,24% 9,78% 9,29% 17,62% 21,43% 15,56% 13,81% 13,00% 15,00% 11,52% 20,95% 19,10% 15,71% 10,09% 20,48% 22,83% 10,24% 20,00% 16,90% 20,94% 7,38%
BH #opt I4-3 23,33% 25,00% 8,57% 11,11% 19,05% 21,11% 14,29% 15,00% 13,33% 15,56% 9,29% 17,22% 19,05% 20,56% 10,00% 16,11% 22,86% 13,33% 19,05% 17,22% 20,24% 7,78%
BH #opt I4-4 22,22% 22,86% 6,67% 4,29% 18,89% 16,67% 12,22% 8,57% 9,44% 7,62% 11,11% 21,43% 20,00% 11,43% 8,89% 21,43% 21,67% 3,33% 18,33% 12,86% 18,33% 0,95%
BH 17,14% 2,86% 10,00% 9,05% 8,10% 4,76% 10,95% 4,76% 10,48% 12,38% 10,95%
21,18%
16,58%
16,04%
16,28%
16,36%
15,25%
11,95%
9,22%
GA-1 FH 4,33 5,89 4,69 5,22 4,95 4,78 5,30 4,80 5,39 5,11 5,59
BH 4,85 6,39 5,42 5,49 5,72 5,92 5,20 5,96 5,05 5,36 5,26
GA 2 5,04 6,89 5,85 5,91 5,74 5,69 5,91 5,75 6,09 5,80 6,95
BH 5,29 7,16 6,18 5,98 6,49 6,97 5,79 6,95 5,35 5,82 5,65
GA 3 5,34 7,31 6,28 5,97 6,37 6,19 6,24 6,05 6,59 6,63 7,55
BH 5,71 7,32 6,16 6,41 7,02 7,00 6,07 6,89 5,73 6,14 5,87
GA 4 5,70 6,97 6,20 6,45 6,46 5,89 6,54 5,89 6,81 6,55 7,21
BH 5,81 7,33 6,87 6,40 6,82 7,19 6,01 7,11 6,20 6,23 6,46
5,10
5,51
5,96
6,15
6,41
6,39
6,42
6,59
100
bijlage
Bijlage 1. 8: impact van I5
H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 gem.
H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 gem.
#opt FH I5-1 27,95% 12,73% 25,45% 16,36% 18,41% 23,64% 18,18% 22,95% 12,50% 21,14% 11,36%
BH #opt I3-2 20,23% 33,39% 9,55% 15,42% 15,00% 28,64% 13,64% 19,32% 12,05% 22,20% 10,91% 28,47% 17,50% 20,34% 9,55% 27,46% 19,55% 14,07% 16,59% 22,88% 18,41% 13,73%
BH #opt I3-3 22,37% 26,29% 8,47% 12,81% 16,44% 24,04% 15,59% 15,96% 11,53% 19,55% 10,68% 23,60% 19,49% 18,43% 9,49% 23,26% 23,22% 12,02% 20,34% 21,57% 21,69% 10,56%
BH #opt I3-4 22,13% 27,41% 8,99% 11,96% 18,76% 23,75% 15,17% 17,05% 14,16% 19,02% 11,24% 23,48% 19,21% 17,41% 9,55% 22,77% 22,47% 12,95% 18,76% 19,11% 20,67% 19,11%
BH 21,88% 8,93% 17,68% 14,38% 11,88% 10,27% 18,04% 9,82% 21,70% 20,09% 20,09%
19,15%
14,81%
22,36%
16,30%
18,92%
16,47%
19,46%
15,88%
GA-11FH 4,58 6,18 4,97 5,65 5,24 5,05 5,74 5,10 5,69 5,39 5,87
BH 5,10 6,56 5,88 5,65 5,67 6,13 5,40 6,09 5,32 5,75 5,47
GA 2 4,12 5,55 4,36 5,11 4,75 4,56 4,99 4,58 5,27 4,90 5,39
BH 4,73 6,46 5,41 5,55 5,77 5,91 5,02 5,91 5,05 5,37 5,25
GA 3 4,75 6,56 5,33 5,72 5,48 5,31 5,76 5,25 5,89 5,52 6,33
BH 5,02 6,58 5,70 5,50 5,92 6,29 5,42 6,38 4,98 5,39 5,21
GA 4 4,69 6,23 5,22 5,32 5,32 5,14 5,54 5,20 5,67 5,57 6,11
BH 5,17 6,76 5,71 5,88 6,25 6,35 5,56 6,34 5,43 5,64 5,69
5,40
5,73
4,87
5,49
5,63
5,67
5,46
5,89
101
bijlage
Bijlage 1. 9: impact van de morfologische indicatoren voor k ∈[0,0.5] (optie ‘none’)
H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 gem.
H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 gem.
H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11
GA RC 0,25 10,74 50,84 10,84 11,37 11,37 13,96 11,59 22,85 8,34 10,46 8,31
BH GA RC 0,5 11,55 11,71 12,70 55,89 11,49 11,45 11,98 12,12 12,01 12,12 11,55 14,51 11,83 12,08 25,30 26,81 11,44 8,77 12,17 10,72 11,42 8,75
15,52
13,04
GA I2FH 0,25 GA 15,58 104,90 14,31 14,95 14,95 17,52 14,73 36,42 10,34 12,93 8,77 24,13
BH GA RC 0,75 11,71 11,13 13,03 13,98 12,02 11,04 12,75 11,98 12,08 11,98 12,11 14,03 12,22 11,79 28,94 34,38 11,96 8,78 12,71 10,59 11,94 8,55
16,81
BH GA FH 0,5 GA 15,95 14,81 14,90 65,52 14,21 13,71 15,04 15,14 14,65 15,14 14,69 17,80 14,79 15,28 37,68 40,68 12,32 10,95 13,77 14,03 12,50 10,74 16,41
21,25
13,77
13,48
BH 11,00 11,56 10,43 11,18 11,11 10,88 10,90 34,10 10,54 11,08 10,46 13,02
BH GA FH 0,75 GA BH 15,22 7,38 7,45 15,30 0,64 9,81 14,59 8,35 8,29 15,31 8,67 8,84 15,27 8,67 8,55 15,29 10,74 8,08 14,90 8,67 8,54 42,05 17,27 18,82 14,14 6,61 9,28 15,78 7,67 9,10 13,98 7,16 9,23 17,44
8,35
9,64
gem. afw. I3-1 11,29 42,81 10,74 11,37 11,37 13,35 11,29 28,65 8,29 10,12 7,94
BH 11,62 11,96 10,89 11,84 11,80 11,37 11,64 30,10 10,52 11,37 10,49
GA-2 11,15 39,56 11,14 11,70 11,70 14,19 11,76 28,05 8,51 10,33 8,39
BH 11,20 11,92 11,22 11,40 11,28 11,45 11,11 29,26 10,77 11,44 10,66
GA 3 12,12 47,05 11,70 12,86 12,86 15,49 12,77 30,31 9,27 11,74 9,28
BH 12,39 14,18 12,62 13,35 12,94 12,39 13,17 31,94 13,04 13,97 13,11
GA 4 9,31 24,27 10,74 11,29 11,29 13,43 11,47 21,31 8,63 10,41 9,07
BH 9,83 12,02 10,15 11,67 10,85 10,38 10,67 23,22 11,90 11,65 11,84
15,20
13,05
15,14
12,88
16,86
14,83
12,84
12,20
102
H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 gem.
H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 gem.
H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 gem.
bijlage
GA I4-1 FH 12,22 48,32 11,97 12,77 12,77 15,26 12,77 30,77 9,28 11,49 9,02
BH 12,49 13,29 12,19 12,90 12,60 12,50 12,57 32,21 12,07 12,88 12,04
GA 2 9,00 17,56 9,42 9,70 9,70 11,84 9,62 22,26 6,99 8,45 7,40
BH 8,96 10,39 9,44 9,75 9,94 9,41 9,34 23,75 9,39 10,04 9,37
GA 3 7,67 27,83 7,89 8,34 8,34 10,57 8,83 19,01 6,27 7,63 6,53
BH 7,44 9,09 7,52 8,23 8,28 7,68 8,36 19,80 7,51 7,99 7,43
GA 4 7,77 13,10 8,16 9,03 9,03 10,40 8,74 17,47 7,04 7,88 7,40
BH 8,47 10,36 9,17 9,82 9,20 8,68 9,41 19,41 10,58 9,98 10,36
16,97
14,34
11,08
10,89
10,81
9,03
9,64
10,49
GA I5-1 FH 11,76 45,06 11,86 13,01 13,01 15,57 13,13 29,70 9,56 11,62 9,25
BH 12,08 13,47 12,07 12,93 12,39 12,80 12,00 30,55 11,95 12,46 11,96
GA 2 12,39 50,44 11,91 13,02 13,02 15,41 12,83 30,24 9,25 11,43 9,00
BH 13,27 14,02 12,77 13,61 13,08 13,12 13,14 32,61 12,50 13,43 12,40
GA 3 11,26 37,85 11,35 11,93 11,93 14,08 11,89 27,45 8,82 10,63 8,60
BH 10,90 12,34 11,06 11,69 11,60 10,80 11,62 28,56 11,28 12,01 11,29
GA 4 10,30 35,38 10,22 10,65 10,65 13,04 10,73 26,53 7,79 9,72 7,97
BH 10,62 11,28 10,48 10,98 10,90 10,75 10,77 27,99 10,49 11,06 10,42
16,68
14,06
17,17
14,90
15,07
13,01
13,91
12,34
GA I6-1FH 12,11 66,54 12,08 13,03 13,03 15,67 13,08 30,54 9,27 11,43 8,68
BH 12,69 13,78 12,29 13,40 12,78 12,52 12,87 32,14 12,21 13,09 12,34
GA 2 12,78 53,20 12,21 13,25 13,25 15,61 13,11 30,71 9,57 12,03 9,26
BH 12,91 13,93 12,40 13,51 13,07 13,04 12,91 32,50 12,40 13,33 12,43
GA 3 10,79 38,22 11,07 11,65 11,65 14,07 11,72 27,79 8,58 10,44 8,53
BH 11,28 12,44 11,44 11,73 11,59 11,42 11,58 28,83 11,31 11,79 11,28
GA 4 9,40 11,84 9,23 9,66 9,66 11,68 9,68 23,45 7,23 8,57 7,63
BH 9,24 9,91 9,31 9,73 9,79 9,30 9,58 25,11 9,59 10,15 9,35
18,68
14,55
17,73
14,77
14,96
13,15
10,73
11,01
103
bijlage
Bijlage 1. 10: impact van morfologische indicatoren voor k ∈ [0.5,1] (optie ‘none’)
H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 gem.
H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11
gem.
BH 4,60 6,56 5,64 5,23 5,89 6,29 5,42 5,80 5,00 5,00 5,21
GA 0,5 4,55 6,63 5,48 5,37 5,69 5,28 5,77 5,92 5,95 5,95 6,38
BH 4,68 6,35 5,77 5,18 5,92 6,28 5,43 5,88 4,78 4,78 5,01
GA 0,75 4,24 6,12 4,91 5,31 5,18 4,92 5,23 5,35 5,34 5,34 5,65
BH 4,41 5,84 5,16 5,04 5,43 5,86 5,10 5,45 4,56 4,56 4,85
5,71
5,51
5,73
5,46
5,23
5,12
GA I2 FH 0,25 4,34 4,24 3,31 4,62 4,07 4,44 4,46 3,79 3,52 3,52 3,04
GA BH 4,46 4,22 3,90 4,56 4,50 4,76 4,06 4,57 3,56 3,56 3,67
GA FH 0,5 3,97 5,78 4,59 4,85 4,63 4,48 5,22 5,09 5,28 5,28 5,41
GA BH 4,17 5,74 5,04 4,61 5,42 5,72 4,78 5,32 4,45 4,45 4,62
GA FH 0,75 4,78 7,64 6,65 5,83 6,62 5,81 6,17 6,87 6,89 6,89 7,81
GA BH 4,84 7,35 6,44 5,70 6,43 6,94 6,12 6,39 5,45 5,45 5,79
3,94
4,17
4,96
4,94
6,54
6,08
gem.
H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11
GA RC 0,25 4,56 6,51 5,74 5,22 5,70 5,23 5,65 5,93 5,95 5,95 6,44
GA I3-1 4,50 6,45 5,33 5,19 5,29 5,31 5,47 5,28 5,43 5,43 5,91
BH 4,70 6,40 5,69 5,57 6,13 6,42 5,70 6,03 4,95 4,95 5,14
GA-2 4,32 6,45 5,43 5,32 5,54 5,21 5,65 5,76 5,64 5,64 6,07
BH 4,60 6,26 5,60 5,01 5,67 6,06 5,17 5,68 4,70 4,70 5,00
GA 3 4,35 6,07 4,97 5,01 5,26 4,70 5,16 5,68 5,71 5,71 6,12
BH 4,43 6,07 5,09 4,99 5,58 5,93 4,94 5,54 4,77 4,77 4,95
GA 4 5,01 6,94 6,15 6,12 6,58 5,38 6,18 6,91 7,01 7,01 7,17
BH 4,41 6,25 5,69 4,98 5,44 6,22 5,68 5,36 4,66 4,66 4,97
5,42
5,61
5,55
5,32
5,34
5,19
6,41
5,30
104
H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 gem.
H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 gem.
H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 gem.
GA I4-1 FH 4,37 6,13 5,09 5,09 5,27 4,91 5,36 5,51 5,54 5,54 5,76
BH 4,52 5,91 5,25 4,95 5,51 5,83 5,07 5,48 4,60 4,60 4,81
GA 2 4,27 7,08 5,80 5,51 5,81 5,59 5,75 5,85 5,86 5,86 6,95
BH 4,52 7,14 6,06 5,42 6,24 6,93 5,74 6,15 4,96 4,96 5,36
GA 3 5,00 7,48 6,45 6,17 6,38 6,16 6,21 6,65 6,56 6,56 7,56
BH 5,03 7,12 6,17 6,26 6,66 7,24 6,29 6,46 5,55 5,55 5,55
GA 4 5,22 7,28 6,66 6,41 6,89 5,88 6,59 7,11 7,02 7,02 7,62
BH 4,70 7,42 6,84 5,76 6,56 6,94 6,22 6,64 5,66 5,66 6,17
5,33
5,14
5,85
5,77
6,47
6,17
6,70
6,23
GA I5-1 FH 4,49 5,88 5,15 5,11 5,51 4,97 5,53 5,58 5,69 5,69 5,77
BH 4,40 6,48 5,73 4,82 5,81 6,22 5,24 5,72 4,78 4,78 5,04
GA 2 4,31 6,05 4,88 4,99 5,01 4,81 5,41 5,47 5,47 5,47 5,76
BH 4,30 5,65 5,19 4,92 5,51 5,97 4,95 5,53 4,31 4,31 4,62
GA 3 4,53 6,49 5,67 5,28 5,61 5,27 5,69 5,75 5,78 5,78 6,32
BH 4,73 6,26 5,42 5,25 5,54 6,06 5,52 5,57 4,90 4,90 5,13
GA 4 4,45 6,77 5,50 5,56 5,73 5,28 5,52 5,93 5,89 5,89 6,39
BH 4,64 6,48 5,70 5,32 6,02 6,28 5,38 5,91 4,93 4,93 5,15
5,40
5,37
5,24
5,02
5,65
5,39
5,72
5,52
GA I6-1 FH 4,52 5,46 4,53 5,12 5,35 4,81 5,13 5,41 4,98 4,98 5,03
BH 4,11 5,23 4,96 4,46 5,01 5,64 4,84 5,08 4,09 4,09 4,47
GA 2 4,41 6,11 5,06 5,18 5,15 5,18 5,46 5,43 5,41 5,41 5,64
BH 4,55 5,86 5,20 4,93 5,61 5,92 5,04 5,63 4,64 4,64 4,78
GA 3 4,55 6,49 5,44 5,38 5,67 5,00 5,65 6,00 6,12 6,12 6,44
BH 4,51 6,32 5,52 5,16 5,63 5,99 5,36 5,56 4,82 4,82 5,09
GA 4 4,31 7,21 6,12 5,42 5,84 5,50 5,74 5,89 6,01 6,01 6,95
BH 4,92 7,18 6,20 5,77 6,49 6,92 5,84 6,38 5,26 5,26 5,51
5,03
4,72
5,31
5,16
5,72
5,34
5,91
5,97
GA: gemiddelde afwijking I6-1: <0.25
bijlage
2: [0.26,0.5]
3: [0.51,0.75] 4: [0.76,1]
FH : voorwaartse prioriteitsregel BH : achterwaartse prioriteitsregel
105 Bijlage 1. 11 :
voorbeeld van een gecreëerd netwerk m.b.v. RanGen 2 (NetworkViewer)
bijlage
106
Referenties
Referenties
107
Referenties
§
Agrawal M. Elmaghraby S. en Herroelen W., 1996, DAGEN: A generator of testsets for project activity nets, European Journal of Operational Research, vol. 90, nr. 20, p. 376-382.
§
Bein W., Kamburowski J. en Stallmann M., 1992, Optimal reduction of two-terminal directed acyclic graphs, SIAM Journal on Computing, vol. 21, p. 1112-1129.
§
Brucker P. et al., 1999, Resource-constrained project scheduling: Notation, classification, models, and methods, European Journal of Operational Research, vol. 112, nr. 1, p. 3-41.
§
Chanas S., Dubois D. en Zielinski P., 2002, On the sure criticality of tasks in Activity networks with imprecise durations, IEEE Transactions on systems, man, and cyberneticspart B: cybernetics, vol. 32, nr. 4, p. 393-407.
§
Cooper D.F., 1976, Heuristics for scheduling resource-constrained projects: an experimental investigation, Management Science, vol. 22, nr. 11, p. 1186-1194.
§
Corder S. en Ruby Jr. R., 1993, Microcomputer-based software alternatives for project management, Journal of Education for Business, vol. 69, Nr. 1, p. 56-60.
§
Davis E.W. en Heidorn G.E., 1971, Optimal project scheduling under multiple resource constraints, Management Science, vol. 17, nr. 12, p. 803-816.
§
Davis E.W., 1975, Project network summary measures constrained-resource scheduling, AIIE Transactions, vol. 7, nr. 2, p. 132-142.
§
Davis E.W. en Patterson J., 1975, A comparison of heuristic and optimal solutions in resource constrained project scheduling, Management Science, vol. 21, nr. 8, p. 944-955.
§
Demeulemeester E. en Herroelen W., 1992, A branch-and-bound procedure for the multiple resource constrained project scheduling problem, Management Science, vol. 38, nr. 12, December 1992, p. 1803-1818.
§
Demeulemeester E., Dodin B. en Herroelen W., 1993, A random activity network generator, Operations Research, vol. 41, nr. 5, p. 972-980.
§
Demeulemeester E. en Herroelen W., 1996, An efficient optimal solution procedure for the preemtive resource-constrained project scheduling problem, European Journal of Operational Research, vol. 90, nr. 2, p. 334-348.
§
De Reyck B. en Herroelen W., 1996, On the use of the complexity index as a measure of complexity in activity networks, European Journal of Operational Research, vol. 91, nr. 2, p. 347-366.
§
De Reyck B. en Herroelen W., 1999, Bieden projectplanningspakketten de oplossing? Projectmanagement en –scheduling, Business Logistics, p. 46-57.
§
De Reyck B. en Herroelen W., 1999, Complex samenspel tussen tijd-, volgorde- en hulpmiddelenbeperkingen, Business Logistics, p. 19-28.
§
De Wit J. en Herroelen Willy, 1990, An evaluation of microcomputer-based software packages for project management, European Journal of Operational Research, vol. 49, nr. 1, p. 102-139.
§
East W. en Liu L., 1993, Infrastructure in projectmanagement: dynamic multiproject scheduling with limited resources, Working paper, University of Illionois.
108
Referenties
§
Elmaghraby S.E. en Herroelen W., 1980, On the measurement of complexity in activity networks, European Journal of Operational Research, vol. 5, nr. 4, p. 223-234.
§
Elmaghraby S.E. en Kamburowski J., 1992, The analysis of activity networks under generalized precedence relations, Management Science, vol. 38, nr. 9, p. 1245-1263.
§
Farrington et al., 1999, Activity scheduling in the dynamic, multi-project setting: choosing heuristics through deterministic simulation, Proceedings of the 1999 Winter Simulation Conference.
§
Focken T., 2002, Review of the development of the project management technology, ENMG 604 Desk Research Project, University of Canterbury, Christchurch, New Zealand.
§
Gemmil D.D. en Edwards M.L., 1999, Improving resource-constrained project schedules with look-ahead techniques, Project Management Journal, vol. 30, nr. 3, p. 44-55.
§
Hartmann S. en Kolisch R., 2000, Experimental evaluation of state-of-the-art heuristics for the resource constrained project scheduling problem, European Journal of Operational Research, vol. 127, nr. , p. 394-407.
§
Hegazy T., 1999, Optimization of Resource Allocation and Leveling Using Genetic Algorithms, Journal of construction and engineering and management, vol. 125, nr. 3, p. 167-175.
§
Herroelen W. en Demeulemeester E., 1996, Project management and scheduling, European Journal of Operational Research, vol. 90, nr. 2, p. 197-199.
§
Herroelen W. en De Reyck B., 1998, A branch-and-bound procedure for the resourceconstrained scheduling problem with generalized precedence relations, European Journal of Operational Research, vol. 111, nr. 1, p. 152-174.
§
Herroelen W. en De Reyck B., 1999, Phase Transitions in Project Scheduling, Journal of the Operational Research Quarterly, vol. 50, nr. ?, p. 148-156.
§
Khamooshi H., 1996, Net-work-based project planning and scheduling, Industrial Management & Data Systems, vol. 96, nr. 8, p. 13-22.
§
Khattab M. en Soyland K., 1998, Limited resource allocation in construction projects, ASC Proceedings of the 34the Annual Conference, 15-18 april 1998, p. 273-280.
§
Kirkpatrick S., Gelatt Jr. C.D. en Vecchi M.P., 1983, Science, Optimization by simulated annealing, vol. 220, nr. 4598, p. 671-771.
§
Klein R., 2000, Bi-directional planning – improving priority rule based heuristics for scheduling resource-constrained projects, European Journal of operational Research, vol. 127, nr. 3, p. 619-638.
§
Klein R., 2000, Project scheduling with time-varying resource constraints, International Journal of Production Research, vol. 38, nr. 16, p. 3937-3957.
§
Kolisch R. et al., 1995, Characterization and generation of a general class of resourceconstrained project scheduling problems, Management Science, vol. 41, nr.10, p. 16931703.
109
Referenties
§
Kolisch R., 1996, Efficient priority rules for the resource constrained project scheduling problem, Journal of Operations management, vol. 14, nr. 3, p. 179-192.
§
Kolisch R., 1996, Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation, European Journal of Operational Research, vol. 90, nr. 2, p. 320-333.
§
Kolisch R., 1999, Resource Allocation Capabilities of Commercial Project Management Software Packages, Interfaces, vol. 29, nr. 4, p. 19-31.
§
Liberatore M.J., Pollack-Johnson B. en Smith C.A., 2001, Project Management in Construction: Software Use and Research Directions, Journal of Construction Engineering and Management, vol. 127, nr. 2, p. 101-107.
§
Mastor A.A., 1970, An experimental and comparative evaluation of production line balancing techniques, Management Science, vol. 16, nr. 2, p. 728-746.
§
McCray G.E., Purvis R.L. en McCray C.G., 2002, Project management under uncertainty: The impact of heuristics and biases, Project Management Journal, vol. 33, nr. 1, mart 2002, p. 49-57.
§
Mellentien C. en Trautmann N., 2001, Resource allocation with project management software, OR Spektrum, vol. 23, nr.3, p. 383-394.
§
Neumann K. en Zimmerman J., 1999, Resource levelling for projects with scheduledependent time windows, European Journal of Operational Research, vol. 117, nr. 3, p. 591-605.
§
Patterson J. en Roth G., 1976, Scheduling a project under multiple resource constraints: A zero one programming approach, AIIE Transactions, vol. 8, nr; 4, p. 449-456.
§
Patterson J., 1984, A comparison of exact approaches for solving the multiple constrained resource project scheduling problem, Management Science, vol. 30, nr. 7, p. 854-867.
§
Project Management Institute, A guide to the Project Management Body of Knowledge (PMBOK®Guide) – 2000 Edition, 216 p.
§
Primavera Project Planner (P3), 1999, Planning and control guide, Primavera Systems, Philadelphia.
§
Primavera Project Planner (P3), 1999, Reference Manual, Primavera Systems, Philadelphia.
§
Schirmer A., 1998, Advanced biased random sampling in serial and parallel scheduling, Institut für Betriebswirtshaftslehre, Lehrstuhl für Produktion und Logistik.
§
Schwindt C., 1996, Generation of resource-constrained project scheduling problems with minimal and maximal time lags, WIOR-Report-489, Institut für Wirtschaftstheorie und Operations Research, Universität Karlsruhe, 52 p.
§
Tavares L.V., Ferreira J.A. en Coelho J.S., 1999, The risk of delay of a project in terms of the morphology of its network, European Journal of Operational Research, vol. 119, nr.2, p. 510-537.
110
Referenties
§
Tormos P., Barber F. en Lova A., 2002, An integration model for planning and scheduling problems with constrained resources, Proceedings of the 8the international workshop on project management and scheduling, p. 354-358.
§
Vanhoucke M., Demeulemeester E. en Herroelen W., 2001, A new random network generator for activity-on-the-node networks, Journal of Scheduling,
§
Vanhoucke M., Coelho J. en Tavares L., 2003, On the morphological structure of a network,
§
Yang B. en Geunes J., 2001, Resource-constrained project scheduling: past work and new directions, Research Report 2001-6, Department of Industrial Engineering, University of Florida.
