Integere programmering voor cyclische personeelsplanning

UNIVERSITEIT GENT FACULTEIT ECONOMIE EN BEDRIJFSKUNDE ACADEMIEJAAR 2011 – 2012

Integere programmering voor cyclische personeelsplanning

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

Jonas Ingels onder leiding van Prof. Broos Maenhout

UNIVERSITEIT GENT FACULTEIT ECONOMIE EN BEDRIJFSKUNDE ACADEMIEJAAR 2011 – 2012

Integere programmering voor cyclische personeelsplanning

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

Jonas Ingels onder leiding van Prof. Broos Maenhout

PERMISSION Ondergetekende verklaart dat de inhoud van deze masterproef mag geraadpleegd en/of gereproduceerd worden, mits bronvermelding. Jonas Ingels

I

Woord vooraf Dit onderzoek is tot stand gekomen dankzij de ondersteuning van professor Broos Maenhout, die veel bruikbare ideeën heeft voorgesteld en altijd bereikbaar was voor feedback.

II

Inhoudsopgave 1.

Inleiding ........................................................................................................................................... 1

2.

Literatuurstudie ............................................................................................................................... 3

3.

Model ............................................................................................................................................ 11 3.1 Indexen en sets............................................................................................................................ 12 3.2 Parameters .................................................................................................................................. 13 3.3 Beslissingsvariabelen ................................................................................................................... 14 3.4 Model .......................................................................................................................................... 15 3.5 Uitleg bij model ........................................................................................................................... 16 3.6 Uitleg bij model ........................................................................................................................... 20

4.

Oplossingen Gurobi Solver voor gewoon model ........................................................................... 22 4.1 Minimum vereist aantal werknemers per shift (beperking (1b)) ................................................ 24 4.2 1 shift of vrije dag beperking (beperking (1g)) ............................................................................ 25 4.3 Maximaal opeenvolgende werkdagen (beperking (1i)) .............................................................. 26 4.4 Vrije dagen (beperkingen (1l), (1m) en (1n)) ............................................................................... 26 4.5 Voorwaartse rotatie van laatste naar eerste shift (beperking (1h)) ........................................... 28 4.6 Het aantal vrije weekenddagen per planningsperiode (beperking (1k)) .................................... 28 4.7 Beperking op teveel en te weinig werknemers (beperking (1s)) ................................................ 29

5.

“Branch and price” methode......................................................................................................... 29 5.1 Masterprobleem.......................................................................................................................... 30 5.1.1 Indexen en sets..................................................................................................................... 30 5.1.2 Parameters ........................................................................................................................... 30 5.1.3 Beslissingsvariabelen ............................................................................................................ 30 5.2 Subprobleem ............................................................................................................................... 31 5.2.1 Parameters ........................................................................................................................... 31 5.3 Methode ...................................................................................................................................... 32 5.3.1 Initiële oplossing ................................................................................................................... 32 5.3.2 Procedure: kolomgeneratie.................................................................................................. 33 5.3.3 Procedure: Naar boven afronden van de oplossing van het masterprobleem .................... 33 5.3.4 Procedure: Selectie branching variabele .............................................................................. 33 5.3.5 Procedure: “Left branch” ..................................................................................................... 34 5.3.6 Procedure: Store solution..................................................................................................... 35 5.3.7 Procedure: Backtracking....................................................................................................... 35 5.3.8 Procedure: “right branch” .................................................................................................... 36 III

6.

Cycliciteitsonderzoek..................................................................................................................... 36 6.1 Karakteristieken........................................................................................................................... 38 6.2 Personeelsvereisten .................................................................................................................... 41 6.3 Resultaten.................................................................................................................................... 44 6.3.1 Volledige cycliciteit ............................................................................................................... 44 6.3.2 Verminderde cycliciteit ........................................................................................................ 49 6.3.3 Relaxatie andere beperkingen.............................................................................................. 63

7.

Conclusie ....................................................................................................................................... 66

8. Referenties ........................................................................................................................................... I Appendix A ............................................................................................................................................. IV Appendix B .............................................................................................................................................. V Appendix C............................................................................................................................................. VII Appendix D ............................................................................................................................................. XI Appendix E ............................................................................................................................................. XV

IV

Lijst met figuren Figuur 1: procedure ............................................................................................................................... 34 Figuur 2: branching tree ........................................................................................................................ 35 Figuur 3: SCD=0 ..................................................................................................................................... 47 Figuur 4: SCD=0 ..................................................................................................................................... 47 Figuur 5: DCD=0 ..................................................................................................................................... 48 Figuur 6: DCD=0 ..................................................................................................................................... 48

Lijst met tabellen Tabel 1: cyclisch personeelsplan ............................................................................................................. 3 Tabel 2: Beperkingen ............................................................................................................................... 6 Tabel 3: bijhorende papers...................................................................................................................... 6 Tabel 4: meest voorkomende beperkingen ............................................................................................ 7 Tabel 5: voorbeeld TCC.......................................................................................................................... 10 Tabel 6: voorbeeld normaal cyclisch schema ........................................................................................ 20 Tabel 7: voorbeeld aangepast cyclisch model ....................................................................................... 20 Tabel 8: voorbeeld aangepast model .................................................................................................... 21 Tabel 9: Beperking volgens belang (1 is hoogste-9 is laagste) .............................................................. 23 Tabel 10: vraag naar werknemers ......................................................................................................... 24 Tabel 11: resultaat model...................................................................................................................... 25 Tabel 12: resultaat model...................................................................................................................... 25 Tabel 13: resultaat model...................................................................................................................... 26 Tabel 14: preferenties voor vrije dagen ................................................................................................ 27 Tabel 15: oplossing model ..................................................................................................................... 27 Tabel 16: oplossing model ..................................................................................................................... 28 Tabel 17: oplossing model ..................................................................................................................... 29 Tabel 18: voorbeeld............................................................................................................................... 34 Tabel 19: right branch variabele............................................................................................................ 36 Tabel 20: shiftovergangen ..................................................................................................................... 38 Tabel 21: voorbeeld cycliciteit............................................................................................................... 40 Tabel 22: werknemers ........................................................................................................................... 43 Tabel 23: resultaten............................................................................................................................... 45 Tabel 24: correlaties .............................................................................................................................. 48 Tabel 25: correlaties .............................................................................................................................. 49 Tabel 26: resultaten % cycliciteit ........................................................................................................... 51 Tabel 27: resultaten % cycliciteit ........................................................................................................... 51 Tabel 28: resultaten % cycliciteit ........................................................................................................... 52 Tabel 29: vergelijking (DCD=0-SCD=0)................................................................................................... 52 Tabel 30: vergelijking (DCD=0,5-SCD=0)................................................................................................ 53 Tabel 31: correlaties TCC=0,2 ................................................................................................................ 54 Tabel 32: correlaties TCC=0,35 .............................................................................................................. 54 Tabel 33: correlaties TCC=0,5 ................................................................................................................ 54 Tabel 34: extra correlaties ..................................................................................................................... 55 V

Tabel 35: vergelijking correlaties........................................................................................................... 56 Tabel 36: extra vergelijking correlaties ................................................................................................. 56 Tabel 37: outliers (DCD=0-SCD=0) ......................................................................................................... 57 Tabel 38: outliers (DCD=0,25-SCD=0,25) ............................................................................................... 57 Tabel 39: outliers (DCD=0,25-SCD=0,25) ............................................................................................... 58 Tabel 40: tijd-correlatie (TCC=0,2) ........................................................................................................ 59 Tabel 41: tijd-correlatie (TCC=0,35) ...................................................................................................... 60 Tabel 42: tijd-correlatie (TCC=0,5) ........................................................................................................ 60 Tabel 43: maximale tijd 100% cycliciteit ............................................................................................... 60 Tabel 44: nodes - IP oplossing ............................................................................................................... 61 Tabel 45: nodes - IP oplossing ............................................................................................................... 62 Tabel 46: vergelijking relaxatie.............................................................................................................. 65 Tabel 47: vergelijking 80% cycliciteit ..................................................................................................... 65

VI

1. Inleiding Aangezien mensen dikwijls de bepalende factor zijn in het waarborgen van een goede productie of dienstverlening, is personeelsplanning een belangrijk onderdeel voor de werking van elk hedendaags bedrijf. Dit zorgt ervoor dat het niet alleen belangrijk is dat de juiste mensen op de juiste momenten aanwezig zijn, maar ook dat er voldoende mensen op de verschillende tijdstippen werken. Hierbij kan onder andere gedacht worden aan de personeelsproblematiek in ziekenhuizen. Deze hebben het soms zeer moeilijk om genoeg personeel te vinden en hebben tegelijkertijd te maken met zeer onverwachte schommelingen in de vraag. Bovendien wordt er een steeds grotere druk uitgeoefend op de kosten, waarvan personeelskosten een groot deel zijn. De voorbeelden waarbij werknemers ontslagen worden omwille van besparingen zijn legio. Dit heeft tot gevolg dat momenten waarop te veel werknemers aanwezig zijn, moeten vermeden worden. Het is echter ook essentieel dat er geen tekort aan werknemers is, want dit zou kunnen leiden tot een slechte dienstverlening en in het ergste geval tot verlies van klanten en bijgevolg, verlies van inkomsten. Hierdoor is, vanuit het standpunt van het bedrijf, het tekort aan werknemers op bepaalde tijdstippen eigenlijk erger dan het teveel aan werknemers. Ook vanuit het perspectief van de werknemers is er een groeiende interesse naar personeelsplanning. Dit komt voort uit het feit dat een werkritme met een gezonde werk-rust balans steeds belangrijker wordt. Bedrijven kunnen een personeelsplanning, die aan deze vereiste voldoet, gebruiken om de beter geschoolde, meer talentrijke werknemers aan te trekken. Het is immers niet alleen het loon dat een doorslaggevende rol speelt bij de keuze van een werkgever. In “Human Resources” wordt dit gevecht voor de meest talentrijke werknemers ook wel eens “the war for talent” genoemd. Een gezonde werk-rust balans is trouwens niet alleen voordelig voor de bedrijven zelf (aantrekken van betere werknemers) maar ook voor de werknemers. Er zal een grotere tevredenheid waargenomen kunnen worden onder de werknemers, precies omdat rekening gehouden wordt met hun behoeften. Onrechtstreeks is dit dan weer positief voor het bedrijf zelf, tevreden werknemers leiden immers, onder andere, tot meer tevredenheid bij de klanten en minder absenteïsme onder de werknemers. Opnieuw kan hier verwezen worden naar ziekenhuizen waar het algemeen geweten is dat er een groeiend tekort aan verplegend personeel is. Een personeelsplan met een goed werkritme kan deze ziekenhuizen dus helpen om voldoende goed getraind verplegend personeel aan te trekken.

1

Al deze trends dragen bij tot het belang van personeelsplanning. Een personeelsplan moet dus voldoen aan de verschillende gestelde vereisten. Deze vereisten worden, echter, niet alleen bepaald door het bedrijf en de werknemers, maar ook door de overheid. Daarom is het belangrijk om, rekening houdend met al deze soms tegenstrijdige vereisten (bv. druk op kosten maar tegelijkertijd voldoen aan de vraag naar personeel), een plan uit te dokteren dat aanvaardbaar is voor zowel het bedrijf als voor de werknemers. De voorgenoemde trends dragen dan ook bij tot de relevantie van het onderzoek dat in deze paper wordt gevoerd. De bedoeling is dat er een indicatie kan gegeven worden over wanneer het interessant kan zijn om een cyclisch personeelsplan te gebruiken, rekening houdend met de fluctuaties in de personeelsvereisten. Bovendien zal er gekeken worden naar opties om onproductieve allocaties zoveel mogelijk te vermijden. Dit is immers belangrijk voor het kostenaspect van een bedrijf. Het verdere verloop van deze paper is als volgt: In het tweede deel van deze paper (Literatuurstudie) wordt er meer uitleg gegeven bij het gevoerde literatuuronderzoek en de meest relevante resultaten ervan. Er wordt stilgestaan bij de verschillende aspecten die in rekening gebracht moeten worden bij het opstellen van een personeelsplan en hoe deze in de literatuur algemeen aangepakt worden. Het derde deel omvat een beschrijving van het mathematisch model dat zal gebruikt worden om het probleem op te lossen. Hier wordt dieper ingegaan op de reden waarom bepaalde beperkingen in het model werden geïntegreerd. Ook wordt meer uitleg gegeven over welke paper de basis heeft gevormd in dit onderzoek en waarom. Dit deel wordt afgesloten met een behandeling van de verschillende mogelijke cyclische schema’s en hun invloed op het eerder voorgestelde mathematische model. Het vierde deel geeft meer uitleg over hoe het model in eerste en tweede instantie werd opgelost, namelijk met de gewone Solver van Microsoft Excel en met een add-in Solver (Gurobi Solver). Het doel van dit deel is tweeledig. Enerzijds toont dit aan dat het zeer moeilijk is om een oplossing te vinden voor een groot model, anderzijds zorgt dit deel ervoor dat het in deel 6 mogelijk wordt om te kijken welke beperkingen eventueel verwijderd kunnen worden om een betere oplossing (met een lager aantal onproductieve allocaties) te kunnen bekomen. Vervolgens wordt in het vijfde deel, de “branch and price” methode die werd geprogrammeerd om het model op te lossen, behandeld. Hierna wordt in het zesde deel de eigenlijke onderzoeksopzet van deze paper besproken. Hier wordt gekeken of er bepaalde conclusies kunnen getrokken worden over wanneer het interessant is om een volledig cyclisch, een gedeeltelijk cyclisch (bv. 80% cyclisch of zelfs 20% cyclisch) of een volledig

2

acyclisch schema te gebruiken. Dit deel eindigt met een bespreking van de invloed van de relaxatie van bepaalde beperkingen op de onproductiviteit. In het laatste deel worden de algemene conclusies, die uit dit onderzoek kunnen getrokken worden, vermeld en wordt er een aanzet tot mogelijk toekomstig onderzoek gegeven.

2. Literatuurstudie Er is reeds uitgebreid onderzoek gevoerd naar personeelsplanning. In de literatuur wordt veelal een onderscheid gemaakt tussen cyclische en niet-cyclische personeelsplanning en personeelsplannen waarbij werknemers zelf kunnen aangeven wanneer ze willen werken (Bard en Purnomo 2006). 

Niet-cyclische personeelsplanning betekent dat er enkel rekening gehouden wordt met de individuele preferenties van de verschillende werknemers en met het feit dat voldaan moet worden aan de vraag naar die werknemers over de verschillende shifts en dagen. Dit betekent dus dat er geen beperking is die stelt dat het personeelsplan zich na verloop van tijd moet herhalen. Het grote voordeel van deze vorm van personeelsplanning is dat er zoveel mogelijk wordt voldaan aan de individuele preferenties van de werknemers. Dit is, met andere woorden, heel positief voor de tevredenheid van werknemers. Echter, het nadeel dat verbonden is aan dit soort personeelsplanning, is het gebrek aan gelijkheid over de verschillende werknemers. Hiermee wordt bedoeld dat de werknemers uiteindelijk niet allemaal hetzelfde schema zullen doorlopen en bijgevolg is het mogelijk dat werknemers het gevoel krijgen dat anderen gunstigere werkvoorwaarden hebben (bv. minder weekendwerk), ook al wordt er zoveel mogelijk met hun preferenties rekening gehouden. Dit is het gevolg van het feit dat het onmogelijk is om aan alle preferenties van alle werknemers tegelijkertijd te voldoen.



Cyclische personeelsplanning betekent dat werknemers een bepaald werkschema zullen toegewezen krijgen dat zich steeds opnieuw zal herhalen. Een heel eenvoudig voorbeeld wordt gegeven in tabel 1. Week 1

Week 2

(maandag tot vrijdag)

(maandag tot vrijdag)

Werknemer 1

Shift 1

Shift 2

Shift 3

Werknemer 2

Shift 2

Shift 3

Shift 1

Werknemer 3

Shift 3

Shift 1

Shift 2

Tabel 1: cyclisch personeelsplan

3

Week 3 (maandag tot vrijdag)

Dit soort schema’s werkt het best in stabiele omgevingen waar de vraag naar werknemers op voorhand gemakkelijk kan voorspeld worden en waarbij deze niet al te veel schommelingen ondervindt over de tijd. Het voordeel van deze methode staat in contrast met het grote nadeel van niet-cyclische personeelsplanning, namelijk de rechtvaardige verdeling van toekenningen. Elke werknemer zal uiteindelijk in het bovenstaande voorbeeld dezelfde shifts gewerkt hebben als alle andere werknemers. De voorspelbaarheid voor de werknemers is, met andere woorden, heel hoog. Millar en Kiragu (1998) stellen daarenboven dat de tijd nodig om zo’n probleem op te lossen lager is dan bij niet-cyclische personeelsplannen. De nadelen, verbonden aan deze vorm van personeelsplanning, zijn volgens Millar en Kiragu (1998) de onmogelijkheid om te beantwoorden aan de aanpassingen in de vraag. Hiermee wordt, met andere woorden, verwezen naar het gebrek aan flexibiliteit om onder andere ziekte van werknemers of het opnemen van vakantie door één of meerdere werknemers op te vangen (Warner 1976, Housos en Valouxis 2000). Een bijkomend nadeel is echter het voordeel voor niet-cyclische personeelsschema’s, namelijk dat er geen rekening gehouden wordt met de persoonlijke voorkeuren van de werknemers (Bard en Purnomo 2005). 

De laatste mogelijkheid is dat de werknemers zelf kunnen bepalen welke shifts op welke dagen ze werken. Het initiatief ligt dus volledig bij de werknemer. De verantwoordelijke voor de personeelsplanning moet er dan voor zorgen dat er ten allen tijde voldoende werknemers aanwezig zijn. Aangezien het zeer waarschijnlijk is dat er minder vrijwilligers zullen zijn voor de minder aantrekkelijke shifts (zoals bijvoorbeeld nacht –en/of weekendshifts), zullen compromissen gesloten moeten worden. Dit heeft tot gevolg dat deze methode zeer tijdrovend is en potentieel gepercipieerd kan worden als onrechtvaardig door de benadeelde werknemers. Bovendien zullen deze benadeelde werknemers willen dat tijdens de volgende planningsperiode zij als eerste kunnen bepalen welke shifts op welke dagen zij werken. Hierdoor brengt zo’n vorm van personeelsplanning dus een extra last mee voor de verantwoordelijke van de personeelsplanning. Deze methode zal dan ook niet verder gebruikt worden in dit onderzoek.

Zoals uit de afweging van de voor –en nadelen van de verschillende methodes blijkt, zijn de cyclische en niet-cyclische personeelsplanning methodes in essentie complementair. Immers wat het grootste voordeel is voor de cyclische methode (namelijk de rechtvaardige verdeling van de verschillende shifts) is dan weer een nadeel voor de niet-cyclische vorm van personeelsplanning (gebrek aan gelijkheid in de toekenningen) en omgekeerd (geen rekening houdend met preferenties versus zo veel mogelijk rekening houdend met preferenties). Bard en Purnomo (2007) stellen dan ook voor om 4

de belangrijkste componenten van de cyclische en niet-cyclische personeelsplanning te combineren in één en hetzelfde model. Er zal dus een trade-off plaatsvinden tussen enerzijds het volgen van het cyclische schema en anderzijds het rekening houden met de preferenties van werknemers. De gedachtegang van deze hybride methode wordt in dit onderzoek ook gevolgd. Een bijkomende reden dat deze methode voordeliger is dan de afzonderlijke methodes is de mogelijkheid om flexibiliteit, in het opvangen van fluctuaties in de vraag naar werknemers, en stabiliteit, in de shiftallocaties, toe te voegen aan respectievelijk cyclische en niet-cyclische schema’s. Elk mathematisch model bestaat uit een doelfunctie, die geminimaliseerd of gemaximaliseerd moet worden, en een aantal, al dan niet, bindende beperkingen waaraan de oplossing van het model moet voldoen. Om bijgevolg tot een goed model te kunnen komen moet er eerst een doelfunctie bepaald worden, alsook beperkingen waaraan de oplossing van deze doelfunctie moeten voldoen. De doelfunctie is over het algemeen een uitdrukking van verschillende subdoelstellingen waaraan verschillende

gewichten

worden

toegekend.

De

meest

voorkomende

doelstellingen

in

personeelsplanning liggen in de lijn van het minimaliseren van de verschillende kosten zoals: de kosten voor interim-werknemers, tekort aan werknemers,.... De doelfunctie zal dan ook geminimaliseerd moeten worden. Beperkingen worden in de literatuur opgedeeld in verschillende klassen. Burke et al. (2004), Bard en Purnomo (2006) en Cheang et al. (2003) maken bijvoorbeeld het onderscheid tussen “hard constraints” en “soft constraints”. Het eerste type beperkingen zijn beperkingen die ten allen tijde moeten voldaan zijn, zoals bijvoorbeeld het maximaal opeenvolgende dagen die de werknemers mogen werken. De “soft constraints” verwijzen naar beperkingen die mogen overtreden worden maar waaraan dan een kost is verbonden die toegerekend moet worden in de doelfunctie. Burke et al. (2004) voegen aan de mogelijke classificaties van beperkingen ook nog “time related constraints” versus “coverage constraints” toe. “Time related constraints” zijn beperkingen die te maken hebben met de beperkingen die opgelegd worden op de persoonlijke schema’s van de werknemers, bijvoorbeeld persoonlijke preferenties. Deze beperking kan echter gezien worden als een “soft constraint”. De “coverage constraints” verwijzen naar het vereist aantal werknemers van een bepaald ervaringsniveau die gedurende een bepaalde shift moeten werken, deze worden hier verder voor de eenvoud personeelsvereisten genoemd. Andere auteurs zoals Maenhout en Vanhoucke (2010a) voegen ook nog het verschil tussen horizontale en verticale beperkingen toe. Horizontale beperkingen zijn beperking die gelden binnen 1 schema voor 1 werknemer, bijvoorbeeld het maximaal opeenvolgende dagen dat een werknemer mag werken. Verticale beperking gelden daarentegen over alle schema’s en over alle werknemers. 5

De personeelsvereisten die gelden over de verschillende shifts en dagen zijn een goed voorbeeld van een verticale beperking. Het is echter wel zo dat het basisonderscheid steeds deze is van “hard constraints” versus “soft constraints” en dat andere classificaties eigenlijk hetzelfde uitdrukken maar dan in een andere bewoording. Uit het gevoerde literatuuronderzoek is gebleken dat de volgende beperkingen (tabel 2) het meest voorkwamen. Merk wel op dat de minder relevante beperkingen, vanuit het standpunt van dit onderzoek, reeds werden verwijderd. 1

Minimale personeelsvereisten

2

Opeenvolgende dagen die werknemers mogen werken

3

Het aantal vrije dagen die een werknemer moet krijgen tijdens de planningsperiode

4

Werknemers moeten hun contractueel bepaald aantal uren werken

5

Limiet op het aantal interim-werknemers

6

Elke werknemer wordt elke dag toegewezen aan een shift of vrije dag

7

Verbod op voorwaartse rotatie (bv. Shift 3 die gevolgd wordt door shift 1 de volgende dag)

8

Limiet op het teveel aan werknemers

9

Het aantal vrije weekends gedurende de planningsperiode

Tabel 2: Beperkingen

Tabel 3 omvat voor elke beperking een aantal voorbeelden van papers waarin deze beperking voorkomt. Merk op dat de getallen overeenkomen met de beperkingen uit tabel 2. Het getal 1 verwijst dus naar de beperking die betrekking heeft op de minimale personeelsvereisten. 1

Brusco en Jacobs (1993), Brusco en Johns (1996), Musliu et al. (2004), Bard en Purnomo (2006 en 2007)

2

Hung (1999), Billionnet (1999), Housos en Valouxis (2000) en Miller et al. (1976)

3

Hung (1999), Billionnet (1999) en Miller et al. (1976)

4

