PROJECT SCHEDULING EN TEAMEFFICIENTIE

UNIVERSITEIT GENT

FACULTEIT ECONOMIE EN BEDRIJFSKUNDE

ACADEMIEJAAR 2013 – 2014

PROJECT SCHEDULING EN TEAMEFFICIENTIE Masterproef voorgedragen tot het bekomen van de graad Master of Science in de Toegepaste Economische Wetenschappen: Handelsingenieur

Bert Aelter Jules Branswyck

onder leiding van

Prof. Dr. Mario Vanhoucke en Len Vandenheede

UNIVERSITEIT GENT

FACULTEIT ECONOMIE EN BEDRIJFSKUNDE

ACADEMIEJAAR 2013 – 2014

PROJECT SCHEDULING EN TEAMEFFICIENTIE Masterproef voorgedragen tot het bekomen van de graad Master of Science in de Toegepaste Economische Wetenschappen: Handelsingenieur


onder leiding van

Prof. Dr. Mario Vanhoucke en Len Vandenheede

PERMISSION

Ondergetekenden verklaren dat de inhoud van deze masterproef mag geraadpleegd en/of gereproduceerd worden, mits bronvermelding.


WOORD VOORAF Deze thesis is meer dan enkel een scriptie waarin een uitvoerig onderzoek wordt neergeschreven. Voor ons is het een afsluiter van een vijf jaar durende studententijd. Daarom willen we in dit voorwoord vooral terugblikken op de afgelopen vijf jaar, waarvan deze thesis een uitdagend maar leerrijk einde is. In 2009 arriveerden wij beiden in Gent, met voor ons de grootste uitdaging waar we tot op dat moment voor hadden gestaan. Met een gevoel van opwinding, gecombineerd met wat onzekerheid, startten we aan een fantastisch avontuur, zonder te weten hoe dit zou verlopen of waar het zou eindigen. Uiteindelijk zijn het vijf erg intense, leerrijke, maar ook schitterende jaren geworden, waar we met volle teugen van hebben genoten. De vergelijking tussen de personen die we waren toen we onze studies aanvatten en de personen die we nu geworden zijn, toont hoe sterk we de voorbije jaren zijn geëvolueerd. Naast heel wat kennis, heeft deze studententijd ons ook een grote portie levenservaring bijgebracht. We willen dan ook de mensen bedanken die ons hierbij hebben begeleid, geholpen en gesteund. Vooral onze ouders verdienen een speciale vermelding omwille van de kans die ze ons geboden hebben om vijf jaar lang zorgeloos te kunnen studeren. Ook wensen wij graag even stil te staan bij de mensen die deze thesis mogelijk maakten. Eerst en vooral willen wij Len Vandenheede bedanken. De voorbije twee jaar heeft hij ons met raad en daad bijgestaan en zonder zijn input zou deze thesis niet tot het huidige resultaat gekomen zijn. Vervolgens willen wij ook Prof. Dr. Mario Vanhoucke bedanken voor de kans en het vertrouwen die hij ons gegeven heeft om een onderwerp binnen de vakgroep Beleidsinformatica en Operationeel Beheer onder zijn leiding te mogen uitwerken. We willen ook nog vermelden dat bepaalde termen in deze thesis consequent in het Engels werden opgenomen. Hier werd voor gekozen indien er, in onze ogen, geen passende Nederlandse vertaling voorhanden was die er in slaagde deze termen volledig te vatten. Tot slot bedanken wij ook de lezer voor zijn interesse en wensen wij hem veel plezier met het doorlezen van deze thesis. Bert Aelter Jules Branswyck I

INHOUDSOPGAVE Woord vooraf ..................................................................................................................................................................................... I Inhoudsopgave ................................................................................................................................................................................. II Gebruikte afkortingen ................................................................................................................................................................. IV Lijst van gebruikte figuren .......................................................................................................................................................... V Lijst van gebruikte tabellen ..................................................................................................................................................... VII Lijst van gebruikte grafieken ....................................................................................................................................................IX

Abstract ............................................................................................................................................................................................... 1 Inleiding .............................................................................................................................................................................................. 2

Deel 1 - Probleembeschrijving .................................................................................................................................................. 4 Inleiding ......................................................................................................................................................................................... 5 Hoofdstuk 1: Het Resource Constrained Project Scheduling Problem (RCPSP) .............................................. 6 1.1 Opbouw van het RCPSP ............................................................................................................................................... 6 1.2 Samenvatting Hoofdstuk 1 ......................................................................................................................................... 8 Hoofdstuk 2: Het Multi-Objective Team Composition Problem (MOTCP) ......................................................... 9 2.1 Team Composition Problem (TCP) ......................................................................................................................... 9 2.2 Multi-Objective Optimization................................................................................................................................. 11 2.3 MOTCP model ............................................................................................................................................................... 14 2.4 Samenvatting Hoofdstuk 2 ...................................................................................................................................... 19 Deel 2 - Complex Project Scheduling ................................................................................................................................... 20 Inleiding ...................................................................................................................................................................................... 21 Hoofdstuk 3: Projecttypes ................................................................................................................................................... 22 3.1 Traditionele Projectindicatoren ........................................................................................................................... 22 3.2 Additionele Projectindicatoren voor het beschouwde MOTCP ............................................................... 26 3.3 Samenvatting Hoofdstuk 3 ...................................................................................................................................... 29 Hoofdstuk 4: Metaheuristieken ......................................................................................................................................... 30 4.1 Schedule Generation Schemes ............................................................................................................................... 30 4.2 Metaheuristieke procedures .................................................................................................................................. 38 4.3 Probleemspecifieke oplossingsvoorstelling .................................................................................................... 46 4.4 Samenvatting Hoofdstuk 4 ...................................................................................................................................... 47 II

Deel 3 - Onderzoeksopzet ......................................................................................................................................................... 48 Inleiding ...................................................................................................................................................................................... 49 Hoofdstuk 5: Methodologie ................................................................................................................................................. 50 5.1 Inleiding .......................................................................................................................................................................... 50 5.2 Pre-simulatie................................................................................................................................................................. 50 5.3 Simulatie ......................................................................................................................................................................... 51 5.4 Samenvatting Hoofdstuk 5 ...................................................................................................................................... 54 HOOFDSTUK 6: ONDERZOEK ...................................................................................................................................................... 55 6.1 Overzicht van de onderzoeksvragen................................................................................................................... 55 6.2 Rapportering van de resultaten ............................................................................................................................ 56 6.2.1 Onderzoeksvraag 1 ............................................................................................................................................ 56 6.2.2 Onderzoeksvraag 2 ............................................................................................................................................ 90 6.2.3 Onderzoeksvraag 3 ............................................................................................................................................ 95 6.2.4 Onderzoeksvraag 4 .......................................................................................................................................... 101 Hoofdstuk 7: Managementconclusies ........................................................................................................................... 107

Algemene conclusie en verder onderzoek....................................................................................................................... 112

Lijst van geraadpleegde werken .......................................................................................................................................... 115

Bijlage 1: Assumpties i.v.m. de probleemsetting Bijlage 2: Ondersteunende definities voor topologische netwerkindicatoren Bijlage 3: Pre-simulatie Bijlage 3.1: Algemene beschrijving van een pre-simulatie Bijlage 3.2: Pre-simulaties voor GA1 en SS1 Bijlage 3.3: Pre-simulatie voor GA4 Besluit Bijlage 4: Simulatie Bijlage 5: Intelligente prioriteitsregels Prioriteitsregels i.v.m activiteiten Prioriteitsregels i.v.m werknemers

III

Gebruikte afkortingen CV

= Coefficient of Variation / Variatiecoëfficiënt

ESS

= Earliest Start Schedule

GA

= Genetic Algorithm

LS

= Local Search

MOTCP

= Multi-Objective Team Composition Problem

PSGS

= Parallel Schedule Generation Scheme

RCPSP

= Resource Constrained Project Scheduling Problem

SGS

= Schedule Generation Scheme

SS

= Scatter Search

SSGS

= Serial Schedule Generation Scheme

TCP

= Team Composition Problem

IV

LIJST VAN GEBRUIKTE FIGUREN Figuur 1 - Schematische voorstelling van het RCPSP .........................................................................................8 Figuur 2 - Vier types beslissingen i.v.m. team composition ............................................................................. 10 Figuur 3 - Optimaliseringsobjectieven ............................................................................................................. 12 Figuur 4 - Schematische voorstelling MOTCP .................................................................................................. 19 Figuur 5 - Netwerktopologie voor I2 = 0 ........................................................................................................... 24 Figuur 6 - Netwerktopologie voor I2 = 1 ........................................................................................................... 24 Figuur 7 - Voorbeeld SSGS en PSGS (AoN netwerk) ......................................................................................... 31 Figuur 8 - Voorbeeld SSGS 1 ............................................................................................................................. 32 Figuur 9 - Voorbeeld SSGS 2 ............................................................................................................................. 33 Figuur 10 - Voorbeeld SSGS 3 ........................................................................................................................... 33 Figuur 11 - Voorbeeld SSGS 4 ........................................................................................................................... 34 Figuur 12 - Voorbeeld SSGS 5 ........................................................................................................................... 35 Figuur 13 - Voorbeeld PSGS 1 ........................................................................................................................... 35 Figuur 14 - Voorbeeld PSGS 2 ........................................................................................................................... 36 Figuur 15 - Voorbeeld PSGS 3 ........................................................................................................................... 37 Figuur 16 - Voorbeeld PSGS 4 ........................................................................................................................... 37 Figuur 17 - Conceptueel model van Genetic Algorithm ................................................................................... 39 Figuur 18 - Conceptueel model van Scatter Search ......................................................................................... 42 Figuur 19 - Voorbeeld oplossingsvoorstelling .................................................................................................. 46 Figuur 20 - Generiek model van metaheuristieken.......................................................................................... 47 Figuur 21 - Scope van de simulatie................................................................................................................... 54 Figuur 22 - Conceptueel model GA1 ................................................................................................................. 58 Figuur 23 - Voorbeeld two-point cross-over (prioriteitslijsten voor cross-over) ............................................. 60 Figuur 24 - Voorbeeld two-point cross-over (transformatie).......................................................................... 60 Figuur 25 - Voorbeeld two-point cross-over (prioriteitslijsten na cross-over)................................................. 60 Figuur 26 - Voorbeeld random swap mutation (prioriteitslijst voor mutatie) ................................................. 62 Figuur 27 - Voorbeeld random swap mutation (transformatie) ...................................................................... 62 Figuur 28 - Voorbeeld random swap mutation (prioriteitslijst na mutatie) .................................................... 62 Figuur 29 - Conceptueel model SS1 .................................................................................................................. 64 Figuur 30 - Voorbeeld euclidische afstand (prioriteitslijsten) .......................................................................... 66 Figuur 31 - Voorbeeld local search (prioriteitslijst voor LS) ............................................................................. 69 Figuur 32 - Voorbeeld local search (buur 2.1) .................................................................................................. 69 Figuur 33 - Overzicht methodologie onderzoeksvraag 1.1 .............................................................................. 71 Figuur 34 - Roulette wheel selection................................................................................................................ 74 Figuur 35 - Voorbeeld gemiddelde cross-over (prioriteitslijsten voor cross-over) .......................................... 75 Figuur 36 - Voorbeeld gemiddelde cross-over (prioriteitslijsten na cross-over) ............................................. 75 Figuur 37 - Conceptueel model GA4 ................................................................................................................. 77 Figuur 38 - Overzicht methodologie onderzoeksvraag 1.2 .............................................................................. 79 Figuur 39 - Overzicht methodologie onderzoeksvraag 1.3 .............................................................................. 83 Figuur 40 - Overzicht methodologie onderzoeksvraag 1.4 .............................................................................. 85 V

Figuur 41 - Vergelijking performantieverschil GA en SS met en zonder intelligentie ...................................... 89 Figuur 42 - Performantiewijzigingen door toevoegen van intelligentie .......................................................... 89 Figuur 43 - Overzicht methodologie onderzoeksvraag 2 ................................................................................. 90 Figuur 44 - Vergelijking PSGS en SSGS .............................................................................................................. 94 Figuur 45 - Verschil tussen PSGS en SSGS bij I2 ................................................................................................ 94 Figuur 46 - Overzicht methodologie onderzoeksvraag 3 ................................................................................. 95 Figuur 47 - Overzicht methodologie onderzoeksvraag 4 ............................................................................... 101 Figuur 48 - Overzicht van de vier metaheuristieken ...................................................................................... 112 Figuur 49 - Voorbeeld hiërarchische levels (AoN-netwerk) ........................................................................... 121 Figuur 50 - Voorbeeld hiërarchische levels (progressief en regressief level) ................................................ 122 Figuur 51 - Voorbeeld pre-simulatie (tweevoudige iteratie van sequentiële optimalisaties) ....................... 125

VI

LIJST VAN GEBRUIKTE TABELLEN Tabel 1 - Gradaties in de variatiecoëfficiënt .................................................................................................... 27 Tabel 2 - Overzicht van de beschouwde projectindicatoren............................................................................ 29 Tabel 3 - Invulling van de dimensies bij metaheuristieken voor GA en SS (Taha, 2007) ................................. 45 Tabel 4 - Voor- en nadelen van Genetic Algorithm .......................................................................................... 45 Tabel 5 - Voor- en nadelen van Scatter Search ................................................................................................ 45 Tabel 6 - Overzicht van de verschillende metaheuristieken ............................................................................ 45 Tabel 7 - Overzicht intervallen van traditionele projectindicatoren ................................................................ 52 Tabel 8 - Overzicht intervallen van probleemspecifieke projectindicatoren ................................................... 52 Tabel 9 - Implementatieonderdelen van GA en SS .......................................................................................... 57 Tabel 10 - Overzicht van de implementatieonderdelen GA1 ........................................................................... 57 Tabel 11 - Overzicht van de implementatieonderdelen van SS1 ...................................................................... 57 Tabel 12 - Voorbeeld rank selection (gegevens) .............................................................................................. 59 Tabel 13 - Voorbeeld rank selection (selectietrommel) ................................................................................... 59 Tabel 14 - Gebruikte prioriteitsregels in SS1..................................................................................................... 65 Tabel 15 - Voorbeeld euclidische afstand (selectie van B2 uit POP)................................................................. 67 Tabel 16 - Overzicht van de verschillende GA-implementaties ....................................................................... 73 Tabel 17 - Implementatie GA2 .......................................................................................................................... 73 Tabel 18 - Implementatie GA3 .......................................................................................................................... 76 Tabel 19 - Gebruikte prioriteitsregels in GA3 ................................................................................................... 76 Tabel 20 - Implementatie GA4 .......................................................................................................................... 77 Tabel 21 - Overzicht van de verschillende GA-implementaties ....................................................................... 80 Tabel 22 - Overzicht van de verschillende SS-implementaties ........................................................................ 81 Tabel 23 - Implementatie SS2 ........................................................................................................................... 81 Tabel 24 - Implementatie SS3 ........................................................................................................................... 82 Tabel 25 - Overzicht van de verschillende SS implementaties ......................................................................... 84 Tabel 26 - Implementatie GA4 .......................................................................................................................... 85 Tabel 27 - Implementatie SS3 ........................................................................................................................... 85 Tabel 28 - Voorbeeld transformatie onderzoeksvraag 3 (sociale cohesie) ...................................................... 96 Tabel 29 - Voorbeeld transformatie onderzoeksvraag 3 (competentieniveau)............................................... 96 Tabel 30 - Voorbeeld transformatie onderzoeksvraag 3 (voor interpolatie) ................................................... 96 Tabel 31- Voorbeeld transformatie onderzoeksvraag 3 (na interpolatie) ....................................................... 97 Tabel 32 - Overzicht van time, cost en quality management......................................................................... 111 Tabel 33 - Metaheuristiek gerelateerde pre-simulatie parameters............................................................... 123 Tabel 34 - Algemene pre-simulate parameters.............................................................................................. 123 Tabel 35 - Overzicht projecten pre-simulatie................................................................................................. 126 Tabel 36 - Pre-simulatie metaheuristiek parameters: Stap 1 (bijlage 3.2)..................................................... 128 Tabel 37 - Pre-simulatie metaheuristiek parameters: Stap 2 (bijlage 3.2)..................................................... 128 Tabel 38 - Pre-simulatie metaheuristiek parameters: Stap 3- GA (bijlage 3.2).............................................. 128 Tabel 39 - Pre-simulatie metaheuristiek parameters: Stap 3- SS (bijlage 3.2) ............................................... 129 Tabel 40 - Pre-simulatie metaheuristiek parameters: Stap 4 (bijlage 3.2)..................................................... 129 VII

Tabel 41 - Pre-simulatie metaheuristiek parameters: Stap 5 (bijlage 3.2)..................................................... 129 Tabel 42 - Pre-simulatie metaheuristiek parameters: Stap 6 (bijlage 3.2)..................................................... 130 Tabel 43 - Pre-simulatie metaheuristiek parameters: Stap 7 (bijlage 3.2)..................................................... 130 Tabel 44 - Pre-simulatie metaheuristiek parameters: Stap 1 (bijlage 3.3)..................................................... 132 Tabel 45 - Pre-simulatie metaheuristiek parameters: Stap 2 (bijlage 3.3)..................................................... 132 Tabel 46 - Pre-simulatie metaheuristiek parameters: Stap 3 (bijlage 3.3)..................................................... 132 Tabel 47 - Pre-simulatie metaheuristiek parameters: Stap 4 (bijlage 3.3)..................................................... 133 Tabel 48 - Pre-simulatie metaheuristiek parameters: Stap 5 (bijlage 3.3)..................................................... 133 Tabel 49 - Pre-simulatie besluit GA ................................................................................................................ 134 Tabel 50 - Pre-simulatie besluit SS ................................................................................................................. 134 Tabel 51 - Simulatie voor paramter I2 ............................................................................................................ 136 Tabel 52 - Simulatie voor paramter I3 ............................................................................................................ 136 Tabel 53 - Simulatie voor paramter I4 ............................................................................................................ 136 Tabel 54 - Simulatie voor paramter I5 ............................................................................................................ 137 Tabel 55 - Simulatie voor parameter I6 .......................................................................................................... 137 Tabel 56 - Simulatie voor parameter μs ......................................................................................................... 137 Tabel 57 - Simulatie voor parameter μc ......................................................................................................... 138 Tabel 58 - Simulatie voor parameter CVs ....................................................................................................... 138 Tabel 59 - Simulatie voor parameter CVc ....................................................................................................... 138

VIII

LIJST VAN GEBRUIKTE GRAFIEKEN Grafiek 1 - Resultaten pre-simulatie Par1 ......................................................................................................... 61 Grafiek 2 - Resultaten pre-simulatie Par2 ......................................................................................................... 63 Grafiek 3 - Resultaten pre-simulatie Par5 ......................................................................................................... 68 Grafiek 4 - Resultaten pre-simulatie Par6 ......................................................................................................... 70 Grafiek 5 - Resultaten pre-simulatie Par7 ......................................................................................................... 70 Grafiek 6 - Performantie van GA1 en SS1 over I2............................................................................................... 72 Grafiek 7 - Gemiddelde performantie van GA1 en SS1 ..................................................................................... 72 Grafiek 8 - Resultaten pre-simulatie Par3 ......................................................................................................... 78 Grafiek 9 - Resultaten pre-simulatie Par4 ......................................................................................................... 78 Grafiek 10 - Resultaten onderzoeksvraag 1.2 .................................................................................................. 80 Grafiek 11 - Performantie van SS bij verschillende B1- en B2-groottes ............................................................ 83 Grafiek 12 - Resultaten onderzoeksvraag 1.3 .................................................................................................. 84 Grafiek 13 - Performantie GA4 en SS3 over I2 ................................................................................................... 86 Grafiek 14 - Gemiddelde performantie GA4 en SS3 .......................................................................................... 86 Grafiek 15 - Vergelijking tussen de 4 GA’s en LS .............................................................................................. 87 Grafiek 16 - Vergelijking van de 3 SS'en en LS.................................................................................................. 87 Grafiek 17 - Vergelijking PSGS en SSGS voor I2................................................................................................. 92 Grafiek 18 - Vergelijking PSGS en SSGS voor I3................................................................................................. 92 Grafiek 19 - Vergelijking PSGS en SSGS voor I4................................................................................................. 92 Grafiek 20 - Vergelijking PSGS en SSGS voor I5................................................................................................. 92 Grafiek 21 - Vergelijking PSGS en SSGS voor I6................................................................................................. 92 Grafiek 22 - Vergelijking PSGS en SSGS voor 𝜇c................................................................................................ 92 Grafiek 23 - Vergelijking PSGS en SSGS voor 𝜇s ................................................................................................ 93 Grafiek 24 - Vergelijking PSGS en SSGS voor CVc ............................................................................................. 93 Grafiek 25 - Vergelijking PSGS en SSGS voor CVs.............................................................................................. 93 Grafiek 26 - Invloed van projectindicatoren .................................................................................................... 98 Grafiek 27 - Invloed van projectindicatoren (2) ............................................................................................... 98 Grafiek 28 - Invloed van belangrijkste projectindicatoren ............................................................................... 98 Grafiek 29 - Invloed van I2 op de deelobjectieven ......................................................................................... 102 Grafiek 30 - Performantie-evolutie van de deelobjectieven .......................................................................... 103 Grafiek 31 - Evolutie van de contributie van de deelobjectieven .................................................................. 104 Grafiek 32 - Evolutie van de performantie van de deelobjectieven over I2 ................................................... 105 Grafiek 33 - Pre-simulatie aantal werknemers............................................................................................... 131 Grafiek 34 - Pre-simulatie stopcriterium ........................................................................................................ 131

IX

ABSTRACT NEDERLANDS Het doel van deze studie is het analyseren van de performantie van de metaheuristieken Genetic Algorithm (GA) en Scatter Search (SS) in combinatie met zowel Serial (SSGS) als Parallel (PSGS) Schedule Generation Scheme voor het Multi-Objective Team Composition Problem (MOTCP). De resultaten tonen aan dat, voor een algemene implementatievorm, SS beter presteert dan GA. Wanneer echter meer probleemspecifieke intelligentie wordt toegevoegd aan de implementatie van de metaheuristieken, verdwijnt de dominantie van SS. Het onderzoek bewijst dat het incorporeren van probleemspecifieke intelligentie voor het MOTCP betekent dat de focus op intensificatie vergroot. Verder wordt aangetoond dat in de geschetste context SSGS beter presteert dan PSGS. De managementconclusies die uit deze studie worden getrokken, benadrukken vooral het belang van het betrekken van een sociale factor bij het samenstellen van projectteams en het schedulen van projecten. De toegevoegde waarde van dit onderzoek ligt enerzijds in het gebruik van SS met het oog op het verder ontdekken van diens mogelijkheden in projectmanagement en anderzijds in het voorzien van een handleiding voor het implementeren van metaheuristieken in project scheduling.

ENGLISH The goal of this study is to analyze the performance of the metaheuristics Genetic Algorithm (GA) and Scatter Search (SS) combined with the Serial (SSGS) as well as the Parallel (PSGS) Schedule Generation Scheme for the Multi-Objective Team Composition Problem (MOTCP). The results show that for a general implementation, SS outperforms GA. However, if some problem specific intelligence is taken into account when implementing the metaheuristics, the dominance of SS disappears. The research shows that the incorporation of problem specific intelligence for the MOTCP shifts the focus towards intensification. Furthermore, it is shown that in the outlined context, SSGS dominates PSGS. The managerial conclusions that can be drawn from this study primarily emphasize the importance of incorporating a social factor when composing project teams and scheduling projects. The added value of this research lies in the involvement of SS to further discover its opportunities in projectmanagement on the one hand and in providing a guide for implementing metaheuristics in project scheduling on the other. TREFWOORDEN: MULTI-OBJECTIVE – TEAM COMPOSITION PROBLEM – SOCIALE COHESIE - GENETIC ALGORITHM – SCATTER SEARCH – SERIAL SCHEDULE GENERATION SCHEME – PARALLEL SCHEDULE GENERATION SCHEME

1

INLEIDING In de huidige, snel evoluerende economie is de rol van projecten in alle lagen van een onderneming van almaar groeiend belang. Veel van deze projecten worden uitgevoerd door interne medewerkers omdat dit vaak een goedkope en snelle oplossing is. Daarenboven bezitten zij kennis die nuttig of zelfs noodzakelijk is om een project tot een goed einde te brengen terwijl het voor externe partijen erg moeilijk is om deze kennis snel te verwerven. Aangezien voor elk nieuw project getracht wordt een optimaal team samen te stellen, kennen dergelijke interne projectteams veelal een wisselende samenstelling. Enerzijds moet elke werknemer als individu competent zijn om de aan hem toegewezen taken naar behoren uit te voeren. Anderzijds moet getracht worden synergiën te creëren tussen de leden van een team. In de bedrijfswereld wordt hoe langer hoe meer het belang van groepsdynamiek erkend als fundamentele voorwaarde van interne synergiën. Zowel bij KMO's als bij multinationals is het besef gegroeid dat voor het behalen van goede resultaten een bepaalde graad van samenhorigheid en bereidheid tot samenwerking tussen de werknemers nodig is. Om een project tot een goed einde te kunnen brengen, hebben bedrijven in de 21e eeuw nood aan een geëngageerde groep werknemers waarin elk individu zich comfortabel voelt. Vele vormings- en opleidingsprogramma’s zijn dan ook gericht op het verbeteren van de onderlinge relaties en samenwerking tussen werknemers. Het belang van deze groepsdynamiek is nog groter in projectgedreven organisaties waar een groep mensen vaak voor een bepaalde periode intensief moet samenwerken. Voor deze organisaties is het van cruciaal belang om het sociale aspect bij teamsamenstelling te onderkennen, te begrijpen en te integreren in de projectplanning. Het incorporeren van informatie in verband met de sociale cohesie tussen werknemers wordt met recht en reden hoe langer hoe meer in de praktijk toegepast. Het betrekken van een sociale factor resulteert echter voor de projectmanager in een extra dimensie in de complexiteit van het teamsamenstellingsprobleem. Een eerste doel van deze thesis is het vergroten van het bewustzijn van de trend dat sociale factoren hoe langer hoe meer in rekening worden gebracht bij het samenstellen van projectteams. Het tweede en voornaamste doel is, gegeven deze trend, de projectmanager te voorzien van enkele inzichten voor het plannen van projecten en het samenstellen van teams. Concreet wordt onderzoek gevoerd naar de effectiviteit van verschillende planningsmethodieken voor verschillende projecttypes. De resultaten van deze studie worden vertaald naar de praktijk zodat deze in de toekomst eventueel kunnen worden gebruikt bij de creatie van een decision support tool voor de projectmanager.

2

Het vervolg van deze thesis is bestaat uit drie grote delen. Deel 1 zal het bestudeerde probleem opbouwen door eerst het klassieke Resource Constrained Project Scheduling Problem toe te lichten en dit daarna uit te breiden tot het Multi-Objective Team Composition Problem. Deel 2 bespreekt vervolgens hoe complexiteit in project scheduling kan worden gekwantificeerd aan de hand van projecttypes. Daarnaast wordt ook ingegaan op hoe metaheuristieken kunnen worden aangewend om met deze complexiteit om te gaan. Deel 3 zal tenslotte de methodologie en resultaten bespreken van een simulatieonderzoek waar de performantie van metaheuristieken voor diverse types projecten werd geanalyseerd. Deze resultaten worden in een laatste fase vertaald naar een aantal inzichten voor de projectmanager.

3

DEEL 1 - PROBLEEMBESCHRIJVING

4

INLEIDING Binnen het domein van projectmanagement is een belangrijke rol weggelegd voor project scheduling. Deze discipline houdt zich bezig met het opstellen van een projectplanning die de projectmanager als leidraad kan gebruiken tijdens de uitvoering van een project. De projectmanager moet namelijk weten wanneer activiteiten kunnen worden aangevat en welke middelen hiervoor moeten worden aangewend. De twee fundamentele aspecten die project scheduling complex maken zijn enerzijds de aanwezigheid van volgorderelaties tussen activiteiten (precedence relations) en anderzijds de schaarste aan middelen (resource constraints) (Brucker et al., 1999). Deze complexiteit noodzaakt de projectmanager om project scheduling te benaderen met een formeel model waarin een te optimaliseren doelfunctie en een set van opgelegde voorwaarden zijn opgenomen. Het standaard model dat het vertrekpunt is van tal van project scheduling modellen in de literatuur is het Resource Constrained Project Scheduling Problem (RCPSP). Vele literaire werken gebruiken dit model als basis voor verdere analyse met als gevolg dat hier allerlei uitbreidingen op en varianten van zijn ontstaan. De variant die centraal staat in deze studie is het Team Composition Problem (TCP). Hierbij worden de resources verdeeld over een reeks individuen en is het de bedoeling de individuen te selecteren die samen alle projectactiviteiten zo efficiënt mogelijk kunnen uitvoeren. Het belang van dit probleem steunt op de overtuiging dat een organisatie extra waarde kan creëren door een optimale personeelsplanning en teamsamenstelling (Higgs et al., 2005). Doorgaans uit deze waardecreatie zich in een verbeterde tijds- en kostenefficiëntie. Een opmerkelijke trend die zich vandaag doorzet in zowel de literatuur als de praktijk is de aandacht voor de noden en wensen van de individuele werknemers. Deze sociale factor wijst op een derde bron, naast tijds- en kostenefficiëntie, van toegevoegde waarde bij de projectuitvoering (Van den Bergh et al., 2013). Deel 1 van dit werk zal het centraal beschouwde probleem opbouwen en bespreken. Hoofdstuk 1 licht enkele fundamentele concepten toe aan de hand van het klassieke RCPSP. Hoofdstuk 2 zal vervolgens dit basisprobleem uitbreiden naar het Multi-Objective Team Composition Problem (MOTCP) dat hierbij ook modelmatig wordt beschreven.

5

HOOFDSTUK 1: HET RESOURCE CONSTRAINED PROJECT SCHEDULING PROBLEM (RCPSP) Het doel van dit hoofdstuk is het beschrijven van de basisdynamieken binnen project scheduling. Hiervoor wordt het klassieke Resource Constrained Project Scheduling Problem (RCPSP) toegelicht aangezien dit een relatief eenvoudig beeld geeft van alle aspecten die bij project scheduling komen kijken en dus relevant zijn voor deze studie. Het RCPSP wordt hieronder opgebouwd naar analogie met de beschrijving van Hartmann en Briskorn (2010).

1.1 OPBOUW VAN HET RCPSP Het RCPSP vertrekt van een verzameling van n activiteiten die elk moeten worden afgewerkt alvorens het project kan worden afgesloten. Twee additionele activiteiten worden aan elk project toegevoegd, zijnde een start- (activiteit 0) en eindactiviteit (activiteit n+1). Beiden zijn zogenaamde dummy activiteiten die noch tijd, noch middelen consumeren. Ze worden toegevoegd aan het project opdat dit steeds met één activiteit zou beginnen en eindigen. Een willekeurige activiteit wordt hierbij aangeduid met de letter i. Elke activiteit i in het RCPSP wordt gekarakteriseerd door drie kenmerken: 

Tijdsduur



Precedence relations



Resource requirements

Ten eerste is er de tijdsduur di. Dit is de tijd die nodig wordt geacht om activiteit i uit te voeren. Hierbij wordt verondersteld dat eens een activiteit start, deze niet mag worden onderbroken tot ze volledig is afgewerkt. Dit is het principe van non-preemption. Als tweede kenmerk zijn er de precedence relations of volgorderelaties waarin elke activiteit i betrokken is. Dit zijn vooraf gedefinieerde volgordes tussen activiteiten die moet worden gerespecteerd. De verzameling van activiteiten die pas mogen starten nadat een activiteit i is afgewerkt, wordt gedefinieerd door Si. Het is op basis van deze informatie dat een projectnetwerk kan worden opgesteld met behulp van een Activity-on-Node (AoN) of Activity-on-Arc (AoA) voorstelling (Vanhoucke, 2012). Als derde en laatste kenmerk heeft elke activiteit i bepaalde resource requirements rik. Dit is het aantal resource eenheden van type k dat nodig is om activiteit i tot een goed einde te kunnen brengen. Resources zijn hierbij hernieuwbaar, wat betekent dat ze tijdelijk onbeschikbaar kunnen zijn op het moment dat ze voor een activiteit worden aangewend, maar opnieuw beschikbaar worden na het aflopen van die activiteit. Er worden K types hernieuwbare resources beschouwd, waarbij de beschikbaarheid van het resourcetype k bij aanvang van het project wordt weergegeven door rk. 6

Bovenstaande informatie vormt de input voor project scheduling. Het objectief dat centraal staat in het klassieke RCPSP is het minimaliseren van de totale tijdsduur. Het is met andere woorden de bedoeling om een starttijd toe te wijzen aan elke activiteit zodat de totale tijdsduur van het project minimaal is (doelfunctiewaarde) terwijl op elk tijdstip wordt voldaan aan de resource requirements en de precendence relations (restricties).

7

1.2 SAMENVATTING HOOFDSTUK 1 Het Resource Constrained Project Scheduling Problem (RCPSP) beschrijft de basisprincipes van project scheduling. Het definieert een project aan de hand van een set activiteiten die elk gekarakteriseerd worden door drie basiskenmerken: 

Tijdsduur: de tijd die nodig is om een activiteit uit te voeren



Precedence relations: de volgorderelaties die zijn opgelegd ten opzichte van andere activiteiten



Resource requirements: de middelen die nodig zijn om een activiteit uit te voeren

Hiernaast wordt een project ook gedefinieerd op basis van een evaluatiecriterium wat in het klassieke RCPSP doorgaans het minimaliseren van de totale tijdsduur is. Het is met andere woorden de bedoeling om een starttijd toe te wijzen aan elke activiteit zodat de totale tijdsduur van het project minimaal is (doelfunctiewaarde), terwijl op elk tijdstip wordt voldaan aan de resource requirements en de precendence relations (restricties). De eenvoud van het RCPSP, samen met zijn capaciteit om de fundamentele aspecten van project scheduling te vatten, maakt het een populair uitgangspunt voor allerlei uitbreidingen en varianten. Onderstaande figuur stelt het generiek model van het RCPSP schematisch voor.

Figuur 1 - Schematische voorstelling van het RCPSP

8

HOOFDSTUK 2: HET MULTI-OBJECTIVE TEAM COMPOSITION PROBLEM (MOTCP) Het doel van dit hoofdstuk is het in hoofdstuk 1 beschreven RCPSP uit te breiden naar het MultiObjective Team Composition Problem (MOTCP). Deze uitbreiding zal enerzijds de beschikbaarheid van resources op een andere manier benaderen en anderzijds meerdere evaluatiecriteria introduceren. Eerst wordt het Team Composition Problem (TCP) beschreven dat toelicht hoe resources worden benaderd binnen het MOTCP. Daarna wordt ingegaan op het concept van multi-objective optimization als additionele component bovenop het TCP. Tenslotte worden beide concepten samengevoegd tot één model dat de beschouwde probleemstelling van deze studie samenvat

