UNIVERSITEIT GENT FACULTEIT ECONOMIE EN BEDRIJFSKUNDE
ACADEMIEJAAR 2009–2010
Het opstellen van examenroosters in universiteiten: een geautomatiseerde aanpak
Masterproef voorgedragen tot het bekomen van de graad van Master in de Toegepaste Economische Wetenschappen: Handelsingenieur door Heidi BEHIELS
onder leiding van Promotor: Prof. M. Vanhoucke Thesisbegeleider: Prof. B. Maenhout
1
Permission Ondergetekende verklaart dat de inhoud van deze masterproef mag geraadpleegd en/of gereproduceerd worden, mits bronvermelding. Heidi Behiels
2
Woord vooraf Graag wil ik hierbij de tijd nemen om een aantal mensen te bedanken, zonder wiens steun en begeleiding deze thesis niet tot stand was gekomen.
Eerst en vooral wil ik prof. Maenhout bedanken voor de begeleiding en ondersteuning gedurende deze twee jaar. Dankzij prof. Maenhout is mijn interesse voor dit onderwerp tot stand gekomen. Daarnaast kon ik bij hem steeds terecht voor de nodige uitleg en adviezen omtrent de gegeven probleemstelling.
Ook mevr. Lena De Cock en mevr. Sarah Barbosa Ferreira verdienen hier een speciale vermelding. Dankzij hun medewerking was het voor mij mogelijk om de examenplanning op respectievelijk de Faculteit Economie en Bedrijfskunde aan de Universiteit Gent en de Faculty Economics and Management aan Universidade Nova de Lisboa te onderzoeken. Bij deze wil ik hen bedanken voor hun tijd en de informatie die ze mij ter beschikking gesteld hebben.
Tot slot wil ik graag mijn familie en vrienden bedanken voor de onvoorwaardelijke steun en het vertrouwen dat ze in mijn kunnen gesteld hebben. Daarnaast verdienen ook mijn medeleidsters van VKSJ Sint Pieters een speciale bedanking. Zij wisten mij op tijd en stond de nodige ontspanning te brengen. Niet in het minst wil ik graag mijn ouders, zus en mijn vriend Robin bedanken voor hun tips, motivatie en interesse die ze toonden in mijn onderwerp.
Heidi Behiels Gent Mei 2010
INHOUDSOPGAVE
3
Inhoudsopgave Lijst van figuren
6
Lijst van tabellen
8
I
Inleiding en Probleemstelling
10
1 Inleiding
11
2 Probleemstelling
13
II
2.1
Probleemdefinitie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
2.2
Wiskundige representatie van het probleem . . . . . . . . . . . . . . . . . . . . .
15
2.3
Gelijkenis met het course timetabling probleem . . . . . . . . . . . . . . . . . . .
20
Literatuurstudie
3 Graph-based Sequenti¨ ele Technieken
23 24
3.1
Inleiding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
3.2
Voor- en nadelen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
3.3
Voorbeeld . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
4 Case-based Reasoning
32
4.1
Inleiding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
4.2
Voor- en nadelen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
4.3
Voorbeeld . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
5 Constraint Based Technieken 5.1
Inleiding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
39 39
INHOUDSOPGAVE
4
5.2
Voor- en nadelen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
5.3
Voorbeeld . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
6 Metaheuristieken 6.1
6.2
6.3
45
Lokale Zoekalgoritmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
45
6.1.1
Tabu Search
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
45
6.1.2
Simulated Annealing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
49
6.1.3
Voor- en nadelen van de lokale zoekalgoritmes . . . . . . . . . . . . . . . .
55
6.1.4
Het bepalen van de omgeving . . . . . . . . . . . . . . . . . . . . . . . . .
55
6.1.5
Tijdsaspect . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
56
Evolutionaire Algoritmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
57
6.2.1
Genetische Algoritmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
57
6.2.2
Ant Colony Algoritmes . . . . . . . . . . . . . . . . . . . . . . . . . . . .
63
Vergelijking van de verschillende metaheuristieken . . . . . . . . . . . . . . . . .
68
7 Memetische Algoritmes
69
7.1
Inleiding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
69
7.2
Voor- en nadelen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
71
7.3
Voorbeeld . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
72
8 Multi-objectieve (Evolutionaire) Algoritmes
75
8.1
Inleiding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
75
8.2
Prestatie van MOEA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
77
8.3
Voorbeeld . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
78
9 Hyperheuristieken
81
9.1
Inleiding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
81
9.2
Voor- en nadelen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
83
9.3
Voorbeeld . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
83
10 Decompositietechnieken en clustering
85
10.1 Inleiding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
85
10.2 Voor- en nadelen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
86
10.3 Voorbeeld . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
87
INHOUDSOPGAVE
III
Examen Scheduling in de praktijk
11 Examen Scheduling in de praktijk 11.1 Inleiding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
89 90 90
11.2 Examenplanning aan de Faculteit Economie en Bedrijfskunde (Universiteit GENT, Belgi¨e) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
91
11.3 Examenplanning aan de Faculty Economics and Management (Universidade Nova de Lisboa, Portugal) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
94
11.4 Implementatie in C++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
95
11.5 Besluit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 A Classificatietabel
107
B Vaste Examenroosters (FEB, Universiteit Gent)
115
C Praktijkvoorbeeld Gent: Aantal inschrijvingen per richting
119
D Implementatie: code C++
121
Bibliografie
122
LIJST VAN FIGUREN
6
Lijst van figuren 3.1
Grafische representatie van het probleem . . . . . . . . . . . . . . . . . . . . . . .
28
3.2
Grafische representatie na toewijzing van examen Project Mgmt . . . . . . . . .
30
3.3
Grafische representatie: Mogelijk examenrooster . . . . . . . . . . . . . . . . . .
31
4.1
Toekenning van attributen aan knooppunten en verbindingslijnen van het oude probleem
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
4.2
CBR Beslissingsboom . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38
4.3
Attribute graph van het nieuwe probleem . . . . . . . . . . . . . . . . . . . . . .
38
6.1
F low Chart voor het Genetisch Algoritme . . . . . . . . . . . . . . . . . . . . . .
60
6.2
Matrix P1 en P2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
61
6.3
Matrix O1 en O2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
62
6.4
Matrix O1 en O2 na toepassing van crossover . . . . . . . . . . . . . . . . . . . .
62
6.5
O1 na toepassing van mutatie operator . . . . . . . . . . . . . . . . . . . . . . . .
63
6.6
Construction Grafiek gebaseerd op ([55]) . . . . . . . . . . . . . . . . . . . . . .
66
7.1
F low Chart voor de memetische Algoritmes . . . . . . . . . . . . . . . . . . . . .
70
7.2
Memetische Algoritmes [25] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
71
7.3
Matrix P1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
72
7.4
Matrix P2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
74
9.1
F low Chart: Werking van de hyperheuristieken . . . . . . . . . . . . . . . . . . .
84
10.1 Matrix X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
87
11.1 F low Chart: Implementatie Construction Heuristiek . . . . . . . . . . . . . . .
97
11.2 Vergelijking doelfunctiewaarden bij toepassing van construction heuristiek . . . .
99
LIJST VAN FIGUREN
7
11.3 Vergelijking doelfunctiewaarden bij toepassing van M ove operator . . . . . . . . 102 11.4 Vergelijking doelfunctiewaarden na toepassing Swap operator . . . . . . . . . . . 103 11.5 Vergelijking doelfunctiewaarden na toepassen combinatie M ove en Swap operatoren103 11.6 Fictief Voorbeeld: Verband tussen CPU-tijd en doelfunctiewaarde . . . . . . . . . 105 11.7 Case Lissabon: Verband tussen CPU-tijd en doelfunctiewaarde . . . . . . . . . . 105 11.8 Case Gent: Verband tussen CPU-tijd en doelfunctiewaarde . . . . . . . . . . . . 106 B.1 Examenrooster: 1e Bach, 2e Semester . . . . . . . . . . . . . . . . . . . . . . . . 116 B.2 2e Bach Economische Wetenschappen: 2e Semester . . . . . . . . . . . . . . . . . 116 B.3 2e Bach Toegepaste Economische Wetenschappen: 2e Semester . . . . . . . . . . 117 B.4 3e Bach EW: 2e Semester . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 B.5 3e Bach TEW: 2e Semester . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 B.6 3e Bach HIR: 2e Semester . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 C.1 Gent: Aantal Inschrijvingen per richting . . . . . . . . . . . . . . . . . . . . . . . 120
LIJST VAN TABELLEN
8
Lijst van tabellen 2.1
Overzicht van soft constraints (Burke et al., 2006) . . . . . . . . . . . . . . . . .
15
2.2
Overzicht van van de gebruikte notaties . . . . . . . . . . . . . . . . . . . . . . .
16
2.3
Set van te plannen examens(I) . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
2.4
Resulterend examenrooster m.b.v. de Constraint Based technieken . . . . . . . .
19
2.5
Berekening van de doelfunctie a.d.h.v. een logaritmische schaal . . . . . . . . . .
21
3.1
Gegevens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
3.2
Aantal Conflicten met andere examens . . . . . . . . . . . . . . . . . . . . . . . .
29
3.3
Aantal Conflicten na allocatie van Project Management . . . . . . . . . . . . . .
31
3.4
Resulterend examenrooster na toepassing van largest degree strategie . . . . . . .
31
4.1
Mogelijke kenmerken van het examen scheduling probleem . . . . . . . . . . . . .
33
4.2
Attributen behorende tot de knooppunten van het Examen Scheduling Probleem
35
4.3
Attributen behorende tot de verbindingslijnen van het Examen Scheduling Probleem 36
4.4
Mogelijke oplossingen gegenereerd via case-based reasoning
. . . . . . . . . . . .
38
5.1
Set van variabelen en hun domeinen voor de Constraint Based technieken . . . .
41
5.2
Resulterend examenrooster m.b.v. de Constraint Based technieken . . . . . . . .
44
6.1
Initieel examenrooster . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47
6.2
Berekening van de doelfunctie a.d.h.v. een logaritmische schaal . . . . . . . . . .
48
6.3
Examenrooster S2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
48
6.4
Berekening van de doelfunctie voor S2 a.d.h.v. een logaritmische schaal . . . . .
49
6.5
Examenrooster S3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
50
6.6
Berekening van de doelfunctie voor S3 a.d.h.v. een logaritmische schaal . . . . .
51
6.7
Initieel examenrooster X1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
LIJST VAN TABELLEN
9
6.8
Examenrooster X2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53
6.9
Examenrooster X3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53
6.10 Berekening van de doelfunctie voor X3 a.d.h.v. een logaritmische schaal . . . . .
54
6.11 Toekennen van een numerieke waarde aan de te plannen examens . . . . . . . . .
61
6.12 Crossover map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
63
6.13 Relevante waarden voor de parameters in het MMAS algoritme (Socha et al.,2003) 68 7.1
Examenrooster P1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
72
7.2
Berekening van de doelfunctie voor P1 a.d.h.v. een logaritmische schaal . . . . .
73
7.3
Examenrooster P2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
74
8.1
Gebruikte notaties voor het MOEA . . . . . . . . . . . . . . . . . . . . . . . . . .
79
11.1 Data voor elke probleemstelling . . . . . . . . . . . . . . . . . . . . . . . . . . . .
96
11.2 Logaritmische schaal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
98
11.3 Bekomen doelfunctiewaarden volgens verschillende ordering strategie¨en na toepassing van de construction heuristiek . . . . . . . . . . . . . . . . . . . . . . . .
99
11.4 Fictief Voorbeeld: Bekomen doelfunctiewaarden . . . . . . . . . . . . . . . . . . . 101 11.5 Case Lissabon: Bekomen doelfunctiewaarden . . . . . . . . . . . . . . . . . . . . 101 11.6 Case Gent: Bekomen doelfunctiewaarden
. . . . . . . . . . . . . . . . . . . . . . 102
11.7 Fictief Voorbeeld: CPU-tijden(in sec) . . . . . . . . . . . . . . . . . . . . . . . . 104 11.8 Case Lissabon: CPU-tijden(in sec) . . . . . . . . . . . . . . . . . . . . . . . . . . 104 11.9 Case Gent: CPU-tijden(in sec) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
10
Deel I
Inleiding en Probleemstelling
INLEIDING
11
Hoofdstuk 1
Inleiding Het onderwerp van deze thesis, het opstellen van examenroosters in universiteiten, betreft een combinatorisch optimalisatieprobleem waaraan onderzoekers sinds de jaren ’60 van vorige eeuw reeds veel tijd en aandacht geschonken hebben. Dat dit onderzoeksdomein ook vandaag nog grondig bestudeerd en onderzocht wordt, wordt bewezen door een steeds toenemende interesse die vastgesteld wordt bij onderzoekers. Een stijgend aantal studenten, een uitgebreider assortiment van de te volgen vakken aangeboden door universiteiten en een groter aantal beperkingen liggen aan de basis van de toenemende complexiteit van het probleem en verklaren voor een groot deel de vernieuwde interesse in dit domein. Bovenstaande gesuggereerde problemen verhogen niet enkel de complexiteit maar doen ook de vraag naar een meer automatische aanpak van dit probleem rijzen. Gedurende het opstellen van deze thesis is namelijk gebleken dat, hoewel reeds vrij veel oplossingsmethodes voor handen zijn in de literatuur, in de praktijk bijna geen gebruik gemaakt wordt van een automatische benadering tot het probleem. Dit is vooral te wijten aan het probleemspecifieke karakter (i.e. afhankelijk van universiteit tot universiteit) van het examen scheduling probleem en de afwezigheid van een algemene oplossingsmethode. Een automatische oplossingsmethode biedt als grote voordeel dat een dergelijk combinatorisch probleem op eenvoudige wijze opgelost wordt door het genereren van een zo optimaal mogelijk examenrooster waarbij rekening gehouden wordt met de verschillende beperkingen die opgelegd werden. T imetabling problemen komen niet alleen voor in een onderwijsgerelateerde context. Ook in andere domeinen zoals de ziekenhuissector en andere public services (bv. openbaar vervoer: bus, trein, ...) is het opstellen van tijdroosters noodzakelijk. Ook in deze sectoren betreft het
INLEIDING
12
opstellen van een effici¨ente dienstregeling een veel besproken combinatorisch probleem. Dit valt evenwel buiten het bereik van deze thesis. Het verloop van deze masterproef is als volgt. Het eerste deel geeft een uitgebreide definitie van het probleem. Daarin wordt het probleem onder meer op een wiskundige manier gemodelleerd. Tenslotte wordt er in het eerste deel een vergelijking gemaakt met het course timetabling probleem dat een analoog probleem beschrijft. In een tweede deel van deze thesis worden de verschillende algoritmes en heuristieken met betrekking tot het opstellen van examenroosters die voor handen zijn in de literatuur, in detail besproken. Er wordt zoveel mogelijk getracht de volgorde te hanteren als deze in [23] om een zo gestructureerd mogelijk overzicht te verschaffen van de beschikbare algoritmes. Het overzicht van [23] vormt een uitbreiding op eerder onderzoek van [30]. Appendix 1 verschaft een classificatietabel waarin alle onderzochte papers gestructureerd worden aan de hand van de gebruikte algoritmes. Dit levert anderen de mogelijkheid om bij verder onderzoek gemakkelijker de literatuur te raadplegen met betrekking tot de beschikbare algoritmes voor het examen scheduling probleem. Aan de hand van een eenvoudig voorbeeld wordt de werking van elk algoritme, beschreven in de literatuurstudie, ge¨ıllustreerd. Verder komen ook de voor- en nadelen van elk algoritme aan bod. In een derde deel wordt het plannen van examenroosters in de praktijk bestudeerd. Zowel voor de Faculteit Economie en Bedrijfskunde aan de Universiteit Gent, als voor dezelfde faculteit aan de Universiteit van Lissabon (Universidade Nova de Lisboa) wordt nagegaan hoe het opstellen van examenroosters daar verloopt. Zoals reeds eerder vermeld en zoals ook uit verder onderzoek zal blijken, wordt het opstellen van examenroosters in universiteiten nog te weinig geautomatiseerd. Dit deel suggereert dan ook een eerste aanpak tot de automatisering van dit tijdrovend proces.
PROBLEEMSTELLING
13
Hoofdstuk 2
Probleemstelling 2.1
Probleemdefinitie
In haar zuiverste vorm is het examen scheduling probleem een allocatieprobleem. Door het toewijzen van een aantal events, in dit geval een set examens, aan een set examenperiodes of -sessies wordt getracht tot een optimale oplossing te komen van een NP-hard (non-deterministic polynomial hard ) probleem, waarbij voldaan is aan een reeks van restricties. Een NP-hard probleem is een zeer complex probleem waarbij het niet mogelijk is om door middel van een exhaustieve zoekactie een oplossing te zoeken voor het probleem binnen een aanvaardbare tijdsperiode [62]. Bij het zoeken naar een oplossing voor dergelijke problemen moet men rekening houden met de eisen en wensen van de stakeholders en met een aantal restricties of constraints. Studenten, professoren en de facultaire administratie kunnen beschouwd worden als de voornaamste stakeholders in het examen scheduling probleem. De voornaamste eis van de studenten is een examenrooster te bekomen waarbij een billijke spreiding tussen de af te leggen examens voorzien is. Ook professoren eisen een examenrooster dat zodanig georganiseerd is dat er voldoende tijd is om examens te verbeteren. De facultaire administratie is veelal belast met het opstellen van examenroosters. Zij streven naar een examenrooster waarbij ieders eisen en wensen zo veel mogelijk ingewilligd zijn. De beperkingen, waaraan examenroosters onderworpen zijn en waarmee rekening gehouden moet worden, kunnen onderverdeeld worden in twee groepen. Als eerste groep onderscheidt men de hard constraints. Deze restricties bepalen de feasibilty of haalbaarheid van het bekomen examenrooster. De hard constraints zijn noodzakelijk en moeten voldaan zijn opdat het bekomen examenrooster als feasible of mogelijk kan beschouwd worden.
2.1 Probleemdefinitie
14
Hoewel deze restricties vari¨eren voor verschillende universiteiten, zijn volgende hard constraints de meest voorkomende: • Een student kan slechts 1 examen per examensessie afleggen. • Het aantal studenten, ingeschreven voor een examen, moet kleiner zijn dan de maximum capaciteit van het examenlokaal. • Elk examen moet toegewezen worden aan exact ´e´en examenperiode. Bovenstaande verzameling van hard constraints is gebaseerd op bevindingen in [23]. Een tweede groep restricties betreft de soft constraints. De soft constraints zijn gewenste restricties en moeten bijgevolg niet noodzakelijk vervuld worden om tot een mogelijke oplossing te komen. Ze bepalen daarentegen wel de kwaliteit van het bekomen examenrooster en een schending van ´e´en of meerdere soft constraints wordt bestraft in de doelfunctie die geminimaliseerd dient te worden. De co¨effici¨enten van de doelfunctie geven een indicatie van de zwaarte van de overtreding. Ook wat betreft de soft constraints kan opgemerkt worden dat deze sterk verschillen over verschillende universiteiten. Zo wordt een schending van een zelfde soft constraint, gehanteerd door twee verschillende universiteiten, bijvoorbeeld niet even zwaar bestraft in de doelfunctie van de desbetreffende universiteiten. Verschillende wegingsco¨effici¨enten worden met andere woorden toegekend. Ondanks het universiteitsafhankelijke karakter van deze beperkingen, kan ook hier een selectie gemaakt worden van de meest voorkomende soft constraints: • De spreiding tussen twee opeenvolgende examens moet voldoende groot zijn. Men tracht met andere woorden te verhinderen dat een student meerdere examens moet afleggen in opeenvolgende periodes. Deze sof t constraints worden ook wel tweede orde restricties genoemd en zijn het meest gekend. Deze restrictie wordt wiskundig gemodelleerd in 2.2. • Belangrijke en/of grote examens moeten toegewezen worden aan een examenperiode in het begin van het examenrooster om de student meer revisie tijd te verschaffen. • Bepaalde examens moeten in een vooraf bepaalde examenperiode plaats vinden. Voor de soft constraints wordt een uitgebreider overzicht verschaft (tabel 2.1). Opnieuw is dit gebaseerd op [23]. Hoewel dit overzicht als vrij volledig kan beschouwd worden is dit niet exhaustief.
2.2 Wiskundige representatie van het probleem
15
Tabel 2.1: Overzicht van soft constraints (Burke et al., 2006) Soft Constraints De examens moeten billijk gespreid zijn over de examenperiode Bepaalde examens moeten in opeenvolgende periodes gepland worden Bepaalde examens moeten toegewezen worden aan bepaalde periodes Plan de grootste of belangrijkste examens zo vroeg mogelijk in het examenrooster Bepaalde examens mogen niet toegewezen worden aan bepaalde periodes Examens kunnen opgesplitst worden over verschillende lokalen Verschillende examens met dezelfde lengte kunnen aan een zelfde lokaal toegewezen worden Bepaalde examens moeten gepland worden volgens een bepaalde volgorde Examens moeten in een bepaald lokaal plaatsvinden omwille van benodigde faciliteiten
Met betrekking tot de hard constraints kan gesteld worden dat hoewel de eerste en tweede hard constraints, bijna altijd hard zijn, dit niet het geval is voor de derde hard constraint. De literatuur verschaft immers ook een reeks voorbeelden waar de derde constraint niet voldaan is en waarbij toch een f easible examenrooster bekomen wordt. De restrictie wordt met andere woorden als soft beschouwd. Dit is meestal het geval wanneer een examen over verschillende blokken verspreid wordt, bijvoorbeeld in het geval van een mondeling examen. Naar het voorbeeld van [46] wordt het beschouwde combinatorisch probleem opgesplitst. Enerzijds bestaat het probleem uit het plannen van de examens. Anderzijds omvat het probleem de planning van andere resources, zoals uit het overzicht van de restricties opgemaakt kan worden. Zo moet er bij het plannen van examens rekening gehouden worden met de capaciteit van de examenlokalen, het aantal beschikbare examenlokalen, de benodigde faciliteiten (bijvoorbeeld video,pc’s,...) en de toekenning en de beschikbaarheid van toezichters. Hoewel deze andere resources en de allocatie ervan niet genegeerd mogen worden, vormt dit niet het hoofddoel van deze thesis en zal dit dan ook niet in detail besproken worden. Het hoofddoel van deze thesis bestaat er enkel in inzicht te verschaffen in het plannen van de examens.
2.2
Wiskundige representatie van het probleem
Naar het voorbeeld van [66],[46],[35],[1] en anderen, wordt het examen scheduling probleem wiskundig gemodelleerd. De volgende notaties worden gebruikt.
2.2 Wiskundige representatie van het probleem
16
Tabel 2.2: Overzicht van de gebruikte notaties Notatie
Beschrijving
I
Set van examens
T
Set van examenperiodes
cij
Het aantal studenten ingeschreven in zowel examen i als in examen j
N
Het aantal studenten
Ei
Het aantal studenten ingeschreven in examen i
Pω
Kost wanneer een student twee examens moet afleggen in ω + 1 periodes
yit
1 wanneer examen i wordt toegewezen aan periode t, 0 in alle andere gevallen
Ω
Set die de orde weergeeft van de vastgestelde conflicten
Door gebruik te maken van bovenstaande afkortingen wordt het examen scheduling probleem als volgt wiskundig geformuleerd:
min
X
X
X
Pω cij yit yj(t−ω) (2.1)
ω∈ Ω i,j∈ I,i6=j t∈T,t>ω
Subject to:
X
yit = 1, ∀i ∈ I
(2.2)
t∈T
X
cij yit yjt = 0
(2.3)
t∈T
yit ∈ {0, 1}, ∀i, j ∈ I, i 6= j
X
X
(2.4)
pirt ≤ krt
(2.5)
yks = 1, ∀k ∈ I
(2.6)
s∈T
X q∈T
ylq 6= 1, ∀l ∈ I
(2.7)
2.2 Wiskundige representatie van het probleem
17
Vergelijking 2.1 stelt de te minimaliseren doelfunctie voor. Hierbij wordt getracht de som van alle conflicten te minimaliseren. Het niet nakomen van de soft constraints wordt weergegeven in de doelfunctie. Er moet evenwel opgemerkt worden dat de beschreven doelfunctie enkel de eerste soft constraint behandelt. Andere sof t constraints kunnen evenwel gemakkelijk ge¨ıncorporeerd worden in de doelfunctie door het niet naleven van deze restricties te bestraffen met een bepaalde kost in de doelfunctie. Onder meer [31] en [62], maar ook vele anderen, stellen dat de kost (m.b.t. de spreiding) logaritmisch daalt wanneer het aantal periodes tussen twee opeenvolgende examens stijgt. Voor ω(1), i.e. studenten moeten examens afleggen in twee opeenvolgende periodes, is er een kost voorzien van 16. De logaritmische schaal in gedachten houdend, resulteert dit in: ω(2) = 8, ω(3) = 4, ω(4) = 2 en ω(5) = 1. Hierbij impliceert ω(2) = 8 dat ´e´en vrije periode tussen twee geplande examens resulteert in een kost van 8 enzovoort. Vergelijking 2.2 impliceert dat elk examen i toegewezen moet worden aan exact ´e´en periode. Dit komt overeen met de derde hard constraint. In de derde vergelijking, vergelijking 2.3, wordt de hard constraint weergegeven die zegt dat examens die studenten gemeenschappelijk hebben, niet gepland mogen worden in een zelfde periode. Vergelijking 2.4 geeft het binaire karakter weer van variabele yit , die 1 is wanneer examen i aan periode t wordt toegewezen en 0 in het andere geval. Vergelijking 2.5 is een voorbeeld van een resource constraint. Vergelijking 2.5 vertegenwoordigt immers de hard constraint waarbij rekening gehouden moet worden met capaciteit van de beschikbare examenruimtes. Deze vergelijking stelt dat het aantal studenten van examen i, toegewezen aan lokaal r in periode t, kleiner moet zijn dan de capaciteit van lokaal r in periode t. Deze resource constraint stelt een tweede luik voor van het examen scheduling probleem maar zal, zoals reeds vermeld in paragraaf 2.2, niet onderworpen worden aan een nauwkeuriger onderzoek. Vergelijking 2.6 vormt dan weer een representatie van de soft constraint, waarbij examen k toegewezen moet worden aan een vooraf bepaalde periode, in dit geval periode s. Deze periode s behoort tot het domein van de examensessies. Vergelijking 2.7 stelt het tegenovergestelde van vergelijking 2.6. Deze vergelijking stelt dat een bepaald examen l niet mag toegewezen worden aan een bepaalde periode q. Met de bedoeling al het bovenstaande te verduidelijken, wordt gebruik gemaakt van een voorbeeld.
2.2 Wiskundige representatie van het probleem
18
Veronderstel een examen scheduling probleem waarbij getracht wordt negen examens te plannen in een examenperiode van zeven dagen. Tabel 2.3 geeft een overzicht van I, i.e. de set van de te plannen examens. Tabel 2.3: Set van te plannen examens(I) Nr.
Beschrijving
1
Examen Supply Chain Management (SCM)
2
Examen ICT (ICT)
3
Examen Project Management (Project)
4
Examen Financiering van Groeigerichte Ondernemingen (FGO)
5
Examen Software Engineering (SW Eng)
6
Examen Marketing van nieuwe Technologie¨en (Mktg nt)
7
Examen Applied Operations Research (AOR)
8
Examen Transport Economie (Trans Eco)
9
Examen Innovation Management (Inn Mgmt)
De beschreven examens moeten gepland worden in een periode van maximum 6 dagen (maandag tot zaterdag). Elke dag bevat drie examensessies, behalve zaterdag waar slechts ´e´en examensessie kan plaats vinden. Aan elke examensessie wordt een natuurlijk getal toegekend dat de examensessies op een onbetwistbare manier van elkaar onderscheidt. Zodoende bestaat de examenperiode uit een set van natuurlijke getallen gaande van 1 tot 16. Onderstaande matrix X (zie ook hoofdstuk 3 en hoofdstuk 5), opgesteld op basis van tabel 3.1, toont de ingeschreven studenten per examen en de mogelijke conflicten die kunnen ontstaan tussen de beschreven examens. De diagonaal in de matrix geeft aan hoeveel studenten ingeschreven zijn voor elk examen.
2.2 Wiskundige representatie van het probleem
2 2 1 1 X= 0 0 0 0 0
19
2 1 1 0 0 0 0 2 1 1 0 0 0 0 1 3 1 2 1 1 1 1 1 1 0 0 0 0 0 2 0 2 1 1 1 0 1 0 1 1 1 1 0 1 0 1 1 1 1 0 1 0 1 1 1 1 0 1 0 1 0 0 0
0 0 1 0 1 0 0 0 1
(2.8)
Een mogelijk examenrooster voor dit probleem wordt voorgesteld in tabel 2.4 (zie ook tabel 5.3). Tabel 2.4: Resulterend examenrooster m.b.v. de Constraint Based technieken Ma
Di
Woe
Do
Vrij
Za
Project
SCM/SW Eng
ICT
FGO
-
-
-
-
Mktg nt
AOR
TRANS Eco/Inn Mgmt
-
-
-
-
-
-
-
Aan de hand van tabel 2.4 wordt getracht de geformuleerde probleemstelling te verduidelijken met een praktisch voorbeeld. Het bekomen rooster zal ge¨evalueerd worden op basis van de beschreven doelfunctie en constraints. Het is hierbij belangrijk op te merken dat tabel 2.4 als gegeven beschouwd wordt, onafhankelijk van de wijze waarop dit examenrooster gegenereerd werd. Uit matrix X en tabel 2.4 kan men besluiten dat vergelijking 2.3 voldaan is. De examens die in dezelfde examensessie gepland werden, hebben geen studenten gemeenschappelijk. Het bekomen examenrooster resulteert met andere woorden niet in een conflict. Zo geldt voor de examens SCM en SW Eng: c15 = 0. De lezer kan dit ook nagaan voor de examens Trans Eco en Inn Mgmt. Ook vergelijking 2.2 is voldaan. Elk examens is immers ondubbelzinning toegewezen aan ´e´en periode. Zoals reeds eerder aangehaald werd, vormt het plannen van de examenlokalen niet het hoofddoel van deze thesis. Vergelijking 2.5 wordt in dit opzicht dan ook als irrelevant beschouwd.
2.3 Gelijkenis met het course timetabling probleem
20
Vergelijkingen 2.6 en 2.7 worden dan weer wel als relevant beschouwd. Deze twee case-specifieke vergelijkingen zijn in dit voorbeeld voldaan, wanneer de facultaire administratie het examen Trans Eco bij voorkeur in periode elf (i.e. de tweede examenperiode op donderdag) (vergelijking 2.6) of wanneer het examen Project niet in de tweede examensessie (i.e. de tweede examensessie op maandag) mag gepland worden. Het niet vervullen van deze vereisten, leidt niet tot een inf easible examenrooster (cfr. sof t constraints) maar zou mogelijks bestraft kunnen worden met een kost van 10. Deze kost werd louter ter illustratie gekozen en verschilt uiteraard over verschillende universiteiten. Afhankelijk van de belangrijkheid die de beschouwde universiteit hecht aan het nakomen van deze restrictie, kan deze kost hoger of lager zijn. Veronderstel verder in dit voorbeeld dat de universiteit werkt met een logaritmische schaal, naar het voorbeeld van [31] en [62], maar ook vele anderen. Tabel 2.5 geeft weer hoe de doelfunctie (vergelijking 2.1) wordt berekend. Hierbij wordt rekening gehouden met hoeveel vrije periodes er zijn tussen twee examens en hoeveel studenten ingeschreven zijn voor beide examens. Wanneer alle waarden uit de rechterkolom van tabel 2.5 opgeteld worden, geeft dit een totale kost van 34. Deze waarde kan vergeleken worden met de totale kost van andere opgestelde examenroosters. Hoe lager de beschouwde kost, des te beter de kwaliteit van het bekomen examenrooster. In dit voorbeeld bepaalt een voldoende spreiding van de examens over de beschouwde examenperiode hoofdzakelijk de kwaliteit van het examenrooster.
2.3
Gelijkenis met het course timetabling probleem
Aanaloog aan het examen scheduling probleem is het course timetabling probleem. Het betreft eveneens een NP-hard combinatorisch probleem waarbij een set of events, in dit geval lessen van bepaalde vakken, toegewezen worden aan bepaalde periodes. Door het gelijkaardig karakter van beide scheduling problemen is het vrij moeilijk om een duidelijk onderscheid te maken tussen beide en vaak kunnen praktische problemen zowel voorgesteld worden als een examen scheduling probleem, als zowel een course timetabling probleem. Desondanks kunnen er toch verschillen tussen beide problemen vastgesteld worden [66]. 1. Voor elk onderwerp is er ´e´en examen terwijl er vaak meerdere lessen zijn per week voor een bepaald onderwerp.
2.3 Gelijkenis met het course timetabling probleem
21
Tabel 2.5: Berekening van de doelfunctie a.d.h.v. een logaritmische schaal Examens
cij
Logaritmische Schaal
# ingeschreven studenten
Kost
Project & SCM
c31
ω(3) = 4
1
4
Project & SW Eng
c35
ω(3) = 4
2
8
SCM & ICT
c12
ω(3) = 4
2
8
SCM & Mktg nt
c16
ω(4) = 2
0
0
SW Eng & ICT
c52
ω(3) = 4
0
0
SW Eng & Mktg nt
c56
ω(4) = 2
1
2
ICT & Mktg nt
c26
ω(1) = 16
0
0
ICT & FGO
c24
ω(3) = 4
1
4
ICT & AOR
c27
ω(4) = 2
0
0
Mktg nt & FGO
c64
ω(2) = 8
0
0
Mktg nt & AOR
c67
ω(3) = 4
1
4
FGO & AOR
c47
ω(1) = 16
0
0
FGO & Trans Eco
c48
ω(4) = 2
0
0
FGO & Inn Mgmt
c49
ω(4) = 2
0
0
AOR & Trans Eco
c78
ω(3) = 4
1
4
AOR & Inn Mgmt
c79
ω(3) = 4
0
0
2. In geval van een conflict, i.e. een student moet deelnemen aan beide examens, moeten de desbetreffende examens op een verschillend moment gepland worden. Dit is niet zo strikt voor het opstellen van lessenroosters. Hierbij wordt verondersteld dat een overlapping van twee vakken voor ´e´en of meerdere studenten mogelijk moet zijn. 3. Het aantal examenperiodes is variabel, dit in tegenstelling tot het aantal periodes in een lessenrooster, dat vast is. 4. Hoewel er meerdere examens kunnen plaatsvinden in een zelfde lokaal, geldt dit niet voor lessen. 5. In tegenstelling tot lessenroosters, waarbij getracht wordt zo weinig mogelijk springuren of idle periods in te plannen, wordt in examenroosters zo veel mogelijk vermeden dat een student meerdere examens moet afleggen in opeenvolgende examenperiodes.
2.3 Gelijkenis met het course timetabling probleem
22
Het opstellen van lessenroosters is net zoals het examen scheduling probleem reeds veel het onderwerp geweest van studies in het operationeel onderzoek. Hoewel ook dit een zeer interessant probleem betreft, valt het buiten het bereik van deze masterproef.
23
Deel II
Literatuurstudie
¨ TECHNIEKEN GRAPH-BASED SEQUENTIELE
24
Hoofdstuk 3
Graph-based Sequenti¨ ele Technieken 3.1
Inleiding
De eerste categorie beschrijft de graph-based sequenti¨ele technieken. Het examen scheduling probleem kan immers in haar eenvoudigste vorm herleid worden tot een graph coloring probleem. Deze technieken werden ontworpen in de jaren zestig van vorige eeuw en vormden een eerste benadering voor het oplossen van het examen scheduling probleem. [65] linkten als ´e´en van de eersten het opstellen van timetables aan het graph coloring probleem. Graph-based sequenti¨ele technieken blijken een bruikbaar instrument bij het opstellen van examenroosters omdat zij een analoog probleem beschrijven. De graph-based heuristiek beschrijft namelijk hoofdzakelijk de toekenning van kleuren aan knooppunten zodat twee aangrenzende knooppunten een verschillende kleur hebben, wat betekent dat een andere tijdsperiode wordt toegekend aan beide knooppunten. De hard constraints (cfr. DEEL I) worden voorgesteld door de verbindingslijnen tussen twee knooppunten. De knooppunten stellen hier de te plannen examens voor. Knooppunten die verbonden zijn door middel van een verbindingslijn indiceren het bestaan van een mogelijk conflict en wijzen er met andere woorden op dat minstens ´e´en student beide examens moet afleggen. Het hoofddoel van deze techniek bestaat erin de examens te plannen in een minimaal aantal periodes, met andere woorden men tracht een minimaal aantal kleuren te gebruiken. Dit minimum wordt ook wel het chromatische getal genoemd en wordt vaak aangeduid met de Griekse letter χ(Chi)[59]. Bij knooppunten met een zelfde kleur kan er geen conflict ontstaan, wat betekent dat beide examens op dezelfde dag kunnen gepland worden. Deze knooppunten zijn niet met elkaar ver-
3.1 Inleiding
25
bonden door een verbindingslijn. Een conflict kan gedefinieerd worden als volgt: een conflict ontstaat wanneer examens die minstens ´e´en student gemeenschappelijk hebben op hetzelfde moment gepland worden. Centraal in deze heuristiek staat de hard constraint die zegt dat examens die gepland worden in eenzelfde periode geen studenten gemeen mogen hebben. Deze heuristiek kan beschouwd worden als een constructieve methode waarbij examens geordend worden naargelang hun moeilijkheidsgraad. Vervolgens worden examens sequentieel, d.w.z. ´e´en per ´e´en, aan verschillende periodes toegekend. Deze toekenning gebeurt aan de hand van een welbepaalde ordering of sequencing strategy. De literatuur ([29],[30]) verschaft een grote mogelijkheid aan toe te passen sequenti¨ele strategie¨en. In wat volgt worden de largest degree strategie, de largest weighted degree strategie, de saturation degree strategie, de largest enrolment strategie en de random ordering strategie verder uitgediept, aangezien zij het meest courant voorkomen in de literatuur. Gemeenschappelijk in al deze strategie¨en is dat zij examens plannen naargelang de moeilijkheid die hiermee gepaard gaat, alleen wordt deze moeilijkheidsgraad op een verschillende manier gedefinieerd. 1. De largest degree strategie plant de examens naargelang het aantal conflicten met andere examens. Met andere woorden, het examen met het hoogste aantal conflicten wordt eerst gepland. 2. De largest weighted degree strategie is een variant van de largest degree strategie waarbij gecorrigeerd wordt voor het aantal betrokken studenten. 3. Wanneer de saturation degree strategie wordt toegepast, worden de examens gerangschikt op basis van het aantal tijdsperiodes die beschikbaar zijn per examen. Examens met een beperkt aantal beschikbare tijdsperiodes worden gepercipieerd als zijnde moeilijk en worden bijgevolg eerst gepland ([12]). 4. Planning op basis van het aantal ingeschreven studenten wordt toegepast door de largest enrolment strategie. Examens met het hoogste aantal ingeschreven studenten worden ge¨ınterpreteerd als belangrijkste en daarom eerst gepland in de beschikbare periodes. 5. De random ordering strategie kent examens toe aan beschikbare periodes in een willekeurige orde. In dit geval zal de planning volledig random zijn in alle mogelijke periodes.
3.2 Voor- en nadelen
26
[26] maken verder nog een interessant onderscheid tussen de statische en de dynamische strategie¨en. De statische strategie¨en blijven constant gedurende de uitvoering ervan. Dit is in tegenstelling tot de dynamische sequenti¨ele strategie¨en, die afhankelijk zijn van het aantal knooppunten die reeds gekleurd zijn. Een voorbeeld van een dynamische sequenti¨ele techniek is de color degree. Wanneer de color degree strategie wordt toegepast, wordt de moeilijkheidsgraad bepaald op basis van het aantal mogelijke conflicten dat een bepaald examen heeft met de reeds geplande examens op dat moment ([23]). Een examen met een hoog aantal mogelijke conflicten wordt beschouwd als moeilijker te plannen en wordt bijgevolg eerst gepland in het examenrooster. Vaak wordt gebruik gemaakt van een conflictmatrix als initi¨ele representatie voor het probleem ([30]). In deze matrix vormt elk element (i,j) een indicatie voor het aantal studenten dat zowel examen i , als examen j moet afleggen. Het organiseren van het probleem in de vorm van een matrix kan heel bruikbaar zijn om bijvoorbeeld het aantal studenten te minimaliseren die 2 examens moeten afleggen in y opeenvolgende periodes ([30]). In de volgende paragraaf worden de voor-en nadelen van deze techniek aangehaald. Dit hoofdstuk over de graph-based sequenti¨ele technieken wordt afgesloten met een voorbeeld waarin de werking van dit algoritme wordt verduidelijkt.
3.2
Voor- en nadelen
Aanvankelijk vormden de graph-based sequenti¨ele technieken een eerste benadering tot het oplossen van het examen scheduling probleem. Het grote voordeel van sequenti¨ele technieken bij het plannen van examenroosters is dat zij een vrij goede uitkomst verschaffen en dit door middel van een beperkte CPU (Central Processing Unit)- tijd. Deze techniek wordt echter minder bruikbaar wanneer het aantal ingeschreven studenten stijgt. Mede door de stijgende complexiteit die gepaard gaat met het opstellen van examenroosters zijn sequenti¨ele technieken te eenvoudig of onpraktisch en worden ze meer en meer gebruikt in hybridisatie met andere algoritmes, m.a.w. de sequenti¨ele technieken worden ge¨ıncorporeerd in andere technieken zoals de evolutionaire algoritmes (cfr. 6.2). Sequenti¨ele technieken tonen zich bijgevolg vooral nuttig in het beginstadium van het examen scheduling probleem aangezien zij een goede en bruikbare initi¨ele oplossing verschaffen. Deze initi¨ele oplossing dient dan op haar beurt als basis voor andere algoritmes. Deze hybridisatie met andere heuristieken verhoogt op een ingrijpende manier de kwaliteit van het uiteindelijke examenrooster ([26],[24],[42]). Naast de hierboven geformuleerde nadelen, is er nog een ander minpunt aan het gebruik van
3.3 Voorbeeld
27
deze techniek waarmee rekening gehouden moet worden. Bij het opstellen van examenroosters door middel van dit algoritme wordt namelijk geen rekening gehouden met de soft constraints. Zo zal steeds getracht worden om de knooppunten van de bekomen grafiek te kleuren met behulp van een minimum aantal kleuren, m.a.w. de examens worden gepland in een minimum aantal periodes. Dit betekent echter dat studenten hoogstwaarschijnlijk meerdere examens in opeenvolgende periodes zullen moeten afleggen. De spreiding van examens over de examenperiodes (tweede orde restrictie) wordt dus niet gerespecteerd.
3.3
Voorbeeld
Aan de hand van een eenvoudig voorbeeld, gebaseerd op [59], wordt geprobeerd de werking van deze techniek duidelijk te maken. Er werd geopteerd om de largest degree strategie toe te passen (cfr.3.1). Volgende data zijn gegeven in tabel 3.1.
Tabel 3.1: Gegevens Student
Vakken
A
SCM,ICT
B
SCM,ICT, Project, FGO
C
Project, SW Eng, Mktg NT, AOR, Trans Eco
D
SW Eng, Project, Inn Mgmt
Zoals reeds vermeld kan bovenstaande informatie ook samengevat worden in een conflictmatrix (cfr 3.1). Matrix X is een symmetrische matrix en geeft weer welke examens studenten gemeenschappelijk hebben.
3.3 Voorbeeld
28
Figuur 3.1: Grafische representatie van het probleem
2 2 1 1 X= 0 0 0 0 0
2 1 1 0 0 0 0 0 2 1 1 0 0 0 0 0 1 3 1 2 1 1 1 1 1 1 1 0 0 0 0 0 0 2 0 2 1 1 1 1 0 1 0 1 1 1 1 0 0 1 0 1 1 1 1 0 0 1 0 1 1 1 1 0 0 1 0 1 0 0 0 1
(3.1)
Uit de gegevens kan opgemaakt worden dat er, naar analogie met het voorbeeld in hoofdstuk 2, negen verschillende examens zijn (SCM, ICT, Project, FGO, SW Eng, Mktg NT, AOR, Trans Eco en Inn Mgmt). Deze negen te plannen examens zullen in onze grafische representatie de knooppunten voorstellen. Examens die ´e´en of meerdere studenten gemeenschappelijk hebben, worden bijgevolg met elkaar verbonden zodat de mogelijke conflicten die kunnen ontstaan zichtbaar worden. Op deze manier wordt de hard constraint die zegt dat examens die studenten gemeenschappelijk hebben niet op hetzelfde moment mogen plaats vinden, gerespecteerd. De resulterende grafiek heeft bijgevolg 9 knooppunten en 18 verbindingslijnen tussen de knooppunten. Dit alles wordt weergegeven in figuur 3.1. Aan de hand van de largest degree strategie zal gepoogd worden de examens toe te kennen aan een minimaal aantal examensessies. De moeilijkheid van de te plannen examens wordt
3.3 Voorbeeld
29
bijgevolg bepaald naar gelang het aantal conflicten met andere examens (tabel 3.2). Tabel 3.2: Aantal conflicten met andere examens Vak
Aantal conflicten
Project
8
SW Eng
5
AOR
4
Mktg NT
4
Trans Eco
4
SCM
3
ICT
3
FGO
3
Inn Mgmt
2
Uit tabel 3.2 blijkt dat het examen Project Management (Project) het grootste aantal mogelijke conflicten vertoont met andere examens. Dit examen wordt volgens de largest degree strategie gepercipieerd als het moeilijkste en wordt bijgevolg als eerste gepland. Aan het knooppunt Project wordt een eerste kleur toegekend (figuur 3.2) en het examen Project Management wordt gepland in de eerste examenperiode. De beslissing om dit examen toe te wijzen aan de eerste examenperiode is in dit voorbeeld gesteund op de overweging om moeilijk te plannen examens zo vroeg mogelijk in te passen in het schema. Het is noodzakelijk op te merken dat het examen Project Management in eender welke periode gepland had kunnen worden, maar om het voorbeeld zo duidelijk mogelijk te behouden en omwille van de hierboven geformuleerde reden, werd gekozen om examens te plannen in de eerst beschikbare periode. Nu Project Management toegekend is aan een examenperiode wordt dezelfde werkwijze verder gezet en wordt het aantal conflicten, i.e. de graad aangepast. Op deze manier komt men opnieuw te weten welk van de overige examens het moeilijkst te plannen is. Dit wordt gegenereerd in tabel 3.3. Uit tabel 3.3 kan men opmaken dat het examen Software Engineering (SW Eng) momenteel het moeilijkst te plannen is aangezien het aantal conflicten met andere examens hier het grootst is. In de grafiek wordt aan het knooppunt SW Eng een tweede kleur toegekend. Met andere woorden, SW Eng wordt gepland in de tweede periode. Ook hier moet opgemerkt worden dat SW Eng aan een andere periode -uitgezonderd de eerste examenperiode wegens conflict met
3.3 Voorbeeld
30
Figuur 3.2: Grafische representatie na toewijzing van examen Project Mgmt
Project Management- had toegewezen kunnen worden. Om de consequentie te behouden, werd ook hier geopteerd om SW Eng toe te wijzen aan de eerst volgende beschikbare examenperiode, i.e. de tweede examenperiode. Op de zelfde manier kunnen de examens Applied Operations Research (AOR), Marketing van Nieuwe Technologie¨en (Mktg NT) en Transport Economie (Trans Eco) gepland worden op basis van de mogelijke conflicten die kunnen ontstaan met de nog te plannen examens. Deze drie examens hebben onderling studenten gemeenschappelijk en kunnen bijgevolg niet in dezelfde periode gepland worden. Aan elk van deze drie examens wordt een verschillende kleur toegekend die eveneens verschilt van de kleuren toegewezen aan Project Management en Software Engineering. De examens Supply Chain Management (SCM), ICT en Financiering van Groeigerichte Ondernemingen (FGO) vertonen geen conflicten met SW Eng. Ze vertonen daarentegen wel onderlinge conflicten. Bijgevolg kan ´e´en van deze examens (bijv. FGO) in dezelfde periode gepland worden als SW Eng. Dit knooppunt zal in de grafische voorstelling dezelfde kleur krijgen als het knooppunt SW Eng. De gehanteerde methode moet herhaald worden voor de overige examens maar zal hier niet verder uitgediept worden. De resulterende grafische voorstelling en het daaruit volgende examenrooster wordt voorgesteld in figuur 3.3 en tabel 3.4. Deze tabel verschaft ´e´en van de mogelijke oplossingen: de hard constraint is immers vervuld. Alle beschouwde examens kunnen gepland worden in minimaal vijf periodes. Dit stelt eveneens het chromatische getal voor.
3.3 Voorbeeld
31
Tabel 3.3: Aantal conflicten na allocatie van Project Management Vak
Aantal conflicten
SW Eng
4
AOR
3
Mktg NT
3
Trans Eco
3
SCM
2
ICT
2
FGO
2
Inn Mgmt
1
Tabel 3.4: Resulterend examenrooster na toepassing van largest degree strategie Periode 1
Periode 2
Periode 3
Periode 4
Periode 5
Project
SW Eng
ICT
Trans Eco
AOR
-
FGO
Inn Mgmt
SCM
-
-
-
Mktg NT
-
-
Figuur 3.3: Grafische representatie: Mogelijk examenrooster
CASE-BASED REASONING
32
Hoofdstuk 4
Case-based Reasoning 4.1
Inleiding
De beschrijving van de case-based reasoning (CBR) techniek steunt hoofdzakelijk op het werk van [19]. In hun paper beschrijven deze onderzoekers op een duidelijke en gestructureerde manier hoe het scheduling probleem op te lossen. Hoewel het hier gaat om het oplossen van het course timetabling probleem wordt deze uiteenzetting toch als zeer waardevol opgevat aangezien het een gelijkaardig probleem betreft (cfr. 2.4), doch tegelijkertijd rekening houdt met de verschillen. Het basisidee achter de CBR techniek is dat oplossingen van vorige examen scheduling problemen een bruikbaar hulpmiddel vormen voor het vinden van oplossingen van een nieuw examen scheduling probleem. In de case-base, i.e. de verzameling van oplossingen van voorgaande problemen, wordt het voorgaande probleem, dat de grootste gelijkenis vertoont met het huidige probleem, gezocht en geselecteerd. Het geselecteerde probleem doet dienst als een soort construct en kan vervolgens hergebruikt en aangepast worden om een oplossing voor het huidige probleem te bekomen. De CBR-technieken behoren dan ook tot de klasse van de knowledge-based technieken aangezien kennis verworven tijdens het oplossen van voorgaande problemen wordt hergebruikt ([28]). Aanvankelijk werden cases, i.e. bekomen examenroosters uit voorgaande probleemstellingen, enkel en alleen gemodelleerd door middel van lijsten met feature-value koppels ([28]). Elk examenrooster werd immers beoordeeld op basis van een aantal kenmerken (f eatures), waaraan een bepaalde waarde of gewicht werd gegeven. De uiteindelijk bekomen gewogen som werd vervolgens gebruikt om de gelijkenissen tussen de twee examenroosters te identificeren ([19]) en om
4.1 Inleiding
33
het meest gelijkaardige examenrooster te gebruiken als basis voor het nieuwe examen scheduling probleem. [28] modelleren dit als volgt:
S(Cb , Cn ) = qP j
1 ωi (f bi − f ni
(4.1) )2
+1
Hierbij is j het aantal kenmerken (i.e.features) waarop examenroosters beoordeeld worden. In [28] wordt een overzicht gegeven van mogelijke kenmerken. Een aantal van deze kenmerken zijn overgenomen in tabel 4.1. Deze lijst is niet-exhaustief en heeft een illustratieve opzet. Voor een uitgebreider overzicht wordt verwezen naar de literatuur [28]. Tabel 4.1: Mogelijke kenmerken van het Examen Scheduling Probleem Kenmerk
Beschrijving
f0
Aantal examens
f1
Aantal mogelijke tijdsperiodes
f2
Aantal hard constraints
f3
Densiteit van de conflictmatrix
Het gewicht toegekend aan het i de kenmerk wordt voorgesteld door ωi . De toegekende gewichten beduiden de relevantie van een bepaald kenmerk bij het vergelijken van verschillende cases. Tenslotte indiceren f bi en f ni de waarden van het i de kenmerk voor de bestaande case (Cb ) en de nieuwe case (Cn ). S wijst op de gelijkaardigheid of similariteit tussen de bestaande en de nieuwe oplossing voor het examen scheduling probleem. Hoe hoger dit getal, hoe gelijkaardiger beide oplossingen. De denkwijze achter CBR steunt met andere woorden op het isomorf karakter van twee grafieken. Twee grafieken worden verondersteld isomorf te zijn als er een ´e´en op ´e´en overeenkomst is tussen verbindingslijnen en knooppunten van twee grafieken ([19]). Het gebruik van de feature-value koppels bleek in de praktijk, meer bepaald bij timetabling problemen, eerder een minder bruikbaar middel aangezien er enkel rekening gehouden werd met de absolute positie van bepaalde events, i.e. geplande examens. Op deze manier wordt belangrijke informatie en kennis, die nodig is om gelijkaardige examenroosters te identificeren, genegeerd. Zo wordt bijvoorbeeld geen rekening gehouden met het feit dat geplande examens meestal onderling verbonden zijn ([19]). [19] suggereren in hun paper dan ook een handiger hulpmiddel om cases te modelleren, namelijk
4.2 Voor- en nadelen
34
de attribute graphs. De attribute graphs kunnen gebruikt worden om de meer diepgaande kennis van een bepaalde case of examenrooster duidelijk te maken. De relatie tussen de verschillende events, in dit geval de examens, wordt op deze manier beschreven. Dit maakt het mogelijk om de case-base op een gestructureerde manier te organiseren en is uitermate interessant in het examen scheduling probleem. Zoals reeds eerder vermeld, geldt namelijk hierbij, net zoals in andere timetabling problemen, dat events onderlinge relaties vertonen. De case-base wordt meestal georganiseerd als een beslissingsboom waarin de attribute graphs van voorgaande problemen hi¨erarchisch gestructureerd worden. Vooraleer de werking van de CBR-techniek met attribute graphs duidelijk te maken aan de hand van een voorbeeld (cfr. 4.3) worden eerst de voor- en nadelen van deze techniek aangehaald.
4.2
Voor- en nadelen
CBR wordt niet alleen toegepast in examen scheduling problemen maar toont zich ook heel bruikbaar in andere domeinen van het operationeel onderzoek zoals ondermeer job shop scheduling en productie planning. CBR maakt het mogelijk om kennis te hergebruiken en te steunen op ervaring met voorgaande, gelijkaardige problemen. Dit kan de verantwoordelijke voor het opstellen van examenroosters heel wat tijd en energie sparen. Volgens [28] zouden CBR-technieken kunnen leiden tot intelligente systemen die in staat zijn om een breder aanbod van problemen op te lossen. In dit geval zou de kost van implementatie aanzienlijk kunnen dalen door gebruik van een meer algemene oplossing in plaats van een case-specifieke oplossing. Uiteraard vergt het verwerken en structureren van voorgaande cases in de case − base heel wat tijd en werk. Dit kan dan ook beschouwd worden als het grootste nadeel verbonden aan het gebruik van deze heuristiek. Een ander nadeel berust op het feit dat het heel moeilijk kan zijn om bestaande cases aan te passen aan een nieuwe probleemstelling. In bepaalde gevallen kan het aanpassen van bestaande examenroosters zelfs zoveel tijd en moeite kosten dat het eenvoudiger is om van nul te starten ([19]).
4.3
Voorbeeld
Het voorbeeld, waarmee de CBR-techniek ge¨ıllustreerd wordt, is gebaseerd op het voorbeeld uit [19], evenwel aangepast voor het examen scheduling probleem. De CBR-techniek zal ge¨ıllustreerd worden door middel van de attribute graphs vermits hier de
4.3 Voorbeeld
35
Figuur 4.1: Toekenning van attributen aan knooppunten en verbindingslijnen van het oude probleem
relatie tussen de verschillende examens duidelijk wordt. Als startpunt voor de attribute graphs worden attributen toegekend aan de knooppunten (i.e. de examens) en aan de verbindingslijnen die deel uit maken van figuur 4.1. De attributen voor de knooppunten en de verbindingslijnen en hun betekenis worden samengevat in tabel 4.2 en 4.3. Tabel 4.2: Attributen behorende tot de knooppunten van het Examen Scheduling Probleem Label
Attribuut
Waarde
Beschrijving
0
Schriftelijk Examen
N/A
Het examen is schriftelijk
1
Mondeling Examen
N/A
Het examen is mondeling
2
Fixed
S
Het examen vastleggen in periode S
3
Examen
S
Het examen mag niet liggen in periode S
De toegekende attributen aan de verbindingslijnen tussen de examens vatten in zekere zin de constraints samen die opgelegd worden aan een examen scheduling probleem. Dit is evenwel probleemspecifiek. Wanneer een vergelijking gemaakt wordt met de constraints opgesteld in hoofdstuk 2 kan men vaststellen dat deze constraints, hoewel ze niet expliciet geformuleerd worden, toch gerespecteerd worden. Ook vergelijking 2.3 wordt impliciet gerespecteerd. Het toekennen van attribuut 7 aan een verbindingslijn indiceert een mogelijk conflict. Bijgevolg zullen deze examens niet op hetzelfde moment gepland kunnen worden.
4.3 Voorbeeld
36
Tabel 4.3: Attributen behorende tot de verbindingslijnen van het Examen Scheduling Probleem Label
Attribuut
Waarde
Beschrijving
4
Voor/Na
1/0
Examen moet resp. voor/na ander examen plaatsvinden
5
Opeenvolgend
N/A
2 examens moeten elkaar opvolgen
6
Niet-Opeenvolgend
N/A
2 examens mogen elkaar niet opvolgen
7
Conflict
N/A
2 examens hebben studenten gemeenschappelijk
Attribuut 2 en 3 vertegenwoordigen vergelijking 2.6 en 2.7 waarbij examens in een bepaalde periode moeten gepland worden of waarbij juist moet vermeden worden dat examens aan een bepaalde periode toegewezen worden. Zoals reeds vermeld in de inleiding van dit hoofdstuk steunt het gebruik van de CBR-techniek op het isomorf karakter van twee grafieken of attribute graphs. Deze attribute graphs kunnen vervolgens vergeleken worden zodat de mate van overeenkomst tussen de twee cases kan vastgesteld worden. [19] suggeren het gebruik van matrices die afgeleid kunnen worden van de attribute graphs van elk van de beschouwde cases. Uit figuur 4.1 kunnen zes matrices afgeleid worden die de basis zullen vormen voor het structureren van de attribute graph in een beslissingsboom. De afgeleide matrices (M1, M2, M3, M4, M5, M6) worden hieronder weergegeven. 0 M 1 = 7 7 0 M 2 = 7 7 1 M 3 = X 7 1 M 4 = 7 4
7 1 X 7 1 4 4 1 7 7 0 7
7
4 1 7 X 1 7 7 0 X 7 1
(4.2)
(4.3)
(4.4)
(4.5)
4.3 Voorbeeld
37
1
M5 = 7 X 1 M 6 = 4 7
7 4 0 7 7 1 X 7 1 7 7 0
(4.6)
(4.7)
De diagonaal van elke matrix geeft de attributen van de knooppunten weer terwijl de overige cellen de attributen van de verbindingslijnen of relaties tussen de knooppunten weergeven. Startend van deze matrices kan men nu de beslissingsboom afleiden. Nog steeds het voorbeeld van [19] volgend, wordt elke (3x3)-matrix voorgesteld als een array van de rij-kolom elementen. De rij-kolom elementen voor de matrices worden samengesteld als volgt:
a1 = a11 a2 = a21 a22 a12 a3 = a31 a32 a33 a23 a13
Het eerste element van elke matrix kan 0 of 1 zijn, i.e. elk geobserveerd examen is schriftelijk of mondeling. Daarom zijn de eerste twee takken van de beslissingsboom 0 of 1. Verdergaand vanuit 0 kan het tweede niveau volgende waarde aannemen: 717. Deze waarde stelt de array a2 voor in matrices M1 en M2. Uit dit niveau kunnen opnieuw twee takken getekend worden, namelijk 741X7 (M1) en 7X147 (M2). Hetzelfde wordt gedaan voor alle takken die uit 1 ontstaan. De resulterende beslissingsboom vindt de lezer in figuur 4.2. Veronderstel nu het nieuw probleem, getoond in figuur 4.3. Een hierbij horende matrix is matrix M. 0 7 7 M = 7 1 4 7 X 1
(4.8)
Door het vergelijken van deze matrix met de beslissingsboom kan men besluiten dat matrix M1 van het oude probleem, het best aansluit met het nieuwe probleem. Indien nodig kan het oude probleem nog worden aangepast, maar dit is in dit geval niet nodig aangezien matrix M
4.3 Voorbeeld
38
Figuur 4.2: CBR Beslissingsboom
Figuur 4.3: Attribute graph van het nieuwe probleem
volledig overeenstemt met ´e´en van de matrices van het oude probleem. Een aantal mogelijke oplossingen voor het nieuwe probleem wordt getoond in tabel 4.3. Tabel 4.4: Mogelijke oplossingen gegenereerd via case-based reasoning Periode 1
Periode 2
Periode 3
Inn Mgmt
SW Eng
AOR
SW Eng
AOR
Inn Mgmt
SW Eng
Inn Mgmt
AOR
Hoewel dit voorbeeld een eenvoudig timetabling probleem beschrijft, waarbij slechts ´e´en kenmerk wordt toegekend aan elk examen (of knooppunt), kan dit probleem uitgebreid worden naar problemen waarbij examens meerdere kenmerken hebben. Zo kan het voorkomen dat een bepaald examen mondeling is (attribuut 1), waarbij het terzelfdertijd ook nog moet liggen in een bepaalde periode (attribuut 2). Dit maakt de beschreven methode natuurlijk iets complexer, maar het gebruik van de matrices moet nog steeds mogelijk zijn.
CONSTRAINT BASED TECHNIEKEN
39
Hoofdstuk 5
Constraint Based Technieken 5.1
Inleiding
Een derde veel gebruikte techniek voor het oplossen van examen scheduling problemen betreft de Constraint Based technieken. Zij vinden hun oorsprong in het gebied van de Artifici¨ele Intelligentie en bestaan uit Constraint Satisfaction Problems (CSP) en Constraint Logic Programming (CLP) technieken. CSP en CLP zijn vrij recent onderzocht door de operationele onderzoekers en vormen een nieuwe aanpak tot het oplossen van het examen scheduling probleem. Naast het suggereren van een oplossing voor dit probleem hebben ze zich in onderzoek ook nuttig getoond bij het oplossen van andere combinatorische problemen aangezien het hierbij meestal ook gaat om het verdelen van een set van resources over een set van met elkaar conflicterende gebeurtenissen. Het examen scheduling probleem wordt meestal gemodelleerd als volgt. Examens worden voorgesteld door een set variabelen X = (x1 , ..., xn ). Voor elke variabele i bestaat er een domein D. Deze domeinen bevatten waarden die kunnen toegekend worden aan elke variabele, rekening houdend met de restricties. Zij vormen beperkingen op de waarden die variabelen, in dit geval de examens, kunnen aannemen. De waarden in elk domein stellen de verschillende examenperiodes voor waaraan examens kunnen toegekend worden. [34] maken het gebruikelijke onderscheid tussen hard (primaire) en soft (secundaire) constraints. De secundaire restricties bepalen mee de kwaliteit van het bekomen examenrooster maar niet de feasibility. Het minder strict naleven van de secundaire constraints, ook wel relaxation genaamd, is mogelijk om een feasible examenrooster te verkrijgen. Het kan namelijk zijn dat er
5.2 Voor- en nadelen
40
zoveel restricties zijn waarmee rekening gehouden moet worden, dat het niet mogelijk is om tot een feasible oplossing te komen. In dit geval worden de secundaire restricties hi¨erarchisch geordend en krijgen ze een bepaald gewicht toegekend om de belangrijkheid en prioriteit weer te geven. Hoe lager dit gewicht, hoe belangrijker de beperking. Hard constraints hebben het gewicht 0, wat wil zeggen dat ze verplicht zijn en relaxatie niet toegestaan is. [30] gebruiken een ander algoritme, namelijk backtracking, om infeasible oplossingen te voorkomen. Hierbij wordt aan een variabele een zekere waarde uit haar domein toegekend. Worden bepaalde restricties geschonden tussen de huidige variabele en alle vorige variabelen dan wordt een andere waarde gekozen uit het domein van deze variabele. Zijn er geen andere waarden meer mogelijk voor de huidige variabele, dan ’backtrackt’ het algoritme naar de vorige variabele en wordt er een nieuwe waarde toegekend aan die variabele.
5.2
Voor- en nadelen
CSP en CLP worden over het algemeen gepercipieerd als een gemakkelijke en flexibele aanpak in het oplossen van examen scheduling problemen. Dit is in tegenstelling tot Operations Research (OR) methodes. Deze methodes missen de nodige flexibiliteit omdat het hierbij vaak heel moeilijk is om een model te vinden dat rekening houdt met alle restricties. Volgens [34] laten CSP en CLP toe goede examen- en lesroosters op te stellen binnen een aanvaardbare tijdsperiode en met een zo effici¨ent mogelijk gebruik van de beschikbare resources. Verder is het ook gemakkelijker via deze technieken om de menselijke voorkeuren met betrekking tot het examenrooster aan bod te laten komen. Overigens maakt CSP het mogelijk om een probleemstelling gemakkelijk aan te passen wanneer restricties gewijzigd, toegevoegd of verwijderd worden. Een nadeel dat gepaard gaat met CSP en CLP is het feit dat het aantal restricties exponentieel stijgt met een toenemend aantal variabelen, in dit geval de examens. Dit zorgt ervoor dat de oplossing van het probleem een grotere CPU-tijd vereist ([34]).
5.3
Voorbeeld
Aan de hand van dit voorbeeld wordt gepoogd de werking van de Constraint Based technieken te illustreren. Eerst wordt een set van variabelen gedefinieerd. Deze set van variabelen stelt de examens voor
5.3 Voorbeeld
41
en wordt nauwkeuriger gedefinieerd in tabel 5.1. In dit voorbeeld bestaat de set van variabelen uit negen examens. Tabel 5.1: Set van variabelen en hun domeinen voor de Constraint Based technieken Variabele
Beschrijving
Domein
Waarden
x1
SCM
D1
{1,2,3,4,5,6,7,8}
x2
ICT
D2
{1,...,16}
x3
Project
D3
{1,...,16}
x4
FGO
D4
{1,3,5,7,10,12,14}
x5
SW Eng
D5
{1,...,16}
x6
Mktg nt
D6
{2,5,8,10,13}
x7
AOR
D7
{1,...,16}
x8
Trans Eco
D8
{3,5,6,9,12,14}
x9
Inn Mgmt
D9
{1,...,16}
Voor dit voorbeeld wordt verondersteld dat de negen beschreven examens gepland moeten worden in een examenperiode van ´e´en week. Dit is gelijkaardig aan het voorbeeld gebruikt in hoofdstuk 2. Op elke werkdag (i.e. maandag tot vrijdag) zijn er drie mogelijke examensessies. Op zaterdag kan er ´e´en examensessie plaatsvinden en geen enkel examen kan gepland worden op zondag. Aan elke examensessie kan een numerieke waarde toegekend worden zodat de volledige examenperiode voorgesteld kan worden als een verzameling (T) van numerieke getallen die elke examensessie onbetwistbaar van elkaar onderscheidt. Deze verzameling wordt hieronder voorgesteld:
T= {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}
Hierbij indiceert 1 de eerste examensessie op maandag in de examenperiode, 2 verwijst naar de tweede examensessie op deze maandag en 3 verwijst naar de laatste examensessie van deze dag. 4 is een indicatie voor de eerste examensessie van de volgende dag enz. De gesuggereerde representatie werd als bruikbaar beschouwd aangezien dit toelaat om de domeinen van de variabelen op een duidelijke manier voor te stellen. Het domein van elke variabele wordt ook weergegeven in tabel 5.1 en stelt de mogelijke examensessies voor waarin elk examen
5.3 Voorbeeld
42
gepland kan worden. Na het defini¨eren van de variabelen, de domeinen en de examenperiode, worden nu de constraints in rekening gebracht. Ook in dit voorbeeld is de belangrijkste hard constraint, deze waarbij gesteld wordt dat examens die studenten gemeenschappelijk hebben, niet op hetzelfde moment gepland mogen worden. Aangezien voor dit voorbeeld dezelfde examens en hun onderlinge relaties werden gebruikt als in het voorbeeld van hoofdstuk 2 en hoofdstuk 3, kan gebruik gemaakt worden van matrix X om mogelijke conflicten tussen de examens te identificeren. Deze matrix zal hieronder niet opnieuw gedefinieerd worden. Er wordt verwezen naar matrix 3.1. Naast deze hard constraint moet ook nog rekening gehouden worden met een aantal andere constraints. [7] geven een overzicht van mogelijke constraints (primaire en secundaire). Deze restricties werden aangepast aan het specifieke probleem en worden hieronder samengevat. • Tussen twee geplande examens, met gemeenschappelijke studenten, moeten telkens twee vrije examensessies gepland worden. • Examen Inn Mgmt moet aan examensessie 14 worden toegewezen. • Examen Inn Mgmt mag niet als eerste examen volgen op het examen Project • Examen AOR en Project mogen elkaar niet opvolgen. Merk op dat de restrictie die zegt dat examens niet toegewezen mogen worden aan bepaalde, vooraf gedefinieerde periodes, reeds opgenomen werd bij het defini¨eren van de domeinen. Bepaalde examensessies werden in het domein van bepaalde examens immers reeds ge¨elimineerd. Zoals in punt 5.1 reeds werd aangehaald kunnen bepaalde van deze constraints minder strict gevolgd worden indien noodzakelijk. Verondersteld wordt dat er slechts ´e´en hard constraint is waarmee rekening gehouden moet worden. Deze krijgt het gewicht 0 toegekend. De overige restricties (soft) worden als gelijkwaardig beschouwd en krijgen allemaal een gewicht 10 toegekend indien relaxation noodzakelijk is om tot een oplossing, i.e. een feasible examenrooster, te komen. Voor dit specifiek voorbeeld gebeurt de toewijzing op basis van het grootste examen, wat betekent dat het examen met de meeste inschrijvingen eerst gepland wordt. Dit betekent dat de examens in de volgende volgorde gepland kunnen worden: Project, SCM, ICT, SW Eng, FGO, Mktg nt, AOR, Trans Eco en Inn Mgmt.
5.3 Voorbeeld
43
Wanneer voor een bepaald examen, verschillende mogelijke examensessies mogelijk zijn, wordt het examen gepland in de vroegste examensessie. Project kan als eerste gepland worden, aangezien hiervoor drie studenten ingeschreven zijn. Dit kan opgemaakt worden uit matrix X. Uit tabel 5.1 kan men opmerken dat Project in elke examensessie gepland kan worden. Bovenstaande regels in acht nemend, betekent dit dus dat Project in de eerste examensessie op de eerste maandag (1) gepland wordt. Het volgende examen dat gepland wordt, is het examen SCM, waarvoor twee studenten ingeschreven zijn. Dit examen heeft ´e´en student gemeenschappelijk met Project Mgmt en mag bijgevolg niet in dezelfde examensessie gepland worden. De eerst volgende mogelijke examenperiode is vier aangezien er twee vrije examensessies moeten gepland worden tussen examens die studenten gemeenschappelijk hebben. Door SCM in de vierde examensessie te plannen wordt ook het domein van deze variabele gerespecteerd. ICT betreft het derde examen dat gepland wordt. Dit examen heeft zowel studenten gemeenschappelijk met Project als met SCM en wordt dus niet toegewezen aan ´e´en van de reeds gevulde examensessies. ICT kan in elke examensessie gepland worden wanneer gekeken wordt naar het domein van deze variabele. Omdat er opnieuw rekening gehouden moet worden met de twee vrije examensessies, wordt examen ICT gepland in periode zeven. Na het plannen van Project, SCM en ICT kan SW Eng opgenomen worden in het examenrooster. SW Eng heeft enkel twee studenten gemeenschappelijk met het examen Project. Volgens haar domein kan SW Eng in alle periodes gepland worden. Rekening houdend met alle beperkingen wordt het examen SW Eng naast SCM gepland in de vierde examensessie. Vervolgens wordt het examen FGO in beschouwing genomen. Dit examen kan slechts aan een beperkt aantal examensessies toegewezen worden (tabel 5.1). FGO kan mogelijke conflicten vormen met alle reeds geplande examens behalve met SW Eng. De eerste beschikbare examensessie voor dit examen betreft de tiende examensessie. Deze examensessie is ook in overeenstemming met het domein van het geobserveerde examen. De overige vier examens worden volgens dezelfde logica toegewezen aan beschikbare examensessies. Dit resulteert in een rooster waarbij Mktg nt aan sessie acht wordt toegewezen. Het examen AOR wordt toegewezen aan examensessie elf. Tenslotte worden zowel examen Trans Eco en examen Inn Mgmt aan periode veertien toegewezen. In dit voorbeeld is backtracking niet vereist aangezien alle examens aan de gekozen periodes toegekend kunnen worden zonder het hiermee onmogelijk te maken voor een ander examen om
5.3 Voorbeeld
44
gepland te worden in de toelaatbare examensessies. Het resulterend examenrooster wordt voorgesteld in tabel 5.2. Tabel 5.2: Resulterend examenrooster m.b.v. de Constraint Based technieken Ma
Di
Woe
Do
Vrij
Za
Project
SCM/SW Eng
ICT
FGO
-
-
-
-
Mktg nt
AOR
TRANS Eco/Inn Mgmt
-
-
-
-
-
-
-
METAHEURISTIEKEN
45
Hoofdstuk 6
Metaheuristieken 6.1
Lokale Zoekalgoritmes
De lokale zoekalgoritmes (Local Search) maken deel uit van de categorie van de metaheuristieken. Zij vormen de vierde soort van algoritmes die hier besproken zullen worden. Deze heuristieken zijn veelal gebaseerd op concepten uit andere domeinen (vb. thermodynamica en metallurgie en andere mechanismes uit de natuur). De meest voorkomende lokale zoekalgoritmes zijn tabu search en simulated annealing. [42] stellen dat lokale zoekalgoritmes niet-exhaustief zijn. Hiermee wordt bedoeld dat ze niet noodzakelijk een feasible of optimale oplossing verschaffen maar dat ze daarentegen wel op een niet-systematische manier de omgeving onderzoeken. De omgeving wordt nauwkeurig onderzocht tot een bepaalde conditie is bereikt. In punt 6.1.4 wordt meer aandacht besteed aan deze omgeving. In punt 6.1.3 worden de voor- en nadelen van de beschreven zoekalgoritmes gezamenlijk besproken. Verder wordt hierin ook een onderlinge vergelijking gemaakt van de gebruikte heuristieken.
6.1.1
Tabu Search
Tabu Search (TS) is ´e´en van de meest voorkomende lokale zoekalgoritmes die wordt toegepast in scheduling problemen. [42] geven een duidelijke uiteenzetting van het TS algoritme die als zeer bruikbaar werd beschouwd. Men start van een initi¨ele oplossing Si , in dit geval een initieel examenrooster. Belangrijk hierbij is dat deze initi¨ele oplossing niet noodzakelijk een mogelijk examenrooster (i.e. hard constraints zijn voldaan) hoeft te zijn. Dit omdat een goede oplossing mogelijks in de omgeving
6.1 Lokale Zoekalgoritmes
46
van een slechte oplossing kan liggen ([62]). De bijhorende waarde van de doelfunctie (een kostfunctie die men wenst te minimaliseren), wordt gegeven door F (Si ). TS doorzoekt een deel V van de omgeving N (Si ). Het element uit V met de laagste waarde voor de kostfunctie wordt geselecteerd en wordt de nieuwe oplossing Si+1 . Dit gebeurt ongeacht of de waarde van de nieuwe doelfunctie F (Si+1 ) kleiner is dan de waarde van de originele doelfunctie F (Si ). Doordat de waarde van de nieuwe doelfunctie, met betrekking tot het nieuw bekomen examenrooster, niet noodzakelijk kleiner moet zijn dan de waarde van de originele doelfunctie van het vorig geobserveerde rooster, wordt verhinderd dat men vast dreigt te zitten in lokale optima. Bovendien verhindert het TS algoritme cyclische bewegingen door gebruik van een Tabu List. De Tabu List bevat een lijst van alle net onderzochte oplossingen uit V , i.e. het paar (examen, periode). Door gebruik van de T abu List wordt de zoekopdracht uitgebreid tot bepaalde regio’s van de zoekomgeving die voorheen nog niet eerder onderzocht waren. Uit onderzoek ([62]) blijkt n/3 een aanvaardbare lengte voor de Tabu List. Hierbij is n het aantal te plannen examens. Deze lijst heeft bijgevolg een vooraf bepaalde lengte L en telkens wanneer een nieuwe, net onderzochte, oplossing wordt toegevoegd, wordt de oudste onderzochte oplossing van de lijst verwijderd. Wanneer oplossing Si+1 geselecteerd is, worden de hierboven vermelde stappen herhaald en wordt een nieuwe oplossing gezocht in een deel V ∗ van N (Si+1 ). Dit algoritme wordt, zoals reeds vermeld in de inleiding, herhaald tot een bepaalde conditie bereikt is, bv. tot wanneer er gedurende een aantal iteraties geen verbetering van de doelfunctie wordt vastgesteld. [62] opteerde als stopcriterium voor 30 iteraties zonder verbetering. In tegenstelling tot het Simulated Annealing algoritme (zie 6.1.2), dat slechts ´e´en oplossing genereert, produceert het Tabu Search algoritme verschillende gemuteerde oplossingen. Voorbeeld Opnieuw wordt voor dit voorbeeld gebruik gemaakt van de reeds in voorgaande hoofdstukken aangehaalde probleemstelling. Bijgevolg moeten ook hier negen examens gepland worden: Project, SCM, ICT, SW Eng, FGO, Mktg nt, AOR, Trans Eco en Inn Mgmt. Matrix X (zie ook hoofdstuk 2, hoofdstuk 3 en hoofdstuk 5) is ook hier van toepassing. De beschouwde examenperiode beschrijft eveneens een periode van een week (van maandag tot zaterdag), waarbij drie examensessies kunnen plaats vinden op elke werkdag en slechts ´e´en
6.1 Lokale Zoekalgoritmes
47
examensessie op zaterdag. Voor elk examen geldt dat het gepland kan worden in elke examenperiode. Het initieel examenrooster (S1 ) van waaruit het T abu Search-algoritme zal starten, wordt gegenereerd in tabel 6.1. Tabel 6.1: Initieel examenrooster Ma
Di
Woe
Do
Vrij
Za
Project/ICT
SCM/SW Eng
-
FGO
-
-
-
-
Mktg nt
AOR
TRANS Eco/Inn Mgmt
-
-
-
-
-
-
-
De lezer kan hierbij opmerken dat het initieel examenrooster niet f easible is. Examen Project en ICT vallen immers op hetzelfde moment, hoewel ze studenten gemeenschappelijk hebben zoals uit matrix X (cfr. matrix 3.1) blijkt. Zoals uit 6.1.1 gebleken is, is f easibility geen vereiste voor het examenrooster waarvan gestart wordt. Veronderstel dat voor het schenden van de hard constraint een kost van 100 wordt gerekend. Dit geeft F(S1 ), in aanvulling tot het berekenen van de doelfunctie (vergelijking 2.1) voor het bekomen examenrooster. Het berekenen van vergelijking 2.1 gebeurt op basis van de logaritmische schaal. De berekening wordt weergegeven in tabel 6.2. Sommatie van de waarden in de rechterkolom geeft een totaal van 30. Dit vermeerdert met de kost van 100, verbonden aan de schending van de hard constraint, geeft 130 voor F(S1 ). Deze waarde is vrij hoog, maar is hoofdzakelijk te wijten aan het inf easible karakter van het examenrooster. Het T abu Search-algoritme bestaat erin de omgeving van de initi¨ele oplossing te onderzoeken. Een examenrooster (S2 ) uit de omgeving van S1 kan gemakkelijk bekomen worden door een swap (i.e. het louter omwisselen van twee examens of examensessies) door te voeren. Voor het gesuggereerde voorbeeld werd gekozen om het examen ICT te wisselen met de zevende examensessie. Op deze manier wordt het examenrooster S2 (zie tabel 6.3) voortgebracht. Het nieuw bekomen rooster is, in tegenstelling tot S1 , f easible. Examens die studenten gemeenschappelijk hebben, zijn in geen enkel geval op hetzelfde moment gepland. De waarde van de doelfunctie F(S2 ) wordt opnieuw berekend door sommatie van de rechterkolom in tabel 6.4. Dit geeft een waarde van 34. Merk op dat hier geen extra kost bij komt, de hard
6.1 Lokale Zoekalgoritmes
48
Tabel 6.2: Berekening van de doelfunctie a.d.h.v. een logaritmische schaal Examens
cij Logaritmische Schaal
# ingeschreven studenten
Kost
Project & SCM
c31
ω(3) = 4
1
4
Project & SW Eng
c35
ω(3) = 4
2
8
ICT & SCM
c21
ω(3) = 4
2
8
ICT & SW Eng
c25
ω(3) = 4
0
0
SCM & Mktg nt
c16
ω(4) = 2
0
0
SW Eng & Mktg nt
c56
ω(4) = 2
1
2
Mktg nt & FGO
c64
ω(2) = 8
0
0
Mktg nt & AOR
c67
ω(3) = 4
1
4
FGO & AOR
c47
ω(1) = 16
0
0
FGO & Trans Eco
c48
ω(4) = 2
0
0
FGO & Inn Mgmt
c49
ω(4) = 2
0
0
AOR & Trans Eco
c78
ω(3) = 4
1
4
AOR & Inn Mgmt
c79
ω(3) = 4
0
0
Tabel 6.3: Examenrooster S2 Ma
Di
Woe
Do
Vrij
Za
Project
SCM/SW Eng
ICT
FGO
-
-
-
-
Mktg nt
AOR
TRANS Eco/Inn Mgmt
-
-
-
-
-
-
-
constraints zijn immers voldaan. Om cyclische bewegingen te vermijden wordt S1 op de T abu List geplaatst (zie 6.1.1). Op deze manier wordt vermeden dat S1 opnieuw geselecteerd wordt bij een volgende iteratie. De T abu List zal voor dit voorbeeld een lengte hebben van 3 (=aantal te plannen examens /3)([62]). Vervolgens kan op S2 opnieuw een swap toegepast worden. De omgeving van S2 wordt met andere woorden onderzocht. Veronderstel dat het examen SW Eng een examensessie later gepland wordt. SW Eng wisselt met andere woorden met de lege vijfde examensessie. S2 wordt op de T abu List geplaatst. Tabel 6.5 geeft het examenrooster S3 weer. Dit examenrooster is eveneens f easible. Net als
6.1 Lokale Zoekalgoritmes
49
Tabel 6.4: Berekening van de doelfunctie voor S2 a.d.h.v. een logaritmische schaal Examens
cij
Logaritmische Schaal
# ingeschreven studenten
Kost
Project & SCM
c31
ω(3) = 4
1
4
Project & SW Eng
c35
ω(3) = 4
2
8
SCM & ICT
c12
ω(3) = 4
2
8
SCM & Mktg nt
c16
ω(4) = 2
0
0
SW Eng & ICT
c52
ω(3) = 4
0
0
SW Eng & Mktg nt
c56
ω(4) = 2
1
2
ICT & Mktg nt
c26
ω(1) = 16
0
0
ICT & FGO
c24
ω(3) = 4
1
4
ICT & AOR
c27
ω(4) = 2
0
0
Mktg nt & FGO
c64
ω(2) = 8
0
0
Mktg nt & AOR
c67
ω(3) = 4
1
4
FGO & AOR
c47
ω(1) = 16
0
0
FGO & Trans Eco
c48
ω(4) = 2
0
0
FGO & Inn Mgmt
c49
ω(4) = 2
0
0
AOR & Trans Eco
c78
ω(3) = 4
1
4
AOR & Inn Mgmt
c79
ω(3) = 4
0
0
voor S1 en S2 , kan F(S3 ) berekend worden. Tabel 6.6 geeft deze berekening weer. Sommatie van de rechterkolom geeft een totale kost (F(S3 )) van 32. Het is belangrijk om op te merken dat bovenstaande werkwijze voor dit voorbeeld steeds een verbetering van de doelfunctiewaarde oplevert. Dit hoeft niet altijd zo te zijn zoals in 6.1.1 vermeld werd. Bovenstaand algoritme kan herhaald worden tot een bepaalde stopconditie bereikt is.
6.1.2
Simulated Annealing
Simulated Annealing is de volgende metaheuristiek waar dieper op in gegaan wordt. Simulated Annealing is een techniek die oorspronkelijk in de thermodynamica en in de metallurgie gebruikt werd om tot een optimale koeling te komen van gesmolten ijzer. Deze optimale toestand impliceert een samenstelling met een minimale hoeveelheid energie. In het operationeel onderzoek, en meer bepaald bij het examen scheduling probleem, tracht
6.1 Lokale Zoekalgoritmes
50
Tabel 6.5: Examenrooster S3 Ma
Di
Woe
Do
Vrij
Za
Project
SCM
ICT
FGO
-
-
-
SW Eng
Mktg nt
AOR
TRANS Eco/Inn Mgmt
-
-
-
-
-
-
-
men deze heuristiek na te bootsen om tot een optimaal examenrooster te komen. De werkwijze van deze heuristiek wordt in wat volgt uitvoerig besproken. Hiervoor wordt de werkwijze, gesuggereerd in [64], gevolgd. Net als bij Tabu Search en andere metaheuristieken, wordt bij Simulated Annealing gestart met een initi¨ele oplossing Xi , in dit geval een initieel examenrooster. Deze oplossing hoeft, net zoals dit bij het Tabu Search algoritme het geval is, niet noodzakelijk een feasible rooster te zijn. Vervolgens wordt voor deze oplossing de bijhorende doelfunctiewaarde F (Xi ) berekend. In een volgende stap wordt een nieuwe, willekeurige oplossing Xi ∗ gekozen uit de omgeving N van Xi . Ook voor Xi ∗ wordt de bijbehorende doelfunctiewaarde F (Xi ∗) berekend en deze wordt vergeleken met F (Xi ). Wanneer F (Xi ∗) <= F (Xi ) , wordt Xi ∗ de nieuwe huidige oplossing. Het examen scheduling probleem is immers een minimalisatieprobleem. Hoe kleiner de doelfunctiewaarde, hoe beter het bekomen examenrooster. In de omgekeerde situatie, indien F (Xi ∗) >= F (Xi ), wordt Xi ∗ niet zonder meer verworpen. Xi ∗ wordt in dit geval aangenomen met een bepaalde waarschijnlijkheid of probabiliteit p(t), die daalt over de tijd t, en met afwijking D(= F (Xi ) − F (Xi ∗)). Deze waarschijnlijkheid wordt gemodelleerd door middel van volgende formule:
p(t) = e(−D/T )
(6.1)
Hierbij stelt T de temperatuur voor. [64] stelt dat deze temperatuur gradueel verlaagd wordt tijdens de zoektocht. In het begin van het algoritme is deze waarschijnlijkheid vrij hoog waardoor bijna alle examenroosters aanvaard worden. Naarmate het algoritme en het aantal iteraties vordert, wordt de probabiliteit veel kleiner, waardoor men steeds veeleisender wordt in het accepteren van mogelijke oplossingen. Ook [30] maakten bovenstaande bevindingen. In de eerste fase van het Simulated Annealing proces wordt om het even welke oplossing geaccepteerd. Zo wordt de zoekomgeving N op een zo volledig mogelijke manier onderzocht. Wanneer de stopconditie is bereikt, wordt het algoritme stopgezet.
6.1 Lokale Zoekalgoritmes
51
Tabel 6.6: Berekening van de doelfunctie voor S3 a.d.h.v. een logaritmische schaal Examens
cij
Logaritmische Schaal
# ingeschreven studenten
Kost
Project & SCM
c31
ω(3) = 4
1
4
Project & SW Eng
c35
ω(4) = 2
2
4
SCM & SW Eng
c15
ω(1) = 16
0
0
SCM & ICT
c12
ω(3) = 4
2
8
SCM & Mktg nt
c16
ω(4) = 2
0
0
SW Eng & ICT
c52
ω(2) = 8
0
0
SW Eng & Mktg nt
c56
ω(3) = 4
1
4
SW Eng & FGO
c54
ω(5) = 1
0
0
ICT & Mktg nt
c26
ω(1) = 16
0
0
ICT & FGO
c24
ω(3) = 4
1
4
ICT & AOR
c27
ω(4) = 2
0
0
Mktg nt & FGO
c64
ω(2) = 8
0
0
Mktg nt & AOR
c67
ω(3) = 4
1
4
FGO & AOR
c47
ω(1) = 16
0
0
FGO & Trans Eco
c48
ω(4) = 2
0
0
FGO & Inn Mgmt
c49
ω(4) = 2
0
0
AOR & Trans Eco
c78
ω(3) = 4
1
4
AOR & Inn Mgmt
c79
ω(3) = 4
0
0
Het gebruik van de Simulated Annealing techniek gaat gepaard met het bepalen van een aantal belangrijke beslissingen, meer bepaald de bepaling van de temperatuur bij elke stap en de stopconditie. Van de gebruiker wordt vereist de benodigde parameters op een zo nauwkeurig mogelijke manier te schatten. Een accurate schatting van de parameters bepaald immers in zeer grote mate de kwaliteit van de bekomen oplossingen. Volgens [64] blijft de temperatuur constant gedurende L opeenvolgende periodes. Verder wordt de temperatuur verlaagd door vermenigvuldiging met een factor α. Deze factor is een indicatie voor de koelingsgraad. Dit alles wordt samengevat in volgende formule (na kL moves): T (kL) = T k = αk To
(6.2)
6.1 Lokale Zoekalgoritmes
52
Bijgevolg impliceert het gebruik van de Simulated Annealing techniek de bepaling van drie parameters: de begintemperatuur To , de koelingsgraad α en tenslotte L, dat een indicatie geeft voor het aantal opeenvolgende periodes. [62] stelt dat de temperatuur logaritmisch moet dalen. Daardoor bestaat een grotere kans dat een optimale oplossing bereikt wordt. De logaritmische daling van de temperatuur impliceert evenwel hogere computing times. De volgende formule wordt gebruikt voor het bepalen van de begintemperatuur T0 [62]: T0 = −D/ln(p)
(6.3)
Naast het bepalen van deze parameters, moet ook de stopconditie bepaald worden. Veelal wordt het algoritme stopgezet na een aantal iteraties zonder verbetering van de doelfunctie. Een andere mogelijkheid is dat het algoritme stopt wanneer de temperatuur 0 nadert ([62]). [30] stellen verder dat, door het gradueel verlagen van de genoemde probabiliteit, het algoritme gestuurd wordt in de richting van een examenrooster dat een lokaal optimum vertegenwoordigt. Door het verder onderzoeken van de zoekomgeving van het bekomen lokaal optimum en door het toepassen van bepaalde moves (zoals bijv. een swap), dreigt men niet vast te blijven zitten in dit optimum. Men kan evolueren naar een volgend lokaal optimum. Het uiteindelijk bekomen rooster is dit examenrooster dat de laagste doelfunctiewaarde bezit van alle beschouwde lokale optima. Voorbeeld Zoals reeds aangehaald, moet bij het Simulated Annealing-algoritme niet gestart worden van een f easible examenrooster. Uit gemakkelijkheidsoverweging werd gekozen voor hetzelfde initieel examenrooster als in het T abu Search voorbeeld. Dit examenrooster wordt opnieuw gepresenteerd in tabel 6.7. Tabel 6.7: Initieel examenrooster X1 Ma
Di
Woe
Do
Vrij
Za
Project/ ICT
SCM/SW Eng
-
FGO
-
-
-
-
Mktg nt
AOR
TRANS Eco/Inn Mgmt
-
-
-
-
-
-
-
Zoals reeds is gebleken, betreft het een inf easible examenrooster, met een bijhorende kost
6.1 Lokale Zoekalgoritmes
53
van 130 (F(X1 )). In een volgende stap wordt een examenrooster uit de omgeving van X1 geselecteerd en de bijhorende waarde van dit nieuw examenrooster wordt vergeleken met F(X1 ). Het nieuw examenrooster wordt voorgesteld in tabel 6.8. Tabel 6.8: Examenrooster X2 Ma
Di
Woe
Do
Vrij
Za
Project
SCM/SW Eng
ICT
FGO
-
-
-
-
Mktg nt
AOR
TRANS Eco/Inn Mgmt
-
-
-
-
-
-
-
Met examenrooster X2 gaat een bijhorende kost gepaard van 34 (zie ook tabel 6.4). De waarde F(X2 ) is kleiner dan de waarde F(X1 ). Examenrooster X2 duidt met andere woorden op een verbetering en wordt aanvaard. Vanaf nu zal met dit examenrooster gestart worden en de omgeving van deze oplossing zal nu verder onderzocht worden. Veronderstel dat er een swap plaatsvindt tussen de examens SCM en SW Eng (periode 4) en het examen ICT (periode 7). Het resulterend examenrooster behoort tot de omgeving van X2 en wordt weergegeven in tabel 6.9. Tabel 6.9: Examenrooster X3 Ma
Di
Woe
Do
Vrij
Za
Project
ICT
SCM/SW Eng
FGO
-
-
-
-
Mktg nt
AOR
TRANS Eco/Inn Mgmt
-
-
-
-
-
-
-
Aan de hand van tabel 6.10 wordt, de logaritmische schaal indachtig houdend, de waarde F(X3 ) berekend. Sommatie van de waarden uit de rechterkolom geeft een waarde van 42 voor F(X3 ). Deze waarde is groter dan F(X2 ), maar rekening houdend met de principes van het Simulated Annealing-algoritme betekent dit niet dat examenrooster X3 zonder meer verworpen wordt. X3 wordt immers met een bepaalde waarschijnlijkheid aanvaard. In [63] wordt voor de waarschijnlijkheid p(t) een waarde aangenomen van 0, 5. Deze waarde bleek de beste combinatie met de koelingsgraad (α) gelijk aan 0, 99 en het aantal moves (L)
6.1 Lokale Zoekalgoritmes
54
Tabel 6.10: Berekening van de doelfunctie voor S3 a.d.h.v. een logaritmische schaal Examens
cij
Logaritmische Schaal
# ingeschreven studenten
Kost
Project & ICT
c32
ω(3) = 4
1
4
ICT & SCM
c21
ω(3) = 4
2
8
ICT & SW Eng
c25
ω(3) = 4
0
0
ICT & Mktg nt
c26
ω(4) = 2
0
0
SCM & Mktg nt
c16
ω(1) = 16
0
0
SCM & FGO
c14
ω(3) = 4
1
4
SCM & AOR
c17
ω(4) = 2
0
0
SW Eng & Mktg nt
c56
ω(1) = 16
1
16
SW Eng & FGO
c54
ω(3) = 4
0
0
SW Eng & AOR
c57
ω(4) = 2
1
2
Mktg nt & FGO
c64
ω(2) = 8
0
0
Mktg nt & AOR
c67
ω(3) = 4
1
4
FGO & AOR
c47
ω(1) = 16
0
0
FGO & Trans Eco
c48
ω(4) = 2
0
0
FGO & Inn Mgmt
c49
ω(4) = 2
0
0
AOR & Trans Eco
c78
ω(3) = 4
1
4
AOR & Inn Mgmt
c79
ω(3) = 4
0
0
gelijk aan 1000. De afwijking D(= F (Xi ) − F (Xi ∗)) bedraagt in dit geval −8. Wanneer al het bovenstaande gecombineerd wordt, kan de begintemperatuur T0 afgeleid worden door de gegevens in te vullen in formule 6.3.
T0 = −(−8)/ln(0, 5)
(6.4)
Dit resulteert in een begintemperatuur gelijk aan −11, 54. Deze temperatuur zal gradueel stijgen en het algoritme zal gestopt worden wanneer de temperatuur 0 nadert.
6.1 Lokale Zoekalgoritmes
6.1.3
55
Voor- en nadelen van de lokale zoekalgoritmes
De lokale zoekalgoritmen worden gekenmerkt door een grote mate van flexibiliteit omdat ze case specifieke restricties in acht nemen en toepasbaar zijn in uiteenlopende domeinen. [64] stelt ook dat lokale zoekalgoritmes gekenmerkt worden door een goede trade-off tussen kwaliteit en computing times. Goede examenroosters worden immers bekomen binnen een aanvaardbare tijd. Eerder (punt 6.1.1 en 6.1.2) werd vermeld dat de onderzochte oplossingen niet noodzakelijk feasible hoeven te zijn. Het aanvaarden van deze infeasible oplossingen laat toe de omgeving te onderzoeken en eventueel goede oplossingen op te sporen. Dit impliceert evenwel een hogere kost.
6.1.4
Het bepalen van de omgeving
Het bepalen van de structuur van de zoekomgeving betreft een uitermate belangrijke beslissing in de lokale zoekalgoritmen. [30] defini¨eren de zoekomgeving (i.e. neighbourhood) van een bepaalde oplossing als de set van alle mogelijke oplossingen die bekomen wordt door het verplaatsen van een bepaald examen naar een nieuwe examensessie. Een goede neighbourhood structuur is cruciaal voor de effectiviteit van het proces ([64]). In [45] wordt een aantal van deze neighbourhood structuren besproken. Ook [1] beschrijven enkele veel gebruikte structuren voor de zoekomgeving. Zo beschrijven ze de two − exhange omgeving waarbij de examens (of slechts een aantal ervan) gepland in twee examensessies van plaats gewisseld worden in het examenrooster. Deze neighbourhood-structuur wordt het meest gebruikt bij het zoeken naar naburige oplossingen in de omgeving van het bestudeerde examenrooster. Naast de two − exhange omgeving, halen [1] ook de cyclic exchange omgeving aan. In navolging van [1] wordt deze zoekomgeving verduidelijkt aan de hand van een kort voorbeeld. [1] beschrijven het examen scheduling probleem bestaande uit partities. Zo stelt elke examensessie een partitie voor. Veronderstel een examen scheduling probleem waarbij 5 examens (E1 , E2 , E3 , E4 , E5 ) gepland worden in drie examensessies. In navolging van de bovengenoemde auteurs wordt elke examensessie voorgesteld als een partitie van het beschreven probleem. Zodoende zijn er in dit voorbeeld drie partities (P1 , P2 , P3 ). Rekening houdend met het bovenstaande kan volgende representatie een mogelijke oplossing zijn tot het examen scheduling probleem.
6.1 Lokale Zoekalgoritmes
56
P1 = (E4 ) P2 = (E5 ,E3 ) P3 = (E1 ,E2 )
Wanneer uitgegaan wordt van een cyclic exchange omgeving bekomt men een naburige oplossing uit het probleem wanneer bijvoorbeeld examen E4 (uit P1 ) verplaatst wordt naar P2 (i.e. de tweede examensessie). Examen E5 uit partitie P2 wordt verplaatst naar P3 . Tenslotte wordt examen E1 uit de derde partitie (P3 ) verplaatst naar de eerste partitie. Volgende oplossing behoort tot de zoekomgeving van eerder geformuleerd examenrooster. P10 = (E1 ) P20 = (E4 ,E3 ) P30 = (E5 ,E2 )
Het cyclisch karakter van deze zoekomgeving kan vrij eenvoudig afgeleid worden uit bovenstaand voorbeeld. Een examen uit elke partitie wordt immers naar de volgende partitie verplaatst.
6.1.5
Tijdsaspect
[14] stellen zich de vraag of de kwaliteit van de resulterende oplossingen afhankelijk is van de tijd waarin de omgeving onderzocht wordt. Zij stellen met andere woorden de zoektijd als input parameter en cre¨eren zo een variant op de Simulated Annealing benadering. De resultaten van dit onderzoek toonden dat het invoeren van de zoektijd als parameter een gunstig effect heeft op de kwaliteit van de resulterende examenroosters. Hoe langer de zoektijd, des te beter de geproduceerde examenroosters zullen zijn. Volgens [14] wordt dit veroorzaakt door het feit dat een groter gebied van de zoekomgeving ge¨exploreerd wordt. Op deze manier wordt de kans om een oplossing met een hogere kwaliteit te vinden vergroot. De gebruiker moet uiteraard de afweging maken tussen de kwaliteit van het bekomen examenrooster en de zoektijd. Daarnaast moet men garanderen dat de zoektijd op een intelligente manier gebruikt wordt om de omgeving te onderzoeken. Een laatste opmerking hieromtrent betreft de vertraagde verbetering van de oplossingen wanneer de zoektijd verlengd wordt.
6.2 Evolutionaire Algoritmes
6.2
57
Evolutionaire Algoritmes
Een tweede categorie metaheuristieken die hier besproken zal worden, behandelt de evolutionaire algoritmes. Deze hebben net als de lokale zoekalgoritmes het kenmerk vrij goede resultaten te produceren binnen een aanvaardbare tijdsperiode. De evolutionaire zoekalgoritmes die hier besproken zullen worden zijn de genetische algoritmes en de algoritmes gebaseerd op het gedrag van mieren, i.e. Ant Colony algoritmes.
6.2.1
Genetische Algoritmes
[64] geeft eveneens een uiteenzetting over de genetische algoritmes die ook als techniek kunnen dienen voor het oplossen van combinatorische optimalisatieproblemen en meer bepaald voor het oplossen van timetabling problemen, waaronder ook het opstellen van examenroosters valt. De genetische algoritmes ontlenen hun naam aan de genetica door het parallel gedrag dat ze hiermee vertonen en principes zoals ’Survival of the Fittest’ en de natuurlijke selectie gelden ook bij toepassing van deze algoritmes. De analogie met de genetica gaat uiteraard nog verder. Zo zijn oplossingen, i.e. examenroosters in het geval van examen scheduling problemen, analoog met chromosomen. Deze examenroosters maken deel uit van de populatie. Variabelen worden voorgesteld door genen en mogelijke waarden voor deze variabelen zijn analoog met allelen. Toegepast op het examen scheduling probleem zijn de variabelen de te plannen examens. De examensessies waarin deze examens gepland kunnen worden komen overeen met de allelen. Door onderlinge interacties van examenroosters ontstaan ’kinderen’. Dit zijn nieuwe generaties van examenroosters die de goede eigenschappen van hun ’ouders’ (i.e. de oplossingen waaruit ze ontstaan zijn) hebben overgenomen. In tegenstelling tot Tabu Search en Simulated Annealing, waarbij men telkens werkt met ´e´en reeds bekomen examenrooster, wordt in de genetische algoritmes gewerkt met een populatie van mogelijke oplossingen. De genetische algoritmes impliceren dus een totaal andere zoekstrategie ([23]) dan de lokale zoekalgoritmes en vormen met andere woorden voorbeelden van populationbased methodes. Bovendien wordt de omgeving van een volledige populatie onderzocht in plaats van de omgeving van een enkel examenrooster. De onderzochte omgeving is niet louter de som van de individuele omgevingen. Dit is het gevolg van de onderlinge interacties van de oplossingen. De werkwijze wordt in wat volgt besproken
6.2 Evolutionaire Algoritmes
58
([62]) en wordt verder nog ge¨ıllustreerd in figuur 6.1. Elk reeds bekomen examenrooster wordt voorgesteld door een bepaalde code of string en stelt een individu van de populatie voor. Deze code bevat de nodige informatie van het beschouwde examenrooster. De codering waarbij elke oplossing bestaat uit een string met zelfde lengte, vergemakkelijkt in een later stadium crossover operaties. De kwaliteit van elke individueel examenrooster wordt gemeten aan de hand van een fitness value. Net zoals bij vele andere algoritmes bekomt men deze fitness value door gebruik te maken van de bijhorende waarde van de doelfunctie. Deze waarde geeft met andere woorden een indicatie van hoe goed deze oplossing is voor het beschouwde probleem. Over het algemeen kan opgemerkt worden dat de gemiddelde fitness value stijgt bij elke volgende generatie, aangezien vooral de goede eigenschappen werden doorgegeven aan deze nieuwe generatie. De initi¨ele populatie P (0), i.e. de populatie op tijdstip t = 0, wordt willekeurig gegenereerd. Deze populatie bestaat uit N examenroosters. P (t) stelt de populatie voor op tijdstip t. De populatie P (t + 1) wordt gegenereerd door het toepassen van de reeds vermelde operatoren. De populatie P (t + 1) stelt een nieuwe generatie voor die bestaat uit de individuen of oplossingen die de vorige generatie overleefd hebben en de nieuwe oplossingen gegenereerd uit oplossingen uit de vorige generatie (offspring). Bij het gebruik van genetische algoritmes moeten, net zoals bij Simulated Annealing, een aantal parameters geschat worden. Deze parameters zijn: selectie, crossover en mutatie operatoren. Zij zijn verantwoordelijk voor het samenstellen van de populatie, de exploratie ervan en het selecteren van de volgende generatie. Door middel van de selectie operator worden reeds bekomen examenroosters uit de populatie geselecteerd aan de hand van hun fitness waarde. Vaak wordt gebruik gemaakt van ´e´en van volgende selectie operatoren. Enerzijds is er de Roulette Wheel selectie operator ([40]). Op basis van de grootte van de fitness waarde worden oplossingen geplaatst op een rad. Een hogere fitness waarde resulteert in een hogere kans om geselecteerd te worden als ’ouder’. Twee ’ouders’ worden vervolgens geselecteerd door het draaien van het rad. Een andere selectie operator is de Tournament selectie operator ([52]). Bij deze eerder eenvoudige methode strijden twee of meer examenroosters tegen elkaar. De beste oplossing, i.e. het individu met de hoogste fitness waarde wordt geselecteerd. Dit proces wordt meermaals herhaald tot er voldoende ouders geselecteerd zijn. De geselecteerde ouder-oplossingen zullen vervolgens gecombineerd worden, door toepassing van
6.2 Evolutionaire Algoritmes
59
de crossover operator, om zo een nieuwe generatie voort te brengen. Het genetische materiaal in deze chromosomen zal met andere woorden gecombineerd worden zodat nieuwe examenroosters of ’kinderen’ zullen ontstaan. De derde en laatste operator, de mutatie operator, brengt een verandering te weeg in bepaalde allelische waarden, i.e. de waarden van de variabelen. Specifiek voor het examen scheduling probleem betekent dit dat een bepaald examen in een andere tijdsperiode wordt gepland of dat er een swap plaats vindt tussen verschillende examens. De mutatie operator is verantwoordelijk voor het introduceren van diversiteit in de populatie zodat men niet dreigt vast te zitten in lokale optima. De mutatie operator heeft slechts een beperkte waarschijnlijkheid en wordt niet op alle bekomen examenroosters (gegenereerd na toepassing van crossover operatoren) toegepast. Het genetisch algoritme wordt stopgezet wanneer een bepaalde stopconditie is bereikt. Voorbeelden van dergelijke stopcondities zijn onder meer een maximum aantal geproduceerde generaties of een aanvaarbaar niveau van de fitness value. Volgens [14] presteren de genetische algoritmes in mindere mate in vergelijking met Tabu Search en Simultated Annealing. De genetische algoritmes worden daarom ook vaak gebruikt in hybridisatie met andere technieken bijvoorbeeld in de memetische algoritmes. De effectiviteit verbonden aan het combineren van genetische algoritmes met andere technieken is reeds bewezen ([63]). Verder vragen de genetische algoritmes heel wat inspanningen op computationeel gebied en het is niet altijd even gemakkelijk een gepaste codering te vinden voor elke oplossing. Dit alles weegt evenwel niet op tegen het feit dat genetische algoritmes flexibele algoritmes zijn die toepasbaar zijn op een groot aantal praktische problemen (e.g. M achine Learning, Game P laying, Bin P acking P roblems, T ravelling Salesman P roblem,). Ze zijn sterk in het vinden van goede globale oplossingen maar blijken inefficient in het vinden van het absolute optimum. Voorbeeld Aan de hand van volgend voorbeeld wordt getracht de werking van het genetisch algoritme, toegepast op het examen scheduling probleem, te verduidelijken. In dit voorbeeld wordt er van uit gegaan dat de populatie reeds bestaat uit N examenroosters en dat volgende roosters reeds gekozen zijn op basis van hun fitness value. De door de selectie operator gekozen examenroosters, verschaffen beiden een rooster waarin 9 examens (Project, SCM, ICT, SW Eng, FGO, Mktg nt, AOR, Trans Eco en Inn Mgmt) gepland werden binnen een tijdsperiode van 5 dagen waarin
6.2 Evolutionaire Algoritmes
Figuur 6.1: F low Chart voor het Genetisch Algoritme
60
6.2 Evolutionaire Algoritmes
61
Figuur 6.2: Matrix P1 en P2
telkens 3 examensessies mogelijk zijn. De te plannen examens krijgen een numerieke waarde toegewezen die ´e´enduidig zal verwijzen naar het desbetreffende examen. Bovendien wordt verondersteld dat alle examens studenten gemeenschappelijk hebben. Dit betekent dat elk examen in een aparte examensessie gepland zal worden om te voldoen aan de hard constraint die zegt dat examens die studenten gemeenschappelijk hebben niet op hetzelfde moment gepland mogen worden. Tabel 6.11: Toekennen van een numerieke waarde aan de te plannen examens Examen
Numerieke waarde
SCM
1
ICT
2
Project
3
SW Eng
4
FGO
5
Mktg nt
6
AOR
7
Trans Eco
8
Inn Mgmt
9
De toekenning van numerieke waarde zal vervolgens gebruikt worden om de bekomen examenroosters voor te stellen door middel van een code. De examendagen worden van elkaar onderscheiden door een asterix (*) en lege examensessies worden ingevuld met een D (Default). De, door de selectie-operator geselecteerde, examenroosters (P1 en P2) worden weergeven in figuur 6.2. Elk examen komt exact ´e´en maal voor in elk geselecteerd rooster wat betekent dat ook aan vergelijking 2.2 voldaan is. Nu beide examenroosters omgevormd zijn tot een string van numerieke waarden kan een
6.2 Evolutionaire Algoritmes
62
Figuur 6.3: Matrix O1 en O2
Figuur 6.4: Matrix O1 en O2 na toepassing van crossover
volgende operator toegepast worden, namelijk de crossover operator. Deze operator laat toe, zoals reeds vermeld in de inleiding, om het genetisch materiaal van beide ’ouder’-oplossingen te combineren om op deze manier een nieuwe generatie van examenroosters tot stand te brengen. In dit voorbeeld wordt gebruik gemaakt van de partially mapped crossover -operator ([53]). Deze operator wordt toegepast door het willekeurig kiezen van twee cut off -punten. In dit voorbeeld wordt het eerste cut off -punt geplaatst net voor de start van de derde examendag. Het tweede cut off -punt wordt geplaatst na de tweede examensessie van de vierde examendag. Vervolgens worden de geplande examens in beide originele examenroosters tussen deze twee punten gewisseld. Dit leidt tot het ontstaan van twee ’kind’-oplossingen (O1 en O2) (figuur 6.3). Uit bovenstaande representatie van de twee ’kind’-oplossingen blijkt dat de bekomen examenroosters van de nieuwe generatie (nog) niet feasible zijn. In zowel O1 als O2 is duidelijk dat niet alle examens ´e´en maal voorkomen, terwijl andere meerdere keren gepland zijn in het examenrooster. Om tegemoet te komen aan dit probleem en om alle duplicaties te verwijderen, maakt de partially mapped crossover -operator gebruik van een crossover map. Deze wordt opgesteld door alle examens tussen de cut off -punten voor ´e´en examenrooster ´e´en per ´e´en te vergelijken met alle examens tussen de cut off -punten voor het andere examenrooster. De crossover map voor bovenstaand probleem wordt weergegeven in tabel 6.12:
De bevindingen uit de crossover map worden toegepast op de elementen buiten de cut off punten. Dit leidt de examenroosters in figuur 6.5:
6.2 Evolutionaire Algoritmes
63
Tabel 6.12: Crossover map 6
<->
2
D
<->
9
8
<->
D
*
<->
*
3
<->
8
2
<->
3
Figuur 6.5: O1 na toepassing van mutatie operator
Deze examenroosters zijn beide mogelijk. Er moet evenwel opgemerkt worden dat dergelijke examenroosters niet echt rekening houden met de billijke spreiding van de examens voor de studenten. Tenslotte kan ook nog de mutatie-operator worden toegepast om de diversiteit in de populatie te behouden. Deze operator moet niet op alle examenroosters van de nieuwe generatie toegepast worden, maar slechts op een beperkt percentage van de populatie. In dit voorbeeld werd geopteerd voor de swap. Hierbij worden twee examens van plaats gewisseld. Toegepast op O1, waar examens Project naar de eerste examensessie van de vijfde en laatste examendag verplaatst werd, geeft dit het examenrooster bekomen in figuur 6.6. Uiteraard kunnen nog andere mutatie-operatoren toegepast worden. Een veel voorkomende operator is bijvoorbeeld de insert-operator waarbij een bepaald examen voor een ander examen gepland wordt. Een ander voorbeeld is de inversie-operator waarbij een bepaalde volgorde van examens ge¨ınverteerd wordt.
6.2.2
Ant Colony Algoritmes
De Ant Colony algoritmes vormen een vrij nieuwe benadering bij het oplossen van combinatorische problemen. In het begin van de jaren negentig werden zij voor het eerst toegepast op het T ravelling Salesman P roblem (TSP) door [36]. Dit werd in de literatuur ook wel Ant Systems (AS) genoemd. Later werden zij ook gebruikt bij het oplossen van andere combinatorische problemen
6.2 Evolutionaire Algoritmes
64
zoals job shop scheduling en quadratic assignment problemen. Ook in timetabling problemen hebben Ant Colony algoritmes zich in voorbij onderzoek zeer bruikbaar getoond. Dit algoritme is net zoals de genetische algoritmes gebaseerd op een proces uit de natuur waarbij mieren het kortste pad trachten te lokaliseren tussen een voedselbron en hun nest ([6],[46],[37]). De mieren kammen de omgeving uit op een willekeurige manier. Wanneer een mier op een mogelijke bron van voedsel botst, transporteert ze een deel ervan terug naar het nest, ondertussen een spoor achterlatend van feromonen. Deze chemische substantie maakt het mogelijk voor de andere mieren die zich bevinden in de omgeving van dit feromoonspoor om het voedsel te lokaliseren en te bereiken. Het gedrag van de mieren wordt nagebootst om zo een oplossing te bieden voor het examen scheduling probleem. Elke mier uit een populatie van m mieren genereert gedurende elke cyclus (in totaal zijn er n cyclussen), een mogelijke oplossing, i.e. een mogelijk examenrooster. [62] stelt dat elke mier de lijst van te plannen examens afloopt. Elk examen i dat een element is van I (de set van examens gedefinieerd in 2.2), wordt door een mier toegewezen aan een tijdsperiode t dat behoort tot T (de set van examenperiodes, 2.2). [62] vervolgt zijn uiteenzetting over het Ant Colony algoritme toegepast op het examen scheduling probleem door parti¨ele toewijzingen Ai , opgebouwd door een mier, te defini¨eren. Deze parti¨ele toewijzingen geven de allocatie weer van een aantal examens aan een aantal examenperiodes. Elke volgende parti¨ele allocatie wordt opgebouwd uit de vorige parti¨ele allocatie Ai−1 en een nieuw paar (examen,periode). De nieuwe periode t wordt gekozen uit T aan de hand van een waarschijnlijkheid die bepaald wordt door de feromoonmatrix (zie onder) en heuristieke informatie. De belangrijkheid van deze twee factoren wordt weergegeven door middel van gewichten α en β. Ook [46] geeft in zijn paper een uiteenzetting over hoe het Ant Colony algoritme een mogelijkheid biedt tot het oplossen van het examen scheduling probleem. Hij gebruikt hiervoor het Ant System algoritme (AS) en past bijgevolg dezelfde werkwijze toe als deze die gebruikt werd bij het oplossen van het TSP. Gedurende elke van de n cyclussen, stelt elke mier een mogelijk examenrooster op. Hiervoor maakt elk van de m mieren in het AS gebruik van twee strategie¨en. Een eerste strategie betreft de constructieve heuristiek waarbij aan de examens een bepaalde prioriteit wordt gegeven. Deze prioriteit bepaalt welke van de examens het eerst gepland moeten worden.
6.2 Evolutionaire Algoritmes
65
De tweede strategie heeft betrekking op het feromoonspoor. De oplossingen die de beste waarde genereren voor de doelfunctie zullen gekenmerkt worden door een hoger feromoongehalte en stellen dus betere oplossingen voor. De hoeveelheid feromonen die gegenereerd worden, worden verzameld in een matrix, i.e. de feromoonmatrix. Aangezien de mieren interageren met elkaar wordt deze matrix ge¨ updatet na elke cyclus. [46] suggereert in zijn paper ook een variant van het Ant System algoritme, namelijk het M ax − M in Ant System (MMAS) algoritme. MMAS verschilt van het eerder besproken Ant System algoritme omdat het bestaande informatie op een andere manier gaat gebruiken. De waarden voor het feromoongehalte wordt gelimiteerd tot het interval [MIN, MAX]. Onderzoek ([46]) wees uit dat de verschillen tussen sommige feromoonwaarden zo hoog waren, dat steeds dezelfde oplossing werd gegenereerd door alle mieren. Door het invoeren van deze minimum- en maximumwaarde wordt stagnatie verhinderd. Er wordt met andere woorden verhinderd dat alle mieren steeds het zelfde examenrooster zouden genereren. Ook [58] ondersteunen deze bevindingen. Verder wordt een update in de matrix die de feromoonwaarden bevat enkel veroorzaakt door de mier die het beste examenrooster geproduceerd heeft gedurende een cyclus. In tegenstelling tot het Ant System algoritme gebeurt hier dus enkel een globale update van de feromoonmatrix, terwijl in het Ant System algoritme de feromoonmatrix ook na elke constructieve stap wordt ge¨ updatet ([58]). [58] stellen verder dat het MMAS geen gebruik maakt van de heuristieke informatie, dit in tegenstelling tot het AS algoritme zoals reeds eerder vermeld werd. Tenslotte stelt [46] dat men een betere oplossing kan bekomen door hybridisatie met andere technieken, zoals bijvoorbeeld de lokale zoekalgoritmes. Gedurende de toepassing van de Ant Colony algoritmes op het examen scheduling probleem wordt de omgeving gebruikt als communicatiemiddel. Het is evenwel belangrijk op te merken dat het feromoonspoor verdampt na een bepaalde tijd. De verdamping van het feromoonspoor verhindert dat men convergeert naar een lokaal optimum en wordt weergegeven door de evaporation rate ρ. In het geval waarbij er helemaal geen verdamping van het feromoonspoor optreedt, zouden de routes gekozen door de eerste mieren als zeer aantrekkelijk beschouwd worden. De zoekomgeving zal zo slechts gedeeltelijk ge¨exploreerd worden. De kortste routes staan symbool voor de beste oplossingen aangezien hier het feromoonspoor het sterkst zal zijn. De motivatie voor het gebruik van dit algoritme voor het examen scheduling probleem, was de afwezigheid van een algemene oplossing die toegepast kan worden in verschillende universiteiten
6.2 Evolutionaire Algoritmes
66
Figuur 6.6: Construction Grafiek gebaseerd op ([55])
([6]). Met behulp van het Ant Colony algoritme tracht men tot een hogere generaliteit te komen. Volgens [46] is de gestegen interesse in dit algoritme voor het opstellen van examenroosters ook te wijten aan de grotere diversificatie van de zoekomgeving die men hierdoor bekomt. Dit algoritme laat immers toe om de zoekomgeving op een meer gediversifieerde manier te doorzoeken. voorbeeld Aangezien onderzoek ([55],[58]) heeft aangetoond dat het MMAS in bijna alle gevallen beter presteert dan het AS algortime, werd gekozen om het algoritme te illustreren aan de hand van het eerstgenoemde algoritme. Deze illustratie verschilt van vroegere voorbeelden aangezien hier eerder wordt getoond hoe praktisch van start te gaan met dit algoritme. Er wordt met andere woorden geen volledig specifiek probleem van begin tot eind ge¨ıllustreerd. Dit is hoofdzakelijk te wijten aan het complex karakter van dit algoritme aangezien naast de set van examens en set van examensessies ook rekening gehouden moet worden met de verschillende mieren die elk een examenrooster genereren. In deze paragraaf worden ook relevante waarden voor de verschillende parameters verschaft op basis van bevindingen uit de literatuur ([55],[58]). [55] stellen dat het Ant Colony algoritme het opstellen van een construction grafiek impliceert. Deze representatie bleek zeer bruikbaar aangezien elk pad doorheen deze grafiek een mogelijke oplossing voor het probleem voorstelt. Figuur 6.6 geeft de construction grafiek weer en is gebaseerd op [55]. Figuur 6.6 toont dat elke mier een lijst van events (e1 ,e2 ,...,en ), in dit geval examens, door-
6.2 Evolutionaire Algoritmes
67
loopt. Dit is in overeenstemming met [62]. Volgens [58] biedt een dergelijke representatie de mogelijkheid om examens te ordenen, bijvoorbeeld op basis van de moeilijkheidsgraad die gepaard gaat met het plannen van examens in het examenrooster. Veronderstel voor het voorbeeld dat een set van 9 examens (e1 ,e2 ,e3 ,e4 ,e5 ,e6 ,e7 ,e8 ,e9 ) gepland moet worden in een set van 10 examensessies (t1 ,t2 ,t3 ,t4 ,t5 ,t6 ,t7 ,t8 ,t9 ,t10 ). De construction grafiek begint met andere woorden met tien takken (want 10 examensessies). Vanuit elk van deze takken kunnen de 9 examens doorlopen worden. De examens stellen de knooppunten voor in de grafiek. Naar het voorbeeld van [62] en zoals reeds in de inleiding tot deze paragraaf werd gesteld, gebeurt de toewijzing van examens aan examensessie door middel van parti¨ele toewijzingen waaraan gedurende elke stap een paar (examen, examensessie) wordt toegevoegd. Een examensessie wordt op een willekeurige manier toegewezen. Naast het opbouwen van een construction grafiek, moet ook een feromoonmatrix geconstrueerd worden. Deze matrix heeft grootte (E x T) waarbij E staat voor het aantal examens en T voor het aantal examenperiodes. Wanneer alle mieren een examenrooster gegenereerd hebben wordt het examenrooster met de hoogste f itness value gekozen. Ook hier wordt de f itness value bepaald overeenkomstig de waarde van de doelfunctie. Deze waarde wordt berekend aan de hand van de kost die gepaard gaat met het niet naleven van de restricties. Op basis van het gekozen examenrooster wordt de feromoonmatrix aangepast. Dit is in tegenstelling tot het AS algoritme waarbij de feromoonmatrix wordt ge¨ updatet na elke parti¨ele toewijzing. Cruciaal in het MMAS algoritme is de bepaling van de maximale (τM AX ) en minimale (τM IN ) waarden die grenzen vormen aan de waarden die de feromonen kunnen aannemen. In tabel 6.13 wordt een overzicht verschaft van relevante waarden voor de verschillende parameters. Dit overzicht is gebaseerd op bevindingen van [58]. Het is evenwel belangrijk op te merken dat de genoemde waarden niet noodzakelijk de beste zijn. Maar de combinatie van deze waarden heeft zich zeer nuttig getoond. In tabel 6.13 staat m voor het aantal mieren dat een examenrooster cre¨eert. De waarden van de parameters verschillen over verschillende auteurs en over de verschillende vormen van het Ant Colony algoritme. Zo geven [62] en [63] een schatting voor de verschillende parameters. De evaporation rate ρ werd vastgelegd op 0,8. Voor α, die de belangrijkheid weergeeft van de informatie in de feromoonmatrix bleek 1 de meest relevante waarde. β, werd
6.3 Vergelijking van de verschillende metaheuristieken
68
Tabel 6.13: Relevante waarden voor de parameters in het MMAS algoritme (Socha et al.,2003) Parameter
Waarde
ρ
0.3
τM AX
3.3
τM IN
0.019
m
10
vastgesteld op 0,4. Deze waarden zijn relevant voor het AS algoritme.
6.3
Vergelijking van de verschillende metaheuristieken
In zijn paper maakt [62] een vergelijking van bovenstaande metaheuristieken (Tabu Search (TS), Simulated Annealing (SA), Genetische Algoritmes (GA) en Ant Colony Algoritmes (AC)). Een vergelijking van de bekomen waarden voor de doelfunctie lijken [62] niet relevant aangezien de stopcondities verschillen over de verschillende metaheuristieken. Hij is daarentegen wel voorstander van een dynamische vergelijking waarbij hij de waarden voor de objectieve functies onder de verschillende algoritmes plot ten opzichte van de benodigde computationele tijd. Hierdoor kunnen de volgende conclusies getrokken worden: 1. De beste oplossing over de verschillende tijden werd in 43,3% van de gevallen gegenereerd door AC, gevolgd door TS en GA (beiden in 26,6% van de gevallen) en tenslotte gevolgd door SA (slechts in 3,3% van de gevallen). 2. TS genereert, in vergelijking met de andere metaheuristieken, de grootste reductie in de waarde van haar doelfunctie. TS verwezenlijkt met andere woorden de hoogste kostreductie. 3. AC start het algoritme met betere initi¨ele oplossingen. Men maakt bij de bepaling hiervan namelijk gebruik van de heuristieke informatie die de initi¨ele oplossing construeert. Dit is in tegenstelling tot TS, SA en GA. Hierbij wordt de initi¨ele oplossing volledig willekeurig bepaald. [63] bestudeert de hybridisatie van TS en AC. De resultaten toonden dat deze gehybridiseerde algoritmes beter presteerden in vergelijking met de niet gehybriseerde TS, AC, SA en GA. De beste resultaten werden behaald door de sequenti¨ele AC gevolgd door TS.
MEMETISCHE ALGORITMES
69
Hoofdstuk 7
Memetische Algoritmes 7.1
Inleiding
Een vijfde categorie van algoritmes omvat de memetische algoritmes. De memetische algoritmes kunnen gezien worden als een bruikbaar alternatief voor de genetische algoritmes aangezien zij vaak een combinatie voorstellen van evolutionaire algoritmes en lokale zoekalgoritmes. Door de hybridisatie tussen een evolutionair en lokaal zoekalgoritme is men in staat om nog betere resultaten te bekomen en een nog kwaliteitsvoller examenrooster op te stellen ([25]). Deze categorie van algoritmes werd voor het eerst voorgesteld door [60]. Centraal staan memes ([39]). Volgens [25] is een meme een unit van informatie en verschilt een meme van een gene doordat een meme aangepast wordt door een individu uit de populatie. Dit is in tegenstelling tot een gene, die onaangepast blijft tijdens de uitwisseling ervan tussen twee individuen en niet kan veranderd worden door ´e´en van deze individuen. [56] zien memes als strategie¨en die chromosomen (examenroosters in het exam scheduling probleem) gebruiken om zichzelf te verbeteren. Verder geven [25] een beschrijving van de werkwijze van de memetische algoritmes specifiek voor het examen scheduling probleem. Deze uiteenzetting bleek een waardevolle aanvulling voor deze thesis en zal dan ook gevolgd worden. [25] beginnen hun uiteenzetting met het bepalen van de initi¨ele populatie. Naar analogie met de genetische algoritmes wordt elk mogelijk examenrooster voorgesteld als een individu of chromosoom in de populatie. Elk individu is een combinatie van een aantal memes die relevante informatie bevatten. Zo stelt elke meme namelijk een periode voor met de daarin geplande
7.1 Inleiding
70
examens. Er bestaat ook een meme die een lijst bevat van de nog niet-geplande examens. Om een initi¨ele populatie te bepalen, maken [25] gebruik van Roulette W heel selectie (cfr. genetische algoritmes). Nadat een initi¨ele populatie bepaald is, worden twee mutatie-operatoren toegepast namelijk de lichte en de zware mutatie-operatoren (light en heavy operatoren). De light mutatie-operator is verantwoordelijk voor de reallocatie van enkele examens. Examens worden op deze manier toegewezen aan een andere periode. De heavy mutatie-operator daarentegen is verantwoordelijk voor de reallocaties van bepaalde sets van examens. Er wordt met andere woorden een volledige periode gerealloceerd. Zo worden periodes die een goede samenhang vertonen toch volledig bewaard. Het gebruik van de hierboven besproken mutatie operatoren, wanneer dit niet in combinatie met een lokaal zoekalgoritme gebeurt, leidt niet tot een significante verbetering in de kwaliteit van het bekomen examenrooster. De combinatie met een lokaal zoekalgortime is bijgevolg noodzakelijk. De f low chart in figuur 7.1 illustreert de werking van de memetische algoritmes.
Figuur 7.1: F low Chart voor de memetische Algoritmes
7.2 Voor- en nadelen
71
Ook figuur 7.2 ([25]) illustreert hoe memetische algoritmes tot betere oplossingen leiden dan evolutionaire algoritmes. Hoewel het hier gaat om een maximalisatieprobleem, vat deze figuur de kern van de memetische algoritmes goed samen. Door toepassing van de mutatie-operator en de lokale zoekalgoritmes wordt een veel hogere waarde voor de doelfunctie bereikt dan dit origineel het geval was.
Figuur 7.2: Memetische Algoritmes [25]
7.2
Voor- en nadelen
Het voordeel van deze techniek ligt in het feit dat de zoekomgeving, die de verzameling van alle mogelijke oplossingen omvat, teruggebracht wordt tot een kleinere zoekomgeving, die een deel vormt van de oorspronkelijke zoekomgeving maar alleen de oplossingen bevat die lokale optima genereren. De combinatie van een evolutionair algoritme (bijv. een genetisch algoritme) met een lokaal zoekalgoritme zal uitmonden in een hogere benodigde computationele tijd om tot een oplossing te komen. Dit wordt echter volledig gecompenseerd door de reductie in de zoekomgeving, zoals hierboven reeds vermeld werd, en door de mogelijkheid om kwaliteitsvollere examenroosters op te stellen ([25]). Per generatie wordt met andere woorden meer bereikt dan wanneer het evolutionair algoritme alleen zou toegepast worden op het examen scheduling probleem. Men kan besluiten dat memetische algoritmes, door de combinatie van de domein-specifieke
7.3 Voorbeeld
72
Figuur 7.3: Matrix P1
lokale zoekalgoritmes en de evolutionaire algoritmes, de voordelen van beide algoritmes kan combineren ([27]). Lokale zoekalgoritmes laten toe om zeer snel aanvaardbare oplossingen te vinden. De metaheuristieken daarentegen zijn eerder intensive zoekstrategie¨en die tot een hogere graad van optimalisatie kunnen komen.
7.3
Voorbeeld
De werking van de memetische algortimes wordt ge¨ıllustreerd aan de hand van volgend voorbeeld. Door middel van dit voorbeeld wordt getracht de hogere performantie van memetische algoritmes, door de combinatie van metaheuristieken en lokale zoekalgoritmes, aan te tonen. Net als bij de genetische algoritmes (cfr. 6.1.1) worden individuele examenroosters voorgesteld als chromosomen. Deze chromosomen bestaan uit de mogelijke examensessies waaraan examens kunnen toegewezen worden. Veronderstel het examenrooster P1 (figuur 7.3). De numerieke waarden verwijzen naar de examens die gepland dienen te worden. Onderstaande representatie stelt het examenrooster voor als een chromosoom. De letter D (Default) verwijst naar een lege examensessies. Een asterix(∗) onderscheid de verschillende examendagen van elkaar. Tabel 7.1 geeft het examenrooster weer in een duidelijker format. Tabel 7.1: Examenrooster P1 Maandag
Dinsdag
Woensdag
Donderdag
Vrijdag
Project
-
SCM
Trans Eco
-
Mktg nt
FGO
Inn Mgmt
ICT
-
-
AOR
-
-
SW Eng
Bij dit examenrooster hoort een waarde van de doelfunctie. De conflictmatrix is een (9x9)-matrix (cfr. matrix 3.1). Verder wordt er uitgegaan van een logaritmische schaal zoals in voorgaande voorbeelden.
7.3 Voorbeeld
73
De berekening van de kost die gepaard gaat met dit examenrooster wordt weergegeven in tabel 7.2. Tabel 7.2: Berekening van de doelfunctie voor P1 a.d.h.v. een logaritmische schaal Examens
cij
Logaritmische Schaal
# ingeschreven studenten
Kost
Project & Mktg nt
c36
ω(1) = 16
1
16
Project & FGO
c34
ω(4) = 2
1
2
Project & AOR
c37
ω(5) = 1
1
1
Mktg nt & FGO
c64
ω(3) = 4
0
0
Mktg nt & AOR
c67
ω(4) = 2
1
2
Mktg nt & SCM
c61
ω(5) = 1
0
0
FGO & AOR
c47
ω(1) = 16
0
0
FGO & SCM
c41
ω(2) = 8
1
8
FGO & Inn Mgmt
c49
ω(3) = 4
0
0
FGO & Trans Eco
c48
ω(5) = 1
0
0
AOR & SCM
c71
ω(1) = 16
0
0
AOR & Inn Mgmt
c79
ω(2) = 8
0
0
AOR & Trans Eco
c78
ω(4) = 2
1
2
AOR & ICT
c72
ω(5) = 1
0
0
SCM & Inn Mgmt
c19
ω(1) = 16
0
0
SCM & Trans Eco
c18
ω(3) = 4
0
0
SCM & ICT
c12
ω(4) = 2
2
4
Inn Mgmt & Trans Eco
c98
ω(2) = 8
0
0
Inn Mgmt & ICT
c92
ω(3) = 4
0
0
Trans Eco & ICT
c82
ω(1) = 16
0
0
Trans Eco & SW Eng
c85
ω(5) = 1
1
1
ICT & SW Eng
c25
ω(4) = 2
0
0
Sommatie van de waarden in de rechterkolom geeft een totaal van 36 voor dit examenrooster. Deze waarden zijn louter kosten verbonden aan de niet-billijke spreiding van de beschouwde examens over de examenperiode. De hard constraint die stelt dat examens die studenten gemeenschappelijk hebben niet op hetzelfde moment gepland mogen worden, is hier voldaan en leidt bijgevolg niet tot andere kosten.
7.3 Voorbeeld
74
Figuur 7.4: Matrix P2
In een volgende stap wordt, zoals beschreven in de f low chart (figuur 7.1) gebruik gemaakt van mutatie-operatoren, namelijk de light en de heavy operatoren. De light mutatie-operator impliceert kleine veranderingen die gemaakt worden aan het examenrooster. Een dergelijk voorbeeld van een kleine verandering aan het examenrooster zou kunnen bekomen worden door het verschuiven van examen ICT naar een examensessie later op de dag. Toepassing van de heavy operator zou kunnen betekenen dat twee examendagen, met de daarin geplande examens, van plaats gewisseld worden. Veronderstel voor dit voorbeeld dat de examens gepland op maandag en vrijdag van plaats verwisselen. Deze keuze is willekeurig en heeft een louter administratieve opzet. Het gebruik van de operatoren resulteert in een aangepast examenrooster zoals weergegeven in P2 en tabel 7.3. De waarde van de doelfunctie van dit examenrooster is 56. De berekening is volledig gelijkaardig aan tabel 7.2 maar wordt hier niet meer ge¨ıllustreerd. De waarde van de doelfunctie is hoger dan voor toepassing van de mutatie-operatoren. In een volgende stap wordt het lokaal zoekalgoritme Hill Climbing toegepast. Volgens [9] bestaat dit algoritme er in om de omgeving van het bestaande rooster te bestuderen en voor elk examen in het bestaand examenrooster het examen toe te wijzen aan een verschillende examensessie. Voor elk examenrooster dat behoort tot de omgeving van het originele rooster wordt de bijhorende doelfunctiewaarde berekend. Het examenrooster met de kleinste doelfunctiewaarde is bijgevolg het lokaal optimum. Deze werkwijze zal niet verder in detail ge¨ıllustreerd worden. Tabel 7.3: Examenrooster P2 Maandag
Dinsdag
Woensdag
Donderdag
Vrijdag
-
-
SCM
Trans Eco
Project
-
FGO
Inn Mgmt
-
Mktg nt
SW Eng
AOR
-
ICT
-
MULTI-OBJECTIEVE (EVOLUTIONAIRE) ALGORITMES
75
Hoofdstuk 8
Multi-objectieve (Evolutionaire) Algoritmes 8.1
Inleiding
De multi-objectieve technieken, ook wel multi-criteria technieken genoemd, vormen de volgende categorie van technieken die besproken wordt. In tegenstelling tot de in vorige hoofdstukken bestudeerde technieken (i.e. de single-objective technieken) gaat het hier, zoals de naam reeds zegt, om multi-objectieve combinatorische optimalisatietechnieken. Bij de single-objective technieken wordt het niet naleven van constraints bestraft in een doelfunctie waar de gewichten de zwaarte weergeven voor de overtreding op deze constraints. Deze gewogen som geeft de uiteindelijke kwaliteit weer van de bekomen examenroosters. Bij de multi-objectieve technieken worden de overtredingen van de restricties niet gezamenlijk geminimaliseerd. [23] stellen een vector van restricties voor in de plaats van de gewogen som om de kwaliteit van de bekomen oplossingen te meten. Zowel [48], als [35] bespreken een multi-objectief evolutionair algoritme (MOEA). [48] stellen dat in een MOEA elk objectief op een individuele manier wordt ge¨evalueerd. Verder maken de MOEA gebruik van een directe representatie van de individuen. Dit wil zeggen dat elke plaats in een chromosoom ´e´en examen voorstelt. De waarden die aangenomen kunnen worden, weerspiegelen de mogelijke periodes waarin dit examen gepland kan worden. Dit is in tegenstelling tot de single-objective benaderingen waar gebruik wordt gemaakt van een indirecte representatie ([48]). [35] baseren hun multi-objectieve aanpak van het examen scheduling probleem op een werk-
8.1 Inleiding
76
wijze ontwikkeld door [25], waarin wordt rekening gehouden met twee verschillende doelstellingen. De eerste doelstelling betreft de minimalisatie van het aantal conflicten. Men tracht hierbij te vermijden dat examens die studenten gemeenschappelijk hebben, gepland worden in opeenvolgende periodes. De tweede doelstelling handelt over het aantal beschikbare examenperiodes, m.a.w. over de lengte van het opgestelde examenrooster. De algemene consensus is dat de lengte van het examenrooster niet te lang mag zijn. De twee besproken doelstellingen zijn conflicterend. Een examenrooster zonder conflicten kan immers verkregen worden door het examenrooster te verlengen met een aantal periodes zodat alle examens gepland kunnen worden, de spreiding van de examens in acht genomen. Het verhogen van het aantal beschikbare examenperiodes vormt evenwel een inbreuk op de tweede doelstelling. Het is met andere woorden onmogelijk om de waarde van ´e´en van de objectieven te verbeteren zonder dat dit een verslechtering inhoudt van de andere objectieven. [25] stelden op basis van de twee geformuleerde doelstellingen twee verschillende kostenfuncties op die geminimaliseerd dienden te worden. Hierbij wordt het aantal beschikbare examenperiodes niet op voorhand vastgelegd. Dit is opnieuw in contrast met de single-objective benaderingen waar men gebruik maakt van een vooraf bepaald aantal beschikbare examenperiodes. De keuze voor een vooraf bepaalde lengte van het examenrooster wordt gestaafd aangezien universiteiten hierdoor op voorhand al een vrij goeie benadering hebben van hoe lang de volledige examenperiode zal duren. Volgens [35] leidt dit echter tot een niet-optimale benadering van het examen scheduling probleem vanuit een operationeel standpunt. Met de ontwikkeling van hun MOEA, trachten [35] een techniek te verschaffen voor het examen scheduling probleem waarbij goede examenroosters bekomen worden zonder de duur van de volledige examenperiode vooraf te bepalen. De lengte van de volledige examenperiode wordt immers aangepast gedurende het proces door gebruik te maken van chromosomen waarvan de lengte variabel is en het aantal periodes gemanipuleerd kan worden. Zoals bij de single-objective evolutionaire algoritmes wordt er bij de MOEA ook gebruik gemaakt van mutatie en crossover operatoren. De waarschijnlijkheid van de mutatie operator zal groter zijn voor de examens waarvoor er een groter aantal alternatieve periodes voor handen zijn ([48]). De mutatie operator vervult in wezen dezelfde functie voor zowel de single-objective als de multi-objectieve evolutionaire algoritmes. Door gebruik te maken van de mutatie operator
8.2 Prestatie van MOEA
77
wordt immers een groter gebied in de zoekomgeving onderzocht([48]). Voor de crossover operator suggereren [35] het gebruik van een day-exchange crossover . In tegenstelling tot de standaard crossover operatoren wordt hierbij wel rekening gehouden met de verbanden tussen examens. De day − exchange crossover laat immers toe dat bepaalde goede combinaties van genen uitgewisseld worden tussen verschillende individuen in de populatie ([35]). De oplossing van een MOEA wordt voorgesteld door een Pareto optimale set ([35]). Om tot een oplossing te komen, moeten er trade-offs gemaakt worden tussen de verschillende doelstellingen. Wil men een bepaalde doelstelling verbeteren, dan zal dit ten koste zijn van de andere objectieven. De verantwoordelijke voor het plannen van examenroosters zal met andere woorden uit de Pareto optimale set van oplossingen, een oplossing moeten kiezen. De gekozen oplossing weerspiegelt in welke mate het bekomen van een conflictloos examenrooster belangrijk is en hoeveel van de tweede doelstelling (een examenrooster met redelijke lengte) opgeofferd moet worden. De MOEA kunnen nog verder uitgebreid worden. Door hybridisatie met lokale zoekalgoritmes is het mogelijk om examenroosters te bekomen met een nog hogere kwaliteit (cfr. Memetische algoritmes). [35] gebruiken in dit opzicht twee lokale zoekalgoritmes, een micro-genetisch algoritme en een hill climber algoritme.
8.2
Prestatie van MOEA
De MOEA’s vormen een vrij recente aanpak tot het oplossen van het examen scheduling probleem. Desondanks verschaft het een bruikbare werkwijze die toelaat, door middel van een grotere generaliteit, feasible examenroosters te bekomen. Een voordeel van de MOEA’s is dat het geen informatie vereist betreffende de lengte van het uiteindelijk te bekomen examenrooster ([35]). Ook de gewichten voor de doelfunctie moeten niet meer bepaald worden en dit laat toe dat de verschillende doelstellingen op een effici¨ente manier geoptimaliseerd kunnen worden. Uit een vergelijking van de werking van MOEA’s met een aantal andere optimalisatietechnieken die [35] maakten, blijkt dat MOEA’s een vrij goede prestatie opleveren. Zoals reeds opgemerkt werd, wordt de prestatie van MOEA’s nog vergroot door gebruik te maken van lokale zoekalgoritmes.
8.3 Voorbeeld
8.3
78
Voorbeeld
In dit voorbeeld met betrekking tot de MOEA wordt getracht de verschillen met de single − objective algoritmes aan te tonen. Dit gebeurt op basis van [15]. Het doel van dit voorbeeld is om de MOEA te illustreren op een modelmatige manier. Er wordt gestart met het identificeren van de verschillende criteria. Zoals reeds gesteld in punt 8.1 wordt gebruik gemaakt van een vector van restricties: (C1 , C2 , C3 , C4 , C5 , C6 , C7 ). Voor dit voorbeeld werden 7 criteria als relevant beschouwd. Een overzicht wordt hieronder gegeven. • C1 : Aantal conflicten waarbij een student examens, die in opeenvolgende periodes gepland zijn op dezelfde dag, moet afleggen. • C2 : Aantal conflicten waarbij een student examens moet afleggen die gepland zijn op dezelfde dag. • C3 : Aantal conflicten waarbij examens gepland zijn op 2 opeenvolgende dagen. • C4 : Aantal conflicten waarbij een examen gepland in de laatste periode van een bepaalde examendag opgevolgd wordt door een examen in de eerste periode van de volgende dag. • C5 : Aantal conflicten waarbij een student een examen moet afleggen dat niet gepland is in de vereiste periode. • C6 : Aantal conflicten waarbij een student een examen moet afleggen dat niet gepland is onmiddellijk voor of na een ander vooraf gedefinieerd examen. • C7 : Aantal conflicten waarbij een student een examen moet afleggen dat niet gepland is voor of na een ander vooraf gedefinieerd examen. Getracht wordt om deze 7 criteria te minimaliseren. Zoals reeds eerder vermeld zijn de verschillende criteria conflicterend. Zo zal de minimalisatie van criterium 6 leiden tot een stijging van criterium 1, 2 en 3. Het doel bestaat er in een examenrooster te bekomen waarin een zo goed mogelijke trade-off gemaakt is tussen de verschillende criteria. Na het identificeren van de verschillende criteria worden gewichten toegekend. Deze gewichten zijn niet verwant aan de moeilijkheid die gepaard gaat met het voldoen aan deze criteria. Ze worden daarentegen wel bepaald door de universiteit en refereren naar de belangrijkheid die de universiteit hecht aan de criteria ([15]). In wat volgt wordt een model opgesteld voor de MOEA. Hierbij worden de notaties van uit [15]
8.3 Voorbeeld
79
behouden, evenals de vergelijkingen. De notaties en hun beschrijving worden samengevat in tabel 8.1. Tabel 8.1: Gebruikte notaties voor het MOEA Notatie
Beschrijving
N
Aantal examens
P
Aantal examenperiodes
K
Aantal Criteria
cij
Aantal studenten die zowel examen i als examen j afleggen
T
Examenrooster (nxp)-matrix
tnp
Binaire variabele die 1 is als examen n toegewezen wordt aan periode p
fk
Waarde van criterium k
ωk
Gewicht van criterium k
De te minimaliseren doelfunctie WF wordt samengevat in vergelijking 8.1. Vergelijking 8.2 en 8.3 geven de constraints weer.
WF = (ω1 f1 (T ), ..., ωk fk (T ))
(8.1)
Subject To:
X
tnp = 1
(8.2)
p∈P,p=1
X n
X
X
tnp tmp cij = 0
(8.3)
m=n+1 p=1
[15] defini¨eren verder een zoekomgeving waarvan de dimensie gelijk is aan het aantal criteria. Elk examenrooster kan op deze manier voorgesteld worden als een punt in deze omgeving. Het optimale examenrooster wordt voorgesteld door vergelijking 8.4. In deze vergelijking stelt fk∗ de beste waarde voor van criterium k.
I = (f1∗ , ..., fk∗ )
(8.4)
Zoals reeds eerder vermeld werd, omvat het optimaliseren van al deze criteria een onmogelijke taak. Daardoor zal getracht worden dit punt in de zoekomgeving zo goed mogelijk te benaderen.
8.3 Voorbeeld
80
Voor deze thesis werd bovenstaande uitleg voldoende geacht voor het modelleren van de MOEA en het aantonen van de verschillen met de single − objective algoritmes. [15] bouwen echter in hun paper voort op het bovenstaande en geven een gedetailleerde uitleg over het verder verloop van dit algoritme.
HYPERHEURISTIEKEN
81
Hoofdstuk 9
Hyperheuristieken 9.1
Inleiding
Hyperheuristieken vormen, net als de multi-objectieve technieken uit hoofdstuk 8, een vrij nieuwe benadering tot het oplossen van het examen scheduling probleem. Ze vormen een aanvulling op de hier eerder aan bod gekomen metaheuristieken (cfr. Hfdst 4). [23] stellen dat de metaheuristieken heel veel vooruitgang boekten in hun poging tot het oplossen van het examen scheduling probleem. Metaheuristieken stellen namelijk voor een bepaald probleem kwaliteitsvolle (eventueel zelfs optimale!) examenroosters op. Het nadeel echter van deze metaheuristieken is dat zij enkel toepasbaar zijn voor specifieke problemen. Ze zijn met andere woorden enkel in staat examenroosters op te stellen voor een specifieke universiteit. Wanneer een dergelijke metaheuristiek toegepast wordt op een andere probleemstelling, dringt een kostelijke en moeilijke taak zich op. Daarnaast gaat het gebruik van metaheuristieken ook gepaard met het bepalen van de benodigde parameters. Het ’finetunen’ van deze parameters vraagt heel wat tijd en moeite, volgens [23] zelfs meer dan het ontwikkelen van een compleet nieuw algoritme. De hyperheuristieken bieden in dit opzicht een nieuw perspectief tot het opstellen van kwaliteitsvolle examenroosters. Hyperheuristieken worden gekenmerkt door een grotere mate van generaliteit en zijn met andere woorden toepasbaar over verschillende universiteiten terwijl ze tezelfdertijd kwaliteitsvolle examenroosters produceren. Hyperheuristieken vereisen geen maatwerk wanneer ze toegepast worden op een nieuw probleem. Dit gebeurt evenwel ten nadele van de kwaliteit van de bekomen examenroosters, hoewel deze zeker nog binnen een aanvaardbaar bereik ligt ([18]). In tegenstelling tot wat alle andere besproken technieken beoogden, wordt hier geen gebruik
9.1 Inleiding
82
gemaakt van een zoekomgeving bestaande uit mogelijke oplossingen (i.e. mogelijke examenroosters), maar uit een zoekomgeving bestaande uit heuristieken of oplossingsmethodes ([23]). Zogenaamde high level heuristieken sporen de zoekomgeving van heuristieken af op zoek naar low level heuristieken die toegepast worden op de kandidaat-oplossing. Hyperheuristieken trachten kandidaat-oplossingen op een indirecte manier te veranderen door gebruik te maken van de low level heuristieken. Dit is niet het geval voor de probleemspecifieke metaheuristieken. Zij trachten de oplossingen op een directe manier te onderwerpen aan verbeteringen ([18]). [5] splitsen de werking van hyperheuristieken op in twee fases. De fases worden herhaald voor elke iteratie. De eerste fase omvat de selectie van een heuristiek uit de zoekomgeving. De meest geschikte heuristiek wordt geselecteerd en vervolgens toegepast op de kandidaat-oplossing. Vervolgens wordt de kwaliteit van het nieuw bekomen examenrooster beoordeeld. Een kernconcept aangaande de keuze van de heuristieken is het ’learning mechanism’ ([18],[61]). Dit mechanisme helpt de hyperheuristiek tijdens het selectieproces. De tweede fase bepaalt of de verbetering die de kandidaat-oplossing ondergaan heeft, voldoende is en of de staat waarin de kandidaat-oplossing zich nu bevindt, geaccepteerd wordt. Het accepteren van een nieuwe staat van de kandidaat-oplossing wordt bepaald door de acceptatiestrategie. M oves die een verbetering van de doelfunctie impliceren worden onmiddellijk geaccepteerd. M oves die geen verbetering van de doelfunctie impliceren worden aanvaard zolang de bekomen doelfunctiewaarde lager (en dus beter) is dan een vooropgesteld niveau voor de doelfunctiewaarde. Dit vooropgesteld niveau wordt het treshold niveau genoemd en verandert bij elke iteratie. Net zoals bij de metaheuristieken, houdt dit algoritme op, wanneer een bepaalde stopconditie bereikt werd. Ook hier kan de stopconditie gaan van een bepaald aantal iteraties tot een vooraf bepaalde CPU-tijd enz. Eigenlijk moet elke hyperheuristiek gezien worden als een zwarte doos of ’black box’ ([18]). De enige vereiste input zijn de low level heuristieken en een manier om de kwaliteit van oplossingen te berekenen. De lezer wordt hier weer gewezen op het feit dat er geen vereiste is voor probleemspecifieke informatie. De gegenereerde output die ontstaat uit de zogenaamde zwarte doos zijn de oplossingen voor het probleem. In de literatuur zijn heel wat mogelijke hyperheuristieken beschikbaar, gaande van een Tabu Search hyperheursitiek ([18]) over de Monte Carlo hyperheuristiek ([3]) en een hyperheuristiek die gebruik maakt van een variabele zoekomgeving (i.e. de zoekomgeving verandert systematisch
9.2 Voor- en nadelen
83
bij elke iteratie) ([54]) tot technieken waarbij Case Based Reasoning ([23]) wordt toegepast als methode voor het selecteren van heuristieken uit de zoekomgeving.
9.2
Voor- en nadelen
De sterkte van deze categorie van heuristieken ligt in het feit dat hyperheuristieken in staat zijn een oplossing te bieden voor dit combinatorisch probleem zonder gebruik te maken van probleem-specifieke informatie. Zoals eerder aangehaald is het bepalen van de waarden voor de parameters niet vereist.
9.3
Voorbeeld
De uiteenzetting van [18] geeft een bruikbaar voorbeeld van de werking van hyperheuristieken en zal in wat volgt besproken worden. De paper beschrijft een Tabu Search hyperheuristiek. Er zal met andere woorden getracht worden, door het toepassen van het Tabu Search algoritme (cfr. 6.1.1), een selectie te maken van de onderling concurrerende low level heuristieken. Een voorbeeld van een dergelijke low level heuristiek is swap waarbij twee examens worden verwisseld van plaats. Elke heuristiek krijgt initieel een score toegekend van 0. Deze scores kunnen veranderen binnen een bepaald interval [rmin , rmax ] en kunnen zowel een stijging als een daling ondergaan. Dit gebeurt op basis van een evaluatie van het nieuwe examenrooster (i.e. na het toepassen van de welbepaalde low level heuristiek) ten opzichte van het voorgaande examenrooster. Wanneer dit resulteert in een verbetering, wordt de score van deze low level heuristiek verhoogt. Bij een verslechtering, daalt de score en wordt deze low level heuristiek ondergebracht in de Tabu list. De Tabu List bevat in tegenstelling tot de Tabu List van een zuiver Tabu Search algoritme, niet de oplossingen, maar wel de heuristieken die ’taboe’ zijn. Een ander verschil is dat deze Tabu List een variabele lengte heeft. Het algoritme wordt herhaald zolang de stopconditie niet bereikt is. Figuur 9.1 toont de werking van het hierboven beschreven algoritme. De f low chart is gebaseerd op de pseudocode in [18].
9.3 Voorbeeld
84
Figuur 9.1: F low Chart: Werking van de hyperheuristieken
DECOMPOSITIETECHNIEKEN EN CLUSTERING
85
Hoofdstuk 10
Decompositietechnieken en clustering 10.1
Inleiding
In dit laatste hoofdstuk van de literatuurstudie gaat de volledige aandacht naar decompositietechnieken. Decompositie betreft het opsplitsen van problemen in kleinere deelgroepen of subsets van problemen. Wat betreft het examen scheduling probleem wordt deze techniek hoofdzakelijk gebruikt voor instanties waar een groot aantal examens moet gepland worden en waar heel veel studenten bij betrokken zijn. Door de toepassing van decompositietechnieken worden deze grote problemen opgesplitst in kleinere problemen. Het opsplitsen in kleinere deelgroepen laat nog steeds toe om examenroosters te produceren met een hoge kwaliteit. Clustering wordt vaak gezien als een vorm van decompositie ([23]). Examens worden namelijk ondergebracht in conflictloze groepen of in groepen met een zo laag mogelijk conflict. [30] hebben het in hun paper ook over clustering en zien dit als een proces dat uit twee stappen bestaat. De eerste fase omvat het groeperen van examens in blokken. Het toewijzen van de examens aan deze blokken kan op verschillende manieren gebeuren en [30] geven een uitgebreid overzicht van een aantal mogelijkheden. Zo is het mogelijk om blokken op te stellen op basis van de grootte van de examens, i.e. de grootste examens worden als eerste toegewezen aan een bepaald blok ([33]). Een andere mogelijkheid is dat examens toegewezen worden aan een blok op basis van het aantal conflicten waarmee een bepaald examen geconfronteerd wordt ([57]). Dit geeft enkel een eerste indicatie van de mogelijkheden om examens toe te wijzen aan bepaald
10.2 Voor- en nadelen
86
blok. De tweede fase in de clusteringmethode van [30] heeft betrekking op de volgorde waarin de bekomen blokken van compatibele examens toegewezen worden aan periodes om een f easible examenrooster te bekomen. Hiervoor worden vaak sequenti¨ele technieken (cfr. Hfdst 3), zoals largest degree of saturation degree gebruikt. Hierbij worden de blokken die als moeilijkst te plannen gepercipieerd worden als eerste toegewezen aan bepaalde periodes. Bovenstaande kan de lezer doen besluiten dat clustering eigenlijk gezien kan worden als een hybridisatie van sequenti¨ele technieken en evolutionaire algoritmes. Men neemt een groep examens in beschouwing in plaats van een enkel examen ([24]).
10.2
Voor- en nadelen
Zoals reeds aangehaald, leidt decompositie tot kwaliteitsvolle examenroosters voor grote problemen binnen beperkte tijd ([24]). Dit is voor een groot deel te wijten aan het feit dat de zoekomgeving beperkt wordt tot een veel kleiner deel dan in de originele oplossingsmethode (i.e. zonder decompositie)([23]). [23] merkten op dat de decompositietechnieken minder aantrekkelijk zijn als oplossingsmethode voor het examen scheduling probleem en suggereren hiervoor twee mogelijke redenen. Enerzijds kan het zijn dat examens uit een bepaalde subset die in een vroegere fase gepland waren er voor zorgen dat examens uit de huidige subset in een latere fase niet meer gepland kunnen worden zodanig dat geen examenrooster opgebouwd kan worden dat aan alle restricties voldoet. [24] suggereren echter het gebruik van backtracking waardoor examens uit een bepaalde subset, hoewel ze eerder al toegewezen waren aan een bepaalde examenperiode, toch nog verplaatst kunnen worden. Anderzijds worden er vaak bepaalde soft constraints genegeerd door het gebruik van decompositie. [43] besluiten dat clustering een handige methode is die kleinere problemen in beschouwing neemt. Deze kleinere problemen zijn gemakkelijker op te lossen en te behandelen en leiden tot compactere roosters.
10.3 Voorbeeld
87
Figuur 10.1: Matrix X
10.3
Voorbeeld
Voor dit voorbeeld werd gebruik gemaakt van een andere probleemstelling. In tegenstelling tot veel van de voorgaande voorbeelden moet in dit voorbeeld een set van 20 examens gepland worden (e1 ,e2 ,...,e20 ). Dit aantal is opvallend hoger dan in voorgaande voorbeelden, aangezien decompostie en clustering net wordt toegepast wanneer een groot aantal events gealloceerd moet worden. Voor dit voorbeeld werd eveneens een conflictmatrix opgesteld. Dit wordt weergegeven in matrix X (figuur 10.1). Naar analogie met [30] wordt het probleem opgesplitst in 2 fases. In de eerste fase worden de examens onderverdeeld in clusters. Op deze manier is decompositie van het probleem mogelijk. In [30] worden de te plannen examens eerst en vooral geordend op basis van hun grootte, met andere woorden op basis van het aantal studenten. Voor de gegeven probleemstelling betekent dit dat de examens in volgende volgorde geordend worden: e4 ,e9 ,e14 ,e19 ,e5 ,e10 ,e15 ,e20 ,e2 ,e7 ,e12 ,e17 ,e3 ,e8 ,e13 ,e18 ,e1 ,e6 ,e11 ,e16 . Op basis van bovenstaande kunnen de examens nu onderverdeeld worden in blokken. Er wordt telkens gestart met de grootste examens. Uit de lijst van te plannen examens worden compatibele examens in eenzelfde blok ondergebracht. In wat volgt worden de clusters
10.3 Voorbeeld
88
ge¨ıdentificeerd. • CLUSTER 1: e4 ,e14 ,e1 • CLUSTER 2: e9 ,e2 ,e10 ,e17 • CLUSTER 3: e19 ,e15 • CLUSTER 4: e5 ,e20 • CLUSTER 5: e7 • CLUSTER 6: e12 ,e13 ,e18 • CLUSTER 7: e3 ,e8 • CLUSTER 8: e6 ,e16 • CLUSTER 9: e11 Het besproken allocatieprobleem wordt bijgevolg herleid tot een probleem waarbij 9 events toegewezen moeten worden aan de beschikbare examenperiodes. In de tweede fase worden de 9 clusters vervolgens gepland. Dit kan aan de hand van ´e´en van de, in de vorige hoofdstukken besproken, algoritmes. Dit zal evenwel hier niet in detail uitgelegd worden.
89
Deel III
Examen Scheduling in de praktijk
EXAMEN SCHEDULING IN DE PRAKTIJK
90
Hoofdstuk 11
Examen Scheduling in de praktijk 11.1
Inleiding
Na een grondig overzicht van alle beschikbare algoritmes die voor handen zijn in de literatuur met betrekking tot het examen scheduling probleem, breidt verder onderzoek zich uit naar de praktijk. Aan de hand van twee praktijkvoorbeelden wordt eerst en vooral nagegaan hoe de huidige examenplanning in haar werk gaat. Voor elk van de twee voorbeelden worden vragen beantwoord zoals: Hoeveel studenten zijn er ingeschreven? Hoeveel examens moeten gepland worden? Wat is de duur van een examenperiode? Wat zijn de hard en sof t constraints waarmee rekening gehouden moet worden? Wanneer wordt een bekomen examenrooster als goed (i.e. rekening houdend met de eisen van alle betrokken stakeholders) beschouwd? Wordt er gebruik gemaakt van bepaalde programma’s of algoritmes bij het opstellen van examenroosters, m.a.w. is er sprake van enige vorm van automatisering? Verder worden oplossingen aangebracht die trachten het examen scheduling probleem effici¨enter op te lossen rekening houdend met de in de literatuurstudie beschreven algoritmes. Dit hoofdstuk verloopt als volgt. In 11.2 wordt het eerste praktijkvoorbeeld beschreven. Het betreft de huidige examen scheduling op de Faculteit Economie en Bedrijfskunde van de Universiteit Gent (Belgi¨e). Het tweede praktijkvoorbeeld beschrijft de examen scheduling op de Faculty Economics and Management van de Universidade Nova de Lisboa (Portugal) (cfr 11.3). Vervolgens worden beide praktijkvoorbeelden ge¨ımplementeerd in C++. Zo wordt een automatische oplossing voor het examen scheduling probleem gesuggereerd. De prestatie van de bekomen examenroosters wordt ge¨evalueerd aan de hand van de bekomen doelfunctiewaarde en
11.2 Examenplanning aan de Faculteit Economie en Bedrijfskunde (Universiteit GENT, Belgi¨e) 91
de benodigde CPU-tijd. Hoewel het beschreven algoritme vrij eenvoudig is en dus bijgevolg niet met alle constraints, waarmee de verantwoordelijke voor het opstellen van examenroosters geconfronteerd wordt, rekening houdt, geeft het voorbeeld toch al een heel goed beeld over de complexiteit van het probleem en suggereert het een eerste aanpak tot het automatisch oplossen van het probleem. Tenslotte worden in 11.5 een aantal waardevolle besluiten getrokken tot het oplossen van het examen scheduling probleem.
11.2
Examenplanning aan de Faculteit Economie en Bedrijfskunde (Universiteit GENT, Belgi¨ e)
In wat volgt wordt de examenplanning aan de Faculteit Economie en Bedrijfskunde beschreven. Eerst wordt een duidelijk overzicht gegeven van de kenmerken van dit planningsprobleem. Zo wordt ondermeer de grootte van het probleem ge¨ıllustreerd, net zoals de duur van de examenperiode en het aantal te plannen examens per semester. Ook de constraints en objectieven, waarmee rekening gehouden moet worden, worden behandeld. Afhankelijk van het geobserveerde studiejaar en de studierichting varieert het aantal ingeschreven studenten van 6 (2e Master HIR: Marketing Management) tot 825 (1e Bach EW, TEW, HIR). Een overzicht van de ingeschreven studenten per jaar en per richting wordt weergegeven in appendix C. Enkel de normale studietrajecten worden beschouwd en Manama’s, schakeljaren en andere werden buiten beschouwing gelaten. De examenperiode aan de Faculteit Economie en Bedrijfkunde omvat een periode van 4 weken, hoewel uitzonderingen hierop mogelijk zijn indien wenselijk. Dit is bijvoorbeeld het geval voor de examenplanning voor de 1e Bachelor waarbij de examenperiode slechts een periode van 3 weken voorziet. Ook wat betreft de examenplanning van het tweede semester voor de 2e Bachelor Handelsingenieur wordt afgeweken van de voorgeschreven periode. Hier wordt vroeger gestart zodat de voorgeschreven examenperiode van 4 weken verlengd wordt, dit om een billijke spreiding tussen de examens te voorzien aangezien hier een groter aantal examens gepland dient te worden. Het opstellen van examenroosters is een activiteit die plaats vindt per semester. Afhankelijk van de gekozen studierichting en het studiejaar moeten examens gepland worden waarvan het aantal gaat van 4 tot 10 examens per semester. Wat betreft de Bachelor-jaren worden dezelfde examenroosters jaarlijks behouden. Dit is gezien het groot aantal ingeschreven studenten een verantwoorde keuze, hoewel het rooster
11.2 Examenplanning aan de Faculteit Economie en Bedrijfskunde (Universiteit GENT, Belgi¨e) 92
hoogstwaarschijnlijk slechts een benadering is tot een optimaal examenrooster. Het gebruik van vaste examenroosters kan beschouwd worden als toepassing van het Case-Based Reasoning (CBR)-principe, beschreven in de literatuurstudie (hfdst. 4), waarbij gesteund wordt op oplossingen van vorige examen scheduling problemen om tot een oplossing voor het huidige examen scheduling probleem te komen. In deze examenroosters is een billijke spreiding van de examens over de beschreven examenperiode gegarandeerd. Deze vaste examenroosters worden in appendix B weergegeven. Hoewel het gebruik van de vaste examenroosters het oplossen van het examen scheduling probleem vergemakkelijkt, wordt de verantwoordelijke voor het opstellen van deze examenroosters jaarlijks geconfronteerd met het toewijzen van deze examens aan lokalen met voldoende capaciteit. Door een steeds toenemend aantal studenten, wordt de verantwoordelijke voor het schedulen van examens geconfronteerd met een ander aspect van het examen scheduling probleem. Dit zal evenwel niet in detail besproken en onderzocht worden. Verdere motivatie voor het gebruik van de vaste examenroosters ligt in het feit dat zowel voor professoren als voor studenten het examenrooster reeds lang op voorhand vastligt, wat impliceert dat beide partijen voorbereid de examenperiode tegemoet kunnen gaan. Wat betreft de examenplanning voor de Master-jaren wordt een andere aanpak gebruikt. Elk jaar stelt de verantwoordelijke voor de examen scheduling een nieuw examenrooster op. De verantwoordelijke geeft een voorbeeldrooster door aan de professoren waarop aanpassingen mogelijk zijn indien de voorgestelde data niet overeenkomen met de desiderata van de betrokken lesgever. Aanvankelijk start het plannen van de examens met het toewijzen van de verplichte vakken. Aan de te plannen examens wordt met andere woorden een zekere prioriteit gegeven. Deze vakken worden zo ver mogelijk uit elkaar gepland in het examenrooster. Vervolgens worden de keuzevakken ingepland. Dit gebeurt in overleg met de studentenvertegenwoordigers zodat ook de belangen van de studenten opgenomen worden en voldoende tijd voorzien wordt voor het studeren van de leerstof. Aanpassingen worden doorgevoerd waar mogelijk. Het opstellen van examenroosters waarin voldoende spreiding tussen de examens voorzien is, kan aan deze faculteit beschouwd worden als een sof t constraint. Examenroosters waarin twee examens na elkaar (i.e. op twee opeenvolgende dagen) gepland worden, wordt zoveel mogelijk vermeden. Alleen met betrekking tot de keuzevakken kan dit voorvallen. Naast de sof t constraints worden uiteraard ook de hard constraints in acht genomen. Zo
11.2 Examenplanning aan de Faculteit Economie en Bedrijfskunde (Universiteit GENT, Belgi¨e) 93
komen alle examens exact ´e´en maal voor in het examenrooster. Daarnaast worden de examenroosters zodanig opgesteld dat overlappingen tussen bepaalde examens (i.e. de examens hebben studenten gemeenschappelijk) vermeden zijn. Na dit meer algemeen overzicht van hoe de examenplanning in zijn werk gaat aan deze faculteit wordt een specifiek examenrooster nauwkeuriger onderzocht. Het betreft het examenrooster voor het eerste semester van de tweede master Handelsingenieur. Hierbij worden vier verplichte vakken en eventueel nog keuzevakken gepland in de vooropgestelde examenperiode van vier weken. Zoals reeds vermeld krijgen de verplichte vakken prioriteit en worden zij eerst toegewezen aan het examenrooster. Tussen deze examens wordt een zo groot mogelijke spreiding voorzien. Voor deze examens zijn een totaal van 104 studenten ingeschreven (appendix C). Studenten kunnen de keuzevakken plannen op afspraak, waardoor een overlap vaak vermeden kan worden en waardoor de hard constraint die zegt dat studenten geen twee examens op hetzelfde moment kunnen afleggen, voldaan is. De te plannen examens worden gekenmerkt door een verschillende duur. Behalve het toekennen van prioriteiten aan verschillende examens (verplichte vakken versus keuzevakken), wordt verder geen gebruik gemaakt van ´e´en van de algoritmes beschreven in de literatuurstudie en is, volgens de verantwoordelijke, heel wat puzzelwerk vereist om aan de wensen van alle betrokken partijen zo goed mogelijk te voldoen. Hoewel de hierboven beschreven aanpak tot het examen scheduling probleem hoofdzakelijk berust op puzzelwerk werd aan de Universiteit Gent toch reeds een eerste stap gezet naar automatisering van dit probleem. Op basis van een nieuw programma, OASIS, wordt getracht een effici¨entere oplossing aan te brengen. Hoewel dit programma nog niet op punt staat, betekent dit toch een eerste stap naar automatisering van het examen scheduling probleem. OASIS streeft evenwel niet naar een volledige automatisering van het probleem. De opzet van OASIS is om een computer-ondersteunende roostering te verschaffen waarbij de verantwoordelijke voor het opstellen van de examenroosters zelf kan beslissen waar en wanneer een activiteit doorgaat. Bij het maken van deze beslissing wordt hij/zij ondersteund door software die aangeeft waar beschikbare tijdstippen en plaatsen zijn. Tot slot kan gesteld worden dat aan de Faculteit Economie en Bedrijfskunde van de UGent wordt getracht examenroosters op te stellen waarbij de wensen en belangen van alle betrokken partijen zoveel mogelijk ingewilligd zijn. Dit kan met andere woorden beschouwd worden als het voornaamste objectief.
11.3 Examenplanning aan de Faculty Economics and Management (Universidade Nova de Lisboa, Portugal) 94
11.3
Examenplanning aan de Faculty Economics and Management (Universidade Nova de Lisboa, Portugal)
Wat betreft de examen scheduling aan de Faculty Economics and Management van Universidade Nova de Lisboa werden volgende data verzameld. Het betreft informatie omtrent de examen scheduling voor de Masters (Finance, Management en Economics). In tegenstelling tot de Faculteit Economie en Bedrijfskunde aan de Universiteit Gent waar elke student per jaar een zelfde portfolio van vakken volgt (met uitzondering van de zelf te bepalen keuzevakken), kan elke student aan de Faculty Economics and Management jaarlijks zijn of haar eigen portfolio samenstellen op basis van het volledige aanbod van de te volgen vakken per richting. Uiteraard zijn er verplichte vakken die gevolgd moeten worden maar een student kan zelf kiezen of hij/zij deze zal volgen in het eerste of in het tweede masterjaar. Elke student kan op deze manier ook zelf kiezen hoeveel examens per semester af te leggen, hierbij wel rekening houdend met het feit dat de Master-opleiding minimum twee jaar moet duren. Wat betreft de examenperiode aan deze faculteit kan opgemerkt worden dat deze een veel kortere periode omvat. De examenperiode beschrijft slechts een maximum van 8 dagen waarin telkens vier examensessies mogelijk zijn die allen een duur hebben van anderhalf uur. Een andere tegenstelling met het eerste praktijkvoorbeeld betreft het feit dat examen scheduling per trimester gebeurt in plaats van per semester. Ook hier is het plannen van de examens niet gesteund op enige vorm van automatisering. Het opstellen van een f easible examenrooster start met het plannen van de verplichte vakken per richting. Deze worden zodanig gepland dat slechts ´e´en verplicht vak (per gekozen richting) per dag plaats vindt. Na het plannen van de verplichte vakken worden de keuzevakken gepland.Dit gebeurt op een zodanige manier dat ook hier de hard constraint die stelt dat een student geen twee verschillende examens kan afleggen op ´e´en examenmoment niet geschonden wordt. In tegenstelling tot het eerste praktijkvoorbeeld, wordt het in dit geval veel moeilijker om tot een mogelijk examenrooster te komen omwille van de uiteenlopende portfolio’s van verschillende studenten. Het plannen van de beschouwde examens op basis van de prioriteit kan gezien worden als een toepassing van een ordering strategie: de belangrijkste examens worden eerst ingepland. De sof t constraint waaraan men tracht te voldoen, is in dit geval dezelfde als in het eerste praktijkvoorbeeld. Men tracht de examens zoveel mogelijk te spreiden zodat studenten voldoende tijd krijgen om de te kennen leerstof te memoriseren. Deze spreiding gebeurt in dit geval
11.4 Implementatie in C++
95
uiteraard over een kleinere periode waarbij een billijke spreiding betekent dat geen enkele student twee examens op dezelfde dag (i.e. in twee opeenvolgende examensessies) moet afleggen. Hoewel het hierboven beschreven scenario wenselijk is, zijn schendingen tegen deze sof t constraint mogelijk. Dit resulteert, zoals beschreven in de probleemstelling, in een examenrooster met lagere kwaliteit. Aan de Faculty Economics and Management zijn, op het moment van onderzoek (academiejaar 2008-2009), 243 master studenten ingeschreven. Dit aantal, gecombineerd met de hierboven geformuleerde wijze van portfoliosamenstelling, toont dat de examen scheduling een complexe activiteit omvat waarbij enige vorm van automatisering zeker welkom kan zijn. Het voornaamste objectief voor deze case betreft het opstellen van een goed examenrooster waarbij alle examenroosters gepland kunnen worden binnen de vooropgestelde examenperiode. Hoewel getracht wordt de examens zo veel mogelijk te spreiden, is het geen uitzondering dat studenten twee examens op ´e´enzelfde examendag moeten afleggen. Eerder wordt er getracht om studenten geen examens te laten afleggen in twee op´e´envolgende periodes.
11.4
Implementatie in C++
In dit deel wordt de implementatie van de in 11.2 en 11.3 besproken case studies in C++ en de bekomen resultaten besproken. Met de toepassing van het C++ algoritme wordt getracht een eerste stap te zetten tot het automatisch oplossen van het examen scheduling probleem. Naast de implementatie van de case in Gent en de case in Lissabon werd ook een fictief voorbeeld ge¨ımplementeerd. De data voor elke probleemstelling zoals bijvoorbeeld het aantal te plannen examens of de problem size wordt voor elk van de probleemgevallen gegenereerd in tabel 11.1. Naast de specifieke data voor elke probleemstelling wordt ook de densiteit van de conflictmatrix weergegeven in tabel 11.1. Deze densiteit geeft de proportie weer van het aantal niet-lege en de niet-diagonale cellen in de conflictmatrix ([31]). Alle experimenten werden uitgevoerd op een Intel Core Duo processor met 2GB RAM geheugen. Het eigenlijk algoritme bestaat uit twee delen en is een illustratie van een zogenaamd Greedy Randomized Adaptive Search Procedure (GRASP) algoritme ([32]). Dit algoritme omvat enerzijds een construction heuristiek. Deze heuristiek is verantwoordelijk voor het genereren van een f easible examenrooster. Anderzijds wordt in een tweede deel van het algoritme een improvement heuristiek toegepast. Deze heuristiek is verantwoordelijk voor het optimaliseren
11.4 Implementatie in C++
96
Tabel 11.1: Data voor elke probleemstelling FEB-UGENT
UNL-LISBOA
FICTIEF VOORBEELD
Aantal te plannen examens
7
30
10
Duurtijd examenperiode (in dagen)
28
8
20
Aantal examensessies per dag
1
4
2
Aantal ingeschreven studenten
120
243
100
Densiteit van de conflictmatrix
0, 73
0, 89
0, 9
van het bekomen examenrooster. De opbouw van de construction heuristiek gebeurt naar analogie met hoofdstuk 3, waar gebruik werd gemaakt van de ordering strategie¨en. Voor deze implementatie werd gebruik gemaakt van de largest enrolment, de largest degree, de saturation degree en de random toewijzing van examens aan het examenrooster. De betekenis van elk van deze strategie¨en kan de lezer terug vinden in 3.1. Deze strategie¨en bepalen telkens op basis van een bepaalde stelregel welk examen vervolgens zal gepland worden. Het is belangrijk op te merken dat voor elke probleemstelling eerst een onderscheid wordt gemaakt tussen de verplichte vakken en de keuzevakken. Verplichte vakken worden gepercipieerd als zijnde belangrijker en moeten in elk van de probleeminstanties als eerste worden toegewezen aan het betreffende examenrooster. Vervolgens wordt binnen elke categorie (verplicht vak of keuze vak) de specifieke ordering strategie toegepast. Voor elk bekomen examenrooster wordt vervolgens de bijhorende doelfunctiewaarde berekend. Aangezien het hier een eenvoudig examen scheduling algoritme betreft, neemt de doelfunctiewaarde enkel en alleen de spreiding van de examens in beschouwing. Figuur 11.1 illustreert aan de hand van een f low chart, hoe de construction heuristiek opgebouwd is. Zoals in de literatuurstudie reeds werd ge¨ıllustreerd wordt ook hier, bij de berekening van de doelfunctiewaarde, gebruik gemaakt van een logaritmische schaal. Voor de volledigheid wordt deze logaritmische schaal nogmaals ge¨ıllustreerd in tabel 11.2. Naast de spreiding van de examens over de verschillende examensessies, wordt zoveel mogelijk getracht overige constraints te incorporeren in het examenrooster. Zo kan vermeden worden dat bepaalde examens toegewezen worden aan bepaalde examenperiodes door deze periode als inf easible aan te duiden in het tekstfile ’Examens’. Dit tekstfile geeft voor elk van de examens aan welke examenperiodes f easible of inf easible zijn.
11.4 Implementatie in C++
Figuur 11.1: F low Chart: Implementatie Construction Heuristiek
97
11.4 Implementatie in C++
98
Tabel 11.2: Logaritmische schaal Logaritmische schaal ω(1) = 16 ω(2) = 8 ω(3) = 4 ω(4) = 2 ω(5) = 1
Naast het tekstfile ’Examens’ dat als input dient voor deze heuristiek, zijn er nog andere inputs vereist. De tekstfiles ’Studenten’ en ’ExamenRooster’ geven respectievelijk weer aan welke examens elke student deelneemt en hoe het initieel (lege) examenrooster eruit ziet. De templates voor deze tekstfiles worden verschaft op de cd-rom, bijgevoegd bij appendix D. Ook kan worden nagegaan dat elk examen inderdaad toegewezen is aan exact ´e´en examensessie. Deze hard constraint is met andere woorden ook vervuld. Voor alle case studies wordt vermeden dat meerdere examens op hetzelfde moment gepland worden. Verder moet opgemerkt worden dat eveneens examens die geen enkele student gemeenschappelijk hebben toch op verschillende examenperiodes gepland worden. Men zou kunnen stellen dat dit een nadeel vormt van deze eenvoudige construction heuristiek. Met betrekking tot de constraints kan met andere woorden het volgende besloten worden. Hoofdzakelijk de spreiding tussen de geplande examens wordt in rekening gebracht in de doelfunctie. Aan andere constraints, zoals restrictie 2.2, is eveneens voldaan. Elk examen is immers exact ´e´en maal gepland in het examenrooster (tenzij het gaat om mondelinge examens). Ook vergelijking 2.3 is voldaan, geen enkel examen is immers gelijktijdig gepland met een ander examen. Voor de case studie betreffende de examen scheduling aan de Faculteit Economie en Bedrijfskunde van de Universiteit Gent, werd een bijkomend kenmerk van de examens ge¨ıncorporeerd in het algoritme. Er wordt namelijk een onderscheid gemaakt of de examens schriftelijk, al dan niet mondeling afgenomen worden. In het geval van mondelinge examens, wordt het aantal inschrijvingen voor dit vak in acht genomen. Is dit aantal groter dan een vooraf bepaald getal, bijvoorbeeld 100, dan wordt dit examen gesplitst over 4 dagen. Een lager aantal inschrijvingen betekent logischerwijze dat de studenten verdeeld worden over een kleiner aantal dagen. Studenten worden vervolgens toegewezen aan ´e´en van deze vier data. Een dergelijke spreiding van
11.4 Implementatie in C++
99
Figuur 11.2: Vergelijking doelfunctiewaarden bij toepassing van construction heuristiek studenten over een aantal examendagen verlicht de werklast voor de ondervrager. De bekomen doelwaarde, berekend voor elke probleemstelling volgens de verschillende toegepaste ordering strategie¨en in de construction heuristiek, wordt weergegeven in tabel 11.3. De examenroosters horende bij elke strategie worden weergeven op de bijgevoegde CD-rom. De doelfunctiewaarde bekomen door toepassing van de random ordering strategie stelt een gemiddelde doelfunctiewaarde voor over 25 iteraties. Een andere representatie van de bekomen doelfunctiewaarden voor elke case wordt ge¨ıllustreerd in figuur 11.2. Deze figuur toont de variatie in de doelfunctiewaarden over de verschillende ordering strategie¨en. Tabel 11.3: Bekomen doelfunctiewaarden volgens verschillende ordering strategie¨en na toepassing van de construction heuristiek FEB-UGENT
UNL-LISBOA
FICTIEF VOORBEELD
Zonder construction heuristiek
485
2664
-
Largest enrolment
2082
3346
4857
Saturation degree
3686
2863
4758
Largest degree
2082
3555
4867
Random
2504
3129
5139
Na analyse van tabel 11.3 en figuur 11.1 kunnen volgende conclusies getrokken worden. Zowel voor de case in Lissabon als de case in Gent genereert het examenrooster, bekomen zonder gebruik van de construction heuristiek, een lagere doelfunctiewaarde dan ´e´en van de andere gevallen. Hiervoor kunnen verschillende redenen aangehaald worden: • De examenroosters bekomen door toepassing van de construction heuristiek stellen slechts
11.4 Implementatie in C++
100
een initieel mogelijk examenrooster voor. Slechts in een tweede deel wordt getracht dit initieel examenrooster verder te optimaliseren. • De toepassing van deze construction heurisitek leunt, wanneer een vergelijking wordt gemaakt met de algoritmes in de literatuurstudie, het dichtst aan bij de graph − based sequenti¨ele technieken. Zoals reeds vermeld in hoofdstuk 3, wordt hierbij getracht de examens toe te wijzen aan een minimum aantal periodes. De spreiding van de examens over de volledige examenperiode wordt dus niet gerespecteerd. • Tenslotte kan gesteld worden dat sommige data niet beschikbaar waren bij de implementatie in C++. Deze onnauwkeurigheden kunnen eveneens de betere prestatie van de nietautomatische benadering tot dit probleem deels verklaren. Daardoor kan gesteld worden dat het fictieve voorbeeld leidt tot meer betrouwbare conclusies. Naast de vergelijking tussen de niet-automatische benadering en het gebruik van de construction heuristiek worden de verschillende ordering strategie¨en onderling vergeleken. Zowel voor het fictief voorbeeld als voor de case in Lissabon scoort de saturation degree strategie, waarbij examens worden toegewezen aan het examenrooster op basis van het aantal beschikbare tijdsperiodes, vrij goed. Dit is in overeenstemming met resultaten bekomen in voorgaande experimenten ([31]). Dit besluit gaat evenwel niet op voor de case in Gent. Hierbij valt de opvallend slechte prestatie van de saturation degree strategie op. De random ordering strategie zou, zoals beschreven in [31] de slechtste doelfunctiewaarde moeten opleveren. Deze strategie dient namelijk louter als benchmark en de andere strategie¨en zouden beter moeten presteren. Deze conclusie gaat op voor het fictief voorbeeld dat hier gebruikt werd. Het gaat echter niet op voor de twee praktijkvoorbeelden. Deze lagere waarden zijn enerzijds te wijten aan de redenen die reeds eerder werden aangehaald. Anderzijds moet rekening gehouden worden met het feit dat de waarden in tabel 11.3 slechts gemiddelde waarden zijn. In sommige van de iteraties werd dus inderdaad een slechtere waarde bekomen dan de waarden bekomen bij het toepassen van de andere ordering strategie¨en. Dit kan evenwel niet veralgemeend worden. In het tweede deel van het algoritme wordt getracht het bekomen examenrooster te verbeteren. Dit gebeurt aan de hand van Local Search-operatoren (LS) (i.e. lokale zoekoperatoren). Verschillende LS kunnen toegepast worden. Voor deze implementatie werd gekozen om de swap
11.4 Implementatie in C++
101
en de move LS toe te passen. Wanneer de swap wordt toegepast, worden twee examensessies van plaats verwisseld. Een move operator laat toe dat bepaalde examens verschuiven naar een andere examensessie in de examenperiode. Elk van deze operatoren wordt gedurende een aantal iteraties toegepast en het examenrooster dat de beste doelfunctiewaarde genereert, wordt onthouden. Zo wordt getracht een zo optimaal mogelijk examenrooster te bekomen. Tenslotte worden de twee genoemde LS-operatoren gecombineerd. Door deze combinatie wordt nog meer intelligentie ge¨ımplementeerd. Ook deze resultaten worden beschouwd. Tabellen 11.4, 11.5 en 11.6 vatten doelfunctiewaarden samen bekomen door toepassing van de construction heuristiek, de move operator, de swap operator en de combinatie van de LS operatoren voor respectievelijk het fictief voorbeeld, de case Lissabon en de case Gent. Tabel 11.4: Fictief Voorbeeld: Bekomen doelfunctiewaarden Construction Heuristiek
Move
Swap
Combinatie: Move en Swap
Largest enrolment
4857
1216
3703
1156
Saturation degree
4758
924
3622
881
Largest degree
4867
1140
3815
1114
Random
5139
1127
3754
1085
Tabel 11.5: Case Lissabon: Bekomen doelfunctiewaarden Construction Heuristiek
Move
Swap
Combinatie: Move en Swap
Largest enrolment
3364
2386
3159
2325
Saturation degree
2863
2672
2679
2581
Largest degree
3555
2972
3264
2958
Random
3129
2634
2551
2666
Tabellen 11.4, 11.5 en 11.6 tonen op een duidelijke manier hoe de doelfunctiewaarde in gunstige zin evolueert door het implementeren van meer intelligentie in het algoritme. Voor de drie cases genereert de combinatie van de LS operatoren (voor elke ordering strategie) de beste doelfunctiewaarde. Hierbij moet evenwel opgemerkt worden dat voor de drie cases deze beste doelfunctiewaarde niet onmiddellijk werd gegenereerd. Dit is te wijten aan het willekeurig kiezen
11.4 Implementatie in C++
102
Tabel 11.6: Case Gent: Bekomen doelfunctiewaarden Construction Heuristiek
Move
Swap
Combinatie: Move en Swap
Largest enrolment
2082
181
1254
181
Saturation degree
3686
307
1112
283
Largest degree
2082
181
1020
181
Random
2504
372
2742
447
Figuur 11.3: Vergelijking doelfunctiewaarden bij toepassing van M ove operator
van twee examensessies door de swap operator in het beste examenrooster voortgebracht door de move LS operator. Er werd evenwel steeds, binnen een aanvaardbaar aantal runs (15-25) van het algoritme, een verbetering in de doelfunctiewaarde gevonden. Wanneer de individuele prestaties van de LS operatoren vergeleken wordt, kan besloten worden dat de toepassing van de move operator in bijna alle gevallen een grotere substanti¨ele daling in de doelfunctie veroorzaakt. Bij toepassing van de move operator wordt gedurende 30 iteraties nagegaan welke examens de grootste contributie leveren tot de doelfunctiewaarde. Het examen dat de grootste contributie levert, is het slechts gepland en is een kandidaat voor het toepassen van de move operator. Wat betreft de waarden bekomen door middel van de swap operator in elke case moet opgemerkt worden dat deze waarden de beste waarden voorstellen, die bekomen werden na 15 runs (elke run doorloopt 30 iteraties). De toepassing van de swap operator zorgt eveneens voor een duidelijke verbetering van de doelfunctiewaarde. Naar analogie met figuur 11.2 illustreren figuren 11.3, 11.4 en 11.5 voor elk algoritme de variatie in doelfunctiewaardes. Naast de vergelijking van de doelfunctiewaarden wordt de effici¨entie van de algoritmes
11.4 Implementatie in C++
Figuur 11.4: Vergelijking doelfunctiewaarden na toepassing Swap operator
Figuur 11.5: Vergelijking doelfunctiewaarden na toepassen combinatie M ove en Swap operatoren
103
11.4 Implementatie in C++
104
(construction heuristiek en improvement heuristieken) bestudeerd aan de hand van de gebruikte CPU-tijd. De CPU-tijden worden voor elk van de drie cases verschaft in tabellen 11.7, 11.8 en 11.9. Deze CPU-tijden worden uitgedrukt in seconden en betreffen gemiddelde waarden over 25 iteraties van elk algoritme. Tabel 11.7: Fictief Voorbeeld: CPU-tijden(in sec) Construction Heuristiek
Move
Swap
Combinatie: Move en Swap
Largest enrolment
1.02
1.31
1.34
1.34
Saturation degree
1.09
1.19
1.17
1.35
Largest degree
1.05
1.31
1.12
1.32
Random
1.04
1.22
1.11
1.46
Tabel 11.8: Case Lissabon: CPU-tijden(in sec) Construction Heuristiek
Move
Swap
Combinatie: Move en Swap
Largest enrolment
0.99
1.23
1.21
1.47
Saturation degree
1.11
1.35
1.36
1.52
Largest degree
1.16
1.40
1.39
1.58
Random
1.08
1.37
1.26
1.53
Tabel 11.9: Case Gent: CPU-tijden(in sec) Construction Heuristiek
Move
Swap
Combinatie: Move en Swap
Largest enrolment
1.16
1.30
1.24
1.55
Saturation degree
0.98
1.20
1.26
1.53
Largest degree
1.21
1.25
1.32
1.36
Random
1.20
1.32
1.31
1.56
Het is duidelijk dat de CPU-tijd toeneemt naarmate meer intelligentie wordt toegevoegd aan het algoritme. Een hogere kwaliteit van de bekomen examenroosters (i.e. een lagere doelfunctiewaarde), gaat met andere woorden gepaard met een hogere benodigde tijd. Deze trade-off werd reeds eerder (cfr. Literatuurstudie) aangehaald, maar wordt nu, aan de hand van expe-
11.5 Besluit
105
Figuur 11.6: Fictief Voorbeeld: Verband tussen CPU-tijd en doelfunctiewaarde
Figuur 11.7: Case Lissabon: Verband tussen CPU-tijd en doelfunctiewaarde
rimenten, gestaafd. Figuren 11.6, 11.7 en 11.8 geven het negatief verband tussen CPU-tijd en doelfunctiewaarde weer voor respectievelijk het fictief voorbeeld, de case Lissabon en de case Gent.
11.5
Besluit
Bovenstaand onderzoek laat toe om een aantal waardevolle conclusies te trekken met betrekking tot het automatisch benaderen van het examen scheduling probleem. Eerst en vooral kan gesteld worden dat het opstellen van examenroosters in universiteiten een belangrijke activiteit betreft. Deze belangrijkheid werd zowel aangeduid in deel 2 als deel 3. Een automatische oplossing, zoals deze hierboven geschetst, zou bijgevolg zeer bruikbaar kunnen zijn. Binnen aanvaardbare tijdsperiodes worden immers betere roosters opgesteld, i.e. roosters met relatief hoge kwaliteit. Desondanks moet een automatische benadering toch aan een aantal vereisten voldoen. In dit
11.5 Besluit
106
Figuur 11.8: Case Gent: Verband tussen CPU-tijd en doelfunctiewaarde
opzicht stellen [17], dat de verantwoordelijken voor het opstellen van examenroosters veelal geen computer experten zijn. Het programma moet met andere woorden eenvoudig te gebruiken zijn zodat het weinig moeite vergt voor facultaire medewerkers om examenroosters op te stellen. Met betrekking tot het in 11.4 ge¨ımplementeerde programma kan gesteld worden dat het programma aan deze vereiste voldoet. Op een vrij eenvoudige manier wordt een facultaire medewerker immers in staat gesteld om een relatief kwalitatief examenrooster op te stellen binnen een beperkte tijd. Van de gebruiker wordt eveneens een minimum aan inputs vereist. Een tweede restrictie stelt dat het programma zo volledig mogelijk moet zijn. Deze restrictie is in dit geval niet voldaan. Zoals reeds eerder werd aangehaald betreft het examen scheduling probleem immers een allocatieprobleem waarbij enerzijds examens toegewezen worden aan een set van examenperiodes. Anderzijds moeten de examens gepland worden rekening houden met andere resources [46]. Voor het ge¨ımplementeerde algoritme werd dit tweede aspect verwaarloosd en lag de focus volledig op het toewijzen van examens aan de examenperiodes. Tenslotte bevat het programma geen backtracking-mogelijkheden. Ondanks de hierboven aangehaalde tekortkomingen, is het ge¨ımplementeerde algoritme een eerste stap tot het automatische oplossen van het examen scheduling probleem. Hoewel het programma nog maar slechts in haar kinderschoenen staat en het geen state − of − the − art oplossing betreft voor het examen scheduling probleem, toont het hoe op een eenvoudige wijze examenroosters tot stand gebracht kunnen worden.
CLASSIFICATIETABEL
107
Bijlage A
Classificatietabel Onderstaande tabel geeft een overzicht van de onderzochte literatuur en classificeert elke paper op basis van de behandelde algoritmes.
CLASSIFICATIETABEL
108
CLASSIFICATIETABEL
109
CLASSIFICATIETABEL
110
CLASSIFICATIETABEL
111
CLASSIFICATIETABEL
112
CLASSIFICATIETABEL
113
CLASSIFICATIETABEL
114
VASTE EXAMENROOSTERS (FEB, UNIVERSITEIT GENT)
Bijlage B
Vaste Examenroosters (FEB, Universiteit Gent)
115
VASTE EXAMENROOSTERS (FEB, UNIVERSITEIT GENT)
Figuur B.1: Examenrooster: 1e Bach, 2e Semester
Figuur B.2: 2e Bach Economische Wetenschappen: 2e Semester
116
VASTE EXAMENROOSTERS (FEB, UNIVERSITEIT GENT)
Figuur B.3: 2e Bach Toegepaste Economische Wetenschappen: 2e Semester
Figuur B.4: 3e Bach EW: 2e Semester
117
VASTE EXAMENROOSTERS (FEB, UNIVERSITEIT GENT)
Figuur B.5: 3e Bach TEW: 2e Semester
Figuur B.6: 3e Bach HIR: 2e Semester
118
PRAKTIJKVOORBEELD GENT: AANTAL INSCHRIJVINGEN PER RICHTING
Bijlage C
Praktijkvoorbeeld Gent: Aantal inschrijvingen per richting
119
PRAKTIJKVOORBEELD GENT: AANTAL INSCHRIJVINGEN PER RICHTING
Figuur C.1: Gent: Aantal Inschrijvingen per richting
120
IMPLEMENTATIE: CODE C++
121
Bijlage D
Implementatie: code C++ Bijgevoegde CD-rom bevat: • Code in C++ en tekstfiles voor elk van de drie cases (Fictief Voorbeeld, case Lissabon, case Gent). • Excel bestand met templates voor tekstfiles. • Excel-bestand voor elk van de drie cases met bekomen roosters door toepassing van de verschillende algoritmes en ordering strategie¨en.
BIBLIOGRAFIE
122
Bibliografie [1] S. Abdullah, S. Ahmadi, E.K. Burke, M. Dror and B. McCollum (2007). A tabu based large neighbourhood search methodology for the capacitated examination timetabling problem. Journal of Operational Research, 58:1494-1502, 2007. [2] H. Asmuni, E.K. Burke, J.M. Garibaldi and B. McCollum (2009). An investigation of fuzzy multiple heuristic orderings in the construction of university examination timetables. Computers and Operations Research, 36(4): 981-1001. [3] M. Ayob and G. Kendall (2003). A monte carlo hyper-heuristic to optimise component placement sequencing for multi head placement machine. Proceedings of the International Conference on Intelligent Technologies. InTech 2003, Chiang Mai, Thailand, 17-19 Dec, 132-141. [4] V.A. Bardadym (1996). Computer-aided school and university timetabling: The new wave. In: E.K. Burke and P. Ross (eds) (1996). Practice and Theory of Automated Timetabling: Selected Papers from the 1st International Conference. Springer Lecture Notes in Computer Science, vol. 1153. 22-45. [5] B. Bilgin, E.E. Korkmaz and E. Ozcan (2007). An experimental study on hyper-heuristics and exam timetabling. In: E.K. Burke and H. Rudova (eds) (2007). Practice and Theory of Automated Timetabling: Selected Papers from the 6th International Conference. Springer Lecture Notes in Computer Science, vol. 3867. 394-412. [6] C. Blum, M. Dorigo (2005). Ant colony optimization theory: a survey. Theoretical Computer Science, 344(2-3): 243-278. [7] P. Boizumault, Y. Delon and L. Peridy (1996). Constraint logic programming for examination timetabling. Journal of Logic Programming, 26(2): 217-233.
BIBLIOGRAFIE
123
[8] P. Boizumault, C. Gu´eret, N. Jussien and C. Prins (1996). Building university timetables using constraint logic programming. In: E.K. Burke and P. Ross (eds) (1996). Practice and Theory of Automated Timetabling: Selected Papers from the 1st International Conference. Springer Lecture Notes in Computer Science, vol. 1153. 130-145. [9] N. Boland, B.D. Hughes, L.T.G. Merlot and P.J. Stuckey (2003). A hybrid algorithm for the examination timetabling problem. In: E.K. Burke and P. De Causemaecker (eds) (2003). Practice and Theory of Automated Timetabling: Selected Papers from the 4th International Conference. Springer Lecture Notes in Computer Science, vol. 2740. 207-231. [10] J.P. Boufflet and S. N`egre (1996). Three methods to solve an examination timetabling problem. In: E.K. Burke and P. Ross (eds) (1996). Practice and Theory of Automated Timetabling: Selected Papers from the 1st International Conference. Springer Lecture Notes in Computer Science, vol. 1153. 327-344. [11] S.C. Brailsford, C.N. Potts and B.M. Smith (1999). Constraint satisfaction problems: Algorithms and applications. European Journal of Operational Research, 119: 557-581. [12] D. Brelaz (1979). New methods to color the vertices of a graph. Communication of the ACM, 22(4): 251-256. [13] E.K. Burke, Y. Bykov (2007). Solving exam timetabling problems with the flex-deluge algorithm. In: E.K. Burke and H. Rudova (eds) (2007). Practice and Theory of Automated Timetabling: Selected Papers from the 6th International Conference. Springer Lecture Notes in Computer Science, vol. 3867. 370-372. [14] E.K. Burke, Y. Bykov, J.P. Newall and S. Petrovic (2004). A time-predefined local search approach to exam timetabling problems. IIE Transactions, 36(6): 509-528. [15] E.K. Burke, Y. Bykov and S. Petrovic (2001). A multicriteria approach to examination timetabling. In: E.K. Burke and W. Erben (eds) (2001). Practice and Theory of Automated Timetabling: Selected Papers from the 3rd International Conference. Springer Lecture Notes in Computer Science, vol. 2079. 118-131. [16] E.K. Burke, A.J. Eckersley, B. McCollum, S. Petrovic and R. Qu (2004). Analysing similarity in examination timetabling. In: E.K. Burke and M. Trick (eds) (2004). Proceedings of The 5th International Conference on the Practice and Theory of Automated Timetabling. 18th-20th Aug, Pitssburgh, PA USA. 89-106.
BIBLIOGRAFIE
124
[17] E.K. Burke, D.G. Elliman, P.H. Ford and R.F. Weare. (1996). Examination timetabling in British universities: A survey. In: E.K. Burke and P. Ross (eds) (1996). Practice and Theory of Automated Timetabling: Selected Papers from the 1st International Conference. Springer Lecture Notes in Computer Science, vol. 1153. 76-90. [18] E.K. Burke, G. Kendall and E. Soubeiga (2003). A tabu-search hyper-heurisic for timetabling and rostering. Journal of Heuristics, 9: 451-470. [19] E.K. Burke, B. MacCarthy, S. Petrovic and R.Qu (2000). Structured cases in CBR- Reusing and adapting cases for timetabling problems. Knowledge-Based Systems, 13(2-3): 159-165. [20] E.K. Burke, B. McCollum, P. McMullan and A.Parkes (2008). Multi-objective aspects of the examination timetabling competition track. Accepted for presentation at the Practice and Theory of Automated Timetabling VII, 2008. [21] E.K. Burke, B. McCollum, P. McMullan and R. Qu (2006). Examination timetabling: a new formulation. In: E.K. Burke and H. Rudova (eds) (2007). Practice and Theory of Automated Timetabling: Selected Papers from the 6th International Conference. Springer Lecture Notes in Computer Science, vol. 3867. 373-375. [22] E.K. Burke, B.McCollum, A. Meisels, S. Petrovic and R. Qu (2007). A graph based hyperheuristic for exam timetabling problems. European Journal of Operational Research, 176: 177-192, 2007. [23] E.K. Burke, B. McCollum, L. Merlot, S.Y. Lee and R. Qu (2006). A survey of search methodologies and automated approaches for examination timetabling. Journal of Scheduling, 12(1): 55-89, 2009. [24] E.K. Burke and J.P. Newall (1999). A multi-stage evolutionary algorithm for the timetable problem. IEEE Transactions on Evolutionary Computation, 3(1): 63-74. [25] E.K. Burke, J.P. Newall and R.F. Weare (1996). A memetic algorithm for university exam timetabling. In: E.K. Burke and P. Ross (eds) (1996). Practice and Theory of Automated Timetabling: Selected Papers from the 1st International Conference. Springer Lecture Notes in Computer Science, vol. 1153. 241-250.
BIBLIOGRAFIE
125
[26] E.K. Burke, J.P. Newall and R.F. Weare (1998). Initialization strategies and diversity in evolutionary timetabling. Evolutionary computation, 6(1): 81-103. [27] E.K. Burke and S. Petrovic (2002). Recent research directions in automated timetabling. European Journal of Operational Research, 140(2): 266-280. [28] E.K. Burke, S. Petrovic and R. Qu (2006). Case-based heuristic selection for timetabling problems. Journal of Scheduling, 9: 99-113, 2006. [29] M.W. Carter (1986). A survey of practical applications of examination timetabling algorithms. Operations Research, 34(2): 193-202. [30] M.W. Carter and G. Laporte (1996). Recent developments in practical examination timetabling. In: E.K. Burke and P. Ross (eds) (1996). Practice and Theory of Automated Timetabling: Selected Papers from the 1st International Conference. Springer Lecture Notes in Computer Science, vol. 1153. 3-21. [31] M.W. Carter, G. Laporte and S.Y. Lee (1996). Examination timetabling: Algorithmic strategies and applications. Journal of Operational Research Society, 47(3): 373-383. [32] S. Casey and J. Thompson (2003). GRASPing the examination scheduling problem. In: E.K. Burke and P. De Caesemaecker (eds) (2003). Practice and Theory of Automated Timetabling: Selected Papers from the 4th International Conference. Springer Lecture Notes in Computer Science, vol. 2740. 232-244. [33] P.W. Chan and G.M. White (1979). Towards the Construction of Optimal Examination Timetables. INFOR 17: 219-229. [34] C. Cheng, L. Kang, N. Leung and G.M. White (1995). Investigations of a constraint logic programming approach to university timetabling. In: E.K. Burke and P. Ross (eds) (1996). Practice and Theory of Automated Timetabling: Selected Papers from the 1st International Conference. Springer Lecture Notes in Computer Science, vol. 1153. 112-129. [35] C.Y. Cheong, K.C. Tan and B. Veeravalli (2009). A multi-objective evolutionary algorithm for examination timetabling. Journal of Scheduling, 12:121-146,2009. [36] A.Colorni, M.Dorigo and V.Maniezzo (1991). Positive feedback as a search strategy. Technical Report n.91-016 Politecnico di Milano, 1991.
BIBLIOGRAFIE
126
[37] D. Costa and A. Hertz (1997). Ants can colour graphs. Journal of Operational Research Society, 48: 295-305. [38] A. Cumming, H. Luchian, M.G. Norman and B. Paechter (1996). Extensions to a memetic timetabling system. In: E.K. Burke and P. Ross (eds) (1996). Practice and Theory of Automated Timetabling: Selected Papers from the 1st International Conference. Springer Lecture Notes in Computer Science, vol. 1153. 251-256. [39] R. Dawkins (1982). The Extended Phenotype. Oxford University Press. [40] K.A. De Jong (1975). An analysis of the behavior of a class of genetic adaptive systems. Thesis. Computer and Communication Sciences Department, Langly Research Center Hampton, Virginia. [41] D. de Werra (1997). Restricted coloring models for timetabling. Discrete Mathematics, 165/166: 161-170. [42] L. Di Gaspero and A. Schaerf (2001). Tabu search techniques for examination timetabling. In: E.K. Burke and W. Erben (eds) (2001). Practice and Theory of Automated Timetabling: Selected Papers from the 3rd International Conference. Springer Lecture Notes in Computer Science, vol. 2079. 104-117. [43] M. Dimopoulou and P. Miliotis (2001). Implementation of a university course and examination timetabling system. European Journal of Operational Research, 130: 202-213. [44] K.A. Dowsland and J. Thompson (2005). Ant colony optimization for the examination scheduling problem. Journal of Operational Research Society, 56: 426-438. [45] G. Dueck (1993). New optimization heuristics: the great deluge and the record-to-record travel. Journal of Computational Physics, 104: 86-92. [46] M. Eley (2007). Ant algorithms for the exam timetabling problem. In: E.K. Burke and H. Rudova (eds) (2007). Practice and Theory of Automated Timetabling: Selected Papers from the 6th International Conference. Springer Lecture Notes in Computer Science, vol. 3867. 364-382. [47] A. Erg¨ ul (1996). GA-based examination timetabling scheduling experience at Middle East technical university. In: E.K. Burke and P. Ross (eds) (1996). Practice and Theory of
BIBLIOGRAFIE
127
Automated Timetabling: Selected Papers from the 1st International Conference. Springer Lecture Notes in Computer Science, vol. 1153. 212-226. [48] C.M. Fonseca and L. Paquete (2001). A study of examination timetabling with multiobjective evolutionary algorithm. Proceedings of the 4th Meta-heuristics International Conference. vol. 2. 149-154 [49] F. Glover (1989) Tabu Search-Part I. Orsa Journal on Computing, 3: 190 e.v. [50] F. Glover (1990) Tabu Search-Part I. Orsa Journal on Computing, 2: 4 e.v. [51] F. Glover and M. Laguna (1993). Tabu search. In: C.R. Reeves (ed.). Modern Heuristic Techniques for Combinatorial Problems. Oxford: Scientific Publications. [52] D.E. Goldberg (1990). A Note on Boltzmann Tournament Selection for Genetic Algorithms and Population-Oriented Simulated Annealing. Complex Systems, 4: 445-460. [53] D.E. Goldberg and R. Lingle (1985). Alleles, Loci, and the Traveling Salesman Problem. Proceedings of an International Conference on Genetic Algorithms and Their Applications (1985)154. [54] P. Hansen and N. Mladenovic (2001). Variable Neighbourhood search : Principles and Applications. European Journal of Operational Research, 130: 449-467. [55] J. Knowles, M. Sampels and K. Socha (2002). A MAX-MIN Ant System for the University Timetabling Problem. In: M. Dorigo, G. Di Caro and M. Sampels (eds.) (2002): Proceedings of ANTS 2002 Third International Workshop on Ant Algorithms. Lecture Notes in Computer Science, Springer Verlag, Berlin, Germany (2002). [56] N. Krasnogor and J.E. Smith (2005). A tutorial for competent memetic algorithms: model, taxonomy and design Issues. IEEE Transactions on Evolutionary Computation, 9:474-488. [57] Y.L. Leong and W.Y. Yeong (1990). A hierarchical decision support system for university examination scheduling. Working paper, National University of Singapore, Sept. 1990. [58] M. Manfrin, M. Sampels and K. Socha (2003). Ant algorithms for the university course timetabling problem with regard to the state-of-the-art. In: Raidl, G. et al. (Eds.), Proceedings of EvoCOP 2003 3rd European Workshop on Evolutionary Computation in Combinatorial Optimization, volume 2611 of LNCS. Springer-Verlag, Berlin, Germany, pp. 334345.
BIBLIOGRAFIE
128
[59] N.K. Mehta (1981). The application of a graph coloring method to an examination scheduling problem. Interfaces, 11: 57-64. [60] P. Moscato and M.G. Norman (1992). A memetic approach for the travelling salesman problem-implementation of a computational ecology for combinatorial optimization on message passing systems. In: Proceedings of the International Conference on Parallel Computing and Transputer Applications. IOS Press (Amsterdam), 177-186. [61] A. Nareyek (2004). AI in Computer Games. ACM Queue, 1(10): 58-65. [62] Z. Naji Azimi (2004). Comparison of metaheuristic algorithms for examination timetabling problem. Applied Mathematics and Computation, 16(1-2): 337-354. [63] Z. Naji Azimi (2005). Hybrid heuristics for examination timetabling problem. Applied Mathematics and Computation, 163(2): 705-733. [64] M. Pirlot (1996). General local search methods. European Journal of Operational Research, 92: 493-511. [65] M.B. Powell and D.J.A. Welsh (1967) The upper bound for the chromatic number of a graph and its application to the timetabling problems. The Computer Journal, 11: 41-47. [66] A. Schaerf (1999). A survey of automated timetabling. Artificial Intelligence Review, 13(2): 87-127. [67] A. Wren (1996). Scheduling, timetabling and rostering - A special relationship? In: E.K. Burke and P. Ross (eds) (1996). Practice and Theory of Automated Timetabling: Selected Papers from the 1st International Conference. Springer Lecture Notes in Computer Science, vol. 1153. 46-75.