Bard en Purnomo (2006 en 2007) en Millar en Kiragu (1998)

5

Bard en Purnomo (2006 en 2007)

6

Housos en Valouxis (2000) en Bard en Purnomo (2006 en 2007)

7

Housos en Valouxis (2000) en Bard en Purnomo (2006 en 2007)

8

Bard en Purnomo (2006 en 2007)

9

Miller et al. (1976) en Bard en Purnomo (2006 en 2007)

Tabel 3: bijhorende papers 6

De bovenstaande beperkingen werden vervolgens vergeleken met de lijst van de meest voorkomende beperkingen, bij het opstellen van personeelsschema’s voor verplegend personeel, volgens Cheang et al. (2003). De onderstaande tabel (tabel 4) geeft een weergave van de zestien belangrijkste beperkingen. Cheang et al. (2003) besloten vervolgens dat beperkingen 1, 3, 5, 6, 7, 8, 10, 14 en 16 het meest aanwezig zijn in de literatuur. Deze zullen dan ook, al dan niet in aangepaste vorm, in het onderstaande model verwerkt worden (zie sectie 3). 1

Minimale/Maximale werklast

2

Minimaal/Maximaal/Exact aantal opeenvolgende shifts van hetzelfde type

3

Minimaal/Maximaal/Exact aantal opeenvolgende werkende shifts/dagen

4

Ervaringsniveaus en categorieën

5

Preferenties of vereisten

6

Minimaal/Maximaal aantal (opeenvolgende) vrije dagen

7

Minimaal aantal uren tussen twee werkende shifts

8

Maximaal aantal toewijzingen aan een bepaald shift type, vereisten voor elk shift type

9

Vakantie

10

Beperkingen die betrekking hebben op weekends gedurende dewelke werknemers moeten werken, bijvoorbeeld, complete weekends. Een compleet weekend betekent dat een werknemer zowel zaterdag als zondag moet werken.

11

Beperkingen die gelden over verschillende werknemers, bijvoorbeeld: verpleegsters die niet mogen samenwerken

12

Shift patronen

13

Historische records, bijvoorbeeld: vorige toewijzingen

14

Andere vereisten die betrekking hebben over een andere tijdspanne dan de eigenlijke planningsperiode

15

Beperkingen over verschillende shifts, bijvoorbeeld: twee shifts kunnen niet toegewezen worden aan een persoon op hetzelfde moment

16

Minimaal/Maximaal/Exact aantal vereiste werknemers over verschillende shifts

Tabel 4: meest voorkomende beperkingen

Verder blijkt uit de literatuurstudie dat de typische lengte van een planningsperiode 4 weken bedraagt (Burke et al. 2004) en dat de lengte van één cyclische periode dikwijls de helft is van de lengte van de volledige planningshorizon (Bard en Purnomo 2007). In dit onderzoek wordt een model opgesteld met drie shifts van telkens acht uur. Merk wel op dat met bepaalde zaken hier geen 7

rekening gehouden wordt. Voorbeelden hiervan zijn de planning van pauzes of de start –en eindtijden van shifts. De achterliggende reden is dat het uitsluitend de bedoeling is om tot een aantal algemene conclusies te komen omtrent cyclische versus niet cyclische personeelsplanning en dit onder verschillende omstandigheden in de vraag naar werknemers. Bovendien zijn zaken zoals planning van pauzes en de duur ervan zeer bedrijfsspecifiek. Het model kan echter gemakkelijk uitgebreid worden zodat deze aspecten wel in rekening gebracht kunnen worden. Dit is dus zeker geen beperkende factor. Nog is het belangrijk voor het model om te bepalen of er al dan niet met meerdere ervaringsniveaus (onder andere Billionnet 1999, Cheang et al. 2003) zal worden gewerkt. Aangezien het weinig realistisch is dat er slechts één type werknemers zou werken in een bepaald bedrijf, wordt gebruik gemaakt van twee ervaringsniveaus. Een gerelateerde beslissing is de manier waarop deze ervaringsniveaus met elkaar interageren. Met andere woorden, is het al dan niet toegelaten dat een werknemer van het hoogste ervaringsniveau werk uitoefent dat normaal door een werknemer van een lager niveau uitgevoerd wordt? Ook moet er beslist worden hoe deze interactie dan zou plaatsvinden. Deze interactie/substitutie wordt in de literatuur “downgrading” genoemd. Bard en Purnomo (2005) identificeren drie manieren waarmee omgegaan kan worden met verschillende ervaringsniveaus. Ten eerste kan men de ervaringsniveaus volledig afzonderlijk behandelen. Men zorgt er dan enkel voor dat de vraag naar werknemers binnen dat bepaalde ervaringsniveau voldaan wordt. Dit is de eenvoudigste methode maar leidt wel tot suboptimale resultaten. Een tweede mogelijkheid is “sequential downgrading” of sequentiële substitutie, dit wil zeggen dat men er eerst voor zorgt dat de vraag naar werknemers voor het hoogste ervaringsniveau voldaan is. Indien er nog vrije werknemers van het hoogste ervaringsniveau zijn, kunnen deze ingezet worden voor het werk dat normaal uitgevoerd wordt door werknemers van een lager ervaringsniveau. De laatste mogelijkheid is deze van de “combined downgrading” of gecombineerde substitutie. Bij deze methode worden de verschillende ervaringsniveaus tegelijkertijd bekeken. Uit de resultaten van de testen die Bard en Purnomo (2005) uitgevoerd hebben, blijkt dat gecombineerde substitutie leidt tot de beste resultaten in het geval van twee ervaringsniveaus. In het model wordt er, zoals reeds vermeld, ook rekening gehouden met twee ervaringsniveaus. Deze keuze werd gemaakt om tot algemene resultaten te kunnen komen en het model niet nodeloos complex te maken. Door deze keuze en de resultaten van Bard en Purnomo (2005) werd er dan ook voor gekozen om met gecombineerde substitutie te werken. Meer uitleg over gecombineerde substitutie zal in deel 3 verschaft worden.

8

Personeelsplanning (in de gezondheidszorg) is typisch “NP-hard” (onder andere Maenhout en Vanhoucke 2010b). Dit betekent dat het niet mogelijk is om een oplossing te vinden binnen een redelijke tijdspanne zonder het gebruiken van een speciale techniek zoals bijvoorbeeld integere programmering. Er zijn verschillende mogelijkheden om een mathematisch model voor personeelsplanning op te lossen. In deze paper wordt de classificatie van Burke et al. (2004) gebruikt. De belangrijkste klassen uit de paper van Burke et al. (2004) voor dit onderzoek zijn de optimalisatieprocedures, zoals integere programmering; en metaheuristieken. Deze zijn het belangrijkste aangezien het de bedoeling is om tot de best mogelijke oplossing te komen (optimalisatieprocedures) of indien dit niet mogelijk is om tot een oplossing te komen die het optimum zo goed mogelijk benaderd. Metaheuristieken zijn, volgens Burke et al. (2004), immers in staat om tot aanvaardbare oplossingen te komen voor modellen die onderworpen zijn aan zeer veel beperkingen. Aangezien personeelsplanning aan zo’n groot aantal beperkingen onderworpen is, kunnen metaheuristieken een oplossing zijn indien er geen optimale oplossing kan gevonden worden. Bekende optimalisatieprocedures voor integere programmering zijn “branch and bound”, “branch and cut” (zie ook o.a. Hoffman en Padberg 1993) en “branch and price” (zie ook o.a. Maenhout en Vanhoucke 2010b). Deze methodes worden ook onder andere nog vermeld in het werk van Ernst et al. (2004) en Bard en Purnomo (2006). Bard en Purnomo (2006) stellen verder dat deze optimalisatieprocedures typisch een bepaalde vorm van decompositie omvatten, zoals kolomgeneratie. Kolomgeneratie wordt in verschillende papers vermeld (o.a. Aickelin en White 2004, Bard en Purnomo 2005a/2005b en Fisher 1981) en betekent dat voor elke werknemer minstens één subprobleem

zal

opgesteld

worden.

Dit

subprobleem

bevat

dan

de

specifieke

beperkingen/preferenties voor de betrokken werknemer. Hierover volgt meer uitleg in deel 5 (“Branch and price” methode). De tweede relevante klasse van oplossingsprocedures is die van de metaheuristieken, zoals “simulated annealing”. Andere veel voorkomende metaheuristieken zijn “tabu search” (bv. Gärtner et al. 2001, Alfares 2004 en, Dowsland en Thompson 2000) en genetische algoritmes (Alfares 2004). Een mogelijke derde klasse, die enkel heel kort vernoemd wordt in het werk van Burke et al. (2004), zijn die van de hybride methodes. Deze methodes zijn combinaties van verschillende oplossingsmethodes. Een aantal auteurs hebben hieromtrent een aantal voorstellen gedaan, zoals Housos en Valouxis (2000), Musliu (2006) en Levine (1996). Het opzet van dit onderzoek houdt in dat een aantal conclusies moet kunnen getrokken worden over de geschiktheid van een cyclisch personeelsschema rekening houdend met fluctuaties in de personeelsvereisten. Om dit te kunnen doen, moeten verschillende personeelsvereisten gegenereerd 9

worden. In lijn met Vanhoucke en Maenhout (2009) worden drie parameters gebruikt om deze personeelsvereisten te kunnen genereren. Deze parameters kunnen elk een waarde hebben van 0 tot en met 1. De relevante formules, opgesteld door deze auteurs, om deze parameters te berekenen, zijn terug te vinden in appendix A. De eerste is de “Total Coverage Constrainedness” of TCC. Deze parameter geeft een indicatie over het gemiddelde van het aantal werknemers die gebruikt worden over de verschillende shifts en dagen. Indien TCC gelijk is aan 1, betekent dit dat het aantal werknemers die per dag ingezet worden precies gelijk is aan het gemiddelde van de som van de vereisten over verschillende dagen. Een voorbeeld wordt gegeven in onderstaande tabel. Dag 1 Shifts

Dag 2

Dag 3

Dag 4

Dag 5

Dag 6

Dag 7

S1 S2 S3 S1 S2 S3 S1 S2 S3 S1 S2 S3 S1 S2 S3 S1 S2 S3 S1 S2 S3

Vereisten 3

3

3

3

2

2

2

3

2

2

2

3

3

3

1

2

3

2

2

2

1

Tabel 5: voorbeeld TCC

Uit tabel 5 blijkt dat de som van de personeelsvereisten 49 is. Dit betekent dat de gemiddelde personeelsvereiste per dag 7 is. Als we nu ook 7 werknemers zouden hebben, dan is TCC=1. De tweede parameter is de “Day Coverage Distribution” of DCD. Dit geeft een weergave van de verdeling van de personeelsvereisten over de verschillende dagen. Indien DCD gelijk zou zijn aan 0, dan zou elke dag een totale personeelsvereiste hebben van precies 7 werknemers. Echter, wanneer DCD én TCC gelijk zijn aan 1, dan zou de personeelsvereiste van 49 volledig over de drie shifts van één bepaalde dag verdeeld worden. Bij lagere waarden voor TCC zal de personeelsvereiste nog altijd maximaal zijn maar dan voor meerdere dagen. De laatste parameter is de “Shift-Coverage Distribution” of SCD. Deze parameter geeft een indicatie over de verdeling van het dagelijks vereiste aantal werknemers over de verschillende shifts. Indien SCD gelijk is aan 0, dan zullen de personeelsvereisten gelijk verdeeld zijn over de verschillende shifts. Dit is bijvoorbeeld het geval voor dag 1 in tabel 5. Opnieuw geldt dat wanneer SCD 1 zou zijn, dat de volledige personeelsvereiste voor één dag zou toegewezen worden aan één bepaalde shift op die dag. Om uiteindelijk de oplossing van het model te kunnen beoordelen moeten een aantal criteria gebruikt worden. Deze criteria moeten het ook mogelijk maken om een relevante vergelijking te maken tussen de oplossingen van de verschillende modellen, i.e. modellen met verschillende graden van cycliciteit en met verschillende personeelsvereisten (verschillende waarden voor TCC, DCD en SCD). Op die manier is het de bedoeling om tot een aantal algemene conclusies te komen omtrent 10

de toepasbaarheid van cyclische personeelsplanning onder deze verschillende omstandigheden (verschillende TCC, DCD en SCD waarden). Warner (1976) definieert de kwaliteit van een personeelsplan als de individuele beoordeling van het personeelsplan. Deze individuele beoordeling betekent dat de kwaliteit vanuit het oogpunt van de werknemer wordt bestudeerd. Volgens Maenhout en Vanhoucke (2007) is de kwaliteit van een personeelsplan de mate waarin aan de persoonlijke preferenties van de individuele werknemers wordt voldaan. Dit terwijl zoveel mogelijk aan de gestelde beperkingen van het model wordt voldaan. Het eerste deel van de definitie van Maenhout en Vanhoucke (2007) ligt met andere woorden in lijn met die van Warner (1976). Bard en Purnomo (2007) zien kwaliteit ook als het al dan niet overtreden van de individuele preferenties van de werknemers. Daarenboven wordt bij hen kwaliteit ook mede gedefinieerd door het aantal werknemers die teveel werken tijdens de verschillende shifts over de verschillende dagen en door het aantal werknemers die er tekort zijn tijdens de shifts over de verschillende dagen. Kwaliteit is echter slechts één van de meerdere criteria die beoordeeld moeten worden. Gebaseerd op de criteria van Warner (1976) maken Burke et al. (2004) een onderscheid tussen vijf criteria die belangrijk zijn voor het bepalen van de personeelsplanning. De eerste is “coverage”. Dit criterium heeft betrekking op het verschil tussen het aantal geplande werknemers tijdens een bepaalde shift en de werkelijk benodigde werknemers. Ten tweede definiëren zij kwaliteit als rechtvaardigheid. Een derde belangrijk criterium is de stabiliteit. Dit verwijst onder andere naar de voorspelbaarheid vanuit het oogpunt van de werknemers van het personeelsplan. Het heeft dus te maken met de perceptie van de individuele werknemers. Een vierde criterium behandelt de flexibiliteit van het voorgestelde personeelsplan. Als laatste moet ook rekening gehouden worden met de kost. In deze context verwijst kost naar de tijd die nodig is om het model te kunnen oplossen.

3. Model In dit deel zal, rekening houdend met de vaststellingen uit de literatuurstudie, een model opgesteld worden. Het model dat hieronder weergegeven wordt, is gebaseerd op de modellen die gebruikt werden in verschillende papers van Bard en Purnomo (onder andere Bard en Purnomo 2006). Het model van Bard en Purnomo (2006) werd gekozen wegens de grote relevantie van de beperkingen die in dat model aanwezig zijn in vergelijking met de beperkingen uit tabel 2. Na vergelijking is het immers duidelijk dat al deze beperking ofwel expliciet of toch zeker impliciet in het model aanwezig zijn. Een beperking vanuit de tabel die bijvoorbeeld impliciet aanwezig is in het model, is het aantal vrije weekends gedurende de planningsperiode. In het model (beperking 1k) staat immers dat 11

werknemers slechts een maximaal aantal weekenddagen mogen werken, wat hetzelfde betekent als het aantal weekends dat een werknemer vrij moet zijn gedurende de planningsperiode. Er werden echter wel een aantal aanpassingen aan het originele model van Bard en Purnomo (2006) gemaakt. In lijn met Bard en Purnomo (2005) werden ook twee ervaringsniveaus toegevoegd, de reden hiervoor werd reeds behandeld in het vorige deel. Vervolgens is er aan de doelfunctie een term toegevoegd die uitdrukking heeft aan het feit dat het ook negatief is om meer werknemers in te plannen dan eigenlijk nodig. Beperking (1e) en (1f) zijn ook niet aanwezig in het model van Bard en Purnomo (2006). Het originele model stelt immers dat het aantal gewerkte uren van een werknemer precies gelijk moet zijn aan het contractueel vastgelegde aantal uren voor die werknemer. Door beperking (1d) aan te passen zodat er langer kan gewerkt worden, is er een toename aan flexibiliteit. Beperkingen (1e) en (1f) zorgen er dan voor dat het aantal overuren toch beperkt blijft. Verder is ook beperking (1j) belangrijk aangezien dit er voor zorgt dat de werknemers identieke toewijzingen krijgen in het weekend (shift 1 op zaterdag wordt gevolgd door shift 1 op zondag, hetzelfde geldt voor shift 2 en 3). Dit zorgt ervoor dat de werknemers tijdens het weekend niet geconfronteerd worden met een verandering in hun werkritme of dat ze het volledige weekend vrij kunnen zijn. Aangezien weekendwerk algemeen als onaangenaam gezien wordt, is de toevoeging van deze beperking zeker relevant. Nog een extra beperking is (1l). Deze zorgt ervoor dat er rekening gehouden wordt met de dagen waarop een werknemer liever niet wil werken. Ten slotte is hier gekozen om een planningsperiode van 28 dagen te nemen, zoals dikwijls het geval is (zie literatuurstudie). Aangezien Bard en Purnomo (2005) slechts een planningsperiode van 2 weken hebben, zorgt dit ervoor dat het aantal toegelaten preferentie-overtredingen, in onderstaand model, hoger zal liggen. Hier volgt in eerste instantie een verduidelijking van de verschillende indexen, parameters en beslissingsvariabelen die gebruikt worden in het model, waarna meer uitleg over de verschillende beperkingen volgt.

3.1 Indexen en sets i

index voor werknemers; i ∈ N;

D

index voor dagen; d ∈ D;

a

index voor het aantal preferentie-overtredingen; a= 1,…., Vmax;

ϴ

index

voor

het

aantal

ervaringsniveaus;

ervaringsniveau; 12

ϴ=1,….,

NSkills, met

1

het

hoogste

t

index voor de shifts; t ∈ T;

t1(t3)

eerste (derde) shift voor een werknemer die tijdens 2 opeenvolgende shift types werkt; t1(t3) ϵ Ti;

Ti

set van shift types waarvoor werknemer i aangenomen is, exclusief een vrije dag. De werknemer moet dus zelf rekening houden met welke shifts hij of zij al dan niet wil werken;

T

set van alle mogelijke shift types, inclusief een vrije dag;

DW

set van weekenddagen gedurende de planningsperiode; Dw ⊆ D;

Dinot

set van dagen gedurende dewelke een werknemer i liever niet werkt; Dinot ⊆ D;

N

set van werknemers waaraan een schema moet toegewezen worden;

NR

set van werknemers die tijdens verschillende shifts kunnen werken; NR ⊆ N;

NBB

set van werknemers met shifts, over 2 verschillende dagen, die elkaar onmiddellijk opvolgen; NBB ⊆ NR ⊆ N;

D

set van dagen waarvoor het model opgelost moet worden;

3.2 Parameters Vmax

maximum aantal overtredingen die toegestaan worden voor elke werknemer;

raϴ

penalty toegewezen aan een schema die a overtredingen bevat; (ra1>ra2); raϴ=2a/ ϴ;

ryϴ

penalty toegewezen voor het inzetten van één of meerdere interim werknemers met ervaringsniveau ϴ; (ry1>ry2); ryϴ=M/(ϴ);

rsϴ

penalty toegewezen voor het teveel aan werknemers van ervaringsniveau ϴ; (rs1>rs2); rsϴ=M/(2+ϴ);

Hi

aantal uur waarvoor werknemer i is aangenomen;

ht

lengte van de shift t;

LDdtϴ

ondergrens voor vraag naar personeelsleden met ervaringsniveau ϴ voor shift t op dag d;

UDdtϴ bovengrens voor vraag naar personeelsleden met ervaringsniveau ϴ voor shift t op dag d; Di,maxon maximum aantal opeenvolgende dagen dat werknemer i mag werken; 13

Pit

minimum aantal shifts van type t die werknemer i moet werken;

Wi,max aantal weekendshifts die werknemer i maximum mag werken tijdens weekends in de planningsperiode (Assumptie: Wi,max is een veelvoud van 2, op deze manier is het gemakkelijker om identieke weekends af te dwingen); TRmax

maximum

aantal

shiftveranderingen

over

opeenvolgende

dagen

toegelaten gedurende de planningsperiode; Odt,maxϴ maximum aantal interim werknemers van ervaringsniveau ϴ die toegewezen kunnen worden aan shift t op dag d; Maxh

maximum aantal uren dat een werknemer mag overwerken gedurende de planningsperiode. Hierbij wordt rekening gehouden met de lengte van de shifts. Zo wordt een volledige shift als overuren geklasseerd als de werknemer reeds zijn/haar contractuele uren heeft gewerkt.

3.3 Beslissingsvariabelen xidtϴ

1 als werknemer i met ervaringsniveau ϴ werkt tijdens shift t op dag d, anders 0;

viaϴ

1 als werknemer i met ervaringsniveau ϴ a overtredingen heeft in zijn of haar schema, anders 0;

bid

1 als werknemer i ∈ NR werkt tijdens shift ta op dag d en shift tb op dag d+1 waarbij a≠b, anders 0;

pid

1 wanneer werknemer i een 0-1-0 patroon heeft dat start op dag d, anders 0;

qid

1 wanneer werknemer i een 1-0-1 patroon heeft dat start op dag d, anders 0;

oi

1 wanneer werknemer i het maximum aantal overuren gewerkt heeft gedurende een planningsperiode, anders 0;

gid

1 wanneer werknemer i moet werken op een dag waarop hij of zij liever niet werkt, anders 0;

ydtϴ

aantal interim werknemers met ervaringsniveau ϴ toegewezen aan shift t op dag d;

sdtϴ

aantal werknemers met ervaringsniveau ϴ die teveel zijn toegewezen aan shift t op dag d;

14

3.4 Model NSkills

Min

 ( z =  1

Vmax

 r v  r  y iN a 1

a

ia

y

dt

dD tTi

 rs  sdt )

(1a)

dD tTi

s.t. 





q 1

q 1

q  sdt   xidt   ydtq   LDdtq , d  D, t  Ti ,   1,..., NSkills

(1b)

 x

(1c)

q 1 iN

dD

 Pit , i  N , t  Ti ,   1,..., NSkills

idt

 h x

 H i , i  N ,  1,..., NSkills

(1d)

 h x

 H i  Maxh , i  N ,  1,..., NSkills

(1e)

t

dD tTi

t

dD tTi

idt

idt

 Maxh  (  ht xidt  H i )  oi  1, i  N ,   1,..., NSkills

(1f)

 x

(1g)

dD tTi

tT

 1, i  N , d  D,  1,..., NSkills

idt

 xidt  xi,d 1,t1  1, i  N BB , d  D,  1,..., NSkills 3 d  Di , max on

 x

ilt

l d tTi

 Di ,max on , i  N , d  D,   1,..., NSkills

 xidt  xi,d 1,t , i  N , d  DW , t  T ,  1,..., NSkills

  x

dDW tTi

idt

 Wi ,max , i  N ,   1,..., NSkills

(1h)

(1i)

(1j) (1k)

 1   xidt  gid  1, i  N , d  Dinot ,   1,..., NSkills

(1l)

 x

(1m)

tTi

tTi

idt

 (1   xi,d 1,t )   xi,d 2,t  pid  1, i  N , d  D,   1,..., NSkills tTi

tTi

 (1   xidt )   xi,d 1,t  (1   xi,d 2,t )  qid  1, i  N , d  D,   1,..., NSkills

(1n)

 1  xidt  1  xi,d 1,t  bid  1, i  N R , d  D,    Ti ,  1,..., NSkills 

(1o)

b

(1p)

tTi

dD

id

tTi

tTi

 TRmax , i  N R 15

Vmax

 ( pid  qid  bid  gid  oi )   avia , i  N

dD Vmax

 v a 1

(1q)

a 1

ia

 1, i  N

(1r)





q 1

q 1

0  sdt  UDdtq   LDdtq ,0  y dt  Odt ,max , d , t;  1,..., NSkills

(1s)

pid , qid , bid , gid , oi {0,1}, i, d ; via {0,1}, a, i