2.1 TEAM COMPOSITION PROBLEM (TCP) Het Team Composition Problem (TCP) onderscheidt zich voornamelijk van het RCPSP door het feit dat resources niet aanwezig zijn als een centrale voorraad van middelen, maar eerder verspreid zijn over verschillende deelvoorraden. In de context van het TCP zijn deze deelvoorraden werknemers die vaardigheden bezitten waarmee activiteiten kunnen uitgevoerd worden. Het TCP bestaat er met andere woorden in om een aantal werknemers te selecteren die samen de juiste vaardigheden bezitten om alle projectactiviteiten zo optimaal mogelijk af te werken (Jackson, 1991). Vooraleer de individuele werknemers kunnen worden geselecteerd, dient de projectmanager een gedetailleerd beeld te vormen van alle afzonderlijke projectactiviteiten. Dit gebeurt meestal door het opstellen van een Work Breakdown Structure (WBS) waarbij abstracte taken in verschillende stappen worden opgedeeld in specifiekere activiteiten. Door het analyseren en identificeren van individuele activiteiten kan een beeld worden gevormd van enerzijds de middelen die nodig zijn voor elke activiteit en anderzijds hoe lang elke activiteit zal duren (Globerson, 1994). Eens dit is onderzocht en vastgelegd, is het de bedoeling dat een aantal individuen wordt geselecteerd die deze activiteiten tot een goed einde kunnen brengen. Het selecteren van individuen voor het samenstellen van een team kan op verschillende manieren gebeuren. Figuur 2 geeft een overzicht van de verschillende types teamsamenstellingsbeslissingen die onderscheiden worden door Mathieu et al. (2013).

9

Figuur 2 - Vier types beslissingen i.v.m. team composition

Ten eerste zijn er beslissingen waarbij een lid aan een team wordt toegevoegd, uit een team wordt verwijderd of met iemand uit het team wordt verwisseld. Bij een tweede soort beslissingen worden meerdere teamleden simultaan vervangen. Ten derde is er de situatie waar meerdere individuen moeten worden toegewezen aan meerdere teams. Een vierde en laatste beslissing is het opstellen van een nieuw team dat een bepaald probleem moet oplossen. Deze laatste beslissing zal centraal staan in het TCP dat wordt beschouwd in deze studie. Het TCP kan voorkomen in zowel een single-skilled, als in een multi-skilled omgeving. In een singleskilled omgeving bezit een individu juist één vaardigheidstype, terwijl in een multi-skilled omgeving een individu meerdere vaardigheidstypes kan bezitten. De scope van deze studie beperkt zich tot het singleskilled TCP. Een skill of vaardigheid verwijst naar bepaalde kennis of competenties die een persoon over een toepassingsdomein bezit. Enerzijds kan dit vanuit een high level perspectief worden benaderd waarbij de toepassingsdomeinen zich op het niveau van de verschillende departementen bevinden (bijvoorbeeld marketing, R&D, IT, HR…). Anderzijds kan de low level benadering worden gevolgd. Hierbij horen de toepassingsdomeinen tot één bepaald departement (bijvoorbeeld procesmodeleren, programmeren, website design en big data analyse behoren allen tot het IT departement). Omdat hier wordt gewerkt in een single-skilled omgeving, schikt de setting zich eerder voor een high level benadering. Voor het single-skilled TCP moeten werknemers worden geselecteerd voor een project op basis van de vaardigheid die ze bezitten. Op die manier kunnen ze ingezet worden voor één of meerdere projectactiviteiten. Omdat de vaardigheden centraal staan in de selectiebeslissing, is het belangrijk om een onderscheid te maken tussen de twee dimensies waarmee de vaardigheid van een werknemer wordt geclassificeerd. Een eerste dimensie is de functionele indeling van vaardigheden. Hier wordt de vaardigheid van een werknemer gedefinieerd door het type. Een vaardigheidstype correspondeert met één van de resource types die door een activiteit kan worden gevraagd. Meer bepaald werd in deze studie gebruik 10

gemaakt van vier vaardigheids-/resourcetypes. Deze werden echter niet gespecifieerd om de praktische toepasbaarheid zo groot mogelijk te houden en de case-specifieke invulling aan de lezer over te laten. Een tweede dimensie is de graduele indeling per vaardigheid. Dit is de mate waarin een werknemer een bepaald vaardigheidstype onder de knie heeft. In de praktijk vertaalt zich dat in de intensiteit en kwaliteit van de opleiding die iemand heeft genoten, de ervaring die iemand heeft verworven of het talent dat iemand bezit in dit domein. In deze studie worden drie competentieniveaus onderscheiden die worden aangeduid met respectievelijk niveau 1, 2 en 3. Deze competentieniveaus worden als cumulatief beschouwd wat betekent dat bijvoorbeeld twee werknemers van niveau 1, samen dezelfde "waarde" creëren als één werknemer van niveau 2.

2.2 MULTI-OBJECTIVE OPTIMIZATION 2.2.1 Literatuuroverzicht van objectieven Zoals eerder vermeld werd, is het bij het TCP de bedoeling om voor een bepaald project de werknemers te selecteren die dit project zo optimaal mogelijk uitvoeren. Optimaliteit wordt beschreven door de objectieven die in rekening worden gebracht tijdens het zoeken naar de beste oplossing. Bij de beschrijving van het klassieke RCPSP werd reeds het tijdsobjectief naar voren geschoven. De focus op minimalisatie van de totale tijdsduur heeft echter als gevolg dat een aantal belangrijke factoren worden genegeerd. Aspecten zoals kosten, kwaliteit, risico, veiligheid en resourcespreiding zijn soms veel relevanter dan enkel het tijdsobjectief (Vanhoucke, 2012). De andere zijde van de medaille is dat het toevoegen van meerdere objectieven aan het RCPSP ervoor zorgt dat de complexiteit sterk wordt verhoogd door het introduceren van een trade-off oefening tussen de verschillende doelstellingen. De laatste decennia werden tal van objectieven behandeld in project scheduling literatuur. Voor een overzicht wordt verwezen naar Icmeli et al. (1993), Elmaghraby (1995), Özdamar & Ulusoy (1995), Herroelen et al. (1998) en Brucker et al. (1999).

2.2.2 Objectieven in het beschouwde MOTCP Naar analogie met Pinnell & Bush (1993) wordt in deze studie uitgegaan van de idee dat een project kan worden geëvalueerd door de projectafloop te vergelijken met de vooropgestelde deadline, het vooropgestelde budget en de vooropgestelde specificaties. Dit onderscheid in deelobjectieven is beter bekend als de duivelsdriehoek (Figuur 3). In de volgende paragrafen wordt dieper ingegaan op de vertaling van deze drie objectieven naar de context van het beschouwde MOTCP.

11

Figuur 3 - Optimaliseringsobjectieven

Tijd In project scheduling literatuur is een centrale rol weggelegd voor tijdsgerelateerde objectieven. Een project heeft namelijk vaak een vooropgestelde deadline. Het is belangrijk dat de projectmanager deze afgesproken deadline respecteert omdat rechtstreekse of onrechtstreekse boetes kunnen volgen wanneer een project te vroeg of te laat klaar is. Een project dat te vroeg klaar is kan bijvoorbeeld resulteren in extra opslagvereisten of inactiviteit van resources. Wanneer een project de deadline overschrijdt, kan dit leiden tot klachten van de klant met een financiële compensatie tot gevolg. Deze trade-off werd door Vanhoucke et al. (2003) expliciet opgenomen als een Just-In-Time (JIT) objectief waarbij een gewogen gemiddelde werd genomen van deze twee tijdsgerelateerde kosten. Deze studie zal voor het tijdsobjectief niet werken met het concept van een vooropgestelde deadline. Er wordt uitgegaan van het feit dat elk moment dat men aan het project besteedt een opportuniteitskost inhoudt om elders waarde te gaan creëren met de resources die aan het project zijn toegewezen. De doelstelling komt met andere woorden neer op het minimaliseren van de totale tijdsduur. De auteurs wensen bij dit tijdsobjectief een kritische noot te plaatsen door de lezer te wijzen op het feit dat de totale projecttijdsduur een directe functie is van de tijdsduur van de individuele activiteiten. Deze informatie wordt in deze en vele andere studies als gegeven en deterministisch beschouwd. Aangezien de kwaliteit van het opgestelde projectschema sterk wordt beïnvloed door de accuraatheid van de inschattingen van de tijdsduur van de individuele activiteiten, is het essentieel dat de projectmanager over kwalitatieve data beschikt. Een slechte inschatting van de tijdsduur van de activiteiten zal elke analyse en elk schedule irrelevant maken. Dit is het bekende garbage in, garbage out (GIGO) principe. Voor een overzicht van mogelijke strategieën die kunnen worden gevolgd voor het correct inschatten van de tijdsduur van activiteiten wordt verwezen naar Vanhoucke (2012). Hier worden drie methodieken geïdentificeerd die aangewezen zijn voor een bepaald niveau van mathematische en statistische expertise bij de onderzoeker. 12

Kosten Naast het tijdsobjectief is ook een belangrijke rol weggelegd voor het kostenobjectief binnen projectmanagement (Hartmann & Briskorn, 2010). Het kostenobjectief onderscheidt zich van de tijdsgerelateerde kosten doordat ze resulteren uit het direct aanwenden van productiefactoren. Zo is een loonkost verbonden aan de productiefactor arbeid, een interestkost aan de productiefactor kapitaal en een huurkost aan het gebruik van land of andere natuurlijke hulpbronnen. De kost van productiefactoren kan bovendien ofwel variabel zijn, waarbij een kost wordt geregistreerd per tijdseenheid die de productiefactor effectief wordt gebruikt, ofwel vast zijn, waarbij een eenmalige kost wordt geregistreerd per eenheidshoeveelheid die wordt geselecteerd (Yamashita et al., 2007). Het kostenobjectief wordt in deze studie gedefinieerd als een vaste kost per geselecteerde eenheid van de productiefactor arbeid. Voor elke werknemer die geselecteerd wordt voor het project, wordt met andere woorden een vaste personeelskost geregistreerd. Het hanteren van deze definitie stelt het minimaliseren van kosten dus gelijk aan het minimaliseren van het aantal geselecteerde werknemers voor het project. De focus op de productiefactor arbeid volgt uit het feit dat human resources een belangrijke rol spelen in dit werk, zoals zal blijken uit het kwaliteitsobjectief. De keuze voor een vaste personeelskost wordt dan weer gemotiveerd door de preferentie om het kostenobjectief duidelijk te onderscheiden van het tijdsobjectief.

Kwaliteit De traditionele objectieven tijd en kosten worden in vele gevallen vergezeld van een kwaliteitsobjectief. Omdat kwaliteit een subjectief karakter heeft en een breed toepassingsdomein kent, voorziet de literatuur geen sluitende definities voor dit objectief. In het algemeen kan kwaliteit worden benaderd als de mate waarin een project voldoet aan vooropgestelde specificaties. Veelal volgt hierbij een terugkoppeling naar de tevredenheid van een interne of externe klant. Voor het kwaliteitsobjectief richt deze studie zich op een trend in projectmanagement die reeds werd aangehaald in de inleiding. Er wordt hoe langer hoe meer aandacht besteed aan groepsdynamiek als potentiële bron van synergiën in een projectteam. Het betrekken van de noden en wensen van individuele werknemers kan dus toegevoegde waarde creëren in een project (Van den Bergh et al., 2012). De persoonlijke voorkeuren van en tussen werknemers wordt gedefinieerd door de term sociale cohesie. Deze term slaat enerzijds op de mate waarin werknemers zich geaccepteerd voelen in een groep (Beal et al., 2003) en anderzijds op de mate waarin teamleden in een bepaalde groep willen blijven (Mullen and

13

Copper, 1994). Onderzoek van verschillende auteurs heeft geleid tot de conclusie dat er een positieve relatie bestaat tussen sociale cohesie en project performantie (Mullen and Copper, 1994; Guzzo and Shea 1992; Helfert, 1998; Lechler, 2001; Summers, 1988). Deze studie vertrekt vanuit de basisfilosofie dat een grotere sociale cohesie in een projectteam leidt tot een betere kwaliteit en dus tot hogere toegevoegde waarde van het project. Net zoals het bij het tijdsobjectief belangrijk is om de duurtijden van de activiteiten accuraat in te schatten, is voor het kwaliteitsobjectief de juistheid van de informatie over de sociale cohesie tussen werknemers van zeer groot belang. Gegeven het subjectieve karakter van kwaliteit is dit echter geen evidentie. Een beschrijving van hoe deze informatie kan worden achterhaald, kan gevonden worden bij Ballesteros–Pérez et al. (2012) die een methode naar voren schuiven om op basis van een sociometrische test de sociale cohesie tussen twee personen kwantitatief uit te drukken als een getal tussen 0 en 100. Naast het achterhalen van deze informatie is een tweede uitdaging het up-to-date houden ervan omdat sociale relaties erg dynamisch en variabel zijn.

2.3 MOTCP MODEL Het beschreven TCP en het concept van multi-objective optimization leiden samen tot het MOTCP dat centraal staat in deze studie. Deze twee fundamentele principes maken deel uit van een breder omliggend kader, dat verder wordt gespecificeerd in bijlage 1. Hier worden de belangrijkste assumpties omtrent de beschouwde probleemstelling opgelijst. Deze informatie laat toe een model op te stellen bestaande uit variabelen, een doelfunctie en een restricties. Dit model wordt in volgende paragrafen voorgesteld.

2.3.1 Variabelen en inputparameters Beslissingsvariabelen = 1 als activiteit i start op tijdstip t, 0 in alle andere gevallen (met i

1,…,n)

= 1 als werknemer w op tijdstip t gescheduled is, 0 in alle andere gevallen Afgeleide variabelen = verzameling van alle activiteiten actief op tijdstip t = 1 als werknemer w geselecteerd wordt voor het project, 0 indien niet

14

Inputparameters = vraag naar resources van activiteit i voor resource type k = tijdsduur van activiteit i = competentieniveau van werknemer w voor vaardigheidstype k ( {1,2,3}) {}

= verzameling van activiteiten die activiteit i onmiddellijk opvolgen = sociale cohesie tussen werknemer w1 en werknemer w2 (

)

2.3.2 Doelfunctie Minimaliseer

(1)

(2)

(3)

De doelfunctie is onderverdeeld in drie deeldoelfuncties: tijd (1), kosten (2) en kwaliteit (3). De totale doelfunctiewaarde wordt voor deze drie objectieven berekend door het vergelijken van de optimale waarde voor het project met de werkelijke waarde. Op die manier worden de objectieven onderling vergelijkbaar tijdens de evaluatie van een oplossing. De volgende paragrafen beschrijven voor alle deelobjectieven hoe de termen "optimaal" en "werkelijk" worden toegepast in de context van het beschouwde MOTCP. (1) TIJD De werkelijke projectduur is het verschil tussen de starttijd van de eerste activiteit en eindtijd van de laatste activiteit. Aangezien verondersteld wordt dat een project start op tijdstip t=0, is de werkelijke projectduur niets anders dan het moment waarop de finale activiteit volledig is afgewerkt. De optimale projectduur wordt, zoals toegelicht in 2.2.2, in het beschouwde MOTCP niet gedefinieerd door middel van een deadline. Tijd wordt namelijk beschouwd als een pure opportuniteitskost. Omdat een project echter onderhevig is aan opgelegde volgorderelaties tussen activiteiten, kan toch een ideaal referentieschema naar voren worden geschoven waarin elke activiteit kan en zal worden aangevat op het moment dat haar voorgangers afgewerkt zijn. Wanneer dit principe voor elke activiteit wordt doorgetrokken, resulteert dit in het Earliest Start Schedule (ESS) van het project. Merk op dat dit de

15

absolute ondergrens is van het gedefinieerde tijdsobjectief aangezien geen rekening gehouden wordt met eventuele resource restricties.

(2) KOSTEN Zoals in paragraaf 2.2.2 werd beschreven, kan het kostenobjectief herleid worden tot het minimaliseren van het aantal geselecteerde werknemers. Het werkelijk aantal werknemers wordt dan ook gedefinieerd als het aantal werknemers dat heeft bijgedragen tot de verwezenlijking van één of meerdere activiteiten in een project. Het optimaal aantal werknemers is het minimaal aantal werknemers waarmee het mogelijk is alle activiteiten in een project uit te voeren. Voor het kostenobjectief worden in het ideale geval met andere woorden alle activiteiten sequentieel uitgevoerd. Na elke activiteit worden de ingezette werknemers namelijk terug beschikbaar, waardoor geen extra werkkrachten moeten worden geselecteerd. In de beschouwde single-skilled omgeving komt het er dus op neer om de maximale vraag naar elk resource/vaardigheidstype te achterhalen. In het optimale geval kan deze maximale vraag ingevuld worden door uitsluitend gebruik te maken van werknemers met een competentieniveau van 3 voor deze vaardigheid. Wanneer geweten is voor elk vaardigheidstype hoeveel werknemers er minimaal nodig zijn om de maximale vraag te beantwoorden, is het optimaal aantal werknemers niets anders dan de som hiervan.

(3) SOCIALE COHESIE Sociale cohesie wordt voorgesteld door een asymmetrische matrix waarbij een coëfficiënt tussen 0 en 100 wordt toegewezen aan elke relatie tussen twee werknemers. De werkelijke sociale cohesie wordt dan berekend als het gemiddelde van de sociale cohesie coëfficiënten tussen de werkelijk geselecteerde werknemers. Optimale sociale cohesie zal plaatsvinden wanneer tussen elk duo van geselecteerde werknemers een sociale cohesie coëfficiënt van 100 bestaat. Dit zal met andere woorden resulteren in een gemiddelde sociale cohesie van 100. Merk op dat een verschil optreedt in vergelijking met de deelobjectieven tijd en

16

kosten. Bij deze objectieven vormde de optimale waarde een ondergrens, voor sociale cohesie is dit een bovengrens. Daarom wordt voor dit objectief de optimale waarde gedeeld door de werkelijke waarde.

2.3.3 Restricties ∑ ∑

+

∑

∑

=

1

(1)

≤

∑

(2)

≥

∑

(3)

≥

∑

(4)

≥

(5)

=

∑

(6)

=

∑

(7)

=

∑

∑ ∑

(8)

, Restrictie (1) geeft weer dat elke activiteit ergens moet aangevat worden tussen zijn Earliest en Latest Start of met andere woorden dat elke activiteit van het project moet gescheduled worden. Restrictie (2) geeft de precedence relationships constraints weer. Als activiteit i de voorhanger is van activiteit j, dan kan activiteit j maar starten eens activiteit i is beëindigd. Restrictie (3) zorgt ervoor dat de ingezette hoeveelheid van vaardigheid k op elk ogenblik groot genoeg moet zijn om te voldoen aan de vraag naar deze resource voor de op dat ogenblik geschedulde activiteiten. In restricties (4) en (5) wordt de relatie tussen de variabelen wnw en wnwt vastgelegd waarbij een werknemer wordt geselecteerd voor een project als deze minimaal op één tijdstip tewerkgesteld geweest is. Constraints (6), (7) en (8) beschrijven de berekening van de werkelijke waarden in de deeldoelfuncties.

17

2.3.4 Bespreking van het model Op basis van het bovenstaande MOTCP model kan worden bepaald 

wat de starttijden zijn van de activiteiten



welke werknemers worden ingezet voor welke activiteit omwille van welke vaardigheid

Het is echter duidelijk dat de spreiding van resources over werknemers en het hanteren van drie deelobjectieven de complexiteit van het probleem sterk verhoogt in vergelijking met het klassieke RCPSP. Dit wordt vertaald in het model door constraints (3), (7) en (8). Deze complexiteit brengt met zich mee dat een optimalisatie van het probleem te veel werk zou vragen. Vaak wordt voor dergelijke problemen een oplossing gezocht aan de hand van heuristieken. Deel 2 zal dieper ingaan op project scheduling in complexere settings.

18

2.4 SAMENVATTING HOOFDSTUK 2 Het Multi-Objective Team Composition Problem (MOTCP) is een uitbreiding van het klassieke RCPSP. Bij dit probleem tracht men een groep van individuen te selecteren die samen al de projectactiviteiten zo efficiënt mogelijk kunnen uitvoeren. Een overzicht van de belangrijkste assumpties is terug te vinden in bijlage 1. De verhoogde complexiteit is terug te leiden tot twee zaken: 1. Team Composition Problem Een resourcetype is niet aanwezig als een centrale voorraad van middelen maar is verspreid over verschillende deelvoorraden. In de context van het single-skilled TCP zijn deze deelvoorraden werknemers die elk één vaardigheidstype bezitten met een bijhorend competentieniveau.

2. Multi-Objective Optimization Naast het minimaliseren van de projectduur (tijdsobjectief) moet er ook worden gestreefd naar minimalisatie van het aantal geselecteerde werknemers (kostenobjectief) en een maximalisatie van de sociale cohesie (kwaliteitsobjectief).

Figuur 4 - Schematische voorstelling van het MOTCP

19

DEEL 2 - COMPLEX PROJECT SCHEDULING

20

INLEIDING In Deel 1 werd in detail ingegaan op het MOTCP als uitbreiding op het klassieke RCPSP. Net zoals vele andere uitbreidingen op en varianten van het RCPSP ging dit gepaard met een toegenomen complexiteit van het project scheduling vraagstuk voor de projectmanager. Het MOTCP wordt algemeen beschouwd als een NP-hard probleem (Blazewick et al., 1983). Dit betekent dat, hoewel het relatief eenvoudig is om een gegeven oplossing te evalueren, het veel tijd en moeite vergt om het probleem in zijn geheel aan te pakken en de optimale oplossing te vinden. In dergelijke gevallen wordt veelal geopteerd voor alternatieve oplossingsstrategieën. Hiervoor wordt de restrictie dat de oplossingsstrategie moeten leiden tot de meest optimale oplossing versoepeld en wordt vrede genomen met een oplossing die aanvaardbaar is, gegeven de tijd en moeite die het vergt om ze te vinden. Een populair voorbeeld van een dergelijke strategie is het gebruik van metaheuristieken. Dit zijn procedures gebaseerd op het systematisch gebruik van trial and error. Er worden met andere woorden op een intelligente manier mogelijke oplossingen voor het probleem gegenereerd, waarvan de kwaliteit kan worden nagegaan en waarbij de beste oplossing wordt onthouden. Naast de inherente complexiteit van het MOTCP, hangt de uiteindelijke complexiteit van een specifiek project sterk af van het beschouwde projecttype. Zo kan het MOTCP toegepast worden voor het samenstellen van een team voor het bouwen van een huis, maar evengoed voor het organiseren van een event. In het eerste geval heeft men te maken met een project dat typisch bestaat uit opeenvolgende activiteiten (bijvoorbeeld fundering leggen en ruwbouw zetten) terwijl in het tweede geval veel zaken simultaan kunnen plaatsvinden (bijvoorbeeld sponsors zoeken en de drankleverancier contacteren). Dit is uiteraard maar een voorbeeld van de vele manieren waarop een project kan worden getypeerd. De verschillende criteria die kunnen worden aangewend om projecten te categoriseren, worden in project scheduling aangeduid als projectindicatoren. Deel 2 van dit werk zal toelichten hoe men kan omgaan met complexiteit in project scheduling. Concreet zal Hoofdstuk 3 dieper ingaan op mogelijke complexiteitsverschillen tussen projecten in een MOTCP-omgeving door het definiëren van projecttypes. Hoofdstuk 4 zal vervolgens enkele metaheuristieken toelichten die hun relevantie ontlenen aan de aandacht die ze vandaag genieten in projectmanagement literatuur en onderzoek.

21

HOOFDSTUK 3: PROJECTTYPES Het doel van dit hoofdstuk is dieper in te gaan op de determinanten van projectcomplexiteit binnen het beschouwde MOTCP. Een reeks projectindicatoren worden aangehaald om een overzicht te bieden van mogelijke projecttypes die kunnen worden onderscheiden. Een projectindicator bevat specifieke projectinformatie die kan opgevraagd worden door de projectmanager vooraleer hij begint met project scheduling. Eerst en vooral wordt ingegaan op die projectindicatoren die in de literatuur algemeen aanvaard worden als bronnen van informatie. Daarna worden enkele additionele projectindicatoren geïdentificeerd die in de beschouwde MOTCP omgeving als additionele bron van informatie kunnen dienen.

3.1 TRADITIONELE PROJECTINDICATOREN De projectmanagement literatuur introduceerde en evalueerde doorheen de jaren een reeks projectindicatoren. Twee grote groepen van projectindicatoren kunnen hierin worden onderscheiden. Enerzijds zijn er de topologische indicatoren die een project bekijken als een netwerk van verbonden activiteiten. Deze indicatoren bevatten informatie over de structuur van een dergelijk netwerk. Anderzijds zijn er ook de resource gerelateerde indicatoren die een project beschouwen vanuit het oogpunt van vraag en aanbod van resources. In volgende paragrafen worden deze twee groepen verder behandeld.

3.1.1 Topologische projectindicatoren De topologie van een projectnetwerk beschrijft de onderlinge volgorderelaties tussen activiteiten, hetgeen in zijn totaliteit resulteert in een projectnetwerk. Het visualiseren van de projecttopologie gebeurt doorgaans aan de hand van een Activity-on-Node netwerk (AoN). Hier worden activiteiten voorgesteld als knooppunten in een netwerk en volgorderelaties als pijlen tussen deze knooppunten (Vanhoucke et al., 2008). Topologische projectindicatoren bevatten de informatie die de structuur van een dergelijk projectnetwerk beschrijft. In wat volgt wordt ingegaan op enkele van deze topologische projectindicatoren zoals geïdentificeerd door Vanhoucke et al. (2008). Samen geven zij een overzicht van de belangrijkste topologische indicatoren zoals die zijn opgenomen in de projectgenerator RanGen2. Met dit software programma kunnen projecten worden gegenereerd die voldoen aan vooraf gespecificeerde projectindicatoren (Demeulemeester et al., 2003). RanGen2 zal ook in het onderzoeksgedeelte van deze studie worden gebruikt om projecten te genereren. Vooraleer wordt ingegaan op de verschillende topologische projectindicatoren wordt eerst een concept naar voren gebracht dat een centrale rol speelt in het beschrijven van de netwerkmorfologie, 22

namelijk het hiërarchische level. Dit is de relatieve positie van een activiteit in een netwerk van activiteiten. Het hiërarchische level wordt gespecificeerd door het progressieve level enerzijds en het regressieve level anderzijds. Het eerste verwijst naar de relatieve positie van een activiteit ten opzichte van het begin van het netwerk en het tweede naar de relatieve positie van een activiteit ten opzichte van het einde van het netwerk (Elmaghraby, 1977). Voor meer informatie over de interpretatie en de berekeningen achter deze concepten wordt verwezen naar bijlage 2. Hieronder worden de zes door Vanhoucke et al. (2008) beschreven indicatoren besproken.

I1 - Netwerkgrootte indicator Deze indicator beschrijft de grootte van een projectnetwerk. Het is een natuurlijk getal, aangeduid met de letter n, dat verwijst naar het aantal niet-dummy activiteiten in een projectnetwerk. I1 = n