(1t)

 xidt  {0,1}, i, d , t : xi,lengteplanningsperiodel ,t  xilt , l  1,..., Di ,max on

  1,..., NSkills

(1u)

3.5 Uitleg bij model (1a)

De doelfunctie minimaliseert de kosten die gepaard gaan met overtredingen van preferenties van de werknemers en deze voor het inzetten van interim werknemers. Bovendien wordt er ook rekening gehouden met de kosten voor het gebruik van te veel werknemers. De kosten die toegekend worden aan het teveel en tekort, werden vermeld bij de parameters hierboven. Merk wel op dat de kosten voor een tekort aan werknemers hoger zullen zijn dan een teveel aan werknemers. Het is immers slechter voor het bedrijf om te weinig werknemers beschikbaar te hebben dan te veel. Verder geldt er een exponentieel principe voor de kost die toegekend wordt aan het aantal overtredingen van preferenties. Hoe meer preferentie-overtredingen er zijn, hoe hoger de penalty zal zijn (raϴ=f(a, ϴ)) . Merk wel op dat voor het tekort en teveel aan werknemers geen gebruik gemaakt wordt van zo’n exponentieel principe. Doordat uiteindelijk de focus ligt op een afweging tussen cycliciteit en preferenties is er voor gekozen om de M gelijk te stellen aan 10000. Dit heeft tot gevolg dat tot een bepaald niveau het tekort/teveel aan werknemers belangrijker zal zijn dan preferentie-overtredingen. Eenmaal een bepaald punt in het aantal preferentie-overtredingen overschreden wordt, zullen echter het aantal preferenties belangrijker worden. Bovendien is er een verschil tussen de kosten, verbonden aan de verschillende termen van de doelfunctie, rekening houdend met de ervaringsniveaus. Vanzelfsprekend is het erger om een tekort/teveel te hebben aan werknemers met het hoogste ervaringsniveaus. Dit is ook het geval voor het aantal overtredingen van de individuele preferenties. In beide gevallen zal er bijgevolg een hogere kost in de doelfunctie verschijnen.

16

(1b)

Deze beperking is ingevoegd om ervoor te zorgen dat er voldoende werknemers aanwezig zijn met de juiste vaardigheden. In dit model wordt, zoals eerder vermeld, gebruik gemaakt van gecombineerde substitutie. Deze vorm van substitutie werkt als volgt: Indien het ervaringsniveau gelijk is aan 1, dan geldt het volgende: 1  s1dt   xidt  y1dt  LDdt1 , d  D, t  Ti iN

Wanneer het ervaringsniveau echter 2 is, dan geldt het volgende: 1 2  sdt2   ( xidt  xidt )  ( y1dt  ydt2 )  LDdt1  LDdt2 , d  D, t  Ti iN

Voor lagere ervaringsniveaus zal de vraag naar werknemers voor dat lagere niveau en alle hogere niveaus gezamenlijk worden bekeken. Op deze manier kan een werknemer van het hoogste ervaringsniveau die eigenlijk als “werknemer teveel” geboekt staat in zijn of haar ervaringsklasse toch ingezet worden en kan een tekort op een lager ervaringsniveau misschien vermeden worden. (1c)

Een werknemer moet een, vooraf bepaald, aantal shifts van een bepaald type werken gedurende de planningsperiode. Deze zijn contractueel bepaald. Dit kan dan ook gezien worden als een preferentie waaraan voldaan moet worden. Werknemers kunnen immers op het moment dat ze aangenomen worden mee beslissen, of toch ten minste onderhandelen, over de shifts die ze willen of moeten werken.

(1d)

Een werknemer moet minstens zijn of haar contractueel bepaald aantal uren werken gedurende de planningsperiode.

(1e)

Het aantal overuren dat een werknemer kan werken is beperkt. Hier wordt verondersteld dat het aantal overuren die werknemers werken steeds een veelvoud is van de lengte van een normale shift. In deze paper wordt het maximaal aantal overuren gelijk gesteld aan de lengte van precies 1 shift, dus 8 uur.

(1f)

Wanneer het maximaal aantal overuren gewerkt wordt dan wordt oi gelijk aan 1. Op die manier wordt een preferentie-overtreding in rekening gebracht.

(1g)

Elke werknemer moet per dag precies één shift toegewezen krijgen. Dit wil zeggen dat elke werknemer niet meer dan één shift mag werken op een bepaalde dag. Hier wordt er voor gekozen om een vrije dag te behandelen als een aparte shift van 24h. 17

(1h)

Deze beperking moet vermijden dat een werknemer 2 opeenvolgende shifts moet werken die verspreid zijn over 2 verschillende dagen. Voorwaartse rotatie van de laatste shift op een bepaalde dag naar de eerste shift op de volgende dag wordt, met andere woorden, dus vermeden.

(1i)

Elke werknemer wordt onderworpen aan een maximaal aantal opeenvolgende dagen dat die persoon mag werken. Stel echter dat het maximaal opeenvolgende dagen vijf is en dat een werknemer de vier laatste dagen van de planningsperiode werkt, dan mag deze werknemer in de volgende planningsperiode de eerste twee dagen niet tweemaal werken.

i, d , t : xi,lengteplanningsperiodel ,t  xilt , l  1,..., Di ,max on

  1,..., NSkills De bovenstaande beperking, i.e. beperking (1u) in het model, houdt hier rekening mee. Zij zorgt ervoor dat op het einde van de planningsperiode ook de overschakeling naar de volgende periode in rekening gebracht wordt. Er kan dus geen sprake zijn van een overtreding van het maximaal opeenvolgende dagen over twee planningsperiodes. (1j)

Dit is de identieke weekend beperking. Deze beperking zorgt ervoor dat een werknemer tijdens een weekend zowel zaterdag als zondag werkt of dat hij/zij zowel zaterdag als zondag een vrije dag heeft. Bovendien zal, indien de werknemer werkt tijdens het weekend, hij of zij zowel zaterdag als zondag tijdens dezelfde shift werken.

(1k)

Deze beperking stelt dat een werknemer maximum Wi,maxon weekenddagen mag werken. Assumptie: Wi,maxon is een veelvoud van twee. Deze assumptie is nodig zodat beperking (1j) niet kan overtreden worden. Aangezien de lengte van de planningsperiode hier 28 dagen is, is het maximaal toegelaten aantal werkende weekenddagen gelijk aan 4.

(1l)

Wanneer een werknemer moet werken op een dag waarop hij/zij liever niet zou werken dan moet gid 1 zijn.

(1m)

Deze beperking stelt dat wanneer een werknemer een 0-1-0 patroon heeft dat de beslissingsvariabele pid 1 moet zijn. Deze beperking is belangrijk omdat zo’n patroon de continuïteit zeker niet ten goede komt.

(1n)

Deze beperking stelt dat wanneer een werknemer een 1-0-1 patroon heeft dat de beslissingsvariabele qid 1 moet zijn. Opnieuw bevordert deze beperking de continuïteit voor de werknemers. 18

(1o)

Deze beperking stelt dat wanneer een werknemer tijdens shift tα werkt op dag d en tijdens shift tβ op dag d+1 dat de beslissingsvariabele bid 1 moet zijn, waarbij tα en tβ niet aan elkaar gelijk zijn. De variabele bid telt op deze manier het aantal maal dat een werknemer tijdens de planningsperiode van shift verandert.

(1p)

Het aantal shiftwisselingen moet beperkt zijn voor elke werknemer.

(1q)

Deze beperking zorgt ervoor dat het aantal preferentie-overtredingen niet groter is dan het maximaal toegelaten aantal overtredingen.

(1r)

viaϴ kan enkel 1 zijn wanneer er exact a overtredingen zijn, viaϴ zal dus niet 1 zijn wanneer er bv. (a-1) overtredingen zijn. Deze beperking zorgt ervoor dat de kost in de doelfunctie een juiste weergave is van het aantal overtredingen. Om dit ietwat te verduidelijken volgt een kort voorbeeld: Stel dat het totaal aantal overtredingen gelijk is aan 6 en gegeven beperking (1q), dan zou het mogelijk zijn dat het volgende voorkomt: 6 = 1*0 +2*1 + 3*0 + 4*1 + … +Vmax*0 Dit zou leiden tot een onderschatting van de kost aangezien 26>(22 + 24).

(1s)

Het overschot aan werknemers dat tijdens een shift aan het werk is, mag niet groter zijn dan het verschil tussen de bovengrens en de normale personeelsvereiste tijdens die shift. Dit verschil is gelijk aan 25% van de personeelsvereiste tijdens die specifieke shift. Merk hier op dat voor het teveel aan werknemers voor een ervaringsniveau dat lager is dan het hoogste, de som van deze onder –en bovengrens voor dat lagere en al de hogere ervaringsniveaus wordt genomen. Dit is nodig omdat werknemers die teveel zijn op het hoogste niveau op een lager niveau kunnen werken en er op dat lager niveau daardoor misschien een overschot aan werknemers wordt gevormd. Ook wordt er een beperking opgelegd op het aantal interim werknemers die ingezet worden om tekorten op te vangen. Opnieuw is dit maximum gelijk aan 25% van het vereiste aantal werknemers gedurende die bepaalde shift. Op die manier zullen de personeelsvereisten gewaarborgd worden tot 75% van de werkelijke vereiste.

(1t)

Deze beperking dwingt af dat de vermelde variabelen binair zijn.

(1u)

De beslissingsvariabele xidtϴ moet binair zijn en de tweede beperking is nodig om de continuïteit over opeenvolgende planningsperiodes te waarborgen.

Merk op dat, aangezien er reeds veel preferenties expliciet in rekening genomen worden, het model geen algemene preferentiescores bevat. Indien deze algemene preferentiescores toch in het model zouden opgenomen worden, dan zou er eigenlijk sprake zijn van dubbeltelling van preferenties. Deze 19

preferentiescores houden immers in dat de shifts die een werknemer het liefst wil werken de laagste score krijgen en dat de minst aantrekkelijke shifts de hoogste scores krijgen. Echter in dit model wordt aangenomen dat werknemers bij het bepalen van hun contractuele verplichtingen inspraak hebben bij de shifts die ze al dan niet werken (zie beperking (1c)). Werknemers kunnen dus zelf mee bepalen hoeveel maal ze elke shift gedurende de planningsperiode minstens willen/moeten werken. Op die manier wordt rekening gehouden met het feit dat bepaalde shifts beter betaald worden (bv. nachtshifts) en bepaalde werknemers deze soms liever werken dan de andere, minder goed betaalde shifts. Ook het feit dat dagen, die werknemers liever niet willen werken, in rekening gebracht worden ondersteunt deze keuze.

3.6 Uitleg bij model Cycliciteit kan onder verschillende vormen voorkomen. Hieronder worden 3 verschillende vormen kort besproken. Merk op dat de eerste vorm gebaseerd is op het eerder gegeven voorbeeld in tabel 1 en dat we dus veronderstellen dat de planningsperiode drie weken bedraagt in plaats van de gebruikelijke vier. 1. Zoals reeds vermeld, vormt tabel 1 het meest gewone voorbeeld van een cyclische personeelsplanning waarbij werknemers binnen één en dezelfde periode allen dezelfde schema’s doorlopen. Stel dat het voorbeeld shift1-shift2-shift3 een schema voorstelt dan zullen de werknemers dit in de volgende planningsperiode ook doorlopen. Verder bouwend op het voorbeeld in tabel 1 krijgen we dan tabel 6. Planningsperiode 1

Planningsperiode 2

Planningsperiode 3

Werknemer 1

Shift 1-Shift 2-Shift 3



Werknemer 2




Werknemer 3




Tabel 6: voorbeeld normaal cyclisch schema

2. Een tweede mogelijkheid is dat elke werknemer een afzonderlijk schema heeft tijdens een bepaalde planningsperiode. Na deze planningsperiode zal dat schema zich gewoon herhalen. Een gemakkelijk voorbeeld wordt gegeven in tabel 7. Planningsperiode 1

Planningsperiode 2

Planningsperiode 3

Werknemer 1




Werknemer 2




Werknemer 3




Tabel 7: voorbeeld aangepast cyclisch model

3. Een laatste mogelijkheid is dat de werknemers over de verschillende planningsperiodes wel volgens verschillende schema’s werken maar dat binnen dezelfde planningsperiode de 20

verschillende werknemers allen verschillende schema’s hebben. Tabel 8 toont opnieuw een eenvoudig voorbeeld om dit te illustreren. Elke werknemer zal dus na verloop van tijd dezelfde schema’s hebben doorlopen. Planningsperiode 1

Planningsperiode 2

Planningsperiode 3

Werknemer 1




Werknemer 2




Werknemer 3




Tabel 8: voorbeeld aangepast model

Merk op dat, zoals hierboven reeds vermeld, het belangrijk is om bij, onder andere, de beperking op het maximaal aantal opeenvolgende werkende dagen rekening te houden met het feit dat er gekeken moet worden naar de overgang met het volgende schema in de volgende planningsperiode. Een laatste belangrijke opmerking hieromtrent is dat deze drie verschillende vormen van cycliciteit een iets andere invloed zullen hebben op de beperkingen die in het mathematisch model zitten. Denken we hierbij aan de volgende beperkingen: 

Beperking (1h): voorwaartse rotatie van de laatste shift op de laatste dag van de planningsperiode naar de eerste shift op de eerste dag van de volgende planningsperiode.



Beperking (1i): maximaal opeenvolgende dagen die een werknemer mag werken. Vanaf het moment dat dag d = (planningsperiode-maximaal opeenvolgende werkende dagen), moet er overgeschakeld worden naar het schema van de volgende planningsperiode.



Beperkingen (1m) en (1n): 0-1-0 en 1-0-1 patronen moeten onderzocht worden over de verschillende planningsperiodes vanaf dag d = (planningsperiode - 2).



Beperking (1o): de shiftwisselingsbeperking moet ook gelden in de overgang van de ene planningsperiode naar de volgende. Als dag d = planningsperiode, dan moet er gekeken worden naar het schema dat de werknemer moet volgen in de volgende planningsperiode.

Het is dus heel belangrijk om de overgangen tussen twee planningsperiodes te controleren. Dit is zowel voor de eerste, tweede als laatste vorm van cycliciteit het geval. Bovendien is er voor de laatste vorm van cycliciteit een extra moeilijkheid. Deze wordt veroorzaakt doordat de werknemer in de volgende planningsperiode het schema van een andere werknemer overneemt. Merk op dat wanneer overgangen vermeld worden dat dit telkens betrekking heeft op het volgende deel van beperking (1u).

i, d , t : xi,lengteplanningsperiodel ,t  xilt , l  1,..., Di ,max on

  1,..., NSkills

21

De beperking, zoals ze in deze vorm staat, is hier van toepassing op de eerste twee mogelijke vormen van een cyclisch personeelsplan. Voor de derde vorm geldt de volgende beperking:

d , t : xi,lengteplanningsperiodel ,t  xjlt , l  1,..., Di ,max on

  1,..., NSkills; i  j  N Hoewel de eerste vorm van cycliciteit de perceptie kan opwekken dat zij de meest rechtvaardige is, zal zij toch niet gebruikt worden in dit onderzoek. De reden hiervoor is dat we opteren voor een combinatie van een cyclisch schema en rekening houden met preferenties. Aangezien onder deze vorm van cycliciteit, elke werknemer hetzelfde schema doorloopt en dit schema dus zeer restrictief is, zal er niet voldoende rekening gehouden worden met de preferenties en dit is zeker niet de bedoeling. Voor de derde vorm van cycliciteit geldt dezelfde opmerking als voor de eerste vorm. Namelijk dat zij te weinig rekening houdt met de individuele preferenties van de werknemers. Merk op dat in het vervolg van deze paper (deel 6: Cycliciteitsonderzoek) de focus op de tweede vorm van cycliciteit zal liggen. Het is de bedoeling om voor de gegeven planningsperiode een zo optimaal mogelijk schema te vinden, rekening houdend met de preferenties van de werknemer. Dit schema zal zich dan, normaal gezien, tijdens de volgende planningsperiode herhalen. Aangezien preferenties over de tijd wel kunnen veranderen, is het wel mogelijk dat dit ervoor zorgt dat in een latere planningsperiode het personeelsschema verandert. Dit is in dit geval echter wel gebaseerd op de individuele preferenties van de werknemers waardoor er geen sprake kan zijn van problemen vanuit het standpunt van de werknemers. Doordat de focus op deze vorm van cycliciteit zal liggen is een extra beperking nodig. Zoals in het literatuuronderzoek reeds werd vermeld is de lengte van één cyclische periode dikwijls de helft van de totale planningsperiode. De volledige planningsperiode wordt dus in twee gesplit maar de preferenties over deze twee cyclische periodes blijven wel verschillen. Op deze manier wordt voor de volledige maand het optimale schema gezocht en niet alleen rekening gehouden met de eerste twee weken. 28

14

 x   x , i  N ,  1,..., NSkills

d 15 tT

idt

d 1 tT

idt

(1v)

4. Oplossingen Gurobi Solver voor gewoon model In dit deel volgt een bespreking van de resultaten die met de Solver bekomen werden en wordt aangetoond welke beperkingen de complexiteit van het probleem sterk verhogen. 22

Zoals reeds vermeld in de inleiding, is in eerste instantie gebruik gemaakt van de normale Solver in Microsoft Excel om het model uit deel 3 op te lossen. Deze heeft echter een beperking van 200 variabele cellen, wat ruim onvoldoende is rekening houdend met het feit dat de meest gebruikelijke lengte van een planningsperiode vier weken bedraagt, wat ook in dit model het geval is. Dit komt erop neer dat er, voor het opstellen van een schema voor 1 werknemer gedurende deze vier weken, (4 * 28 =) 112 variabele cellen nodig zijn. Het getal vier is afgeleid van het feit dat er uitgegaan wordt van drie shifts van 8 uur per dag en dat een vrije dag ook gezien wordt als een shift, maar dan met een lengte van 24 uur. Bovendien zijn er nog de variabelen om de preferenties van werknemers weer te geven en om andere overtredingen te tellen. Hiermee rekening houdend, kan besloten worden dat de gewone Solver veel te beperkt is voor het gegeven model. Door deze enorme beperkingen is er voor gekozen om naar een krachtigere Solver (Frontline Excel Solvers) over te schakelen. Deze Solver kan een maximum van 8000 variabele cellen en 8000 beperkingen aan, wat een enorme verbetering inhoudt. Bovendien maakt het gebruik van “branch and bound”-algortime om tot een oplossing te komen. Dat zo’n algoritme gebruikt wordt, is te zien in onderstaande resultaatstabellen. Deze tabellen vermelden immers het aantal subproblemen. Vanuit het onderzoeksopzet is er voor gekozen om het model stapsgewijs te implementeren om zo te weten te komen waar de mogelijke problemen met de beperkingen liggen. Er worden dus stapsgewijs nieuwe beperkingen toegevoegd volgens hun respectievelijke belang. Deze graduele toevoeging heeft tot gevolg dat de kwaliteit van de oplossing er gradueel op achteruit zal gaan. Het respectievelijke belang van de beperkingen werd afgeleid uit het aantal maal dat deze beperkingen voorkwamen in het bovenvermelde literatuuronderzoek. De resultaten staan in de tabel hieronder. Beperking

Belang

Minimale personeelsvereisten

1

Opeenvolgende dagen die werknemers mogen werken

3

Het aantal vrije dagen die een werknemer moet krijgen tijdens de planningsperiode

4

Werknemers moeten hun contractueel bepaald aantal uren werken

9

Limiet op het aantal interim-werknemers

8

Elke werknemer wordt elke dag toegewezen aan een shift of vrije dag

2

Verbod op voorwaartse rotatie (bv. Shift 3 die gevolgd wordt door shift 1 de volgende dag)

5

Limiet op het teveel aan werknemers

7

Het aantal vrije weekends gedurende de planningsperiode

6

Tabel 9: Beperking volgens belang (1 is hoogste-9 is laagste)

23

Merk wel op dat bepaalde beperkingen, zoals bijvoorbeeld de limiet op het aantal interimwerknemers en de limiet op het teveel aan werknemers, evenveel voorkwamen. Om toch een ranking te kunnen weergeven is daarom beslist dat een limiet op het teveel aan werknemers belangrijker is dan een limiet op het aantal interim, i.e. tekort aan normale, werknemers. Deze keuze kan gerechtvaardigd worden aangezien het voor een bedrijf erger is om te weinig werknemers aanwezig te hebben en het dus onder sommige omstandigheden minder interessant zou kunnen zijn om zo’n sterk restrictieve limiet te hebben. Deze gedachtegang wordt ook weerspiegeld in de kosten die toegekend worden aan respectievelijk het teveel en tekort aan werknemers. Om het model niet nodeloos ingewikkeld te maken is in dit eerste onderzoek een model geformuleerd dat bestaat uit 7 werknemers die allen hetzelfde ervaringsniveau hebben. Wel is de planningsperiode onmiddellijk al gelijk gesteld aan de normale vier weken.

4.1 Minimum vereist aantal werknemers per shift (beperking (1b)) In onderstaande tabel (tabel 10) wordt de vraag weergegeven die gebruikt werd om het model op te lossen. Deze getallen werden random, met een maximum van drie, gegenereerd. Shift 1

Shift 2

Shift 3

Dag 1

1

3

2

Dag 2

2

3

1

Dag 3

2

3

2

Dag 4

1

3

1

Dag 5

3

2

2

Dag 6

1

2

1

Dag 7

1

2

1

Tabel 10: vraag naar werknemers

Voor de eenvoud zijn de volgende drie weken aan dezelfde vraag onderworpen. Het oplossen van het model met enkel deze beperking gaf het volgende resultaat. De kosten verbonden aan het tekort aan werknemers is 50 per werknemer tekort. Voor het teveel aan werknemers geldt een kost van 5 per werknemer teveel.

24

Result: Solver found an integer solution within tolerance. All constraints are satisfied. Engine: Standard LP/Quadratic Solution Time: 00 Seconds Iterations: 0 Subproblems: 0 Incumbent Solutions: 0

Objective Cell (Min) Cell

Name

Original Value

Final Value

$AF$24

Totaal te minimaliseren

7200

0

Tabel 11: resultaat model

4.2 1 shift of vrije dag beperking (beperking (1g)) De variabelen worden, eerst en vooral, terug op 0 gezet zodat de Solver van dezelfde basis vertrekt. Dit zal in elk van de volgende stappen herhaald worden. In het bovenstaande model komt deze beperking overeen met het feit dat elke werknemer elke dag precies één toewijzing moet krijgen. Dit betekent dat de werknemer ofwel tijdens een bepaalde shift werkt ofwel een dag vrij heeft. Het model wordt nu opgelost met in acht name van beperkingen (1b) en (1g). Dit heeft het volgende als resultaat. Report Created: 16-11-2011 20:44:49 Result: Solver found an integer solution within tolerance. All constraints are satisfied. Engine: Standard LP/Quadratic Solution Time: 01 Seconds Iterations: 0 Subproblems: 0 Incumbent Solutions: 0


Name

Original Value Final Value

$AF$24


7200

200


Uit het resultaat blijkt dat, aangezien er een kost toegewezen is aan het teveel of te weinig aan werknemers, het niet meer mogelijk is om perfect aan de vraag te voldoen. 25

4.3 Maximaal opeenvolgende werkdagen (beperking (1i)) In dit model is ervoor gekozen om het maximum aantal opeenvolgende dagen te beperken tot vijf. De keuze voor maximaal vijf opeenvolgende werkdagen is hier voor de hand liggend aangezien een “5 dagen werken–2 dagen vrij” patroon immers in veel sectoren de regel is. Result: Solver found an integer solution within tolerance. All constraints are satisfied. Engine: Standard LP/Quadratic Solution Time: 01 Seconds Iterations: 0 Subproblems: 1 Incumbent Solutions: 1


Name

Original Value

Final Value

$AF$24


7200

200


Uit tabel 13 blijkt dat hier reeds sprake is van één subprobleem. Hoewel dit nog niet weerspiegeld wordt in de tijd nodig om het model op te lossen, betekent dit wel dat het moeilijker wordt om een geschikte oplossing te vinden.

4.4 Vrije dagen (beperkingen (1l), (1m) en (1n)) Deze beperkingen geven, op een impliciete wijze, de preferenties weer van de werknemers inzake vrije dagen. Beperking (1l) geeft bijvoorbeeld weer op welke dagen de werknemer liever niet werkt. Voor beperking (1l) zijn de volgende preferenties (tabel 14) voor vrije dagen gebruikt. Ook hier wordt er vanuit gegaan dat deze preferenties tijdens de vier weken van de planningsperiode hetzelfde blijven. In werkelijkheid is het zeer goed mogelijk dat de dagen waarop een werknemer liever niet werkt tijdens week 1 niet dezelfde zijn als die dagen in de andere weken. Beperkingen (1m) en (1n) moeten ervoor zorgen dat “niet werken-werken-niet werken” en “werken-niet werken-werken” patronen zoveel mogelijk vermeden worden.

26

Dagen die werknemer liever niet werkt Werknemer 1

Maandag en zaterdag

Werknemer 2

Dinsdag

Werknemer 3

Woensdag

Werknemer 4

Donderdag

Werknemer 5

Vrijdag, zaterdag en zondag

Werknemer 6

Zaterdag en zondag

Werknemer 7

Zondag Tabel 14: preferenties voor vrije dagen

Doordat we hier werken met preferentiebeperkingen moet ook beperking (1q) toegevoegd worden om ervoor te zorgen dat het aantal overtredingen minder is dan maximaal toegelaten. Bovendien zal nu ook het deel in de doelfunctie die een kost toewijst aan de overtredingen van preferenties geactiveerd moeten worden. Ook is het belangrijk om te melden dat er hier nog geen gebruik gemaakt wordt van een exponentiële toename in de kost naarmate meer preferenties overtreden worden. Het maximaal aantal overtredingen dat hier nog toegelaten wordt, is 10 en de kost verbonden aan het aantal preferentie-overtredingen is twee maal het aantal geobserveerde overtredingen. Voor 10 overtredingen zal dus een kost van 20 aan de doelfunctie toegevoegd worden. Toevoeging van deze drie beperkingen geeft volgend resultaat (tabel 15). Result: Solver found an integer solution within tolerance. All constraints are satisfied. Engine: Standard LP/Quadratic Solution Time: 07 Minutes, 42 Seconds Iterations: 0 Subproblems: 5466 Incumbent Solutions: 5


Name

Original Value

Final Value

$AF$24


7200

286

Tabel 15: oplossing model

Opvallend is dat er een sterke toename is in de benodigde tijd om tot een oplossing te komen en in het aantal doorlopen subproblemen.

27

4.5 Voorwaartse rotatie van laatste naar eerste shift (beperking (1h)) Deze beperking betekent dat het verboden wordt dat de laatste shift op een dag gevolgd wordt door de vroegste shift op de volgende dag. Bovendien worden het aantal shiftwisselingen die een werknemer mag ondergaan gedurende de planningsperiode sowieso beperkt (beperking (1p)), maar deze beperking is hier nog van geen belang. Deze zal pas toegevoegd worden wanneer ook beperking (1o) van kracht is. Result: Solver found an integer solution within tolerance. All constraints are satisfied. Engine: Standard LP/Quadratic Solution Time: 03 Minutes, 21 Seconds Iterations: 0 Subproblems: 1999 Incumbent Solutions: 4


Name

Original Value

Final Value

$AF$24


7200

286


De waarde van de doelfunctie is dezelfde gebleven en de tijd om een oplossing te bekomen is lager dan zonder deze beperking (tabel 15).

4.6 Het aantal vrije weekenddagen per planningsperiode (beperking (1k)) Beperking (1k) moet ervoor zorgen dat werknemers maximaal 2 weekends moeten werken gedurende de 4 weken durende planningsperiode. Beperking (1j) werd hier ook reeds toegevoegd omdat dit belangrijk is om tot twee volledig vrije weekends te kunnen komen.

28

Result: Solver found an integer solution within tolerance. All constraints are satisfied. Engine: Standard LP/Quadratic Solution Time: 15 Hours, 06 Minutes, 39 Seconds Iterations: 0 Subproblems: 538956 Incumbent Solutions: 4


Name

Original Value

Final Value

$AF$24


7200

752


Door het opleggen van deze beperkingen is er een grote toename in de waarde van de doelfunctie. Echter de toename in computationele tijd en het aantal subproblemen is exponentieel, wat het ergste doet vermoeden voor wanneer er nog meer beperkingen zullen worden toegevoegd. Deze observatie zal in deel 6.3.3 gebruikt worden.

4.7 Beperking op teveel en te weinig werknemers (beperking (1s)) Zoals te verwachten was, heeft de Solver voor de toevoeging van deze beperking, zeker meer dan 15 uur nodig gehad. Aangezien dit echter veel te lang is en rekening houdend met het feit dat er al met een sterk vereenvoudigd model gewerkt werd (bv. slechts één ervaringsniveau, nog geen enkele vorm van cycliciteit en maar 7 werknemers) blijkt dat het model nooit op deze manier opgelost kan worden.

5. “Branch and price” methode Aangezien deel 4 heeft aangetoond dat het zeer moeilijk is om een optimale oplossing te vinden met gewone Solvers, zal hier een “branch and price”-algoritme uitgewerkt worden. Zoals reeds vermeld, is de “branch and price” methode een exacte methode voor het oplossen van een mathematisch model. Deze methode omvat kolomgeneratie. Dit wil zeggen dat het boven vernoemde model zal opgesplitst worden in een masterprobleem (deel 5.1) en een subprobleem (deel 5.2). Het masterprobleem is het model dat geldt voor alle werknemers samen, terwijl er voor elke werknemer een subprobleem bestaat. Dit subprobleem bevat dan ook de specifieke beperkingen voor de verschillende werknemers, zoals de individuele preferenties en ander algemene beperkingen die gelden per werknemer. Het masterprobleem daarentegen bevat enkel de beperkingen die stellen dat 29

er enerzijds voldoende werknemers moeten zijn en anderzijds dat het tekort (of het aantal interim werknemers) en het teveel aan werknemers beperkt moet zijn. Bovendien stelt dit masterprobleem ook dat, gezien er sprake is van kolomgeneratie, voor elke werknemer geldt dat de som over de verschillende kolommen, ook wel patronen genoemd, precies gelijk moet zijn aan één. Hieronder wordt de mathematische weergave gegeven van het master –en subprobleem, waarna meer uitleg volgt over het geprogrammeerde algoritme.

5.1 Masterprobleem 5.1.1 Indexen en sets l index voor de kolommen; l ϵ Ki Ki

set van kolommen voor werknemer i; i ϵ N

5.1.2 Parameters Vmax

cil

de kost van kolom l voor werknemer i; i ϵ N; met cil=

r a 1

f (i ) f (i ) a ia

v

; met f(i)=ϴ; f(i) geeft dus

het bijhorende ervaringsniveau van de werknemer aan; 5.1.3 Beslissingsvariabelen yil 1 wanneer kolom l wordt toegewezen aan werknemer i, anders 0; Het is echter wel belangrijk op te merken dat voor deze variabele geldt dat deze niet noodzakelijkerwijs binair moet zijn. Een andere waarde, liggend tussen 0 en 1 is ook mogelijk. aildt ϴ

1 wanneer werknemer i met ervaringsniveau ϴ toegewezen wordt aan kolom l die op dag d shift t bevat, anders 0;

Min : z RMP   cil yil 

NSkills

iN lKi

r  n   1 dD tTi

n

dt



NSkills

r  m   1 dD tTi

m

dt

(2a)

s.t. 





q 1

q 1

q  mdt   aildt yil   ndtq   LDdtq , d  D, t  Ti ,   1,..., NSkills

(2b)

y

(2c)

q 1 iN lKi

lKi

il

 1, i  N 



q 1

q 1

0  mdtq  UDdtq   LDdtq ,0  ndt  Odt ,max , d , t;  1,..., NSkills

30

(2d)

Hierboven zijn enkel de nieuwe indexen en sets, parameters en beslissingsvariabelen vermeld. De andere die vermeld worden in het masterprobleem zijn gelijkaardig aan deze die in het normale model werden gebruikt. Merk op dat hier geen integraliteitsbeperking geldt.

5.2 Subprobleem 5.2.1 Parameters µi de duale prijs van beperking (2c) ωdtf(i)

de duale prijs van beperking (2b) voor het ervaringsniveau f(i)= ϴ

De doelfunctie in het subprobleem is de gereduceerde kost of “reduced cost” van een kolom l voor werknemer i. De duale prijzen van de twee beperkingen worden afgetrokken van de kost van de kolom. Een kolom zal aldus enkel toegevoegd worden aan de mogelijke kolommen K i indien de gereduceerde kost negatief is. Indien deze niet negatief is, betekent dit dat de waarde van de doelfunctie van het masterprobleem niet langer kan verminderen onder behoud van de toevoeging van kolommen voor die bepaalde werknemer. Het subprobleem voor werknemer i is:

Min :  il 

Vmax

r

f (i ) f (i ) a ia

a 1

v

f (i )  i   aildt dtf (i )

(3a)

dD tTi

s.t.

x

idt

dD

 Pit , t  Ti

(3b)

 h x

 Hi

(3c)

 h x

 H i  Maxh

(3d)

Maxh  (  ht xidt  H i )  oi  1

(3e)

x

 1, d  D

(3f)

xidt3  xi ,d 1,t1  1, d  D

(3g)

dD tTi

dD tTi

t idt

t idt

dD tTi

tT

idt

d  Di , max on

 x l d tTi

ilt

 Di ,max on , d  D

(3h)

xidt  xi ,d 1,t , d  DW , t  T

(3i) 31

 x

idt

dDW tTi

 Wi ,max

(3j)

1   xidt  g id  1, d  Dinot

(3k)

x

 (1   xi ,d 1,t )   xi ,d 2,t  pid  1, d  D

(3l)

(1   xidt )   xi , d 1,t  (1   xi , d  2,t )  qid  1, d  D

(3m)

1  xidt  1  xi ,d 1,t  bid  1, d  D,     Ti

(3n)

b

(3o)

tTi

idt

tTi

tTi

tTi

id

dD

tTi

tTi

tTi

 TRmax Vmax

 ( pid  qid  bid  gid  oi )   aviaf (i )

dD

Vmax

v a 1

(3p)

a 1

f (i ) ia

28

1

(3q) 14

 xidt   xidt

(3r)

pid , qid , bid , gid , oi {0,1}, d ; viaf (i ) {0,1}, a

(3s)

d 15 tT

d 1 tT

xidt  {0,1}, d , t : xi ,lengteplanningsperiodel ,t  xilt , l  1,..., Di ,max on

(3t)

De bovenstaande beperkingen zijn dezelfde als deze in het gewone model. Merk wel op dat hier geen ervaringsniveau wordt vermeld. Dit omdat er specifiek per werknemer gewerkt wordt. Het ervaringsniveau is dan ook enkel en alleen afhankelijk van de werknemer waarvoor een kolom gegenereerd wordt. Dit is dan ook de reden waarom hier gebruik gemaakt wordt van f(i) om het ervaringsniveau aan te geven.

5.3 Methode In deze stap wordt kort de “branch and price” procedure, zoals ze geprogrammeerd is in C++ met behulp van Gurobi, besproken (zie figuur 1). 5.3.1 Initiële oplossing Om te starten is er voor gekozen om het subprobleem voor elke werknemer al één maal aan te roepen. Op die manier krijgt elke werknemer reeds één kolom toegewezen. Dit is ook nodig omdat 32

het masterprobleem straks nog moet aangeroepen worden. Indien deze initialisatie niet zou plaatsgevonden hebben, zouden er dan ook geen kolommen zijn die gebruikt kunnen worden in het masterprobleem. Aangezien het gaat om een initiële oplossing werden beide duale prijzen hier nog gelijk gesteld aan nul, zodat enkel het aantal preferentie-overtredingen van tel is. Na het bepalen van deze initiële oplossing begint de eigenlijke procedure. 5.3.2 Procedure: kolomgeneratie De procedure start met de kolomgeneratie. Dit houdt in dat eerst en vooral het masterprobleem een eerste keer wordt opgelost. Hierna wordt onderzocht of de eerste oplossing van dit masterprobleem een oplossing is die beter is dan de huidige oplossing (die tijdens de fase van de initiële oplossing gelijk gesteld werd aan tien miljard voor de eerste iteratie). Ook wordt onderzocht of de oplossing integer is en het model “feasible” was. Indien aan al deze voorwaarden voldaan is, kan de huidige oplossing een eerste keer opgeslagen (store solution) worden. Vervolgens vindt het uitprijzen (price) plaats. Hierbij worden de duale prijzen, die uit het masterprobleem gehaald werden, onrechtstreeks aan het subprobleem toegevoegd. Nadien wordt het subprobleem aangeroepen en onderzoekt men wat de gereduceerde kost is. Indien deze voldoende negatief is, kan er gecontroleerd worden of de nieuwe kolom verschillend is van de kolommen die al toegekend werden aan een bepaalde werknemer. Als de kolom verschillend is van de reeds bestaande kolommen voor deze werknemer, dan wordt de kolom toegevoegd (enter new column). Het is echter mogelijk dat geen enkel van de kolommen, die het subprobleem voorstelt, verschillend is van de reeds bestaande kolommen. In dit geval zal de kolomgeneratie gestart worden voor de volgende werknemer. De kolomgeneratie start ook opnieuw voor de volgende werknemer wanneer blijkt dat de gereduceerde kost voor een werknemer niet langer negatief is. Dit betekent immers dat er geen kolommen meer gevonden kunnen worden die de waarde van de doelfunctie van het masterprobleem kunnen laten dalen. De kolomgeneratie herhaalt zich voor elke werknemer totdat het niet langer mogelijk is om voor een werknemer een kolom toe te voegen die een negatieve gereduceerde kost heeft of totdat het gewoon niet langer mogelijk is om een

kolom

te

vinden

die

verschillend

is

33

van

de

reeds

toegevoegde

kolommen.

Initiële oplossing

procedure

oplossing niet fractioneel of oplossing niet beter of oplossing infeasible maar level>=0

right branch Kolomgeneratie feasible

Masterprobleem

Store solution

beter dan vorige oplossing , niet fractioneel, feasible

herhaal zolang reduced cost< -maxerror

round up objective

oplossing is fractioneel en feasible, en upperbound

oplossing niet fractioneel of oplossing niet beter of oplossing infeasible

Price kost kolom< -maxerror

Subprobleem

herhaal voor alle kolommen

backtrack Selectie branching variabele left branch

Enter new column

oplossing is niet fractioneel en feasible, en upperbound oplossing is

Store solution

Figuur 1: procedure

34

herhaal zolang level>=0

5.3.3 Procedure: Naar boven afronden van de oplossing van het masterprobleem Deze stap betekent dat, in eerste instantie, de oplossing van het masterprobleem omgezet wordt naar een integere oplossing. Hierna wordt bij deze integere oplossing één eenheid toegevoegd als blijkt dat het verschil tussen de originele oplossing en de integere oplossing voldoende groot is. Dit wil zeggen dat de oplossing in dat geval dus het meest aansluit bij een hoger integer getal. Om dit wat te verduidelijken volgt een kort voorbeeld: Stel dat de waarde van de doelfunctie van het masterprobleem gelijk is aan 1533,25. In dit geval wordt de integere oplossing gelijk gesteld aan 1533. Als blijkt dat 0,25 groter is dan de maximale error (hier 0,001) dan zal de “upperbound” van de oplossing met 1 verhoogd worden tot 1534. 5.3.4 Procedure: Selectie branching variabele De voorwaarden om een branching variabele te mogen selecteren houden in dat de oplossing fractioneel en het model “feasible” moet zijn. Bovendien moet de naar boven afgeronde oplossing (zie 5.3.3) kleiner zijn dan de huidig opgeslagen oplossing. Is dit niet het geval, dan zal het niet mogelijk zijn om in de branch waarin de compiler zich bevindt, een betere (en dus lagere) oplossing te vinden. Maenhout en Vanhoucke (2010b) hebben drie verschillende strategieën geïdentificeerd om deze branching uit te voeren. Bij het selecteren van een branching variabele werden de originele variabelen gebruikt. We krijgen dus een 0-1 schema. Bovendien stellen zij dat de branching variabelen op verschillende manieren kunnen geselecteerd worden. In dit onderzoek werd gebruik gemaakt van de eerst voorgestelde manier. Deze selectiemethode houdt in dat men eigenlijk de meest fractionele variabele gaat gebruiken. Dit zijn de variabelen wiens waarde het dichtst bij 0,5 liggen. De eerste variabele die het dichtst bij 0,5 ligt, wordt gekozen. Met andere woorden, een variabele die even dicht ligt bij 0,5 maar later in de planningshorizon voorkomt, zal niet gekozen worden. Er geldt dus een “first come, first pick” principe. Merk op dat Maenhout en Vanhoucke (2010b) dit principe niet gebruiken. Zij zullen immers, in het geval dat er meerdere variabelen op dezelfde afstand van 0,5 liggen, de variabele kiezen die de laagste overtreding inhoudt in termen van preferenties. Het “first come, first pick” principe zal echter ook voor een graduele verbetering zorgen naargelang de variabele steeds verder en verder in de planningsperiode zal komen te liggen. De reden dat deze selectiemethode werd gekozen, is dat deze het meest intuïtief is. De tweede selectiemethode van Maenhout en Vanhoucke (2010b) houdt in dat de fractionele variabele waarvoor de waarde van de doelfunctie op een bepaalde dag het slechtst is, in vergelijking met de beste shifttoewijzing op die dag, geselecteerd wordt. Dit betekent dat op zoek gegaan wordt naar de shift die het slechts is in vergelijking met de beste shift op diezelfde dag. De laatste strategie kiest de variabele die het dichtst bij één ligt. 33

Om de gekozen selectiemethode wat duidelijker te maken, volgt nu een kort voorbeeld. Stel dat werknemer w, 8 mogelijke kolommen heeft. Elke kolom is een combinatie van 0-1 waarden die aangeven of deze werknemer op dat moment in de planningshorizon al dan niet werkt. Elke kolom zal een bepaalde waarde toegewezen krijgen waarbij de som over deze waarden gelijk moet zijn aan 1. Kolom 1

0,125

Kolom 2

0

Kolom 3

0

Kolom 4

0

Kolom 5

0,5

Kolom 6

0,125

Kolom 7

0

Kolom 8

0,25

Tabel 18: voorbeeld

We beginnen op dag 1 en shift 1. Voor dit tijdstip wordt over alle kolommen gekeken of de werknemer, in de respectievelijke kolommen, effectief toegewezen is aan shift 1 op dag 1. Stel dat dit het geval is voor de eerste drie en laatste 2 kolommen, dan nemen we de som van de waarden die bij deze kolommen horen. Dit is dus (0,125 + 0 + 0 + 0 + 0,25 =) 0,375. Hetzelfde wordt herhaald voor shift 2 op dag 1. Stel dat hier enkel voor kolom 5 geldt dat werknemer w tijdens deze shift op deze dag moet werken. Dan hebben we een som van 0,5. Nu we de som van twee verschillende shifts hebben, kunnen we bepalen welk van de twee het meest interessant is om te gebruiken als branching variabele. Shift1 = maximum(0,375 – 0,5; 0,5 – 0,375) = 0,125 Shift 2 = maximum(0,5 – 0,5; 0,5 – 0, 5) = 0 Van deze twee wordt dan het minimum genomen en hieruit blijkt dat er gebrancht zal worden op dag 1 shift 2. Merk wel op dat dit dus gedaan wordt voor alle shifts over de verschillende dagen van de planningsperiode. 5.3.5 Procedure: “Left branch” Nadat een variabele geselecteerd is, moeten de kolommen, die de juiste waarde hebben, gekopieerd worden naar het volgende niveau in de “branch tree”. Dit betekent dat de kolommen met de waarde nul op de dag en shift die het meest fractioneel is, meegenomen worden naar het volgende niveau. 34

Het is belangrijk dat de kolommen die in het verdere verloop toegevoegd worden op deze dag en shift een waarde nul toegewezen krijgen. Er worden op die manier extra beperkingen toegevoegd aan het subprobleem om dit mogelijk te maken. Merk op dat dit voor alle niveaus in die bepaalde branch van de “branching tree” geldt. 5.3.6 Procedure: Store solution Indien al de voorwaarden gelden die vermeld worden in figuur 1 kan de oplossing die nu werd bekomen, opgeslagen worden. Op die manier wordt de oude, slechtere, oplossing overschreven. 5.3.7 Procedure: Backtracking Als één van de voorwaarden voor de selectie van een variabele -en de “left branch”-procedure niet geldt dan komt de compiler na store solution in backtracking terecht. Indien de, naar boven afgeronde, oplossing van het masterprobleem groter is dan of gelijk is aan de oplossing van het masterprobleem die op dit moment opgeslagen is, dan zal er geen betere oplossing meer gevonden kunnen worden in de rechtse branch. Hierbij moet de compiler terug gaan naar het vorige niveau. De compiler moet zover teruggaan totdat de naar boven afgeronde oplossing opnieuw kleiner is dan de opgeslagen oplossing én totdat de compiler niet langer in de rechtse branch zit. Deze laatste voorwaarde is noodzakelijk, anders zou er een eeuwig durende loop ontstaan waarbij de compiler steeds naar het vorige niveau teruggaat en later via rechts branchen opnieuw op dezelfde plaats in de “branch tree” terecht komt. Onderstaande figuur moet deze gedachtegang wat verduidelijken.

0

Level 0

Level 1

0

1

0

Level 2

Level 3

1

1

Level 4

Figuur 2: branching tree

Op het moment dat de compiler zich op level 4 en in de rechtse branch bevindt, blijkt dat de naar boven afgeronde oplossing die daar gevonden wordt hoger is dan de huidig opgeslagen oplossing. Dit betekent dat er geen betere oplossing kan gevonden worden in deze branch. Hierdoor moet de compiler terugkeren naar level 1 om zo in de rechtse branch op level 2 te kunnen komen. Anders zou de compiler vast zitten in de rechtse branch op level 3 of 4. 35

5.3.8 Procedure: “right branch” Na backtracking volgt de “right branch”-procedure. De kolommen met de waarde één op de juiste dag en shift worden meegenomen naar het volgende niveau in de “branch tree”. De variabele waarbij hier gebrancht wordt, wordt bepaald door de selectie van de branching variabele. Moest deze subprocedure nog niet aangeroepen zijn vooraleer de compiler in de “right branch”-procedure terechtkomt, omdat de juiste voorwaarden op dat moment nog niet voldaan waren, dan gelden de variabelen die als branching variabelen in de initiële oplossing werden bepaald. In de initiële oplossing werden deze gelijk gesteld aan het werknemer nummer. Voor werknemer 10 geldt dan bijvoorbeeld dat er gebrancht zal worden op shift drie tijdens dag drie (tabel 19). Merk op dat zowel de nummers van de werknemers als de dagen en shifts starten met nul. Wanneer in een vorige iteratie echter een variabele werd geselecteerd voor de “left branch” dan zal deze zelfde variabele ook hier gebruikt worden. Shift 1

Shift 2

Shift 3

Vrije dag

Dag 1

0

1

2

3

Dag 2

4

5

6

7

Dag 3

8

9

10

11

Tabel 19: right branch variabele

Hierna herhaalt de hele procedure zich totdat de compiler zover is teruggekeerd dat het niveau in de “branch tree” kleiner is dan nul.