I2 - Serieel/Parallel indicator Deze indicator beschrijft de mate waarin een projectnetwerk aanleunt bij een 100% parallel (I2 = 0) of een 100% serieel (I2 = 1) netwerk. De formule achter I2 wordt hieronder weergegeven. Hierbij is m het maximale progressieve level en n het aantal niet-dummy activiteiten in een projectnetwerk. I2 = {

Omwille van het belang van deze projectindicator in de literatuur en in dit werk, wordt even langer stilgestaan bij het verschil tussen een serieel en een parallel netwerk. Figuren 5 en 6 geven een projectnetwerk weer van vier non-dummy activiteiten in respectievelijk een 100% parallelle configuratie (I2 = 0) en een 100% seriële configuratie (I2 = 1). Ook de interpretatie dat projectindicator I2 veelal gezien wordt als een relatieve maatstaf voor het aantal activiteiten dat op het kritische pad ligt (Tavares et al., 1999), valt uit deze figuren af te leiden.

23

100% Parallel I2 = 0

100% Serieel I2 = 1

Figuur 5 - Netwerktopologie voor I2 = 1

Figuur 6 - Netwerktopologie voor I2 = 0

I3 - Activiteitsdistributie indicator Deze indicator beschrijft de mate waarin de activiteiten evenwichtig zijn verdeeld over de progressieve levels. Een I3-waarde 0 betekent dat er evenveel activiteiten voorkomen op elk progressief level, terwijl een I3 waarde 1 betekent dat alle progressieve levels uit slechts één activiteit bestaan, behalve één level dat bestaat uit n-m-1 activiteiten. Onderstaande formule geeft de wiskundige vertaling van deze indicator weer. Hier is wa de breedte van een gegeven progressief level a

{1,…,m}. Deze breedte is het

aantal activiteiten dat tot een bepaald progressief level behoort. De parameter wgem beschrijft de gemiddelde breedte van de progressieve levels.

I3 = { ∑

|

|

I4 - Korte pijlen-indicator De I4-indicator is een relatieve weergave van het aantal korte precedence relationships. Een korte precedence relationship wordt in een projectnetwerk gedefinieerd als een pijl waarvan het verschil tussen het progressief level van de starten eindactiviteit 1 is. Als alle mogelijk precedence relationships kort en bestaand zijn, wat betekent dat alle activiteiten behorende tot een progressief level een precedence relationship hebben met alle activiteiten van het volgende progressieve level, dan heeft I4 de waarde 1. Een minimaal aantal korte pijlen resulteert in een I4 die 0 is. Onderstaande formule is een vertaling van deze 24

kwalitatieve beschrijving in mathematische vorm. Hierbij is D het maximaal aantal mogelijke korte pijlen in een netwerk en n’1 het werkelijk aantal pijlen met lengte 1.

I4 = {

met D = ∑

Wanneer er veel korte pijlen aanwezig zijn in een netwerk betekent dit dat er weinig flexibiliteit is in het schedulen van de activiteiten. Er zijn namelijk weinig mogelijkheden om activiteiten later te schedulen zonder dat de totale tijdsduur van het project verandert (Tavares, 1999).

I5 - Lange pijlen-indicator Deze indicator is een relatieve weergave voor het aantal lange precedence relationships. Een lange precedence relationship wordt in een projectnetwerk gedefinieerd als een pijl waarvan het verschil tussen het progressief level van starten eindactiviteit groter dan 1 is. De I5-indicator heeft een waarde gelijk aan 0 als n-w1 pijlen een lengte 1 hebben en alle andere pijlen een maximum lengte van m-1. De I5-indicator heeft een waarde 1 als alle pijlen een lengte 1 hebben. Onderstaande formule geeft dit mathematisch weer. Hierbij is n’l het werkelijk aantal pijlen met lengte l en A de verzameling van pijlen in het netwerk. | | I5 = {

(∑

) | |

| |

I6 - Toplogische float indicator De laatste topologische projectindicator die hier wordt besproken is I6. Deze indicator meet het gemiddelde verschil tussen het regressieve en progressieve level van alle activiteiten. Als dit verschil voor alle activiteiten gelijk is aan 0, neemt de I6-indicator een waarde van 0 aan. In het geval van een netwerk met m seriële activiteiten en n-m parallelle activiteiten (met RLi - PLi = m-1) is I6 gelijk aan 1.

I6 = {

∑

25

3.1.3 Resource gerelateerde projectindicatoren Naast de topologie van een netwerk bestaan er in de literatuur ook projectindicatoren die gerelateerd zijn aan de resources. Deze benaderen een project als vraag en aanbod van resources. Naast het aantal verschillende resource types dat aanwezig is in een project, kunnen projectindicatoren ook inzicht geven in de vraag naar resources door activiteiten te specificeren in type en hoeveelheid. Deze indicatoren worden in deze studie deterministisch gedefinieerd om de scope van de studie te beperken.

K - # resource types Deze indicator specifieert het aantal hernieuwbare resource types die beschikbaar zijn in een project. Deze resources worden actief gevraagd door een aantal activiteiten. In deze studie is K = 4.

RU - Resource Use Deze indicator is een maatstaf voor het aantal verschillende resources types dat een activiteit vraagt. De bovengrens van RU wordt bepaald door K, het aantal resource types dat aanwezig is in het project. Een nadeel van deze indicator is dat ze geen variatie toelaat over de activiteiten. In deze studie is RU = 3, wat concreet betekent dat elke activiteit telkens 3 van de 4 resource types zal vragen.

RC - Resource Constrainedness Deze indicator is een maatstaf voor het aantal resource eenheden dat een activiteit gemiddeld vraagt voor een resource type. Concreet wordt deze vraag relatief weergegeven door een getal uit het interval ]0,1]. In deze studie is RC = 0.4, wat betekent dat voor elk resource type, de activiteiten gemiddeld 40% van de totale beschikbaarheid van deze resource vragen.

3.2 ADDITIONELE PROJECTINDICATOREN VOOR HET BESCHOUWDE MOTCP In sectie 3.1 werd toegelicht welke topologische en resource gerelateerde parameters een project kunnen karakteriseren. Deze studie zal deze parameters gebruiken als eerste luik voor het definiëren van een project. Daarenboven zullen een aantal andere indicatoren naar voren worden geschoven die zich lenen tot het beschrijven van het MOTCP. Het complexere karakter van het MOTCP brengt namelijk met zich mee dat extra informatie beschikbaar is. Enerzijds zijn er de resources die op een bepaalde manier verdeeld zijn over de werknemers door middel van competentieniveaus en anderzijds is er de sociale cohesie tussen werknemers. Informatie hieromtrent laat toe nieuwe projecttypes te onderscheiden.

26

3.2.1 Competentieniveau-gerelateerde projectindicatoren In het MOTCP wordt het aanbod van resources gedefinieerd als vaardigheden die behoren tot werknemers waarbij het competentieniveau de kwantiteit bepaalt. In deze studie wordt informatie over de aanwezigheid van vaardigheden bij de werknemers mee geïncorporeerd bij de mogelijke indicatoren die de complexiteit van een project beschrijven. Twee parameters worden in deze context naar voren geschoven: het gemiddelde competentieniveau per vaardigheid en de variantie van dit competentieniveau doorheen de volledige groep.

µc - Gemiddeld competentieniveau Deze projectindicator specificeert het gemiddelde µc van een normaalverdeling

waaruit

een competentieniveau wordt bepaald en toegewezen aan de vaardigheid die elke werknemer bezit.

CVc - Variatiecoëfficiënt van het competentieniveau Deze projectindicator specificeert de variatiecoëfficiënt CVC die samen met het gemiddeld competentieniveau µc, de standaardafwijking

van een normaalverdeling

specificeert.

Hieruit wordt een competentieniveau bepaald en toegewezen aan de vaardigheid die elke werknemer bezit. De variatiecoëfficiënt is een relatieve maatstaf voor de variantie door deze laatste uit te drukken ten opzichte van het gemiddelde (Hopp & Spearman, 2011). De kracht van deze indicator ligt in het feit dat ze toelaat de varianties te vergelijken van zaken die niet gerelateerd zijn. Hieronder wordt uitgelegd hoe deze indicator wordt berekend en welke intervallen worden beschouwd om de mate van variantie te definiëren. Deze intervallen werden gedefinieerd op basis van Hopp & Spearman (2011).

𝜇 Tabel 1 - Gradaties in de variatiecoëfficiënt

CV INTERVAL [0 - 0.75] ]0.75 - 1 ] ]1 - 1.33] ]1.33 - +∞[

MATE VAN VARIANTIE Lage variantie Medium-lage variantie Medium-hoge variantie Hoge variantie

27

3.2.1 Sociale cohesie-gerelateerde projectindicatoren In het MOTCP krijgen resources een extra dimensie door het bestaan van een sociale cohesiecoëfficiënt tussen elk werknemersduo. Deze studie schuift informatie over de sociale cohesie in een groep werknemers naar voren als een mogelijke projectindicator die mede de complexiteit van een project bepaalt. Deze informatie valt onder te brengen in twee parameters: het gemiddelde sociale cohesie niveau en de variantie van deze sociale cohesie doorheen de volledige groep.

µs - Gemiddelde sociale cohesie Deze projectindicator specifieert het gemiddelde µs van een normaalverdeling

𝜇

waaruit

een sociale cohesie-factor wordt bepaald en toegewezen aan een werknemerskoppel.

CVs - Variatiecoëfficiënt van sociale cohesie Deze projectindicator specificeert de variatiecoëfficiënt CVs die samen met het gemiddeld competentieniveau µs de standaardafwijking

van een normaalverdeling

specifieert waaruit

een sociale cohesie-factor wordt bepaald en toegewezen aan een werknemerskoppel. De berekening en interpretatie van deze indicator gebeurt analoog als deze bij de variatiecoëfficiënt van het competentieniveau.

28

3.3 SAMENVATTING HOOFDSTUK 3 De complexiteit van project scheduling wordt enerzijds bepaald door de aard van het probleem zelf en anderzijds door projectspecifieke aspecten. Dit laatste wordt gekwantificeerd door projectindicatoren die informatie bevatten over het project en kunnen worden opgevraagd door de projectmanager vooraleer hij begint met project scheduling. Deze informatie is ofwel gerelateerd aan de topologie van een projectnetwerk ofwel aan de resources die ter beschikking staan en worden geconsumeerd door de activiteiten. Het MOTCP introduceert de mogelijkheid om naast een aantal traditionele projectindicatoren een aantal extra projectindicatoren te definiëren die probleemspecifieke informatie bevatten. Onderstaande tabel geeft een compleet overzicht van de projectindicatoren die in deze studie worden beschouwd als potentiële drivers van projectcomplexiteit.

Tabel 2 - Overzicht van de beschouwde projectindicatoren

TYPE PROJECTINDICATOR Topologische projectindicatoren

INDICATOR

OMSCHRIJVING Serieel/Parallel indicator Activiteitsdistributie indicator Korte Pijlen indicator Lange Pijlen indicator Topologische Float indicator

Resource gerelateerde projectindicatoren

𝜇

Gemiddeld Competentieniveau Variatiecoëfficiënt Competentieniveau

𝜇

Gemiddelde Sociale Cohesie Variatiecoëfficiënt Sociale Cohesie

29

HOOFDSTUK 4: METAHEURISTIEKEN Het doel van dit hoofdstuk is het introduceren van metaheuristieken. Zoals in de inleiding reeds werd besproken, zijn dit alternatieve strategieën voor het oplossen van complexe problemen zoals het MOTCP. Eerst worden twee algoritmes besproken die kunnen worden aangewend om een project systematisch in te plannen. Daarna wordt ingegaan op twee metaheuristieke procedures. Aangezien een planningsalgoritme kan worden ingezet als onderdeel van een metaheuristieke procedure, kunnen vier grote metaheuristieken onderscheiden worden die een centrale rol zullen spelen in het onderzoek van deze studie. Het hoofdstuk besluit met een korte toelichting van de oplossingsvoorstelling die zal worden gebruikt om met deze metaheuristieken te werken.

4.1 SCHEDULE GENERATION SCHEMES Het eerste deel van hoofdstuk 4 geeft de achtergrond van het concept schedule generation schemes weer. Dit zijn methodes die bepalen hoe het eigenlijke schedule wordt opgebouwd door het toewijzen van starttijden aan de activiteiten van een project enerzijds en het toewijzen van resources aan de activiteiten anderzijds. Doorgaans worden er twee varianten onderscheiden: het Serial Schedule Generation Scheme (SSGS) en het Parallel Schedule Generation Scheme (PSGS). Beiden hebben een specifiek uitgangspunt om een schedule op te bouwen, maar zowel SSGS als PSGS gebruiken hiervoor prioriteitslijsten. Dit zijn beslissingsregels die worden gehanteerd om de activiteiten of werknemers te selecteren. In wat volgt wordt eerst kort ingegaan op het concept van prioriteitslijsten waarna de methodes SSGS en PSGS stap voor stap worden toegelicht met behulp van een eenvoudig voorbeeld.

4.1.1 Prioriteitslijsten Een prioriteitslijst bepaalt een rangorde op basis waarvan sequentieel een selectie plaatsvindt. Een prioriteitsregel zal de beschikbare projectinformatie op een unieke manier gebruiken om zo een hiërarchie naar voren te schuiven. Ze zorgen er voor dat er een uitgesproken preferentie bestaat wanneer men dient te kiezen tussen gelijkwaardige alternatieven (Kolisch, 1996). Doorgaans worden prioriteitsregels gebruikt om activiteiten te prioritiseren maar in het MOTCP zullen ook werknemers geselecteerd worden op basis van prioriteitslijsten. Vanhoucke (2012) beschrijft vier klassen van prioriteitsregels voor activiteiten. De klasse van de activiteitsgebaseerde regels gebruikt de informatie van de activiteiten zelf zoals bijvoorbeeld de tijdsduur. De klasse van de netwerkgebaseerde regels bouwt verder op de informatie in verband met de relaties 30

tussen activiteiten, zoals bijvoorbeeld het aantal activiteiten dat aan een beschouwde activiteit voorafgaat. Een derde klasse baseert zich op het kritische pad en zal bijvoorbeeld informatie over de vroegst of laatst mogelijke start- of eindtijd van activiteiten gebruiken. De vierde en laatste klasse die wordt onderscheiden, wordt gevormd door resource-gebaseerde regels die logischerwijs de vraag van activiteiten naar resources verder analyseert. Prioriteitslijsten voor werknemers zijn zowel minder courant als minder gestandaardiseerd in de literatuur. Prioriteitslijsten vormen de basis van het schedule generation scheme. In de volgende paragrafen wordt ingegaan op SSGS en PSGS. Beide methodes werken op basis van prioriteitslijsten, maar de manier waarop deze worden gebruikt, verschilt.

4.1.2 Serial Schedule Generation Scheme (SSGS) Om de logica van elk schedule generation scheme te verduidelijken, werd geopteerd om zowel SSGS als PSGS te illustreren aan de hand van een centraal voorbeeld. Beschouw hiervoor onderstaand ActivityOn-Node (AoN) netwerk (Figuur 7) bestaande uit 10 activiteiten waaronder 2 dummy activiteiten. Voor elke activiteit wordt de tijdsduur en de vraag naar resources gespecificeerd door respectievelijk een superscript en subscript. Om de complexiteit te beperken, wordt hier verondersteld dat er slechts één resource is met een hernieuwbaar karakter en met een totale beschikbaarheid van vijf eenheden. Naast dit netwerk is er ook een prioriteitslijst voorhanden die een rangorde beschrijft tussen de activiteiten.

Figuur 7 - Voorbeeld SSGS en PSGS (AoN netwerk)

31

Bij de SSGS-methode worden activiteiten één voor één in volgorde van de prioriteitslijst overlopen en zo vroeg mogelijk gescheduled, rekening houdend met de precedence relationships en de beschikbaarheid van resources. Omdat een iteratie in SSGS bestaat uit het selecteren van een volgende activiteit spreekt men van activity-incrementation (Artigues et al., 2005). In wat volgt, wordt stap voor stap door de iteraties gegaan die worden gevolgd bij het toepassen van SSGS op bovenstaand voorbeeldproject. ITERATIE 1

Activiteiten: { 0, 1, 5, 7, 2, 3, 6, 8, 4, 9} Bij de eerste iteratie wordt activiteit 0 geselecteerd als de activiteit met de hoogste prioriteit. Aangezien dit een dummy activiteit is, verbruikt deze noch tijd noch resources en dient ze dan ook niet expliciet te worden gescheduled. Bij deze eerste iteratie wordt dus direct doorverwezen naar de volgende stap. ITERATIE 2 Activiteiten: { 0, 1, 5, 7, 2, 3, 6, 8, 4, 9} Na de eerste iteratie zijn activiteiten 1, 2, 3 en 4 beschikbaar geworden. Activiteit 1 wordt door de prioriteitslijst naar voren geschoven om eerst te worden gescheduled. Het AoN-netwerk geeft aan dat de activiteit 2 tijdseenheden en 1 resource eenheid vergt. SSGS wil deze activiteit zo vroeg mogelijk inplannen en aangezien er in deze fase nog geen activiteiten aan de gang zijn, kan activiteit 1 worden aangevat op tijdstip 0.

Figuur 8 - Voorbeeld SSGS 1

32

ITERATIE 3 Activiteiten: { 0, 1, 5, 7, 2, 3, 6, 8, 4, 9} Na de tweede iteratie zijn activiteiten 2, 3, 4 en 5 beschikbaar. Activiteit 5 wordt door de prioriteitslijst naar voren geschoven om als eerste te worden gescheduled. Het AoN-netwerk geeft aan dat deze activiteit 5 tijdseenheden en 3 resource eenheden vergt. SSGS plant deze activiteit zo vroeg mogelijk, rekening houdend met de precedence relations en de resource beschikbaarheid. Activiteit 5 kan enkel plaatsvinden vanaf tijdstip 2 omdat activiteit 1 pas dan is afgewerkt en er een precedence relationship bestaat tussen activiteiten 1 en 5.


ITERATIE 4 Activiteiten: { 0, 1, 5, 7, 2, 3, 6, 8, 4, 9} Na de derde iteratie zijn activiteiten 2, 3, 4 en 7 beschikbaar. Activiteit 7 wordt door de prioriteitslijst aangeduid om te worden gescheduled. Het AoN-netwerk geeft aan dat deze activiteit 1 tijdseenheid en 1 resource eenheid vergt. Activiteit 7 kan enkel plaatsvinden vanaf tijdstip 7 omdat activiteit 5 dan is afgewerkt en er een precedence relationship bestaat tussen de twee.


33

ITERATIE 5 Activiteiten: { 0, 1, 5, 7, 2, 3, 6, 8, 4, 9} Na de vierde iteratie zijn activiteiten 2, 3 en 4 beschikbaar. Activiteit 2 wordt door de prioriteitslijst naar voren geschoven om te worden gescheduled. Het AoN-netwerk geeft aan dat deze activiteit 1 tijdseenheid en 2 resource eenheden vergt. SSGS wil deze activiteit zo vroeg mogelijk inplannen rekening houdend met de precedence relations en de resource beschikbaarheid. Aangezien activiteit 2 niet gebonden is door precedence relations zoekt de SSGS-methode het vroegst mogelijke tijdstip waarop nog voldoende resources aanwezig zijn. In dit geval is dit tijdstip 0.


ITERATIE 6 - 10 Wanneer bovenstaande logica wordt doorgetrokken zullen, nog 5 iteraties plaatsvinden vooraleer alle activiteiten zijn ingepland. Hieronder worden kort de overblijvende iteraties aangehaald waarna het resultaat wordt getoond dat verkregen wordt na iteratie 10. Het project zou dan uiteindelijk een totale tijdsduur hebben van 11 tijdseenheden.

Iteratie 6: { 0, 1, 5, 7, 2, 3, 6, 8, 4, 9}

Iteratie 7: { 0, 1, 5, 7, 2, 3, 6, 8, 4, 9}

Iteratie 8: { 0, 1, 5, 7, 2, 3, 6, 8, 4, 9}

Iteratie 9: { 0, 1, 5, 7, 2, 3, 6, 8, 4, 9}

Iteratie 10: { 0, 1, 5, 7, 2, 3, 6, 8, 4, 9}

34


4.1.3 Parallel Schedule Generation Scheme (PSGS) Waar een iteratie in SSGS gebaseerd is op activity-incrementation, wordt bij PSGS geïtereerd over de tijdshorizon (Artigues et al., 2005). Bij deze aanpak, ook wel time-incrementation genoemd, wordt op elk tijdstip een overzicht gemaakt van alle activiteiten die, rekening houdend met de precedence relationships, beschikbaar zijn om gescheduled te worden. Deze activiteiten worden gesorteerd op basis van de prioriteitslijst en één voor één gescheduled op voorwaarde dat er voldoende resources beschikbaar zijn. Opnieuw wordt het voorbeeldnetwerk uit 4.1.2 gebruikt om deze methode te illustreren door stap voor stap door de iteraties te gaan die worden gevolgd door PSGS. ITERATIE 1 Tijd: { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15…} Bij de eerste iteratie worden alle activiteiten geselecteerd die kunnen aanvangen op tijdstip 0. Deze activiteiten worden vervolgens gerangschikt op basis van de prioriteitslijst. Dummy activiteit 0 wordt hierbij voor de eenvoud buiten beschouwing gelaten omdat deze alleen de start van het project aanduidt terwijl dit bij PSGS automatisch gebeurt bij het ingaan van de eerste iteratie. PSGS zal proberen zo veel mogelijk activiteiten te schedulen die op een gegeven tijdstip beschikbaar zijn, rekening houdend met een maximale resource beschikbaarheid van 5 eenheden. Activiteiten: { 1, 5, 7, 2, 3, 6, 8, 4, 9}

Figuur 13 - Voorbeeld PSGS 1

35

Activiteit 1 wordt eerst ingepland en verbruikt hierbij 1 resource eenheid. Omdat er nog 4 resource eenheden over zijn kan ook activiteit 2, die 2 resource eenheden gebruikt, worden ingepland. Hetzelfde geldt voor activiteit 3 die met een resource vraag van 2 eenheden er voor zorgt dat er op tijdstip 0 geen resources meer aanwezig zijn. Voor activiteit 4 zijn er geen resources meer beschikbaar, bijgevolg zal deze activiteit moeten wachten tot er terug resources beschikbaar worden. ITERATIE 2

Tijd: { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15…} Bij een nieuwe iteratie in PSGS wordt overgegaan naar het eerstvolgende tijdstip en opnieuw worden alle activiteiten geselecteerd die dan kunnen aanvangen. Op tijdstip 1 is activiteit 2 afgelopen en dus komen er 2 resource eenheden vrij. Opnieuw worden de activiteiten geselecteerd die gegeven de precendence relations op tijdstip 1 kunnen starten en worden deze gerangschikt op basis van de prioriteitslijst.

Activiteiten: { 1, 5, 7, 2, 3, 6, 8, 4, 9}

Merk op dat activiteiten 1 en 3 nog bezig zijn op tijdstip 1 en activiteit 2 volledig is afgewerkt. Dit resulteert in het feit dat alleen activiteit 4 kan worden ingepland. Aangezien voldoende resources aanwezig zijn, kan deze activiteit ook effectief op dat ogenblik worden ingepland.


36

ITERATIE 3 Tijd: { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15…} Met een nieuwe iteratie start ook het volgende tijdstip. Op tijdstip 2 is enkel activiteit 4 nog bezig omdat activiteiten 1 en 3 volledig zijn afgewerkt.

Activiteiten: { 1, 5, 7, 2, 3, 6, 8, 4, 9} Aangezien er op tijdstip 2 nog 3 resource eenheden beschikbaar zijn kan enkel activiteit 5, die 3 resource eenheden vraagt, worden ingepland. Activiteit 6 wordt uitgesteld tot een later tijdstip.


ITERATIE 4 - 8 Wanneer bovenstaande logica wordt doorgetrokken, zullen er nog 5 iteraties plaatsvinden vooraleer alle activiteiten zijn ingepland. Hoewel het project, net als bij SSGS, ook resulteert in een totale tijdsduur van 11 tijdseenheden, kan een duidelijk verschil worden opgemerkt tussen de starten eindtijden van de activiteiten. In dit voorbeeld resulteert dit toevallig in eenzelfde totale tijdsduur maar dit is zeker geen vaste regel.


37

4.2 METAHEURISTIEKE PROCEDURES Het geschetste MOTCP heeft een relatief grote complexiteit terwijl de onzekerheid eerder beperkt is. Dit wil zeggen dat hoewel het relatief eenvoudig is om een gegeven oplossing te evalueren, het veel tijd en moeite vraagt om het probleem volledig te optimaliseren en de beste oplossing te vinden. Om deze reden wordt in deze studie gebruik gemaakt van metaheuristieken om een oplossing te genereren. Metaheuristieken zijn procedures gebaseerd op het systematisch gebruik van trial and error. Het doel is een voldoende goede oplossing naar voren te brengen binnen een aanvaardbaar tijdsinterval. Eén van de belangrijkste eigenschappen van metaheuristieken is de probleemsonafhankelijkheid. Hierdoor hebben ze een zeer groot toepassingsgebied. Ze moeten gezien worden als algemene algoritmische ideeën die een raamwerk schetsen om moeilijke problemen systematisch op te lossen. Typisch hierbij is een terugslag naar een realistische setting zoals artificiële intelligentie, biologische evolutie, mechanische en chemische systemen... (Osman & Kelly, 1996). In het vervolg van dit hoofdstuk zullen twee metaheuristieken worden beschreven die gebruikt zullen worden om het MOTCP te behandelen: Genetic Algorithm en Scatter Search. In wat volgt wordt het achterliggende principe van deze theorie besproken, waarna een conceptueel model wordt opgesteld en tot slot worden de sterktes en zwaktes kort overlopen.

4.2.1 Genetic Algorithm Genetic Algorithm (GA) is een optimalisatietechniek die gebaseerd is op het genetische proces van biologische organismen. Het algoritme werd voor het eerst beschreven door Holland (1975). De basisgedachte achter het algoritme, "survival of the fittest", is gebaseerd op de evolutietheorie van Darwin.

Principe De evolutietheorie van Darwin steunt op drie pijlers die samen bepalen hoe een populatie evolueert doorheen verschillende generaties. Ten eerste is er het principe van de genetische overdracht. Bij de voortplanting van organismen gebeurt er een overdracht van genetisch materiaal van twee individuen wat een vermenging van DNA inhoudt. Ten tweede heeft Darwin onderzocht en bewezen dat individuen die zich het best aanpassen aan hun omgeving, de grootste kans hebben om zich voort te planten en op die manier hun eigenschappen door te geven aan afstammelingen. Dit beschrijft het veelbesproken principe van survival of the fittest. Het derde principe van de Darwiniaanse theorie gaat over mutaties die af en toe optreden in het evolutieproces. Een mutant is een individu met afwijkend genetisch materiaal waarbij het achteraf moeilijk is om de oorzaak van deze afwijking te achterhalen. Deze mutanten overleven meestal niet 38

omdat ze niet voldoen aan Darwin’s criteria van survival of the fittest. Soms blijken deze mutanten echter meer geschikt om te overleven in hun omgeving, omdat de sterftegraad veel lager ligt, en ze zich meer dan de niet-mutanten zullen kunnen voortplanten. Belangrijk om te onthouden uit dit hele verhaal is dat een populatie zich steeds aanpast aan haar omgeving. Om het evolutieproces te begrijpen, is het dan ook cruciaal deze omgeving en haar dynamieken te doorgronden (Darwin, 1860).

Model De evolutietheorie van Darwin vormt de rode draad doorheen het Genetic Algorithm (GA). Een populatie, bestaande uit mogelijke oplossingen voor een probleem, zal zich door middel van combinatieprocedures (genetisch overdracht) trachten aan te passen aan haar omgeving (survival of the fittest en mutatie). Figuur 17 geeft een overzicht van het conceptuele model van GA. Aan de basis van deze metaheuristieke procedure ligt een kringloopproces dat het idee vervat van een steeds evoluerende populatie waarin via iteraties nieuwe generaties worden voortgebracht. Hieronder wordt dieper ingegaan op wat een dergelijke iteratie specifiek inhoudt (Bex, 2001; Busetti, 2007; Chang et al., 2001; Oliveri & Massa, 2011).

Figuur 17 - Conceptueel model van Genetic Algorithm

39

Een iteratie vertrekt van een huidige populatie die bestaat uit een reeks individuen. Elk van deze individuen bevat informatie waarmee een score voor potentiële oplossing voor het probleem kan worden berekend. Deze score is de waarde van de doelfunctie die verkregen wordt als het probleem concreet wordt opgelost of is met andere woorden een indicatie van hoe goed deze oplossing geschikt is voor de omgeving waarin ze zich bevindt. De eerste keer dat de iteratie wordt uitgevoerd, moet deze populatie uiteraard zelf gespecificeerd worden als vertrekpunt van de metaheuristiek. Hiernaar wordt verwezen als de initiële populatie. Het doel van een iteratie is de informatie die de individuen uit de huidige populatie bevatten te gebruiken om een nieuwe, verbeterde populatie te maken. Het analyseren van deze informatie gebeurt tijdens de evaluatie. Voor elk individu i wordt de doelwaarde fi berekend. Hoe hoger de score, hoe groter de kans dat de individuen worden geselecteerd om hun informatie over te dragen aan een nieuwe generatie. Op basis van deze logica worden telkens twee individuen geselecteerd in een selectiestap. Eens een individu is geselecteerd zal zijn informatie doorstromen naar de nieuwe populatie. Dit kan rechtstreeks gebeuren, zonder aanpassingen aan de informatie, of via een procedure die deze informatie zal transformeren in de hoop een individu te creëren met een betere score. Een transformatie bestaat uit een cross-over, eventueel gevolgd door een mutatie. Tijdens de cross-over wordt de informatie van de twee geselecteerde individuen (de ouders) gecombineerd om zo nieuwe individuen te creëren (de kinderen) die kenmerken bezitten van beide ouders. Deze nieuwe individuen kunnen hierna de nieuwe populatie vervoegen. Sommigen zullen eerst een bijkomende transformatie ondergaan, een mutatie. Bij een mutatie zal men een willekeurige bewerking uitvoeren op het individu om zo te vermijden dat de informatie die de huidige populatie bevat, ontoereikend zou zijn om de best mogelijke oplossing te vinden. Er wordt dus voor gezorgd dat de metaheuristiek niet vastloopt in een lokaal optimum. Door achtereenvolgens deze selectie-, cross-over- en/of mutatie-procedure toe te passen op de huidige populatie wordt een nieuwe generatie gevormd die het vertrekpunt vormt van een volgende iteratie. Aangezien de oplossingen met een lagere score minder worden geselecteerd, sterven deze uit terwijl die met een hogere score een hogere kans hebben om te overleven. Doorheen dit evolutieproces wordt de populatiegrootte constant gehouden en wordt de metaheuristiek stopgezet eens een stopcriterium is bereikt. Dit stopcriterium kan inhouden dat een “voldoende kwaliteitsvolle” oplossing gevonden is, dat de voorziene tijd is verstreken of dat een maximum aantal evaluatie-momenten heeft plaatsgevonden.

40

Discussie GA is vandaag de dag één van de meest populaire metaheuristieken. Het bewees zijn nut en sterkte in tal van problemen in en rond het domein van project scheduling, wat de reden was om GA bij deze studie te betrekken. De sterkte ervan wordt mede bepaald door de simpliciteit van het achterliggende verhaal wat zich vertaalt in een reeks van logische procedurestappen die relatief eenvoudig te implementeren zijn. Daarenboven kent GA een groot applicatiedomein omdat het geschikt is voor een hele reeks probleemtypes zonder dat de gebruiker hierbij veel over de onderliggende dynamiek en kenmerken van zijn probleem dient te specificeren. Een veel geuite kritiek op GA is dat het er niet genoeg in slaagt eventuele lokale optima te vermijden door een dominantie van procedures die gericht zijn op lokale verbetering (gebrek aan diversificatie).

4.2.2 Scatter Search Scatter Search (SS) is net als GA een evolutionair algoritme dat gebruikt wordt voor het oplossen van combinatorische en niet-lineaire problemen. Dezelfde structuur als bij de bespreking van GA wordt hier toegepast, waarbij eerst het achterliggende principe van deze theorie wordt besproken, gevolgd door een toelichting van het conceptueel model om te eindigen met een korte discussie.

Principe Het SS-algoritme werkt volgens een gestructureerde zoekstrategie waarbij een set oplossingen wordt geüpdatet met als objectief de oplossing te vinden met de meest gunstige doelwaarde. Het belangrijkste structuurkenmerk in de metaheuristiek is dat een expliciet onderscheid wordt gemaakt tussen oplossingen met een gunstige doelwaarde enerzijds en oplossingen die een verschillend deel van de totale zoekruimte beschrijven anderzijds.

Model De gestructureerde zoekstrategie vormt de rode draad doorheen de SS metaheuristiek. Figuur 18 geeft het conceptueel model weer dat de logica achter SS probeert te vervatten. Het SS algoritme bestaat enerzijds uit een proces dat een initiële set van oplossingen genereert als startpunt van het algoritme en anderzijds een kringloopproces dat het idee vervat dat een iteratie een zoektocht is naar een betere oplossing. Hieronder wordt een overzicht gegeven van de stappen die worden gevolgd in deze

41

metaheuristieke procedure aan de hand van haar pseudocode. In wat volgt wordt elk stap kort besproken (Glover et al., 2003; Van Peteghem & Vanhoucke, 2011). PSEUDOCODE SCATTER SEARCH 1. Diversification generation method 2. Improvement method 3. Reference set construction method While (Stop Criterium is niet voldaan) { 4. Subset generation method 5. Solution combination method 6. Improvement method 7. Reference set update method }

Figuur 18 - Conceptueel model van Scatter Search

42

Het eerste deel van SS bestaat uit de Diversification generation method, de Improvement method en de Reference set update method die, zoals aangegeven in de pseudocode, buiten de eigenlijke iteratie vallen. In de Diversification generation method worden een reeks initiële oplossingen gegenereerd. De reden waarom dit in het SS algoritme als een volwaardige stap wordt beschouwd, is dat dit gebeurt op een intelligente manier. Via een slimme procedure tracht men oplossingen te genereren die samen de volledige zoekruimte beschrijven en op die manier de kans op succes van het algoritme verhogen. Deze stap kan eventueel gevolgd worden door een Improvement method die de initiële oplossingen eerst aanpast door middel van een kwaliteitsverbetering en/of een feasibility controle. Deze kwaliteitsverbetering gebeurt doorgaans door een local search. De laatste stap van dit eerste deel is de Reference set construction method. Hierin wordt de eigenlijke input gegenereerd voor het kringloopproces. In deze stap wordt de structuur aangebracht die SS zo typeert. De oplossingen uit de vorige stap worden namelijk onderverdeeld in een groep van b1 beste oplossingen (B1) en een groep van b2 diverse oplossingen (B2). Diversiteit wordt berekend ten opzichte van b1 en wordt doorgaans bepaald via de euclidische afstand. Het tweede deel van SS bevat de Subset generation method, de Solution combination method, de Improvement method en de Reference set update method. De Subset generation method zal uit de gestructureerde referentieset een aantal subsets genereren door het groeperen van oplossingen uit B1 en B2. Dit groeperen kan op verschillende manieren gebeuren waarbij steeds 2, 3 of meer oplossingen uit B1 en/of B2 worden samengevoegd. Dit is het voorbereidende werk voordat de combinatie van deze subsets plaatsvindt. De eigenlijke transformatie gebeurt in de Solution combination method. De informatie van individuele oplossingen in een subset wordt gebruikt om een nieuwe oplossing te genereren die informatie bevat van alle leden van de subset. Hierna wordt een Improvement method voorzien die opnieuw een kwaliteitsverbetering en/of een feasibilitycontrole uitvoert op de nieuwe oplossingen. De oplossingen die op dergelijke wijze zijn gegenereerd, vormen de potentiële kandidaten om opgenomen te worden in de referentieset. In de Reference set update method wordt elke oplossing geëvalueerd op basis van zowel kwaliteit als diversiteit. Oplossingen met een betere kwaliteit dan één van de b1 beste oplossingen zullen de plaats innemen van de slechtste oplossing in B1. Oplossingen met een hogere diversiteit dan één van de b2 oplossingen zullen de plaats innemen van de minst diverse oplossing in B2. Door deze iteratie steeds te herhalen, wordt de referentieset steeds geüpdatet totdat de metaheuristiek wordt stopgezet omdat een stopcriterium is bereikt.

43

Discussie SS is één van de meest veelbelovende metaheuristieken. Deze relatief jonge metaheuristiek bewees al zijn potentieel als effectieve zoekstrategie voor combinatorische, niet-lineaire problemen. Bovendien staat SS in de belangstelling bij de vakgroep Beleidsinformatica en Operationeel Beheer van de Universiteit Gent die deze masterproef begeleidt. Het systematische en gestructureerde karakter van SS zorgt voor het behoud van diversiteit doorheen de zoekprocedure. Dit resulteert in een grotere kans op succes bij het zoeken naar het globale optimum. De mogelijkheid om zelf een invulling te geven aan de deterministische methodes die de metaheuristiek bevat, geeft de gebruiker bovendien de flexibiliteit om de zoekprocedure heel probleemspecifiek aan te pakken. Dit is echter tegelijkertijd ook een nadeel omdat SS minder zelfstandig is in die zin dat probleemspecificaties de implementatiecomplexiteit verhogen. Hierbij komt nog dat SS geen aantrekkelijk onderliggend verhaal bevat, wat interpretatie en logica zeker niet ten goede komt.

4.2.3 Vergelijking van Genetic Algorithm en Scatter Search Om metaheuristieken te vergelijken, kunnen enkele dimensies die terugkomen in elke metaheuristiek naar voren worden geschoven. Tabel 3 geeft een overzicht van deze dimensies samen met de invulling ervan bij respectievelijk GA en SS (Taha, 2007). Een eerste criterium is de combinatiebasis. Dit is het aantal oplossingen dat effectief betrokken is bij het genereren van een nieuwe oplossing door informatie-uitwisseling. Bij GA worden slechts twee oplossingen gecombineerd in de cross-over stap terwijl bij SS de mogelijkheid bestaat om subsets te vormen met 2, 3 of meer oplossingen. Een tweede criterium is de beslissingsbasis. Dit is de manier waarop beslist wordt welke methodes worden toegepast op welke oplossingen. Bij GA is dit veelal op basis van randomisatie waarbij probabiliteit een rol speelt in zowel de selectie-, de cross-over- als de mutatiestap. De SS metaheuristiek is eerder opgebouwd uit systematische procedures waarbij meer controle gegeven wordt aan de implementator. Een derde criterium is de populatiegrootte. Typisch is deze bij GA groter dan bij SS. Een vierde en laatste criterium is de manier waarop de populatie evolueert. Bij GA gebeurt dit op basis van het principe van survival of the fittest waarbij kwaliteitsvollere oplossingen een grotere kans hebben te overleven. Bij SS gebeurt dit op een eerder deterministische manier waarbij telkens wordt geëvalueerd of de oplossingen voldoen aan de criteria om opgenomen te worden in de referentieset.

44

Tabel 3 - Invulling van de dimensies bij metaheuristieken voor GA en SS (Taha, 2007)

GENETIC ALGORITHM

SCATTER SEARCH

Combinatiebasis

2 ouderoplossingen

2, 3 of meer oplossingen

Beslissingsbasis

Randomisatie

Systematische procedures

Populatiegrootte

Grote populatie (≥50)

Kleine referentieset (≤20)

Populatie evolutie

Survival of the fittest

Deterministische regels i.v.m. kwaliteit en diversiteit

Deze karakteristieken hebben een eerder beschrijvend karakter. Om de implementatie en implicaties voor de gebruiker te schetsen, worden de voor -en nadelen van zowel GA als SS op een rijtje gezet in tabellen 4 en 5. Een aantal ervan werden reeds aangehaald bij de discussie over de metaheuristiek zelf. Tabel 4 - Voor- en nadelen van Genetic Algorithm

GENETIC ALGORITHM Voordelen

Nadelen



Aantrekkelijk verhaal dat de gebruiker van de zoekprocedure begeleidt



Relatief makkelijk te programmeren



Robuust: goede prestaties zonder veel specificaties van de gebruiker



Weinig controle over de procedures



Relatief hoge CPU-tijd belasting



Risico op premature convergentie door de dominantie van intensificatie

Tabel 5 - Voor- en nadelen van Scatter Search

SCATTER SEARCH Voordelen 

Behoud van diversificatie



Effectief als optimalisatieprocedure binnen een andere metaheuristiek



Hoge mate van controle door het gebruik van systematische procedures en deterministische regels

Nadelen 

Nood aan specificaties voor het te behandelen probleem



Relatief moeilijk te programmeren



Geen aantrekkelijk verhaal dat de gebruiker van de zoekprocedure begeleidt

45

4.3 PROBLEEMSPECIFIEKE OPLOSSINGSVOORSTELLING Een metaheuristiek kan enkel slagen in haar opzet als een oplossing zo is voorgesteld dat: 

de doelwaarde eenduidig, transparant en efficiënt kan worden nagegaan



het mogelijk is bewerkingen uit te voeren op discrete onderdelen

Om deze twee redenen werd geopteerd om de oplossingen voor te stellen door prioriteitslijsten. Enkele voordelen van deze voorstellingsmethode worden besproken in Hartmann (1998). De reden waarom prioriteitslijsten in deze setting een goede voorstellingswijze zijn, is dat ze de nodige informatie bevatten om een project te plannen. Daarenboven bestaan ze uit een geordende reeks van getallen (i.e. prioriteiten) waardoor ze geschikt zijn voor allerlei transformatieprocedures die in se allemaal gebaseerd zijn op het van plaats verwisselen van getallen. In het MOTCP staan twee keuzes centraal. Enerzijds moet worden beslist wanneer elke activiteit zal starten. Anderzijds moet worden beslist welke werknemers de activiteiten zullen uitvoeren. Omdat deze twee beslissingen aan de basis liggen van het schedulen, dienen ze allebei te worden opgenomen in de voorstelling van een mogelijke oplossing voor het probleem. Concreet worden hiervoor twee prioriteitslijsten aan elkaar gekoppeld. De eerste prioriteitslijst bevat de prioriteiten tussen de verschillende activiteiten terwijl de tweede prioriteitslijst de prioriteiten bevat tussen de verschillende werknemers. Onderstaande figuur geeft een voorbeeld van een mogelijke oplossing van een probleem met 7 activiteiten, weergegeven in de eerste rij, en 9 werknemers, weergegeven in de tweede rij.

Figuur 19 - Voorbeeld oplossingsvoorstelling

Merk op dat een prioriteitslijst in deze setting steeds bestaat uit een reeks natuurlijke getallen tussen 0 en 100 waarbij een groter getal wijst op een grotere prioriteit. Te allen tijde wordt hierbij gewaarborgd dat minstens één van de prioriteiten op 100 staat. Indien na een zekere transformatieprocedure geen enkele prioriteit meer voorkomt met een waarde 100, worden alle prioriteiten van deze prioriteitslijst herschaald, waarbij de grootste prioriteit een waarde 100 wordt toegewezen en de andere prioriteiten relatief tegenover deze prioriteit worden uitgedrukt.

46

4.4 SAMENVATTING HOOFDSTUK 4 Metaheuristieken zijn alternatieve strategieën voor het oplossen van complexe problemen zoals het MOTCP. Het zijn probleemonafhankelijke raamwerken die kunnen worden aangewend om een voldoende goede oplossing te vinden binnen een aanvaardbaar tijdsinterval. De ingrediënten van een metaheuristiek in project scheduling zijn de prioriteitsregels die de oplossing voorstellen, de metaheuristieke procedure die mogelijke oplossingen genereert, het schedule generation scheme dat een project inplant en de evaluatie waar de oplossing wordt geanalyseerd.

Figuur 20 - Generiek model van metaheuristieken

Dit hoofdstuk ging in op twee verschillende schedule generation schemes namelijk SSGS en PSGS. Daarnaast werden ook twee metaheuristieke procedures besproken namelijk GA en SS. Tabel 6 vat de vier verschillende metaheuristieken samen die op deze manier kunnen worden opgesteld. Tabel 6 - Overzicht van de verschillende metaheuristieken

SCHEDULE GENERATION SCHEME SSGS

PSGS

METAHEURISTIEKE

GA

METAHEURISTIEK 1

METAHEURISTIEK 2

PROCEDURE

SS

METAHEURISTIEK 3

METAHEURISTIEK 4

47

DEEL 3 - ONDERZOEKSOPZET

48

INLEIDING In deel 1 werd het Multi-Objective Team Composition Problem (MOTCP) opgebouwd en besproken met als doel inzicht te geven in het complexe karakter van dit probleem. De diffusie van resource beschikbaarheid over werknemers enerzijds en de trade-off tussen drie objectieven anderzijds werden geïdentificeerd als de drivers van de extra complexiteit van het MOTCP tegenover het RCPSP. In deel 2 werd op basis van deze informatie ingegaan op het kwantificeren van complexiteit in project scheduling aan de hand van projectindicatoren. Daarnaast werd de rol van metaheuristieken besproken bij het oplossen van dergelijke complexe problemen. Concreet werden hierbij vier metaheuristieken naar voren geschoven die kunnen worden gevormd door het combineren van de metaheuristieke procedures Genetic Algorithm (GA) en Scatter Search (SS) met de planningsmethodieken Serial Schedule Generation Scheme (SSGS) en Parallel Schedule Generation Scheme (PSGS). In deel 3 wordt de performantie van metaheuristieken onderzocht bij het oplossen van het beschouwde MOTCP in combinatie met de verschillende projecttypes. Hierbij wordt zowel aandacht geschonken aan metaheuristieken in het algemeen als aan de vier verschillende metaheuristieken die in deze studie worden naar voren geschoven. Concreet wordt hiervoor een simulatie uitgevoerd op basis van een reeks voorbeeldprojecten die één voor één door de metaheuristieken worden gescheduled. Door de gestructureerde en systematische opbouw van deze voorbeeldprojecten aan de hand van projecttypes kan op die manier het volledige complexiteitsspectrum van het MOTCP behandeld worden. In hoofdstuk 5 worden eerst en vooral de scope en de methodologie van de simulatie uit de doeken gedaan. Daarna worden in hoofdstuk 6 de resultaten besproken van het onderzoek aan de hand van vier onderzoeksvragen. Als laatste wordt in hoofdstuk 7 de terugkoppeling gemaakt naar de praktijk door de onderzoeksresultaten terug te koppelen naar de implicaties voor de projectmanager.

49

HOOFDSTUK 5: METHODOLOGIE 5.1 INLEIDING In dit hoofdstuk wordt de methodologie van het onderzoek opgebouwd en toegelicht. Hierbij worden de grote lijnen aangehaald in het hoofdstuk zelf, terwijl een meer gedetailleerd overzicht werd bijgevoegd in bijlagen 3 en 4. Er wordt gewerkt aan de hand van een simulatie die uiteenvalt in twee fases. Eerst wordt een verkennende simulatie uitgevoerd met als doel het maken van enkele implementatiekeuzes. Daarna volgt de uiteindelijke simulatie waar de nodige informatie wordt verzameld om een antwoord te kunnen geven op de vier onderzoeksvragen die in het volgende hoofdstuk centraal staan.

5.2 PRE-SIMULATIE Een simulatieoefening vindt steeds plaats binnen een kader van assumpties. Het interpreteren van simulatieresultaten moet dan ook gebeuren in functie van deze assumpties. Naast de veronderstellingen die worden gemaakt omtrent de beschouwde setting van het MOTCP (bijlage 1), vertalen assumpties zich ook in de implementatiekeuzes van de procedures waarrond de simulatie is opgebouwd. In het geval van deze studie zijn de procedures de metaheuristieken en hun onderdelen. In het volgende hoofdstuk wordt in onderzoeksvraag 1 dieper ingegaan op enkele van deze implementatiekeuzes voor zowel GA als SS. De implementatiekeuzes die daarin echter niet worden beschouwd, maken ook deel uit van het omliggende kader van assumpties en mogen zeker niet worden verwaarloosd. Denk maar aan iemand die beslist zich te verplaatsen van plaats A naar plaats B en hierbij de implementatiekeuze maakt de auto te nemen als transportmiddel. Hoewel het verkiezen van de auto boven andere transportmiddelen de centrale implementatiekeuze is, wordt deze keuze gemaakt gegeven de assumpties van bandenkeuze, topsnelheid, gewicht… Het is duidelijk dat ook deze specificaties een rol spelen. Om deze assumpties zeker niet als vanzelfsprekend te beschouwen, wordt eerst een verkennende simulatie uitgevoerd waarnaar in het vervolg wordt verwezen als de pre-simulatie. Voor de procedures in de metaheuristieken die gestuurd worden door parameters, wordt van deze pre-simulatie gebruik gemaakt om deze parameters zo te kiezen dat de efficiëntie en effectiviteit van de procedure wordt gewaarborgd. Concreet wordt een set voorbeeldprojecten gegenereerd die de grote lijnen van het complexiteitspectrum van het beschouwde MOTCP beschrijven. Elk van hen wordt meerdere malen door de metaheuristieken geleid, telkens voor andere parameterwaarden van de te optimaliseren procedures. Een volledig overzicht

50

van de opbouw en bespreking van deze pre-simulatie kan worden gevonden in bijlage 3. Het is aan te raden sectie 3.2 en 3.3 uit deze bijlage te beschouwen in combinatie met onderzoeksvraag 1 in hoofdstuk 6.

5.3 SIMULATIE In de centrale simulatie van deze studie wordt de nodige informatie verzameld om inzicht te krijgen in de performantie van en tussen metaheuristieken voor het oplossen van het beschouwde MOTCP. Aangezien een simulatie een nabootsing van de realiteit voorstelt, is hiervoor een dataset van voorbeeldprojecten vereist. Elk voorbeeldproject bevat informatie over bepaalde restricties en omstandigheden, zoals bijvoorbeeld de volgorderelaties tussen activiteiten, de vraag naar resources van elke activiteit en het aanbod van resources door elke werknemer. Het plannen van een voorbeeldproject kan enkel als succesvol worden beschouwd als aan deze restricties wordt voldaan. Om alle dimensies van complexiteit in rekening te brengen, worden deze voorbeeldprojecten gestructureerd opgebouwd aan de hand van de netwerkgenerator RanGen2 samen met een eenvoudige resourcegenerator in Visual Studio Express 2012 (C++).

De netwerkgenerator RanGen2 biedt de mogelijkheid projecten te genereren op basis van de traditionele projectindicatoren besproken in 3.1. De aandacht gaat hier vooral uit naar de topologische projectindicatoren. De invloed van de resource gerelateerde projectindicatoren wordt buiten de scope van deze simulatie gelaten. De kracht van RanGen2 als netwerkgenerator werd besproken door Vanhoucke et al. (2008) terwijl een introductie tot het gebruik van deze tool werd aangehaald door Demeulemeester et al. (2003). Om de invloed van elke beschouwde projectindicator te kunnen analyseren, wordt het bestaansinterval van elke indicator opgedeeld in deelintervallen. Achtereenvolgens worden projecten gegenereerd waarbij de waarde van een beschouwde projectindicator wordt gelimiteerd tot een bepaald interval terwijl de andere projectindicatoren vrij kunnen variëren zodat hun invloed wordt uitgemiddeld. Tabel 7 geeft een overzicht van de projectindicatoren wiens invloed op deze manier wordt onderzocht, samen met de keuze voor projectindicatoren die buiten de scope van deze studie vallen.

51

Tabel 7 - Overzicht intervallen van traditionele projectindicatoren

Indicator I1

Min 1

Max +∞

Waarde 1 20

Waarde 2 n.v.t.

Waarde 3 n.v.t.

Waarde 4 n.v.t.

Waarde 5 n.v.t.

Waarde 6 n.v.t.

I2 0 1 0.1 0.25 0.5 0.75 0.9 n.v.t. I3 0 1 0 – 0.1 0.1 – 0.25 0.25 – 0.5 0.5 – 0.75 0.75 – 0.9 0.9 – 1 I4 0 1 0 – 0.1 0.1 – 0.25 0.25 – 0.5 0.5 – 0.75 0.75 – 0.9 0.9 – 1 I5 0 1 0 – 0.1 0.1 – 0.25 0.25 – 0.5 0.5 – 0.75 0.75 – 0.9 0.9 – 1 I6 0 1 0 – 0.1 0.1 – 0.25 0.25 – 0.5 0.5 – 0.75 0.75 – 0.9 0.9 – 1 * K 1 +∞ 4 n.v.t. n.v.t. n.v.t. n.v.t. n.v.t. * RU 1 K 3 n.v.t. n.v.t. n.v.t. n.v.t. n.v.t. * RC 0 1 0.4 n.v.t. n.v.t. n.v.t. n.v.t. n.v.t. * Deze indicatoren werden gekozen in lijn met een gelijkaardig onderzoek door Vanhoucke et al. (2008)

De resourcegenerator die werd geprogrammeerd in Visual Studio Express 2012, werd in het leven geroepen om de invloed van enkele additionele projectindicatoren te kunnen onderzoeken. Deze zijn probleemspecifiek en relevant voor het beschouwde MOTCP. Het gaat hier meer bepaald over de projectindicatoren in verband met het competentieniveau van werknemers en de sociale cohesie tussen werknemers zoals besproken in 3.2. Analoog aan de RanGen2-indicatoren worden ook hier de projectindicatoren opgedeeld in deelintervallen. Een overzicht wordt gegeven in tabel 8. Tabel 8 - Overzicht intervallen van probleemspecifieke projectindicatoren

Indicator 𝜇s 𝜇c CVs CVc

Min 0 0 0 0

Max 100 100 +∞ +∞

Waarde 1 10 1.33 0.50 0.50

Waarde 2 25 1.66 0.75 0.75

Waarde 3 50 2.00 1.00 1.00

Waarde 4 75 2.33 1.33 1.33

Waarde 5 90 2.66 1.58 1.58

Voor deze simulatie worden voorbeeldprojecten gegenereerd die op negen dimensies, weergegeven door de negen projectindicatoren, kunnen worden gespecificeerd. Voor een overzicht van de opbouw van deze dataset aan voorbeeldprojecten wordt verwezen naar bijlage 4. Concreet worden voor elke waarde die of elk interval dat wordt beschouwd voor een projectindicator, 30 projecten gegenereerd die elk door vier metaheuristieken worden opgelost: 1. Genetic Algorithm + Serial Schedule Generation Scheme 2. Genetic Algorithm + Parallel Schedule Generation Scheme 3. Scatter Search + Serial Schedule Generation Scheme 4. Scatter Search + Parallel Schedule Generation Scheme

52

Om de performantie van een metaheuristiek te kwantificeren, worden telkens de waarden voor de drie deelobjectieven tijd, kosten en sociale cohesie opgeslagen voor de beste oplossing die gevonden werd na respectievelijk 0, 1000, 2000, 3000 en 4000 gegenereerde schedules.

53

5.4 SAMENVATTING HOOFDSTUK 5 Om de performantie van metaheuristieken te onderzoeken voor het oplossen van het beschouwde MOTCP wordt in deze studie beroep gedaan op een simulatie. De input van deze simulatie wordt gevormd door een dataset van projecten die gestructureerd gegenereerd worden op basis van projectindicatoren. De verwerking van deze informatie gebeurt door vier verschillende metaheuristieken die elk als doel hebben deze projecten zo optimaal mogelijk te schedulen. Om de performantie van de metaheuristiek te kwantificeren worden telkens de waarden voor de drie deelobjectieven tijd, kosten en sociale cohesie opgeslagen voor de beste oplossing die gevonden werd na respectievelijk 1000, 2000, 3000 en 4000 gegenereerde schedules. De opbouw van de dataset van projecten staat beschreven in bijlage 4.

Figuur 21 - Scope van de simulatie

Simulatieresultaten dienen steeds te worden geïnterpreteerd in het kader van de assumpties waarop ze zijn gebouwd. Waar in bijlage 1 reeds een overzicht werd gegeven van de belangrijkste veronderstellingen omtrent het MOTCP zelf, bestaan er eveneens assumpties omtrent de implementatie van de metaheuristieken. Hierin worden namelijk parameters gekozen die bepalen hoe procedures in de metaheuristiek verlopen. Omdat dit niet als vanzelfsprekend mag worden beschouwd, werd voor dit onderzoek geopteerd voor een pre-simulatie. Dit is een verkennende simulatie waarbij de efficiëntie en effectiviteit van procedures in de metaheuristieken wordt geanalyseerd voor een reeks parameters die voor het vervolg van de simulatie als gegeven zullen worden beschouwd. Een overzicht van deze pre-simulatie werd ondergebracht in bijlage 3. 54

HOOFDSTUK 6: ONDERZOEK Het zesde hoofdstuk heeft als doel een overzicht te geven van de simulatieresultaten. Om deze resultaten gestructureerd te kunnen toelichten, worden de uitgevoerde analyses onderverdeeld in vier grote onderzoeksvragen. In 6.1 wordt het onderzoek ingeleid door de beschouwde onderzoeksvragen kort te positioneren. Vervolgens worden de onderzoeksvragen in 6.2 overlopen. Voor elk van hen worden zowel de methodologie als de resultaten besproken.

6.1 OVERZICHT VAN DE ONDERZOEKSVRAGEN Een simulatie is maar zo sterk als de opportuniteit om haar output te interpreteren. In het licht van dit gegeven werd besloten om de simulatie op te delen in onderzoeksvragen die elk vanuit een eigen invalshoek de resultaten benaderen. Deze invalshoeken vallen terug op de vier grote thema’s die tot nu toe aan bod zijn gekomen: 1. Metaheuristieke procedures: GA en SS 2. Planningsmethodes: SSGS en PSGS 3. Projecttypes: I2, I3, I4, I5, I6, µc, CVc, µs en CVs 4. Deelobjectieven: tijd, kosten en sociale cohesie In wat volgt worden vier onderzoeksvragen aangebracht die elk overeenkomen met één van bovenstaande thema’s. Elke onderzoeksvraag is gebaseerd op één of meerdere simulaties en zal de simulatieresultaten op een eigen manier structureren en analyseren. ONDERZOEKSVRAAG 1: Wat is het verschil in impact tussen GA en SS op de totale doelfunctiewaarde? Voor deze onderzoeksvraag wordt onderzocht of er in het MOTCP een performantieverschil is tussen GA en SS. Verder worden verworven inzichten omtrent intensificatie en diversificatie in metaheuristieken gebruikt om de performantie van GA en SS te vergroten. ONDERZOEKSVRAAG 2: Wat is het verschil in impact tussen PSGS en SSGS op de totale doelfunctiewaarde? doelfunctiewaarde? Voor deze onderzoeksvraag wordt onderzocht of er een performantieverschil is tussen de planningsmethodes PSGS en SSGS. Dit verschil wordt onderzocht voor de verschillende projecttypes in het MOTCP. Het doel is om een aanvulling te bieden op onderzoeksvraag 1 over welke metaheuristiek het best presteert en deze resultaten verder te specificeren voor verschillende projecttypes. 55

ONDERZOEKSVRAAG 3: Wat is de impact van elke projectindicator op de totale doelfunctiewaarde? doelfunctiewaarde? Voor deze onderzoeksvraag wordt via een sensitiviteitsanalyse onderzocht wat de impact is van de verschillende projectindicatoren bij het gebruik van metaheuristieken. Het doel is te achterhalen welke projectindicatoren de grootste invloed hebben op de performantie van metaheuristieken. ONDERZOEKSVRAAG 4: Wat is de impact van de projectindicator I2 op de deelobjectieven? doelfunctiewaarde? Voor deze onderzoeksvraag wordt de impact van de projectindicator I2 onderzocht op de drie deelobjectieven tijd, kosten en sociale cohesie. Het doel is te achterhalen wat de invloed is van I2 op het potentieel van elk van deze deelobjectieven.

6.2 RAPPORTERING VAN DE RESULTATEN 6.2.1 Onderzoeksvraag 1 Wat is het verschil in impact tussen GA en SS op de totale doelfunctiewaarde? Het doel van deze onderzoeksvraag is enerzijds te onderzoeken of er een algemeen performantieverschil bestaat tussen GA en SS. Anderzijds wordt getracht om inzichten te verwerven omtrent de rol van intensificatie en diversificatie in metaheuristieken voor het behandelen van het MOTCP. Om dit op een gestructureerde manier aan te pakken, wordt onderzoeksvraag 1 opgesplitst in vier kleinere onderzoeksvragen: Onderzoeksvraag 1.1: Wat is het verschil tussen GA en SS bij een implementatie zonder probleemspecifieke intelligentie? Onderzoeksvraag 1.2: Hoe kan probleemspecifieke intelligentie de performantie van GA verbeteren? Onderzoeksvraag 1.3: Hoe kan probleemspecifieke intelligentie de performantie van SS verbeteren? Onderzoeksvraag 1.4: Wat is het verschil tussen GA en SS bij een implementatie met probleemspecifieke intelligentie? Omdat doorheen deze onderzoeksvragen verschillende implementaties van GA en SS worden behandeld, worden in tabel 9 de implementatieonderdelen aangehaald die in dit onderzoek worden onderzocht. Het toevoegen van probleemspecifieke intelligentie in onderzoeksvragen 1.2 en 1.3 zal plaatsvinden in deze domeinen. 56

Tabel 9 - Implementatieonderdelen van GA en SS

Genetic Algorithm INITIELE POPULATIE VORMING SELECTIE DIRECT ELITISME CROSS-OVER MUTATIE

Scatter Search DIVERSIFICATION GENERATION METHOD REFERENCE SET CONSTRUCTION METHOD SUBSET GENERATION METHOD SOLUTION COMBINATION METHOD IMPROVEMENT METHOD REFERENCE SET UPDATE METHOD

6.2.1.1 Onderzoeksvraag 1.1 Wat is het verschil tussen GA en SS bij een implementatie zonder probleemspecifieke intelligentie? In dit eerste luik van onderzoeksvraag 1 wordt een eerste implementatie voor GA en SS opgebouwd. Deze implementatie is een algemene invulling van de theoretische principes achter beide metaheuristieken. Op die manier wordt getracht een beeld te vormen van de effectiviteit van beide metaheuristieken als pure zoekstrategieën waarin weinig probleemspecifieke intelligentie is geïncorporeerd. Eerst wordt de implementatie besproken, vervolgens de simulatie en tot slot de resultaten. Implementatie In wat volgt worden de algemene implementatievormen van GA en SS toegelicht. In de rest van dit werk wordt naar deze implementaties verwezen als GA1 en SS1. Tabellen 10 en 11 vatten kort samen hoe de implementatieonderdelen van GA1 en SS1 specifiek worden ingevuld. Vervolgens worden deze implementatieonderdelen stap voor stap overlopen en uitgelegd. Tabel 10 - Overzicht van de implementatieonderdelen van GA1

IMPLEMENTATIEONDERDEEL INITIELE POPULATIE VORMING DIRECT ELITISME SELECTIE CROSS-OVER MUTATIE

GA1 Willekeurige prioriteiten n.v.t. Rank selection Two-point cross-over Random swap mutation

Tabel 11 - Overzicht van de implementatieonderdelen van SS1

IMPLEMENTATIEONDERDEEL DIVERSIFICATION GENERATION METHOD REFERENCE SET CONSTRUCTION METHOD SUBSET GENERATION METHOD SOLUTION COMBINATION METHOD IMPROVEMENT METHOD REFERENCE SET UPDATE METHOD

SS1 Intelligente prioriteiten B1 = 12 en B2 = 8 (B1 x B1) en (B1 x B2) + Willekeurige selectie B1 Two-point cross-over Local search B1 = f(doelwaarden) en B2 = f(euclidische afstand t.o.v. B1)

57

Genetic Algorithm 1 (GA1)

Figuur 22 visualiseert GA1 aan de hand van het conceptueel model waarin de implementatieonderdelen duidelijk kunnen worden onderscheiden. Voor sommige onderdelen moeten één of meerdere parameters vastgelegd worden. Deze bepalen in grote mate de werking van dit onderdeel en/of het algoritme. In figuur 22 worden deze parameters aangeduid als Parx. De waarden voor deze parameters worden bepaald aan de hand van de pre-simulatie die beschreven werd in sectie 5.2 en bijlage 3.2. De resultaten van deze pre-simulaties worden toegelicht bij het desbetreffende implementatieonderdeel. MUTATIE

POPULATIE

x 20

x Par2

CROSSOVER

x Par1

EVALUATIE

v v

Indirect elitisme x (1 - Par1 )

= f1

= f5

= f7

= f2

= f6

…

= f3 = f4

v v

= f6 = f7

v v

= fn-1 = fn

SELECTIE x2

Figuur 22 - Conceptueel model GA1

Initiële populatie vorming

Bij GA1 wordt vertrokken van een willekeurige populatie. In 4.3 werd toegelicht dat een populatielid bestaat uit twee prioriteitslijsten, één in verband met activiteiten en één in verband met werknemers. Bij een willekeurige populatie zullen de toegekende prioriteiten aan een activiteit of werknemer een willekeurig getal zijn tussen 0 en 100. Er werd beslist te starten met een initiële populatiegrootte van 50 leden. Na een eerste generatie-iteratie wordt deze grootte gereduceerd tot 20 leden waarna ze constant blijft voor de daaropvolgende generaties. Direct elitisme

Aan het begin van een iteratie kan gekozen worden om de beste leden van de huidige populatie direct door te sturen naar de nieuwe populatie. Bij GA1 wordt direct elitisme echter niet geïmplementeerd, omdat dit door de auteurs niet beschouwd wordt als standaard onderdeel van GA.

58

Selectie

In de eerste stap van de iteratie worden leden uit de huidige populatie geselecteerd. Hun kenmerken zullen in een tweede stap gebruikt worden om een nieuwe populatie op te bouwen. Deze selectie gebeurt op basis van het principe van survival of the fittest, waarbij individuen met een grotere doelwaarde een grotere kans maken om geselecteerd te worden. De selectie gebeurt in GA1 aan de hand van rank selection. Bij rank selection worden alle leden van de initiële populatie van maximale naar minimale fitness value geordend. Merk op dat in de beschouwde MOTCP-setting wordt gewerkt met minimalisatie en de oplossing met de kleinste fitness value bijgevolg de beste is. Na het ordenen van de leden bepaalt de positie van elk lid het aantal keer dat de oplossing in een "selectietrommel" wordt toegevoegd. De eerste (slechtste) oplossing wordt één maal toegevoegd, de tweede oplossing twee maal, enzovoort (Goldberg en Deb, 1991). Onderstaand voorbeeld verduidelijkt de selectiemethode. Tabel 12 schetst de situatie van een minimalisatieprobleem waarbij de populatie bestaat uit vier oplossingen die geïdentificeerd worden door een oplossing-ID. Voor elk van deze oplossingen kan een fitness value worden berekend en aan elk van hen wordt vervolgens een rangnummer toegewezen. Tabel 12 - Voorbeeld rank selection (gegevens)

Oplossing-ID I II III IV

Fitness value 15 12 13 17

Rang (1 = max) 2 4 3 1

Op basis van deze rangorde wordt de selectietrommel samengesteld (tabel 13). Hierbij zal een oplossing met een groter rangnummer meer voorkomen dan een oplossing met een kleiner rangnummer. Bij de selectie worden vervolgens willekeurig twee oplossingen uit deze selectietrommel gekozen. Hierbij hebben betere oplossingen een grotere kans om geselecteerd te worden aangezien deze meer voorkomen. Dit bouwt verder op het principe van intensificatie. De oplossingen met een minder hoge doelfunctiewaarde worden echter niet volledig buiten beschouwing gelaten en maken door de willekeurige keuze nog steeds kans om geselecteerd te worden. Dit behoudt de diversificatie doorheen het algoritme. Tabel 13 - Voorbeeld rank selection (selectietrommel)

Plaats Oplossing-ID Fitness value

1 IV 17

2 I 15

3 I 15

4 III 13

5 III 13

6 III 13

7 II 12

8 II 12

9 II 12

10 II 12

59

Cross-over

Een cross-over is een combinatiemethode die prioriteitslijsten van twee ouders samenvoegt. Dit stelt een paring tussen twee ouders voor uit de Darwiniaanse theorie. In de setting van deze studie wordt de activiteitsgerelateerde prioriteitslijst van de ene ouder gecombineerd met de activiteitsgerelateerde prioriteitslijst van de andere ouder. Hetzelfde gebeurt voor de werknemersgerelateerde lijsten. Voor GA1 wordt gebruik gemaakt van een two-point cross-over. Bij een two-point cross-over worden twee lijsten gecombineerd door een aantal prioriteiten van de ene lijst te verwisselen met een aantal prioriteiten uit de andere lijst (Spears & De Jong, 1990). Hieronder wordt de two-point cross-over techniek geïllustreerd aan de hand van een eenvoudig voorbeeld. Dit voorbeeld beschouwt twee prioriteitslijsten bestaande uit zeven prioriteiten, waarbij elke prioriteit een getal is uit het gesloten interval [0,100]. Het doel van deze transformatie is om een sectie van prioriteiten uit de ene lijst te wisselen met dezelfde sectie uit de andere lijst. De sectie wordt bepaald door twee willekeurige getallen, één om de start en één om het einde van de sectie aan te duiden. In onderstaand voorbeeld zijn deze getallen respectievelijk 2 en 5. Prioriteitslijsten voor cross-over (ouders):

Figuur 23 - Voorbeeld two-point cross-over (prioriteitslijsten voor cross-over)

Transformatie:

Figuur 24 - Voorbeeld two-point cross-over (transformatie)

Prioriteitslijsten na cross-over (kinderen):

Figuur 25 - Voorbeeld two-point cross-over (prioriteitslijsten na cross-over)

60

De twee getransformeerde prioriteitslijsten worden kinderen genoemd omdat ze informatie overnemen van beide initiële lijsten, zijnde de ouders. Hierna worden de kinderen eerst herschaald zodat de grootste prioriteit 100 is. De andere prioriteiten worden relatief uitgedrukt tegenover deze grootste prioriteit. In bovenstaand voorbeeld is deze herschaling echter niet van toepassing.

PRE-SIMULATIE: Par1 (Cross-over rate) De beslissing of er al dan niet een cross-over plaatsvindt op een geselecteerd lid, wordt gestuurd door de cross-over rate (in figuur 22 aangeduid met Par1). Deze parameter beschrijft de probabiliteit dat een oplossing een cross-over ondergaat. Als geen cross-over wordt uitgevoerd en de geselecteerde oplossing direct wordt doorgestuurd naar de volgende generatie is er sprake van indirect elitisme. Dit wordt in figuur 22 aangeduid door 1 - Par1. Om een geschikte waarde voor de cross-over rate te bepalen, wordt gebruik gemaakt van een pre-simulatie (zie sectie 5.2 en bijlage 3.2). Hierbij wordt aan de hand van een beperkte set projecten een eerste analyse uitgevoerd om te bepalen welke cross-over rate optimaal is voor de geschetste probleemsetting. Uit grafiek 1, die de resultaten van deze pre-simulatie samenvat, blijkt duidelijk dat een cross-over rate van 90% resulteert in een minimale fitness value. Deze waarde werd dan ook in het algoritme geïmplementeerd.

Pre-simulatie Par1 Gemiddelde doelfunctiewaarde

9,5 9,4 9,3 9,2 9,1 9 50% 55% 60% 65% 70% 75% 80% 85% 90% 95% Parameterwaarde Grafiek 1 - Resultaten pre-simulatie Par1

61

De two-point cross-over zorgt enerzijds voor intensificatie omdat de selectiemethode de betere oplossingen combineert. Anderzijds zorgt het ook voor diversificatie omdat niet geweten is welk deel van de informatie waardevol is en door de willekeurige combinatie een volledig nieuwe oplossing kan worden gecreëerd. Mutatie

Na de cross-over wordt voor elk van de getransformeerde leden beslist of deze nog een mutatie ondergaan vooraleer ze de volgende populatie vervoegen. Voor deze eerste implementatie van het genetische algoritme werd gekozen voor een random swap mutation. Bij random swap mutation worden op een willekeurige manier twee prioriteiten in een prioriteitslijst verwisseld. Onderstaand voorbeeld toont hoe dit in zijn werk gaat. Prioriteitslijst voor mutatie:

Figuur 26 - Voorbeeld random swap mutation (prioriteitslijst voor mutatie)

Transformatie (bijvoorbeeld 2  6)

Figuur 27 - Voorbeeld random swap mutation (transformatie)

Prioriteitslijst na mutatie:

Figuur 28 - Voorbeeld random swap mutation (prioriteitslijst na mutatie)

62

PRE-SIMULATIE: Par2 (Mutation rate) De beslissing om al dan niet een mutatie uit te voeren, wordt gestuurd door de mutation rate (in figuur 22 aangeduid met Par2). Deze parameter beschrijft de probabiliteit dat een oplossing een mutatie zal ondergaan. Als geen mutatie moet worden uitgevoerd, wordt de oplossing van de cross-over rechtstreeks lid van de volgende populatie. Net zoals de cross-over rate, wordt de mutation rate gekozen op basis van een pre-simulatie (zie sectie 5.2 en bijlage 3.2). Uit deze pre-simulatie wordt een mutation rate van 20% gekozen.

Gemiddelde doelfunctiewaarde

Pre-simulatie Par2 9,6 9,4 9,2 9 8,8 0%

5%

10% 15% 20% 25% 30% 35% 40% Parameterwaarde

Grafiek 2 - Resultaten pre-simulatie Par2

De random swap mutation stimuleert de diversificatie. Een willekeurige ingreep voorkomt namelijk dat de metaheuristiek vastloopt in een lokaal optimum.

63

Scatter Search 1 (SS1)

Figuur 29 visualiseert SS1 aan de hand van het conceptueel model waarin de implementatieonderdelen

kunnen

worden

onderscheiden.

Zoals

bij

GA1

worden

de

verschillende

implementatieonderdelen besproken voor SS1. Weer zijn er een aantal parameters die moeten worden gespecificeerd. Hiervoor wordt opnieuw een pre-simulatie gebruikt zoals beschreven in 5.2 en bijlage 3. De resultaten van deze pre-simulaties worden toegelicht bij de desbetreffende implementatieonderdelen.

Figuur 29 - Conceptueel model SS1

Diversification generation method

De eerste stap van SS1 heeft als objectief het construeren van een initiële set potentiële oplossingen met diversiteit als primaire doelstelling. Diverse oplossingen laten namelijk toe de volledige oplossingsruimte te beschrijven en vermijden dat gestart wordt met een te intense of eentonige set oplossingen. Om het doel van diversiteit te bereiken, wordt geopteerd voor het opstellen van een initiële populatie op basis van uiteenlopende prioriteitsregels die elk een eigen focus hebben (bijvoorbeeld gerelateerd aan tijd-, werkinhoud- en sociale cohesie). Concreet wordt een eerste reeks oplossingen gegenereerd

door

vijf

activiteitsgerelateerde

prioriteitsregels

te

combineren

met

vijf

werknemersgerelateerde prioriteitsregels, wat in totaal 25 leden geeft. Tabel 14 geeft een overzicht van de 64

gebruikte prioriteitsregels. De betekenis en berekeningen achter elk van deze prioriteitsregels wordt uitgebreider besproken in bijlage 5. Een aantal van deze prioriteitsregels zijn algemeen aanvaard en worden veel gebruikt in de literatuur (Vanhoucke, 2012), terwijl een aantal door de auteurs zelf werden opgesteld omdat het beschouwde MOTCP toelaat extra informatie hierin te verwerken. Tabel 14 - Gebruikte prioriteitsregels in SS1

Activiteiten Earliest Start Time Shortest Processing Time Least Non-Related Jobs Greatest Cumulative Work Content Greatest Resource Scarcity

Werknemers Greatest Time Related Skill Requirement Greatest Skill Scarcity Greatest Social Likability Greatest Social Tolerance Greatest Competence Weighted Social Strength

De 25 gecombineerde prioriteitslijsten ondergaan vervolgens drie maal een cross-over bewerking opdat de set van initiële oplossingen groot genoeg zou zijn. De resulterende set van 100 leden wordt RANDPOP genoemd. Voor de referentieset wordt samengesteld, wordt een selectie gemaakt van 50 van deze 100 leden. De gekozen oplossingen bestaan uit de twee oplossingen met de minimale totale fitness value enerzijds en de 16 oplossingen die best scoren op respectievelijk sociale cohesie, tijd en kosten. De resulterende set van 50 leden wordt POP genoemd. Er wordt geen tussentijdse Improvement method meer voorzien, onder andere omdat infeasibility niet aan de orde is wanneer gewerkt wordt met prioriteitsregels als oplossingsvoorstelling. Omdat de selectie van POP uit RANDPOP gebeurt op basis van de partiële doelfuncties wordt deze stap gekenmerkt door zowel diversificatie (“partiële”) als intensificatie (“doelfunctie”). Reference set construction method

Uit de in de Diversification generation method geconstrueerde POP, wordt in de Reference set construction method een gestructureerde verzameling van oplossingen opgesteld die zal dienen als starten eindpunt van de Scatter Search iteraties. Het doel van elke iteratie is om deze referentieset up te daten. Er wordt gesproken over een gestructureerde verzameling omwille van het feit dat een onderscheid wordt gemaakt tussen oplossingen met een grote doelfunctiewaarde enerzijds en oplossingen met een grote diversiteit anderzijds. Dit is één van de grote verschillen met GA. Concreet worden uit de 50 leden van POP eerst de 12 leden met de beste doelwaarde geselecteerd en ondergebracht in een verzameling genaamd B 1. Vervolgens worden de 8 leden die de grootste diversiteit vertonen tegenover de 12 leden uit B1 ook geselecteerd en ondergebracht in verzameling B2. Het selectiecriterium voor B1 is eenduidig en eenvoudig, namelijk de doelfunctiewaarde. Voor B2 is dit criterium echter iets complexer, gezien de diversiteit tussen 65

twee oplossingen moet worden gekwantificeerd. In deze setting wordt diversiteit gedefinieerd aan de hand van de euclidische afstand. Deze afstand d(x,y) tussen twee prioriteitslijsten x en y wordt berekend volgens onderstaande formule.

√∑

√∑

Onderstaand voorbeeld verduidelijkt de berekeningen in verband met diversiteit aan de hand van twee oplossingen in de vorm van de oplossingsvoorstelling. Hierbij is n = 5 en m = 10. LID X 50 100

30 20

56 80

80 26

100 40

80

100

60

25

80

LID Y 100 80

9 40

50 63

76 5

40 70

100

89

90

95

10

Figuur 30 - Voorbeeld euclidische afstand (prioriteitslijsten)

De euclidische afstand voor de prioriteitslijst in verband met activiteiten: √ De euclidische afstand voor de prioriteitslijst in verband met werknemers: √ Voor de totale diversiteit wordt het gemiddelde van beide afstanden berekend:

Na het selecteren van 12 leden uit POP voor B1 blijven er nog 38 leden over waaruit nu 8 leden moeten worden gekozen die zo veel mogelijk afwijken van B1. Tabel 15 geeft een overzicht van hoe B2 wordt gevormd. Voor elk van de 38 overblijvende leden uit POP (x) wordt de euclidische afstand berekend ten opzichte van elk van de 12 leden uit B1 (y). De kleinste euclidische afstand, weergegeven in de laatste kolom, wordt nu naar voren geschoven als maatstaf voor de diversiteit van een oplossing. De 8 oplossingen met de grootste minimale afstand worden geselecteerd voor B2 aangezien zij de grootste diversiteit bezitten.

66

Tabel 15 - Voorbeeld euclidische afstand (selectie van B2 uit POP)

X= (50 leden van POP – 12 leden van B1)

Y = 12 leden van B1

D(x,y)

1

2

3

4

5

6

7

8

9

10

11

12

Min D(x,y)

1

80

50

120

60

60

59

120

130

50

90

80

75

50

2

70

65

80

90

78

50

200

90

70

40

40

40

40

3

100

130

150

90

90

140

130

95

80

74

90

60

60

4

60

120

80

100

70

50

90

40

100

140

120

39

39

5

80

50

55

70

100

130

150

90

90

140

140

120

50

6

90

70

95

101

80

100

70

70

90

80

74

90

70

…

…

35

100

130

100

70

32

100

140

120

39

70

50

90

32

36

80

100

70

100

100

130

150

74

90

50

80

74

50

37

95

80

101

80

120

100

140

140

120

70

100

140

70

38

32

100

32

100

100

130

150

140

90

80

74

90

32

Iteratief zal deze referentieset evolueren via een sequentiële procedure die bestaat uit een Subset generation, Solution combination, Improvement en Reference set update method. Deze iteratie eindigt eens het stopcriterium van 4000 gegenereerde schedules is bereikt. De initiële grootte van de referentieset van 20 wordt hierbij constant gehouden met 12 oplossingen in B1 en 8 oplossingen in B2. Subset generation method

In deze stap start de eigenlijke iteratie. Vooraleer overgegaan wordt tot het vormen van nieuwe potentiële referentiesetleden, moet eerst bepaald worden welke oplossingen gecombineerd zullen worden. Voor dit implementatieonderdeel van SS wordt gekozen om oplossingen op twee manieren te combineren: A. Subset 1: B1 x B1 In totaal kunnen 144 (i.e. 12x12) mogelijke paren geconstrueerd worden op basis van B1. Hieruit worden een aantal paren willekeurig geselecteerd. Deze vormen samen de subset B1 x B1. B. Subset 2: B1 x B2 In totaal kunnen 96 (i.e. 12x8) mogelijke paren geconstrueerd worden door B1 en B2 te combineren. Ook hier worden een aantal paren willekeurig geselecteerd die samen de subset B1 x B2 vormen.

67

PRE-SIMULATIE: Par5 (Aantal leden per subset) Het aantal paren dat uitgekozen wordt om tot een subset toe te treden, wordt bepaald door de parameter Par5 uit figuur 29. Om een geschikte waarde voor deze parameter te bepalen, wordt gebruik gemaakt van een pre-simulatie (sectie 5.2 en bijlage 3.2). Uit grafiek 3, die de resultaten van deze pre-simulatie samenvat, wordt geconcludeerd dat een subset van 3 keer twee oplossingen resulteert in een minimale fitness value. Dit betekent dat er per iteratie 6 nieuwe oplossingen worden geconstrueerd, 3 uit elke subset. Deze worden in verdere fases van het algoritme onderzocht en verbeterd om potentiële nieuwe leden voor de referentieset te construeren.


9,8 9,7 9,6

9,5 9,4 9,3 1

2

3

4

5

Parameterwaarde Grafiek 3 - Resultaten pre-simulatie Par5

Omdat in B1xB1 kwaliteitsvolle oplossingen met elkaar worden gecombineerd, stimuleert deze subset intensificatie. De subset B1xB2 combineert dan weer oplossingen van hoge kwaliteit met sterk diverse oplossingen wat dan weer voor diversificatie zorgt.

Solution combination method

Op de koppels in B1xB1 en de koppels in B1xB2 wordt vervolgens een two-point cross-over uitgevoerd in de Solution combination method, waaruit één resultaat wordt onthouden. Op die manier worden een aantal nieuwe leden verkregen die, na de Improvement method, in aanmerking komen om de huidige referentieset te vervoegen. De two-point cross-over procedure werd reeds besproken bij GA1. De reden waarom voor dezelfde cross-over werd gekozen als bij GA, is een kwestie van behoud van vergelijkbaarheid. 68

Opnieuw wordt intensificatie gestimuleerd door het bouwen van een nieuwe populatie op basis van de informatie van potentieel sterke leden. Anderzijds laat het enige diversificatie toe omdat het niet weet welk deel van de informatie waardevol is en de combinatie dus op een willekeurige manier gebeurt. Improvement method

Alvorens af te wegen of de uit de Solution combination method gegenereerde oplossingen aan de voorwaarden voldoen om tot de referentieset toe te treden, worden de voorlopige oplossingen geoptimaliseerd in de Improvement method. Deze voert een local search (LS) uit op alle oplossingen. Een local search heeft als doel het bereiken van een lokaal optimum. Dit wordt gedaan door de buren van een specifieke oplossing te onderzoeken. Telkens wordt de beste buur geselecteerd en vervolgens worden de buren van deze beste buur onderzocht. Deze iteratie gaat verder tot geen betere buur meer kan gevonden worden. De geïmplementeerde toepassing van de local search procedure wordt hieronder toegelicht, vertrekkend van een prioriteitslijst met 10 activiteiten en 15 werknemers. 100

20

50

100

20

55

60

32

0 80

36 90

70 70

55

90

80

100

100

25

20

20

20

80

80

Figuur 31 - Voorbeeld local search (prioriteitslijst voor LS)

Een naburige oplossing wordt beschouwd als een prioriteitslijst waar twee naast elkaar gelegen prioriteiten zijn omgewisseld. Een dergelijke buur wordt gedefinieerd door middel van een index bestaande uit twee cijfers, gescheiden door een punt. Het cijfer voor het punt verwijst naar de verwisselde activiteitsprioriteiten, terwijl het tweede cijfer verwijst naar de verwisselde werknemersprioriteiten. Zo zijn bijvoorbeeld bij een buur met index 2.1 activiteitsprioriteiten 2 en 3 en werknemersprioriteiten 1 en 2 omgewisseld. 100

50

20

100

55

20

60

32

0 80

36 90

70 70

55 100

90

80

100

25

20

20

20

80

80

Figuur 32 - Voorbeeld local search (buur 2.1)

69

PRE-SIMULATIE: Par6 en Par7 (Local search parameters) In theorie zouden alle buren van een oplossing kunnen worden beschouwd en de beste worden geselecteerd om dan verder onderzocht te worden. Echter, in de probleemsetting met 40 werknemers en 20 activiteiten kunnen in totaal 800 dergelijke buren worden gevonden. Aangezien het stopcriterium wordt bereikt na 4000 gegenereerde schedules, zou deze local search de metaheuristiek te sterk domineren. Daarom wordt slechts een bepaald percentage van de buren onderzocht. Dit percentage wordt, zoals kan gezien worden in figuur 29, gedefinieerd door parameter Par6. Verder wordt, opnieuw om de dominantie van de local search onder te houden, een maximum gezet op het aantal local search-iteraties. Deze parameter wordt bepaald door Par7. Par6 en Par7 dienen te worden geoptimaliseerd door een pre-simulatie (sectie 5.2 en bijlage 3.2). Uit grafieken 4 en 5, die de resultaten van deze pre-simulaties samenvatten, wordt geconcludeerd dat het percentage van de te onderzoeken buren een minimum vertoont bij 2%. Het maximaal aantal iteraties in een local search procedure resulteert in een minimale fitness value bij 3 iteraties.

Gemiddelde doel functiewaarde

Pre-simulatie Par6 9,90 9,80 9,70 9,60 9,50 9,40 9,30 9,20 1%

2%

3%

4%

5%

Parameterwaarde Grafiek 4 - Resultaten pre-simulatie Par6


Pre-simulatie Par7 9,60 9,55 9,50 9,45 9,40 9,35 9,30 1

2

3

4

5

Parameterwaarde


70

Een local search is het bekendste voorbeeld van intensificatie. Er wordt namelijk gezocht naar een lokaal optimum in de buurt van een beschouwde oplossing. Reference set update method

Gezien de referentieset uit twee subsets is opgebouwd (B1 en B2), zijn er voor elke oplossing twee toegangstickets tot deze referentieset. Een eerste mogelijkheid is dat een oplossing een betere doelfunctiewaarde heeft dan het slechtst presterende lid van B1. Een tweede mogelijkheid is dat een oplossing een grotere diversiteit (i.e. hogere minimale euclidische afstand ten opzichte van de leden in B1) heeft dan het slechtst presterende lid van B2. Concreet wordt eerst en vooral gekeken of één van de oplossingen een betere doelfunctiewaarde heeft dan het slechtst presterende lid in B1. Als dit het geval is, wordt dit lid vervangen. Vervolgens wordt voor de overblijvende oplossingen onderzocht of deze een grotere diversiteit hebben tegenover de leden van B1 dan de huidige leden in B2. Indien dit het geval is, wordt de referentieset opnieuw geüpdatet. De berekeningen in verband met diversiteit werden toegelicht in de Reference set construction method. Methodologie Hierboven werd voor zowel GA als SS een algemene implementatie uitgewerkt die respectievelijk werden omgedoopt tot GA1 en SS1. Hierbij werd echter abstractie gemaakt van het gebruik van SSGS of PSGS. De in bijlage 4 besproken simulatie beschrijft hoe de performantie van een metaheuristiek kan worden onderzocht. Onderstaand schema geeft weer welke simulaties concreet worden uitgevoerd voor onderzoeksvraag 1.1 en hoe deze worden verwerkt. De verwerking houdt in dat er wordt uitgemiddeld over SSGS en PSGS om de invloed van het SGS er uit te filteren. Uiteindelijk worden GA1 en SS1 naast elkaar gelegd om te kijken of er eventuele verschillen bestaan in performantie.

SIMULATIE GA1 SSGS SIMULATIE GA1 PSGS SIMULATIE SS1 SSGS SIMULATIE SS1 PSGS

VERWERKING GA1 ANALYSE GA1 vs. SS1 VERWERKING SS1

Figuur 33 - Overzicht methodologie onderzoeksvraag 1.1

71

Resultaten Grafiek 6 geeft de resultaten weer voor GA1 en SS1 over de projectindicator I2. Voor elke beschouwde I2-waarde presteert SS1 beter dan GA1. In grafiek 7 wordt de dominantie van SS1 nog eens benadrukt met een gemiddelde doelfunctie waarde die 4,82% lager ligt dan GA1. Merk hierbij op dat de verschillen in doelfunctiewaarde klein lijken, maar dit is te wijten aan de keuze om de partiële doelfuncties relatief uit te drukken. Zo kan een relatief verschil van 1 voor de partiële doelfunctie kosten bijvoorbeeld wijzen op het gebruik van dubbel zo veel werknemers voor het project als minimaal nodig wordt geacht. Dit betekent dat de kleine verschillen toch belangrijk zijn in de gegeven context.

Performantie van GA1 en SS1 over I2

Gemiddelde performantie van GA1 en SS1

9,00

6,90

8,50

6,80 Gemiddelde Doelfunctiewaarde

Doelfunctiewaarde

8,00 7,50 7,00 6,50 6,00 5,50

5,00

6,70 6,60 6,50 6,40 6,30 6,20

4,50 4,00

6,10 0,1

0,25 0,5 0,75 Parameterwaarden I2

Grafiek 6 - Performantie van GA1 en SS1 over I2

0,9

GA1

SS1

Grafiek 7 - Gemiddelde performantie van GA1 en SS1

De conclusie voor onderzoeksvraag 1.1 luidt dus dat voor het beschouwde MOTCP, Scatter Search beter presteert dan Genetic Algorithm wanneer beide zonder probleemspecifieke intelligentie worden geïmplementeerd. Als pure zoekstrategie presteert SS opvallend beter dan GA in deze setting.

72

6.2.1.2 Onderzoeksvraag 1.2 Hoe kan probleemspecifieke intelligentie de performantie van GA verbeteren? Voor onderzoeksvraag 1.2 worden de implementatieonderdelen van GA1 onder de loep genomen, met als doel de performantie van GA voor het MOTCP te verbeteren. Concreet gebeurt dit in drie stappen waarbij in elke stap een nieuwe volwaardige metaheuristiek wordt gevormd. Deze uitbreidingen worden in het vervolg van dit werk aangeduid met respectievelijk GA2, GA3 en GA4. Tabel 16 vat kort samen hoe de implementatieonderdelen werden ingevuld voor de drie varianten in vergelijking met GA1. Hierna wordt stap voor stap ingegaan op deze implementatieonderdelen. Tabel 16 - Overzicht van de verschillende GA-implementaties

IMPLEMENTATIEONDERDEEL INITIELE POPULATIE VORMING DIRECT ELITISME SELECTIE CROSS-OVER MUTATIE

GA1 GA2 GA3 GA4 Willekeurige prioriteiten Intelligente prioriteiten n.v.t. Direct elitisme van 4 leden Rank selection Roulette wheel selection Two-point cross-over Two-point + Gemiddelde cross-over Random swap mutation Local search

Implementatie Genetisch Algorithm 2 (GA2)

Voor de tweede variant van GA werd vertrokken van GA1, waaraan vervolgens 3 aanpassingen werden doorgevoerd in de implementatieonderdelen direct elitisme, selectie en cross-over. Tabel 17 vat de implementatie van GA2 kort samen, waarna meer informatie wordt gegeven over de drie veranderde implementatieonderdelen. Tabel 17 - Implementatie GA2

INITIELE POPULATIE VORMING DIRECT ELITISME SELECTIE CROSS-OVER MUTATIE

GA2 Willekeurige prioriteiten Direct elitisme van 4 leden Roulette wheel selection Two-point cross-over + Gemiddelde cross-over Random swap mutation

73

Direct elitisme

Een eerste ingreep in de implementatie is het toevoegen van direct elitisme. In de nieuwe implementatievorm worden de vier beste oplossingen van een populatie rechtstreeks doorgestuurd naar de volgende populatie. Op die manier wordt verzekerd dat de beste oplossingen niet verloren gaan. Zonder deze stap bestaat immers de kans dat de beste oplossingen niet worden geselecteerd, of indien geselecteerd een cross-over- en/of mutatiebewerking ondergaan die resulteert in een oplossing met een minder optimale doelwaarde. Selectie

Naast het integreren van direct elitisme wordt ook de selectiemethode gewijzigd. Rank selection wordt hierbij vervangen door roulette wheel selection. Deze methode werkt gelijkaardig aan rank selection, maar neemt ook de relatieve verschillen tussen oplossingen in overweging. De kans op selectie hangt niet langer af van de rangorde van de oplossing, maar van het relatieve verschil in doelfunctiewaarde tegenover de andere oplossingen. In figuur 34 wordt deze selectiemethode visueel toegelicht. Er wordt een willekeurig lid uit de populatie geselecteerd door aan het wiel te draaien. Doordat de betere leden (deze met een lagere doelfunctiewaarde) een grotere oppervlakte van het roulette wheel innemen, is de kans dat deze gekozen worden groter. SELECTIE Individu met de slechtste doelfunctiewaarde Individu met de beste doelfunctiewaarde

Figuur 34 - Roulette wheel selection

74

Het bevoordelen van betere oplossingen stimuleert, net als bij rank selection, de intensificatie. De reden waarom roulette wheel selection meer intelligentie bezit dan de rank selection, is het feit dat naast de volgorde van de leden, ook de verschillen tussen de leden in rekening worden gebracht. De procedure wordt dus gekarakteriseerd door een nog grotere intensificatie bij het zoeken naar een oplossing voor het probleem. Cross-over

De laatste verandering, in vergelijking met GA1, is de keuze om een intelligentere cross-over uit te voeren. Naast de two-point cross-over wordt ook een gemiddelde cross-over geïmplementeerd. Deze crossover berekent voor elke activiteit/werknemer de gemiddelde prioriteit van de twee ouders. Onderstaand voorbeeld illustreert hoe de gemiddelde cross-over bewerking verloopt.

Figuur 35 - Voorbeeld gemiddelde cross-over (prioriteitslijsten voor cross-over)

Figuur 36 - Voorbeeld gemiddelde cross-over (prioriteitslijsten na cross-over)

De gemiddelde cross-over zal de two-point cross-over niet vervangen maar wordt als additionele cross-over ingevoerd. De geselecteerde ouders zullen dus enerzijds een gemiddelde cross-over ondergaan waar een eerste kind wordt gegenereerd. Anderzijds wordt een tweede kind gecreëerd door de two-point cross-over waarbij er willekeurig één oplossing wordt geselecteerd. Het grote voordeel van een gemiddelde cross-over is dat alle prioriteiten worden gecombineerd. Als de prioriteit in beide lijsten hoog (laag) is, blijft deze hoog (laag). Als deze echter hoog is in de ene en laag in de andere lijst, zal ze uitgemiddeld worden. Op die manier wordt over de iteraties heen gezorgd dat de belangrijke activiteiten/werknemers belangrijker worden en de minder belangrijke activiteiten/ werknemers minder belangrijk. In het voorbeeld is activiteit 4 in beide lijsten belangrijk en dit resulteert in de hoogste prioriteit na de cross-over. Activiteit 5 daarentegen had een hoge prioriteit bij de eerste ouder maar een zeer lage prioriteit bij de tweede ouder en krijgt daardoor nu ook een lagere prioriteit. Het incorporeren van een gemiddelde cross-over stimuleert met andere woorden de intensificatie. 75

Genetisch Algorithm 3 (GA3)

Deze derde variant van GA vertrekt op basis van GA2. Er wordt echter één belangrijke verandering aan toegevoegd namelijk de manier waarop de initiële populatie wordt samengesteld. Tabel 18 vat de implementatie van GA3 kort samen waarna meer duiding wordt gegeven bij de doorgevoerde wijziging. Tabel 18 - Implementatie GA3


GA3 Intelligente prioriteiten Direct elitisme van 4 leden Roulette wheel selection Two-point cross-over + Gemiddelde cross-over Random swap mutation

Initiële populatie vorming

In GA1 en GA2 werd de initiële populatie gevormd op basis van willekeurige prioriteiten. In deze derde implementatievariant worden deze willekeurige prioriteiten vervangen door intelligente prioriteitsregels. Deze voegen probleemspecifieke informatie toe aan de metaheuristiek. De initiële populatie wordt gevormd door 10 activiteitsgerelateerde prioriteitsregels te combineren met 5 werknemersgerelateerde prioriteitsregels. Dit geeft in totaal 50 populatieleden. Tabel 19 geeft een overzicht van de verschillende gebruikte prioriteitsregels. Deze worden uitgebreider besproken in bijlage 5. Tabel 19 - Gebruikte prioriteitsregels in GA3

Activiteiten Earliest Start Time Shortest Processing Time Longest Processing Time Most Immediate Successors Most Total Successors Least Non-Related Jobs Greatest Rank Positional Weight Greatest Work Content Greatest Cumulative Work Content Greatest Resource Scarcity

Werknemers Greatest Time Related Skill Requirement Greatest Skill Scarcity Greatest Social Likability Greatest Social Tolerance Greatest Competence Weighted Social Strength

Elk lid van de initiële populatie bestaat uit een combinatie van twee van de bovenstaande prioriteitsregels, zoals beschreven in 4.3. De initiële populatiegrootte van 50 wordt in een eerste generatieiteratie opnieuw gereduceerd tot 20 leden. Hierna blijft de populatiegrootte constant voor de daaropvolgende generaties. Het opstellen van prioriteitslijsten volgens uiteenlopende bronnen van informatie verhoogt de intelligentie die in het algoritme zit vervat.

76

Genetisch Algorithm 4 (GA4)

De vierde variant van het GA verschilt van GA3 omdat de random swap mutation wordt vervangen door een local search. Tabel 20 vat de implementatie van GA4 kort samen. Vervolgens wordt deze verandering en zijn implicaties besproken. Tabel 20 - Implementatie GA4


GA4 Intelligente prioriteiten Direct elitisme van 4 leden Roulette wheel selection Two-point cross-over + Gemiddelde cross-over Local search

Mutatie

In GA4 wordt, zoals reeds vermeld, de random swap mutation vervangen door een local search. De geïmplementeerde local search is gelijkaardig aan die beschreven in de sectie Improvement method onder SS1. Voor de local search dienen ook hier twee extra parameters te worden gedefinieerd binnen de mutatiestap: Par3 en Par4. Par3 beschrijft het procentueel aantal buren dat moet worden onderzocht, terwijl Par4 het maximaal aantal local search iteraties beschrijft. Figuur 37 geeft de locatie van deze parameters weer in GA.

Figuur 37 - Conceptueel model GA4

77

PRE-SIMULATIE: Par3 en Par4 (Local search parameters) Voor Par3 en Par4 werd, net zoals voor de andere parameters in GA, een pre-simulatie uitgevoerd (zie sectie 5.2 en bijlage 3.3). De resultaten staan beschreven in grafieken 8 en 9. Het percentage van de te onderzoeken buren vertoont twee minima. Omdat bij een te hoge parameterwaarde de local search te dominant wordt, wordt deze waarde op 1% gezet. Voor Par4 ligt het minimum bij 9 iteraties. Deze relatief hoge waarde compenseert deels de gereduceerde capaciteit tot intensificatie door de relatief lage waarde van Par3.


9,6 9,5 9,4 9,3

9,2 9,1 0,5% 1,0% 1,5% 2,0% 2,5% 3,0% 3,5% 4,0% 4,5% 5,0% Parameterwaarde



9,7 9,6 9,5 9,4 9,3 9,2 9,1 5

6

7

8

9

10

Parameterwaarde


Het introduceren van een local search als mutatie-stap zorgt voor een verschuiving van diversificatie naar intensificatie. Het willekeurig wisselen van prioriteiten in de random swap mutation om uit een eventueel lokaal optimum te komen, wordt nu vervangen door een intelligente wissel van prioriteiten op het vlak van intensificatie door de fitness value in rekening te brengen. Er werd voor deze mutatieimplementatie gekozen na een analyse op basis van trial and error omdat de performantie van de metaheuristiek door deze intensificatie sterk verhoogde. Dit wordt in onderstaande analyse besproken.

78

Methodologie Hierboven werden voor GA enkele meer intelligente implementaties uitgewerkt die respectievelijk werden omgedoopt tot GA2, GA3 en GA4. De in bijlage 4 besproken simulatie beschrijft hoe de performantie van deze metaheuristieken kan worden onderzocht. Onderstaand schema geeft weer welke simulaties concreet werden uitgevoerd voor onderzoeksvraag 1.2 en hoe deze werden verwerkt. Opnieuw dienen de simulaties te worden uitgemiddeld over SSGS en PSGS. SIMULATIE GA1 SSGS [ENKEL OVER I2] SIMULATIE GA1 PSGS [ENKEL OVER I2] SIMULATIE GA2 SSGS [ENKEL OVER I2] SIMULATIE GA2 PSGS [ENKEL OVER I2] SIMULATIE GA3 SSGS [ENKEL OVER I2] SIMULATIE GA3 PSGS [ENKEL OVER I2] SIMULATIE GA4 SSGS [ENKEL OVER I2] SIMULATIE GA4 PSGS [ENKEL OVER I2]

VERWERKING GA1

VERWERKING GA2 ANALYSE GA1 vs. GA2 vs. GA3 vs. GA4 VERWERKING GA3

VERWERKING GA4


79

Resultaten Grafiek 10 geeft de resultaten weer voor de gemiddelde performantie van GA1, GA2, GA3 en GA4. Het is duidelijk dat elke implementatiestap gepaard gaat met een verbetering van de performantie. Zo brengt de meeste intelligente implementatie GA4 een gemiddelde verbetering met zich mee van 7.35% in vergelijking met de algemene implementatie GA1.

Performantie van GA bij verschillende implementaties 6,90


6,80 6,70 6,60 6,50 6,40 6,30 6,20 6,10 6,00 GA 1

GA 2

GA 3

GA 4

Grafiek 10 - Resultaten onderzoeksvraag 1.2

Wanneer dieper wordt ingegaan op de wijzigingen die de implementatieonderdelen hebben ondergaan (samengevat in tabel 21), kan worden geconcludeerd dat deze vooral een grotere focus plaatsten op intensificatie. Dit laatste lijkt dus een belangrijke rol te spelen in het beschouwde MOTCP. Tabel 21 - Overzicht van de verschillende GA-implementaties


GA1 GA2 GA3 GA4 Willekeurige prioriteiten Intelligente prioriteiten n.v.t. Direct elitisme van 4 leden Rank selection Roulette Wheel Selection Two-point cross-over Two-point + Gemiddelde cross-over Random swap mutation Local search

80

6.2.1.3 Onderzoeksvraag 1.3 Hoe kan probleemspecifieke intelligentie de performantie van SS verbeteren? In onderzoeksvraag 1.3 worden de implementatieonderdelen van SS1 geoptimaliseerd voor het beschouwde MOTCP. Er worden twee uitbreidingen opgesteld waarbij in elke uitbreiding een nieuwe volwaardige metaheuristiek wordt gevormd. Deze uitbreidingen worden in het vervolg aangeduid met respectievelijk SS2 en SS3. Tabel 22 vat kort samen hoe de implementatieonderdelen werden ingevuld voor deze twee uitbreidingen. Hierna wordt op elk van hen dieper ingegaan. Tabel 22 - Overzicht van de verschillende SS-implementaties


SS1

SS2 SS3 Intelligente prioriteiten B1 = 12 en B2 = 8 B1 = 4 en B2 = 16 (B1 x B1) en (B1 x B2) + (B1 x B1) en (B1 x B2) + Willekeurige selectie B1 Roulette wheel selection B1 Two-point Two-point + Gemiddelde cross-over cross-over Local search B1 = f(doelwaarden) en B2 = f(euclidische afstand t.o.v. B1)

Implementatie Scatter Search 2 (SS2)

Voor deze tweede variant van SS wordt vertrokken van SS1 en wordt gekozen om een verandering door te voeren op twee plaatsen in de metaheuristiek: Subset generation en Solution combination method. Tabel 23 vat de implementatie van SS2 kort samen, waarna de veranderingen verder worden gespecificeerd. Tabel 23 - Implementatie SS2

SS2 DIVERSIFICATION GENERATION METHOD REFERENCE SET CONSTRUCTION METHOD SUBSET GENERATION METHOD SOLUTION COMBINATION METHOD IMPROVEMENT METHOD REFERENCE SET UPDATE METHOD

Intelligente prioriteiten B1 = 12 en B2 = 8 (B1 x B1) en (B1 x B2) + Roulette wheel selection B1 Two-point cross-over + Gemiddelde cross-over Local search B1 = f(doelwaarden) en B2 = f(euclidische afstand t.o.v. B1)

81

Subset generation method

Het selectiemechanisme op basis waarvan subsets worden samengesteld, werd in SS2 aangepast. Waar dit bij SS1 gebeurde door een willekeurige selectie, wordt hiervoor nu roulette wheel selection gebruikt.

Meer

informatie

over

deze

selectiemethode

kan

worden

gevonden

bij

de

implementatiebeschrijving van GA2. Zoals werd aangehaald bij het beschrijven van roulette wheel selection in GA2 zal roulette wheel selection bijdragen tot intensificatie. Solution combination method

De cross-over opties worden, net als bij GA2, uitgebreid met een gemiddelde cross-over methode. De oplossingen uit de subsets B1 x B1 en B1 x B2 gebruiken op willekeurige manier één van beide cross-overs. De intelligentie van een gemiddelde cross-over zit in het feit dat het informatie van andere prioriteitsregels slimmer gaat combineren door voor elke prioriteit twee bronnen van informatie te gebruiken. Scatter Search 3 (SS3)

Voor deze derde variant van SS werd SS2 aangepast in de Reference set construction (update) method. Tabel 24 vat de implementatie van SS3 kort samen. Tabel 24 - Implementatie SS3



Reference set construction (update) method

De grootte van de referentieset werd vastgelegd op 20 leden. In lijn met de literatuur werd hierbij een grotere deelverzameling voorzien voor de kwaliteitsvolle oplossingen en daarom werd gekozen voor een B1-grootte van 12 leden en een B2-grootte van 8 leden (Van Peteghem & Vanhoucke, 2011). Via een simulatie van verschillende combinaties kan echter geconcludeerd worden dat de performantie van het algoritme verhoogt door B1 te beperkten tot 4 leden, en B2 te vergroten tot 16 leden. De resultaten waarop deze beslissing is gebaseerd, worden samengevat in grafiek 11.

82


Performantie van SS bij verschillende implementaties van de Reference set construction method 6,42 6,40 6,38 6,36 6,34 6,32 6,30 6,28 6,26

Grafiek 11 - Performantie van SS bij verschillende B2- en B2-groottes

Deze verandering verhoogt wederom de intensificatie aangezien een kleinere B1 de kansen vergroot dat de beste oplossingen opnieuw worden geselecteerd en gebruikt in de subsets en hun informatie dus kunnen doorgeven aan volgende generaties. Een te kleine B1 resulteert echter in een suboptimale oplossing aangezien dit te weinig diversiteit genereert in de oplossing en geen verbeteringen meer kunnen worden bekomen. Methodologie Hierboven werden voor SS enkele meer intelligente implementaties uitgewerkt die respectievelijk werden omgedoopt tot SS2 en SS3. De in bijlage 4 besproken simulatie beschrijft hoe de performantie van deze metaheuristieken kan worden onderzocht. Onderstaand schema geeft weer welke simulaties concreet worden uitgevoerd voor onderzoeksvraag 1.2 en hoe deze worden verwerkt. Opnieuw dienen de simulaties te worden uitgemiddeld over SSGS en PSGS. SIMULATIE SS1 SSGS [ENKEL OVER I2] SIMULATIE SS1 PSGS [ENKEL OVER I2] SIMULATIE SS2 SSGS [ENKEL OVER I2] SIMULATIE SS2 PSGS [ENKEL OVER I2] SIMULATIE SS3 SSGS [ENKEL OVER I2] SIMULATIE SS3 PSGS [ENKEL OVER I2]

VERWERKING SS1

VERWERKING SS2

ANALYSE SS1 vs. SS2 vs. SS3

VERWERKING SS3


83

Resultaten Grafiek 12 geeft de resultaten weer voor de gemiddelde performantie van SS1, SS2 en SS3. Het is duidelijk dat elke implementatiestap gepaard gaat met een verbetering van de performantie. Zo brengt de meeste intelligente implementatie SS3 een gemiddelde verbetering met zich mee van 2.66% in vergelijking met de algemene implementatie van SS1.


Performantie van SS bij verschillende implementaties 6,50 6,45 6,40 6,35 6,30 6,25 6,20

SS 1

SS2

SS 3

Grafiek 12 - Resultaten onderzoeksvraag 1.3

Net als bij GA kan uit de samenvattende tabel (tabel 25) geconcludeerd worden dat de wijzigingen in de implementatieonderdelen van SS opnieuw meer intensificatie met zich mee brengen. Dit bevestigt nogmaals het belang van intensificatie in het beschouwde MOTCP. Tabel 25 - Overzicht van de verschillende SS implementaties


SS1

SS2 SS3 Intelligente prioriteiten B1 = 12 en B2 = 8 B1 = 4 en B2 = 16 (B1 x B1) en (B1 x B2) + (B1 x B1) en (B1 x B2) + Willekeurige selectie B1 Roulette wheel selection B1 Two-point Two-point + Gemiddelde cross-over cross-over Local search B1 = f(doelwaarden) en B2 = f(euclidische afstand t.o.v. B1)

84

6.2.1.4 Onderzoeksvraag 1.4 Wat is het verschil tussen GA en SS bij een implementatie met probleemspecifieke intelligentie? Implementatie Onderzoeksvraag 1.4 heeft als bedoeling onderzoeksvraag 1 af te sluiten door GA en SS opnieuw te vergelijken voor het MOTCP, maar nu in hun geoptimaliseerde implementatievorm. Deze implementaties werden opgebouwd in onderzoeksvragen 1.2 en 1.3. Hiernaar wordt verwezen als GA4 en SS3. Tabellen 26 en 27 vatten deze implementaties nog eens kort samen. Tabel 26 - Implementatie GA4


GA4 Intelligente prioriteitsregels Direct elitisme van 4 leden Roulette wheel selection Two-point cross-over + Gemiddelde cross-over Local search

Tabel 27 - Implementatie SS3



Methodologie De simulaties die voor deze onderzoeksvraag vereist zijn, werden reeds uitgevoerd voor onderzoeksvraag 1.2 en 1.3 bij het analyseren van de performantie van respectievelijk GA4 en SS3. Deze resultaten zullen nu opnieuw worden geanalyseerd met als verschil dat GA en SS worden vergeleken.


85

Resultaten Uit grafieken 13 en 14 kan worden afgeleid dat de verschillen tussen GA en SS in de optimale, intelligente implementatie volledig zijn weggewerkt. De dominantie van SS tegenover GA in de algemene implementatie is door het toevoegen van intelligentie verdwenen. Zoals kan worden afgeleid uit de bespreking van de verschillende implementatievormen, leidt het toevoegen van intelligentie in bijna alle gevallen tot intensificatie in de metaheuristieken. Als voorbeeld werd ook het verschil in performantie bij verschillende parameterwaarden voor I2 toegevoegd. Zoals kan worden gezien op de grafiek is hier geen verschil merkbaar. Ook voor de andere in hoofdstuk 3 gedefinieerde projectindicatoren bestaat geen verschil over de verschillende parameterwaarden heen.

Gemiddelde Performantie van GA4 en SS3

8,50 8,00 7,50 7,00 6,50 6,00 5,50 5,00 4,50

Gemiddelde Doelfunctiewaarde

Doelfunctiewaarde

Performantie van GA4 en SS3 in functie van I2

0,1

0,25

0,5

0,75

6,90 6,80 6,70 6,60 6,50 6,40 6,30 6,20 6,10 GA 4

0,9

SS 3

Parameterwaarden I2 Grafiek 13 - Performantie GA4 en SS3 over I2

Grafiek 14 - Gemiddelde performantie GA4 en SS3

Omdat de hogere graad van intensificatie de performantie van de metaheurisitieken positief beïnvloedt, wordt er nog een extra analyse uitgevoerd. Een grote bron van intensificatie is namelijk de local search procedure. Deze is aanwezig in zowel GA4 als in SS3, weliswaar met andere waarden voor de parameters. De resultaten van deze analyse worden samengevat in grafieken 15 en 16 waar de algemene performantie van de local search procedures in GA en SS wordt vergeleken met die van de verschillende implementatievarianten

van

beide

metaheuristieken.

De

intelligente

implementaties

van

de

metaheuristieken presteren hierbij beter dan de local search procedures. De local search uit GA4 lijkt wel tot betere resultaten te leiden dan de algemene variant GA1. Er kan worden besloten dat de metaheuristieken wel degelijk een meerwaarde bezitten ten opzichte van een pure local search.

86

Gemiddelde performantie van de drie implementaties van SS en de LS uit SS3

6,90

6,90

6,80

6,80

6,70

6,70



Gemiddelde performantie van de vier implementaties van GA en de LS uit GA4

6,60 6,50 6,40 6,30 6,20 6,10

6,60 6,50 6,40 6,30 6,20 6,10

6,00

6,00 GA 1

GA 2

GA 3

GA 4

LS GA

Grafiek 15 - Vergelijking tussen de 4 GA’s en LS

SS 1

SS 2

SS 3

LS SS

Grafiek 16 - Vergelijking van de 3 SS'en en LS

87

6.2.1.5 Besluit In onderzoeksvraag 1 werd het performantieverschil tussen GA en SS onderzocht voor het beschouwde MOTCP. Verder werden een aantal inzichten verworven rond de begrippen intensificatie en diversificatie. De gevoerde analyses en resultaatverwerking werden gestructureerd aan de hand van vier sub-onderzoeksvragen: Onderzoeksvraag 1: Wat is het verschil in impact tussen GA en SS op de totale doelfunctiewaarde?

1.1 Wat is het verschil tussen GA en SS bij een implementatie zonder probleemspecifieke intelligentie?

Zonder

probleemspecifieke

intelligentie voor het

beschouwde MOTCP presteert de

metaheuristiek SS beter dan GA. Gemiddeld genomen kan een verbetering van 4,82% worden waargenomen bij het gebruik van SS tegenover GA. v

1.2 Hoe kan probleemspecifieke intelligentie de performantie van GA verbeteren? intelligentie?

Door het toevoegen van probleemspecifieke intelligentie kan de performantie van GA gemiddeld met 7,35% verbeterd worden. In het beschouwde MOTCP vertaalt het toevoegen van intelligentie zich voor GA in een grotere nadruk op intensificatie. 1.3 Hoe kan probleemspecifieke intelligentie de performantie van SS verbeteren? intelligentie?

Door het toevoegen van probleemspecifieke intelligentie kan de performantie van SS gemiddeld met 2,66% verbeterd worden. In het beschouwde MOTCP vertaalt het toevoegen van intelligentie zich voor SS in een grotere nadruk op intensificatie. 1.4 Wat is het verschil tussen GA en SS bij een implementatie met probleemspecifieke intelligentie?

De intelligente implementaties van GA en SS presteren gemiddeld even goed. Beiden presteren

intelligentie?

bovendien als metaheuristieken beter dan een pure local search wat hun relevantie bevestigt bij het aanpakken van het complexe MOTCP. Figuur 41 en 42 stellen deze resultaten nog eens visueel voor.

88

4,82 % 0%

Figuur 41 - Vergelijking performantieverschil GA en SS met en zonder intelligentie

Bovenstaande figuur toont kwalitatief de performantieverschillen tussen de twee metaheuristieken, eerst zonder en daarna met intelligentie. Het initiële verschil wordt weggewerkt door de toevoeging van intelligentie. Daarnaast verbetert de performantie van beide algoritmes. Het toevoegen van intelligentie betekent in het MOTCP het toevoegen van intensificatie. Zoals onderstaande (kwalitatieve) figuur echter aantoont, presteren de metaheuristieken beter dan een pure intensificatie-methode zoals local search.

GA1 , SS1

GA4 , SS3

DIVERSIFICATIE

Local Search INTENSIFICATIE

Figuur 42 - Performantiewijzigingen door toevoegen van intelligentie

89

6.2.2 Onderzoeksvraag 2 ONDERZOEKSVRAAG 2: Wat is het verschil in impact tussen PSGS en SSGS op de totale doelfunctiewaarde? Onderzoeksvraag 2 heeft als hoofddoel te achterhalen of er een voorkeur bestaat tussen de schedulingsmethodes PSGS en SSGS in het MOTCP. Dit wordt ook geanalyseerd voor de projectindicatoren. Hiermee wordt de analyse van metaheuristieken uit onderzoeksvraag 1 uitgebreid naar de planningsmethodes binnen een metaheuristiek. Eerst wordt de methodologie besproken zodat duidelijk wordt welke simulaties plaatsvonden en hoe de resultaatverwerking verliep. Vervolgens worden de eigenlijke resultaten aangehaald en verduidelijkt.

Methodologie Voor deze onderzoeksvraag wordt verder gewerkt met de intelligente implementatievormen van GA en SS die werden opgesteld in onderzoeksvraag 1. Om de coherentie te bewaren, worden deze intelligente metaheuristieken hier aangeduid als respectievelijk GA4 en SS3. De volledige simulatie wordt beschreven in bijlage 4. Deze zal nu opnieuw worden uitgevoerd voor zowel PSGS als SSGS. De vergelijking wordt gemaakt door zowel GA4 als SS3 hetzelfde project te laten plannen met beide schedulingsalgoritmes. Op die manier kan de invloed van verschillende waarden voor deze indicatoren op de performantie van PSGS en SSGS worden onderzocht. Onderstaande figuur verduidelijkt de analyse. SIMULATIE GA4 SSGS SIMULATIE SS3 SSGS

VERWERKING SSGS ANALYSE SSGS vs. PSGS

SIMULATIE GA4 PSGS SIMULATIE SS3 PSGS

VERWERKING PSGS

Figuur 43 – Overzicht methodologie onderzoeksvraag 2

Zoals reeds aangehaald heeft de definiëring van de objectieven in relatieve termen als gevolg dat de verschillen steeds klein lijken. Om deze verschillen toch duidelijk te maken, wordt gewerkt met het concept netto doelfunctiewaarde. Dit is het verschil tussen PSGS en SSGS. Omdat het beschouwde MOTCP een minimalisatieprobleem is, wijst een positieve netto doelfunctiewaarde op superioriteit van SSGS, terwijl een negatieve waarde op superioriteit van PSGS wijst.

90

De analyse wordt, conform de simulatie besproken in bijlage 4, uitgevoerd voor negen projectindicatoren. Vijf van deze indicatoren zijn gerelateerd aan de netwerktopologie (I2, I3, I4, I5 en I6) en vier indicatoren zijn gerelateerd aan de opbouw van het werknemersbestand (µc, CVC, µs en CVs).

Resultaten Grafieken 17 tot en met 25 vatten de resultaten samen voor elke projectindicator. Zoals in de methodologie werd beschreven, wordt hiervoor de netto doelfunctiewaarde berekend waarbij een positieve waarde wijst op een superieure performantie van SSGS tegenover PSGS. Deze netto doelfunctiewaarde wordt uitgezet op de verticale as. Elke grafiek doet dit voor een unieke projectindicator. Voor alle projectindicatoren is SSGS superieur in vergelijking met PSGS wat blijkt uit een positieve netto doelfunctiewaarde. Een mogelijke reden hiervoor is dat de beschikbaarheid van werknemers in de simulatie relatief groot is tegenover de vraag naar resources. Kolisch (1996) heeft aangetoond dat in een dergelijk geval, SSGS beter presteert dan PSGS. Voor de projectindicator I2 is het hierbij opmerkelijk dat de superioriteit van SSGS afneemt als de waarde van de projectindicator toeneemt. Er blijkt dus een algemene preferentie te bestaan voor de planningsmethode SSGS bij lage en gemiddelde waarden voor I2, terwijl bij hoge waarden indifferentie optreedt. Een hoge I2 wijst namelijk op een meer serieel project. In een dergelijk geval is er minder bewegingsvrijheid voor een schedulingsmethode om te profiteren van nog beschikbare resources. Dit verklaart met andere woorden waarom de superioriteit van SSGS afneemt naar mate het project meer serieel wordt. De andere projectindicatoren oefenen geen noemenswaardige invloed uit. Enkel bij de werknemersgerelateerde indicator µc wordt de dominantie van SSGS ten opzichte van PSGS groter naarmate het gemiddelde competentieniveau toeneemt. Dit is te verklaren door het feit dat een hoger gemiddeld competentieniveau bij een constant aantal werknemers resulteert in de aanwezigheid van meer resources. Het eerder beschreven effect van Kolisch (1996) zal dus versterkt worden naarmate µc toeneemt.

91

0,20 0,15 0,10 0,05 0,00 -0,05 -0,10 -0,15 -0,20

0,20 0,15 0,10 0,05 0,00 -0,05 -0,10 -0,15 -0,20

0,1

0,25

0,5

0,75

0,9

Netto doelfunctiewaarde (PSGS - SSGS)

Performantie van planningsmethodes PSGS en SSGS in functie van de projectindicator I3



Parameterwaarden

Grafiek 17 - Vergelijking PSGS en SSGS voor I2



Performantie van planningsmethodes PSGS en SSGS in functie van de projectindicator I5 Netto doelfunctiewaarde (PSGS - SSGS)


0,20 0,15 0,10 0,05 0,00

-0,05 -0,10 -0,15 -0,20

0,20 0,15 0,10 0,05 0,00 -0,05 -0,10 -0,15 -0,20

Parameterwaarden

Parameterwaarden




Performantie van planningsmethodes PSGS en SSGS in functie van de projectindicator 𝜇c

0,20 0,15 0,10 0,05 0,00 -0,05 -0,10 -0,15 -0,20

0,20 0,15 0,10 0,05 0,00 -0,05 -0,10 -0,15 -0,20



Parameterwaarden

Parameterwaarden


1,33

1,66

2,00

2,33

2,66

Parameterwaarden

Grafiek 22 - Vergelijking PSGS en SSGS voor 𝜇c

92

Performantie van planningsmethodes PSGS en SSGS in functie van projectindicator CVc

0,20 0,15 0,10 0,05 0,00 -0,05 -0,10 -0,15 -0,20

10

25

50

75

90

Parameterwaarden

Grafiek 23 - Vergelijking PSGS en SSGS voor 𝜇s



Performantie van planningsmethodes PSGS en SSGS in functie van de projectindicator 𝜇s

0,20 0,15 0,10 0,05 0,00 -0,05 -0,10 -0,15 -0,20

0,5

0,75

1

1,33

1,58

Parameterwaarden

Grafiek 24 - Vergelijking PSGS en SSGS voor CVc


Performantie van planningsmethodes PSGS en SSGS in functie van projectindicator CVs 0,20 0,15 0,10 0,05 0,00 -0,05 -0,10 -0,15 -0,20

0,5

0,75

1

1,33

1,58

Parameterwaarden

Grafiek 25 - Vergelijking PSGS en SSGS voor CVs

93

Besluit In onderzoeksvraag 2 werd het performantieverschil tussen SSGS en PSGS voor het beschouwde MOTCP onderzocht. Het doel was om te achterhalen of er een voorkeur bestaat tussen de schedulingsmethodes voor verschillende projectindicatoren. ONDERZOEKSVRAAG 2: Wat is het verschil in impact tussen PSGS en SSGS op de totale doelfunctiewaarde? De conclusies die werden getrokken uit deze analyse zijn: 

Voor alle projectindicatoren domineert SSGS over PSGS voor het beschouwde MOTCP. Een mogelijke verklaring hiervoor is het feit dat de beschikbaarheid van werknemers relatief groot is in vergelijking met de vraag naar resources van de activiteiten. Dit fenomeen verklaart ook waarom de superioriteit van SSGS toeneemt als het gemiddelde competentieniveau stijgt.

Figuur 44 – Vergelijking PSGS en SSGS

Naarmate een project een meer serieel karakter heeft, vervaagt de superioriteit van SSGS en ontstaat een indifferentie tussen beide methodes. De oorzaak hiervan ligt in het feit dat seriële projecten in het algemeen minder bewegingsvrijheid toelaten voor een schedulingsmethode om te profiteren van nog beschikbare resources, waardoor SSGS en PSGS zich niet meer echt van elkaar kunnen onderscheiden. Performantie van planningsmethodes PSGS en SSGS in functie van de projectindicator I2 0,20 Netto doelfunctiewaarde (PSGS - SSGS)



0,15

SUPERIORITEIT VAN SSGS

0,10 0,05

INDIFFERENTIE

0,00 -0,05

0,1

0,25

0,5

0,75

0,9

-0,10

SUPERIORITEIT VAN PSGS

-0,15 -0,20

Parameterwaarden

Figuur 45 - Verschil tussen PSGS en SSGS bij I2

94

6.2.3 Onderzoeksvraag 3 ONDERZOEKSVRAAG 3: Wat is de impact van elke projectindicator op de totale doelfunctiewaarde?

Waar in onderzoeksvragen 1 en 2 het verschil in performantie werd onderzocht tussen verschillende metaheuristieken wordt in onderzoeksvraag 3 dieper ingegaan op de invloed van de projecttypes op de performantie van een metaheuristiek. Enerzijds kan het projecttype het de metaheuristiek makkelijker of moeilijker maken om de beste oplossing te vinden en anderzijds kan het projecttype een directe impact hebben op de best mogelijke oplossing. Het doel van deze onderzoeksvraag is te achterhalen welke projectindicatoren een grotere of kleinere invloed uitoefenen op de performantie van een metaheuristiek.

Methodologie Net als in onderzoeksvraag 2, zullen de simulaties voor onderzoeksvraag 3 uitgevoerd worden voor GA4 en SS3, aangezien deze in onderzoeksvraag 1 werden geïdentificeerd als de best presterende implementatievormen voor GA en SS. De volledige simulatie zoals beschreven in bijlage 4 zal voor elk van de vier metaheuristieken worden uitgevoerd. Voor de verwerking van de resultaten worden de simulatieresultaten voor de vier metaheuristieken uitgemiddeld per parameterwaarde. Onderstaand schema geeft concreet weer welke simulaties worden uitgevoerd voor onderzoeksvraag 3, hoe deze worden verwerkt en welke analyse hieruit volgt.

SIMULATIE GA4 SSGS SIMULATIE GA4 PSGS SIMULATIE SS3 SSGS SIMULATIE SS3 PSGS

VERWERKING I2 VERWERKING I3 VERWERKING I4 VERWERKING I5 VERWERKING I6 VERWERKING µc VERWERKING CVc VERWERKING µs VERWERKING CVs

ANALYSE I2 vs. I3 vs. I4 vs. I5 vs. I6 vs. µc vs. CVc vs. µs vs. CVs

Figuur 46 - Overzicht methodologie onderzoeksvraag 3

De analyse per projectindicator onderzoekt hoe de gemiddelde doelfunctiewaarde van de vier metaheuristieken wijzigt voor bepaalde waarden of intervallen. Voor de analyse over de projectindicatoren moet een referentiepunt gevonden worden waarmee de projectindicatoren onderling kunnen worden vergeleken. Dit moet toelaten om bijvoorbeeld een gemiddelde sociale cohesie van 75 in het interval 0 tot 95

100 te vergelijken met een gemiddeld competentieniveau van 2.33 in het interval 1 tot 3. Om deze analyse mogelijk te maken, is met andere woorden nood aan een vergelijkingsbasis die toelaat de verschillende projectindicatoren tegenover elkaar uit te zetten. Hiervoor worden voor elke projectindicator de beschouwde waarden relatief uitgedrukt tegenover het bestaansinterval van die projectindicator. Onderstaande tabellen tonen als voorbeeld hoe deze transformatie gebeurt voor de parameter µs voor vijf indicatorwaarden variërend van 0 tot 100 en voor de parameter µc voor vijf indicatorwaarden variërend van 1 tot 3. Via lineaire interpolatie kunnen de doelfunctiewaarden dan worden uitgezet en met elkaar worden vergeleken. Voor de indicatorintervallen werd het gemiddelde van elk interval gebruikt als indicatorwaarde. Tabel 28 - Voorbeeld transformatie onderzoeksvraag 3 (sociale cohesie)

GEMIDDELDE SOCIALE COHESIE Indicatorwaarde

Doelfunctiewaarde

Transformatie van de indicatorwaarde

Getransformeerde indicatorwaarde

10 25 50 75 90

3.5 5.2 6.1 7.2 9.1

= (10-0)/(100-0) = (25-0)/(100-0) = (50-0)/(100-0) = (75-0)/(100-0) = (90-0)/(100-0)

10.00% 25.00% 50.00% 75.00% 90.00%

Tabel 29 - Voorbeeld transformatie onderzoeksvraag 3 (competentieniveau)

Indicatorwaarde 1.33 1.66 2.00 2.33 2.66

GEMIDDELD COMPETENTIENIVEAU Transformatie van Doelfunctiewaarde de indicatorwaarde 8.5 = (1.33-1)/(3-1) 7.0 = (1.66-1)/(3-1) 6.0 = (2.00-1)/(3-1) 4.9 = (2.33-1)/(3-1) 4.1 = (2.66-1)/(3-1)

Getransformeerde indicatorwaarde 16.50% 33.00% 50.00% 66.50% 83.00%

Tabel 30 - Voorbeeld transformatie onderzoeksvraag 3 (voor interpolatie)

Getransformeerde Indicatorwaarde 10.00% 16.50% 25.00% 33.00% 50.00% 66.50% 75.00% 83.00% 90.00%

Doelfunctiewaarde µs

Doelfunctiewaarde µc

3.5 8.5 5.2 6.1

7.0 6.0 4.9

7.2 4.1 9.1 96

Onderstaande formule kan worden gebruikt om via lineaire interpolatie de doelfunctiewaarden (y) te schatten op basis van de getransformeerde indicatorwaarden (x).

ontbrekende

Tabel 31 - Voorbeeld transformatie onderzoeksvraag 3 (na interpolatie)

Getransformeerde indicatorwaarden 10.00% 16.50% 25.00% 33.00% 50.00% 66.50% 75.00% 83.00% 90.00%

Doelfunctiewaarde µs

Doelfunctiewaarde µc

3.5 4.2 5.2 5.5 6.1 6.8 7.2 8.2 9.1

8.5 7.7 7.0 6.0 4.9 4.5 4.1

Op basis van bovenstaande tabel kunnen µs en µC worden vergeleken tussen een laagste extreme waarde van 16,5% en een hoogste extreme waarde van 83%.

97

Resultaten Op grafieken 26 en 27 wordt de impact van elke projectindicator op de gemiddelde performantie getoond. Hierbij worden CVs en CVC afzonderlijk beschouwd aangezien voor de variatiecoëfficiënt geen eindige bovengrens bestaat.

Invloed van projectindicatoren (2)

8

8

7,5

7,5

Doelfunctiewaarde

Doelfunctiewaarde

Invloed van projectindicatoren

7 6,5 6 5,5

7 6,5

6 5,5 5

5 0%

20%

40%

60%

80%

0

100%

0,25 0,5 0,75

Relatieve parameterwaarden

1

1,25 1,5 1,75

2

Parameterwaarden

I2

I3

I4

I5

I6

Gemiddeld competentieniveau

CV competentieniveau

CV Sociale cohesie

Gemiddelde sociale cohesie

Grafiek 26 - Invloed van projectindicatoren

Grafiek 27 - Invloed van projectindicatoren (2)

Uit deze grafieken kan worden afgeleid dat de projectindicatoren I3, I4, I5, I6, CVS en CVC geen systematische invloed uitoefenen op de doelfunctiewaarde. De projectindicatoren I2, µs en µc oefenen daarentegen wel een systematische invloed uit. Om de analyse van deze impact overzichtelijk te maken, werden deze indicatoren afzonderlijk uitgezet in grafiek 28.

Invloed van de projectindicatoren

Doelfunctiewaarde

8 7,5 7


6,5


6 5,5

I2

5 0%

20%

40%

60%

80%

100%

Relatieve parameterwaarden Grafiek 28 - Invloed van belangrijkste projectindicatoren

98

De projectindicator I2 vertoont een positieve impact naarmate de parameterwaarde stijgt. Hoe meer serieel het project wordt, hoe beter de doelfunctiewaarde. De projectindicator µc beschrijft het gemiddelde competentieniveau. Zoals kan worden verwacht, resulteert een hoger gemiddeld competentieniveau in een hogere gemiddelde doelfunctiewaarde. Er zijn immers minder werknemers nodig om hetzelfde werk te verrichten. Tenslotte vertoont ook de projectindicator µS (gemiddelde sociale cohesie) een systematische impact. Sociale cohesie heeft een centrale rol in dit onderzoek, wat ook werd bevestigd in haar directe invloed op de doelfunctiewaarde (zie sectie 2.3.2). Ook hier heeft, zoals verwacht, een hogere gemiddelde sociale cohesie een positieve impact op de gemiddelde performantie van de metaheuristieken. Het belangrijkste resultaat van deze onderzoeksvraag komt echter naar voren als de sensitiviteit van de drie indicatoren met een systematische invloed wordt bekeken. Grafiek 28 toont zeer duidelijk dat de indicator I2 de grootste sensitiviteit en dus impact heeft. Dit betekent dat een verandering van I2 met 1% de grootste invloed heeft op de uiteindelijke doelfunctiewaarde. Ook de gemiddelde sociale cohesie heeft een erg grote sensitiviteit, al is deze iets kleiner dan die van I2. Tot slot valt uit de grafiek af te leiden dat het gemiddeld competentieniveau een veel kleinere impact heeft in vergelijking met de twee andere projectindicatoren. Merk hierbij op dat een projectmanager typisch weinig controle heeft over de I2-waarde aangezien deze sterk afhangt van de projectomgeving. Sociale cohesie en competentieniveau zijn daarentegen veel directere beslissingsvariabelen. Dit leidt tot een aantal interessante managementgerichte conclusies waarvoor wordt verwezen naar hoofdstuk 7.

99

Besluit Onderzoeksvraag 3 was gericht op het bepalen van de invloed van de projectindicatoren op de performantie van een metaheuristiek voor het beschouwde MOTCP. Hierbij werd naast aan de traditionele projectindicatoren ook aandacht geschonken aan de additionele projectindicatoren die voor deze onderzoeksetting werden opgesteld. ONDERZOEKSVRAAG 3: Wat is de impact van elke projectindicator op de totale doelfunctiewaarde?

De conclusies die werden getrokken uit deze analyse zijn: 

De projectindicatoren I2, µs en µc hebben in tegenstelling tot de andere indicatoren een systematische impact op de performantie van metaheuristieken voor het beschouwde MOTCP



Als de projectindicatoren I2, µs en µc een grotere waarde aannemen zal dit resulteren in een betere performantie van metaheuristieken voor het beschouwde MOTCP



De projectindicator I2 heeft de grootste invloed op de doelfunctiewaarde, gevolgd door µs en ten slotte µc.

Al deze conclusies worden samengevat in onderstaande grafiek.

Invloed van de projectindicatoren

Doelfunctiewaarde

8 7,5

7


6,5


6

I2

5,5 5 0%

20%

40%

60%

80%

100%

Relatieve parameterwaarden Grafiek 28 - Invloed van belangrijkste projectindicatoren

100

6.2.4 Onderzoeksvraag 4 ONDERZOEKSVRAAG 4: Wat is de impact van de projectindicator I2 op de deelobjectieven? Onderzoeksvraag 4 gaat dieper in op het thema van de deelobjectieven tijd, kosten en sociale cohesie als onderdelen van de totale doelfunctie. Omdat uit onderzoeksvragen 1, 2 en 3 blijkt dat I2 een belangrijke rol speelt in het MOTCP, wordt voor onderzoeksvraag 4 op deze projectindicator gefocust. Meer bepaald wordt de impact onderzocht van wijzigingen van I2 op elk van de drie deelobjectieven.

Methodologie Analoog met onderzoeksvragen 2 en 3 worden de simulaties voor onderzoeksvraag 4 uitgevoerd voor GA4 en SS3 uit onderzoeksvraag 1. Voor deze analyse worden de simulatieresultaten verwerkt voor de projectindicator I2 en opgesplitst voor de deelobjectieven tijd, kosten en sociale cohesie. Er wordt hierbij geen onderscheid gemaakt tussen de verschillende metaheuristieken. Onderstaand schema geeft een overzicht van de simulaties die worden uitgevoerd voor onderzoeksvraag 4, hoe deze worden verwerkt en welke analyse hieruit volgt. SIMULATIE GA4 SSGS [ENKEL OVER I2] SIMULATIE GA4 PSGS [ENKEL OVER I2] SIMULATIE SS3 SSGS [ENKEL OVER I2] SIMULATIE SS3 PSGS [ENKEL OVER I2]

VERWERKING Tijd VERWERKING Kosten VERWERKING Sociale Cohesie

ANALYSE Tijd vs. Kosten vs. Sociale Cohesie

Figuur 47 - Overzicht methodologie onderzoeksvraag 4

101

Resultaten De algemene impact van de projectindicator I2 werd reeds toegelicht bij onderzoeksvraag 3. Grafieken 29, 30 en 31 tonen aan hoe deze analyse kan omgevormd worden naar enerzijds de evolutie van de deelobjectieven afzonderlijk en anderzijds naar de contributie van de verschillende deelobjectieven tot de totale performantie van een metaheuristiek in functie van I2. Grafiek 29 toont de absolute doelfunctiewaarden voor de verschillende I2-waarden. Deze doelfunctiewaarden werden opgesplitst voor de verschillende deelobjectieven. Als de toppen van deze gestapelde kolommen met elkaar zouden worden verbonden, zou de gemiddelde performantie van de vier metaheurstieken worden bekomen. Deze figuur komt dan overeen met grafiek 28 uit onderzoeksvraag 3.

Absolute performantie

Absolute invloed van de projectindicator I2 op de performantie van de deelobjectieven 9,00 8,00 7,00 6,00 5,00 4,00 3,00 2,00 1,00 0,00

1,66 1,23

1,04 1,01

4,36

3,86

1,97

1,94

0,1

0,25

3,30

1,00

2,57

2,08

1,92

1,84

1,77

0,5

0,75

0,9

Parameterwaarden I2 Sociale Cohesie

Kosten

Tijd

Grafiek 29 - Invloed van I2 op de deelobjectieven

In grafiek 30 worden de gegevens uit grafiek 29 omgevormd zodat inzicht kan worden verkregen in de evolutie van de deelobjectieven voor de verschillende I2-waarden. Om deze analyse mogelijk te maken, werd elke waarde van een deelobjectief relatief uitgezet tegenover de waarde van dat deelobjectief als I2 = 0,1.

102

Evolutie van de performantie van een metaheuristiek op elk deelobjectief over de projectindicator I2 heen (met I2 = 0,1 → 100%) Performantie van een deelobjectief relatief t.o.v. de performantie bij I2 = 0,1

110% 100%

100%

100%

99%

100%

98% 94% 90%

89%

90% 80%

76%

74%

70% 63%

61%

60%

59%

48%

50% 40%

60%

0,1

0,25

0,5

0,75

0,9

Tijd

100%

74%

63%

61%

60%

Kosten

100%

89%

76%

59%

48%

Sociale Cohesie

100%

99%

98%

94%

90%

Parameterwaarden I2

Grafiek 30 - Performantie-evolutie van de deelobjectieven

Uit grafiek 30 kan worden afgeleid dat naarmate een project meer serieel wordt (i.e. I2 groter wordt), beter wordt gepresteerd op alle deelobjectieven. Voor het deelobjectief tijd is een progressief verloop zichtbaar. De verbeteringen zijn vooral merkbaar bij een lichte stijging van I2 in een sterk parallel project. De kosten verbeteren recht evenredig met de stijging van I2. Dit betekent dat de verbetering van een I2-stijging bij een sterk parallel project dezelfde is als bij een sterk serieel project. Het deelobjectief sociale cohesie lijkt in mindere mate beïnvloed te worden door I2 hoewel ook hier een verbetering valt waar te nemen. Deze verbetering is echter te beperkt om een trendverloop (recht evenredig, progressief, degressief...) waar te nemen. De reden voor deze drie evoluties wordt in de volgende paragrafen verklaard. Indien een eerder serieel project (hoge I2) wordt vergeleken met een eerder parallel project (lage I2), is dit eerste type project meest compatibel met een kleine groep werknemers. Het beschikbaar worden van activiteiten zal namelijk samenvallen met het beschikbaar worden van de meeste werknemers. Dit verhoogt de opportuniteiten om werknemers meerdere keren in te zetten tijdens eenzelfde project, wat de verbetering in het deelobjectief kosten verklaart. Een parallel project zal vaker geconfronteerd worden met meerdere activiteiten die op eenzelfde moment nood hebben aan resources. Dit verhoogt de kans dat een activiteit onvoldoende resources beschikbaar heeft op een bepaald ogenblik en moet worden uitgesteld. Een serieel project heeft een kleinere kans op een tekort aan werknemers en zal doorgaans dan ook beter presteren op het deelobjectief tijd. Dit nadeel van parallelliteit komt echter vooral bij extreem parallelle projecten terug.

103

Het deelobjectief sociale cohesie ondervindt een minder directe invloed van I2. De gevonden verbeteringen zijn echter indirect verbonden met het deelobjectief kosten. Bij een meer serieel project zullen minder werknemers worden geselecteerd, wat betekent dat er meer keuzevrijheid is bij de selectie. Er kan daarom meer rekening gehouden worden met sociale cohesie bij de selectie wat de verbeteringen, die worden gerealiseerd voor sociale cohesie bij een toenemende waarde voor I2, verklaart. In grafiek 31 wordt de informatie uit grafiek 29 opnieuw geïnterpreteerd door de evolutie van de contributie van de deelobjectieven tegenover de totale performantie over I2 te tonen. Hierbij wordt de contributie bij I2 = 0.1, net als in grafiek 30, gelijk gesteld aan 100%. Op die manier kan de evolutie van de contributie worden vergeleken. Evolutie van de contributie van de deelobjectieven over projectindicator I2 heen 175% 150% 125% 100% 75% 50% 25% 0,1

0,25

0,5

0,75

0,9

Parameterwaarden I2 Tijd

Kosten

Sociale Cohesie

Grafiek 31 - Evolutie van de contributie van de deelobjectieven

Om de relevantie van grafiek 31 aan te tonen, nodigen wij de lezer uit zich in de positie van een projectmanager te plaatsen. Voor elk project dient de projectmanager zijn aandacht te verdelen over verschillende managementactiviteiten. Hierbij is het belangrijk om te focussen op wat een grote impact heeft aangezien de manager niet genoeg tijd heeft om zich 100% te concentreren op alle activiteiten. De drie grote managementdomeinen die in dit opzicht kunnen worden onderscheiden zijn time-, cost- en qualitymanagement. Deze analyse laat toe te concluderen dat naarmate een project meer serieel is, de contributie van zowel tijd als kosten afneemt met een grotere contributie van sociale cohesie als gevolg. Voor een meer praktische interpretatie en toelichting bij deze redenering wordt verwezen naar de management implicaties die in hoofdstuk 7 worden besproken. 104

Besluit In onderzoeksvraag 4 werd geanalyseerd hoe de drie deelobjectieven in the beschouwde MOTCP beïnvloed worden door de serieel/parallel indicator I2. ONDERZOEKSVRAAG 4: Wat is de impact van de projectindicator I2 op de deelobjectieven? De conclusies die werden getrokken uit deze analyse zijn: 

Hoe groter de projectindicator I2 - en dus hoe meer serieel een project is - hoe beter de algemene performantie van metaheuristieken voor het beschouwde MOTCP



Zoals blijkt uit grafiek 32, ondergaan de verschillende deelobjectieven een verschillende evolutie. Om deze evolutie voor te stellen, werd elke waarde voor een bepaald deelobjectief uitgedrukt tegenover de waarde voor dit deelobjectief als I2 = 0,1. Als conclusie kan gesteld worden dat alle deelobjectieven dalen, maar in verschillende mate en volgens een verschillende trend. De kosten ondervinden de grootste invloed. Deze invloed is recht evenredig met de wijziging in I2. De impact van I2 op het deelobjectief tijd is iets beperkter, maar wel nog opvallend en kent een progressief verloop. Tenslotte is de impact op sociale cohesie bestaand maar beperkt, waardoor verder geen trend in deze evolutie waarneembaar is. Evolutie van de performantie van de deelobjectieven over projectindicator I2 heen 120%

100% 80% 60%

Tijd

40%

Kosten Sociale Cohesie

20%

0% 0,1

0,25

0,5

0,75

0,9

Parameterwaarden I2 Grafiek 32 - Evolutie van de performantie van de deelobjectieven over I2

105



Een derde en laatste conclusie volgt uit de evolutie van de contributie van de deelobjectieven. Hoe meer serieel een project is, hoe hoger de contributie van sociale cohesie op de totale performantie. Dit betekent dat het voor een projectmanager bij een hogere I2-waarde belangrijker is om te focussen op sociale cohesie. Evolutie van de contributie van de deelobjectieven over projectindicator I2 heen 175% 150% 125% 100% 75% 50% 25% 0,1

0,25

0,5

0,75

0,9

Parameterwaarden I2 Tijd

Kosten

Sociale Cohesie


106

HOOFDSTUK 7: MANAGEMENTCONCLUSIES In hoofdstuk 6 werden de resultaten van een simulatie besproken. Het doel van hoofdstuk 7 is om deze theoretische resultaten te vertalen naar toepasbare inzichten voor managers. Op die manier kan dit werk zowel gebruikt worden voor theoretici die meer inzicht willen krijgen in de implementatie en performantie van metaheuristieken en planningsmethodes, als voor managers die op zoek zijn naar praktische tips om het project scheduling- en teamselectieprobleem efficiënter aan te pakken. Projectmanagers kunnen gebruik maken van tal van softwaretools om projecten te schedulen (bijvoorbeeld ProTrack, Microsoft Project…). Daarin worden projectgegevens via geavanceerde rekenmodellen omgezet in een planning voor activiteiten en resources. Deze planning vormt echter veelal slechts een startpunt voor de projectmanager. In een tweede fase moet deze immers vertaald worden naar de praktische setting. De resultaten van het gevoerde onderzoek in hoofdstuk 6 kunnen worden herleid tot enkele inzichten die de projectmanager kan gebruiken in deze fase. Hierbij blijven de softwaretools nuttig, aangezien zij toelaten de projectgegevens te kwantificeren. Deze gegevens kunnen dan helpen bij het schedulen en managen van projecten.

MANAGEMENT IMPLICATIES I.V.M. ALGEMENE PERFORMANTIE VAN METAHEURISTIEKEN De metaheuristieken die in deze studie aan bod kwamen, zijn erg gelijkaardig aan het beslissingsproces dat een projectmanager in de praktijk doormaakt bij het plannen van een project en het toewijzen van werknemers hieraan. Om de parallellen te leggen tussen een metaheuristiek enerzijds en een beslissingsproces anderzijds, wordt een brainstormsessie als voorbeeld genomen. Net als bij een brainstorm vertrekt een metaheuristiek van een probleemstelling, in dit geval het MOTCP. Het doel van een brainstormsessie is het overlopen en evalueren van mogelijke oplossingen voor het probleem om zo de beste oplossing te vinden. In de metaheuristiek is zo een mogelijke oplossing een koppel van prioriteitsregels dat geëvalueerd wordt op basis van een doelfunctie. Om de link te leggen tussen de performantie van metaheuristieken enerzijds en de performantie van beslissingsprocessen anderzijds, wordt verwezen naar de concepten intensificatie en diversificatie in de context van metaheuristieken. In het voorbeeld van de brainstormsessie kan diversificatie gezien worden als "out of the box"-thinking. Oplossingssuggesties voor een probleem zijn enorm uiteenlopend en worden individueel geëvalueerd. Bij intensificatie bouwen de oplossingssuggesties daarentegen verder op reeds bestaande oplossingen en worden individuele suggesties gecombineerd om tot een betere oplossing te komen. Voor zowel intensificatie als diversificatie zijn argumenten pro en contra te vinden. Veel hangt echter af van het 107

omliggend kader. Zo zal een beslissingsproces over het oplossen van het global warming probleem hoogstwaarschijnlijk beter af zijn met out of the box thinking en dus diversificatie. Voor het zoeken van oplossingen voor het verhogen van de capaciteit van een machine wordt daarentegen beter verder gebouwd op bestaande praktijken, intensificatie dus. Uit de analyse van de metaheuristieken voor het MOTCP bleek dat dit beslissingsproces voornamelijk voordelen haalt uit intensificatie. Bij de verbeteringsstappen die van een algemene implementatievorm (GA1 en SS1) naar een meer intelligente implementatievorm (GA4 en SS3) overgingen, werd steeds geopteerd voor methodes die bijdragen tot intensificatie in tegenstelling tot diversificatie. Het belang van intensificatie voor het MOTCP betekent voor de projectmanager dat het essentieel is om zoveel mogelijk en zo kwalitatief mogelijke informatie te genereren over het project, de activiteiten en de werknemers. Die informatie moet de drijvende kracht zijn achter selectie- en planningsbeslissingen. Het is van groot belang om via allerlei technieken een project te evalueren om op die manier verbetermogelijkheden te ontdekken. Door te leren uit fouten uit het verleden, kan de performantie van projecten sterk verbeteren. Een mogelijke manier om projecten te evalueren, is door het ondervragen van werknemers. Zij ervaren zelf wat goed of fout loopt en wat eventueelmoet worden bijgestuurd. Vaak is het algemeen overzicht van de manager nodig om oplossingen te genereren, maar het is belangrijk dat deze beseft welke problemen op de werkvloer voorkomen. In de geschetste setting is informatie over de persoonlijkheden van en relaties tussen de werknemers van groot belang. In het beschreven MOTCP vertalen deze persoonlijkheidseigenschappen en relaties zich in de sociale cohesie tussen werknemers. Doordat intensificatie zo belangrijk is in het MOTCP, is het voor een projectmanager belangrijk dat deze informatie compleet en up-to-date is. Degradatie van de informatiekwaliteit staat namelijk rechtstreeks in verband met eventueel kwaliteitsverlies voor het project. Een goede techniek om de persoonlijkheid van mensen in kaart te brengen, is de Myers-Briggs Type Indicator (MBTI) (Myers, 1962). Deze classificatie tool probeert het karakter van iemand te beschrijven op basis van de vier onderstaande dimensies. 1. Extravert versus introvert 2. Waarnemend versus intuïtief 3. Logisch versus emotioneel 4. Planmatig versus spontaan

108

Op basis van deze informatie kunnen afspraken gemaakt worden binnen een team over de manier van onderlinge samenwerking. Een projectmanager die deze informatie bezit zal zijn team kunnen samenstellen op basis van enorm interessante inzichten.

MANAGEMENT IMPLICATIES I.V.M. INVLOED VAN PROJECT TYPES Grafiek 28 vat kort de resultaten van onderzoeksvraag 3 samen waar de impact van de serieel/parallel-indicator I2, de gemiddelde sociale cohesie µs en het gemiddeld competentieniveau µc onderzocht werd. De algemene conclusie die uit deze figuur werd getrokken, is dat wanneer de drie indicatoren een grotere waarde aannemen, de performantie van het schedulen verbetert. Hierbij heeft I2 de grootste impact, gevolgd door de gemiddelde sociale cohesie en het gemiddeld competentieniveau. Invloed van de projectindicatoren

Doelfunctiewaarde

8 7,5 7 6,5 6 5,5 5 0%

20%

40%

60%

80%

100%

Relatieve parameterwaarden Gemiddelde sociale cohesie

Gemiddeld comp niv

I2

Grafiek 28 - Invloed van belangrijkste projectindicatoren

De eerste conclusie die hieruit kan worden getrokken heeft te maken met project control. Op de figuur staat de sensitiviteit af te lezen van de verschillende parameters. Als projectmanager is het belangrijk inzicht te hebben in de factoren die een grote impact kunnen hebben op de afloop van het project om bij het project op de juiste zaken te focussen. Op I2 heeft de manager vaak weinig impact omdat dit vaak sterk gedetermineerd wordt door het type business waarin wordt geopereerd. Daarom gaat de aandacht hier vooral uit naar de gemiddelde sociale cohesie en het gemiddelde competentieniveau van de werknemers. Hoewel beiden hun invloed hebben, is het duidelijk dat gemiddelde sociale cohesie in de beschouwde MOTCP omgeving een grote impact heeft op de performantie van project scheduling. De projectmanager dient dus vooral te focussen op het behoud of de verbetering van de gemiddelde sociale cohesie, eerder dan op het gemiddeld competentieniveau. Een kleine wijziging in sociale cohesie heeft namelijk een veel 109

grotere impact op de totale projectperformantie dan een even grote wijziging in competentieniveau. Dit betekent niet dat het competentieniveau uit het oog mag worden verloren. Dit is en blijft belangrijk, maar heeft in het kader waarin deze studie plaatsvindt minder impact dan sociale cohesie. Een tweede belangrijke conclusie die uit deze onderzoeksvraag kan worden getrokken, is van toepassing op het rekruteringsproces. Hier kan geconcludeerd worden dat, eens een acceptabel competentieniveau is bereikt, sociale cohesie een prioritaire rol moet spelen bij de selectieprocedure van nieuwe werknemers. In dit geval speelt een culturele match met het bedrijf en een sociale match met de collega’s een prominente rol.

MANAGEMENT IMPLICATIES I.V.M. DE CONTRIBUTIE VAN DEELOBJECTIEVEN De contributie van een deelobjectief kan worden geïnterpreteerd als de prioriteit die de projectmanager dient toe te wijzen aan het overeenkomstige managementdomein. Grafiek 31 toont nogmaals de contributie van elk deelobjectief voor de verschillende I2-waarden. Evolutie van de contributie van de deelobjectieven over projectindicator I2 heen 175% 150% 125% 100% 75%

50% 25% 0,1

0,25

Tijd

0,5 Parameterwaarden I2 Kosten

0,75

0,9

Sociale Cohesie


Bij een serieel project volgen de activiteiten elkaar eerder sequentieel op terwijl bij een parallel project activiteiten vooral gelijktijdig worden uitgevoerd. Ongeacht het type project waarmee een projectmanager wordt geconfronteerd, dient deze zijn aandacht te verdelen over een reeks

110

managementactiviteiten. Tabel 32 geeft een overzicht van drie fundamentele managementdomeinen en een paar voorbeelden van activiteiten die tot elk domein behoren. Tabel 32 - Overzicht van time, cost en quality management

TIME MANAGEMENT ACTIVITEITEN Bv. SMED Systematisch reduceren van set-up en overgangsprocessen

COST MANAGMENT ACTIVITEITEN Bv. Mentorship program Constante evaluatie en feedback naar werknemers toe

QUALITY MANAGEMENT ACTIVITEITEN Bv. Teammeetings Periodieke opvolging van wat er leeft in de groep (proactief)

Bv. 5S Orde en netheid op de werkplek om zo efficiënt mogelijk te werken

Bv. Cross-training Waarde per werknemer verhogen door het uitbreiden van zijn vaardigheden

Bv. Conflictbehandeling Opmerken en aanpakken van eventuele spanningen of problemen in de groep (reactief)

BUDGETTERING Bv. Interim budget Door budget voor te behouden voor interim werkkrachten wordt vermeden dat er uiteindelijk een nog grotere kost resulteert uit het niet halen van de deadline

BUDGETTERING Bv. Time penalty budget Door budget voor te behouden voor het niet halen van de deadline wordt vermeden dat er uiteindelijk een nog grotere kost resulteert uit het inzetten van te veel werknemers

BUDGETTERING Bv. Teambuilding budget Door budget voor te behouden voor teambuilding activiteiten tussen werknemers, zal de sociale cohesie tussen de werknemers groeien. Dit resulteert in een betere projectkwaliteit

Het is duidelijk dat deze managementdomeinen samenvallen met de deelobjectieven die werden beschouwd in het MOTCP. Een projectmanager zal weinig kunnen veranderen aan het type project waarmee hij wordt geconfronteerd in termen van serialiteit of parallelliteit. Wat hij echter wel kan doen, is analyseren wat de typische probleemdomeinen zijn, gegeven de projectomgeving. Het is deze analyse die wordt ondersteund door de simulatieresultaten in verband met de deelobjectieven. Hoe meer serieel de projectomgeving is waarin een projectmanager zich bevindt, hoe meer het project "uit zichzelf" beter presteert op vlak van personeelskosten en behalen van de deadline. De kwaliteit van het project wordt echter bepaald door de mate waarin de teamleden zich goed voelen in de groep en zich gestimuleerd voelen om zich 100% in te zetten voor het bereiken van teamobjectieven. Dit gegeven groeit aan belang eens men te maken heeft met een meer serieel project. Meer aandacht zou dan ook besteed moeten worden aan quality management activiteiten in dit type projecten.

111

ALGEMENE CONCLUSIE EN VERDER ONDERZOEK Om dit werk te besluiten, worden nog een aantal conclusies getrokken en een aantal mogelijk opties voor verder onderzoek aangereikt. De conclusies zullen worden onderverdeeld in academische en praktische conclusies. Hoewel deze deels overlappen en zeker niet los van elkaar kunnen worden gezien, werd voor deze indeling gekozen omdat de lezer op die manier de voor hem relevante onderdelen kan lezen.

ACADEMISCHE CONCLUSIES Het doel van deze thesis was het onderzoeken van verschillende werknemersselectie-, plannings- en schedulingmethodes, toegepast op het Multi-Objectieve Team Composition Problem (MOTCP). Uiteindelijk werd gekozen om vier verschillende methodes te vergelijken. Deze worden in onderstaande figuur voorgesteld.

Figuur 48 - Overzicht van de vier metaheuristieken

Voor deze vier metaheuristieken werd een simulatie uitgevoerd op een reeks van voorbeeldprojecten die werden gestructureerd aan de hand van negen projectindicatoren: I2, I3, I4, I5, I6, µc, µs, CVc en CVs

112

Op basis van deze simulaties werden volgende conclusies getrokken: 

De specifieke invulling van Genetic Algorithm en Scatter Search heeft een grote impact op de performantie van het algoritme. Voor beide methodes werd aangetoond dat het toevoegen van intelligentie een positieve impact heeft op de uiteindelijke resultaten. Met het toevoegen van intelligentie wordt bedoeld dat meer informatie die inherent in het algoritme zit verweven, wordt gebruikt in de verschillende stappen. In deze specifieke probleemsetting werd deze intelligentietoevoeging gebruikt voor vergroting van de intensificatie. Voor de onderzochte probleemsetting leidt een grotere focus op intensificatie tot betere resultaten in vergelijking met diversificatie. Echter, de metaheuristieken domineren nog steeds een gewone local search, wat hun relevantie bewijst.



De twee metaheuristieken (GA en SS) werden met elkaar vergeleken in een ruwe, weinig intelligente vorm enerzijds en in een probleemspecifieke, intelligente vorm anderzijds. Als conclusie kan hier worden gesteld dat in de ruwe vorm Scatter Search Genetic Algorithm domineert, terwijl in de intelligente vorm beide metaheuristieken gelijkaardig presteren.



Verder werden ook de twee Schedule Generation Schemes vergeleken (SSGS en PSGS). Uit dit onderzoek kon worden geconcludeerd dat in bijna alle gevallen SSGS PSGS domineert. Een reden die hiervoor werd geïdentificeerd is dat in een omgeving wordt gewerkt waar resources relatief goed beschikbaar zijn en SSGS beter presteert in een dergelijke omgeving. Daarnaast bleek dat voor de projectindicator I2 de preferentie van SSGS tegenover PSGS verkleint naarmate de indicator grotere waarden aanneemt en het project dus meer serieel is.



De impact van een groot aantal projectindicatoren werd geanalyseerd in onderzoeksvraag 3 voor het gemiddelde van alle metaheuristieken. Dit onderzoek resulteerde in de conclusie dat heel wat indicatoren geen directe invloed hebben op de performantie van de metaheuristieken (I3, I4, I5, I6, CVC en CVS). Voor drie parameters was echter een duidelijke invloed zichtbaar. Voor I2,

en

werd geconcludeerd dat een grotere parameterwaarde resulteerde in een beter performantie van het algoritme. Hierbij was de impact van I2 dominant, gevolgd door respectievelijk µs en µc. 

Tot slot werd de invloed van I2 onderzocht op de verschillende deelobjectieven (tijd, kosten en sociale cohesie). Hier gold als algemene conclusie dat in absolute termen alle deelobjectieven verbeteren naarmate I2 groter wordt. Echter, uit een vergelijking van de relatieve verbetering van de deelobjectieven bleek dat tijd en kosten relatief gezien meer verbeteren dan sociale cohesie. 113

PRAKTISCHE/MANAGERIAL CONCLUSIES Op basis van de hierboven geschetste academische conclusies kunnen ook een aantal inzichten die in de praktijk kunnen toegepast worden naar voren worden gebracht. 

De rol van intensificatie heeft een grote impact op het werk van een projectmanager. Het is namelijk essentieel zoveel mogelijk projectgerelateerde informatie te genereren en deze informatie zo goed mogelijk te gebruiken bij het verbeteren van selectiemethodes en bij het samenstellen van teams in de toekomst. Als voorbeeld hiervan werd de MBTI-indicator naar voren geschoven omdat deze de sociale factor die centraal staat in dit werk, beschrijft en de manager kan helpen bij het selecteren van teamleden die goed bij elkaar passen.



De verschillende impact van sociale cohesie en competentieniveau leiden tot de conclusie dat een projectmanager tijdens het project vooral moet focussen op sociale cohesie. Een verandering in het gemiddelde sociale cohesie-niveau heeft immers een grotere impact dan een verandering in het competentieniveau. Het 80/20-principe vertelt dat het belangrijk is om te focussen op wat echt belangrijk is, sociale cohesie dus in de hier beschreven setting.



Het verschil tussen de invloed van sociale cohesie en van competentieniveau heeft ook een invloed op rekruteringsbeslissingen, waarbij ook hier het belang van sociale cohesie niet buiten beschouwing mag worden gelaten. HR managers moeten ervoor zorgen dat new joiners niet alleen competent zijn, maar ook binnen de groep passen.



Uit de conclusie van de deelobjectieven bleek dat het relatieve belang van sociale cohesie vergroot naarmate het project meer serieel wordt. Dit betekent dat een manager meer aandacht moet schenken aan sociale cohesie in een serieel dan in een parallel project.

VERDER ONDERZOEK De gevoerde studie is, zoals steeds bij een onderzoek, gelimiteerd in scope waarbij de belangrijkste assumpties zijn samengevat in bijlage 1. Het lijkt de auteurs interessant om de relevantie van de getrokken conclusies te valideren in een multi-skilled omgeving met een meer gedetailleerde benadering van de personeelskosten. Een eerste aanzet tot de C++-implementatie voor het multi-skilled MOTCP werd hiervoor reeds geprogrammeerd door de auteurs en kan worden opgevraagd. Bovendien kunnen projecttypes ook verder gespecifieerd worden door een cross-analyse over de projectindicatoren uit te voeren. 114

LIJST VAN GERAADPLEEGDE WERKEN Artigues, C., Lopez, P., & Ayache, P. D. (2005). Schedule generation schemes for the job-shop problem with sequence-dependent setup times: dominance properties and computational analysis. Annals of Operations Research, 138(1), 21-52.

Ballesteros-Pérez, P., González-Cruz, M. C., & Fernández-Diego, M. (2012). Human resource allocation management in multiple projects using sociometric techniques. International Journal of Project Management, 30(8), 901-913.

Beal, D. J., Cohen, R. R., Burke, M. J., & McLendon, C. L. (2003). Cohesion and performance in groups: a meta-analytic clarification of construct relations. Journal of Applied Psychology, 88(6), 989.

Bex, G.J. (2001). Genetische Algoritmen. (Available from Hasselt University WNI Department, Agoralaan, buidling D B-3590, Diepenbeek Belgium).

Blackstone, J. H., Phillips, D. T., & Hogg, G. L. (1982). A state-of-the-art survey of dispatching rules for manufacturing job shop operations. The International Journal of Production Research, 20(1), 27-45.

Blazewicz, J., Lenstra, J. K., & Kan, A. H. G. (1983). Scheduling subject to resource constraints: classification and complexity. Discrete Applied Mathematics, 5(1), 11-24.

Brucker, P., Drexl, A., Möhring, R., Neumann, K., & Pesch, E. (1999). Resource-constrained project scheduling: Notation, classification, models, and methods. European journal of operational research, 112(1), 3-41.

Busetti, F. (2007). Genetic algorithms overview. Retrieved on December, 1.

Chang, C. K., Christensen, M. J., & Zhang, T. (2001). Genetic algorithms for project management. Annals of Software Engineering, 11(1), 107-139.

Cooper, D. F. (1976). Heuristics for scheduling resource-constrained projects: An experimental investigation. Management Science, 22(11), 1186-1194. 115

Demeulemeester, E., Vanhoucke, M., & Herroelen, W. (2003). RanGen: A random network generator for activity-on-the-node networks. Journal of Scheduling, 6(1), 17-38.

Darwin, C. (1860). The preservation of favored races in the struggle for life. New York: D. Appleton.

Elmaghraby, S. E. (1977). Activity networks: Project planning and control by network models (pp. 228313). New York: Wiley.

Elmaghraby, S. E. (1995). Activity nets: A guided tour through some recent developments. European Journal of Operational Research, 82(3), 383-408.

Globerson, S. (1994). Impact of various work-breakdown structures on project conceptualization. International Journal of Project Management, 12(3), 165-171.

Glover, F., Laguna, M., & Martí, R. (2003). Scatter search. In Advances in evolutionary computing (pp. 519-537). Springer Berlin Heidelberg.

Goldberg, D. E., & Deb, K. (1991). A comparative analysis of selection schemes used in genetic algorithms. Urbana, 51, 61801-2996.

Guzzo, R. A., & Shea, G. P. (1992). Group performance and intergroup relations in organizations. Handbook of industrial and organizational psychology, 3, 269-313.

Hartmann, S. (1998). A competitive genetic algorithm for resource‐constrained project scheduling. Naval Research Logistics (NRL), 45(7), 733-750.

Hartmann, S., & Briskorn, D. (2010). A survey of variants and extensions of the resource-constrained project scheduling problem. European Journal of Operational Research, 207(1), 1-14.

Helfert, G. (1998). Teams im Relationship-Marketing. Wiesbaden: Gabler.

116

Herroelen, W., De Reyck, B., & Demeulemeester, E. (1998). Resource-constrained project scheduling: a survey of recent developments. Computers & Operations Research, 25(4), 279-302.

Higgs, M., Plewnia, U., & Ploch, J. (2005). Influence of team composition and task complexity on team performance. Team Performance Management, 11(7/8), 227-250. Holland, J. H. (1975). Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence. U Michigan Press.

Hopp, W. J., & Spearman, M. L. (2011). Factory physics, 252. Waveland Press.

Icmeli, O., Erenguc, S. S., & Zappe, C. J. (1993). Project scheduling problems: a survey. International Journal of Operations & Production Management, 13(11), 80-91.

Jackson, S. E. (1991). Team composition in organizational settings: Issues in managing an increasingly diverse work force. In Symposium on Group Productivity and Process, 1989, Texas A & MU, College Station, TX, US. Sage Publications, Inc.

Klein, R. (2000). Bidirectional planning: improving priority rule-based heuristics for scheduling resource-constrained projects. European Journal of Operational Research, 127(3), 619-638.

Kolisch, R. (1996). Efficient priority rules for the resource-constrained project scheduling problem. Journal of Operations Management, 14(3), 179-192.

Kolisch, R. (1996). Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation. European Journal of Operational Research, 90(2), 320-333.

Kolisch, R. (2000). Integrated scheduling, assembly area-and part-assignment for large-scale, make-toorder assemblies. International Journal of Production Economics, 64(1), 127-141.

Kolisch, R., & Hartmann, S. (2006). Experimental investigation of heuristics for resource-constrained project scheduling: An update. European Journal of Operational Research, 174(1), 23-37.

117

Lechler, T. (2001). Social interaction: A determinant of entrepreneurial team venture success. Small Business Economics, 16(4), 263-278.

Mathieu, J. E., Tannenbaum, S. I., Donsbach, J. S., & Alliger, G. M. 2013. Achieving optimal team composition for success. Developing and enhancing high-performance teams: Evidence-based practices and advice, 520-551. San Francisco: Jossey-Bass. Mullen, B., & Copper, C. (1994). The relation between group cohesiveness and performance: An integration. Psychological bulletin, 115(2), 210. Myers, I. B. (1962). The myers-briggs type indicator (pp. 1-5). Palo Alto, CA: Consulting Psychologists Press.

Neumann, K., Schwindt, C., & Zimmermann, J. (2003). Project scheduling with time windows and scarce resources: temporal and resource-constrained project scheduling with regular and nonregular objective functions. Springer.

Oliveri, G., & Massa, A. (2011). Genetic algorithm (GA)-enhanced almost difference set (ADS)-based approach for array thinning. IET Microwaves, Antennas & Propagation, 5(3), 305-315.

Oral, M., & Malouin, J. L. (1973). Evaluation of the shortest processing time scheduling rule with truncation process. AIIE Transactions, 5(4), 357-365.

Osman, I. H., & Kelly, J. P. (1996). Meta-heuristics: an overview. In Meta-Heuristics (pp. 1-21). Springer US.

Özdamar, L., & Ulusoy, G. (1995). A survey on the resource-constrained project scheduling problem. IIE transactions, 27(5), 574-586.

Pinnell S., Busch J. (1993). How do you measure the quality of your project management? PM Network, December: 35-36.

118

Summers, I., Coffelt, T., & Horton, R. E. (1988). Work-group cohesion. Psychological Reports, 63(2), 627-636.

Spears, W. M., & De Jong, K. A. (1990). An analysis of multi-point crossover. NAVAL RESEARCH LAB WASHINGTON DC.

Taha, H. A. (2007). Operations research: an introduction (pp. 490-7). Pearson/Prentice Hall.

Tavares, L. V., Antunes Ferreira, J., & Silva Coelho, J. (1999). The risk of delay of a project in terms of the morphology of its network. European Journal of Operational Research, 119(2), 510-537.

Van den Bergh, J., Beliën, J., De Bruecker, P., Demeulemeester, E., & De Boeck, L. (2013). Personnel scheduling: A literature review. European Journal of Operational Research, 226(3), 367-385.

Vanhoucke, M. (2012). Project Management with dynamic scheduling. Berlin: Springer.

Vanhoucke, M., Coelho, J., Debels, D., Maenhout, B., & Tavares, L. V. (2008). An evaluation of the adequacy of project network generators with systematically sampled networks. European Journal of Operational Research, 187(2), 511-524.

Vanhoucke, M., Demeulemeester, E., & Herroelen, W. (2001). An exact procedure for the resourceconstrained weighted earliness–tardiness project scheduling problem. Annals of Operations Research, 102(1-4), 179-196.

Van Peteghem, V., & Vanhoucke, M. (2011). Using resource scarceness characteristics to solve the multi-mode resource-constrained project scheduling problem. Journal of Heuristics, 17(6), 705-728.

Yamashita, D. S., Armentano, V. A., & Laguna, M. (2007). Robust optimization models for project scheduling with resource availability cost. Journal of Scheduling, 10(1), 67-76.

119

BIJLAGE 1: ASSUMPTIES I.V.M. DE PROBLEEMSETTING Het MOTCP beschrijft het algemene probleem van teamsamenstelling in project scheduling waarbij rekening moet gehouden worden met meerdere objectieven. Voor het analyseren en onderzoeken van dit probleem dient echter in zekere mate abstractie gemaakt te worden van de realiteit om zo het eindobjectief van deze studie niet uit het oog te verliezen. Hieronder worden de fundamentele veronderstellingen overlopen die een invulling geven aan enkele aspecten binnen het MOTCP. Enkele van hen hebben betrekking op het Team Composition Problem, andere op Multi-Objective Optimization. TEAM COMPOSITION PROBLEM 1. Er worden in totaal vier verschillende vaardigheden/resources types beschouwd 2. Elke werknemer bezit juist één vaardigheid (single-skilled omgeving) 3. Voor elk vaardigheidstype bestaan drie competentieniveaus 4. Competentieniveaus zijn cumulatief 5. Elke werknemer kan op elk tijdstip slechts voor één activiteit worden ingezet (geen multi-tasking) 6. Eens een activiteit is gestart, wordt deze niet meer onderbroken (geen activity preemption) 7. Eens een werknemer aan een activiteit start, werkt hij deze volledig af (geen werknemer preemption) MULTI-OBJECTIVE OPTIMIZATION 8. Er worden drie objectieven onderscheiden: tijd, kosten en sociale cohesie 9. Werknemers worden betaald gedurende de volledige projectduur ongeacht de tijd die ze effectief besteden aan activiteiten. Bovendien is de personeelskost per werknemer dezelfde 10. Sociale cohesie is een inputparameter gedefinieerd voor elk koppel van werknemers als een getal tussen 0 en 100

Bijlage 1-1

BIJLAGE 2: ONDERSTEUNENDE DEFINITIES VOOR TOPOLOGISCHE NETWERKINDICATOREN

Een belangrijk concept in het beschrijven van de topologie van een netwerk is het hiërarchische level. Dit is een kenmerk van elke activiteit die de relatieve positie van de activiteit in een projectnetwerk beschrijft. Dit wordt verder gespecificeerd door het progressieve level enerzijds en het regressieve level anderzijds. Het eerste verwijst naar de relatieve positie van een activiteit ten opzichte van het begin van het netwerk en het tweede naar de relatieve positie van een activiteit ten opzichte van het einde van het netwerk (Elmaghraby, 1977). In wat volgt worden de berekeningen achter beide concepten kort toegelicht en geïllustreerd aan de hand van onderstaand voorbeeldproject.

Figuur 49 - Voorbeeld hiërarchische levels (AoN-netwerk)

Het progressieve level PLi van een activiteit verwijst naar de relatieve positie van een activiteit i ten opzichte van het begin van het netwerk. De formule voor PLi wordt hieronder weergegeven. Hierbij is Pi de verzameling van activiteiten die activiteit i rechtstreeks voorafgaan. Merk op dat wanneer deze verzameling leeg is, het progressieve level gelijk is aan 1. PLi = { Het regressieve level RLi van een activiteit verwijst naar de relatieve positie van een activiteit i ten opzichte van het einde van het netwerk. De formule voor RLi wordt hieronder weergegeven. Hierbij is Si de verzameling van activiteiten die activiteit i rechtstreeks opvolgen. Merk op dat wanneer deze verzameling Bijlage 2-1

leeg is, het regressieve level gegeven wordt door het maximale progressieve level aangeduid met de letter m. RLi = { met m =

Om bovenstaande concepten te verduidelijken wordt een overzicht gegeven van de progressieve en regressieve levels van de activiteiten in het beschouwde voorbeeldproject. Merk hierbij op dat de start dummy activiteit nooit wordt beschouwd als onderdeel van Pi zodat deze activiteit een progressief level 0 krijgt toegewezen.

Figuur 50 - Voorbeeld hiërarchische levels (progressief en regressief level)

Bijlage 2-2

BIJLAGE 3: PRE-SIMULATIE De uiteindelijke resultaten van de simulatie moeten worden geïnterpreteerd in functie van de beslissingen die het omliggende kader ervan bepalen. In deze studie wordt het omliggende kader voornamelijk bepaald door de metaheuristieken zelf en hun implementatie. Bij het onderzoeksdeel van onderzoeksvraag 1 worden voor zowel GA als SS enkele van deze implementaties toegelicht. Bij bepaalde implementaties worden echter methodes geïntroduceerd waarvan de werking (i.e. efficiëntie en effectiviteit) afhangt van één of meerdere parameters. Tabel 33 geeft een overzicht van de parameters die bij een bepaalde implementatievorm van beide metaheuristieken worden geïntroduceerd. De eigenlijke betekenis van elke parameter wordt in het onderzoek zelf toegelicht bij de desbetreffende implementatie. Tabel 33 - Metaheuristiek gerelateerde pre-simulatie parameters

SCATTER SEARCH

GENETIC ALGORITHM GA1

GA4

Parameter

Omschrijving

Par5

# leden per subset

Mutation rate (%)

Par6

# te analyseren buren (%) in local search Maximum # local search iteraties

Par7


Parameter

Omschrijving

Par1

Cross-over rate (%)

Par2 Par3 Par4

SS1

Daarnaast zijn er ook een aantal parameters die niet zo zeer met de implementatie van een metaheuristiek zelf te maken hebben, maar eerder met de keuzes omtrent de scope van het probleem en het onderzoek. In Tabel 34 wordt weergegeven dat voor de probleemsetting enerzijds een keuze moet worden gemaakt over het aantal werknemers dat maximaal beschikbaar zal zijn voor een project. Anderzijds moet worden beslist welk stopcriterium wordt gebruikt. Tabel 34 - Algemene pre-simulatie parameters

ALGEMEEN Parameter

Omschrijving

# wkn

# beschikbare werknemers

Stopcriterium

Max # gegenereerde schedules

Bijlage 3-1

Om aan alle hierboven beschreven parameters een waarde toe te kennen, wordt hun kwaliteit getest aan de hand van een verkennend onderzoek. Dit komt neer op een simulatie met dit verschil dat de scope een stuk beperkter is dan de uiteindelijke simulatie die verder wordt beschreven. In het vervolg wordt naar dit onderzoek verwezen met de term pre-simulatie. In wat volgt wordt verder ingegaan op de pre-simulaties die plaatsvonden voor beide metaheuristieken. Eerst wordt de dataset van projecten besproken waarop deze pre-simulaties werden uitgevoerd. Vervolgens worden voor zowel GA als SS de uitgevoerde presimulaties besproken.

Bijlage 3-2

BIJLAGE 3.1: ALGEMENE BESCHRIJVING VAN EEN PRE-SIMULATIE Zoals reeds werd aangehaald, is het doel van een pre-simulatie aan bepaalde parameters in de metaheuristieken een specifieke waarde toe te kennen. Hiervoor wordt gebruikt gemaakt van een tweevoudige iteratie van sequentiële optimalisaties. Figuur 51 toont voor een voorbeeld met drie parameters hoe een iteratie van sequentiële optimalisaties verloopt. Eerst wordt parameterwaarde 1 geoptimaliseerd, terwijl parameterwaarden 2 en 3 worden vastgezet op hun initiële waarden. Vervolgens wordt parameter 2 geoptimaliseerd, waarbij parameterwaarde 1 nu de geoptimaliseerde waarde krijgt toegewezen uit de eerste stap terwijl parameter 3 nog steeds op zijn initiële waarde staat. Tenslotte wordt in een volgende stap parameterwaarde 3 geoptimaliseerd op basis van de geoptimaliseerde waarden voor parameter 1 en 2. Deze iteratie wordt hierna nogmaals herhaald met als verschil dat de parameters nu worden geïnitialiseerd op hun optimale waarde uit de eerste iteratie.

Figuur 51 – Voorbeeld pre-simulatie (tweevoudig iteratie van sequentiële optimalisaties)

Voor deze pre-simulatie wordt een testset van 60 voorbeeldprojecten gebruikt die worden gespecificeerd aan de hand van een beperkt aantal projectindicatoren. Zo wordt er gebruik gemaakt van één activiteitsgerelateerde projectindicator (I2) en twee werknemersgerelateerde projectindicatoren (gemiddeld competentieniveau en gemiddelde sociale cohesie). Er wordt gekozen voor deze drie indicatoren omdat deze in grote lijnen de belangrijkste zaken van het MOTCP beschrijven: activiteiten (I2), resources (µc) en sociale cohesie (µs). Naast de selectie van projectindicatoren, wordt ook besloten om een beperkt aantal waarden te beschouwen voor elke projectindicator. De combinatie van vijf waarden voor I2, vier waarden voor μs en met drie waarden voor μc resulteert in 60 projecten. Voor een overzicht van deze projecten wordt verwezen naar tabel 35. I2

{0.1, 0.25, 0.5, 0.75 , 0.9}

μs

{10, 33.33, 66.67, 90}

μc

{1.33, 2, 2.66 }

Bijlage 3-3

Tabel 35 - Overzicht projecten pre-simulatie

Nr.

I2

μs

μC

Nr.

I2

μs

μC

1

0.10

10.00

1.33

31

0.50

66.67

1.33

2

0.10

10.00

2.00

32

0.50

66.67

2.00

3

0.10

10.00

2.66

33

0.50

66.67

2.66

4

0.10

33.33

1.33

34

0.50

90.00

1.33

5

0.10

33.33

2.00

35

0.50

90.00

2.00

6

0.10

33.33

2.66

36

2.66

7

0.10

66.67

1.33

37

0.50 0.75

90.00 10.00

1.33

8

0.10

66.67

2.00

38

0.75

10.00

2.00

0.75

10.00

2.66

9

0.10

66.67

2.66

39

10

0.10

90.00

1.33

40

0.75

33.33

1.33

0.75

33.33

2.00

11

0.10

90.00

2.00

41

12

0.10

90.00

2.66

42

0.75

33.33

2.66

10.00

1.33

43

0.75

66.67

1.33

0.75

66.67

2.00

13

0.25

14

0.25

10.00

2.00

44

15

0.25

10.00

2.66

45

0.75

66.67

2.66

16

0.25

33.33

1.33

46

0.75

90.00

1.33

0.75

90.00

2.00

17

0.25

33.33

2.00

47

18

0.25

33.33

2.66

48

0.75

90.00

2.66

19

0.25

66.67

1.33

49

0.90

10.00

1.33

0.90

10.00

2.00

20

0.25

66.67

2.00

50

21

0.25

66.67

2.66

51

0.90

10.00

2.66

0.90

33.33

1.33

22

0.25

90.00

1.33

52

23

0.25

90.00

2.00

53

0.90

33.33

2.00

24

0.25

90.00

2.66

54

0.90

33.33

2.66

10.00

1.33

55

0.90

66.67

1.33

25

0.50

26

0.50

10.00

2.00

56

0.90

66.67

2.00

27

0.50

10.00

2.66

57

0.90

66.67

2.66

0.90

90.00

1.33

28

0.50

33.33

1.33

58

29

0.50

33.33

2.00

59

0.90

90.00

2.00

30

0.50

33.33

2.66

60

0.90

90.00

2.66

Bijlage 3-4

BIJLAGE 3.2: PRE-SIMULATIES VOOR GA1 EN SS1 De basisimplementaties van GA en SS staan op zich los van elkaar. Toch werden ze hier samen beschouwd omdat bij de eerste implementatie ook enkele algemene parameters dienen te worden bepaald in verband met de probleem- en onderzoeksetting. Er werd beslist deze algemene parameters te optimaliseren voor beide metaheuristieken samen. Zo wordt voorkomen dat eventuele verschillen in performantie zouden ontstaan tussen GA en SS die niets te maken hebben met de implementatie van de metaheuristieken zelf. Concreet werd voor deze optimalisatieoefening, zoals in bijlage 3.1 besproken, geopteerd voor een tweevoudige iteratie van sequentiële optimalisaties. Voor elke parameter die moet worden geoptimaliseerd, wordt eerst en vooral een interval van discrete waarden bepaald waaruit vervolgens een optimale waarde kan worden gekozen. Eens deze intervallen zijn opgesteld, worden alle parameters geïnitialiseerd op hun gemiddelde intervalwaarde. Hierna kan de eerste iteratie van sequentiële optimalisaties plaatsvinden. Eén voor één worden de parameters vervolgens geoptimaliseerd door, ceteris paribus, de gemiddelde performantie over de 60 projecten in de testset te bepalen voor elke parameterwaarde in het beschouwde interval. Eens een parameter werd geoptimaliseerd, wordt de gevonden optimale waarde toegewezen aan deze parameter en wordt overgegaan tot de volgende te optimaliseren parameter. Deze eerste iteratie van sequentiële optimalisaties zal plaatsvinden voor zowel GA en SS. Hierna worden de algemene parameters geoptimaliseerd op basis van de gemiddelde performantie over GA en SS. Op die manier wordt de eerste iteratie beëindigt. Deze wordt vervolgens herhaald met als verschil dat de parameters geïnitialiseerd worden op de reeds geoptimaliseerde parameterwaarden en dat er eventueel wordt beslist het beschouwde interval met discrete parameterwaarden aan te passen. In wat volgt worden de stappen van deze pre-simulatie gevisualiseerd en worden enkele resultaten getoond.

Bijlage 3-5

STAP 1: Bepaling van de intervallen van discrete parameterwaarden per parameter Tabel 36 - Pre-simulatie metaheuristiek parameters: Stap 1 (bijlage 3.2)

Par1

1 50%

2 55%

3 60%

4 65%

5 70%

6 75%

7 80%

8 85%

9 90%

10 95%

Par2

1%

2.5%

5%

10%

15%

20%

25%

30%

35%

40%

Par5

1

2

3

4

5

Par6 Par7

1%

2%

3%

4%

5%

6%

7%

8%

9%

10%

1

2

3

4

5

6

7

8

9

10

35 1000

40 2000

45 3000

50 4000

55 5000

60 6000

7000

8000

9000

# wkn Stopcriterium

STAP 2: Initialisatie van de parameters op hun gemiddelde intervalwaarde Tabel 37 - Pre-simulatie metaheuristiek parameters: Stap 2 (bijlage 3.2) Parameter

Par1

Initialisatie 72.5%

Par2

17.5%

Par5

3

Par6

5.5%

Par7

6

# wkn

50 6000

Stopcriterium

STAP 3: Eerste iteratie van sequentiële optimalisaties voor GA1 en SS2 Tabel 38 - Pre-simulatie metaheuristiek parameters: Stap 3 – GA (bijlage 3.2) Parameter

Initialisatie

Run 1

Resultaat

Run 2

Resultaat

Par1

72.5%

OPTIMALISATIE

85%

85%

85%

Par2

17.5%

17.5%

17.5%

OPTIMALISATIE

20%

# wkn

50

50

50

50

50

Stopcriterium

6000

6000

6000

6000

6000

Bijlage 3-6

Tabel 39 - Pre-simulatie metaheuristiek parameters: Stap 3 – SS (bijlage 3.2) Parameter

Initialisatie

Run 1

Resultaat

Run 2

Resultaat

Run 3

Resultaat

Par5

3

OPTIMALISATIE

4

4

4

4

4

Par6

5.5%

5.5%

5.5%

OPTIMALISATIE

1%

1%

1%

Par7

6

6

6

6

6

OPTIMALISATIE

3

# wkn

50

50

50

50

50

50

50

Stopcriterium

6000

6000

6000

6000

6000

6000

6000

STAP 4: Optimalisatie van de algemene parameters Tabel 40 - Pre-simulatie metaheuristiek parameters: Stap 4 (bijlage 3.2) Parameter

Initialisatie

Run 1

Resultaat

Run 2

Resultaat

Par1

85%

85%

85%

85%

85%

Par2

20%

20%

20%

20%

20%

Par5

4

4

4

4

4

Par6

1%

1%

1%

1%

1%

Par7

3

3

3

3

3

# wkn

50

OPTIMALISATIE

45

45

45

Stopcriterium

6000

6000

6000

OPTIMALISATIE

4000

STAP 5: Initialisatie van de parameters op hun optimale waarde na de eerste iteratie Tabel 41 - Pre-simulatie metaheuristiek parameters: Stap 5 (bijlage 3.2) Parameter

Par1

Initialisatie 85%

Par2

20%

Par5

4

Par6

1%

Par7

3

# wkn

45

Stopcriterium

4000

Bijlage 3-7

STAP 6: Herdefiniëring van de intervallen uit stap 1 Tabel 42 - Pre-simulatie metaheuristiek parameters: Stap 6 (bijlage 3.2)

Par1

1 50%

2 55%

3 60%

4 65%

5 70%

6 75%

7 80%

8 85%

9 90%

10 95%

Par2

1%

2.5%

5%

10%

15%

20%

25%

30%

35%

40%

Par5

1

2

3

4

5

Par6

1%

2%

3%

4%

5%

Par7

1

2

3

4

5

# wkn

35

40

45

50

55

60

1000

2000

3000

4000

5000

6000

7000

8000

9000

Stopcriterium

6%

STAP 7: Herhaling van STAP 3 en STAP 4 De resultaten van deze pre-simulatie worden samengevat in onderstaande tabel. Tabel 43 - Pre-simulatie metaheuristiek parameters: Stap 7 (bijlage 3.2) Parameter

Par1

Resultaat 90%

Par2

20%

Par5

3

Par6

2%

Par7

3

# wkn

40

Stopcriterium

4000

De geoptimaliseerde parameterwaarden worden niet enkel gekozen op basis van de performantie. Naast dit kwantitatief criterium, worden ook kwalitatieve criteria in rekening gebracht om de uiteindelijke resultaten te bevestigen of bij te sturen. Het gaat hier vooral om het criterium tijdsefficiëntie enerzijds en intensief gebruik van de metaheuristieken anderzijds. Met dit laatste wordt bedoeld dat het uiteindelijke doel van deze studie niet is om de best presterende metaheuristiek te implementeren, maar het vergelijken van metaheuristieken. Daarom mogen de parameters niet verhinderen dat een metaheuristiek voldoende doorlopen wordt. De argumentatie bij Par1 tot en met Par7 wordt vermeld bij het bespreken van de Bijlage 3-8

implementaties doorheen het onderzoek. De optimalisatie van de twee algemene parameters wordt hierna besproken. De pre-simulatie van het maximum aantal beschikbare werknemers (#wkn) toont aan dat een minimale doelfunctiewaarde wordt bereikt bij 50 werknemers. Toch wordt geopteerd voor 40 werknemers om te vermijden dat de resource constraints triviaal zouden worden omdat een overvloedige aanwezigheid van werknemers het tijdsobjectief irrelevant maakt aangezien er genoeg werknemers zijn om alles zo vlug mogelijk te schedulen. Als stopcriterium is een maximaal aantal gegenereerde schedules van 4000 een goede trade-off tussen streven naar optimaliteit in termen van de gemiddelde doelfunctiewaarde enerzijds en tijdsconsumptie van de uiteindelijke simulatie anderzijds. Tijdens de simulatie zullen de resultaten na 0, 1000, 2000, 3000 en 4000 schedules worden opgeslagen.


Pre-simulatie # wkn 9,9 9,85 9,8 9,75 9,7 9,65 9,6 9,55 9,5 9,45 9,4 40

45

50

55

Parameterwaarde

Grafiek 33 - Pre-simulatie aantal werknemers


Pre-simulatie stopcriterium 10 9,9 9,8 9,7 9,6 9,5 9,4 9,3 9,2 9,1 9 0

1000

2000

3000

4000

5000

6000

7000

8000

9000 10000

Aantal gegenereerde schedules

GA PSGS

GA SSGS

SS PSGS

SS SSSGS

Grafiek 34 - Pre-simulatie stopcriterium

Bijlage 3-9

BIJLAGE 3.3: PRE-SIMULATIE VOOR GA4 Bij de implementatie van GA4 wordt een local search methode toegevoegd, gelijkaardig aan de local search in de implementatie van SS1. Net als bij SS1, zullen opnieuw twee parameters moeten worden bepaald. Omdat SS en GA echter als twee aparte metaheuristieken worden beschouwd, wordt opnieuw een tweevoudige iteratie van sequentiële optimalisaties uitgevoerd om te verzekeren dat de local search is afgesteld op de setting in GA. STAP 1: Bepaling van de intervallen van discrete parameterwaarden per parameter Tabel 44 - Pre-simulatie metaheuristiek parameters: Stap 1 (bijlage 3.3)

Par3 Par4

1

2

3

4

5

6

7

8

9

10

1%

2%

3%

4%

5%

6%

7%

8%

9%

10%

1

2

3

4

5

6

7

8

9

10

STAP 2: Initialisatie van de nieuwe parameters op hun gemiddelde intervalwaarde Tabel 45 - Pre-simulatie metaheuristiek parameters: Stap 2 (bijlage 3.3) Parameter

Initialisatie

Par3 Par4

5.5% 6

STAP 3: Eerst iteratie van sequentiële optimalisaties voor GA4 Tabel 46 - Pre-simulatie metaheuristiek parameters: Stap 3 (bijlage 3.3) Parameter

Initialisatie

Run 1

Resultaat

Run 2

Resultaat

Par1

90%

90%

90%

90%

90%

Par2

20%

20%

20%

20%

20%

Par3

5.5%

OPTIMALISATIE

1%

1%

1%

Par4

6

6

6

OPTIMALISATIE

9

# wkn

40

40

40

40

40

Stopcriterium

4000

4000

4000

4000

4000

Bijlage 3-10

STAP 4: Initialisatie van de parameters op hun optimale waarde na de eerste iteratie Tabel 47- Pre-simulatie metaheuristiek parameters: Stap 4 (bijlage 3.3) Parameter

Par3

Initialisatie 1%

Par4

9

STAP 5: Tweede iteratie van sequentiële optimalisaties voor GA4 Tabel 48 - Pre-simulatie metaheuristiek parameters: Stap 5 (bijlage 3.3) Parameter

Par1

Initialisatie 90%

Run 1 90%

Resultaat 90%

Run 2 90%

Resultaat 90%

Par2

20%

20%

20%

20%

20%

Par3

1%

OPTIMALISATIE

1%

1%

1%

Par4

9

9

9

OPTIMALISATIE

9

# wkn

40

40

40

40

40

Stopcriterium

4000

4000

4000

4000

4000

Bijlage 3-11

BESLUIT Deze pre-simulatie beschreef hoe een reeks parameters wordt bepaald voorafgaand aan de eigenlijke simulatie. De invulling van deze parameters behoort mede tot het kader waarin dit onderzoek zich afspeelt. De resultaten worden samengevat in onderstaande tabellen. Tabel 49 - Pre-simulatie besluit GA

GENETIC ALGORITHM GA1

GA4

Parameter Par1 Par2

Omschrijving Cross-over rate (%) Mutation rate (%)

Waarde 90% 20%

Par3 Par4


1% 9

Tabel 50 - Pre-simulatie besluit SS

SCATTER SEARCH

SS1

Parameter

Omschrijving

Waarde

Par5

# leden per subset

3

Par6

# te analyseren buren (%) in local search

2%

Par7

Maximum # local search iteraties

3

Bijlage 3-12

BIJLAGE 4: SIMULATIE De simulatie die aan de basis ligt van deze studie beschrijft de impact van elke projectindicator op de performantie van vier metaheuristieken die worden samengesteld door de metaheuristieken GA en SS te combineren met de planningsmethodes PSGS en SSGS. Om alle dimensies van complexiteit in rekening te brengen wordt hiervoor een set van projecten samengesteld aan de hand van de netwerkgenerator RanGen2 samen met een eenvoudige resourcegenerator in Visual Studio Express 2012 (C++). Het is ook in dit laatste programma dat de eigenlijke simulatie zal plaatsvinden. Om de impact van een projectindicator te onderzoeken, moet deze achtereenvolgens worden vastgezet op een bepaalde waarde of een bepaald interval terwijl de andere projectindicatoren willekeurig variëren. Op die manier wordt de invloed van de andere indicatoren uitgeschakeld en kan dus de reële impact van de beschouwde projectindicator worden afgeleid. Tabellen 51 tot en met 59 geven een overzicht van hoe een simulatie voor één bepaalde metaheuristiek is opgebouwd. Voor de projectindicatoren I2, µc, CVc, µs en CVs worden telkens vijf mogelijke indicatorwaarden beschouwd terwijl voor de projectindicatoren I3, I4, I5 en I6, zes intervallen worden gedefinieerd in lijn met een gelijkaardig onderzoek gevoerd door Vanhoucke (2008). Om een besluit te kunnen trekken over de performantie van een metaheuristiek voor een gegeven waarde van een projectindicator of een gegeven interval waarin een projectindicator kan variëren, worden telkens 30 projecten gegenereerd om dan die performantie uit te middelen. Gegeven het feit dat er 5 waarden worden onderscheiden voor I2, 5 voor de probleemspecifieke projectindicatoren en 6 intervallen voor de andere vier projectindicatoren, werden er dus 49 keer 30 projecten gesimuleerd wat neerkomt op 1470 projecten per metaheuristiek. Aangezien in deze studie vier verschillende metaheuristieken worden beschouwd, komt dit neer op een totaal van 5880 projecten. Om inzicht te krijgen in de performantie van een metaheuristiek zal voor elk van deze 5880 projecten informatie over de doelwaarde worden opgeslagen na respectievelijk 0, 1000, 2000, 3000 en 4000 gegenereerde schedules en dit voor de deelobjectieven tijd, kosten en sociale cohesie. Samen laat dit toe volgende analyses uit te voeren: 1. Performantie van de metaheuristieken GA en SS (zie onderzoeksvraag 1) 2. Performantie van de planningsmethodes PSGS en SSGS (zie onderzoeksvraag 2) 3. Performantie van een metaheuristiek over een projectindicator heen (zie onderzoeksvraag 3) 4. Performantie van een metaheuristiek over de deelobjectieven heen (zie onderzoeksvraag 4)

Bijlage 4-1

Tabel 51 - Simulatie voor indicator I2

I2

I3, I4, I5 en I6

μS

μC

CVs en CVc

#

0.10

[0-1]

{10, 25, 50, 75 , 90}

{1.33 , 1.66, 2, 2.33, 2.66 }

{0.5, 0.75, 1, 1.33, 1.58}

30

0.25

[0-1]

{10, 25, 50, 75 , 90}

{1.33 , 1.66, 2, 2.33, 2.66 }

{0.5, 0.75, 1, 1.33, 1.58}

30

0.50

[0-1]

{10, 25, 50, 75 , 90}

{1.33 , 1.66, 2, 2.33, 2.66 }

{0.5, 0.75, 1, 1.33, 1.58}

30

0.75

[0-1]

{10, 25, 50, 75 , 90}

{1.33 , 1.66, 2, 2.33, 2.66 }

{0.5, 0.75, 1, 1.33, 1.58}

30

0.90

[0-1]

{10, 25, 50, 75 , 90}

{1.33 , 1.66, 2, 2.33, 2.66 }

{0.5, 0.75, 1, 1.33, 1.58}

30


2

I3

I4, I5 en I6

μS

μC

CVs en CVc

#

{0.10, 0.25, 0.50, 0.75 , 0.90}

[0-0.1]

[0-1]

{10, 25, 50, 75 , 90}

{1.33 , 1.66, 2, 2.33, 2.66 }

{0.5, 0.75, 1, 1.33, 1.58}

30

{0.10, 0.25, 0.50, 0.75 , 0.90}

[0.1-0.25]

[0-1]

{10, 25, 50, 75 , 90}

{1.33 , 1.66, 2, 2.33, 2.66 }

{0.5, 0.75, 1, 1.33, 1.58}

30

{0.10, 0.25, 0.50, 0.75 , 0.90}

[0.25-0.5]

[0-1]

{10, 25, 50, 75 , 90}

{1.33 , 1.66, 2, 2.33, 2.66 }

{0.5, 0.75, 1, 1.33, 1.58}

30

{0.10, 0.25, 0.50, 0.75 , 0.90}

[0.5-0.75]

[0-1]

{10, 25, 50, 75 , 90}

{1.33 , 1.66, 2, 2.33, 2.66 }

{0.5, 0.75, 1, 1.33, 1.58}

30

{0.10, 0.25, 0.50, 0.75 , 0.90}

[0.75-0.9]

[0-1]

{10, 25, 50, 75 , 90}

{1.33 , 1.66, 2, 2.33, 2.66 }

{0.5, 0.75, 1, 1.33, 1.58}

30

[0.9-1]

[0-1]

{10, 25, 50, 75 , 90}

{1.33 , 1.66, 2, 2.33, 2.66 }

{0.5, 0.75, 1, 1.33, 1.58}

30

{0.10, 0.25, 0.50, 0.75 , 0.90}


I2

I3

I4

I5 en I6

μS

μC

CVs en CVc

#

{0.10, 0.25, 0.50, 0.75 , 0.90}

[0-1]

[0-0.1]

[0-1]

{10, 25, 50, 75 , 90}

{1.33 , 1.66, 2, 2.33, 2.66 }

{0.5, 0.75, 1, 1.33, 1.58}

30

{0.10, 0.25, 0.50, 0.75 , 0.90}

[0-1]

[0.1-0.25]

[0-1]

{10, 25, 50, 75 , 90}

{1.33 , 1.66, 2, 2.33, 2.66 }

{0.5, 0.75, 1, 1.33, 1.58}

30

{0.10, 0.25, 0.50, 0.75 , 0.90}

[0-1]

[0.25-0.5]

[0-1]

{10, 25, 50, 75 , 90}

{1.33 , 1.66, 2, 2.33, 2.66 }

{0.5, 0.75, 1, 1.33, 1.58}

30

{0.10, 0.25, 0.50, 0.75 , 0.90}

[0-1]

[0.5-0.75]

[0-1]

{10, 25, 50, 75 , 90}

{1.33 , 1.66, 2, 2.33, 2.66 }

{0.5, 0.75, 1, 1.33, 1.58}

30

{0.10, 0.25, 0.50, 0.75 , 0.90}

[0-1]

[0.75-0.9]

[0-1]

{10, 25, 50, 75 , 90}

{1.33 , 1.66, 2, 2.33, 2.66 }

{0.5, 0.75, 1, 1.33, 1.58}

30

{0.10, 0.25, 0.50, 0.75 , 0.90}

[0-1]

[0.9-1]

[0-1]

{10, 25, 50, 75 , 90}

{1.33 , 1.66, 2, 2.33, 2.66 }

{0.5, 0.75, 1, 1.33, 1.58}

30

Bijlage 4-2


I2

I3, I4

I5

I6

μS

μC

CVs en CVc

#

{0.10, 0.25, 0.50, 0.75 , 0.90}

[0-1]

[0-0.1]

[0-1]

{10, 25, 50, 75 , 90}

{1.33 , 1.66, 2, 2.33, 2.66 }

{0.5, 0.75, 1, 1.33, 1.58}

30

{0.10, 0.25, 0.50, 0.75 , 0.90}

[0-1]

[0.1-0.25]

[0-1]

{10, 25, 50, 75 , 90}

{1.33 , 1.66, 2, 2.33, 2.66 }

{0.5, 0.75, 1, 1.33, 1.58}

30

{0.10, 0.25, 0.50, 0.75 , 0.90}

[0-1]

[0.25-0.5]

[0-1]

{10, 25, 50, 75 , 90}

{1.33 , 1.66, 2, 2.33, 2.66 }

{0.5, 0.75, 1, 1.33, 1.58}

30

{0.10, 0.25, 0.50, 0.75 , 0.90}

[0-1]

[0.5-0.75]

[0-1]

{10, 25, 50, 75 , 90}

{1.33 , 1.66, 2, 2.33, 2.66 }

{0.5, 0.75, 1, 1.33, 1.58}

30

{0.10, 0.25, 0.50, 0.75 , 0.90}

[0-1]

[0.75-0.9]

[0-1]

{10, 25, 50, 75 , 90}

{1.33 , 1.66, 2, 2.33, 2.66 }

{0.5, 0.75, 1, 1.33, 1.58}

30

{0.10, 0.25, 0.50, 0.75 , 0.90}

[0-1]

[0.9-1]

[0-1]

{10, 25, 50, 75 , 90}

{1.33 , 1.66, 2, 2.33, 2.66 }

{0.5, 0.75, 1, 1.33, 1.58}

30


I2

I3, I4, I5

I6

μS

μC

CVs en CVc

#

{0.10, 0.25, 0.50, 0.75 , 0.90}

[0-1]

[0-0.1]

{10, 25, 50, 75 , 90}

{1.33 , 1.66, 2, 2.33, 2.66 }

{0.5, 0.75, 1, 1.33, 1.58}

30

{0.10, 0.25, 0.50, 0.75 , 0.90}

[0-1]

[0.1-0.25]

{10, 25, 50, 75 , 90}

{1.33 , 1.66, 2, 2.33, 2.66 }

{0.5, 0.75, 1, 1.33, 1.58}

30

{0.10, 0.25, 0.50, 0.75 , 0.90}

[0-1]

[0.25-0.5]

{10, 25, 50, 75 , 90}

{1.33 , 1.66, 2, 2.33, 2.66 }

{0.5, 0.75, 1, 1.33, 1.58}

30

{0.10, 0.25, 0.50, 0.75 , 0.90}

[0-1]

[0.5-0.75]

{10, 25, 50, 75 , 90}

{1.33 , 1.66, 2, 2.33, 2.66 }

{0.5, 0.75, 1, 1.33, 1.58}

30

{0.10, 0.25, 0.50, 0.75 , 0.90}

[0-1]

[0.75-0.9]

{10, 25, 50, 75 , 90}

{1.33 , 1.66, 2, 2.33, 2.66 }

{0.5, 0.75, 1, 1.33, 1.58}

30

{0.10, 0.25, 0.50, 0.75 , 0.90}

[0-1]

[0.9-1]

{10, 25, 50, 75 , 90}

{1.33 , 1.66, 2, 2.33, 2.66 }

{0.5, 0.75, 1, 1.33, 1.58}

30

Tabel 56 - Simulatie voor indicator μs

I2

I3, I4, I5 en I6

μS

μC

CVs en CVc

#

{0.10, 0.25, 0.50, 0.75 , 0.90}

[0-1]

10

{1.33 , 1.66, 2, 2.33, 2.66 }

{0.5, 0.75, 1, 1.33, 1.58}

30

{0.10, 0.25, 0.50, 0.75 , 0.90}

[0-1]

25

{1.33 , 1.66, 2, 2.33, 2.66 }

{0.5, 0.75, 1, 1.33, 1.58}

30

{0.10, 0.25, 0.50, 0.75 , 0.90}

[0-1]

50

{1.33 , 1.66, 2, 2.33, 2.66 }

{0.5, 0.75, 1, 1.33, 1.58}

30

{0.10, 0.25, 0.50, 0.75 , 0.90}

[0-1]

75

{1.33 , 1.66, 2, 2.33, 2.66 }

{0.5, 0.75, 1, 1.33, 1.58}

30

{0.10, 0.25, 0.50, 0.75 , 0.90}

[0-1]

90

{1.33 , 1.66, 2, 2.33, 2.66 }

{0.5, 0.75, 1, 1.33, 1.58}

30

Bijlage 4-3

Tabel 57 - Simulatie voor indicator μc

I2

I3, I4, I5 en I6

μS

μC

CVs en CVc

#

{0.10, 0.25, 0.50, 0.75 , 0.90}

[0-1]

{10, 25, 50, 75 , 90}

1.33

{0.5, 0.75, 1, 1.33, 1.58}

30

{0.10, 0.25, 0.50, 0.75 , 0.90}

[0-1]

{10, 25, 50, 75 , 90}

1.66

{0.5, 0.75, 1, 1.33, 1.58}

30

{0.10, 0.25, 0.50, 0.75 , 0.90}

[0-1]

{10, 25, 50, 75 , 90}

2

{0.5, 0.75, 1, 1.33, 1.58}

30

{0.10, 0.25, 0.50, 0.75 , 0.90}

[0-1]

{10, 25, 50, 75 , 90}

2.33

{0.5, 0.75, 1, 1.33, 1.58}

30

{0.10, 0.25, 0.50, 0.75 , 0.90}

[0-1]

{10, 25, 50, 75 , 90}

2.66

{0.5, 0.75, 1, 1.33, 1.58}

30

Tabel 58 - Simulatie voor indicator CVs

I2

I3, I4, I5 en I6

μS

μC

CVs

CVc

#

{0.10, 0.25, 0.50, 0.75 , 0.90} {0.10, 0.25, 0.50, 0.75 , 0.90} {0.10, 0.25, 0.50, 0.75 , 0.90} {0.10, 0.25, 0.50, 0.75 , 0.90} {0.10, 0.25, 0.50, 0.75 , 0.90}

[0-1] [0-1] [0-1] [0-1] [0-1]

{10, 25, 50, 75 , 90} {10, 25, 50, 75 , 90} {10, 25, 50, 75 , 90} {10, 25, 50, 75 , 90} {10, 25, 50, 75 , 90}

{1.33 , 1.66, 2, 2.33, 2.66 } {1.33 , 1.66, 2, 2.33, 2.66 } {1.33 , 1.66, 2, 2.33, 2.66 } {1.33 , 1.66, 2, 2.33, 2.66 } {1.33 , 1.66, 2, 2.33, 2.66 }

0.5 0.75 1 1.33 1.58

{0.5, 0.75, 1, 1.33, 1.58} {0.5, 0.75, 1, 1.33, 1.58} {0.5, 0.75, 1, 1.33, 1.58} {0.5, 0.75, 1, 1.33, 1.58} {0.5, 0.75, 1, 1.33, 1.58}

30 30 30 30 30

Tabel 59 - Simulatie voor indicator CVc

I2

I3, I4, I5 en I6

μS

μC

CVS

CVc

#

{0.10, 0.25, 0.50, 0.75 , 0.90} {0.10, 0.25, 0.50, 0.75 , 0.90} {0.10, 0.25, 0.50, 0.75 , 0.90} {0.10, 0.25, 0.50, 0.75 , 0.90} {0.10, 0.25, 0.50, 0.75 , 0.90}

[0-1] [0-1] [0-1] [0-1] [0-1]

{10, 25, 50, 75 , 90} {10, 25, 50, 75 , 90} {10, 25, 50, 75 , 90} {10, 25, 50, 75 , 90} {10, 25, 50, 75 , 90}

{1.33 , 1.66, 2, 2.33, 2.66 } {1.33 , 1.66, 2, 2.33, 2.66 } {1.33 , 1.66, 2, 2.33, 2.66 } {1.33 , 1.66, 2, 2.33, 2.66 } {1.33 , 1.66, 2, 2.33, 2.66 }

{0.5, 0.75, 1, 1.33, 1.58} {0.5, 0.75, 1, 1.33, 1.58} {0.5, 0.75, 1, 1.33, 1.58} {0.5, 0.75, 1, 1.33, 1.58} {0.5, 0.75, 1, 1.33, 1.58}

0.5 0.75 1 1.33 1.58

30 30 30 30 30

Bijlage 4-4

BIJLAGE 5: INTELLIGENTE PRIORITEITSREGELS In deze bijlage wordt een uitgebreider overzicht gegeven van de gebruikte prioriteitsregels in Genetic Algorithm en Scatter Search.

Prioriteitsregels i.v.m activiteiten 1. Earliest Start Time (EST) De EST van een activiteit is het tijdstip waarop deze ten vroegste kan worden aangevat. Hiervoor wordt gekeken naar het moment waarop de voorafgaande activiteiten zijn afgewerkt. Activiteiten met een kleinere EST krijgen een hogere prioriteit (Klein, 2000). 2. Shortest Processing Time (SPT) De processing time van een activiteit is de tijdsduur van deze activiteit. Activiteiten met een kortere tijdsduur krijgen een hogere prioriteit (Oral, 1973). 3. Longest Processing Time (LPT) De processing time van een activiteit is de tijdsduur van deze activiteit. Activiteiten met een grotere tijdsduur krijgen een hogere prioriteit (Blackstone, 1982). 4. Most Immediate Successors (MIS) De immediate successors van een activiteit zijn de activiteiten die pas kunnen worden aangevat als de beschouwde activiteit is afgewerkt. Een activiteit met een groter aantal onmiddellijke opvolgers krijgt een hogere prioriteit (Klein, 2000). 5. Most Total Successors (MTS) De total successors van een activiteit zijn alle activiteiten die pas kunnen worden aangevat als de beschouwde activiteit is afgewerkt, samen met hun respectievelijke opvolgers. Een activiteit met een groter aantal opvolgers krijgt een hogere prioriteit (Klein, 2000). 6. Least Non-Related Jobs (LNJ) De non-related jobs van een activiteit zijn de activiteiten die niet via een predecessor of successor relatie in verbinding staan met de beschouwde activiteit. Een activiteit met een kleiner aantal ongerelateerde activiteiten krijgt een hogere prioriteit (Cooper, 1972).

Bijlage 5-1

7. Greatest Rank Positional Weight (GRPW) De rank positional weight van een activiteit is de som van zijn duurtijd en de duurtijd van zijn onmiddelijke opvolgers. Een activiteit met een hogere rank positional weight krijgt een hogere prioriteit (Cooper, 1972). 8. Greatest Work content (GWC) De work content van een activiteit is het product van de gesommeerde resource requirements en de activiteitsduur. Een activiteit met een grotere werkinhoud krijgt een hogere prioriteit (Vanhoucke, 2012). 9. Greatest Cumulative Work Content (GCWC) De cumulative work content is de sommatie van de work content van de activiteit zelf en deze van zijn onmiddellijke opvolgers. Een activiteit met een grotere cumulatieve werkinhoud krijgt een hogere prioriteit (Vanhoucke, 2012). 10. Greatest Resource Scarcity (GRS) De scarcity van een resource is het quotiënt van de totale vraag naar die resource over alle activiteiten en het totale aanbod van die resource over alle werknemers. Een activiteit krijgt een hogere prioriteit naargelang deze veel van een schaarsere resource vraagt. Deze prioriteitsregel bestaat niet standaard in de literatuur maar werd ontworpen in functie van het TCP.

Prioriteitsregels i.v.m werknemers 1. Greatest Time Related Skill Requirement (GTRSR) De time related skill requirement van een vaardigheid is de sommatie van de work contents over de activiteiten voor die vaardigheid. Werknemers die vaardigheden bezitten die in grote hoeveelheden en voor lange tijd worden gevraagd worden, worden als belangrijker beschouwd. Een werknemer krijgt een hogere prioriteit naargelang hij meer van deze resources bezit. Deze prioriteitsregel bestaat niet standaard in de literatuur maar werd ontworpen in functie van het TCP. 2. Greatest Skill Scarcity (GSS) De scarcity van een vaardigheid (skill) is het quotiënt van de totale vraag naar die vaardigheid over alle activiteiten en het totale aanbod van die vaardigheid over alle werknemers. Een werknemer krijgt een hogere prioriteit naargelang hij meer van een schaarsere vaardigheid bezit. Deze prioriteitsregel bestaat niet standaard in de literatuur maar werd ontworpen in functie van het TCP.

Bijlage 5-2

3. Greatest Social Likability (GSL) De social likability van een werknemer is de som van de sociale cohesie coëfficiënten van de andere werknemers ten opzichte van deze werknemer. Het is met andere woorden een indicatie van de mate waarin een werknemer goed in de groep ligt. Een werknemer met een grotere social likability krijgt een hogere prioriteit. Deze prioriteitsregel bestaat niet standaard in de literatuur maar werd ontworpen in functie van het TCP. 4. Greatest Social Tolerance (GST) De social tolerance van een werknemer is de som van de sociale cohesie coëfficiënten van deze werknemer ten opzichte van de andere werknemers. Het is met andere woorden een indicatie van de mate waarin een werknemer verdraagzaam is tegenover de andere werknemers. Een werknemer met een grotere social tolerance krijgt een hogere prioriteit. Deze prioriteitsregel bestaat niet standaard in de literatuur maar werd ontworpen in functie van het TCP. 5. Greatest Competence Weighted Social Strength (GCWSS) De competence weighted social strength is het quotiënt van de som van de social likability en social tolerance, en het competentieniveau van de werknemer. Het bevoordeelt werknemers die goede relaties hebben met de andere werknemers en een hoog competentieniveau hebben. Een werknemer met een grotere competence weighted social strength krijgt een hogere prioriteit. Deze prioriteitsregel bestaat niet standaard in de literatuur maar werd ontworpen in functie van het TCP.

Bijlage 5-3

PROJECT SCHEDULING EN TEAMEFFICIENTIE

Recommend Documents