6. Cycliciteitsonderzoek In dit deel wordt de toepasbaarheid van cyclische schema’s onder verschillende omstandigheden getest en wordt er gekeken welke beperkingen verwijderd kunnen worden, zonder de realiteit uit het oog te verliezen, zodat de onproductieve shiftallocaties dalen. Vooraleer dit gebeurt, zal er eerst wat uitleg volgen over de karakteristieken van het model en de gebruikte personeelsvereisten. In de sectie over het literatuuronderzoek werd al aangegeven hoe een oplossing geëvalueerd kan worden. Aangezien de mate waarin preferenties van werknemers worden overtreden en het teveel/tekort aan werknemers belangrijke factoren zijn, moet sowieso de waarde van de doelfunctie in rekening genomen worden. Deze twee factoren zijn belangrijk door de keuze om cycliciteit te combineren met een schema waarin zoveel mogelijk aan de individuele preferenties van werknemers wordt voldaan. Verder zullen in dit onderzoek de volgende parameters, die gebruikt werden in Maenhout en Vanhoucke (2010b), gebruikt worden. 36

De eerste is het totaal aantal iteraties in de kolomgeneratie-procedure. Deze parameter geeft aan hoeveel maal de procedure doorlopen wordt. Het is echter wel belangrijk op te merken dat dit niet betekent dat bij elke iteratie ook een kolom, aan de verzameling van bestaande kolommen voor een werknemer, toegevoegd wordt. Om dit in rekening te brengen wordt een andere parameter gebruikt, namelijk het aantal toegevoegde kolommen. Deze parameter geeft een belangrijke indicatie over het uiteindelijke resultaat van het probleem dat het “branch & price” algoritme moet oplossen. Hoe meer iteraties, of hoe meer toegevoegde kolommen, hoe langer het duurt om tot de best mogelijke oplossing te komen maar ook hoe lager de uiteindelijke oplossingswaarde zal zijn. Dit zal later in deze sectie aangetoond worden. Vervolgens is het ook belangrijk te kijken naar hoe lang het geduurd heeft om tot die optimale oplossing te komen. Op die manier is het mogelijk om de efficiëntie van het algoritme, onder verschillende omstandigheden, te beoordelen. De eerste belangrijke factor hierbij is het aantal nodes die de procedure doorlopen hebben. Ook deze factor zal een indicatie geven over de uiteindelijke oplossing van het probleem. Dit zal opnieuw, later in dit deel, aangetoond worden. De laatste parameter om de oplossing te evalueren is de tijd die het algoritme nodig had om tot de optimale oplossing te komen. Al deze parameters zijn een directe uiting van de vijf criteria van Burke et al. (2004), behalve de stabiliteit en de flexibiliteit. Deze twee factoren van een personeelsplan moeten eigenlijk vooraf bepaald worden door het nemen van bepaalde keuzes, zoals bijvoorbeeld het gebruiken van een cyclisch personeelsplan om de stabiliteit te kunnen garanderen of net geen cyclisch personeelsplan om een grotere flexibiliteit te kunnen waarborgen. In dit onderzoek worden deze twee factoren zoveel mogelijk gecombineerd doordat zowel cycliciteit als preferenties zoveel mogelijk in het schema geïntegreerd worden. Het “coverage” criterium wordt weerspiegeld in de waarde van de doelfunctie, namelijk de kost verbonden aan het teveel en tekort aan werknemers gedurende de verschillende shifts. Ook het rechtvaardigheidscriterium, door Warner (1976) ook wel kwaliteit genoemd of dus het aantal preferentie-overtredingen, zit in deze doelfunctie vervat. Beide criteria kunnen op die manier beoordeeld worden aan de hand van de verschillen in de waarde van de doelfunctie tussen verschillende oplossingen. Het laatste criterium is deze van de kost. Er werd reeds vermeld dat dit te maken heeft met de tijd nodig om tot een oplossing te komen. Hierdoor, zullen het aantal iteraties in de kolomgeneratie, het aantal toegevoegde kolommen, het aantal doorlopen nodes en de tijd nodig om tot een oplossing te komen, beoordeeld worden.

37

6.1 Karakteristieken In dit deel volgt kort wat meer uitleg over de karakteristieken van het geïmplementeerde model. De belangrijkste specifieke factoren, die hier vermeld moeten worden, zijn: het maximaal toegelaten aantal shiftveranderingen over de hele planningsperiode, het maximaal aantal toegelaten fouten, de individuele preferenties van de werknemers en de cycliciteitsbeperkingen. Het maximaal aantal toegelaten shiftveranderingen is direct verbonden met het aantal shifts die een werknemer gedurende de planningsperiode moet werken. Er is gekozen om voor de meeste werknemers minstens twee verschillende shifts te voorzien. Op die manier kunnen ze eventueel een hoger loon ontvangen doordat één van deze twee shifts bijvoorbeeld een nachtshift is. Uiteindelijk werd het maximaal aantal toegelaten shiftveranderingen voor elke werknemer vastgelegd op 10. Merk op dat dit een zeer hoog getal is in vergelijking met de waarde gebruikt door Bard en Purnomo (2007). Zij hebben immers het maximum vastgelegd op drie. Het grote verschil kan verklaard worden doordat de planningsperiode tweemaal zo lang is dan bij Bard en Purnomo (2007) en doordat in het model (deel 3) alle mogelijke shiftovergangen worden gecontroleerd (tabel 20) en dus niet enkel de overgangen van shift 1 naar 2 of omgekeerd. Dag 1

Dag 2

Shift 1

Shift 2

Shift 1

Shift 3

Shift 2

Shift 1

Shift 2

Shift 3

Shift 3

Shift 2

Tabel 20: shiftovergangen

De overgang van shift 3 op een bepaalde dag naar shift 1 op de volgende dag moet niet gecontroleerd worden aangezien deze reeds expliciet verboden wordt door beperkingen (1h) of (3g). Bovendien worden overgangen tussen een bepaalde shift op een bepaalde dag, waarna één of meerdere dagen vrij volgen, en een bepaalde shift op de eerste dag na de verlofdagen ook niet in rekening gebracht. De werknemer krijgt immers de kans om zich tijdens de periode, waarin hij of zij niet moet werken, aan te passen. Het maximaal aantal toegelaten fouten is ook een belangrijke factor die wat meer uitleg verdient. Deze wordt vastgelegd op 20. Deze 20 toegelaten fouten omvatten niet alleen de overtredingen op “1-0-1” en “0-1-0” patronen. Andere factoren zijn de overtredingen op het contractueel vastgelegde aantal uur dat een werknemer mag werken, op dagen die de werknemer liever niet werkt en als laatste op de shiftovergangen. Indien blijkt dat een werknemer 10 shiftovergangen kent gedurende 38

de planningsperiode, zal deze werknemer dus slechts 10 andere overtredingen kunnen oplopen in zijn/haar schema. Opnieuw blijkt dat het maximaal toegelaten aantal overtredingen in deze paper veel hoger is dan het geval is in de paper van Bard en Purnomo (2007). De redenen zijn dezelfde als hierboven aangehaald. Daarbij komt nog eens dat er extra preferentiebeperkingen werden toegevoegd in het model. Deze zijn de beperkingen op de overuren en de dagen die de werknemer liever niet wil werken. De verschillende preferenties werden ondertussen al behandeld maar nu volgt nog wat meer uitleg. Eerst en vooral, hoewel het aantal contracturen niet specifiek als preferentie kan beschouwd worden, heeft dit toch een belangrijke invloed op een andere preferentie. Deze preferentie is die op het al dan niet werken van overuren. Ten tweede zijn er de dagen die een werknemer liever niet werkt. Belangrijk hierbij is dat deze geen rekening houdt met het feit dat de werknemers slechts 2 op 4 volle weekends mogen werken. De beperking op de dagen waarop een werknemer liever niet werkt, houdt hier geen rekening mee. Dit wil zeggen dat het mogelijk is dat een werknemer bijvoorbeeld op zaterdag liever niet werkt, maar de kans is even groot dat dit een dag buiten het weekend is en dan moet de werknemer zowel 2 vrije weekends krijgen als zoveel mogelijk de niet-weekenddagen die deze persoon wenst. Ten slotte moet er nog wat gezegd worden over de cycliciteitsbeperkingen. Er bestaan verschillende mogelijkheden om met een variabele vraag naar werknemers om te gaan (Maenhout en Vanhoucke 2011). Twee van deze mogelijkheden blijken de beste resultaten op te leveren qua consistentie en flexibiliteit. De eerste mogelijkheid is het opdelen van de werknemers in subsets. Een subset is dan een verzameling van werknemers die cyclisch werken en de andere subset bestaat uit werknemers die niet cyclisch werken. De tweede mogelijkheid, besproken door deze auteurs, is het opdelen van de planningsperiode in subperiodes en toe te laten dat werknemers tijdens deze subperiodes ofwel een cyclisch ofwel een ad hoc schema volgen. Merk op dat de eerste mogelijkheid het meest relevant is in dit onderzoek. De reden hiervoor is dat de planningsperiode beperkt blijft tot vier weken. Indien een langere periode in acht genomen zou worden, zou de tweede mogelijkheid interessanter zijn om uit te werken. Er werd reeds een beperking vermeld die stelt dat een werknemer volgens hetzelfde schema moet werken tijdens de laatste 14 dagen van de planningsperiode als tijdens de eerste 14 dagen. Echter in dit onderzoek is het de bedoeling om verschillende graden van cycliciteit te bespreken. Dit houdt in dat niet alle werknemers noodzakelijkerwijs een volledig cyclisch schema zullen hebben (Maenhout en Vanhoucke 2011). Voor de werknemers, zonder cyclisch schema van twee weken, geldt wel dat hun vooropgesteld schema zich na 28 dagen zal herhalen (zie beperking (1u) en (3t)). Op deze manier 39

wordt een soort van “end of game” scenario vermeden, waarbij geen rekening zou gehouden worden met het feit dat, bijvoorbeeld, de beperking op het maximaal toegelaten opeenvolgende werkende dagen over verschillende planningsperiodes moet gelden. In het “end of game” scenario zou het anders mogelijk zijn dat een werknemer de laatste vijf dagen werkt en bij het begin van de volgende planningsperiode ook de eerste dag moet werken. Om deze gedachtegang wat te verduidelijken volgt een kort voorbeeld. Stel dat de lengte van de planningsperiode twee weken is en bijgevolg de lengte van een cyclische periode slechts één week. Bovendien is er slechts één mogelijke shift per dag. Onderstaande tabel (tabel 21) bevat het werkschema voor twee werknemers. dagen werknemer 1 werknemer 2

1 0 1

2 1 1

3 1 1

4 1 0

5 1 0

6 1 0

7 0 1

8 0 1

9 1 0

10 1 1

11 1 1

12 1 1

13 1 1

14 0 1

Tabel 21: voorbeeld cycliciteit

De tabel toont dat werknemer 1 een volledig cyclisch schema volgt. Voor werknemer 2 geldt dit cyclisch schema niet. Het blijkt dat deze werknemer tijdens de laatste vijf dagen van de planningsperiode moet werken. Dit heeft tot gevolg dat deze werknemer bij het begin van de volgende planningsperiode minstens één vrije dag moet krijgen. Om dit tot stand te kunnen brengen wordt dus het begin van de huidige planningsperiode genomen als het begin van de volgende planningsperiode en wordt zoiets vermeden. Hierbij wordt dan impliciet verondersteld dat de vraag naar werknemers in de volgende planningsperiode dezelfde zal zijn. Het is echter ook mogelijk om voor de volgende planningsperiode extra beperkingen in te voeren (zie tabel 4 nummer 13), maar aangezien hier maar één planningsperiode in rekening gebracht wordt, werd de huidige aanpak verkozen. Er zullen verschillende graden van cycliciteit uitgetest worden. Deze variëren van volledig nietcyclisch tot volledig cyclisch (0%-20%-40%-60%-80%-100%). Voor het niet-cyclische schema wordt enkel de cycliciteitsbeperking verwijderd. Voor de andere percentages wordt deze beperking lichtjes aangepast. Om een schema te kunnen vinden dat bijvoorbeeld 80% cyclisch is, wordt ervoor gekozen om 80% van de werknemers volgens een cyclisch schema te laten werken, ongeacht de toepasbaarheid van zo’n cyclisch schema voor de betrokken werknemer. Het zou immers beter zijn om werknemers te kiezen voor het cyclische schema die bijvoorbeeld allemaal voltijds werken. Op die manier kunnen de andere, deeltijdse werknemers de overblijvende tekorten opvangen. Deze aanpak werd niet gekozen, want de huidige trend is dat er meer en meer mensen afstappen van het voltijds werken. Bovendien behoudt men, met werknemers die niet cyclisch werken maar wel een voltijds contract hebben, een extra flexibiliteit achter de hand. Deze werknemers kunnen dan op meer momenten ingezet worden dan een niet voltijdse werknemer. 40

Om te bepalen welke werknemers volgens een cyclisch schema moeten werken werd de volgende procedure gebruikt: stel dat we uitgaan van 80% cycliciteit, dan betekent dit dat 80% van de werknemers een cyclisch schema moeten toegewezen krijgen. Aangezien er twee ervaringsniveaus zijn, moeten deze cyclische werknemers over beide klassen verdeeld worden. Als eerste stap wordt 80% van het totaal aantal werknemers genomen. Dit aantal cyclische werknemers wordt vervolgens proportioneel opgesplitst naar werknemers van ervaringsniveau 1 en 2. Dit wil zeggen dat wanneer er 25% van de werknemers in de klasse van ervaringsniveau 1 zitten, er 25% van de 80% (=20%) werknemers cyclisch zullen werken. De overige 75% van de 80% (=60%) cyclische werknemers zijn werknemers met ervaringsniveau 2. Hierna worden de eerste werknemers uit beide ervaringsniveaus toegewezen aan een cyclisch schema totdat de respectievelijke percentages bereikt worden, namelijk 20% en 60%. Hetzelfde principe wordt gebruikt voor 20%, 40% en 60% cycliciteit. Het is mogelijk dat, wanneer een bepaald percentage van werknemers genomen wordt, de uitkomst hiervan niet integer is. Als dit het geval is, dan zal de waarde moeten omgezet worden naar een integere waarde. Stel dat er in totaal 26 werknemers zijn, waarvan 13 met ervaringsniveau 1 en 13 met ervaringsniveau 2 en indien een 60% cyclisch schema gevonden moet worden, dan wordt de volgende werkwijze gebruikt: 0,6 * 26 = 15,6 Aangezien er 2 ervaringsniveaus zijn met dezelfde hoeveelheid werknemers, moet dit getal gedeeld worden door 2. 15,6/2 = 7,8 Met andere woorden, van elk ervaringsniveau moeten 7 werknemers volgens een cyclisch schema werken (tabel 22). Enkel het laatste getal wordt naar beneden afgerond.

6.2 Personeelsvereisten Deze werden gegenereerd aan de hand van drie parameters; namelijk de TCC-, DCD- en SCDparameters. Hiervoor moest eerst echter bepaald worden wat de totale vereiste over de volledige planningsperiode zou worden. Deze werd in dit geval gelijk gesteld aan 224. De logica achter deze keuze houdt in dat een vereiste van 224 verspreid over 28 dagen gelijk is aan een gemiddelde van 8 opdrachten per dag verspreid over drie verschillende shifts. Op deze manier wordt een te gemakkelijk schema vermeden. Deze vereiste van 224 opdrachten werd zowel voor ervaringsniveau 1 als 2 genomen. Op die manier is er een gelijk aantal werknemers in beide klassen van werknemers. Zoals reeds vermeld zullen drie verschillende waarden voor TCC gebruikt worden om de personeelsvereisten te bepalen. Deze zullen allen een verschillende invloed hebben op het aantal werknemers die ingezet kunnen worden. 41

Zowel ervaringsniveau 1 als 2 zal bestaan uit 39 werknemers in het geval TCC=0,2. Indien TCC gelijk is aan 0,35, levert dit voor elk niveau 22 werknemers op en ten laatste in het geval dat TCC 0,5 is, zijn er slechts 16 werknemers per niveau. Deze grote variatie in het aantal werknemers kan potentieel een grote invloed hebben op de toepasbaarheid van cyclische schema’s. In de drie gevallen is het nodig om een aantal waarden vast te leggen, zoals de contracturen. Onderstaande tabel (tabel 22) bevat de belangrijkste voor het geval dat TCC 0,2 is. Merk op dat voor andere waarden van TCC dezelfde tabel geldt maar dan moet enkel gekeken worden naar de eerste 22 of 16 werknemers van elk ervaringsniveau voor TCC=0,35 en TCC=0,5 respectievelijk. Merk op dat, zowel in als tussen de ervaringsniveaus, er heel wat werknemers zijn die hetzelfde aantal shifts van een bepaald type moeten werken. Binnen één ervaringsniveau laat dit toe dat, tot op een bepaalde hoogte, de cyclische werknemers dezelfde karakteristieken hebben als de niet-cyclische werknemers. Tussen de twee ervaringsniveaus mag dit normaal geen groot probleem vormen omdat de personeelsvereisten voor beide ervaringsniveaus zeer gelijkaardig zullen zijn. Bovendien geldt voor sommige van deze werknemers dat zij een verschillend aantal contractuele uren moeten werken. Andere belangrijke waarden die niet in deze tabel vermeld zijn, zijn het maximaal aantal overuren en het maximaal aantal toegelaten opeenvolgende werkdagen. Deze zijn respectievelijk gelijk aan 8, i.e. de lengte van één shift, en 5 voor alle werknemers. Verder zijn er nog de eerder vermelde waarden voor het maximaal aantal toegelaten werkende weekends, i.e. 4, en de maximaal toegelaten shiftwisselingen tussen twee dagen, i.e. 10. Niet alleen voor TCC werden verschillende waarden gebruikt. Zowel de DCD- als de SCD-parameters variëren tussen vijf verschillende waarden, namelijk 0 – 0,25 – 0,5 – 0,75 – 1. De combinatie van de drie verschillende parameters zorgen voor 75 verschillende personeelsvereisten. Hierbij is het wel belangrijk te melden dat het verschil tussen de personeelsvereisten voor TCC=0,2/0,35/0,5 – DCD=0 – SCD=0 en TCC=0,2/0,35/0,5 – DCD=0 – SCD=0,25 zodanig klein is, dat enkel het probleem met de personeelsvereiste voor de eerste combinatie werd uitgevoerd (zie Appendix B voor de personeelsvereisten voor TCC=0,2 en bijhorende grafiek). Dit kleine verschil zit in de plaatsing van de specifieke vereisten maar de vereisten voor de drie shifts op één dag blijven wel voor beide mogelijkheden een combinatie van twee 3-en en één 2. Door het verwijderen van deze drie probleeminstanties blijven er in totaal nog 72 over.

42

Ervaringsniveau 1 werknemer 1 werknemer 2 werknemer 3 werknemer 4 werknemer 5 werknemer 6 werknemer 7 werknemer 8 werknemer 9 werknemer 10 werknemer 11 werknemer 12 werknemer 13 werknemer 14 werknemer 15 werknemer 16 werknemer 17 werknemer 18 werknemer 19 werknemer 20 werknemer 21 werknemer 22 werknemer 23 werknemer 24 werknemer 25 werknemer 26 werknemer 27 werknemer 28 werknemer 29 werknemer 30 werknemer 31 werknemer 32 werknemer 33 werknemer 34 werknemer 35 werknemer 36 werknemer 37 werknemer 38 werknemer 39

Shift 1 3 3 0 0 0 5 0 7 0 8 0 0 2 4 5 3 5 6 1 0 3 3 0 3 0 5 0 7 0 0 0 0 2 4 5 3 5 6 1

Shift 2 3 2 2 6 0 0 1 1 5 0 5 3 0 0 2 1 5 0 5 7 3 2 2 6 0 0 1 1 5 6 5 3 0 0 2 1 5 0 5

Shift Ervaringsniveau Contracturen 3 2 0 160 werknemer 1 1 160 werknemer 2 6 160 werknemer 3 0 80 werknemer 4 6 120 werknemer 5 2 160 werknemer 6 2 160 werknemer 7 0 160 werknemer 8 0 160 werknemer 9 0 80 werknemer 10 2 160 werknemer 11 1 120 werknemer 12 4 80 werknemer 13 2 160 werknemer 14 0 160 werknemer 15 1 160 werknemer 16 0 160 werknemer 17 1 120 werknemer 18 1 80 werknemer 19 0 160 werknemer 20 0 160 werknemer 21 1 160 werknemer 22 6 160 werknemer 23 0 80 werknemer 24 4 120 werknemer 25 2 160 werknemer 26 2 160 werknemer 27 0 160 werknemer 28 0 80 werknemer 29 0 80 werknemer 30 2 160 werknemer 31 1 120 werknemer 32 4 80 werknemer 33 2 160 werknemer 34 0 160 werknemer 35 1 160 werknemer 36 0 160 werknemer 37 1 120 werknemer 38 1 160 werknemer 39

Tabel 22: werknemers

43

Shift Shift Shift Contracturen 1 2 3 3 3 0 160 3 2 1 160 0 2 6 160 0 6 0 160 0 0 6 120 5 0 2 120 0 1 2 160 7 1 0 160 0 5 0 160 0 6 0 80 0 5 2 80 0 3 1 160 2 0 4 120 4 0 2 80 5 2 0 160 3 1 1 160 5 5 0 160 6 0 1 160 1 5 1 160 0 7 0 120 3 3 0 160 3 2 1 160 0 2 6 160 0 6 0 160 0 0 6 80 5 0 2 120 0 1 2 160 7 1 0 160 0 5 0 160 0 6 0 80 0 5 2 80 0 3 1 160 2 0 4 80 4 0 2 80 5 2 0 160 3 1 1 160 5 5 0 160 6 0 1 160 1 5 1 120

6.3 Resultaten In dit deel zullen de resultaten van het gevoerde onderzoek worden besproken, voor zowel volledige cycliciteit (deel 6.3.1) als verminderde cycliciteit (deel 6.3.2). Afsluiten wordt er gedaan met een bespreking van de invloed van bepaalde beperkingen (deel 6.3.3). 6.3.1 Volledige cycliciteit In onderstaande tabel (tabel 23) staat voor elke probleeminstantie wat de waarde was van de initiële oplossing versus de integere, uiteindelijke oplossing; hoeveel maal de kolomgeneratie procedure doorlopen is en hoeveel kolommen hierbij toegevoegd zijn. Ten laatste worden ook het aantal nodes die doorlopen werden en de tijd, nodig om de hele procedure (zie 5.3.2 tot en met 5.3.8) te doorlopen, weergegeven. DCD=0-SCD=0 LP solution IP_solution Iteraties kolommen nodes seconden DCD=0-SCD=0,75 LP solution IP_solution Iteraties kolommen nodes seconden

TCC=0,2 TCC=0,35 TCC=0,5 DCD=0-SCD=0,5 3762139 1358047 756896,5 LP solution 3762139 1358047 687999 IP_solution 125 100 1547 Iteraties 69 68 1322 kolommen 1 1 13 nodes 139,71 113,58 8019,37 seconden TCC=0,2 TCC=0,35 TCC=0,5 DCD=0-SCD=1 3758334 1690784,1 1673681,66 LP solution 3758334 1114095 1689344 IP_solution 171 1128 573 Iteraties 112 779 429 kolommen 1 11 7 nodes 177,59 3274,77 1777,35 seconden

TCC=0,2 TCC=0,35 TCC=0,5 3757454 1526644 1046937,57 3757454 1211074 1249128 153 2042 1113 94 1495 879 1 21 13 174,76 5905,67 3381,7 TCC=0,2 TCC=0,35 TCC=0,5 3764103,33 2043359,49 1860598,25 1264602 1886300 1660349 5333 1844 391 2208 1101 162 46 24 10 8105,34 3484,47 586,16

DCD=0,25-SCD=0 LP solution IP_solution Iteraties kolommen nodes seconden DCD=0,25-SCD=0,5 LP solution IP_solution Iteraties kolommen nodes seconden DCD=0,25-SCD=1 LP solution IP_solution Iteraties kolommen nodes seconden

TCC=0,2 TCC=0,35 TCC=0,5 DCD=0,25-SCD=0,25 3752128 1357388 842336,8 LP solution 3752128 715160 1056979 IP_solution 144 2868 1756 Iteraties 87 2206 1478 kolommen 1 26 16 nodes 165,17 9872,8 4886,59 seconden TCC=0,2 TCC=0,35 TCC=0,5 DCD=0,25-SCD=0,75 3758533 1469023,7 1389009,39 LP solution 3758533 1217324 1451476 IP_solution 186 2141 1156 Iteraties 127 1572 848 kolommen 1 22 16 nodes 240,29 5684,94 3233,01 seconden TCC=0,2 TCC=0,35 TCC=0,5 DCD=0,5-SCD=0 4020579 2259808,35 1877577 LP solution 1769820 1885849 1877577 IP_solution 2241 1371 89 Iteraties 1328 920 65 kolommen 16 15 1 nodes 4839,25 2946,98 124,99 seconden

TCC=0,2 TCC=0,35 TCC=0,5 3752703 1563775 734261,85 3752703 1563775 952804 166 118 1251 107 86 990 1 1 15 196,63 141,51 6631,14 TCC=0,2 TCC=0,35 TCC=0,5 3920987 1732871,94 1640393,25 3920987 1454603 1619631 189 1561 735 130 1186 512 1 14 11 234,44 4475,71 1489,69 TCC=0,2 TCC=0,35 TCC=0,5 3768326 1539451 1081423,58 3768326 1539451 976593 163 126 517 104 94 426 1 1 5 178,65 148,65 1767,82

44

DCD=0,5-SCD=0,25 LP solution IP_solution Iteraties kolommen nodes seconden DCD=0,5-SCD=0,75 LP solution IP_solution Iteraties kolommen nodes seconden DCD=0,75-SCD=0 LP solution IP_solution Iteraties kolommen nodes seconden DCD=0,75-SCD=0,5 LP solution IP_solution Iteraties kolommen nodes seconden DCD=0,75-SCD=1 LP solution IP_solution Iteraties kolommen nodes seconden DCD=1-SCD=0,25 LP solution IP_solution Iteraties kolommen nodes seconden DCD=1-SCD=0,75 LP solution IP_solution Iteraties kolommen nodes seconden

TCC=0,2 3798901 3798901 176 117 1 192,81 TCC=0,2 3868873,63 1701800 4221 2178 32 9345,19 TCC=0,2 3864389 3864389 177 118 1 193,69 TCC=0,2 4323029 4323029 188 129 1 224,13 TCC=0,2 4736594 4736594 177 118 1 176,09 TCC=0,2 5008483 3127185 283 178 2 304,58 TCC=0,2 4658704 3022833 265 153 2 252,65

TCC=0,35 1450063,3 1176437 2109 1695 15 6807,78 TCC=0,35 2080580,75 1870492 1313 928 12 3364,85 TCC=0,35 1903919,5 1476634 1750 1234 18 3208,26 TCC=0,35 1982847,13 1869452 783 467 12 1767,63 TCC=0,35 2970170 2589572 203 137 2 336,32 TCC=0,35 2196424 1943354 254 193 2 539,64 TCC=0,35 2971910 2971910 93 60 1 104,17

TCC=0,5 1022754,92 1043975 1311 1047 14 4675,17 TCC=0,5 1721198,18 1687543 655 414 11 1414,12 TCC=0,5 1296926,75 1304426 1391 1001 21 3675,72 TCC=0,5 1835137,4 1714620 471 360 5 1271,86 TCC=0,5 2560292 2560292 73 50 1 85,46 TCC=0,5 1940489,71 1739617 383 297 4 601,32 TCC=0,5 2584065,67 2442241 162 117 2 264,48

DCD=0,5-SCD=0,5 LP solution IP_solution Iteraties kolommen nodes seconden DCD=0,5-SCD=1 LP solution IP_solution Iteraties kolommen nodes seconden DCD=0,75-SCD=0,25 LP solution IP_solution Iteraties kolommen nodes seconden DCD=0,75-SCD=0,75 LP solution IP_solution Iteraties kolommen nodes seconden DCD=1-SCD=0 LP solution IP_solution Iteraties kolommen nodes seconden DCD=1-SCD=0,5 LP solution IP_solution Iteraties kolommen nodes seconden DCD=1,0-SCD=1,0 LP solution IP_solution Iteraties kolommen nodes seconden

Tabel 23: resultaten

45

TCC=0,2 3795406 1511326 2686 1720 17 7487,58 TCC=0,2 4064026 2004928 367 252 2 553,66 TCC=0,2 3904182 1964193 688 453 4 1209,78 TCC=0,2 3773831,5 1751806 4541 1155 72 7056,79 TCC=0,2 3953603,67 2985566 404 287 2 642,74 TCC=0,2 4721906 4721906 177 118 1 162,22 TCC=0,2 4710007 4710007 119 60 1 93,63

TCC=0,35 1759586,09 1589241 2456 1796 21 7499,44 TCC=0,35 2267910 1924259 565 319 7 919,83 TCC=0,35 1733622,5 1520238 4322 2241 60 7031,49 TCC=0,35 2314822,25 2090381 814 450 10 1732,25 TCC=0,35 2030396 1811386 502 324 6 869,34 TCC=0,35 2664652 2664652 122 89 1 137,05 TCC=0,35 3242064 3242064 72 39 1 64,26

TCC=0,5 1522127,5 1473228 532 371 9 1317,76 TCC=0,5 2373786 2055981 355 239 5 841,35 TCC=0,5 1305232,45 1287698 794 610 10 2247,34 TCC=0,5 1876746,33 1774777 650 430 9 1406,72 TCC=0,5 1492439,53 1384899 741 421 13 1220,23 TCC=0,5 2178542,33 2059803 249 177 3 338,94 TCC=0,5 2633185 2633185 46 23 1 31,47

In bovenstaande tabel is telkens in blauw aangeduid wanneer er slechts 1 node doorlopen werd. Het blijkt dat dit vooral het geval is voor TCC=0,2. Bovendien is het zo dat het aantal maal dat er maar 1 node onderzocht werd, daalt naarmate de waarde van TCC toeneemt (zes maal voor TCC=0,35 en drie keer voor TCC=0,5). Ook is het opvallend dat wanneer zowel DCD als SCD gelijk zijn aan 1, de drie verschillende waarden voor TCC allen leiden tot slechts 1 node. Dit kan verklaard worden door het uiterst restrictieve karakter van de bijhorende personeelsvereisten. Deze zijn immers zodanig, dat ze zeer geconcentreerd zijn op een aantal dagen en shifts. Dit zorgt ervoor dat er weinig ruimte overblijft voor aanpassingen in de configuratie van de betrokken werknemers. Een ander opvallend resultaat is dat, ook bij DCD=0 en SCD=0, twee van de drie instanties maar 1 doorlopen node hebben. Dit is het geval voor de instanties met het hoogst aantal werknemers, namelijk 78 voor TCC=0,2 en 44 voor TCC=0,35. De mogelijke reden voor dit fenomeen kan zijn dat, door het groter aantal werknemers, er onmiddellijk meer werknemers met gepaste schema’s zijn om de personeelsvereisten in te lossen. Op deze manier worden reeds meer goede mogelijkheden tijdens de eerste iteratie behandeld dan het geval is voor TCC=0,5. Voor TCC=0,5 werden uiteindelijk 13 nodes onderzocht, wat resulteert in een sterke stijging in de tijd nodig om tot een oplossing te komen. Deze logica kan overigens verder getrokken worden naar de andere meest cyclische klassen, i.e. de klassen waarbij SCD=0 en de klassen waarbij DCD=0. Tabel 23 toont aan dat er telkens voor SCD=0 slechts 1 of, in het geval dat DCD=1, 2 nodes onderzocht worden voor TCC=0,2. Bovendien is het aantal onderzochte nodes voor de meest cyclische probleeminstanties, zoals uit onderstaande grafiek (figuur 3) blijkt, telkens minder dan voor TCC=0,35 en TCC=0,5. Figuur 5 geeft hetzelfde weer als figuur 3 maar dan voor de klassen waarbij DCD vastligt op 0. Bij SCD=1 is er echter wel een stijging in het aantal nodes op te merken, die is zelfs zeer uitgesproken voor TCC=0,2. Voor de andere klassen met TCC=0,2 wordt ook slechts 1 node onderzocht. We kunnen hierbij besluiten dat voor een groot aantal werknemers de kost (tijd, aantal iteraties en toegevoegde kolommen), die gepaard gaat bij het vinden van een gepast schema, het laagst is voor de meest cyclische schema’s. Er zal in het verdere verloop van deze sectie meer bewijs gezocht worden om deze vaststelling te ondersteunen. De vraag die nu gesteld kan worden is, of er al dan niet een relatie bestaat tussen het aantal onderzochte nodes en de integere oplossingswaarde. Met andere woorden, hoe goed is een oplossing rekening houdend met het aantal doorlopen nodes? Om deze vraag te beantwoorden worden ook hier twee vergelijkingen gemaakt, één waarbij SCD vast ligt en één waarbij DCD vast ligt. Figuur 3 en 4 geven het aantal onderzochte nodes en de waarde van de integere oplossing in het 46

geval dat SCD vast ligt op nul. De grafieken voor de andere waarden voor SCD, kunnen teruggevonden worden in appendix C.

Aantal Nodes 30 25 20 15 10 5 0

TCC=0,2 TCC=0,35 TCC=0,5

Figuur 3: SCD=0

IP oplossing 5000000 4000000 3000000 2000000 1000000 0

TCC=0,2 TCC=0,35 TCC=0,5

Figuur 4: SCD=0

De evolutie van zowel het aantal onderzochte nodes en de integere oplossing doet vermoeden dat er een verband bestaat tussen deze twee parameters. Dit verband lijkt te betekenen dat, hoe meer nodes doorlopen worden vooraleer een uitkomst gevonden wordt, hoe lager de waarde van deze uitkomst zal zijn. Om deze trend te kunnen bevestigen, werden de correlaties tussen het aantal nodes en de waarde van de integere oplossing berekend (tabel 24).

47

TCC=0,2 SCD=0 -0,99214 SCD=0,25 -0,99941 SCD=0,5 -0,94487 SCD=0,75 -0,84104 SCD=1 -0,69631

Correlatie TCC=0,35 -0,70633 -0,25514 -0,96992 -0,86222 -0,75045

TCC=0,5 0,39458 -0,99891 -0,84228 -0,91408 -0,72128

Tabel 24: correlaties

In tweede instantie werd de DCD samen met de TCC constant gehouden waardoor enkel de SCD verandert. Opnieuw worden hier enkel de grafieken, voor het aantal nodes en de integere oplossingen, gegeven voor één geval. Dit is het geval waarbij DCD gelijk is aan nul. De andere grafieken zijn terug te vinden in appendix D.

Aantal nodes 50 40 30 20

TCC=0,2

10

TCC=0,35

0

TCC=0,5

Figuur 5: DCD=0

IP oplossing 4000000 3500000 3000000 2500000 2000000 1500000 1000000 500000 0

TCC=0,2 TCC=0,35 TCC=0,5

Figuur 6: DCD=0

48

De relatie tussen de grootte van de integere oplossing en het aantal nodes die nodig waren om tot deze oplossing te komen is voor TCC=0,2 zeer uitgesproken. Het is duidelijk te zien dat, op het moment dat SCD gelijk wordt aan één, er een sterke daling is in de oplossingswaarde. Tegelijkertijd is er een sterke stijging waar te nemen in het aantal nodes. Om deze trend te kunnen bevestigen, is opnieuw een correlatietest uitgevoerd (tabel 25).

TCC=0,2 DCD=0 -1,00000 DCD=0,25 -0,99684 DCD=0,5 -0,70208 DCD=0,75 -0,66883 DCD=1 -0,99838

Correlatie TCC=0,35 0,45943 -0,66270 -0,24517 -0,68016 -0,76301

TCC=0,5 -0,79915 -0,81086 -0,29694 -0,78261 -0,87003

Tabel 25: correlaties

Zowel tabel 24 als tabel 25 maken duidelijk dat er een soort van tegengestelde relatie bestaat tussen de twee factoren. In elke tabel is er echter wel één uitzondering waarbij de waarde van de oplossing toeneemt naarmate het aantal onderzochte nodes toeneemt. Dit is telkens zo voor de meest cyclische klasse uit de tabel. Met de meest cyclische klasse wordt de klasse bedoeld die, in vergelijking met de andere klassen, de meest stabiele personeelsvereisten heeft en dus de laagste waarde voor DCD en/of SCD heeft. Indien SCD constant gehouden wordt op nul, dan is dit het geval voor TCC=0,5 en wanneer DCD gelijk blijft aan nul voor TCC=0,35. 6.3.2 Verminderde cycliciteit Rekening houdend met de vaststelling dat er in de meeste gevallen wel degelijk een soort van omgekeerde relatie bestaat tussen het aantal nodes en de oplossingswaarde, is het interessant om te kijken welk effect een vermindering in de cycliciteit heeft op de waarde van de oplossing. De veronderstelling die hierbij gemaakt wordt, is dat het aantal nodes zou moeten toenemen door het minder strikt maken van de cycliciteitsbeperking. Het verwachte gevolg van deze actie is dat de waarde van de oplossing zal verminderen. Enkel de probleeminstanties waarbij de oplossing gevonden werd na het doorlopen van slechts één node (zie tabel 26 voor de resultaten waarbij TCC=0,2, tabel 27 voor TCC=0,35 en tabel 28 voor TCC=0,5), zullen aan de vermindering van de beperking op cycliciteit worden onderworpen. De reden voor deze keuze is dat, voor de probleeminstanties die meerdere nodes hebben doorlopen, blijkt dat het vinden van de oplossing, voor een 100% cyclisch schema, reeds vrij lang duurde. Dit zou tot gevolg kunnen hebben dat de tijd nodig om een minder cyclische oplossing te vinden veel te hoog wordt (zie Millar en Kiragu 1998) om nog relevant te zijn. Bovendien wordt er verwacht dat voor deze 49

instanties het verminderen van de cycliciteit een kleiner effect zal hebben op de waarde van de integere oplossing aangezien er reeds meerdere nodes onderzocht werden. aantal nodes

TCC=0,2 - DCD=0 - SCD=0

IP oplossing

aantal nodes

TCC=0,2 - DCD=0 - SCD=0,5

IP oplossing

0

2

74600

0

1

3711750

0,2

1

3725091

0,2

1

3717683

0,4

1

3730970

0,4

3

264156

0,6

1

3742008

0,6

3

289025

0,8

2

89119

0,8

1

3740621

1

3757454 IP oplossing

1

1 aantal nodes

TCC=0,2 - DCD=0 - SCD=0,75

3762139 1 IP aantal oplossing TCC=0,2 - DCD=0,25 - SCD=0 nodes

0

1

3709335

0

1

3716735

0,2

1

3710205

0,2

1

3725091

0,4

6

558957

0,4

4

157749

0,6

12

970488

0,6

5

165384

0,8

1

3746039

0,8

1

3738715

1


1 TCC=0,2 - DCD=0,25 SCD=0,25

1 aantal nodes

3758334 IP TCC=0,2 - DCD=0,25 oplossing SCD=0,5

1 aantal nodes

0

2

348877

0

2

444303

0,2

1

3717612

0,2

3

430417

0,4

3

325658

0,4

5

495472

0,6

5

356627

0,6

1

3729857

0,8

1

3740520

0,8

1

3745791

1

3758533 IP oplossing 3706833

1 TCC=0,2 - DCD=0,25 SCD=0,75

1 aantal nodes


0

3

469362

0

1

0,2

5

533707

0,2

8

829228

0,4

6

528569

0,4

1

3733918

0,6

11

836819

0,6

11

976464

0,8

1

3778190

0,8

1

3751011

1


1 TCC=0,2 - DCD=0,5 - SCD=0,25

1 aantal nodes


0

7

729707

0

20

1393224

0,2

1

3700366

0,2

11

1447011

0,4

9

836742

0,4

19

1592660

0,6

10

961424

0,6

22

1618944

0,8

1

3742971

0,8

25

1742696

1

1

3798901

1

1

3864389

50

TCC=0,2 - DCD=0,75 - SCD=0,5

aantal nodes

IP oplossing

aantal nodes

TCC=0,2 - DCD=0,75 - SCD=1

IP oplossing

0

20

1447905

0

1

4322916

0,2

12

1441571

0,2

2

2191561

0,4

80

1467669

0,4

2

2347761

0,6

1

3995512

0,6

1

4590672

0,8

1

4109870

0,8

1

4699256

1


1

1 aantal nodes

TCC=0,2 - DCD=1 - SCD=0,5

4323029 IP oplossing TCC=0,2 - DCD=1 - SCD=1

1 aantal nodes

0

1

4555345

0

1

4418574

0,2

2

3000240

0,2

1

4482683

0,4

1

4513575

0,4

1

4539943

0,6

1

4531992

0,6

1

4583701

0,8

1

4618113

0,8

1

4675247

1

1

4721906

1

1

4710007

Tabel 26: resultaten % cycliciteit

aantal nodes

TCC=0,35 - DCD=0 - SCD=0

IP oplossing

TCC=0,35 - DCD=0,25 SCD=0,25

aantal nodes

IP oplossing

0

1

1296821

0

2

414115

0,2

2

178837

0,2

3

398864

0,4

2

176152

0,4

4

414054

0,6

4

188200

0,6

1

1485250

0,8

3

160580

0,8

1

1516431

1

1

1358047

1

1

1563775

aantal TCC=0,35 - DCD=0,5 - SCD=0 nodes

IP oplossing

aantal nodes

TCC=0,35 - DCD=1 - SCD=0,5

IP oplossing

0

292

1521964

0

1

2108571

0,2

56

1668024

0,2

10

1810915

0,4

53

1893800

0,4

3

1848219

0,6

134

2080846

0,6

1

2328324

0,8

45

2283053

0,8

1

2452402

1


1 TCC=0,35 - DCD=1 SCD=0,75

50 aantal nodes

2560292 IP oplossing TCC=0,35 - DCD=1 - SCD=1

1 aantal nodes

0

2

1764607

0

1

2610102

0,2

1

2086235

0,2

1

2791529

0,4

2

1968753

0,4

1

2852268

0,6

1

2525064

0,6

1

3008861

0,8

2

2421848

0,8

1

3112756

1

1

2971910

1

1

3242064


51

TCC=0,5 - DCD=0,25 - SCD=1

aantal nodes

IP oplossing

0

13

1120826

0,2

13

1210723

0,4

27

1203472

0,6

17

1300515

0,8

13

1351405

1

1

1877577

TCC=0,5 - DCD=0,75 - SCD=1

aantal nodes

IP oplossing

0

5

1296545

0,2

1

1668024

0,4

1

1893800

0,6

3

1625094

0,8

1

2283053

1

1

2560292

TCC=0,5 - DCD=1 - SCD=1

aantal nodes

IP oplossing

0

1

1933275

0,2

1

2053295

0,4

1

2225708

0,6

1

2354654

0,8

1

2455432

1

1

2633185


Opnieuw valt het op (tabel 26) dat er heel wat probleeminstanties, met SCD gelijk aan 0, slechts 1 node doorlopen hebben vooraleer de optimale oplossing gevonden werd. Dit wijst erop dat de verbetering door het verminderen van de cycliciteit in deze gevallen eerder beperkt is. Er zijn twee instanties die vergeleken kunnen worden, zoals in figuur 3 en 5. Deze instanties zijn TCC=0,2 – DCD=0 – SCD=0 en TCC=0,2 – DCD=0,5 – SCD=0 enerzijds en TCC=0,35 – DCD=0 – SCD=0 en TCC=0,35 – DCD=0,5 – SCD=0 anderzijds. TCC=0,2 - DCD=0 - SCD=0

aantal nodes

IP oplossing TCC=0,35 - DCD=0 - SCD=0

aantal nodes

IP oplossing

0

2

74600

0

1

1296821

0,2

1

3725091

0,2

2

178837

0,4

1

3730970

0,4

2

176152

0,6

1

3742008

0,6

4

188200

0,8

2

89119

0,8

3

160580

1

1

3762139

1

1

1358047

Tabel 29: vergelijking (DCD=0-SCD=0)

Uit tabel 29 blijkt dat het maximaal aantal nodes die doorlopen worden voor TCC=0,2 zeer beperkt blijven. Wanneer er echter dan toch 2 nodes doorlopen worden, is de verbetering in de oplossing spectaculair. Ook voor TCC=0,35 is het aantal onderzochte nodes eerder beperkt. De verbetering in de oplossing is hier echter minder spectaculair. 52

Ondanks deze verbeteringen in de oplossing, is het niet nuttig om, voor de bijhorende personeelsvereisten, een vermindering van cycliciteit door te voeren. De tijd die nodig is om tot een oplossing te komen is hier voor beide waarden van TCC gewoon te hoog. Deze varieert voor TCC=0,2 van 16279,93 tot 17003,72 seconden voor de twee gevallen waarbij 2 nodes doorlopen worden. Dit betekent dat het bijna 5 uur duurt om de oplossing te vinden. Voor TCC=0,35 is dit van 13694,43 (bijna 4 uur) tot 18636,23 seconden (meer dan 5 uur). TCC=0,2 - DCD=0,5 - SCD=0 aantal nodes

IP oplossing

TCC=0,35 - DCD=0,5 - SCD=0 aantal nodes

IP oplossing

0

1

3706833

0

292

1521964

0,2

8

829228

0,2

56

1668024

0,4

1

3733918

0,4

53

1893800

0,6

11

976464

0,6

134

2080846

0,8

1

3751011

0,8

45

2283053

1

1

3768326

1

50

2560292

Tabel 30: vergelijking (DCD=0,5-SCD=0)

Tabel 30 geeft aanleiding tot dezelfde conclusies. Hier zijn het aantal doorlopen nodes echter wel veel hoger. Als voorlopige conclusie kan gesteld worden dat bij TCC=0,2 minder nodes doorlopen worden, maar als er dan toch meer dan 1 node onderzocht wordt, is de verbetering veel groter voor TCC=0,2 dan voor TCC=0,35. Ook bij de andere klassen zijn er redelijk veel instanties met slechts 1 doorlopen node. Het blijkt echter wel dat wanneer er meer dan 1 node onderzocht werd, het resultaat ook voor deze instanties sterk verbeterde. Voor de volledigheid en vergelijkbaarheid, tussen de verschillende graden van cycliciteit, zijn de instanties met volledige cycliciteit ook in bovenstaande tabellen opgenomen. Nu moet onderzocht worden of er wel degelijk een verband bestaat tussen het verlagen van de cycliciteit en de grootte van de oplossing. Bovendien zal ter bevestiging ook nog eens de relatie tussen het aantal nodes en de uitkomst onderzocht worden. Om deze verbanden te kunnen beoordelen zal opnieuw een correlatietest uitgevoerd worden, maar deze keer voor zowel de cycliciteitsklasse als voor de nodes. Aangezien het in bepaalde gevallen zo is dat deze herberekeningen voor dezelfde waarden voor DCD en SCD gedaan werden, kunnen de correlaties tussen deze instanties vergeleken worden. Onderstaande tabellen (tabellen 31-33) bevatten al de correlaties voor alle instanties, voor zowel de nodes als de cycliciteitsklassen.

53

DCD=0-SCD=0 DCD=0-SCD=0,5 DCD=0-SCD=0,75 DCD=0,25-SCD=0 DCD=0,25-SCD=0,25 DCD=0,25-SCD=0,5 DCD=0,25-SCD=0,75 DCD=0,5-SCD=0 DCD=0,5-SCD=0,25 DCD=0,75-SCD=0 DCD=0,75-SCD=0,5 DCD=0,75-SCD=1 DCD=1-SCD=0,5 DCD=1-SCD=1

TCC=0,2 correlatie IP-nodes correlatie IP-klasse -0,999974687 0,213364648 -0,99994829 0,009651719 -0,870076246 0,026563548 -0,984789103 0,006534339 -0,79630995 0,492325315 -0,791424165 0,882974622 -0,662879011 0,864657211 -0,970134964 0,230267481 -0,963278407 0,523393324 -0,793753652 0,746980087 -0,64008705 0,901198197 -0,991935572 0,524268624 -0,993268132 0,467214019 NVT 0,995298242 Tabel 31: correlaties TCC=0,2

DCD=0-SCD=0 DCD=0,25-SCD=0,25 DCD=0,5-SCD=0 DCD=1-SCD=0,5 DCD=1-SCD=0,75 DCD=1-SCD=1

TCC=0,35 correlatie IP-nodes correlatie IP-klasse -0,769893317 0,023662988 -0,86527736 0,891285369 0,023735758 0,801676627 -0,689966098 0,81405634 -0,595497671 0,927838971 NVT 0,995037433 Tabel 32: correlaties TCC=0,35

DCD=0,25-SCD=1 DCD=0,75-SCD=1 DCD=1-SCD=1

TCC=0,5 correlatie IP-nodes correlatie IP-klasse -0,746877772 0,840987531 -0,744927401 0,909962518 NVT 0,997608376 Tabel 33: correlaties TCC=0,5

In het grijs staat, bij de correlatie tussen de oplossing en het aantal doorlopen nodes, niet van toepassing. Dit is zo omdat het aantal nodes in dit geval nooit veranderde (tabel 26, 27 en 28). Bijgevolg zal de standaarddeviatie gelijk zijn aan nul en aangezien deze standaarddeviatie in de noemer van de formule van de correlatie staat, kan deze dus niet berekend worden. De rood aangeduide cel in tabel 32 is de enige instantie waarbij de redenering van extra nodes leiden tot lagere oplossingen, niet volledig opgaat (zie tabel 30 voor de evolutie van het aantal nodes). Merk wel op dat deze correlaties, zowel tussen de oplossing en de nodes als tussen de oplossing en de graad van cycliciteit, slechts indicaties geven. Het is dus goed mogelijk dat er gevallen zijn waarbij de 54

oplossing stijgt naarmate het aantal nodes toeneemt terwijl de algemene trend in die klasse een negatief verband weergeeft. Een eerste observatie die volgt uit tabel 31-33 is dat bij DCD=1 en SCD=1, en dus bij de meest acyclische personeelsvereisten, de correlatie tussen de oplossing van het probleem en graad van cycliciteit het hoogst zijn. De verbeteringen in de oplossing (tabel 26, 27 en 28) zijn niet uitzonderlijk, maar wel consistent. In zulke gevallen is het dus zeker aangeraden om de cycliciteit van het vooropgestelde schema te verminderen. Ook is deze correlatie bij TCC=0,5 lichtjes hoger dan bij TCC=0,2. Dit betekent dat het effect van het verminderen van de cycliciteit net iets hoger ligt voor hogere TCC-waarden dan voor kleinere. Merk wel op dat uit de resultaten uit tabel 23 blijkt dat de correlatie voor TCC=0,35 kleiner is dan indien TCC=0,2. Rekening houdend met de resultaten uit tabel 23, zou het interessant kunnen zijn om een aantal extra instanties opnieuw te berekenen met in acht name van de verschillende graden van cycliciteit. Door dit te doen, wordt het aantal instanties die over de TCC-klassen kunnen vergeleken worden groter. Nu is dit enkel maar mogelijk voor DCD=1 en SCD=1, wat niet tot heel algemene conclusies kan leiden. De volgende instanties komen hiervoor in aanmerking: TCC=0,35 – DCD=0,75 – SCD=1; TCC=0,5 – DCD=0,5 – SCD=0; TCC=0,5 – DCD=1 – SCD=0,5; TCC=0,2 – DCD=1 – SCD=0,75 en TCC=0,5 – DCD=1 – SCD=0,75. Deze vijf problemen zijn het meest geschikt voor verder onderzoek omdat het aantal nodes, die doorlopen werden in de zoektocht naar een oplossing, én de tijd, die daarvoor nodig was, vrij klein zijn in vergelijking met andere oplossingen. Zo werd voor TCC=0,5 – DCD=0,5 – SCD=0 5 nodes doorlopen in 1762,82 seconden. Rekening houdend met de meeste andere tijden voor de andere instanties is deze tijd vrij laag. Voor de andere geselecteerde instanties waren er zelfs slechts 2 of 3 nodes die doorlopen werden met een tijd van minder dan 10 minuten. Aangezien reeds aangetoond werd dat er in de meeste gevallen een negatief verband bestaat tussen het aantal nodes en de waarde van de oplossing, zullen voor deze extra instanties enkel de correlaties tussen de integere oplossing en de verschillende klassen van cycliciteit vermeld worden (tabel 34). correlatie IP-klasse TCC=0,35-DCD=0,75-SCD=1 0,615448782 0,821723804 TCC=0,5-DCD=0,5-SCD=0 TCC=0,5-DCD=1-SCD=0,5 0,913589229 TCC=0,2-DCD=1-SCD=0,75 -0,306106808 TCC=0,5-DCD=1-SCD=0,75 0,733984498 Tabel 34: extra correlaties

55

Door deze extra berekeningen is het mogelijk om de invloed van de waarde van TCC beter in te schatten. Tabel 33 bevat deze cijfers voor de drie verschillende waarden voor TCC om de vergelijking te vereenvoudigen. De correlaties in cursief zijn deze die extra berekend werden.

DCD=0,75-SCD=1 DCD=0,5-SCD=0 DCD=1-SCD=0,5 DCD=1-SCD=0,75

TCC=0,2 0,524268624 0,230267481 0,467214019 -0,306106808

TCC=0,35 0,615448782 0,801676627 0,81405634 0,927838971

TCC=0,5 0,909962518 0,821723804 0,913589229 0,733984498

Tabel 35: vergelijking correlaties

In de eerste drie gevallen is er een duidelijke trend waarbij de relatie tussen de grootte van de oplossingswaarde en de verschillende graden van cycliciteit toeneemt naarmate de waarde voor TCC stijgt. De achterliggende reden zou dezelfde kunnen zijn als diegene die hierboven aangehaald werd. Hoe meer werknemers, hoe gemakkelijker het cyclische schema kan voldaan worden en hoe minder nuttig een vermindering in de graad van cycliciteit is. Het is echter wel opvallend dat voor DCD=1 en SCD=0,75 deze trend niet bevestigd kan worden. In dit geval zal voor TCC=0,2 de waarde van de oplossing zelfs een lichte stijging ondervinden naarmate de cycliciteit verminderd wordt. Dit is niet helemaal tegenstrijdig met de hierboven aangehaalde reden die stelt dat door het groter aantal werknemers een cyclisch schema beter toepasbaar is. Het eigenlijke probleem zit in de overgang tussen de twee andere waarden voor TCC. De verwachting was dat de correlatie hoger zou zijn voor TCC=0,5. Zo’n tegenstrijdigheid bestaat ook wanneer zowel DCD als SCD gelijk zijn aan nul. In dit geval is de gevonden correlatie groter voor TCC=0,2 (=0,213364648) dan voor TCC=0,35 (=0,023662988). Door het bestaan van deze tegenstrijdigheden, werd er op zoek gegaan naar een andere klasse van gelijke waarden voor zowel DCD als SCD. De voorkeur gaat hier uit naar instanties waarbij voor twee van de drie waarden voor TCC na 1 node reeds een oplossing gevonden werd. Dit leidt naar DCD=0,25 en SCD=0,25. Voor deze parameters werd na 1 node reeds een oplossing gevonden voor TCC=0,2 en TCC=0,35. De extra correlatie die dus berekend moet worden, is deze voor TCC=0,5 – DCD=0,25 – SCD=0,25. Opnieuw is hier de correlatie voor TCC=0,35 wel hoger dan deze voor TCC=0,2 maar die voor TCC=0,5 blijkt lager te zijn dan deze voor TCC=0,35 (tabel 36). DCD=0,25-SCD=0,25

TCC=0,2 0,492325315

TCC=0,35 0,891285369

TCC=0,5 0,763067

Tabel 36: extra vergelijking correlaties

Het resultaat van al deze vergelijkingen is dat de correlaties meestal een stijgende lijn volgen van TCC=0,2 naar TCC=0,5. Echter, er kan geen sprake zijn van een significant verschil tussen de correlaties voor TCC=0,35 en TCC=0,5. Ondanks het feit dat in drie van de vijf gemaakte vergelijkingen het verwachte patroon (een stijgende correlatie van een lage naar een hogere TCC) 56

wel aanwezig was, kan geen duidelijk verschil gevonden worden tussen TCC=0,35 en TCC=0,5. Hoewel er één uitzondering aanwezig is op de trend, gevonden in de vijf vergelijkingen, kan er wel gezegd worden dat dit verschil in correlatie tussen TCC=0,2 en TCC=0,35 duidelijker aanwezig is. Deze uitzondering bestaat voor TCC=0,2 – DCD=0 – SCD=0 en TCC=0,35 – DCD=0 – SCD=0. Merk op dat de correlatiecoëfficiënten niet noodzakelijk iets zeggen over de grootte van de verbetering in de oplossing en dat zij sterk onderhevig zijn aan “outliers”. Dit zijn waarnemingen die, door hun uitzonderlijke karakter, een grote invloed kunnen hebben op de uitkomst van de regressielijn. Als laatste stap in de vergelijking, tussen de verschillende waarden voor TCC, van de toepasbaarheid van een cyclisch schema zal daarom gekeken worden naar de aanwezigheid van zulke waarnemingen en hun invloed op de uiteindelijke correlatiecoëfficiënt. 1. Bij de eerste observatie (DCD=1 en SCD=1) die hier gemaakt werd, is er geen enkel probleem met “outliers”. Aangezien het aantal onderzochte nodes bij elk van de verschillende graden van cycliciteit gelijk was aan 1, is dit niet zo verwonderlijk. 2. Ook werd een uitzondering gevonden op de algemene trend tussen instanties waarbij TCC=0,2 of TCC=0,35 is. DCD=0-SCD=0 0 0,2 0,4 0,6 0,8 1

TCC=0,2 TCC=0,35 74600 1296821 3725091 178837 3730970 176152 3742008 188200 89119 160580 3762139 1358047

Tabel 37: outliers (DCD=0-SCD=0)

Voor zowel TCC=0,2 en TCC=0,35 zijn er twee observaties die respectievelijk veel lager en veel hoger zijn dan de andere oplossingswaarden. 3. Bij de vergelijkingen die gemaakt werden (tabel 35 en 36) zijn, in tegenstelling tot puntje 1, zulke observaties wel aanwezig. Aangezien er twee vergelijkingen zijn die een ietwat contraintuïtief resultaat opleveren, zullen deze gecontroleerd worden op uitzonderlijke observaties (tabel 38 en 39). De tabellen die de overige vergelijkingen bevatten, staan in appendix E. DCD=0,25-SCD=0,25 TCC=0,2 TCC=0,35 TCC=0,5 0 348877 414115 261502 0,2 3717612 398864 604255 0,4 325658 414054 266606 0,6 356627 1485250 416447 0,8 3740520 1516431 1110253 1 3752703 1563775 952804 Tabel 38: outliers (DCD=0,25-SCD=0,25) 57

TCC=0,2 en TCC=0,35 hebben telkens drie hoge en drie lage waarden, terwijl bij TCC=0,5 enkel de waarde die overeenstemt met 80% cycliciteit uit de algemene trend valt. DCD=1-SCD=0,75 0 0,2 0,4 0,6 0,8 1

TCC=0,2 TCC=0,35 TCC=0,5 3829680 1764607 1953295 3974316 2086235 1821210 4161571 1968753 2141884 2875142 2525064 2045814 4511497 2421848 2006745 3022833 2971910 2442241

Tabel 39: outliers (DCD=0,25-SCD=0,25)

Bij TCC=0,2 bleek dat de correlatie tussen de cycliciteitsklassen en de oplossing lichtjes negatief was en tabel 39 toont aan dat dit waarschijnlijk te maken heeft met de oplossingswaarden voor 60 en 100% cycliciteit. Uit deze en de tabellen in appendix E blijkt dat er omzichtig moet omgesprongen worden met de correlatiecoëfficiënten en de conclusies die hierop gebaseerd worden. Hoewel over het algemeen geldt dat “outliers” best verwijderd worden, bestaat hierover toch geen echte consensus in de literatuur (Osborne en Overbay 2004). Hiermee rekening houdend, zullen deze uitzonderlijke resultaten dan ook niet weggelaten worden. Bovendien zou het wel weglaten ervoor kunnen zorgen dat de realiteit niet meer voldoende weerspiegeld wordt in de correlatiecoëfficiënten. Het resultaat van de correlatietest moet dus gecombineerd worden met andere vaststellingen. De vaststelling waar hier naar verwezen wordt, is het feit dat het aantal maal dat er slechts 1 node onderzocht wordt, het hoogst is voor TCC=0,2 en daalt met een toename in de waarde voor TCC. Doordat slechts één node onderzocht moest worden om tot de beste oplossing te komen, betekent dit dat de tijd die hiervoor nodig was, beperkt is gebleven. Dit betekent dus dat voor een groot aantal werknemers sneller een oplossing gevonden kan worden die voldoet aan de verschillende beperkingen, waaronder de beperking op de cycliciteit. Dit is vooral het geval voor lage waarden voor DCD en SCD omdat voor die waarden de personeelsvereisten over de verschillende TCC-klassen nog zeer gelijkaardig zijn. Door de daling in het aantal maal dat er maar 1 node onderzocht wordt, zijn er steeds meer instanties die een langere tijd nodig hebben om tot een oplossing te komen. De conclusie die we hier uit kunnen trekken is dat hoe meer werknemers er beschikbaar zijn voor gelijkaardige personeelsvereisten, hoe beter aan een cyclisch schema kan voldaan worden. Dit blijkt ook uit de studie van de correlaties, waarbij de correlatie tussen de graad van cycliciteit en de uitkomst over het algemeen het kleinst was voor TCC=0,2. Een kleine correlatie heeft tot gevolg dat een verlaging van de cycliciteit slechts een beperkte verbetering in de oplossing met zich mee brengt. 58

Tot nu toe lag de focus op het vergelijken van de toepasbaarheid van cyclische schema’s tussen de klassen met verschillende waarden voor TCC. Binnen een klasse met een bepaalde waarde voor deze parameter (TCC) kunnen echter ook verschillen optreden in de toepasbaarheid van een cyclisch schema. Om dit te testen zal opnieuw naar de correlatiecoëfficiënt gekeken worden. Deze coëfficiënten zijn dezelfde als deze in tabellen 31 tot en met 34. Rekening houdend met de mogelijkheid dat er bijgevolg “outliers” kunnen optreden, zal ook naar de tijd gekeken worden die nodig is om een oplossing te vinden. Via de combinatie van deze factoren zouden er een aantal trends moeten verschijnen (tabellen 40, 41 en 42). Deze tabellen bevatten een aantal extra berekeningen, in vergelijking met deze in bovenstaande tabellen, om meer vergelijkingen te kunnen maken. Deze extra berekening zijn TCC=0,35 – DCD=0,25 – SCD=1; TCC=0,35 – DCD=0,75 – SCD=0,5 en TCC=0,5 – DCD=0,75 – SCD=0,5. Elk van deze extra instanties had voor 100% cycliciteit minder dan 1 uur nodig voor het vinden van een oplossing. TCC=0,2 tijd minimum maximum

correlatie IPklasse

1

DCD=0-SCD=0

154,70

17003,72

0,213364648

2

DCD=0-SCD=0,5

174,18

17813,97

0,009651719

3

DCD=0-SCD=0,75

304,67

14439,91

0,026563548

4

DCD=0,25-SCD=0

147,50

14250,58

0,006534339

5

DCD=0,25-SCD=0,25

283,62

14723,69

0,492325315

6

DCD=0,25-SCD=0,5

263,11

13499,36

0,882974622

7

DCD=0,25-SCD=0,75

260,41

16996,82

0,864657211

8

DCD=0,5-SCD=0

283,55

10805,43

0,230267481

9

DCD=0,5-SCD=0,25

208,25

11279,71

0,523393324

10

DCD=0,75-SCD=0

4190,17

8590,63

0,746980087

11

DCD=0,75-SCD=0,5

222,90

7137,49

0,901198197

12

DCD=0,75-SCD=1

249,27

440,91

0,524268624

13

DCD=1-SCD=0,5

180,56

449,61

0,467214019

14

DCD=1-SCD=0,75

151,29

363,36

-0,306106808

15

DCD=1-SCD=1

102,33

119,91

0,995298242

Tabel 40: tijd-correlatie (TCC=0,2)

59

TCC=0,35 tijd Minimum Maximum

correlatie IPklasse

1

DCD=0-SCD=0

266,55

18636,23

0,023662988

2

DCD=0,25-SCD=0,25

165,58

18357,35

0,891285369

3

DCD=0,25-SCD=1

227,38

10988,13

0,72232146

4

DCD=0,5-SCD=0

9742,28

11063,03

0,801676627

5

DCD=0,75-SCD=0,5

3269,36

9098,18

0,910621563

6

DCD=0,75-SCD=1

93,25

347,00

0,615448782

7

DCD=1-SCD=0,5

98,56

1410,73

0,81405634

8

DCD=1-SCD=0,75

98,41

338,69

0,927838971

9

DCD=1-SCD=1

53,22

64,43

0,995037433


TCC=0,5 tijd Minimum Maximum

correlatie IPklasse

1

DCD=0,25-SCD=0,25 12106,80

15230,30

0,763067477

2

DCD=0,25-SCD=1

1912,11

3123,46

0,840987531

3

DCD=0,5-SCD=0

9254,43

11058,33

0,821723804

4

DCD=0,75-SCD=0,5

782,54

4243,28

0,451437276

5

DCD=0,75-SCD=1

71,44

774,55

0,909962518

6

DCD=1-SCD=0,5

84,65

1990,97

0,913589229

7

DCD=1-SCD=0,75

88,06

1753,83

0,733984498

8

DCD=1-SCD=1

36,25

38,81

0,997608376


Tabellen 40, 41 en 42 bevatten voor elke instantie de minimale en maximale tijd die nodig was om tot de optimale oplossing te komen. Deze minima en maxima zijn een weergave van de verschillende tijden over de verschillende graden van cycliciteit. Merk op dat er, bij het bepalen van bovenstaande minima en maxima, geen rekening gehouden werd met de tijd nodig om de instantie met 100% cycliciteit op te lossen. Om te weten welke tijd aanvaardbaar is om een bepaald probleem op te lossen, wordt gekeken naar de maximale tijd die nodig was om de originele problemen (100% cycliciteit) op te lossen (zie tabel 23).

Tijd (in seconden)

TCC=0,2

TCC=0,35

TCC=0,5

9345,19

9872,80

8019,37

Tabel 43: maximale tijd 100% cycliciteit

Tabel 43 toont voor elke TCC-klasse de maxima. Deze maxima zullen gebruikt wordt als richttijd. Deze tijd, in combinatie met de correlatie, dient om te bepalen wanneer een vermindering van de cycliciteit al dan niet aanvaardbaar is. Aangezien bij cyclische schema’s sneller een oplossing 60

gevonden wordt dan bij niet-cyclische schema’s, moeten deze maxima wel nog enigszins verhoogd worden om daarmee rekening te houden (zie deel 2: literatuurstudie). Tabel 40 toont duidelijk dat de tijd, nodig om een oplossing te vinden, in vergelijking met tabel 49, tot en met DCD=0,25 en SCD=0,75 (nummer 7) zeer hoog ligt. Ook de correlatie blijft in het begin vrij laag en dit tot en met DCD=0,25 en SCD=0,25 (nummer 5). De lage correlaties gekoppeld aan de hoge oplossingstijden, zorgen ervoor dat het weinig interessant is om voor deze instanties de cycliciteit te verlagen. Voor de andere twee instanties, i.e. nummer 6 en 7, blijkt wel dat de correlatie tussen een vermindering van de cycliciteit en de verbetering in de waarde van de oplossing hoog is. In combinatie met deze hoge correlatie is er echter een lange oplossingstijd. Hierdoor is het beter om opnieuw nog een gewoon cyclisch schema te gebruiken. Vanaf DCD=0,5 wordt het interessanter. De oplossingstijden beginnen lager en lager te worden. Het is echter wel zo dat de correlaties voor een lage waarde van SCD (SCD=0 of SCD=0,25) nog niet voldoende hoog liggen om een verlaagde cycliciteit toe te laten. Vanaf DCD=0,75 (nummer 10) is er een sterke daling in de oplossingstijd. Ondanks de soms wat lage correlaties, is de verlaging van de cycliciteit nu wel interessant. Nu moet nog bepaald worden welke graad van cycliciteit het meest interessant is. Om dit te kunnen bepalen moet tabel 44 vergeleken worden met tabel 26. Deze extra tabel (tabel 44) is nodig omdat de instantie in deze tabel eerst niet werd onderworpen aan een vermindering van de cycliciteit, waardoor deze instantie niet aanwezig is in tabel 26. TCC=0,2 - DCD=1 - SCD=0,75 aantal nodes IP oplossing 0

1

3829680

0,2

1

3974316

0,4

1

4161571

0,6

2

2875142

0,8

1

4511497

1

2

3022833

Tabel 44: nodes - IP oplossing

Voor DCD=0,75 blijkt uit tabel 26 dat voor SCD=0, de cycliciteit best minstens tot 80% wordt verlaagd. Voor SCD=0,5 en 1 is er een sterke verbetering in de oplossingswaarde vanaf 40% cycliciteit. Voor DCD=1 is het duidelijk, uit zowel tabel 26 als 44, dat de cycliciteit best zo laag mogelijk gehouden wordt. Ondanks het feit dat er in tabel 44 redelijk wat variatie zit in de oplossingswaarde, lijkt het ook voor deze instantie beter om de cycliciteit zo laag mogelijk te houden (“outliers”). Tabel 41 (TCC=0,35) en tabel 42 (TCC=0,5) tonen beide eigenlijk dezelfde trend als tabel 40. Vanaf het moment dat DCD gelijk wordt aan 0,75, is het duidelijk dat de combinatie van oplossingstijd en 61

de bijhorende correlaties zodanig is dat vermindering van cycliciteit enkel voordelen kan opleveren. Opvallend is wel dat ook voor DCD=0,25 – SCD=1 er een aanvaardbare combinatie tussen de twee factoren bestaat. Opnieuw is de vraag hoe ver de cycliciteit verminderd moet worden. TCC=0,35-DCD=0,25SCD=1

aantal nodes

IP oplossing

TCC=0,35-DCD=0,75SCD=0,5

aantal nodes

IP oplossing

0

27

1151600

0

18

1290169

0,2

21

1233592

0,2

15

1333663

0,4

22

1357521

0,4

39

1353723

0,6

1

2050333

0,6

20

1430461

0,8

10

1425513

0,8

19

1580220

12


1 TCC=0,35-DCD=0,75SCD=1

15 aantal nodes

1885849 1 IP aantal oplossing TCC=0,5-DCD=0,75-SCD=0,5 nodes

0

1

2278000

0

19

1580220

0,2

2

1887109

0,2

2

1190658

0,4

1

2403359

0,4

13

1447738

0,6

1

2513702

0,6

14

1358223

0,8

2

2282805

0,8

25

1506793

5


1

2 aantal nodes

TCC=0,5-DCD=1-SCD=0,5

2589572 1 IP aantal oplossing TCC=0,5-DCD=1-SCD=0,75 nodes

0

14

1104071

0

1

1953295

0,2

5

1126571

0,2

34

1821210

0,4

1

1510779

0,4

1

2141884

0,6

13

1344890

0,6

2

2045814

0,8

4

1632058

0,8

6

2006745

1

3

2059803

1

2

2442241

Tabel 45: nodes - IP oplossing

Opnieuw worden de extra uitgevoerde instanties in tabel 45 weergegeven. Voor DCD=0,25 en SCD=1 kan de cycliciteit het best verminderd worden tot 80%. Deze conclusie volgt uit de vergelijking van tabel 45 en 28. Bij DCD=0,75 – SCD=0,5 kan de cycliciteit ver teruggedrongen worden maar hier bestaat geen consensus tussen TCC=0,35 en TCC=0,5. Hetzelfde kan gezegd worden over de instanties waarbij DCD=0,25 en SCD=1, DCD=0,75 en SCD=1, DCD=1 en SCD=0,5, of DCD=1 en SCD=0,75. Ook voor TCC=0,35 en TCC=0,5 geldt dat, indien DCD=1 en SCD=1, de cycliciteit best zo ver mogelijk kan verminderd worden. Dit levert immers telkens een verbetering in de oplossingswaarde op zonder significante verhoging in de tijd nodig om deze oplossing te vinden. Over het algemeen kunnen we dus stellen dat cycliciteit het best toepasbaar is wanneer er een groot aantal werknemers ingezet kunnen worden in vergelijking met de personeelsvereisten. Bovendien blijkt dat het minder interessant is om de graad van cycliciteit te laten verminderen voor DCD=0, 62

DCD=0,25 en DCD=0,5. Hierop is telkens wel een uitzondering, namelijk wanneer SCD gelijk wordt aan 1. In dat geval is het nuttig om rekening te houden met de voordelen van een vermindering in de graad van cycliciteit. Deze uitzondering wordt belangrijker naarmate de waarde van DCD ook toeneemt. Verder werd aangetoond dat vanaf DCD=0,75 de combinatie correlatie en tijd gunstig genoeg is om een minder cyclisch schema te overwegen. Er kan echter geen eenzijdig besluit genomen worden over welke graad van cycliciteit het beste toepasbaar is in zulke gevallen. 6.3.3 Relaxatie andere beperkingen Bij al de vorige resultaten werd nog niet vermeld dat de beperking op het teveel en tekort aan werknemers weggelaten werd. Deze beperkingen zouden er immers voor zorgen dat voor de meest acyclisch en cyclische personeelsvereisten geen passend schema zou kunnen gevonden worden. Dit komt doordat de personeelsvereisten, in het zeer acyclische geval, zeer sterk geconcentreerd zijn op bepaalde shifts en dagen. Het is met andere woorden, gegeven de andere beperkingen, onmogelijk om al de werknemers in te plannen zonder een overtreding te krijgen op bijvoorbeeld het teveel aan werknemers. Dit komt doordat het met deze beperking niet mogelijk zou zijn om elke werknemer zijn of haar contractueel bepaald aantal uren te laten werken. Om de resultaten vergelijkbaar te houden, is er daarom voor gekozen om deze beperking voor zowel de meest cyclische als de meest acyclische personeelsvereisten weg te laten. Merk ook op dat in deel 4 bleek dat het toevoegen van de beperking op het teveel en te weinig aan werknemers, de oplossing niet gevonden kon worden binnen een aanvaardbare tijdslimiet. In dit deel zal gekeken worden op welke manier deze beperkingen toch ingevoerd kunnen worden, waardoor het aantal niet productieve shifttoewijzingen (Maenhout en Vanhoucke 2011) verminderd zou moeten worden. Al deze tests zullen uitgevoerd op de instantie waarbij TCC=0,5 – DCD=1 – SCD=1. De resultaten die bekomen worden, zullen vergeleken worden met de resultaten uit tabel 26. Het is zeer waarschijnlijk dat andere beperkingen zullen verwijderd moeten worden om een mogelijkheid te vinden waarbij zowel de beperking op het teveel en tekort aan werknemers kan toegevoegd worden. Een voorbeeld van zo’n beperking, zoals hierboven al aangehaald, is het contractueel aantal uren die een werknemer moet werken. Een ander voorbeeld is de beperking op het aantal shifts die een werknemer moet werken gedurende de planningsperiode. Door deze beperkingen weg te laten moet het mogelijk worden om ervoor te zorgen dat het teveel en tekort aan werknemers beperkt blijft. Na het toevoegen van de beperkingen op het teveel en te weinig aan werknemers, en het verwijderen van de beperking op het werken van het contractueel bepaald aantal uren blijkt dat het

63

algoritme niet tot een oplossing kan komen. Het model is met andere woorden niet haalbaar zolang het teveel en tekort op 25% van de personeelsvereiste blijft staan. In een volgende stap is er geprobeerd om zowel de beperking op het teveel/tekort aan werknemers weg te laten als de beperking op het aantal uren. De gevonden oplossing staat in tabel 46 onder puntje 1. Dit komt overeen met in totaal 313 onproductieve werktoewijzingen, wat betekent dat er in totaal, verspreid over de hele planningsperiode, 313 werknemers teveel zullen worden toegekend. De bedoeling is nu om te kijken hoe dit verder kan afnemen. Hierna werd het teveel aan werknemers beperkt tot 25% van de personeelsvereiste. Bovendien werd de beperking, die stelt dat een werknemer een bepaald aantal van elke shift moet werken, verwijderd. Dit zorgde echter voor een oplossing waarbij bijna geen enkele werknemer effectief moest werken. Met dit in het achterhoofd, is de beperking op het aantal shifts terug toegevoegd. Er werden nog meerdere combinaties, van verschillende beperkingen op het teveel en tekort aan werknemers, uitgeprobeerd maar allen leiden tot de volgende conclusie: het is, bij deze zeer acyclische personeelsvereisten, niet mogelijk om een werkbare oplossing te vinden met een beperking op het teveel en tekort aan werknemers. In deel 4.6 bleek dat toevoeging van de beperkingen op weekendwerk (identieke weekends en maximaal aantal toegelaten weekends), een grote stijging in de waarde van de doelfunctie veroorzaakten. Hiermee rekening houdend werden, in vergelijking met puntje 1, deze twee beperkingen ook weggelaten. Dit zorgt voor een kleine daling in zowel de waarde van de oplossing en de onproductiviteit (zie punt 2 in tabel 46). Het is ook interessant om eens veranderingen aan te brengen in het maximaal aantal toegelaten fouten en shiftwisselingen. In puntje drie werden deze respectievelijk op 10 en 5 gezet. Dit resulteert opnieuw in een verbetering van de doelfunctie. Er is echter wel een relatief grote toename in de onproductiviteit. In punt 4 werd het probleem ook eens opgelost zonder dat fouten toegelaten werden. Hoewel er een daling is in de onproductiviteit is er toch een toename in de doelfunctie. Dit is te wijten aan het feit dat het tekort aan werknemers is toegenomen. Hiermee rekening houdend, zullen de maxima op het aantal fouten en het aantal shiftwisselingen terug op respectievelijk 20 en 10 gezet worden. Het blijkt dus dat naarmate het aantal preferentie-overtredingen wordt verhoogd, de combinatie onproductiviteit-tekort daalt. Ook bestaat de vraag of het verminderen van de cycliciteit een verdere invloed heeft op het aantal onproductieve toewijzingen van shifts. Punt 5 toont dan ook de oplossing voor een volledig acyclisch schema. Dit is een zeer gunstig resultaat. De laatste beperking die (opnieuw) verwijderd wordt, is deze die bepaalt dat werknemers een vastgelegd aantal shifts van een bepaald type moeten werken. Het resultaat hiervan staat in punt 6. 64

Hierbij is de onproductiviteit zelfs gedaald tot 2. Dit is een enorme verbetering ten opzichte van de originele oplossing. Als laatste stap is dan ook hetzelfde model als in stap 6 nog eens uitgevoerd maar dan voor een 100% cyclisch schema (punt 7).

LP solution IP_solution Iteraties kolommen nodes seconden onproductiviteit

Originele oplossing 2633185 2633185 46 23 1 31,47 408

1 2400441 2400441 48 25 1 32,22 313

2 2348776 2348776 49 26 1 31,45 312

3 2340631 2340631 51 27 1 35,36 325

4 3177482 3177482 43 19 1 22,75 262

5 1261471 1261471 49 26 1 26,45 111

6 840025 840025 48 24 1 24,68 2

7 2041551 2041551 48 24 1 26,46 200

Tabel 46: vergelijking relaxatie

De resultaten tonen dus aan dat door verwijdering van bepaalde beperkingen grote verbeteringen kunnen bekomen worden. Het moet wel gezegd worden dat het verwijderen van deze beperkingen niet altijd even realistisch is. Het is immers zo dat zonder bepaalde beperkingen, zoals op het contractueel bepaald aantal uren, de werknemers veel te weinig zullen werken. Daarom lijkt het interessant om, wanneer de cycliciteit verminderd wordt, de niet-cyclische werknemers te behandelen als werknemers die enkel inspringen wanneer het nodig blijkt te zijn. Dit betekent dat er voor hen geen beperkingen zijn op het aantal uren die ze werken, op weekendwerk en op het aantal keer dat een bepaalde shift gewerkt moet worden. De cyclische werknemers blijven wel nog altijd onderworpen aan de deze beperkingen. Om hiervan het voordeel aan te tonen, zal deze logica eens uitgevoerd worden voor een 80% cyclisch schema. Deze uitkomst wordt in tabel 47 vergeleken met de originele oplossing. De tabel toont dat er reeds een grote afname is in de onproductiviteit bij een kleine vermindering van de cycliciteit. 80% origineel

80% aangepast

LP solution

2455432,00

2220474,00

IP_solution

2455432

2220474

Iteraties

47

46

kolommen

24

23

1

1

37,35

32,24

393

314

nodes seconden onproductiviteit

Tabel 47: vergelijking 80% cycliciteit

65

7. Conclusie In deze masterproef is er een onderzoek gevoerd naar de toepasbaarheid van een cyclisch personeelsplan onder verschillende omstandigheden. Eerst en vooral moest daarvoor een model opgesteld worden dat, gegeven het onderzoeksopzet, relevant genoeg was. Het model dat uiteindelijk gebruikt werd, is gebaseerd op een bestaand model. Dit model werd gekozen omdat het een combinatie van veel voorkomende doelstellingen en beperkingen in de literatuur bevat. Voorts zijn in het basismodel preferenties aanwezig, zodat het eigenlijk een combinatie van een cyclische component en preferenties bevat. Met dit in het achterhoofd werden aan het basismodel nog een aantal extra preferenties toegevoegd. De verschillende omstandigheden, waaraan het resulterende model is onderworpen, werden gegenereerd met behulp van drie parameters, namelijk de “Total-coverage constrainedness” (TCC), de “day-coverage distribution” (DCD) en de “shift-coverage distribution” (SCD). Deze parameters geven een uitdrukking van de verdeling van de totale personeelsvereisten over de verschillende dagen en shifts. Bovendien zullen verschillende waarden voor TCC leiden tot een verschil in het aantal werknemers. In totaal werden 75 probleeminstanties gegenereerd via drie verschillende waarden voor TCC en vijf verschillende waarden voor zowel DCD als SCD. Om al deze instanties te kunnen oplossen is een “branch and price” algoritme, met behulp van Gurobi, geprogrammeerd waarna uit de resultaten is gebleken dat een cyclisch schema het best toepasbaar is voor lage TCC-, DCD- en SCD-waarden. De reden hiervoor is dat bij lage DCD –en SCDwaarden de personeelsvereisten, tussen de verschillende waarden voor TCC, niet heel veel verschillen. Bovendien is er bij lagere TCC-waarden een groter aantal werknemers beschikbaar om dezelfde personeelsvereisten in te vullen dan het geval is bij hogere TCC-waarden. Uitzonderingen op de toepasbaarheid van een cyclisch schema zijn te vinden wanneer DCD groter en SCD gelijk aan 1 wordt. Het blijkt dat voor de drie verschillende waarden van TCC vanaf DCD=0,75 een minder cyclisch schema sowieso interessant is, ongeacht de bijhorende SCD-waarde. Het is echter niet mogelijk gebleken om op basis van dit onderzoek een eenduidige conclusie te geven over de meest gepaste graad van cycliciteit onder deze verschillende acyclische omstandigheden. Om af te sluiten werd nog een kort onderzoek gevoerd naar mogelijkheden om de totale onproductiviteit te laten dalen. Hieruit bleek dat het niet mogelijk is om dit te bereiken door een beperking te stellen op het teveel of het tekort aan werknemers. Dit kan wel bereikt worden door de beperkingen op weekendwerk en de beperkingen op het totaal aantal shifts, die een werknemer moet werken, weg te laten. Zonder deze twee beperkingen werd een afname in de totale onproductiviteit waargenomen. 66

Alhoewel geprobeerd is om dit onderzoek zo algemeen mogelijk te maken, is het mogelijk dat deze conclusies niet in alle situaties geldig zijn (bijvoorbeeld andere waarden voor de totale personeelsvereisten). Bovendien is er geen eenzijdig besluit over de graad van cycliciteit, die het best past, bij de meer acyclische personeelsvereisten. Een mogelijkheid voor toekomstig onderzoek ligt in het bevestigen van deze basisconclusies, bij andere waarden voor de verschillende parameters en de totale personeelsvereisten, en het verder uitwerken van de toepasbaarheid van de verschillende graden van cycliciteit.

67

8. Referenties Aickelin, U. & White, P (2004). Building better nurse scheduling algorithms. Annals of operations research 128, 159-177. Alfares, H. K. (2004). Survey, categorization, and comparison of recent tour scheduling literature. Annals of operations research 127, 145-175. Bard, J. F. & Purnomo, H. W. (2005a). A column generation-based approach to solve the preference scheduling problem for nurses with downgrading. Socio-Economic Planning Sciences, Vol. 39, Issue 3, 193-213. Bard, J. F. & Purnomo, H. W. (2005b). Preference scheduling for nurses using column generation. European Journal of Operational Research 164, 510-534. Bard, J. F. & Purnomo, H. W. (2006). Cyclic Preference Scheduling for Nurses using Branch and Price. Wiley InterScience Vol. 54, No. 2, 200-220. Bard, J. F. & Purnomo, H. W. (2007). Cyclic preference scheduling of nurses using a Lagrangian-based heuristic. J Sched 10, 5-23. Billionnet, A. (1999). Integer programming to schedule a hierarchical workforce with variable demands. European journal of operational research, Vol. 114, Issue 1, 105-114. Brusco, J. M. & Jacobs, L. W. (1993). A simulated annealing approach to the solution of flexible labour scheduling problems. The Journal of the Operational Research Society, Vol. 44, No. 12, 1191-1200. Brusco, J. M. & Johns, T. R. (1996). A sequential integer programming method for discontinuous labor tour scheduling. European Journal of Operational Research, Vol. 95, Issue 3, 537-548. Burke, E. K., De Causmaecker, P., Vanden Berghe, G. & Van Landeghem, H. (2004). The state of the art of nurse rostering. Journal of scheduling 7, 441-499. Cheang, B., Li, H., Lim, A. & Rodrigues, B. (2003). Nurse rostering problems-a bibliographic survey. European Journal of Operational Research, Vol. 151, 447-460. Dowsland, K. A. & Thompson, J. M. (2000). Solving a nurse scheduling problem with knapsacks, networks and tabu search. Journal of operational research society 51, 825-833.

I

Ernst, A. T., Jiang, H., Krishnamoorthy, M. & Sier, D. (2004). Staff scheduling and rostering: A review of applications, methods and models. European Journal of Operational Research 153, 3-27. Fisher, L. M. (1981). The lagrangian relaxation method for solving integer programming problems. Management Science, Vol. 27, No.1, 1-18. Gärtner, J., Musliu, N. & Slany, W. (2001). Rota: a research project on algorithms for workforce scheduling and shift design optimization. Journal AI Communications, Vol. 14, Issue 2, 83-92. Hoffman, K. L. & Padberg, M. (1993). Solving airline crew scheduling problems by branch and cut. Management Science, Vol. 39, No. 6, 657-682. Housos, E. & Valouxis, C. (2000). Hybrid optimization techniques for the workshift and rest assignment of nursing personnel. Artificial Intelligence in Medicine, Vol. 20, Issue 2, 155-175. Hung, R. (1999). A multiple shift workforce scheduling model under annualized hours. Naval Research Logistics, Vol. 46, Issue 6, 726-736. Levine, D. (1996). Application of a hybrid genetic algorithm to airline crew scheduling. Computers Ops Res., Vol. 23, No. 6, 547-558. Maenhout, B. & Vanhoucke, M. (2007). An electromagnetic meta-heuristic for the nurse scheduling problem. Journal of heuristics 13, 359-385. Maenhout, B. & Vanhoucke, M. (2010a). Days on and days off scheduling of pilots under a variable workload. Airline industry: strategies, operations and safety, Chapter 9, 1-21. Maenhout, B. & Vanhoucke, M. (2010b). Branching strategies in a branch-and-price approach for a multiple objective nurse scheduling problem. J Sched 13, 77-93. Maenhout, B. & Vanhoucke, M. (2011). Days on and days off pilot scheduling. Airline industry: strategies, operations and safety. Chapter 9, 1-21. Millar, H. H. & Kiragu, M. (1998). Cyclic and non-cyclic scheduling of 12h shift nurses by network programming. European Journal of Operational Research, Vol. 104, Issue 3, 582-592. Miller, H. E., Pierskalla, W. P. & Rath, G. J. (1976). Nurse scheduling using mathematical programming. Operations Research, Vol. 24, Issue 5, 857-870. Musliu, N. (2006). Heuristic methods for automatic rotating workforce scheduling. International Journal of Computational Intelligence Research, Vol. 2, No. 4, 309-326. II

Musliu, N., Schaerf, A. & Slany, W. (2004). Local search for shift design. European Journal of Operational Research, Vol. 153, Issue 1, 51-64. Osborne, J. W. & Overbay, A. (2004). The power of outliers (and why researchers should always check for them). Practical assessment, research and evaluation. Vanhoucke, M. & Maenhout, B. (2009). On the characterization and generation of nurse scheduling problem instances. European Journal of Operational Research, Vol. 196, Issue 2, 457-467. Warner, D. M. (1976). Scheduling nursing personnel according to nursing preferences: a mathematical programming approach. Operations Research, Vol. 24, No.5, 842-856.

III

Appendix A Het gemiddeld aantal werknemers vereist per shift op dag j:

Het gemiddeld aantal werknemers vereist per dag:

De formule voor TCC:

De formule voor DCD:

met

De formule voor SCD:

met

IV

Appendix B De personeelsvereisten voor TCC=0 – DCD=0 – SCD=0:

Ervaringsniveau 1

Ervaringsniveau 2

3 3 2 2 2 2 3 2

3 2 3 3 3 3 3 3

2 3 3 3 3 3 2 3

3 2 3 2 3 3 2 2

3 3 2 3 3 2 3 3

2 3 3 3 2 3 3 3

3 3 2 3 3 2 2 3

3 3 3 3 2 3 3 3

2 2 3 2 3 3 3 2

2 3 3 3 2 3 3 3

3 2 3 3 3 3 2 2

3 3 2 2 3 2 3 3

2 3 2 3 2 3 3 2

3 2 3 2 3 2 2 3

3 3 3 3 3 3 3 3

3 3 3 3 2 3 3 3

2 2 2 3 3 3 3 2

3 3 3 2 3 2 2 3

3 3 3 2 2 3 3 3

2 3 3 3 3 3 2 3

3 2 2 3 3 2 3 2

3 3 2 2 3 3 3 3

3 3 3 3 3 2 3 2

3 3 2 3 3 3 3 3

2 3 3 3 3 3 3 3

3 2 3 2 2 2 2 2

3 2 3 3 2 3 2 3

3 3 3 2 3 2 3 3

2 3 2 3 3 3 3 2

3 3 2 3 3 3 3 3

2 3 3 2 2 2 2 2

3 2 3 3 3 3 3 3

De personeelsvereisten voor TCC=0 – DCD=0 – SCD=0,25:

Ervaringsniveau 1

Ervaringsniveau 2

3 3 3 3 3 2 3 3

3 3 2 3 3 3 3 2

2 2 3 2 2 3 2 3

3 3 3 3 2 3 2 3

3 2 2 2 3 3 3 3

2 3 3 3 3 2 3 2

2 3 3 2 3 3 2 3

3 3 2 3 3 3 3 2

V

3 2 3 3 2 2 3 3

2 2 3 3 2 3 2 3

shift 1 shift 3 shift 2 shift 1 shift 3 shift 2 shift 1 shift 3 shift 2 shift 1 shift 3 shift 2 shift 1 shift 3 shift 2 shift 1 shift 3

3,5 3

2,5

2

1,5 Ervaringsniveau 1

Ervaringsniveau 2

1

0,5

0

VI

Appendix C

IP oplossing 4000000 3500000 3000000 2500000 2000000 1500000 1000000 500000 0

TCC=0,2 TCC=0,35 TCC=0,5

VII

IP oplossing 5000000 4500000 4000000 3500000 3000000 2500000 2000000 1500000 1000000 500000 0

TCC=0,2 TCC=0,35 TCC=0,5

Aantal Nodes 25 20 15 10

TCC=0,2

5

TCC=0,35

0

TCC=0,5

VIII

IP oplossing 4500000 4000000 3500000 3000000 2500000 2000000 1500000 1000000 500000 0

TCC=0,2 TCC=0,35 TCC=0,5

Aantal Nodes 80 70 60 50 40 30 20 10 0

TCC=0,2 TCC=0,35 TCC=0,5

IX

IP oplossing 5000000 4500000 4000000 3500000 3000000 2500000 2000000 1500000 1000000 500000 0

TCC=0,2 TCC=0,35 TCC=0,5

Aantal Nodes 50 45 40 35 30 25 20 15 10 5 0

TCC=0,2 TCC=0,35 TCC=0,5

X

Appendix D

IP oplossing 4500000 4000000 3500000 3000000 2500000 2000000 1500000 1000000 500000 0

TCC=0,2 TCC=0,35 TCC=0,5

XI

IP oplossing 4000000 3500000 3000000 2500000 2000000 1500000 1000000 500000 0

TCC=0,2 TCC=0,35 TCC=0,5

Aantal nodes 35 30 25 20 15 10 5 0

TCC=0,2 TCC=0,35 TCC=0,5

XII

IP oplossing 5000000 4500000 4000000 3500000 3000000 2500000 2000000 1500000 1000000 500000 0

TCC=0,2 TCC=0,35 TCC=0,5

Aantal nodes 80 70 60 50 40 30 20 10 0

TCC=0,2 TCC=0,35 TCC=0,5

XIII

IP oplossing 5000000 4500000 4000000 3500000 3000000 2500000 2000000 1500000 1000000 500000 0

TCC=0,2 TCC=0,35 TCC=0,5

Aantal nodes 14 12 10 8 6 4 2 0

TCC=0,2 TCC=0,35 TCC=0,5

XIV

Appendix E

DCD=0,75-SCD=1 0 0,2 0,4 0,6 0,8 1 DCD=0,5-SCD=0 0 0,2 0,4 0,6 0,8 1

TCC=0,2 TCC=0,35 TCC=0,5 4322916 2278000 1296545 2191561 1887109 1668024 2347761 2403359 1893800 4590672 2513702 1625094 4699256 2282805 2283053 4736594 2589572 2560292 TCC=0,2 TCC=0,35 TCC=0,5 3706833 473323 701106 829228 624287 527578 3733918 471700 665191 976464 1528925 853786 3751011 990086 1110575 3768326 1539451 976593

DCD=1-SCD=0,5 TCC=0,2 TCC=0,35 TCC=0,5 0 4555345 2108571 1104071 0,2 3000240 1810915 1126571 0,4 4513575 1848219 1510779 0,6 4531992 2328324 1344890 0,8 4618113 2452402 1632058 1 4721906 2664652 2059803

XV

Integere programmering voor cyclische personeelsplanning

Recommend Documents