Ontwerp van een optimaal examenrooster

Ontwerp van een optimaal examenrooster Arnaud Deveugle

Promotor: prof. Pieter Vansteenwegen Begeleider: Derek Verleye Masterproef ingediend tot het behalen van de academische graad van Master in de ingenieurswetenschappen: bedrijfskundige systeemtechnieken en operationeel onderzoek

Vakgroep Technische Bedrijfsvoering Voorzitter: prof. dr. El-Houssaine Aghezzaf Faculteit Ingenieurswetenschappen en Architectuur Academiejaar 2011-2012

Ontwerp van een optimaal examenrooster Arnaud Deveugle

Promotor: prof. Pieter Vansteenwegen Begeleider: Derek Verleye Masterproef ingediend tot het behalen van de academische graad van Master in de ingenieurswetenschappen: bedrijfskundige systeemtechnieken en operationeel onderzoek

Vakgroep Technische Bedrijfsvoering Voorzitter: prof. dr. El-Houssaine Aghezzaf Faculteit Ingenieurswetenschappen en Architectuur Academiejaar 2011-2012

"De auteur geeft de toelating deze masterproef voor consultatie beschikbaar te stellen en delen van de masterproef te kopiëren voor persoonlijk gebruik. Elk ander gebruik valt onder de beperkingen van het auteursrecht, in het bijzonder met betrekking tot de verplichting de bron uitdrukkelijk te vermelden bij het aanhalen van resultaten uit deze masterproef." "The author gives permission to make this master dissertation available for consultation and to copy parts of this master dissertation for personal use. In the case of any other use, the limitations of the copyright have to be respected, in particular with regard to the obligation to state expressly the source when quoting results from this master dissertation."

4 juni 2012

Arnaud Deveugle

Voorwoord Het onderwerp van deze masterproef vormde een mooie aanvulling bij mijn opleiding als burgerlijk Ingenieur in Bedrijfskundige Systeemtechnieken en Operationeel Onderzoek. Deze masterproef gaf me de mogelijkheid om me te verdiepen in het programmeren van softwareprogramma’s en het opstellen van algoritmes. Dit zijn onderwerpen waar ik in eerste instantie slechts weinig mee vertrouwd was. Bij aanvang van deze masterproef wil ik enkele personen bedanken die hebben bijgedragen aan het tot stand komen van dit werk. Eerst en vooral zou ik graag mijn promotor Pieter Vansteenwegen willen bedanken voor het coördineren van deze masterproef. Zijn advies en bemerkingen hebben mij geholpen om deze masterproef te voltooien. Ook wil ik graag mijn begeleider Derek Verleye bedanken voor alle hulp en raad die hij mij geboden heeft tijdens het opstellen en afwerken van deze masterproef. Ook ben ik een woordje van dank verschuldigd aan Cédric Verbeeck, wiens computer ik tot meermaals toe mocht gebruiken om mijn model op uit te testen. Tot slot had ik nog Veerle Joliet van de facultaire studentenadministratie willen bedanken, om meermaals tijd te willen vrijmaken om te antwoorden op mijn vragen.

Overzicht Deze masterproef behandelt het opstellen van een examenplanning aan de faculteit Ingenieurswetenschappen en Architectuur aan de Universiteit van Gent. Het doel van deze masterproef is om de mogelijkheid tot automatisering van het opstellen van deze roosters te onderzoeken. De examenplanning zal rekening moeten houden met enkele restricties die eigen zijn aan de faculteit. Er zal eerst gezocht worden naar een wiskundig model dat in staat is om dit probleem op een exacte wijze op te lossen. Het zal echter blijken dat dit niet haalbaar is voor een grote dataset. Daarom zal er in een tweede fase gezocht worden naar een heuristische benadering. Er wordt uiteindelijk gekozen om het probleem aan te pakken met een two-phase algoritme. In een eerste fase zal er met behulp van een wiskundig model een feasible oplossing worden gezocht om deze dan in een tweede fase met en een variable neighbourhoud search heuristiek te optimaliseren. Het zal blijken dat deze aanpak zal resulteren in een goede oplossing.

Trefwoorden: -

Examination Timetabling Problem

-

Integer Programming

-

Variable Neighbourhood Search

Creating an ideal Examination Timetable Arnaud Deveugle Supervisor: Pieter Vansteenwegen Abstract: In this paper, two approaches for creating an examination schedule for the faculty of Engineering and Architecture at the University of Ghent, are investigated. The first approach uses only integer programming in order to create a schedule. Because this method only works on small datasets, a second approach is investigated. This second method uses a combination of integer programming and a variable neighbourhood heuristic, in order to find an optimal solution. It is demonstrated that this technique is able to produce quality solutions. Possible extensions to this overall approach are also discussed. Keywords: Examination Timetabling Problem, Integer Programming, Variable Neighbourhood Search

I. INTRODUCTION Until today, the scheduling of exams at the faculty of Engineering and Architecture (FEA) is a manual task. The scheduling happens three times a year: in January, June and September. It takes about three weeks to create one schedule for the entire faculty! Having a tool available that helps creating the examination schedules, could reduce the time needed in a drastically way. But because every university has its own restrictions and demands, there is no general tool available [1]. A. Examination rules at the FEA of the University of Ghent. There are several restrictions and demands that are the same for almost every examination timetabling problem. These restrictions are [2]: 1. A student can only have one examination at a time. 2. There is a limited number of timeslots. 3. There is a limited number of rooms of certain capacity in each timeslot. Because the faculty disposes of more than 100 rooms, the last constraint will be ignored in this paper. Besides the ‘standard’ restrictions, the faculty of Engineering and Architecture at the University of Ghent, like many other universities, also has its own restrictions, demands and properties. The first demand of this faculty states that every student should have an as good as possible examination timetable. The quality of the timetable is determined by the spread of the examinations because students should be able to have enough time to study for their next exam. Every course gets an amount of credits assigned. The more credits the course has, the more time a student needs to study for the exam of this course. This should also be taken into account when creating an examination timetabling. A second specific property of this faculty is that there is no one-to-one relation between courses and exams: it happens

A. Deveugle is with the Industrial Engineering Department, Ghent University (UGent), Gent, Belgium. E-mail: [email protected].

often that a student has to participate in more than one exam in order to pass for a course. The different exams for the same course can be an oral and written examination or a theory and exercise part. A further demand of the faculty states that a professor should be able to conduct exams in small groups of students. This implies that the entire group of students, who are taking the course, should be divided in smaller subgroups. However, when using preset groups when scheduling the exams, optimality for every student will be not guaranteed. That is why in this paper, the division of the students into groups will be defined as a variable and not as a fixed parameter. Unfortunately, this way a lot more extra variables are being introduced which will make the model a lot harder to solve. Because students can be divided in subgroups, there is an extra restriction that presents itself: it is not allowed to schedule an exam between two exams of the same course. A student should always finish all the exams of one course before he or she can undertake an exam of a new course. A last demand that is very specific to this faculty states that not only can a student only have maximum one exam in each timeslot, but he can only have maximum one exam (unless it’s an exam from the same course) each 24 hours. This implies that having exams from different courses in consecutive timeslots is not allowed. All the restrictions and demands create a very specific and complex timetabling problem that has not been researched yet.

B. Size of the problem at the FEA Since the introduction of the bachelor/master-structure at the University of Ghent, students are given a lot more freedom for creating their curriculum. This is mainly the case in the masters, where almost none of the students have the same curriculum. That is why, in this paper, only courses taught in the masters will be considered. Taking this into account, a dataset is created with 123 courses and 1182 students that need to be scheduled. All these students together have to take a total of 5261 exams. However, 757 out of these 1182 students still have to take one or several exams from courses taught in the bachelor. This should be taken into account when comparing the timetable created manually by the university and the timetable created with the methods explained later in this paper. C. Examination timetabling techniques The examination timetabling problem is a well studied topic across both Operational Research and Artificial Intelligence. The university timetabling problems are also considered to be NP- complete [3,4]. A lot of researchers that created an exact mathematical model and tried solving this

with integer programming techniques, came to the conclusion that the model only worked for small datasets, but is not capable in solving realistic datasets [5-7]. That is why the heuristic approach is a very popular approach for the timetabling problems. Meta-heuristic approaches have been particularly successful, including Tabu Search [8-10], Simulated Annealing [11,12] and Variable Neighbourhoods Search (VNS) [13,14]. Especially this last meta-heuristic, VNS, returned very good results. Another popular approach is using so called swarmalgorithms such as the Ant Colony Optimization algorithm [15] and Honey-bee Mating Optimization algorithm [16]. Besides the algorithms listed above, there are many others. Listing them all however, would bring us too far and falls out of the scope of this paper.

1. 2. 3. 4. 5. 6. 7.

8.

For every part, the student should be scheduled in exactly one of the part’s exams. When a student has an exam on timeslot t, y[e,t] should be equal to one. Every exam should be scheduled exactly one time. Every exam has a maximum number of students allowed. There can be scheduled only one exam per course in one timeslot. Every student can have maximum one exam in each timeslot. In between two examinations of the same course, a student should not undertake an exam of another course. Consecutive exams are not allowed unless they are exams from the same course.

II. INTEGER PROGRAMMING Before creating a mathematical model, a specific structure is introduced to the problem as can be seen in figure 1.

Course

Part

Exam Figure 1: Structure

First, there is the collection of courses: this collection contains all the courses that need to be scheduled. Beneath this collection, there is the collection of the parts. For instance, a part can be the oral part of an examination, the exercise part of the examination, etcetera. A course can have maximum two parts. The last collection is the collection of exams. When a part consists of multiple exams, a student should only be scheduled one of these exams. For instance, when an oral part of an examination takes place in several groups, a student should only be scheduled in one of these groups. Each group will be considered as a different exam. Every layer of this structure has its own properties. Because of the way this structure is formed, a property of a course applies to an exam but not vice versa. It will be possible to access the properties of an upper layer; this is shown in figure 1 by the arrows. Once this structure existed, it was time to introduce the variables. In total 3 variables were used: - x[s,e,t]: binary variable that equals one if students s has exam e scheduled in timeslot t. - y[e,t]: binary variable that equals one if exam e is scheduled in timeslot t. - slackvar[e1,e2,t,t]: variable that represents the amount of time there is short for a student, who has both exams e1 and e2, to study for exam e1. After the variables were created, the constraints could be modeled:

These are all the constraints for the mathematical model of the examination timetabling problem. The preference of timeslots of professors can be included by saying in constraint three that every exam should be scheduled exactly one time in the collection of possible timeslots for the accompanying professor. After having defined the variables and constraints, it is time to define the objective function. Each student has to be given a schedule were all his exams are spread evenly across the timetable. When a student does not have enough time to study for an exam, a punishment will be assigned to that student. However, the hardest part of modeling this problem is finding a linear way to write down the punishment. Because students are not assigned to exams before the exams are being scheduled, it is not possible to work with a conflict matrix. Researchers used this matrix to get around the non-linear character of a spread function [16, 17]. Linearizing the non-linear objective function resulted in a model that could solve even a small dataset because of the high-memory usage of the model. That is why there was chosen to work with slack variables that represent the amount of time two exams are scheduled too close in order to give a perfect spread for a student undertaking both exams. The objective function will minimize these slack variables in order to find the optimal solution. When applying this model to solve a small examination problem of 12 student and 9 courses, an optimal solution was give within three minutes on a computer with an Intel Core Quad Q9300 (2.5 GHz) processor and 4 GB RAM. In order to solve this sub problem, already 700 MB of memory was used. So when using this model to solve a real life problem, the required amount of memory would be enormous. Because solving the examination timetabling problem with integer programming was only applicable for small datasets, a new method had to be created.

III. VARIABLE NEIGHBOURHOOD SEARCH The constraints of this problem can be divided into two categories: hard constraints and soft constraints. Hard constraints are those which must be satisfied in order to have a feasible timetable solution. Soft constraints are less essential and violation of them is acceptable, although still undesirable [14].

The algorithm applied in this paper in order to solve the examination timetabling problem is a two-phase algorithm. In the first phase of a two-stage algorithm, a feasible solution is found. In the second phase of the algorithm, the solution found in the previous stage is being optimized. For the first phase, a mathematical model will be solved by integer programming in order to find a feasible solution. In the second phase, a Variable Neighbourhood Meta-heuristic was used to optimize the feasible solution. A. First Phase For the first stage the mathematical model discussed in the previous section will be used as a basis for our new model. To be able to find a feasible solution, the hard constraints have to be defined first. These are the hard constraints used in this model: 1. 2.

3. 4.

Every student can have maximum one exam in each timeslot. In between two examinations of the same course, a student should not undertake an exam of another course. There can be scheduled only one exam per course in one timeslot. Every exam should be scheduled exactly one time.

Notice that constraints 7 and 8 from previous section are not considered hard constraint but relaxable-hard constraints. A relaxable-hard constraint is a hard constraint that can be relaxed during the process, but ultimately has to be satisfied. The minimization of a slack variable is used again as objective function. Although this time the slack variable will have nothing to do with the spread of exams. Instead, the slack variable will be added to the first hard constraint, that way the following function was obtained: � 𝑥𝑠,𝑒,𝑡 − 𝑠𝑙𝑎𝑐𝑘𝑠,𝑡 ≤ 1

𝑒∈𝑒𝑥𝑠𝑠

∀𝑠, 𝑡

(1)

Formula (1) says that the summation over all possible exams student s can take, has to be smaller than one at every timeslot. When this is not the case a slack variable will be needed to satisfy this constraint. When minimizing the sum of the slack variables, the goal will be to find a solution equal to zero. That implies that no slack variable were necessary and that the hard constraint is met for every student at every timeslot. This model was solved on a computer with 8GB RAM and an Intel i5 2540 sandybridge processor. It took the model 50 minutes to find a solution for the big dataset discusses in section 1B of this paper. Having found a feasible solution, it is now time to improve this solution so that a good timetable is attained.

B. Second Phase As mentioned before, a VNS approach will be used to optimize the feasible solution. In order to evaluate the timetables, a score is needed. There are three types of scores. A first score will be equal to 50000 when a student has consecutive exams from a

different course planned. A second score will also be equal to 50000 when a student has to undertake an examination in between two exams from the same course. Note that these first two scores will try to make sure that relaxable-hard constraints are fulfilled. The last score will be a measure for the spread of the exams for a student. For every exam planned, the time difference with the previous planned exam will be measured. When this is more or equal to the optimal amount of time needed for this exam, the score will be equal to zero. If this is not the case the score will be calculated as follows: 5

(2𝐶𝑟𝑒𝑑𝑖𝑡𝑒 − 𝑗 + 1)2 (11 − 𝐶𝑟𝑒𝑑𝑖𝑡𝑒 )3

(2)

In the first term j equals the amount of timeslots in between two exams. When j is larger than two times the amount of credits the course of the exam has, the score will be calculated. The first term calculates the score of the spread of the exams. The second term of formula (2) simply makes sure that the score for exams with a high amount of credits isn’t many times bigger than the score for exams with a low amount of credits. So the function of the second term of the formula is to balance the score between exams with different amount of credits. The maximum amount of credits assigned to a course is 10, hence the 11 in the second term. Every number smaller than 11 would result in a score ≤ 0. The pseudo code for this heuristic can be found in figure 2.

- Initialisation: Select the set of neighbourhood structures Nk , k = 1,…,kmax ; find an initial solution x; choose stopping criteria. - Repeat until stopping criteria is satisfied: 1. Set k:=1; 2. Until k = kmax, repeat: a) Shaking: Generate a point x´∈ Nk(x) at random from the kth neighboorhood of x; b) Local Search: Apply a local search (a simple steepest descent) to x´, until a local optimum, x´´ is obtained; c) Move or not: if x´´ is better than the solution x then x→ x´´and continue the search with Nk; otherwise, set k=k+1; Figure 2: VNS pseudo code [14]

The local search within VNS uses a simple steepest descent approach: one exam will be randomly chosen from the timetable and will be placed in the slot that will give the best score. In a simple local search heuristic, the same neighbourhood is used in every iteration. Here the search continues using the current neighbourhood which yielded the improvement. When a neighbourhood fails to improve the solution, another neighbourhood will be used. In total six different neighbourhoods were used: 1. 2. 3. 4. 5. 6.

Swap two timeslots Swap two exams Move two timeslots Move three timeslots Move four timeslots Kempe chain neighbourhood

IV. RESULTS The initial feasible solution had score equal to 58868334. From ten runs, the best solution had a score of 694816 after 43737 iterations or 2 hours and 22 minutes. The examination timetable that was made manually had a final score of 1189982. We should note however that in this timetable, more than half of the students had to undertake exams from their bachelor and not only from their master. These exams are not taken into account in the solution generated by the VNS-heuristic, but they were taken into account when the university made the schedule. That’s why we could expect a worse solution for the manually scheduled timetable. Nevertheless is the solution given by the two-phase algorithm a high quality solution in which half of the students were assigned a perfect timetable. Only 3.5% of the students are assigned a bad schedule (>4000) points. However, a lot of these students have a heavy curriculum (up to 8 courses instead of the average of 4 courses). These students know that by taking up such a heavy semester, there is a big risk that their examination schedule will be bad.

ACKNOWLEDGEMENT I would like to thank my promoter Pieter Vansteenwegen and his assistant Derek Verleye for all the help and advice they have given me. REFERENCES [1]

[2]

[3] [4]

[5]

[6]

[7]

[8]

V. CONCLUSION AND FURTHER RESEARCH DIRECTIONS

[9]

One significant advantage of the basic variable neighbourhood search is that it involves very few parameters apart from the selection of neighbourhoods. Neighbourhoods can also easily being added or taken away [14]. Further improvements can be made by researching the possibility of combining the VNS heuristic with genetic algorithm. The possibility of adding preferences for professors can be investigated. However, even if the suggested VNS algorithm provides a very good solution, implementing this algorithm in the administrative system of the university will be really hard because of the non-user friendly database system for programmers. Before the dataset was ready to use, a lot of preprocessing was needed. Slight modifications in the database system will be needed in order to make efficient use of the algorithm. A good solution for the examination timetabling problem could exist in letting the students choose their own examination times out of several dates. If every professor gives at the beginning of the semester two to three possible dates to undertake their exam, students can then choose from these dates and compose their own optimal timetable. That way the demands of both the student as the professor are taken into account and there will be less work for the administration.

[10]

[11] [12]

[13]

[14]

[15]

[16]

[17]

K. Schimmelpfeng & S. Helber, Application of a real-world universitycourse timetabling model solved by integer programming, OR Spectrum, Volume 29, Nr 4, 2007, pp. 783-803 E.K. Burke et al., Hybrid variable neighbourhood approaches to university exam timetabling, European Journal of OR, Volume 206, Issue 1, 2010, pp. 46-53 D. deWerra, The Combinatorics of timetabling, European Journal of Operations Research, Volume 96, Issue 3, 1997, pp. 504-513 Rhydian Lewis, A Survey of metaheuristic-based techniques for University Timetabling Problems, OR Spectrum, Volume 30, Number 1, 2008, pp. 167-190 Convens Gerrie, Ontwikkelen van een methode voor studentvriendelijke examenplanning aan de Faculteit Ingenieurswetenschappen, Katholieke Universiteit Leuven, 2009 S. Daskalaki et al., An integer programming formulation for a case study in university timetabling, European Journal of OR, Volume 153, Issue 1, 2004, pp. 117-135 S. Daskalaki & T. Birbas, Efficient solutions for a university timetabling problem through integer programming, European Journal of OR, Volume 160, Issue 1, 2005, pp. 106-120 M. Gendreau & J-Y. Potvin, Tabu Search, Search Methodologies, 2005, pp. 165-186 H Arntzen & A. Løkketangen, A tabu search heuristic for a university timetabling problem, Metaheuristics: progress as real problem solvers, Volume 32, pp. 65-86 L. Di Gaspero & A. Schaerf, Tabu search techniques for examination timetabling, Lecture Notes in Computer Science, Volume 2079/2001, 2001, pp. 104-117 E. Aarts et al., Simulated annealing, Search Methodologies, 2005, pp. 187-210 J. M. Thompson & K. A. Dowsland, A robust simulated annealing based examination timetabling system, Computers & OR, Volume 25, Issues 7-8, 1998, pp. 637-648 E. Burke et al., Hybrid Variable Neighbourhood Approaches to University Exam Timetabling, Technical Report No. NOTTCS-TR2006-2, University of Nottingham, 2006 E.K. Burke et al., Hybrid variable neighbourhood approaches to university exam timetabling, European Journal of OR, Volume 206, Issue 1, 2010, pp. 46-53 K. Socha et al., Ant algorithms for the university course timetabling problem with regard to the state-of-the-art, Lecture Notes in Computer Science, Volume 2611/2003, 2003, pp. 334-345 N. R. Sabar et al., A Honey-bee mating optimization algorithm for educational timetabling problems, European Journal of OR, Volume 216, Issue 3, 2012, pp. 533-543 N. Pillay & W. Banzhaf, An informed genetic algorithm for the examination timetabling problem, Applied Soft Computing, Volume 10, Issue 2, 2010, pp. 457-467

Inhoudstafel HOOFDSTUK 1: INLEIDING ............................................................................................................. 1 1.1

PROBLEEMSTELLING ....................................................................................................................... 1

1.2

PROBLEEMGROOTTE ....................................................................................................................... 3

1.3

DOELSTELLING ............................................................................................................................... 3

HOOFDSTUK 2: LITERATUURSTUDIE .............................................................................................. 5 2.1 COMPLEXITEIT ....................................................................................................................................... 5 2.2 EXACTE OPLOSSINGSMETHODES .............................................................................................................. 6 2.2.1 Linear Programming (LP) .............................................................................................................. 6 2.2.2 Integer Programming (IP) ............................................................................................................. 7 2.2.3 Exacte opslossingsmethodes voor university timetabling problems in de literatuur .......................... 8 2.3 HEURISTISCHE OPLOSSINGSMETHODES ..................................................................................................... 9 2.3.1 Basis Metaheuristieken ............................................................................................................... 10 2.3.2 Honey-Bee Mating Optimization algorithm ................................................................................. 15 HOOFDSTUK 3: DATASETS ............................................................................................................ 17 HOOFDSTUK 4: EXACTE METHODE ...............................................................................................19 4.1 EERSTE WISKUNDIG MODEL ................................................................................................................... 19 4.1.1 Notatie ....................................................................................................................................... 20 4.1.2 Formulering ................................................................................................................................ 21 4.1.3 Uitvoeren model op een kleine dataset......................................................................................... 26 4.2 TWEEDE WISKUNDIG MODEL .................................................................................................................. 26 4.2.1 Notatie en constraints ................................................................................................................ 27 4.2.2 Doelfunctie ................................................................................................................................ 30 4.2.3 Model in OPL.............................................................................................................................. 32 4.2.4 Kleine Dataset ............................................................................................................................ 33 HOOFDSTUK 5: EEN HEURISTISCHE AANPAK ................................................................................39 5.1 EERSTE FASE: EEN FEASIBLE OPLOSSING OPSTELLEN.................................................................................. 39 5.1.1 Definiëren van het probleem........................................................................................................ 39 5.1.2 Notatie....................................................................................................................................... 41 5.1.3 Formulering ................................................................................................................................ 41 5.2 TWEEDE FASE: OPTIMALISEREN (THEORETISCHE ACHTERGROND) ................................................................. 42 5.2.1 Globale concept van VNS ............................................................................................................ 43 5.2.2 De neighbourhoods..................................................................................................................... 44 5.2.3 Local Search ............................................................................................................................... 45 5.3 TWEEDE FASE: OPTIMALISEREN (IMPLEMENTATIE) ..................................................................................... 46 5.3.1 De verschillende klasses .............................................................................................................. 46 5.3.2 De neighbourhoods ..................................................................................................................... 47

5.3.3 Local search ............................................................................................................................... 52 5.3.4 In- en uitlezen van gegevens ....................................................................................................... 53 HOOFDSTUK 6: TESTEN VAN HET ALGORITME ............................................................................. 54 6.1 DATASET ............................................................................................................................................ 54 6.2 EERSTE FASE ....................................................................................................................................... 55 6.3 TWEEDE FASE ...................................................................................................................................... 55 6.4 VERGELIJKING MET HET ROOSTER OPGESTELD DOOR DE FSA ...................................................................... 56 HOOFDSTUK 7: CONCLUSIE ..........................................................................................................59 REFERENTIES ................................................................................................................................61 BIJLAGE A: KLEINE DATASET ....................................................................................................... 64 BIJLAGE B: OPL MODEL (TOEGEPAST OP DE KLEINE DATASET) ................................................... 66 MOD-FILE ............................................................................................................................................... 66 DAT-FILE................................................................................................................................................. 70 BIJLAGE C: KLASSES ..................................................................................................................... 71 EXAMEN .................................................................................................................................................. 71 TIMESLOT ................................................................................................................................................ 72 PAIR ........................................................................................................................................................ 73 BIJLAGE D: NEIGHBOURHOODS .................................................................................................... 74 BIJLAGE E: LOCAL SEARCH............................................................................................................79 BIJLAGEN OP DIGITALE VERSIE .................................................................................................... 80

Afkortingen en symbolen LP

Linear Programming

IP

Integer Programming

FSA

Facultaire Studenten Administratie

VNS

Variable Neighbourhood Search

Hoofdstuk 1: Inleiding In dit hoofdstuk zal het probleem worden gesitueerd, zal er een korte uiteenzetting gegeven worden over de probleemgrootte en zal het doel van deze masterproef worden bepaald.

1.1

Probleemstelling

Tot enkele jaren geleden was het opstellen van examenroosters aan de faculteit Ingenieurswetenschappen en Architectuur nog behoorlijk eenvoudig. Studenten volgden modeltrajecten, wat inhield dat twee studenten in eenzelfde jaar dezelfde vakken volgden op eventueel enkele keuzevakken na. Hier kwam echter verandering in toen de Universiteit van Gent het internationale bachelor-mastersysteem invoerde. Dit bracht met zich mee dat studenten plots veel meer keuzemogelijkheden en vrijheden kregen om hun curriculum samen te stellen en had als gevolg dat dit vanuit een administratief standpunt veel ingewikkelder werd. Zo ook werd het opstellen van examenroosters nog intensiever en ingewikkelder dan voorheen. Zoals reeds aangehaald, zijn de grote vrijheid en hoeveelheid aan keuzemogelijkheden die de studenten kregen één van de grootste veranderingen. Zo zorgde de invoering van het GITsysteem (Geïndividualiseerd Traject) ervoor dat er niet meer gesproken werd over jaren, maar dat de focus werd gelegd op credits (een student kan een creditbewijs voor een vak behalen wanneer hij of zij minstens 10/20 heeft gehaald voor dit vak). Om een universitair diploma te verkrijgen, moet een student slagen voor een bepaald aantal credits, onafhankelijk van het aantal jaren dat hij of zij hierover doet. Hierdoor ontstond er een hele grote verscheidenheid aan curricula tussen de studenten. Deze grote verscheidenheid aan curricula werd nog eens versterkt doordat het nieuwe systeem de toestroom van erasmusstudenten en master-na-master-studenten bevorderde. Zo is het typerend voor de faculteit ingenieurswetenschappen en architectuur dat de studenten in de masterrichtingen niet enkel bestaan uit studenten met een bachelordiploma in de ingenieurswetenschappen, maar dat er ook heel wat industriële ingenieurs zijn die een extra master volgen. Deze industriële ingenieurs moeten bepaalde bachelorvakken bij hun masteropleiding volgen opdat ze recht zouden hebben op een diploma. Het feit dat zij niet enkel mastervakken volgen maar ook bachelorvakken, zorgt er dus voor dat het verschil in curricula tussen studenten nog groter wordt.

1

Samengevat kunnen we dus stellen dat de grote vrijheid die de studenten krijgen bij het opstellen van hun curriculum, de verscheidenheid aan studenten en de grote hoeveelheid keuzevakken in de masterjaren, als gevolg heeft dat het manueel opstellen van de examenroosters een helse opdracht is geworden. En doordat de samenstelling van curricula zoveel verschillen van academiejaar tot academiejaar kan men zich bij het opstellen van de examenroosters ook niet baseren op vorige jaren en moet men per examenperiode van nul beginnen. Daarom wordt er in deze masterproef op zoek gegaan naar methodes of algoritmes die het opstellen van examenroosters kunnen vereenvoudigen. Het is dus de bedoeling dat er gestreefd wordt naar een optimaal examenrooster voor elke student. Een optimaal rooster houdt in dat elke student genoeg tijd heeft om elk examen voor te bereiden. De examens moeten met andere woorden voor elke student zo goed mogelijk worden gespreid. In deze masterproef zal volgende regel gehanteerd worden: een student hoort voor een examen evenveel studiedagen voor zijn volgend examen te hebben als het aantal studiepunten van dit examen. Zo hoort een student voor een vak van bijvoorbeeld zes studiepunten minstens zes studiedagen te hebben. Er zal in hoofdstuk 4 dieper worden ingegaan op de precieze formulering van de doelfunctie. Vervolgens moet er bij het opstellen van de examenroosters ook rekening gehouden worden met bepaalde beperkingen: 1. Een student kan op één tijdstip slechts één examen afleggen. Op de faculteit Ingenieurswetenschappen aan de Universiteit van Gent mag een student volgens het examenreglement maximum één examen per 24uur hebben. Het is met andere woorden niet toegelaten om op aansluitende tijdsloten examens te plannen voor één student (tenzij het examens zijn van hetzelfde vak, hierover meer uitleg in hoofdstuk 4). 2. Sommige examens hebben een beperking op het aantal studenten. Het komt dus voor dat er voor sommige vakken meerdere examensessies moeten worden gepland. Indien dit het geval is, mag er per tijdstip slechts één examensessie worden gepland. 3. Wanneer er voor een vak meerdere examenonderdelen moeten worden ingepland (bijvoorbeeld zowel een mondeling als een schriftelijk examen), dan mag een student geen examen hebben van een ander vak tussen de examens van deze twee onderdelen. 4. Een professor moet beschikbaar zijn op het moment dat er een examen, waarvoor hij verantwoordelijk is, wordt afgenomen. Er zal in deze masterproef niet worden gekeken naar eventuele restricties die betrekking hebben op lokalen, aangezien het met grote waarschijnlijkheid steeds mogelijk zal zijn om elk gepland examen toe te wijzen aan een geschikt lokaal.

2

De faculteit beschikt namelijk over meer dan honderd lokalen die kunnen dienen als examenlokaal. Alle lokalen zullen dus nooit tegelijkertijd bezet zijn, waardoor het dus steeds mogelijk zal zijn om een geschikt lokaal voor een examen te vinden.

1.2

Probleemgrootte

De meeste problemen worden ondervonden bij het opstellen van examenroosters voor de masterjaren, aangezien daar de curricula van de studenten het meest verschillen dankzij de vele keuzemogelijkheden die ze daar hebben. Daarom zal in deze masterproef de focus worden gelegd op de examenroosters van de studenten uit deze twee masterjaren. De dataset die in deze masterproef zal gebruikt worden is deze van de examenperiode van het eerste semester van het academiejaar 2011-2012. In totaal zullen de examenroosters van ongeveer 1200 studenten onder de loep genomen worden. In de examenperiode van het eerste semester van het academiejaar 2011-2012 legden deze studenten examens af van gemiddeld vier à vijf vakken. Echter, door de eerder besproken grote keuzevrijheid, kan het aantal vakken waarvoor een student examen moet afleggen in een semester enorm variëren. Een examenperiode aan de faculteit Ingenieurswetenschappen en Architectuur aan de Universiteit van Gent bestaat uit vier opeenvolgende weken waarbij op alle dagen, behalve zondagen, een examen kan plaatsvinden. De dagen in de examenperiode zijn onderverdeeld in twee tijdsloten (voor- en namiddag) waarbij elk examen één tijdslot in beslag neemt. Dit resulteert in een totaal van 48 tijdsloten waarin er een examen kan worden afgenomen. Het kan voorkomen dat er voor één vak verschillende examens moeten worden gepland. Dit is bijvoorbeeld meestal het geval bij mondelinge examens aangezien er bij dit soort examens vaak een beperking op het aantal studenten per examensessie staat. Zo komt het voor dat er voor één onderdeel van een vak tot tien examensessies moeten worden gepland.

1.3

Doelstelling

Het opstellen van examenroosters gebeurt tot op heden bijna volledig manueel. Het enige programma dat de verantwoordelijke ter beschikking heeft is een Microsoft Office Accesstoepassing dat visuele hulp biedt bij het opstellen van de examenroosters.

3

Zo kan men dankzij dit programma direct zien welke tijdsloten er nog vrij zijn voor een bepaald examen en welke tijdsloten er niet mogen gebruikt worden. De tijsloten die niet meer toegankelijk zijn, zijn bijvoorbeeld tijdsloten waarop studenten van het te plannen examen reeds een ander examen hebben. Het doel van deze masterproef is om de mogelijkheid tot automatisering van het opstellen van deze roosters te onderzoeken, en dus niet om een gebruiksklaar softwarepakket af te leveren. In hoofdstuk 2 zal de aan dit probleem gerelateerde literatuur besproken worden. Vervolgens zal in hoofdstuk 3 meer uitleg gegeven worden over de dataset om dan in hoofdstuk 4 over te gaan tot het opstellen van een wiskundig model. In hoofdstuk 5 zal er worden gezocht naar een heuristische aanpak voor dit probleem. De resultaten van deze heuristische aanpak zullen nadien in hoofdstuk 6 worden besproken. Tot slot zal er in hoofdstuk 7 een algemene conclusie van deze masterproef worden gevormd. Er zal in deze masterproef gesproken worden over University Timetabling Problems. Dit is de officiële term voor de verzameling van alle planningsproblemen die men kan tegenkomen op een universiteit. De meest bekende voorbeelden van dit soort problemen zijn Examination Timetabling problems (het opstellen van examenroosters) en Course Timetabling problems (het opstellen van lessenroosters).

4

Hoofdstuk 2: Literatuurstudie In dit hoofdstuk zal eerst de complexiteit van het ‘University Timetabling Problem’ worden uiteengezet. Het oplossen van dit probleem kan op twee manieren gebeuren: ofwel exact ofwel met behulp van heuristieken. Nadat de complexiteit van het probleem is onderzocht, zal eerst de theoretische achtergrond van de exacte methodes besproken worden. Vervolgens zal er gekeken worden in welke mate deze reeds zijn toegepast bij het University Timetabling Problem. Tot slot zullen de belangrijkste heuristieken en hun implementatie worden onderzocht.

2.1 Complexiteit Een beslissingsprobleem heeft complexiteit NP wanneer dit probleem met een nietdeterministische computer in een polynomiale tijd kan opgelost worden en de oplossing in een polynomiale tijd kan geverifieerd worden met behulp van een deterministische computer [1]. Binnen de complexiteitsklasse NP kunnen we nog onderscheid maken tussen o.a. NP-volledige en NP-moeilijke problemen. Een probleem met complexiteit NP behoort tot de complexiteitsklasse NP-volledig als en alleen maar als elk ander probleem in NP getransformeerd kan worden naar dit probleem in een polynomiale tijd [2]. Anderzijds behoort een probleem met complexiteit NP tot de complexiteitsklasse NP-moeilijk wanneer ze niet oplosbaar zijn in een polynomiale tijd en P ≠ NP[3]. Merk op dat dit als gevolg heeft dat wanneer een NP-moeilijk probleem in een polynomiale tijd oplosbaar zou zijn, het mogelijk is om alle problemen in de complexiteitsklasse NP op te lossen in een polynomiale tijd. Dit is helaas tot op heden nog niet bewezen en vormt één van de belangrijkste vraagstukken binnen de wiskunde. Na veel onderzoek is gebleken dat het timetabling probleem een NP-volledig of een NP-hard probleem is, afhankelijk van het feit of we het probleem bekijken vanuit een optimalisatiestandpunt of niet [4, 5]. De grootste factor die zal bepalen of het al dan niet mogelijk is om een oplossing te bekomen binnen een acceptabele tijdspanne is natuurlijk de probleemstelling zelf. De moeilijkheid om tot een oplossing te komen zal voornamelijk afhangen van de restricties van het probleem. Deze beperkingen of constraints hebben niet enkel invloed op het optimalisatieproces van het probleem, maar ook op de feasibility van het probleem. Zo is het bijvoorbeeld mogelijk dat een bepaalde combinatie van constraints ervoor zorgt dat er zelfs geen feasible rooster kan worden gevonden, laat staan een optimaal rooster.

5

2.2 Exacte oplossingsmethodes Deze paragraaf is gebaseerd op de theorie besproken door Winston in Operations Research [6].

2.2.1 Linear Programming (LP) Linear Programming is een tool die wordt gebruikt bij het oplossen van optimalisatieproblemen. In 1947 ontwierp Geoge Dantzig een erg efficiënte methode om lineaire problemen op te lossen: de simplexmethode. Doordat veel praktische problemen kunnen worden omgevormd tot lineaire problemen en dus heel efficiënt kunnen worden opgelost, is LP wereldwijd een erg populaire methode

om

optimalisatieproblemen

op

te

lossen.

Er

bestaan

enkele

krachtige

softwarepakketten die gespecialiseerd zijn in het oplossen van zulke problemen. Het meest bekende programma is ‘IBM ILOG CPLEX Optimization Studio’. Dit is ook het programma dat verder in deze masterproef zal worden gebruikt. In zijn meest algemene vorm is een lineair probleem als volgt bekend: Objective function: Subject to:

𝑀𝑎𝑥 𝑐1 𝑥1 + 𝑐2 𝑥2

𝑎11 𝑥1 + 𝑎12 𝑥2 ≤ 𝑏1

𝑎21 𝑥1 + 𝑎22 𝑥2 ≤ 𝑏2 𝑎31 𝑥1 + 𝑎32 𝑥2 ≤ 𝑏3 𝑥1 , 𝑥2 ≥ 0

Dit probleem kan ook herschreven worden in een matrixvorm en dan krijgt men de volgende formule: 𝑀𝑎𝑥{𝑐 𝑇 𝑥 | 0 ≤ 𝐴𝑥 ≤ 𝑏 𝛬 𝑥 ≥ 0} Eigen aan linear programming is dat alle variabelen in een lineair verband voorkomen, zowel in de doelfunctie (objective function) als in de voorwaarden (constraints). Er worden met andere woorden geen variabelen met elkaar vermenigvuldigd. Dit zou namelijk leiden tot nietlineariteiten. Grafisch kan een LP worden voorgesteld zoals in figuur 2.1. In deze figuur kan men zien dat wanneer de doelfunctie verschoven wordt in de richting van de pijl, de optimale oplossing van het lineaire probleem het laatste raakpunt tussen de feasible solution en de objective function is.

6

Figuur 2.1: Grafische voorstelling van een LP [7]

2.2.2 Integer Programming (IP)

Een integer programma is een lineair programma waarbij enkele of alle variabelen enkel nietnegatieve waarden kunnen aannemen. Net zoals bij linear programming kunnen heel wat problemen in het dagelijkse leven geformuleerd worden met behulp van integer programming. Helaas moet men concluderen dat door het toevoegen van integere variabelen aan een probleem het oplossen ervan heel wat ingewikkelder wordt. Er zullen andere methodes nodig zijn dan bij lineair programming om tot een oplossing te kunnen komen. Eén van de meest bekende en gebruikte methodes is het branch-and-bound algoritme. Bij dit algoritme komt men tot een optimale oplossing door het efficiënt opsommen van de punten in een mogelijk gebied van een subprobleem. Men splitst met andere woorden het probleem op in verschillende takken totdat voor alle deelproblemen de optimale oplossing kan worden gevonden. Figuur 2.2 geeft een Grafische voorstelling van het Branch-and-bound algoritme. Hier ziet men mooi hoe men het initiële probleem opsplitst in kleinere subproblemen. De optimale oplossing van een lager gelegen probleem is ook de optimale oplossing van zijn hoger gelegen probleem. Daardoor is de optimale oplossing van het volledige probleem de meest optimale oplossing van alle eindpunten van alle ‘branches’ of takken.

7

Figuur 2.2: Branch-and-Bound [7]

Er bestaan nog meerdere algoritmes waarmee lineaire integere problemen kunnen worden opgelost. Een verdere verdieping in deze algoritmes zou ons echter te ver leiden van het doel van deze masterproef. We onthouden uit vorige uiteenzetting dat er voor lineaire problemen zeer efficiënte algoritmes bestaan.

2.2.3

Exacte

opslossingsmethodes

voor

university

timetabling

problems in de literatuur

In het verleden zijn er al heel wat succesvolle pogingen ondernomen om ‘university timetabling problems’ met behulp van integer programming te tackelen: zo zijn bijvoorbeeld K. Schimmelpfeng en S. Helber [10] er in geslaagd om via IP een lessenrooster op te stellen voor de faculteit economie en management aan de universiteit van Hannover. Enkele andere voorbeelden van succesvolle IP-modellen voor het opstellen van lessenroosters kan men vinden aan de universiteit van Patras (Griekenland) [11,12] en aan de universiteit van Shahrood (Iran) [13]. Merk op dat bovenstaande voorbeelden enkel het opstellen van lessenroosters bekijken en niet het opstellen van examenroosters.

8

In de literatuur vindt men minder voorbeelden van succesvolle toepassingen van een IP-model bij examenroosters dan bij lessenroosters. Op het eerste zicht lijken beide problemen nochtans zeer gelijkaardig, maar eens er dieper ingegaan wordt op de probleemstelling blijkt dit niet meer zo te zijn. Bij het opstellen van lessenroosters zal de doelfunctie bijvoorbeeld een minimalisatie zijn van het aantal overtredingen op restricties [11]. Bij examenroosters echter, zal er niet gekeken worden naar de overtredingen, maar zal de doelfunctie bijvoorbeeld de spreiding van de examens omvatten of de minimalisatie van de tijdspanne van de examenperiode [14]. Het is eenvoudig in te zien dat het voor een student minder erg is om de lessen van een keuzevak niet te kunnen bijwonen, dan het niet kunnen deelnemen aan een examen. Dit heeft als gevolg dat de restricties bij examenroosters veel strenger zullen zijn. Men kan stellen dat het examination timetabling problem enorm veranderd is in vergelijk met vroeger. Waar vroeger feasibility centraal stond (zoals bij de lessenroosters), staat nu het ‘comfort’ van de student centraal. Ook hadden studenten vroeger veel minder vrijheid in het samenstellen van hun curriculum, met als gevolg dat er grote groepen studenten met hetzelfde curriculum bestonden waardoor het veel eenvoudiger was om examenroosters op te stellen. Enkele onderzoekers hebben dit probleem met de ‘hedendaagse’ academische restricties onderzocht [15], maar zijn er niet in geslaagd om optimale resultaten te genereren. Vervolgens is hun mathematische formulering enkel bruikbaar bij kleine datasets en niet bij echte probleemgroottes. Verder moeten er tot de vaststelling gekomen worden dat er bijzonder weinig papers zijn die ook de spreiding van de examens vermelden. En indien het toch wordt vermeld, dan wordt dit thema enkel algemeen besproken zonder dat er dieper op ingegaan wordt [15]. Het oplossen van de moderne examination timetabling problems met behulp van integer programming is dus tot op heden nog niet gelukt. Tot slot geldt er ook dat de mathematische formuleringen gevonden in papers sterk afhankelijk zijn van de instituten waarvoor ze zijn ontworpen. Zo heeft elk instituut zijn eigen doelfunctie en beperkingen. Het is daarom ook niet verrassend dat er geen algemene tool beschikbaar is om deze problemen op te lossen [10].

2.3 Heuristische oplossingsmethodes In deze paragraaf zal er een overzicht geven worden van de belangrijkste heuristieken die tot nu toe zijn toegepast bij de university timetabling problems. Eerst zullen de belangrijkste metaheuristieken besproken worden en vervolgens zal er dieper in te gegaan worden op enkele andere belangrijke heuristieken. 9

2.3.1 Basis Metaheuristieken Deze paragraaf is gebaseerd op het overzicht gegeven in een paper geschreven door Rhydian Lewis [4]. Sinds enkele jaren is de interesse om metaheuristieken toe te passen op university timetabling problems alleen maar gestegen. Dit komt waarschijnlijk door het feit dat deze problemen zoals eerder gezegd sterk kunnen verschillen tussen verschillende instituten en metaheuristieken een algemene oplossingsmethode geven die toepasbaar is op een breed gamma van problemen. Metaheuristieken zijn heuristieken die op zoek gaan naar een optimale oplossing door iteratief een mogelijke oplossing te gaan verbeteren. Deze heuristieken worden dan ook heel vaak aangewend om NP-moeilijke problemen op te lossen. Het zijn benaderende algoritmes, wat met zich meebrengt dat er geen garantie bestaat dat de optimale oplossing zal worden gevonden. De bedoeling is echter dat ze een zo goed mogelijke, bruikbare oplossing genereren. De restricties van een timetabling probleem kunnen worden opgesplitst in hard en soft constraints. Hard constraints zijn beperkingen waar te allen tijde aan moet voldaan worden, terwijl soft constraints eventueel kunnen gebroken worden. Wanneer er gesproken wordt over een feasible of mogelijke examenrooster, wil dit zeggen dat er voldaan is aan alle hard constraints, maar niet noodzakelijk aan alle soft constraints. Algoritmes kunnen worden geclassificeerd op basis van de manier waarop het algoritme omgaat met de verschillende soorten constraints. Wij zullen ons in deze masterproef richten op de ‘twostage optimisation’ algoritmes. Deze algoritmes gaan eerst op zoek naar een feasible oplossing om deze dan in een tweede fase te gaan optimaliseren terwijl de feasibility behouden blijft. Dit is dan ook het grote voordeel dat two-stage algoritmes hebben ten opzichte van one-stage algoritmes, waar men tegelijkertijd aan zowel de hard als de soft constraints tracht te voldoen. Bij one-stage algoritmes kan het namelijk zijn dat men, om te voldoen aan enkele soft constraints, feasibility verliest. Het is dan ook niet gegarandeerd dat er in de toekomst nog terug kan worden gegaan naar een feasible oplossing. Er bestaan in totaal vijf basissoorten metaheuristieken [16], namelijk: 1. Simulated Annealing 2. Iterated Local Search 3. Tabu Search 4. Ant Colony Optimization 5. Evolutionary Computing

10

Voornamelijk Simulated Annealing en Tabu Search worden vaak gebruikt in de timetabling problems [4,18,19,21,22,42,43,44]. Het is daarom dat er in het verdere verloop van deze paragraaf gefocust wordt op deze twee metaheuristieken om vervolgens de Iterated Local Search-methode te bespreken. Simulated Annealing Bij simulated annealing vertrekt men van een bestaande oplossing die men wil optimaliseren. Men gaat een neighbour selecteren (een andere feasible oplossing) en indien deze een beter resultaat oplevert, zal deze worden geaccepteerd. Er bestaat echter een kans dat indien deze nieuwe oplossing slechter is dan de best gevonden oplossing, ze toch zal worden geaccepteerd om zo te voorkomen dat men vast komt te zitten op een locaal minimum (of maximum). Dit kan duidelijk worden waargenomen op figuur 2.3. Wanneer er een kans bestaat dat er toch een slechtere oplossing zal worden geaccepteerd, kan het meest optimale punt worden bereikt [16].

Figuur 2.3: Simulated Annealing [18]

De probabiliteit waarmee een slechtere oplossing kan worden geaccepteerd, hangt af van de parameter T of de temperatuur genaamd. De ratio waarmee men de temperatuur laat dalen, zal dus bepalen in hoeverre we slechte oplossingen blijven toelaten. Men verlaagt de temperatuur door telkens na een vast aantal iteraties deze te vermenigvuldigen met een bepaalde factor. Deze factor varieert meestal tussen 0.8 en 0.99 [17]. Deze techniek werd toegepast door Thompson en Dowsland [19]. Zij hebben met behulp van de two-stage benadering een examenrooster opgesteld aan Swansea, de universiteit van Wales. In hun eerste fase zochten ze naar een feasible rooster door middel van een graph colouring heuristiek en in een tweede fase gingen ze op zoek naar een feasible rooster dat rekening hield met de spreiding van de examens voor de studenten. Zoals reeds vermeld hebben ze, om te voldoen aan de soft contraints van het probleem, gebruikt gemaakt van simulated annealing.

11

In totaal werden er drie verschillende soorten neighbourhoods getest. Thompson en Dowsland kwamen tot de conclusie dat Kempe chain neighbourhood een heel goede oplossing gaf doordat deze veel meer flexibiliteit biedt dan bij standaard neighbourhoods. Bij een standaard neighbourhood gaat men uit een feasible rooster één willekeurig examen kiezen en dit examen plaatsen in een willekeurig tijdslot. Wanneer dit resulteert in een infeasible rooster, zal er opnieuw een ander tijdslot worden gekozen. Dit doet men totdat er een tijdslot wordt gevonden waarin het gekozen examen kan worden gepland zonder dat er hard constraints worden gebroken. Een Kempe Chain neighbourhood opstellen begint net zo als het opstellen van een standaard neighbourhood, met dat verschil dat wanneer de verplaatsing van een gekozen examen e1 van tijdslot t1 naar tijdslot t2 resulteert in een infeasible oplossing, er geen nieuw tijdslot zal worden gekozen. Echter, de examens in tijdslot t2 die een conflict geven met examen e1, zullen worden verplaatst naar tijdslot t1. Dit proces herhaalt zich totdat er geen conflicten meer zijn. Figuur 2.4 toont een heel mooi voorbeeld van het Kempe chain-principe. In de linker figuur stellen de bollen examens voor en de lijnstukken tussen verschillende examens impliceren dat deze examens niet in hetzelfde tijdslot mogen worden geplaatst. Wanneer men in de linker figuur examen 1 wenst te verplaatsen van tijdslot 1 naar tijdslot 2, dan merkt men dat dit een conflict zal geven met examen 5. Daarom wordt examen 5 verplaatst naar tijdslot 1. Dat zal dan weer een conflict geven met examens 2 en 3 waardoor zij op hun beurt worden verplaatst naar tijdslot t2. Aangezien nu examens 2 en 8 niet mogen worden gepland in hetzelfde tijdslot zal ook examen 8 moeten worden verplaatst naar tijdslot 1. Uiteindelijk zal men de planning in de rechter figuur van figuur 2.4 verkrijgen.

Figuur 2.4: Kempe Chain [20]

12

Tabu Search Tabu Search is een local search algoritme dat in staat is om zich door locale optima heen te verplaatsen. Het basisprincipe van dit algoritme zegt dat wanneer men een lokaal optimum tegenkomt, het toegestaan is om neighbourhoods te selecteren die niet resulteren in een betere oplossing. Dit heeft als gevolg dat wanneer men dit toelaat, er een kans bestaat dat er cycling zal optreden: het algoritme zal constant heen en weer slingeren tussen één of meerdere oplossingen. Dit kan worden voorkomen door een lijst bij te houden van de laatst bezochte neighbourhoods en het algoritme te verbieden deze neighbourhoods te bezoeken om zo cycling te voorkomen. Deze lijst wordt ook wel de ‘tabu list’ genoemd [21]. Deze search methode werd toegepast door onder meer Arntzen en Løkketangen [22]. Zij maakten in de tweede fase gebruik van een tabu search in combinatie met eenvoudige neighbourhood operators om te voldoen aan de soft constraints. Iterated Local Searc: Variable Neighbourhood Search (VNS) Iterated local search is één van de vijf basismetaheuristieken en werkt als volgt: met behulp van een local search methode gaat men steeds op zoek naar een local minimum. Wanneer deze gevonden is, wordt er gezocht naar een nieuwe tussentoestand en voert men opnieuw een local search uit. Wanneer de gevonden oplossing voldoet aan een bepaald criterium, zal men deze aanvaarden en gaat men vanuit deze oplossing op zoek naar een nieuwe tussentoestand [16]. Bij een VNS-algoritme zal er steeds een nieuwe tussentoestand verkregen worden door telkens van neighbourhood te veranderen. Thompson en Dowsland [19] kwamen tot de conclusie dat het gebruik van een complexere neighbourhoordstructuur leidt tot significant betere oplossingen dan bij de standaard ‘single move’ neighbourhood. Door telkens de neighbourhood aan te passen, hoeft men geen slechtere oplossingen meer te aanvaarden om te ontsnappen uit locale minima zoals onder andere bij simulated annealing [27]. Een tweede voordeel van het VNS-algoritme is dat de afhankelijkheid van de initiële oplossing sterk zal dalen. Wanneer er slechts met één neighbourhood wordt gewerkt, wordt de zoekruimte sterk bepaald door de initiële oplossing omdat er dan een kans bestaat dat er goede oplossingen onbereikbaar zullen zijn. Wanneer er daarentegen gebruik wordt gemaakt van meerdere neighbourhoods is de kans dat er onbereikbare gebieden zijn in de zoekruimte veel kleiner waardoor de kans dat er een goede oplossing wordt gevonden vergroot. Omdat dit algoritme zal toegepast worden in de tweede fase van een optimaliseringproces, moet bij elke neighbourhood steeds de feasibility van de nieuwe oplossing gecontroleerd worden, zodat er allen tijde aan de hard constraints voldaan is. 13

E. K. Burke et al. hebben een VNS-heuristiek toegepast op het examination timetabling probleem [20, 27]. In totaal gebruikten ze negen verschillende neighbourhoods: 1. Verplaats een examen: een willekeurig examen kiezen en verplaatsen naar een willekeurig tijdslot. 2. Wissel 2 examens: het wisselen van twee willekeurige examens. 3. Verplaats 2 examens random 4. Verplaats 3 examens random 5. Verplaats 4 examens random 6. Verplaats 5 examens random 7. Verplaats een volledig tijdslot (analoog aan 1) 8. Wissel 2 tijdsloten (analoog aan 2) 9. Kempe chain neighbourhood Eens er een nieuwe oplossing werd gevonden met behulp van één van bovenstaande neighbourhoods werd er gezocht naar een locaal minimum. Dit werd bereikt dankzij een local search algoritme. De eerste neighbourhood werd als local search gekozen (verplaatsen van een willekeurig examen). Dit alles resulteert in de volgende pseudocode [27]: -

Initialisation: Select the set of neighbourhood structures Nk , k = 1,…,kmax ; find an initial solution x; choose stopping criteria. Repeat until stopping criteria is satisfied: 1. Set k:=1; 2. Until k = kmax, repeat: a) Shaking: Generate a point x´∈ Nk(x) at random from the kth neighboorhood of x; b) Local Search: Apply a local search (a simple steepest descent) to x´, until a local optimum, x´´ is obtained; c) Move or not: if x´´ is better than the solution x then x→ x´´and continue the search with Nk; otherwise, set k=k+1;

E.K. Burke et al. [27] kwamen tot de conlcusie dat het VNS-algoritme momenteel één van de betere algoritmes is op vlak van examination timetabling problems. De allergrootste voordelen die dit algoritme biedt is dat het heel eenvoudig aan te passen is en dat er bijzonder weinig parameters moeten worden ingesteld. Een nadeel is dat de rekentijd voor dit algoritme gemakkelijk 90 minuten kan bedragen. In deze masterproef is dit echter niet zo een groot probleem aangezien examenroosters slechts 3 keer per jaar (januari, juni en september) moeten worden opgesteld en er hier momenteel telkens minstens 3 weken aan wordt besteed. 14

Het grootste verschil tussen de probleemstelling van E.K. Burke et al. [20, 27] en het probleem aan de faculteit ingenieurswetenschappen en architectuur aan de universiteit van Gent is dat de indeling van de studenten in een examen bij Burke et al. niet variabel is, terwijl dit in deze masterproef wel het geval is. Hierdoor zal er in deze masterproef ook aandacht besteed worden aan neighbourhoods die studenten zullen wisselen tussen examens. Ook zal er in deze masterproef worden afgezien van het gebruik van neighbourhoods die volledige tijdsloten verplaatsen, omdat deze zelden leiden tot betere oplossingen. Er zal hier dieper worden op ingegaan in hoofdstuk 5.

2.3.2 Honey-Bee Mating Optimization algorithm Zwermintelligentie is een relatief nieuw onderzoeksveld en betreft het modelleren van het gedrag van sociale insecten zoals mieren en bijen. De metaheursitiek ‘Ant Colony Optimization’ [36] is een voorbeeld van een algoritme dat het gedrag van mieren die op zoek zijn naar voedsel heeft gekopieerd om optimalisatieproblemen op te lossen. Het honey-bee Mathing Optimization (HBMO) algoritme is op zijn beurt afgekeken van de paringswijze van honingbijen [23]. De sterkte van deze algoritmes is het feit dat ze bij elke iteratie telkens een volledige populatie van oplossingen bekijken in plaats van één enkele oplossing [24]. Een honingbij kolonie bestaat uit een koningin (beste oplossing), bijen (mogelijke oplossingen), werkers (heuristiek) en larven (proefoplossingen). De koningin wordt in het begin een bepaalde energiehoeveelheid meegegeven vooraleer ze vertrekt op haar paringsvlucht. Ze keer pas terug wanneer haar energiepijl een bepaalde drempelwaarde heeft bereikt of wanneer haar spermatheca vol is. Tijdens haar vlucht kan een bij volgens een bepaalde probabiliteit met de koning paren. Deze probabiliteit wordt gegeven door de volgende functie [23,24,25]: −𝑣𝑒𝑟𝑐ℎ𝑖𝑙 𝑃𝑟𝑜𝑏(𝐾, 𝐵) = 𝑒𝑥𝑝( ) 𝑠𝑛𝑒𝑙ℎ𝑒𝑖𝑑

In bovenstaande functie is ‘verschil’ gelijk aan het absolute verschil tussen de fitheid van de bij en koningin en ‘snelheid’ stelt de snelheid van de koningin voor. Het is duidelijk dat de kans op paring het hoogst zal zijn in het begin van de vlucht, wanneer de snelheid van de koningin nog hoog is, of wanneer de fitheid van de bij zo goed als gelijk is aan de fitheid van de koningin. Na elke paring, zal de snelheid en de energie van de koningin afnemen met een vooraf bepaalde factor. Eens terug aangekomen in het nest zal de koningin beginnen broeden door willekeurig genetisch materiaal te selecteren uit haar spermatheca.

15

De larven die ontstaan uit dit proces worden grootgebracht door de werkers en wanneer er een larve fitter is dan de koningin zal deze worden vervangen en ontstaat er een nieuwe koningin (of beste oplossing) [25]. N. R. Sabar et al. hebben dit algoritme herschreven voor het timetabling probleem [26]. Zij kregen met behulp van het honey-bee optimization algoritme heel erg goede restultaten. Hun resultaten waren beter dan bijna alle methoden die tot nu toe zijn uitgedacht. Er was maar één algoritme dat het beter deed: het variable neighbourhood algoritme. In dit hoofdstuk hebben we enkele van de, op dit moment, belangrijkste algoritmes besproken op gebied van examination timetabling problemen. Er bestaan echter veel meer algoritmes dan hier besproken [30-41]. De geïnteresseerde lezer die zich hier graag nog verder wil in verdiepen kan altijd meer informatie vinden in de referenties op het einde van deze masterproef.

16

Hoofdstuk 3: Datasets Om de methodes die verder in deze masterthesis zullen worden uitgewerkt te kunnen toetsen, is er nood aan een dataset. Zoals eerder vermeld, zal hiervoor de examenroosters van het eerste semester van het academiejaar 2011-2012 worden gebruikt. In totaal werden er voor deze masterproef 3 Excel files ter beschikking gesteld. In een eerste bestand stonden alle gegevens van alle studenten aan de faculteit Ingenieurswetenschappen en Architectuur aan de Universiteit van Gent (studentenlijst). In het tweede bestand stond dan op zijn beurt alle informatie van alle vakken gegeven aan de universiteit (vaklijst), en tot slot was er het derde bestand met daarin de door de FSA-medewerkers manueel gegenereerde examenplanning. Deze lijsten zijn terug te vinden in bijlage F. Helaas komt de door de FSA opgestelde examenplanning niet helemaal overeen met de gegevens van alle studenten. Zo zijn er namelijk enkele studenten waarvoor er een examen gepland is, maar die volgens de andere file niet zijn ingeschreven voor dat vak. Ook het omgekeerde komt voor. Om er dus voor te zorgen dat de oplossingen uit deze masterproef zouden kunnen worden vergeleken met de oplossing van de FSA, werd de dataset aangepast. Dit is als volgt gebeurd: -

Zoals eerder besproken, worden in deze masterproef enkel de masterjaren bekeken omdat daar de meeste problemen voorkomen. Daarom werd er een eerste selectie doorgevoerd in de vaklijst op basis van het jaar waarin het vak onderwezen hoort te worden in een modeltraject. Enkel de vakken van de masterjaren werden geselecteerd en alle bachelorvakken, inclusief de voorbereidingsprogramma’s aangezien zijn samen worden gepland met de bachelorjaren, werden genegeerd.

-

In een tweede stap werden alle vakken verwijderd die worden gepland op afspraak en waarmee er dus bij het plannen geen rekening hoeft gehouden te worden (dit zijn in totaal 52 vakken waarmee er geen rekening mee hoeft gehouden te worden).

-

Vervolgens werd er per vak gekeken welke studenten deze vakken volgden om zo tot een selectie van studenten te komen.

-

Tot slot werden alle studenten die slechts voor 1 vak uit de selectie een examen moesten afleggen, verwijderd uit de lijst aangezien het plannen van examens voor hen triviaal is.

Zo werd er een lijst bekomen van 1182 studenten en 123 vakken die moesten worden gepland. In totaal moeten er 5261 examens worden afgenomen of dus gemiddeld een 4 à 5-tal vakken per student. De volledige dataset kan men terugvinden in bijlage G.

17

Van deze 1182 studenten zijn er echter nog 757 studenten die ook nog minstens één examen hebben uit hun bachelor. Dit kunnen GIT-studenten zijn die nog enkele bachelorvakken moeten meenemen of master-na-master-studenten die verplicht zijn sommige bachelorvakken te nemen als keuzevak. Aangezien zoveel studenten ook nog examens hebben van vakken die niet in de masterrichtingen worden onderwezen, zal er altijd een verschil zijn tussen de rooster dat zal opgesteld woorden met bovenstaande dataset en de rooster opgesteld door de FSA. Bij het opstellen van de examenroosters moet er dus eigenlijk ook rekening gehouden worden met de bachelorvakken. Wanneer men dit zouden doen, dan zou er ook rekening moeten gehouden worden met alle bachelorstudenten die deze bachelorvakken volgen. Er moet echter ergens een lijn getrokken worden en er is ervoor gekozen om enkel de mastervakken te plannen. Ook is er een fictieve dataset aangemaakt van 12 studenten, 9 vakken en 40 tijdsloten om verdere methodes te testen. Deze dataset is zo opgesteld dat ze alle moeilijkheden van de echte grote dataset ook bevat. Deze dataset is terug te vinden in bijlage A.

18

Hoofdstuk 4: Exacte methode Zoals eerder beschreven wordt linear en integer programming wereldwijd gebruikt voor het oplossen van een hele brede waaier aan problemen. Zoals besproken in hoofdstuk 2 bleek deze methode effectief bij het oplossen van course timetabling problems, maar nog niet bij de examination timetabling problems. Daarom wordt er in dit hoofdstuk onderzocht of een exacte methode bruikbaar is voor dit probleem.

4.1 Eerste wiskundig model Het eerste wiskundige model werd gebasseerd op het model geschreven door Schimmelpfen & Helber [10]. Zij verkregen namelijk op een hele korte rekentijd (enkele minuten) heel mooie oplossingen voor het course timetabling probleem aan de universiteit van Hannover. Zij beschouwden zogenaamde ‘teaching groups’ en gebruikten dan deze groepen om tot een oplossing te komen. Dit is ook wat er in dit eerste model zal geprobeerd worden. Aan onze faculteit is het niet noodzakelijk zo dat er voor elk vak slechts één examen kan worden afgenomen, iets waarmee er in de literatuur weinig rekening wordt gehouden. Dit maakt ons probleem enkel maar complexer aangezien de zoekruimte veel groter wordt en er meer variabelen aan te pas zullen komen omdat studenten niet op voorhand kunnen worden ingedeeld in een examen. Indien men zou opteren om de studenten toch eerst in te delen in groepen vooraleer men gebruik maakt van een wiskundig model, verkleint men de zoekruimte drastisch en zal de oplossing voornamelijk afhangen van de indeling van de studenten. De kans dat in dit geval de optimale oplossing gevonden kan worden, zal veel kleiner zijn dan wanneer de studenten niet op voorhand worden ingedeeld in groepen. Niet alleen de kans op een optimale oplossing zal verkleinen, maar ook de kans dat er feasible rooster gevonden kan worden, zal kleiner worden. In het eerste wiskundig model zal er op de volgende manier een onderscheid worden gemaakt tussen examens en groepen: -

Er zijn in totaal drie verzamelingen: er zijn vakken, examens en groepen.

-

Een vak kan maximaal uit twee examens bestaan. Meestal gaat het dan over ofwel een mondeling en een schriftelijk deel ofwel een oefeningen en een theoretisch deel. Alle studenten moeten examen afleggen van alle verschillende delen.

-

Een examen kan dan op zijn beurt bestaan uit verschillende groepen. Zo kan het zijn dat bij een mondeling examen van een vak er per tijdslot een maximaal aantal studenten is dat een examen mag afleggen. Dit heeft als gevolg dat alle studenten voor elk examen in exact één groep moeten worden gepland. 19

Beschouw het volgende voorbeeld: vak 1 heeft twee examens: examen 1 en 2. Examen 1 heeft geen beperking op het aantal studenten en gaat dus door in één groep: groep 1. Bij examen twee daarentegen kunnen er slechts 10 studenten tegelijkertijd een examen afleggen. Dit resulteert in bijvoorbeeld vier groepen: groep 2 tot 5. Een student die examen moet afleggen van vak 1 moet dus worden gepland in groep 1 en in één van de vier groepen van examen 2: groepen 2 tot 5. In dit model zullen er dus tegelijkertijd studenten in groepen worden onderverdeeld en groepen gepland in een rooster. In het vervolg van deze paragraaf zal er worden uitgelegd hoe het wiskundige model werd opgesteld.

4.1.1 Notatie Indices s

Student

p

Professor

v

Vak

e

Examen

t

Tijdslot: (gaat van 1 tot 54: elke dag heeft 2 tijdsloten en we hebben 4 weken examenperiode met 3 zondagen tussenin die in rekening worden gebracht)

i

Groep van het examen

Parameters exs[s] exp[p]

Elk element is een verzameling met examens waarvan student s examen moet afleggen. Elk element is een verzameling met examens waarvan professor p examen moet afnemen.

stud[e]

Elk element is een verzameling van studenten die het examen e moeten afleggen.

ex[v]

Elk element is een verzameling van examens die bij vak v horen.

T[p]

Elk element is een verzameling van tijdsloten waarop een prof geen examens kan afnemen (ook zondagen inbegrepen).

multi[v]

Binaire parameter die 1 is als er voor vak v twee examens voorzien zijn.

SP[e]

Integere parameter die het aantal studiepunten van een examen e weergeeft.

m[e]

Binaire parameter die 1 is als het examen e in verschillende groepen moet doorgaan.

aantal[e]

Integer die het aantal groepen voor examen e weergeeft (minstens 1 groep/examen).

grootte[e] Integer die het maximale aantal studenten per groep van een examen e weergeeft.

20

Variabelen g[e,i,t]

Binaire variabele die 1 is indien groep i van examen e examen heeft in tijdslot t.

x[s,e,t]

Binaire variabele die 1 is indien student s examen e aflegt in tijdslot t.

y[p,e,t]

Binaire variabele die 1 is indien professor p examen e afneemt in tijdslot t.

straf[s,e]

Geeft de straf van een vak op een welbepaald tijdslot te plannen weer.

z

Binaire variabele

4.1.2 Formulering Doelfunctie Aan de faculteit ingenieurswetenschappen en architectuur hoort elke studenten een zo goed mogelijke spreiding van zijn examens te hebben. Dit moet dus kunnen worden weergegeven in de doelfunctie. Zoals gezegd in de inleiding, wordt een goede spreiding gedefinieerd als een spreiding waar een student evenveel studiedagen heeft als het aantal studiepunten van een vak. Een student moet dus voor een vak met bijvoorbeeld zes studiepunten minstens zes dagen ofwel twaalf tijdsloten studietijd hebben. Wanneer een student te weinig studietijd voor een bepaald examen heeft, dan zal hiervoor een straf worden aangerekend. Men kan bijvoorbeeld ook bonuspunten geven indien een student wel genoeg tijd heeft om te studeren. De keuze werd gemaakt om te werken met een straffunctie om de eenvoudige reden dat dan de straf kan worden verhoogd naar gelang een student dagen te kort heeft om te studeren. Zo kan er een lage straf worden toegekend indien een student bijvoorbeeld vijf dagen heeft om te studeren voor een examen van zes studiepunten, en kan er een veel hogere straf worden toegekend indien hij maar één dag zou hebben om te studeren voor ditzelfde examen. Deze nuance is niet aanwezig indien er gewerkt zou worden met bonuspunten in plaats van strafpunten. De doelfunctie kan men op meerdere manieren opstellen. Eén manier is zeggen dat de doelfunctie het aantal studenten met een straf boven een bepaalde drempelwaarde moet minimaliseren. De doelstelling op deze manier formuleren kan als gevolg hebben dat er enkele studenten zullen zijn met een erg slechte planning om ervoor te zorgen dat andere studenten een iets betere planning hebben. Dit kan men als volgt inzien: stel er is een student wiens straf reeds boven de drempelwaarde zit. Dan kan het gebeuren dat, als men een examen verplaatst, de straf voor enkele andere mensen onder de drempelwaarde duikt, maar dat de totale straf gigantisch groot wordt voor deze ene student wiens straf reeds boven de drempelwaarde zat. Terwijl de doelfunctie een betere waarde zal meegeven, kan het dus zijn dat je een aantal studenten hebt met een iets betere rooster en één student met een veel slechtere rooster. Dit wil men natuurlijk vermijden. 21

Een tweede manier om de doelfunctie op te stellen, is zeggen dat de maximale toegelaten score voor elke student moet worden geminimaliseerd. Elke student moet in dit geval een score hebben die minder is dan een bepaalde waarde en deze waarde zal men minimaliseren. Zoals eerder aangehaald, varieert het aantal vakken waarvan een student examen moet afleggen tussen één en tien vakken. Dit heeft als gevolg dat de straf van een student met tien vakken altijd veel hoger zal liggen dan de straf van een student met bijvoorbeeld drie vakken. De minimale straf zal dus meestal gevonden worden bij de student met het zwaarste curriculum waardoor het rooster van vele studenten dus niet optimaal zal zijn. Een derde methode om de doelfunctie op te stellen, en tevens de methode die in deze masterproef is gebruikt, is zeggen dat de doelfunctie de totale straf moet minimaliseren. Indien de doelfunctie goed wordt opgesteld, kan men het feit dat er één student wordt gestraft voor het examenrooster van een groep andere studenten, beperken. Bij deze doelfunctie kan er dan wel weer het omgekeerde gebeuren! Zo kan het gebeuren dat er een groep studenten een iets slechtere rooster krijgt opdat er één student een veel betere rooster zou krijgen. De mate waarin dit mogelijk is, zal opnieuw gecontroleerd kunnen worden door de doelfunctie goed te definiëren. Er zal moeten gezocht worden naar een gulden middenweg tussen deze twee situaties. Na wat zoekwerk werd de volgende definitie voor de straffunctie opgesteld:

𝑆𝑡𝑟𝑎𝑓𝑠,𝑒 = � 𝑥𝑠,𝑒,𝑡 � 𝑡

min(2𝑆𝑃𝑒 ,𝑡−1)

� 𝑗=1

5

� 𝑥𝑠,𝑧,𝑡−𝑗 �(2𝑆𝑃𝑒 − 𝑗 + 1)2 (11 − 𝑆𝑃𝑒 )3 ��

𝑧∉𝑒𝑥[𝑣]

a∀𝑠, 𝑒 ∈ 𝑒𝑥𝑠𝑠 , 𝑣: 𝑒 ∈ 𝑒𝑥[𝑣]

(4.1)

a

Indien x[s,e,t] gelijk is aan één, of met andere woorden indien student s examen e moet afleggen op tijdtip t, zal er gekeken worden of er examens zijn gepland binnen de j tijdsloten voor tijdslot t, met j variërend van één tot het minimum van twee keer het aantal studiepunten van het beschouwde examen en het tijdslot waarop dit examen gepland is min één. Indien een vak van zes studiepunten gepland is op tijdslot 3, dan hoeft men namelijk enkel te kijken naar tijdsloten 1 en 2. De coëfficiënt j kunnen we dus beschouwen als het aantal tijdsloten aanwezig tussen twee examens indien deze buiten de optimale spreidingszone liggen (zijnde 2 keer het aantal studiepunten van het laatst geplande vak). De term ‘𝑧∉𝑒𝑥[𝑣]’ in de tweede somfunctie zegt dat we enkel een straf gaan bepalen tussen examens van een verschillend vak. Wanneer een student twee examens moet afleggen van hetzelfde vak, zal er dus niet worden gekeken hoeveel studietijd deze student heeft voor het tweede examen. 22

Dit komt omdat er een constraint is (zie pagina 25) die zegt dat er tussen examens van hetzelfde vak geen ander examen mag vallen en twee examens van het zelfde vak dus altijd op elkaar moeten volgen. De term x[s,z,t-j] is dus gelijk aan één indien er een examen z, dat niet hetzelfde vak heeft als het beschouwde examen e, gepland is op j tijdsloten voor het tijdslot t waarop examen e gepland is. Bij elk vak van elke student gaat men dus gaan kijken of er examens vallen van een ander vak binnen 2SP-tijdsloten. Indien dit het geval is, zal dit worden bestraft. De totale straf bestaat uit twee termen. De eerste term (2SPe – j +1)5/2 is de spreidingsterm en zal de grootte van de straf bepalen op basis van het aantal studiedagen. Indien bijvoorbeeld j gelijk is aan twee, of met andere woorden indien een student slechts 2 tijdsloten heeft om te studeren, zal voor een vak van zes studiepunten deze term gelijk zijn aan (12-2+1)5/2 ≈ 401. Vervolgens zal de tweede term (11-SPe)3 ervoor zorgen dat de straf van een vak van zes studiepunten niet enorm veel zwaarder doorweegt dan bijvoorbeeld een vak van drie studiepunten. Op deze manier voorkomt men dat er veel minder rekening zal worden gehouden met een vak met weinig studiepunten. Het maximale aantal studiepunten van een vak is op onze faculteit gelijk aan 10. Vandaar dat het aantal studiepunten wordt afgetrokken van 11. Zo zorgt men er steeds voor dat de straf ≥ 0 zal zijn.

Indien er geen goede resultaten verkregen worden, dan kan men bij zowel de eerste term als de tweede term van de straffunctie de graad van de machtsverheffing aanpassen om zo bijvoorbeeld nog een veel hogere straf toe te wijzen bij weinig studietijd of om het verschil tussen weinig en veel studiepunten te verminderen. De uiteindelijke doelfunctie zal dus als doel hebben de totale straf te minimaliseren. Dit resulteert in volgende formule:

𝑀𝑖𝑛 � � 𝑆𝑡𝑟𝑎𝑓𝑠,𝑒

(4.2)

𝑠 𝑒∈𝑒𝑥𝑠𝑠

Merk op dat de doelfunctie in zijn huidige vorm een niet-lineaire functie is. Er zal echter eerst gekeken worden hoe de wiskundige solver hiermee zal omgaan vooraleer er een poging ondernomen wordt om deze functie te lineariseren of herformuleren. Wanneer de straf uitgezet wordt in functie van het aantal vrije studiedagen voor een vak met zes studiepunten, dan krijgt men bovenste zwarte straffunctie zoals weergegeven in figuur 4.1. De onderste grijze functie is de straffunctie voor een vak met drie studiepunten.

23

In onderstaande grafiek kan men zien dat wanneer een student genoeg studietijd heeft de straf op nul zal staan en dat de straf zal stijgen naargelang zijn studietijd daalt. Ook ziet men dat het erger is om een slechts een bepaald aantal studiedagen te hebben voor een vak met zes studiepunten dan voor een vak met drie studiepunten. De grafiek toont ook aan dat de straf ongeveer gelijk is voor vakken met 3 en 6 SP indien het aantal studiedagen dubbel zo veel is. Zo zal de straf voor twee studiedagen bij een 3SP-vak ongeveer gelijk aan de straf voor slechts 4 studiedagen bij een 6SP-vak.

Straffunctie (6 SP) 7000 6000

Straf

5000 4000 3000 2000 1000 0 1

2

3

4

5

6

7

8

9

10

11

12

13

Aantal tijdsloten studietijd Figuur 4.1: Straffunctie: 6 SP (zwart) en 3 SP (grijs)

Constraints 1.

Elke groep moet exact één keer worden ingepland: � 𝑔𝑒,𝑖,𝑡 = 1

2.

𝑡

Een student moet in 1 groep per examen worden ingedeeld: 𝑥𝑠,𝑒,𝑡 ≤ � 𝑔𝑒,𝑖,𝑡 𝑖

� 𝑥𝑠,𝑒,𝑡 = 1 𝑡

∀𝑒, 𝑖 = 1. . 𝑎𝑎𝑛𝑡𝑎𝑙𝑒

(4.3)

∀𝑠, 𝑒 ∈ 𝑒𝑥𝑠𝑠 , 𝑡

(4.4)

∀𝑠, 𝑒 ∈ 𝑒𝑥𝑠𝑠

(4.5)

24

3.

Elke groep heeft een maximale grootte: � 𝑥𝑠,𝑒,𝑡 ≤ 𝑔𝑟𝑜𝑜𝑡𝑡𝑒𝑒

4.

5.

𝑠∈𝑠𝑡𝑢𝑑𝑒

∀𝑝, 𝑒 ∈ 𝑒𝑥𝑝𝑝 𝑖, 𝑡

(4.7)

� � 𝑥𝑠,𝑒,𝑡 ≤ 1

∀𝑠, 𝑡\{1,54}

(4.8)

𝑥𝑠,𝑒,53 + 𝑥𝑠,𝑒,54 ≤ 1

∀𝑠, 𝑒 ∈ 𝑒𝑥𝑠𝑠

(4.10)

∀𝑝, 𝑒 ∈ 𝑒𝑥𝑝𝑝

(4.11)

𝑦𝑝,𝑒,𝑡 ≥ 𝑔𝑒,𝑖,𝑡

Een student heeft mag slechts 1 examen afleggen per 24 uur:

𝑡−1 𝑒∈𝑣𝑎𝑘𝑠𝑠

𝑥𝑠,𝑒,1 + 𝑥𝑠,𝑒,2 ≤ 1

� 𝑦𝑝,𝑒,𝑡 = 𝑎𝑎𝑛𝑡𝑎𝑙𝑒

8.

9.

∀𝑠, 𝑒 ∈ 𝑒𝑥𝑠𝑠

(4.9)

Er mag enkel een examen worden afgenomen wanneer de professor vrij is:

𝑡\𝑇𝑝

7.

(4.6)

Bij elke groep die wordt ingepland, moet ook de professor worden ingepland:

𝑡+1

6.

∀𝑒, 𝑡

Er mag slechts 1 examen per tijdstip, per professor worden gepland: � 𝑦𝑝,𝑒,𝑡 ≤ 1

∀𝑝, 𝑡

(4.12)

𝑒∈𝑒𝑥𝑝𝑝

� 𝑔𝑒,𝑖,𝑡 = 1

∀𝑒, 𝑡

(4.13)

Er mag slechts 1 groep per vak per tijdstip worden gepland:

𝑖

Wanneer een student twee examens van één vak moet afleggen, dan mogen er tussen deze examens geen examens van andere vakken worden gepland: (1 − 2𝑧)𝑡𝑖 𝑥𝑠,𝑒𝑖,𝑡𝑖 ≥ (1 − 2𝑧)𝑡𝐴 𝑥𝑠,𝑒𝐴 ,𝑡𝐴

(1 − 2𝑧)𝑡𝑖 𝑥𝑠,𝑒𝑖,𝑡𝑖 ≥ (1 − 2𝑧)𝑡𝐵 𝑥𝑠,𝑒𝐵 ,𝑡𝐵

∀𝑠, 𝑒 ∈ 𝑒𝑥𝑠𝑠 , 𝑡,

(4.14) (4.15)

10. Elk examen moet één keer worden ingepland: Is voldaan met constraint 1.

25

4.1.3 Uitvoeren model op een kleine dataset In deze masterproef werd er gebruik gemaakt van het softwarepakket OPL ILOG CPLEX van IBM om de wiskundige modellen uit te rekenen. Bovenstaand model werd met de kleine dataset uit bijlage A uitgerekend op een computer met een 1.83 GHz Intel Core 2 Duo T5600 processor en 2558 MB RAM-geheugen. Wanneer bovenstaand model werd uitgerekend, verscheen er al snel een error: de CPLEX-solver kon niet overweg met de niet-lineariteit van de doelfunctie. In een tweede stap werd de doelfunctie vervangen door een simpele lineaire functie die niets met de originele doelfunctie te maken had, louter om te kijken of het model op zich werkte. Toen werd er vastgesteld dat het model heel veel problemen gaf omtrent de indeling van de groepen. Daar waar Schimmelpfeng en Helber [10] reeds ingedeelde groepen planden, worden in ons model de groepen simultaan gepland met het indelen van de studenten in deze groepen. Dit resulteert in een model met heel veel variabelen en constraints en al snel kregen we een error vanwege te weinig geheugen om het model op te kunnen lossen. Het lineariseren van de doelfunctie in dit model leek zinloos aangezien dit enkel zou leiden tot nog meer constraints en dus geheugencapaciteit. Dit wiskundige model bleek dus praktisch niet haalbaar en het gebrek aan geheugen en de niet-lineaire doelfunctie gaven aan dat dit model volledig moest worden herbekeken. Omdat er na lang zoeken jammer genoeg geen oplossing en resultaten verkregen werden, werd er op zoek gegaan naar een nieuwe formulering voor dit wiskundig model.

4.2 Tweede wiskundig model Omwille van de problemen in het eerste model, werd er besloten om een nieuw model op te stellen. Er werd gezocht naar een manier om de doelfunctie linear te schrijven en om het aantal variabelen en constraints te beperken. In dit model wordt er gebruik gemaakt van drie verschillende verzamelingen: vakken, onderdelen en examens. Een vak kan uit één of twee onderdelen bestaan en een onderdeel kan op zijn beurt uit één tot tien examens bestaan. Merk de gelijkenis op met het eerste model daar waar men per examen een aantal groepen beschouwde, beschouwt men elk van deze groepen nu als een apart examen. De onderverdeling vanuit het eerste model (vak → examen → groep) werd nu dus veranderd naar vak → onderdeel → examen.

26

Deze nieuwe verdeling en benaming zorgen ervoor dat het probleem vanuit een ander standpunt zal benaderd worden om zo tot een ander model te komen. Tijdens één van de vergaderingen met het FSA werd de raad gegeven om niet te kijken naar de eisen van de proffen bij het opstellen van de examenroosters. Bij het manueel opstellen kijkt de FSA namelijk enkel of het rooster al dan niet goed is voor de studenten en houdt geen rekening met de vraag van proffen om een examen bijvoorbeeld niet op een zaterdag te plannen. Indien het plannen van examenroosters automatisch zou gebeuren en niet meer manueel, dan kunnen de examenroosters vroeger worden bekendgemaakt zodat de ook de proffen vroeger de data van de examens kennen en zo eenvoudiger eventuele conflicten kunnen vermijden. In een eerste fase zal er dus geen rekening meer gehouden worden met voorkeuren van de proffen. Eens het opstellen van een model geslaagd is, kan er in een tweede fase onderzocht worden of het incorporeren van voorkeursdata van proffen toch niet mogelijk is. Net zoals bij het vorige model werd er in dit model geen rekening gehouden met constraints betreffende lokalen. In het verdere verloop van deze paragraaf zal eerst het nieuwe model besproken worden en vervolgens zal er onderzocht worden op welke manier men de doelfunctie kan herformuleren.

4.2.1 Notatie en constraints Indices s

Student

v

Vak

o

Onderdeel

e

Examen

t

Tijdslot: gaat van 1 tot 54. Elke dag heeft 2 tijdsloten en we hebben 4 weken examenperiode. Enkel de zondagen (6 tijdslots) werden weggelaten uit deze verzameling.

De zondagen zijn bij de tijdsloten weggelaten uit de verzameling omdat er op deze dagen geen examen mag worden gepland, maar ze moeten wel meetellen als studiedagen. Dit werd als volgt opgelost: stel een zaterdag heeft tijdsloten 11 en 12, dan krijgt de daaropvolgende maandag tijdsloten 15 en 16 toegewezen en worden tijdsloten 13 en 14 weggelaten uit de verzameling. Zo zorgt men ervoor dat er op zondag geen examen kan vallen, maar dat de zondagen niet worden verwaarloosd bij het uitrekenen van het verschil in tijd tussen bijvoorbeeld maandag en zaterdag.

27

Variabelen x[s,e,t]

Binaire variabele die 1 is indien student s examen e aflegt in tijdslot t.

y[e,t]

Binaire variabele die 1 is indien examen e doorgaat in tijdslot t.

Parameters Elk element is een verzameling van vakken waarvan student s examen moet

vaks[s]

afleggen. Elk element is een verzameling van onderdelen waarvan student s examen

onds[s]

moet afleggen. Elk element is een verzameling van alle mogelijke examens die student s kan

exs[s]

afleggen. Elk element is een verzameling van studenten die het examen e kunnen

studEx[e]

afleggen.

aantalOnd[v]

Integer die het aantal onderdelen horend bij vak v weergeeft.

vak[o]

Integer die weergeeft bij welk vak het onderdeel o hoort.

maxStud[o]

Integer die het maximale aantal studenten per onderdeel weergeeft.

ond[e]

Integer die weergeeft bij welk onderdeel examen e hoort.

SP[e]

Integer die het aantal studiepunten van een examen e weergeeft.

Constraints 1.

Voor elk onderdeel moet een student in exact één examen worden gepland: �

2.

3.

4.

�

𝑥𝑠,𝑒,𝑡 = 1

∀𝑠, 𝑜 ∈ 𝑜𝑛𝑑𝑠𝑠

(4.16)

𝑦𝑒,𝑡 ≥ 𝑥𝑠,𝑒,𝑡

∀𝑠, 𝑒 ∈ 𝑒𝑥𝑠𝑠 , 𝑡

(4.17)

� 𝑦𝑒,𝑡 = 1

∀𝑒

(4.18)

∀𝑒, 𝑡

(4.19)

𝑡 𝑒: 𝑜𝑛𝑑[𝑒]=𝑜

y[e,t] koppelen aan x[s,e,t]:

Elk examen moet exact één keer worden gepland:

𝑡

Per examen mag er slechts een maximum aantal studenten worden gepland: �

𝑠∈𝑠𝑡𝑢𝑑𝐸𝑥𝑒

𝑥𝑠,𝑒,𝑡 ≤ 𝑦𝑒,𝑡 𝑚𝑎𝑥𝑆𝑡𝑢𝑑[𝑜𝑛𝑑[𝑒]]

28

5.

Er mag maximum één examen per vak per tijdstip worden gepland: �

6.

𝑒:𝑣𝑎𝑘[𝑜𝑛𝑑[𝑒]]=𝑣

𝑦𝑒,𝑡 ≤ 1

Een student heeft op één tijdstip maximum één examen: � 𝑥𝑠,𝑒,𝑡 ≤ 1

7.

𝑒∈𝑒𝑥𝑠𝑠

∀𝑡, 𝑣

(4.20)

∀𝑠, 𝑡

(4.21)

Tussen twee examens van hetzelfde vak mogen er geen andere examens worden gepland: 𝐼𝐹(𝑎𝑎𝑛𝑡𝑎𝑙𝑂𝑛𝑑�𝑣𝑎𝑘[𝑜𝑛𝑑]� > 1) a �

𝑒∈𝑒𝑥𝑠𝑠 :𝑣𝑎𝑘�𝑜𝑛𝑑[𝑒]�≠𝑣

𝑥𝑠,𝑒,𝑡3 ≤ 2 − 𝑥𝑠,𝑒1 ,𝑡1 − 𝑥𝑠,𝑒2 ,𝑡2

(4.22)

∀𝑠, 𝑣 ∈ 𝑣𝑎𝑘𝑠𝑠 , 𝑡1 , 𝑡2 : 𝑡1 < 𝑡2 , 𝑡3 : 𝑡1 < 𝑡3 < 𝑡2 , 𝑒1 ∈ 𝑒𝑥𝑠𝑠 : 𝑣𝑎𝑘�𝑜𝑛𝑑[𝑒1 ]� = 𝑣,

8.

𝑒2 ∈ 𝑒𝑥𝑠𝑠 : 𝑣𝑎𝑘�𝑜𝑛𝑑[𝑒2 ]� = 𝑣 𝛬 𝑜𝑛𝑑[𝑒2 ] ≠ 𝑜𝑛𝑑[𝑒1 ]

Een student mag op 24 uur slechts één examen afleggen: � �

𝑒∈𝑣𝑎𝑘𝑠𝑠

𝑡+1

(𝑥𝑠,𝑒,𝑡𝑡 −

𝑡𝑡:𝑡−1

� (𝑥𝑠,𝑒𝑒,1 + 𝑥𝑠,𝑒𝑒,2 )) ≤ 1

𝑒𝑒∈𝑣𝑎𝑘𝑠𝑠

Met 𝑒𝑒: 𝑒𝑒! = 𝑒 𝛬 𝑣𝑎𝑘�𝑜𝑛𝑑[𝑒𝑒]� = 𝑣𝑎𝑘[𝑜𝑛𝑑[𝑒𝑒]]

� (𝑥𝑠,𝑒,53 + 𝑥𝑠,𝑒,54 −

𝑒∈𝑣𝑎𝑘𝑠𝑠

𝑥𝑠,𝑒𝑒,𝑡𝑡 ) ≤ 1

Met 𝑒𝑒: 𝑒𝑒! = 𝑒 𝛬 𝑣𝑎𝑘�𝑜𝑛𝑑[𝑒𝑒]� = 𝑣𝑎𝑘[𝑜𝑛𝑑[𝑒𝑒]]

� (𝑥𝑠,𝑒,1 + 𝑥𝑠,𝑒,2 −

𝑒∈𝑣𝑎𝑘𝑠𝑠

�

𝑒𝑒∈𝑣𝑎𝑘𝑠𝑠

� (𝑥𝑠,𝑒𝑒,53 + 𝑥𝑠,𝑒𝑒,54 )) ≤ 1

𝑒𝑒∈𝑣𝑎𝑘𝑠𝑠

Met 𝑒𝑒: 𝑒𝑒! = 𝑒 𝛬 𝑣𝑎𝑘�𝑜𝑛𝑑[𝑒𝑒]� = 𝑣𝑎𝑘[𝑜𝑛𝑑[𝑒𝑒]]

∀𝑠, 𝑡\{1,54}

(4.23)

∀𝑠

(4.24)

∀𝑠

(4.25)

Merk op dat constraint 7 enkel moet worden toegepast bij vakken met twee onderdelen. Vandaar dat er bij deze constraint ook een if-voorwaarde hoort die hierop zal toezien. Deze restrictie is een heel erg zware beperking: er zijn namelijk drie verschillende tijdsloten waarmee rekening moet gehouden worden. Deze constraint zal dus erg zwaar doorwegen op het nodige geheugen om dit model te kunnen oplossen. Constraint 8 is redelijk complex aangezien een student slechts één examen mag hebben binnen de 24 uur, tenzij de examens van een gemeenschappelijk vak zijn. Voor elk tijdslot zal er dus gekeken worden of er binnen het interval t-1 … t+1 meer dan één examen is gepland. 29

Dit wordt weergegeven door de eerste twee sommaties in formule (4.23). Aangezien alle examens beschouwd werden in de eerste sommatie, moeten de examens van een gemeenschappelijk vak worden afgetrokken opdat er toch zou voldaan zijn aan de constraint. Indien bovenstaand model goede resultaten geeft, zal er gekeken worden of het mogelijk is voorkeuren van proffen in rekening te brengen. Om dit in het model op te nemen, zal men een bijkomende parameter moeten definiëren. De parameter Tp[e] zal per examen een verzameling geven met data waarop de professor van dit examen beschikbaar is. Indien men deze parameter in rekening brengt, zal constraint 3 van bovenstaand model (formule 4.18) als volgt veranderen: 3.

Elk examen moet exact één keer worden gepland: � 𝑦𝑒,𝑡 = 1

𝑡∈𝑇𝑝[𝑒]

∀𝑒

(4.26)

Door bovenstaande constraint aan te passen, zegt men dat elk examen exact één keer moet worden gepland, indien de professor van dit examen beschikbaar is.

4.2.2 Doelfunctie Het probleem dat de doelfunctie niet-lineair is, is echter nog steeds aan de orde. In een eerste poging werd er geprobeerd deze doelfunctie te herschrijven naar een lineaire functie. Het zal blijken dat dit in ons geval niet vanzelfsprekend is. In de literatuur werd de doelfunctie vaak opgesteld met behulp van een conflict matrix [26,35]. Dit houdt in dat men eerst een matrix s[k,l] aanmaakt met s[k,l] gelijk aan het aantal studenten dat zowel examen k als examen l moet afleggen. Indien het absolute verschil in tijd tussen k en l meer bedraagt dan een op voorhand vastgelegde waarde i, wordt er een straf berekend. Deze straf wordt weergegeven door 2|4−𝑖| 𝑠𝑘,𝑙 . Tot slot wordt er gesommeerd over k en l en verkrijgt men de totale straf.

Deze methode is jammer genoeg niet toepasbaar op ons probleem. Eerst en vooral zijn in de literatuur de studenten op voorhand ingedeeld in een examen en is deze matrix dus een bekende, niet veranderende matrix. Daar waar er in deze masterproef niet op voorhand geweten is welke student er in welk examen zal worden ingedeeld, kan men deze matrix dus niet op voorhand aanmaken.

30

Een tweede reden waarom het bij ons niet toepasbaar is, is omdat in de literatuur enkel een straf wordt berekend indien het verschil tussen twee examens in tijd groter is dan een vooraf gedefinieerde waarde. Bij ons echter, varieert die waarde naar gelang het aantal studiepunten van het laatst geplande examens van twee examens. Er moet dus niet alleen gekeken worden naar de studiepunten, maar ook welk van de twee examens het laatst gepland is. Dit alles maakt het voor onze probleemstelling bijzonder ingewikkeld om gebruik te maken van een conflict matrix als doelstelling. Een tweede optie was om de doelfunctie te lineariseren. Het lineariseren had als gevolg dat er een nieuwe variabele moest ingevoerd worden en dat er enkele heel zware constraints bijkwamen waardoor er zelfs niet genoeg geheugen was om een erg kleine dataset van nog geen tien studenten op te lossen. Een derde optie en tevens de optie waarvoor er is gekozen, is om te werken met slackvariabelen en deze te gaan definiëren in enkele constraints. Dit gebeurt als volgt: Er zal gebruik worden gemaakt van de slackvariabele slackvar[e1,e2,t1,t2] die weergeeft hoeveel tijdsloten er minder zitten tussen examen e1 en examen e2 dan er optimaal minstens moeten tussenzitten. Stel dat examen e1 zes studiepunten heeft en er tussen examen e1 en e2 slechts tien tijdsloten zitten, zal de slackvariabele van e1 en e2 gelijk zijn aan twee (2*6-10=2). Op deze manier wordt er echter geen onderscheid gemaakt tussen vakken van verschillende studiepunten. De slackvariabele van een vak met veel studiepunten zal in het zelfde geval dus evenveel bedragen indien dit vak minder studiepunten zou hebben. Om dit te voorkomen zullen de slackvariabelen in de constraint gedeeld worden door het aantal studiepunten van het beschouwde vak. Indien een student nu twee tijdsloten studietijd te weinig heeft gekregen voor een vak met zes studiepunten, zal de slackvariabele 12 bedragen in plaats van twee. Zoals daarnet aangehaald worden de slackvariabelen met behulp van constraints bepaald en ook hier zal er een if-voorwaarde aan te pas komen: ∀𝑠, 𝑒1 ∈ 𝑒𝑥𝑠𝑠 , 𝑒2 ∈ 𝑒𝑥𝑠𝑠 , 𝑡1 , 𝑡2 : 𝑡1 − 12 ≤ 𝑡2 ≤ 𝑡1 a

𝐼𝐹(𝑆𝑃[𝑒1 ] = 6 𝛬 𝑣𝑎𝑘[𝑜𝑛𝑑[𝑒1 ]] ≠ 𝑣𝑎𝑘[𝑜𝑛𝑑[𝑒2 ]]): a

(𝑡1 − 𝑡2 )�𝑥𝑠,𝑒1 𝑡1 + 𝑥𝑠,𝑒2 𝑡2 − 1� ≥ 13�𝑥𝑠,𝑒1 𝑡1 + 𝑥𝑠,𝑒2 𝑡2 − 1� − (𝑠𝑙𝑎𝑐𝑘𝑣𝑎𝑟𝑒1 ,𝑒2 ,𝑡1 ,𝑡2 /6)a 12 ≥ 𝑠𝑙𝑎𝑐𝑘𝑣𝑎𝑟𝑒1 ,𝑒2 ,𝑡1 ,𝑡2

(4.27) (4.28)

Bovenstaande constraint is enkel geldig voor vakken van zes studiepunten. Er zal voor alle vakken met verschillende soorten studiepunten zulke constraints moeten worden opgesteld.

31

De if-voorwaarde van de restrictie zal erop toezien dat enkel examens met het juiste aantal studiepunten (in dit geval dus zes) worden beschouwd en dat er enkel gekeken zal worden naar het verschil in examens van verschillende vakken. De doelfunctie zal er nu als volgt uitzien:

𝑀𝑖𝑛 � � � � 𝑠𝑙𝑎𝑐𝑘𝑣𝑎𝑟𝑒1 ,𝑒2 ,𝑡1 ,𝑡2 𝑒1

𝑒1

𝑡1

(4.29)

𝑡2

De doelfunctie in zijn huidige vorm is nu dus lineair en kan met behulp van CPLEX worden opgelost. Merk op dat deze functie geen kwadratische straf meer berekent maar een lineaire straf (zijnde de slackvariabele). Dit heeft dus als gevolg dat de straf niet langer kwadratisch maar lineair zal stijgen met het tekort aan studietijd. Dit zal bij een kleine dataset echter geen probleem blijken. Merk op dat, door met een slackvariabele t werken, constraint 8 kan worden geherformuleerd. Wanneer men de maximaal toegelaten waarde voor de slackvariabele vermindert, zal de minimale afstand tussen twee examens vergroot worden. Door dit te doen, kan men uiteindelijk constraint 8 weglaten. Beide methodes zullen worden uitgetest.

4.2.3 Model in OPL Het geprogrammeerde model in OPL ILOG kan men terugvinden in bijlage B. In een eerste stap definieert men de vakken, onderdelen, examens en studenten als een range. In plaats van te werken met de unieke vakcodes en studentnummers werd er in een Excel file aan elke vak, onderdeel, examen en student een uniek nummer gegeven (zie bijlage A). Dit zorgt er ten eerste voor dat de dataset veel overzichtelijker zal worden en ten tweede dat het zoeken van een bepaald element dus veel eenvoudiger kan verlopen. De tijdsloten zijn dan weer gedefinieerd als een integere verzameling zonder de zondagen. In een tweede stap wordt er gebruik gemaakt van tuples om eigenschappen aan vakken, onderdelen en examens toe te voegen. Tuples kan men beschouwen als een verzameling van gegevens die allemaal betrekking hebben op het zelfde element. Met behulp van deze tuples verkrijgt men de verdeling van figuur 4.2.

32

VAK vak[o] ONDERDEEL ond[e] EXAMEN

Figuur 4.2: Onderverdeling tuples

Vervolgens worden de lijsten vaks[s], onds[s], exs[s] en StudEx[e] opgesteld. Elk element van deze lijsten bevat een verzameling: zo is vaks[1] bijvoorbeeld de verzameling van alle vakken waarvoor student 1 een examen moet afleggen. Door deze verzamelingen te creëren, kan men tijdens het rekenen eenvoudiger de juiste examens kiezen en hoeft men bijvoorbeeld voor een student enkel de examens te beschouwen waarvan hij examen heeft. Hierdoor is men in staat om het aantal constraints drastisch te verminderen. In het vervolg van het programma worden de doelfunctie en de constraints opgesteld en wordt ervoor gezorgd dat de oplossing eenvoudig kan worden uitgelezen naar een Excel file. Het wegschrijven naar een Excel file kan echter bijzonder veel tijd in beslag nemen omdat odbcconnecties eg traag zijn. Het in ILOG wegschrijven van de oplossing naar het scherm in plaats van naar een extern bestand kan hiervoor een oplossing zijn.

4.2.4 Kleine Dataset Bovenstaande wiskundige modellen zijn getest met een kleine fictieve dataset die alle moeilijkheden van een grote dataset ook bevat (bijlage A). Hiervoor werd een computer gebruikt met een Intel Core Quad Q9300 (2.5Ghz) processor en 4 GB RAM-geheugen. Model met constraint 8 Voor dit model werd er een oplossing gevonden na 5 minuten en 15 seconden rekenen. De uiteindelijke doelfunctie had voor deze dataset waarde nul, wat dus impliceert dat elke student voor elk examen genoeg studeertijd heeft en er dus geen slackvariabelen nodig waren om te voldoen aan de spreidingsconstraints. 33

Figuur 4.3 stelt de planning voor: in de eerste kolom staat de ‘S’ voor student, in de tweede kolom staat ‘E’ voor het examen waarin de student is gepland en in de derde kolom geeft ‘T’ het tijdstip waarom dit examen is gepland. Figuur 4.4 geeft op een compacte manier weer welk examen op welk tijdstip is gepland. Tot slot geeft figuur 4.5 op zijn beurt de volledige planning weer. Uit deze figuur valt het direct op dat de examens mooi gespreid zijn. Het is een handige visuele manier om te controleren dat elke student genoeg studietijd heeft voor al zijn examens.

Figuur 4.3: Planning met constraint 8

Figuur 4.4: Oplossing met constraint 8

34

Figuur 4.5: Oplossing kleine dataset met constraint 8

Er zal nu nog worden nagegaan indien er voldaan is aan alle constraints: 1. Voor elk onderdeel moet elke student in exact één examen worden gepland: Examens 1 en 2 horen beide bij onderdeel 1. Een student mag dus enkel gepland zijn in examen 1 of 2. Wanneer men dit controleert in figuur 4.3, ziet men dat dit steeds het geval is. Dit is ook het geval voor examens van onderdelen 2, 4 en 5. 2. y[e,t] koppelen aan x[s,e,t]: Het zal duidelijk worden bij de constraint 5 of dit weldegelijk het geval is. 3. Elk examen moet één keer worden gepland: Er zijn in totaal 15 examens en men kan zien in figuur 4.4 dat ze inderdaad allemaal gepland zijn. 4. Per examen mag er slechts een maximaal aantal studenten worden gepland: Bij examens 1 tot 4 weet men dat er maximaal drie studenten per examen mogen worden gepland (zie bijlage A). Wanneer men dit controleren in figuur 4.3, dan ziet men dat al deze examens exact drie keer zijn ingepland. Ook indien we de andere examens bekijken merken we dat dit overal klopt. 5. Er mag maximum één examen per vak per tijdstip worden gepland: Wanneer men opnieuw kijkt naar examens 1 tot 4, dan mogen deze niet op hetzelfde tijdstip gepland zijn. We zien in figuur 4.4 dat dit inderdaad niet het geval is. Dit klopt ook voor alle andere vakken met meer dan één examen. Ook aan deze constraint is er dus voldaan. 6. Een student heeft op één tijdstip maximaal één examen: Wanneer men de tabellen uit figuur 4.3 overloopt, dan merkt men dat deze voorwaarde voldaan is voor alle studenten. 7. Tussen twee examens van hetzelfde vak mogen er geen andere examens worden gepland: Dit is het geval bij vakken 1 en 2. Voor vak 1 geldt er dat een student tussen examens 1 of 2 en examens 3 of 4 geen ander examen mag hebben. Dit blijkt inderdaad te kloppen. Voor vak 2 geldt er dat tussen examen 5 en examens 6 of 7 geen ander examen mag vallen. Wanneer we kijken naar figuur 4.4 of figuur 4.5 dan zien we snel dat ook dit klopt.

36

8.

Elke student mag in 24 uur slechts 1 examen afleggen, tenzij de examens behoren tot hetzelfde vak.

In figuur 4.3 kan men gemakkelijk aflezen dat dit inderdaad het geval is voor elke student. Er is dus voldaan aan alle constraints! Model zonder constraint 8 en met beperking van de slackvariabelen Reeds na minder dan 3 minuten werd er een oplossing voor dit model gevonden. Ook hier had de uiteindelijke doelfunctie waarde nul, waardoor ook in dit model elke student genoeg studeertijd heeft. Figuren 4.6 en 4.7 op de volgende pagina stellen de volledige planning voor. Wanneer men voor dit model alle constraints controleert, zal men merken dat ook hier aan alles voldaan is. Model zonder constraint 8 en rekening houdend met de voorkeuren van proffen Ook het model waarbij er rekening wordt gehouden met proffen, werd getest. Om dit te testen werd er voor slechts 1 examen een datum vastgelegd waarop de prof van dit examen niet aanwezig kon zijn. De restrictie zei dat examen 10 mag niet doorgaan op tijdslot 1. Merk op dat dit tijdslot niet werd gebruikt voor dit examen in de modellen zonder voorkeursdata. Na 1.5 uur rekenen, had het model nog geen oplossing gevonden. Er werd gekozen om het programma stop te zetten. Het verbieden om een examen op een bepaald tijslot te plaatsen, maakte het probleem blijkbaar enorm veel complexer. Conclusie Met behulp van deze kleine dataset werd er dus aangetoond dat het mogelijk is om een wiskundig model op te stellen dat in staat is om een goed examenrooster weer te geven. Mits te voldoen aan enkele constraints, voorziet de verkregen examenrooster genoeg spreiding zodat studenten genoeg tijd hebben om te studeren. Het incorporeren van voorkeursdata voor proffen is in dit model jammer genoeg niet gelukt. Dit optimalisatieprobleem met deze beperkingen en vrijheden, zijnde het feit dat we ook studenten moeten inplannen in examens en niet enkel examens in een rooster, was in de literatuur nog niet opgelost. Echter moet men, zoals vele andere onderzoekers die het examination timetabling probleem probeerden aan te pakken via integer programming, tot de vaststelling komen dat het model enkel haalbaar is op kleine schaal en niet voor realistische datasets. Voor bovenstaande modellen werd er namelijk 600 tot 750 MB geheugen gebruikt om tot een oplossing te komen. Een dataset met 1200 studenten oplossen met dit model zal gigantisch veel geheugen vergen en is dus niet realistisch. Om tot een oplossing te komen voor de grote dataset zal er dus heuristisch te werk moeten gegaan worden. 37

Figuur 4.6: Oplossing model met beperking slackvariabelen

Figuur 4.7: Planning model met beperking slackvariabelen

Hoofdstuk 5: Een heuristische aanpak Uit het vorige hoofdstuk bleek dat het oplossen van een het examination timetabling problem voor een realistische dataset niet lukte met behulp van integer programming. Daarom wordt er nu gezocht naar een heuristische methode om tot een oplossing te komen. Aangezien uit de literatuurstudie bleek dat het VNS-algoritme bijzonder goede resultaten gaf, zal deze methode worden toegepast op het planningsprobleem [20]. Het VNS-algoritme behoort tot de klasse van de ‘two stage’-algoritmes. Er zal in dit hoofdstuk in een eerste fase gezocht worden naar een feasible oplossing om deze dan in een tweede fase te optimaliseren. Eens er voor beide fases een methode gevonden is, zal in het volgende hoofdstuk de verkregen heuristiek getoetst worden met behulp van de datasets.

5.1 Eerste fase: Een feasible oplossing opstellen 5.1.1 Definiëren van het probleem De eerste vraag die men zich moeten stellen is: “Wat wordt er verstaan onder een feasible oplossing?”. De feasible oplossing is een oplossing die voldoet aan alle hard constraints. Wanneer we gebruik maken van dezelfde indeling als in het tweede exacte model van het vorige hoofdstuk (vak → onderdeel → examen), kunnen de hard constraints als volgt gedefinieerd worden: 1. Een student kan per tijdslot slechts één examen afleggen. 2. Tussen twee examens van hetzelfde vak mag er geen ander examen van een ander vak worden gepland. 3. Op elk tijdstip mag er slechts één examen per vak worden gepland. 4. Elk examen moet exact één keer worden gepland. Dit zijn de constraints waaraan te allen tijde voldaan moet zijn opdat de oplossing feasible zou zijn. Echter in het vorige hoofdstuk werd de conclusie getrokken dat met deze constraints het voor een realistische probleemgrootte niet haalbaar is om een oplossing te vinden. Om dit probleem op te lossen, kan men in de eerst fase de hard constraints af zwakken om deze dan in een tweede fase terug aan het model toe te voegen. Dit is een erg riskante manier van werken aangezien feasibility in de tweede fase dan niet gegarandeerd is. Het zal echter blijken dat deze methode goede resultaten oplevert voor het probleem besproken in deze masterproef.

39

Wanneer men naar het tweede wiskundige model uit het vorige hoofdstuk kijkt, valt het op te merken dat er twee soorten constraints zijn die heel zwaar doorwegen op het geheugengebruik waardoor het model voor de grote dataset niet oplosbaar is. De eerste constraint die erg zwaar doorweegt op het model is de constraint die instaat voor de spreiding van de examens (de slackvariable-constraints) en de tweede zware constraint is deze die zegt dat er tussen twee examens van hetzelfde vak geen ander examen mag vallen. Door deze constraints in de eerste fase te gaan relaxeren, zal het mogelijk blijken voor onze dataset om tot een oplossing te komen. Deze constraints zullen dus beschouwd worden als relaxable-hard constraints. Dit zijn constraints waaraan uiteindelijk moet voldaan worden, maar die tijdelijk mogen worden gebroken [15]. Er zal in de tweede fase getracht worden te voldoen aan deze constraints door aan elke overtreding een straf toe te kennen en de totale straf te minimaliseren. Door deze constraints niet in rekening te brengen krijgt men nu volgende hard constraints: 1. Een student kan slechts één examen hebben per tijdstip. 2. Op elk tijdstip mag er slechts één examen per vak worden gepland. 3. Elk examen moet exact één keer worden gepland.

Een tweede probleem dat zich nu stelt is de formulering van de doelfunctie aangezien de spreidingsrestricties werden weggelaten. Om dit probleem op te lossen werden er een slackvariabele toevoegd bij de constraint die zegt dat elke student slechts één examen per tijdstip kan afleggen (zie formule 5.6 op pagina 42). De doelfunctie zal dan de minimalisatie zijn van de som van al deze slackvariabelen (formule 5.7). Het spreekt voor zich dat er verwacht wordt dat de doelfunctie de nul-oplossing zal geven, wat impliceert dat alle studenten op elk tijdstip maximaal één examen hebben. Indien dit niet het geval is, bestaat er geen feasible solution en zal het dus geen zin hebben om verder te optimaliseren. In hoofdstuk 6 zal echter blijken dat er weldegelijk een feasible solution bestaat. Een volgende verandering die wordt aangebracht is dat elk examen exact zijn maximum capaciteit aan studenten moet bevatten. Daarom worden er dummy-studenten geïntroduceerd. Wanneer een onderdeel uit bijvoorbeeld 2 examens van maximum 4 studenten bestaat en er zijn in totaal 6 studenten die een examen van dit onderdeel moeten afleggen, dan zullen er 2 dummies worden aangemaakt opdat er voor elk examen exact 4 studenten kunnen worden gepland. Het gebruik van dummies heeft ook een praktisch nut in het optimaliseringproces. Er zal hier in paragraag 5.2.2 dieper op in worden gegaan.

40

5.1.2 Notatie Indices s

Student

v

Vak

o

Onderdeel

e

Examen

t

Tijdslot: gaat van 1 tot 54. Elke dag heeft 2 tijdsloten en we hebben 4 weken examenperiode. Enkel de zondagen werden weggelaten uit deze verzameling.

Variabelen x[s,e,t]

Binaire variabele die 1 is indien student s examen e aflegt in tijdslot t.

y[e,t]

Binaire variabele die 1 is indien examen e doorgaat in tijdslot t.

slack[s,t]

Deze variabele geeft weer hoeveel studenten er meer dan één examen per tijdslot hebben.

Parameters onds[s]

Lijst met onderdelen waarvan student s examen moet afleggen.

exs[s]

Lijst met alle mogelijke examens die student s kan afleggen.

studEx[e]

Lijst met studenten die het examen e kunnen afleggen.

aantalOnd[v]

Integer die het aantal onderdelen horend bij vak v weergeeft. (=1 of 2)

vak[o]

Integer die weergeeft bij welk vak het onderdeel o hoort.

maxStud[o]

Integer die het maximale aantal studenten per onderdeel weergeeft.

ond[e]

Integer die weergeeft bij welk onderdeel examen e hoort.

SP[e]

Het aantal studiepunten van een examen e.

Zoals men kan merken, is er dus niet veel veranderd aan de variabelen en parameters. Bij de doelfunctie en constraints zullen er zoals besproken wel enkele veranderingen zijn.

5.1.3 Formulering Constraints 1.

Voor elk onderdeel moet een student in exact één examen worden gepland: �

2.

�

𝑡 𝑒: 𝑜𝑛𝑑[𝑒]=𝑜

𝑥𝑠,𝑒,𝑡 = 1

y[e,t] koppelen aan x[s,e,t]: 𝑦𝑒,𝑡 ≥ 𝑥𝑠,𝑒,𝑡

∀𝑠, 𝑜 ∈ 𝑜𝑛𝑑𝑠𝑠

(5.1)

∀𝑠, 𝑒 ∈ 𝑒𝑥𝑠𝑠 , 𝑡

(5.2) 41

3.

4.

Elk examen moet exact één keer worden gepland: � 𝑦𝑒,𝑡 = 1 𝑡

𝑠∈𝑠𝑡𝑢𝑑𝐸𝑥𝑒

𝑥𝑠,𝑒,𝑡 = 𝑦𝑒,𝑡 𝑚𝑎𝑥𝑆𝑡𝑢𝑑[𝑜𝑛𝑑[𝑒]]

∀𝑒, 𝑡

(5.4)

∀𝑡, 𝑣

(5.5)

∀𝑠, 𝑡

(5.6)

Er mag maximum één examen per vak per tijdstip worden gepland: �

6.

(5.3)

Per examen mag er slechts een maximum aantal studenten worden gepland: �

5.

∀𝑒

𝑒:𝑣𝑎𝑘[𝑜𝑛𝑑[𝑒]]=𝑣

𝑦𝑒,𝑡 ≤ 1

Een student heeft op één tijdstip maximum één examen: � 𝑥𝑠,𝑒,𝑡 − 𝑠𝑙𝑎𝑐𝑘𝑠,𝑡 ≤ 1

𝑒∈𝑒𝑥𝑠𝑠

Doelfunctie De doelfunctie is dus een minimalisatiefunctie van de slackvariabele:

𝑀𝑖𝑛 � � 𝑠𝑙𝑎𝑐𝑘𝑠,𝑡 𝑠

(5.7)

𝑡

De oplossing van dit model zal, indien de doelfunctie gelijk is aan nul, een feasible examenrooster zijn. Het spreekt voor zich dat de code in ILOG volledig analoog zal zijn aan de code geschreven voor het tweede wiskundig model uit vorig hoofdstuk (bijlage B). Voor uitleg betreffende de code kan u dus terecht in paragraaf 4.2.3. De volledige code van dit model is terug te vinden in bijlage I.

5.2 Tweede fase: optimaliseren (theoretische achtergrond) Eens er een feasible oplossing gevonden is, moet deze worden geoptimaliseerd. Zoals vermeld in het begin van dit hoofdstuk zal er hiervoor gebruik gemaakt worden van het VNS-algoritme opgesteld door E.K. Burke et al. [20, 27].

42

5.2.1 Globale concept van VNS Het concept van het VNS-algoritme is dat er per iteratie een nieuwe neighbourhood wordt geselecteerd om zo uit eventuele locale minima te ontsnappen. Eens er een nieuwe feasible neighbourhood gevonden is, wordt er met behulp van een local search gezocht naar een lokaal optimum. Wanneer de oplossing een betere oplossing geeft dan de tot dan toe beste gevonden oplossing, zal de beste oplossing worden vervangen door de nieuwe oplossing. Dit doet men totdat er een stopvoorwaarde is bereikt. Als stopvoorwaarde is er in deze masterproef gekozen voor een vooraf bepaald aantal opeenvolgende iteraties zonder verbetering. Men kan als stopvoorwaarde bijvoorbeeld ook het totale maximale iteraties kiezen of de maximale tijd dat het algoritme mag lopen. De werking van het VNS-algoritme is weergegeven in de flowchart van figuur 5.1. In onderstaande flowchart kan men duidelijk de pseudocode uit paragraaf 2.3.1 herkennen. Start Zoek een feasible oplossing Stel k = 1 Genereer een random oplossing x´ uit de kde neighbourhood

k++

Zoek mbv local search een lokaal minimum x´´ nee nee

1

teller++

ja

nee

2

3

ja

ja

Stel x = x´´ en stel teller = 0 Stop

Legende: 1: Is straf x´´< straf x? 2: Is teller = stopconditie? 3: Is k = kmax? Figuur 5.1: Flowchart VNS-algoritme

43

Zoals eerder vermeld zijn er twee soorten straffen die een rol spelen. De eerste straf heeft betrekking op de spreiding van de examens bij een welbepaalde student. Hiervoor zal de reeds eerder gedefinieerde formule 5.8 worden gebruikt. Alle uitleg betreffende deze formule is terug te vinden in paragraaf 4.1.2.

𝑆𝑡𝑟𝑎𝑓1𝑠 = � � 𝑥𝑠,𝑒,𝑡 �

min(2𝑆𝑃𝑒 ,𝑡−1)

𝑒∈𝑒𝑥𝑠𝑠 𝑡

� 𝑗=1

5

� 𝑥𝑠,𝑧,𝑡−𝑗 �(2𝑆𝑃𝑒 − 𝑗 + 1)2 (11 − 𝑆𝑃𝑒 )3 ��

𝑧∉𝑒𝑥[𝑣]

a∀𝑠, 𝑣: 𝑒 ∈ 𝑒𝑥[𝑣]

(5.8)

a

Aangezien de constraint die zegt dat een student per 24 uur slechts één examen mag hebben gerelaxeerd werd, zal er een extra straf worden toegekend bovenop de spreidingsstraf indien er niet voldaan is aan deze constraint. Wanneer een student dus binnen de 24 uur twee examens heeft van verschillende vakken, zal er bovenop straf1 een extra straf van 50000 worden bijgeteld. Vervolgens werd ook de constraint gerelaxeerd die zegt dat er tussen twee examens van hetzelfde vak geen ander examen mag vallen. Om ervoor te zorgen dat de uiteindelijke oplossing ook aan deze constraint voldoet, wordt er een tweede straf (straf2) geïntroduceerd. Wanneer er aan deze restrictie niet voldaan is, zal er ook hier een extra straf van 50000 bijgeteld worden. Wanneer er wel voldaan is aan deze restrictie, is deze straf gelijk aan nul. De waarde voor de extra straffen is groot genoeg gekozen opdat het algoritme steeds geneigd zal zijn te voldoen aan deze constraints. Indien men merkt dat het algoritme geen goede resultaten geeft, kan men deze waarde later nog aanpassen. Dit zal echter niet nodig blijken. De totale straf voor een student bedraagt de som van straf1 en straf2. Het doel van het VNSalgoritme is om de globale straf, gesommeerd over alle studenten, te minimaliseren.

5.2.2 De neighbourhoods Er wordt in deze masterproef gebruik gemaakt van zes verschillende neighbourhoods. De neighbourhoods die gekozen werden, zijn niet allemaal dezelfde als deze gebruikt door E.K. Burke et al. in hun algoritme [20]. Zo zijn er in deze masterproef bijvoorbeeld geen neighbourhoods die volledige tijdsloten verplaatsen. Er werd namelijk opgemerkt dat wanneer het algoritme aan het lopen was, deze neighbourhoods zo goed als nooit leidden tot een betere oplossing. De reden hiervoor is dat wanneer een tijdslot wordt verplaatst, de kans heel groot is dat er een student zal zijn die opeens weer tussen twee examens van hetzelfde vak een ander examen heeft. Dit heeft als gevolg dat zelfs na de local search de straf van de gevonden oplossing meestal hoger is dan de straf van de tot dan toe beste oplossing. 44

Omdat deze neighbourhoods dus niet bijdroegen tot een betere oplossing en enkel rekentijd in beslag namen, werd er geopteerd deze weg te laten uit het algoritme. Ook werd er een nieuwe neighbourhood geïntroduceerd. Er wordt namelijk een neighbourhood gebruikt die studenten tussen examens van hetzelfde onderdeel verwisselen. Op deze manier houdt men ook rekening met het feit dat studenten voor bepaalde onderdelen in verschillende examens kunnen worden gepland, waardoor het algoritme weer heel wat meer vrijheden krijgt om op zoek te gaan naar een beter oplossing. In deze neighbourhood komt ook het nut van het gebruik van dummies naar boven. In plaats van altijd studenten met studenten te wisselen, kunnen er ook studenten met dummies worden gewisseld. Dit creëert opnieuw extra vrijheden waardoor er dus nog meer neighbourhoods kunnen worden aangesproken en ons algoritme nog beter zal kunnen werken. De zes neighbourhoods die werden gebruik, zijn: 1.

Het verwisselen van twee examens.

2.

Het verwisselen van twee studenten in verschillende examens met hetzelfde onderdeel.

3.

Het verplaatsen van twee examens.

4.

Het verplaatsen van drie examens.

5.

Het verplaatsen van vier examens.

6.

Kempe-chain neighbourhood.

Alle neighbourhoods zullen enkel feasible oplossingen toelaten. Bij elke verwisseling of verplaatsing zal dan ook de feasibility moeten worden gecontroleerd (of met andere woorden of de nieuwe oplossing ook voldoet aan de daarnet gedefinieerde hard constraints). Hoe deze neighbourhoods geprogrammeerd werden, zal in één paragraaf 5.3.2 van dit hoofdstuk worden besproken.

5.2.3 Local Search Als local search wordt er gebruik gemaakt van een simpele steepest descent zoekmethode. Eens er een nieuwe feasible oplossing is gegenereerd met behulp van één van de neighbourhoods, zal er een random examen gekozen worden en op zoek gegaan worden naar het tijdslot met de laagste straf voor dit examen. Merk op dat er voor de local search dus gebruik gemaakt wordt van een single-move neighbourhood (het verplaatsen van één random gekozen examen) om op deze manier een lokaal minimum te bereiken.

45

5.3 Tweede fase: optimaliseren (implementatie) In deze masterproef werd er geopteerd om het VNS-algoritme in Java te programmeren. Java werd als programmeertaal gekozen omdat deze taal relatief eenvoudig is en heel wat mogelijkheden biedt. Tijdens het programmeren van dit algoritme werd er beroep gedaan op de cursus informatica die in de eerste bachelor ingenieurswetenschappen aan onze faculteit wordt onderwezen [46]. Er werd gebruik gemaakt van het programma Eclipse om de heuristiek te runnen.

5.3.1 De verschillende klasses

Java is een objectgeoriënteerde programmeertaal die toelaat om gebruik te maken van het klassesysteem. Met behulp van deze klasses is men in staat om het programma veel duidelijker te structureren. In totaal werden er drie verschillende klasses aangemaakt: de klasse Examen, de klasse Timeslot en de klasse Pair. De code is terug te vinden in bijlage C. De eerste klasse die werd aangemaakt, is de klasse Examen. Elke element uit deze klasse zal de volgende gegevens bevatten: -

Een uniek examennummer.

-

Het nummer van het tijdslot waarin dit examen is gepland.

-

Het nummer van het onderdeel waartoe het beschouwde examen behoort.

-

Het nummer van het vak waartoe dit examen behoort.

-

Het aantal studiepunten van dit examen.

-

Een lijst met studenten die dit examen zullen afleggen.

Vervolgens is er de tweede klasse Timeslot. Deze klasse bevat twee gegevens: -

Een uniek tijdslotnummer.

-

Een lijst met examens die zijn gepland in het beschouwde tijdslot.

En tot slot is er nog de klasse Pair. Aangezien elke methode in Java slechts één element kan teruggeven, werd deze klasse aangemaakt om ervoor te zorgen dat er steeds genoeg informatieoverdracht bestaat tussen verschillende methodes. Elementen uit de klasse Pair bevatten de volgende gegevens:

46

-

Een rij van examens: op deze manier kan alle data van alle examens worden doorgegeven.

-

Een rij van alle tijdsloten.

-

Een rij met lengte gelijk aan het aantal studenten en elk element van de rij is een ArrayList. Elk element van de rij zal een student voorstellen en de ArrayList bevat alle examens die deze student zal afleggen.

-

Een integere waarde die de straf van een oplossing weergeeft.

Wanneer men bijvoorbeeld een nieuwe oplossing zoekt met behulp van één van de neighbourhoods, dan zal deze neighbourhood elk van deze elementen van de klasse Pair hebben aangepast. Om alle gegevens uit deze methode te halen en door te geven aan andere methodes, zal er dus gebruik worden gemaakt van de klasse Pair.

5.3.2 De neighbourhoods

In deze paragraaf wordt er een korte uitleg geven over de verschillende neighbourhoods. De code is terug te vinden in bijlage D.

Switchen van twee examens Zoals men kan aflezen uit de flowchart van figuur 5.2 op de volgende pagina, zullen er eerst twee willekeurige examens worden gekozen. Wanneer beide examens (ex1 en ex2) niet gelijk zijn aan elkaar, zullen de examens verwisseld worden. Het verwisselen van de examens houdt in dat men het timeslotnummer van examen e1 zal veranderen naar dat van examen e2 en dat men examen e1 verwijdert uit zijn tijdslot en toevoegt aan het tijdslot van examen e2. Hetzelfde doet men met examen e2. Vervolgens zal er gecontroleerd worden of deze nieuwe oplossing, gegeneerd door het verwisselen van de twee examens, feasible is. De verplaatsing van examen e1 naar het tijdslot van examen e2 zal feasible zijn wanneer er in het nieuwe tijdslot geen ander examen is gepland van een vak waartoe e1 behoort en indien er geen studenten zijn die, door de verplaatsing van examen e1 naar het nieuwe tijdslot, meer dan één examen hebben op dat tijdslot. Indien er aan deze voorwaarden is voldaan, zal er op deze neighbourhood een local search worden toegepast. Wanneer er echter niet voldaan is aan de voorwaarden, zullen er nieuwe examens e1 en e2 worden gekozen.

47

Om te voorkomen dat deze neighbourhood in een lus komt te zitten en geen feasible oplossingen vindt, werd er een stopvoorwaarde verbonden aan deze neighbourhood. Indien er tot honderd keer na elkaar geen feasible oplossing wordt gevonden, zal de local search-methode worden toegepast op de oude oplossing. De flowchart van deze neighbourhood ziet er als volgt uit: Kies examen 1 Kies examen 2 ja

1

nee

nee verwissel nee

2

ja

3

stop++

ja naar local search

Neem initiële oplossing

Legende: 1: Is examen 1 = examen 2? 2: Leidt de verwisseling van beide examens tot een feasible solution? 3: Is de stopvoorwaarde bereikt? Figuur 5.2: Flowchart examens verwisselen

Verplaatsen van 2 of meerdere examens Het verplaatsen van twee examens gebeurt volledig gelijkaardig. In plaats dat men nu de tijdsloten neemt van de twee examens die werden gekozen, zal men nu ook twee random tijdsloten kiezen. Het enige verschil met de vorige neighbourhood is dat men hier zal moeten controleren of de gekozen tijdsloten op een zondag vallen. Indien dit het geval is, zal er een nieuw tijslot moeten worden gekozen. Verder zal er geen verschil zijn met het switchen van twee examens. Ook met meer dan twee examens verloopt het proces volledig analoog.

48

Switchen van 2 studenten Figuur 5.3 geeft de flowchart weer van deze neighbourhood. Kies een onderdeel met > 1 examen Kies stud1 ja

1 nee

Zoek dummy ja nee

2

Kies stud2

3 nee

ja 4

5

stop++

Neem initiële oplossing

ja

nee

Wissel studenten

naar local search

Legende: 1: 2: 3: 4: 5:

Is student 1 een dummy? Hebben we een dummy kunnen vinden? Is het examen van student 2 = examen van student 1? Geeft het wisselen van beide studenten een feasible oplossing? Is de stopvoorwaarde bereikt? Figuur 5.3: Flowchart studenten verwisselen

Wanneer men twee studenten wil wisselen van plaats, zal er eerst een onderdeel moeten gekozen worden met meer dan twee examens (het is namelijk nutteloos om twee studenten binnen eenzelfde examen te wisselen). Eens er een onderdeel gekozen is, kiest men een willekeurige student die een examen van dit onderdeel moet afleggen. Er zal worden gezorgd dat deze student geen dummy is.

49

Vervolgens gaat men op zoek naar een dummy die gepland is in één van de examens van hetzelfde onderdeel, maar niet hetzelfde examen van student 1 is. Indien er zo een dummy gevonden wordt, kan men controleren of het wisselen van deze student en dummy zal resulteren in een feasible rooster. Wanneer er echter geen dummy gevonden werd, zal er op zoek gegaan worden naar een gewone student. Opnieuw zal ervoor gezorgd worden dat beide studenten in verschillende examens van hetzelfde onderdeel gepland zijn. Nu dat we twee studenten of een student en een dummy gevonden hebben, kan men de feasibility controleren. Men hoeft hiervoor enkel te controleren of het wisselen van beide studenten ervoor zal zorgen dat een student plots meer dan één examen heeft op één tijdslot. Indien de verkregen oplossing een feasible oplossing is, zal deze worden doorgestuurd naar de local search methode. Ook hier wordt er gebruik gemaakt van een stopvoorwaarde om te voorkomen dat deze neighbourhood in een lus komt te zitten wanneer er geen feasible oplossingen zijn.

Kempe Chain Zoals men kan aflezen uit de flowchart van figuur 5.4 op de volgende pagina, zal er eerst een willekeurig examen ex1 en tijdslot t2 worden gekozen. Wanneer het gekozen tijdslot een zondag blijkt te zijn, zal er een nieuw tijdslot worden gekozen. Vervolgens zal men controleren of de verplaatsing van examen ex1 naar tijdslot t2 een feasible oplossing geeft. Wanneer dit feasible blijkt te zijn, zal deze neighbourhood in essentie een single move neighbourhood zijn, aangezien er dan enkel één examen kan worden verschoven naar een ander tijdslot. Wanneer de verplaatsing van het examen ex1 naar tijdslot t2 niet in een feasible oplossing resulteert, zullen de examens, waarmee ex1 in conflict is worden verplaatst naar t1 (het oorspronkelijke tijdslot van ex1). Er zal dus met behulp van een kempe chain feasibility worden gegarandeerd. Een uitgebreide uitleg van deze methode is terug te vinden in paragraaf 2.3.1. Er wordt in de flowchart gebruik gemaakt van ‘kempe chains’ k1 en k2. Deze worden als volgt gedefinieerd: kempe chain k1 is de verzamling van examens uit tijdslot t1 waarmee examens uit tijdslot t2 in conflict komen en kempe chain k2 is dan de verzameling van examens uit tijdslot t2 waarmee examens uit tijdslot t1 in conflict komen. Initieel zal k1 dus enkel examen ex1 bevatten. Vervolgens gaat men, met behulp van k1, kempe chain k2 opstellen. Wanneer men nu net het omgekeerde doet, namelijk k1 opnieuw opstellen aan de hand van k2, kan het zijn dat er examens zijn bijgekomen waarmee er een conflict is. Eens de lengte van k1 niet meer verandert, zal men alle examens gevonden hebben die in conflict zijn met elkaar. Dit kan men duidelijk zien met behulp van het voorbeeld uit paragraaf 2.3.1.

50

Uit figuur 2.4 haalt men dat k1 = {1,2,3} en k2 = {5,8}. Wanneer men nu opnieuw k1 vertrekkende van k2 opstelt, zal k1 steeds dezelfde verzameling blijven aangezien er, vertrekkend vanuit examen 1, enkel een conflict bestaat tussen deze examens. Dus eens de lengte van k1 niet meer verandert, werden alle conflicten gevonden. Wanneer men alle examens uit beide kempe chains verwisselt van tijdslot, zal men steeds een feasible oplossing krijgen. Echter, om te voorkomen dat de oplossing na het verschuiven van de examens toch niet feasible zou zijn, werd er hier een extra controle geprogrammeerd. Maar normaal gezien zou deze overbodig moeten zijn. Kies een examen ex1 Kies een tijdslot t2 ja

1

nee

2

nee

Maak kempe chain k1 aan met ex1 als enige element

ja Bepaal lengte van k1 Verplaats examen(s) nee

Neem initiële oplossing

4 ja

Maak kempe chain k2 Maak kempe chain k1 ja

3

nee

Naar local search Legende: 1: 2: 3: 4:

Is tijdslot t2 een zondag? Is de verplaatsing van ex1 naar t2 feasible? Is de lengte van k1 verandert? Is de oplossing feasible? (normaal gezien wel) Figuur 5.4: Flowchart Kempe Chain neighbourhood

51

5.3.3 Local search Eens men een nieuwe oplossing heeft verkregen dankzij één van de neighbourhoods, zal men op zoek gaan naar een locaal minimum. Zoals eerder vermeld, wordt er hiervoor een local search methode gebruikt die gebaseerd is op de single-move neighbourhood.

Kies examen ex1 Stel i = 0

i++

ja

1 nee ja

Return beste resultaat

2 nee

nee

3 ja

Wijzig gegevens Bereken straf nee

4

ja

Beste resultaat = huidige oplossing

Legende: 1: 2: 3: 4:

Is i = aantal tijdsloten? Is tijdslot i een zondag? Is de verplaatsing van examen ex1 naar tijdslot i feasible? Is de oplossing beter dan voordien? Figuur 5.5: Flowchart van de ‘local search’-methode

52

Zoals in de flowchart in figuur 5.5 staat getekend, begint men met het kiezen van een willekeurig examen ex1. Vervolgens komt men in een for-lus, gaande van nul tot het aantal tijdsloten (in ons geval zijn dat er dus 54). In een tweede stap zal er gecontroleerd worden of het verplaatsen van examen ex1 naar het tijdslot feasible is. Indien dit het geval is, zal de straf berekend worden. Indien deze oplossing beter is dan de tot dan toe best gevonden oplossing van de local search, zal men deze oplossing opslaan als tijdelijk beste oplossing. Wanneer de for-lus volledig is doorlopen, wordt het beste resultaat verkregen door de local search weergegeven. Indien deze oplossing beter is dan de tot dan toe beste oplossing van het probleem, zal de beste oplossing vervangen worden door de nieuwe oplossing en kan er een nieuwe neighbourhood worden gezocht. Samengevat wordt er bij de local search methode dus een random vak gekozen en kijkt men welk tijdslot de laagste straf zal geven voor dit vak en wordt het gekozen examen in het beste tijdslot verplaatst.

5.3.4 In- en uitlezen van gegevens Aangezien het in Java erg complex is om gegevens in te lezen vanuit Excel bestand, worden eerst alle gegevens omgezet naar een txt bestand om deze dan als tabel in te lezen. In een tweede stadium wordt deze tabel gesplitst en creëert men op deze manier dezelfde matrix als deze uit het Excel bestand. Ook zullen alle gegevens worden uitgelezen naar txt bestanden. Dankzij het gebruik van tabs kunnen deze files achteraf heel erg simpel worden omgezet naar Excel bestanden.

53

Hoofdstuk 6: Testen van het algoritme 6.1 Dataset Nu het algoritme volledig is opgesteld, is het tijd om het te testen. Dit gebeurt met behulp van de, in hoofdstuk 3, opgestelde dataset. Echter, vooraleer het algoritme kan worden testen, moet men de data aanpassen zodat deze op een eenvoudige manier kan worden ingelezen. In een eerste fase zal er dus gebruik gemaakt worden van integer programming om tot een feasible oplossing te komen. De Excel files waaruit alle gegevens worden uitgelezen, zijn terug te vinden in bijlages G en K. Alle tabellen in dit bestand zijn eenvoudig op te stellen met behulp van enkele simpele Excel formules. Enkel de lijst StudEx, de lijst met alle mogelijke examens die elke student kan afleggen, werd aangemaakt met behulp van een macro. De werking van de macro kan als volgt worden uitgelegd: stel een student moet examen afleggen van vakken 1, 2 en 3. Vakken 1 en 2 zijn vakken met een enkel schriftelijk examen. Zo hoort bij vak 1 examen 1 en bij vak 2 examen 2. Het examen van 3 daarentegen is een mondeling examen en hier zijn er in totaal 5 mogelijke examens voor gepland (examens 3 tot 7). Aangezien er op voorhand niet wordt beslist welke student er in welk examen wordt ingedeeld, kan de student initieel in één van vijf mogelijke examens worden gepland. Dit heeft als gevolg dat het totaal aantal mogelijke examens die deze student kan afleggen gelijk is aan examens 1 tot 7. Wanneer men dit manueel moet doen voor bijna 1200 studenten, is dit een onbegonnen werk. Daarom wordt er gebruikt gemaakt van een macro in Excel die, aan de hand van alle vakken die een student moet afleggen, een lijst opstelt met alle mogelijke examens per student. Deze macro is terug te vinden in bijlage J. Ook zal men er op moeten toezien dat er voor elk examen genoeg dummies worden aangemaakt, maar ook dit is manueel heel eenvoudig te doen in Excel. Uiteindelijk verkrijgt men een lijst van 1182 studenten en 94 dummies en zijn er 123 vakken of 151 onderdelen waarvan een examen moet worden afgenomen. Dit resulteert in 271 verschillende examens die moeten worden gepland. Wanneer men dan met behulp van de Marco de lijst StudEx opstelt, verkrijgt men in totaal 13104 examens die kunnen worden gepland voor in totaal 1276 studenten. Deze gegevens zijn terug te vinden in bijlage G.

54

6.2 Eerste fase Om tot een feasible oplossing te komen hebben we bovenstaande dataset opgelost met behulp van het wiskundige model uitgelegd in paragraaf 5.1. Hiervoor hebben we een computer met 8GB RAM-geheugen en een intel i5 2540 sandybridge processor gebruikt. Na 50 minuten rekenen had OPL reeds een oplossing gevonden met een waarde voor de doelfunctie de gelijk aan nul was. Er is dus met andere woorden een feasible oplossing gevonden (zie bijlage K). Het wegschrijven naar een Excel bestand duurde daarentegen nog eens 12 uur! Zoals eerder besproken, komt dit doordat de odbc connecties erg traag zijn en kan dit eenvoudig worden opgelost door de oplossing in OPL te laten printen op het scherm zodat we nadien deze oplossing simpelweg kunnen kopiëren naar een Excel bestand.

6.3 Tweede fase Nadat er een feasible oplossing is gevonden, is het de bedoeling deze te optimaliseren. De straf van de initiële oplossing bedroeg 58868334.In totaal werd de VNS-heuristiek 10 keer toegepast, telkens met 1000 iteraties zonder verbetering als stopvoorwaarde. Om de heuristiek te runnen, werd er gebruik gemaakt van een computer met een Intel Core Duo CPU 75800 van 2Ghz met 3032MB RAM. De beste oplossing is terug te vinden in bijlage M. Elke run gaf een feasible rooster weer, wat dus impliceert dat er geen studenten zijn die twee examens van verschillende vakken moeten afleggen op 24 uur en dat er geen enkele student is die tussen twee examens van hetzelfde vak examen van een ander vak moet afleggen. In tabel 6.1 staan de resultaten van elke run weergegeven.

Gemiddeld:

Straf

Aantal Iteraties

694816

43737

720375

54907

740325

60276

757334

57565

789116

55012

823164

48413

835503

42554

840726

25545

892595

33472

924346

43003

801830

46449 Tabel 6.1

55

De beste score die werd verkregen met de heuristiek is gelijk aan 694816. Hiervoor had de heuristiek 2 uur 22 minuten nodig, wat dus neerkomt op ongeveer 0,2 seconden per iteratie. In figuur 6.1 werd het verloop van de straf in functie van het aantal iteraties uitgezet voor de oplossing met straf gelijk aan 924346. Men merkt duidelijk op dat de straf drastisch daalt in de eerste duizend iteraties. Dit komt doordat de oplossing uit fase 1 niet feasible is en enorm veel overtredingen bevat. Deze overtredingen worden in het begin weg gefilterd aangezien er een erg grote reductie (50000) aan vast hangt. Eens deze overtredingen niet meer in het rooster aanwezig zijn, zal een local search slechts kleine verbeteringen geven. Hierdoor zal de straf slechts heel langzaam dalen naarmate het aantal iteraties stijgt. 6,00E+07 5,00E+07

Totale Straf

4,00E+07 3,00E+07 2,00E+07 1,00E+07 0,00E+00 0

469

1739

4435

10855

22973

Aantal iteraties

Figuur 6.1: Straf ifv aantal iteraties 1

6.4 Vergelijking met het rooster opgesteld door de FSA Wanneer men de examenrooster die het FSA heeft opgesteld gaat onderzoeken, merkt men dat er vier studenten zijn met een infeasible rooster (zie bijlage L)! Drie studenten (studenten 986, 1030 en 1088) hebben namelijk binnen de 24 twee examens van een verschillend vak en één student (student 1094) heeft zelfs twee verschillende examens op hetzelfde tijdslot. De totale straf van deze rooster bedraagt 1189982. Het rooster opgesteld met behulp van de VNSheuristiek heeft dus een veel lagere score dan de manueel opgestelde rooster. Bovendien is het manueel opgestelde rooster niet feasible, daar waar de VNS-heuristiek wel een feasible rooster geeft als resultaat. 56

Wanneer de studenten worden uitgezet tegenover hun straf, krijgt men de volgende grafiek: 600

Aantal Studenten

500 400 300 200 100

10500

10000

9500

9000

8500

8000

7500

7000

6500

6000

5500

5000

4500

4000

3500

3000

2500

1500

2000

1000

500

0

0

Straf Figuur 6.2: Aantal studenten in functie van hun straf

Bovenstaande figuur moet men als volgt interpreteren: de balkjes boven een getal (straf) geven het aantal studenten weer tussen deze straf en de vorige straf. Zo stellen de balkjes boven een straf van 500 het aantal studenten voor met een straf tussen 0 en 500. De zwarte balken zijn deze voor het rooster gevonden met de heuristiek, de grijze balken representeren het manueel opgestelde rooster. Men ziet dus op bovenstaande grafiek dat er heel wat meer studenten zijn (ongeveer de helft) met een rooster met score die gelijk is aan nul bij de heuristische methode. Er zijn dus veel meer studenten met een perfect rooster (578 studenten vs 390 studenten). Er zijn in totaal 3 studenten met een erg slechte rooster (>8000 strafpunten): Student

Straf

310

8030

264

8814

374

10331 Tabel 6.2

Bij de eerste twee studenten is de straf enorm hoog omdat alle examens die deze studenten moeten afleggen ofwel in het begin van de examenperiode zijn gepland, ofwel op het einde. Hierdoor hebben beide studenten voor twee tot drie examens te weinig studietijd.

57

De student met de slechtste rooster is een student die examen moet afleggen van maar liefst acht verschillende vakken, waardoor het erg moeilijk wordt om voor een goede spreiding te zorgen voor deze student. Deze student heeft in de FSA-rooster een straf van 5979 strafpunten. Bij de door de FSA opgestelde rooster heeft de student met de zwaarste straf (student 639) een straf van 8802. Ook deze student heeft acht verschillende vakken opgenomen in zijn curriculum. Ter vergelijking: deze student heeft in de rooster opgesteld met behulp van de VNS-heuristiek een straf van 6861 strafpunten. Tot slot moet er opgemerkt worden dat men deze twee roosters niet zo maar mag vergelijken. Bij de FSA-rooster werd er bij het plannen ook rekening gehouden met de bachelorvakken. Studenten die dus vakken van zowel de bachelor als de master in hun curriculum hebben opgenomen, zullen bij de FSA-rooster waarschijnlijk een slechtere score hebben. Hoe dan ook kan er geconcludeerd worden dat het opstellen van een examenrooster met behulp van het VNS-algoritme tot een mooie, feasible oplossing zal leiden. Namelijk ongeveer de helft van de studenten heeft een perfect rooster toegewezen gekregen en slechts 3.5% van de studenten kreeg een slecht rooster (>4000 strafpunten). Er zitten hier echter ook studenten tussen met een heel zwaar curriculum. Deze studenten zijn er zich echter van bewust dat, door een zwaar curriculum op te nemen, de kans bestaat dat ze een slecht examenrooster zullen toegewezen krijgen.

58

Hoofdstuk 7: Conclusie Het opstellen van een optimaal examenrooster met behulp van integer programming bleek enkel te lukken voor een kleine dataset. Ook werd er geen rekening gehouden met de voorkeuren van de proffen (wat volgens de FSA bij het manueel opstellen ook niet gebeurt). De combinatie van integer progamming om tot een feasible oplossing te komen en een VNS-heuristiek om deze oplossing te optimaliseren, leverde dan wel weer goede restultaten. Het grootste voordeel dat het gebruik van een VNS heuristiek biedt is dat er heel erg weinig parameters moeten worden ingesteld. Er kunnen ook heel gemakkelijk neighbourhoods worden toegevoegd of weggehaald uit dit algoritme. Er zijn echter nog een paar punten waar deze heuristiek kan op verbeterd worden. De in deze masterproef gebruikte VNS-heuristiek is relatief eenvoudig. Wanneer men een veel complexere hybride VNS-heuristiek in combinatie met genetisch algoritmes toepast [27], kan men tot nog betere oplossing komen. Ook kan er nog gezocht worden of er eventueel met de voorkeuren van professoren rekening kan gehouden worden. Let wel: dit zal ervoor zorgen dat de zoekruimte verkleint en dus zullen de mogelijke feasible neighbourhoods beperkt worden, wat de werking van de VNS-heuristiek zal bemoeilijken. Om aan de faculteit ingenieurswetenschappen en architectuur van de Universiteit van Gent een geautomatiseerd systeem te gebruiken dat examenroosters opstelt, zal het centrale databasesysteem (OASIS genaamd) moeten worden aangepast. Momenteel wordt alle informatie omtrent examens doorgegeven aan de FSA in de vorm van opmerkingen. Zo zal een professor bijvoorbeeld schrijven: “Graag een mondeling en schriftelijk examen. Het mondeling moet doorgaan in groepen van maximum 10 studenten en voor het schriftelijk zit iedereen samen.” Zulke informatie moet dus momenteel manueel worden omgezet naar binaire en integere parameters. Dit vergt heel veel werk en neemt behoorlijk veel tijd in beslag. Een compleet andere manier van examenroosters opstellen is om de studenten zelf te laten kiezen. Zo kan men professoren in het begin van het semester twee à drie verschillende data doorgeven waarop een student een examen kan afleggen. Stel: een student moet examen afleggen van bijvoorbeeld vier verschillende vakken en elke prof geeft 3 data door. Dan heeft deze student in het beste geval keuze uit 34 (= 81) roosters om uit te kiezen. Op deze manier wordt er rekening gehouden met de voorkeursdata van de proffen en kan een student in het begin van het semester zelf zijn optimaal rooster kiezen. Dit geeft als bijkomend voordeel dat de student al van ver op voorhand zijn rooster kent en dus op voorhand weet hoeveel tijd hij heeft om een examen te herhalen.

59

60

Referenties [1]

P & NP, http://explorations.chasrmartin.com/2008/11/24/what-are-p-np-complete-andnp-hard/

[2]

NP-complete, http://en.wikipedia.org/wiki/NP-complete

[3]

NP-hard, http://en.wikipedia.org/wiki/NP-hard

[4]

Rhydian Lewis, A Survey of metaheuristic-based techniques for University Timetabling Problems, OR Spectrum, Volume 30, Number 1, 2008, pp. 167-190

[5]

D. deWerra, The Combinatorics of timetabling, European Journal of Operations Research, Volume 96, Issue 3, 1997, pp. 504-513

[6]

Wayne L. Winston, Operations Research (fourth edition) Applications and Algorithms, Indiana University, Thomson Brooks/Cole, 2004

[7]

Mixed

Integer

Programming

Basis,

http://www.gurobi.com/resources/getting-

started/mip-basics [8]

R. Bosch & M. Trick, Integer Programming, Search Methodologies, 2005, pp. 69-95

[9]

Convens Gerrie, Ontwikkelen van een methode voor studentvriendelijke examenplanning aan de Faculteit Ingenieurswetenschappen, Katholieke Universiteit Leuven, 2009

[10]

K. Schimmelpfeng & S. Helber, Application of a real-world university-course timetabling model solved by integer programming, OR Spectrum, Volume 29, Nr 4, 2007, pp. 783-803

[11]

S. Daskalaki et al., An integer programming formulation for a case study in university timetabling, European Journal of OR, Volume 153, Issue 1, 2004, pp. 117-135

[12]

S. Daskalaki & T. Birbas, Efficient solutions for a university timetabling problem through integer programming, European Journal of OR, Volume 160, Issue 1, 2005, pp. 106-120

[13]

S.A. MirHassani, A computational approach to enhancing course timetabling with integer programming, Applied Mathematics & Computation, Volume 175, Is. 1, 2006, pp. 814-822

[14]

M. Dimopoulou & P. Miliotis, Implementation of a university course and examination timetabling system, European Journal of OR, Volume 130, Issue 1, 2001, pp. 201-213

[15]

B. McCollum et al., A new model for automated examination timetabling, Annals of Operation Research, Volume 194, Number 1, 2012, pp. 291-315

[16]

Metaheuristics Nework, http://www.metaheuristics.org/

[17]

E. Aarts et al., Simulated annealing, Search Methodologies, 2005, pp. 187-210

[18]

Simulated Annealing, http://lion.disi.unitn.it/reactive-search/thebook/node17.html

[19]

J. M. Thompson & K. A. Dowsland, A robust simulated annealing based examination timetabling system, Computers & OR, Volume 25, Issues 7-8, 1998, pp. 637-648

[20]

E. Burke et al., Hybrid Variable Neighbourhood Approaches to University Exam Timetabling, Technical Report No. NOTTCS-TR-2006-2, University of Nottingham, 2006

61

[21]

M. Gendreau & J-Y. Potvin, Tabu Search, Search Methodologies, 2005, pp. 165-186

[22]

H Arntzen & A. Løkketangen, A tabu search heuristic for a university timetabling problem, Metaheuristics: progress as real problem solvers, Volume 32, pp. 65-86

[23]

H.A. Abbass, A monogenous MBO approach to statisfiability, In: Proceeding of the International Conference on Computational Intelligence for Modeling, Control and Automation, CIMCA’2001, Las Vegas, NV, USA

[24]

D.T. Pham et al., The Bees Algorithm – A Novel Tool for Complex Optimization Problems, IPROMS 2006 Proceeding 2nd International Virtual Conference on Intelligent Production Machines and Systems, Oxford, Elsevier, 2006a.

[25]

H. A. Abbass, MBO: Marriage in Honey Bees Optimization; A Haplometrosis Polygynous Swarming Approach, Evolutionary Computation, Volume 1, pp. 207-214

[26]

N. R. Sabar et al., A Honey-bee mating optimization algorithm for educational timetabling problems, European Journal of OR, Volume 216, Issue 3, 2012, pp. 533-543

[27]

E.K. Burke et al., Hybrid variable neighbourhood approaches to university exam timetabling, European Journal of OR, Volume 206, Issue 1, 2010, pp. 46-53

[28]

N. Mladenović & P. Hansen, Variable Neighbourhood Search, Computers Ops. Res., Volume 24, Number 11, 1997, pp. 1097-1100

[29]

N. Mladenović & P. Hansen, Variable Neighbourhood Search: Principles and applications, European Journal of Operations Research, Volume 130, Issue 3, 2001, pp. 449-467

[30]

B. Bilgin et al., An Experimental Study on Hyper-Heuristics and Final Exam Scheduling, Lecture Notes in Computer Science, Volume 3867/2007, 2007, pp. 394-412

[31]

P. Boizumault et al., Constraint logic programming for examination timetabling, The Journal of logic programming, Volume 26, Issue 2, 1996, pp. 217-233

[32]

M.N.M. Kahar & G. Kendall, The examination timetabling problem at University Malaysia Pahang: comparison of a constructive heuristic with an existing software solution, European Journal of Operations Research, Volume 207, Issue 2, 2010, pp. 557-565

[33]

R.R. Weitz, An empirical comparison of heuristic and graph theoretic methods for creating maximally diverse groups, VLSI design, and exam scheduling; Omega, Volume 25, Issue 4, 1997, pp. 473-482

[34]

V. Lofti & R. Cerveny, A Final-exam-scheduling package, The Journal of Operational Research Society, Volume 43, Number 3, 1991, pp. 205-216

[35]

N. Pillay & W. Banzhaf, An informed genetic algorithm for the examination timetabling problem, Applied Soft Computing, Volume 10, Issue 2, 2010, pp. 457-467

[36]

K. Socha et al., Ant algorithms for the university course timetabling problem with regard to the state-of-the-art, Lecture Notes in Computer Science, Volume 2611/2003, 2003, pp. 334-345

62

[37]

E.K. Burke et al., A Graph-based hyper-heuristic for educational timetabling problems, European Journal of Operations Research, Volume 176, Issue 1, 2007, pp. 177-192

[38]

P. Kostuch, The University course timetabling problem with a 3-phase approach, Lecture Notes in Computer Science, Volume 3616/2005, 2005, pp. 109-125

[39]

E.K. Burke& Y. Bykov, Solving exam timetabling problems with the flex-deluge algorithm. In: Proceedings of the 6th International Conference on the Practice and Theory of Automated Timetabling, 2006, Brno, pp. 370-372

[40]

E.K. Burke et al., Monte Carlo hyper-heuristics for examination timetabling, Annals of Operations Research, 2010, DOI: 10.1007/s10479-010-0782-2

[41]

R. Qu et al., A Survey of search methodologies and automated system development for examination timetabling, Journal of Scheduling, Volume 12, Nr. 1, 2009, pp. 55-89

[42]

L. Di Gaspero & A. Schaerf, Tabu search techniques for examination timetabling, Lecture Notes in Computer Science, Volume 2079/2001, 2001, pp. 104-117

[43]

G. M. White & B. S. Xie, Examination timetables and tabu search with longer-term memory, Lecture Notes in Computer Science, Volume 2079/2001, 2001, pp. 85-103

[44]

L.T.G. Merlot et al., A hybrid algorithm for the examination timetabling problem, Lecture Notes in Computer Science, Volume 2740/2003, 2003, pp. 207-231

[45]

OPL ILOG CPLEX solver information, http://www.ibm.com/us/en/

[46]

Bart Dhoedt, Informatica (Java), Department of Information Technology, Ghent University, 2006

63

Bijlage A: kleine dataset De eerste tabel geeft de vakcode met het aantal onderdelen weer. De tweede tabel geeft het onderdeel met bijhorend vak en het maximaal toegelaten aantal studenten weer. En tot slot geeft de derde tabel het examen met bijhorend onderdeel en aantal studiepunten weer.

64

In deze tabellen staat er opgesomd welke examens welke studenten kunnen afleggen.

65

Bijlage B: OPL model (toegepast op de kleine dataset) MOD-file range V = 1..9; range O = 1..11; range E = 1..15; range S = 1..12; {int} T = {1,2,3,4,5,6,7,8,9,10,11,12,15,16,17,18,19,20,21,22,23,24,25,26,29, 30,31,32,33,34,35,36,37,38,39,40,43,44,45,46,47,48,49,50,51,52,53,54}; {int} T2 = {3,4,5,6,7,8,9,10,11,12,15,16,17,18,19,20,21,22,23,24,25,26, 29,30,31,32,33,34,35,36,37,38}; tuple Vakken{ int AantalOnd; } Vakken VD[V] = ...; tuple Onderdelen{ int Vak; int maxStud; } Onderdelen OD[O] = ...; tuple Examens{ int Ond; int SP; } Examens ED[E]=...; int lengte=70; int a=1; int exs[1..lengte][1..2] = ...;/*welke Examens kan Student s afleggen?*/ {int} ExS[S]; {int} OndS[S]; {int} VakS[S]; {int} StudEx[E];/*welke studenten volgen welk examen?*/ {int} StudOnd[O];/*welke studenten volgen welk onderdeel*/ execute Assign_ExS{ for(var s in S){ for(var i=a; i<=lengte; i++){ if(exs[i][1]==s) ExS[s].add(exs[i][2]); else {a=i; break;} } } a=1; }

66

execute Assign_OndS{ for(var s in S){ for(var i=a; i<=lengte; i++){ if(exs[i][1]==s) OndS[s].add(ED[exs[i][2]].Ond); else {a=i; break;} } } a=1; } execute Assign_VakS{ for(var s in S){ for(var i=a; i<=lengte; i++){ if(exs[i][1]==s) VakS[s].add(OD[ED[exs[i][2]].Ond].Vak); else {a=i; break;} } } a=1; } execute Assign_StudEx{ for(var e in E){ for(var i=1; i<=lengte; i++){ if(exs[i][2]==e) StudEx[e].add(exs[i][1]); } } } execute Assign_StudOnd{ for(var ond in O){ for(var i=1; i<=lengte; i++){ if(ED[exs[i][2]].Ond==ond) StudOnd[ond].add(exs[i][1]); } } } dvar boolean x[S][E][T]; dvar float+ slackvar[E][E][T][T]; dvar boolean y[E][T]; minimize sum(e1 in E, e2 in E, t1 in T, t2 in T) slackvar[e1][e2][t1][t2]; subject to{ forall(s in S, e1 in ExS[s], e2 in ExS[s], t1 in T, t2 in T:t112<=t2<=t1){ if(ED[e1].SP==6 && OD[ED[e1].Ond].Vak!=OD[ED[e2].Ond].Vak) t1-t2)*(x[s][e1][t1] +x[s][e2][t2] -1)>=13*(x[s][e1][t1] +x[s][e2][t2] -1)-(slackvar[e1][e2][t1][t2]/6); }

67

forall(s in S, e1 in ExS[s]:ED[e1].SP==6, e2 in ExS[s]:OD[ED[e1].Ond].Vak!=OD[ED[e2].Ond].Vak, t1 in T, t2 in T:t2<=t1){ 12>=slackvar[e1][e2][t1][t2]; } forall(s in S, e1 in ExS[s], e2 in ExS[s], t1 in T, t2 in T:t18<=t2<=t1){ if(ED[e1].SP==4 && OD[ED[e1].Ond].Vak!=OD[ED[e2].Ond].Vak) (t1-t2)*(x[s][e1][t1] +x[s][e2][t2] -1)>=9*(x[s][e1][t1] +x[s][e2][t2] -1)-(slackvar[e1][e2][t1][t2]/4); } forall(s in S, e1 in ExS[s]:ED[e1].SP==4, e2 in ExS[s]:OD[ED[e1].Ond].Vak!=OD[ED[e2].Ond].Vak, t1 in T, t2 in T:t2<=t1){ 8>=slackvar[e1][e2][t1][t2]; } forall(s in S, e1 in ExS[s], e2 in ExS[s], t1 in T, t2 in T:t16<=t2<=t1){ if(ED[e1].SP==3 && OD[ED[e1].Ond].Vak!=OD[ED[e2].Ond].Vak) (t1-t2)*(x[s][e1][t1] +x[s][e2][t2] -1)>=7*(x[s][e1][t1] +x[s][e2][t2] -1)-(slackvar[e1][e2][t1][t2]/3); } forall(s in S, e1 in ExS[s]:ED[e1].SP==3, e2 in ExS[s]:OD[ED[e1].Ond].Vak!=OD[ED[e2].Ond].Vak, t1 in T, t2 in T:t2<=t1){ 6>=slackvar[e1][e2][t1][t2]; } /*student moet in 1 examen worden ingepland*/ forall(s in S, ond in OndS[s]){ sum(e in E: ED[e].Ond==ond, t in T)x[s][e][t]==1; } /*max aantal studenten per groep*/ forall(e in E, t in T){ sum(s in StudEx[e])x[s][e][t] <= y[e][t]*OD[ED[e].Ond].maxStud; } /*y[e][t] bepalen*/ forall(s in S, e in ExS[s], t in T){ y[e][t]>=x[s][e][t]; } /*elke examen max 1 keer*/ forall(e in E){ sum(t in T)y[e][t]==1; }

68

/*max 1 examen per vak per tijdstip*/ forall(t in T, v in V){ sum(e in E: OD[ED[e].Ond].Vak==v)y[e][t]<=1; } /*een student mag per 24h slechts 1 examen afleggen*/ forall(s in S, t in T2) sum(e in ExS[s],tt in t-2..t+2)(x[s][e][tt]-sum(ee in ExS[s]: OD[ED[ee].Ond].Vak == OD[ED[e].Ond].Vak && ee != e)x[s][ee][tt])<=1; forall(s in S) sum(e in ExS[s])(x[s][e][1]+x[s][e][2]-sum(ee in ExS[s]: OD[ED[ee].Ond].Vak == OD[ED[e].Ond].Vak && ee != e)(x[s][ee][1]+x[s][ee][2]))<=1; forall(s in S) sum(e in ExS[s])(x[s][e][39]+x[s][e][40]-sum(ee in ExS[s]: OD[ED[ee].Ond].Vak == OD[ED[e].Ond].Vak && ee != e)(x[s][ee][39]+x[s][ee][40]))<=1;

/*een student heeft op 1 tijdstip max 1 examen*/ forall(s in S, t in T){ sum(e in ExS[s])x[s][e][t]<=1; } /*tussen 2 examens van zelfde vak geen ander vak*/ forall(s in S, v in VakS[s], t1 in T, t2 in T: t1
69

DAT-file SheetConnection sheet("subset.xlsx"); VD from SheetRead(sheet,"uitlezen!B2:B10"); OD from SheetRead(sheet,"uitlezen!E2:F12"); ED from SheetRead(sheet,"uitlezen!K2:L16"); exs from SheetRead(sheet,"uitlezen!N2:O71");

//SheetConnection sheetData("Results.xlsx"); //Export to SheetWrite(sheetData,"Result!Data");

70

Bijlage C: klasses Examen import java.util.*; public class Examen { protected protected protected protected protected protected

int timeslot; final int SP; ArrayList student; final int ond; final int vak; final int exnr;

//constructor public Examen(int t, int sp, int o, int v, int ex){ timeslot = t; SP = sp; ond = o; vak = v; student = new ArrayList(); exnr = ex; } //copy-constructor public Examen (Examen e){ timeslot=e.timeslot; SP=e.SP; ond=e.ond; vak=e.vak; student=copyList(e.student); exnr=e.exnr; } //wijzigen timeslot public void changeT(int t){ timeslot=t; } //copyList public static ArrayList copyList(List source){ ArrayList dest = new ArrayList(); for (Integer item : source) { dest.add(item); } return dest; } //toevoegen student aan examen public void addStud(int s){ student.add(s); } //verwijderen student uit examen public void removeStud(int s){ student.remove(student.indexOf(s)); } }

71

Timeslot import java.util.*; public class Timeslot { public ArrayList <Examen> examens; protected final int timenr; //constructor public Timeslot(int t){ timenr = t; examens = new ArrayList <Examen>(); } public static ArrayList<Examen> copyList(List<Examen> source) { ArrayList<Examen> dest = new ArrayList<Examen>(); for (Examen item : source) { dest.add(item); } return dest; } //copy-constructor public Timeslot(Timeslot t){ examens=copyList(t.examens); timenr=t.timenr; } //toevoegen examen public void addEx(Examen e){ examens.add(e); } //verwijderen examen public void removeEx(Examen e){ examens.remove(e); } //weergeven van de examenslijst public ArrayList<Examen> geefEx(){ return examens; } //weergeven van het tijdslotnummer public int geefTime(){ return timenr; } //weergeven van het aantal //tijdslot public int geefRijGrootte(){ return examens.size(); }

examens

gepland

op

beschouwde

}

72

Pair import java.util.*; public class Pair{ public public public public

Examen[] e; int s; //straf Timeslot[] t; ArrayList[] SE;

//constructor public Pair(Timeslot[] ArrayList[] SE) { this.e= e; this.s= s; this.t= t; this.SE=SE; }

t,

Examen[]

e,

int

s,

public Examen[] returnE(){ return e; } public int returnS(){ return s; } public Timeslot[] returnT(){ return t; } public ArrayList[] returnSE(){ return SE; } //wijzigen van Pair public void changeTot(Pair p){ this.e=p.returnE(); this.s=p.returnS(); this.t=p.returnT(); this.SE=p.returnSE(); } //wijzigen van Timeslot public void changeT(Timeslot[] t){ this.t=t; } //wijzigen van Examen public void changeE(Examen[] e){ this.e=e; } //wijzigen van straf public void changeS(int s){ this.s=s; } }

73

Bijlage D: Neighbourhoods Switchen van twee examens static Pair Neighbourhood1(Timeslot[] t, Examen[] exdata, int lengtese, ArrayList[] SE, int x, ArrayList zondag){ System.out.println("\tN1"); //eerst een eerste oplossing x bepalen int aantalex = exdata.length; Timeslot[] t2 = new Timeslot[t.length]; int indelen; Examen[] exd2 = new Examen[exdata.length]; int straf; int ex1; int ex2; boolean vlag; int tijd; int stop=0; do{ for(int i=0;i<exdata.length;i++){ exd2[i]=new Examen(exdata[i]); } for(int i=0;i
74

Switchen van twee studenten @SuppressWarnings("unchecked") static Pair Neighbourhood2(ArrayList onderdeel, ArrayList[] OS, ArrayList[] OE, ArrayList dummy, ArrayList [] SE, Examen[] exdata, Timeslot[] t, int x, int lengtese, ArrayList zondag){ System.out.println("\tN2"); Examen[] exd2 = new Examen[exdata.length]; for(int z=0;z<exdata.length;z++){ exd2[z]= new Examen(exdata[z]); } ArrayList[] SE2 = new ArrayList[SE.length]; for(int z=0;z<SE.length;z++){ SE2[z] = copyList(SE[z]); } int ond = onderdeel.get((int)Math.round((onderdeel.size()-1)* Math.random())); int a; int stud1; int ex1; int stud2; int ex2; boolean vlag1 = false; boolean vlag2 = false; int stop=0; do{ stud1= 5000; ex1 = 1000; stud2 = 5000; ex2 = 1000; vlag1=false; vlag2=false; do{ a = (int)Math.round((OS[ond].size()-1)*Math.random()); stud1 = OS[ond].get(a); }while(dummy.contains(stud1)); for(int i=0;i<SE2[stud1].size();i++){ if(exd2[SE2[stud1].get(i)].ond == ond) ex1 = SE2[stud1].get(i); if(ex1 != 1000) break; } //zoeken naar dummie for(int i=0;i
75

} } if(stud2 != 5000) break; } if(stud2 == 5000){ do{ a = (int)Math.round((OS[ond].size()-1)* Math.random()); stud2 = OS[ond].get(a); for(int i=0;i<SE2[stud2].size();i++){ if(exd2[SE2[stud2].get(i)].ond == ond) ex2 = SE2[stud2].get(i); } }while(ex1 == ex2); } vlag1 = feasibleStud(t,exd2[ex2].timeslot,stud1); vlag2 = feasibleStud(t,exd2[ex1].timeslot,stud2); stop++; }while(!(vlag1&&vlag2) && stop<100); Pair result; Pair doorgeven; Pair Temp; if(vlag1 && vlag2 && ex1!=1000 && ex2!=1000){ exd2[ex1].removeStud(stud1); exd2[ex2].removeStud(stud2); exd2[ex1].addStud(stud2); exd2[ex2].addStud(stud1); SE2[stud1].remove(SE2[stud1].indexOf(ex1)); SE2[stud2].remove(SE2[stud2].indexOf(ex2)); SE2[stud1].add(ex2); SE2[stud2].add(ex1); int straf = berekenStraf(exd2, lengtese, t.length, SE2); doorgeven = new Pair(t,exd2,straf,SE2); Temp = localSearch(doorgeven, lengtese,zondag); if(Temp.returnS()<x) result = Temp; else result = new Pair(t,exdata,x,SE); } else result = new Pair(t,exdata,x,SE); return result; }

76

Kempe Chain static Pair Neighbourhood6(Timeslot [] t, Examen[] exdata, int x, ArrayList[] SE, ArrayList zondag, int lengtese){ System.out.println("\tN6"); Timeslot[] ts2 = new Timeslot[t.length]; int indelen; Examen[] exd2 = new Examen[exdata.length]; Pair result = new Pair(t,exdata,x,SE); //result is nu = beginwaarden int ex1 =(int)Math.round((exd2.length-1)*Math.random()); int t1 = exdata[ex1].timeslot; int t2; do{ t2 = (int)Math.round((t.length-1)*Math.random()); }while(zondag.contains(t2)); for(int z=0;z<exd2.length;z++){ exd2[z]= new Examen(exdata[z]); } for(int z=0;z k1 = new ArrayList<Examen>(); int lengte = k1.size(); k1.add(exdata[ex1]); ArrayList<Examen> k2 = new ArrayList<Examen>(); if(!feasible(ts2,t2,exd2[ex1])){ do{ lengte = k1.size(); k2 = Kempe(ts2,t2,k1); k1 = Kempe(ts2,t1,k2); for(int i=0;i
77

else{ exd2[ex1].timeslot=t2; for(int z=0;z
78

Bijlage E: Local search static Pair localSearch (Pair p, int lengtese, ArrayList zondag){ ArrayList[] SE = p.returnSE(); Timeslot[] t2=p.returnT(); Examen[] exd2=p.returnE(); int straf = p.returnS(); Timeslot[] tTemp = new Timeslot[t2.length]; Examen[] exTemp = new Examen[exd2.length]; int straf2; int strafBest = straf; int indelen; int ex1; Pair result = new Pair(t2,exd2,straf,SE); ex1=(int)Math.round((exd2.length-1)*Math.random()); for(int i=0;i
79

Bijlagen op digitale versie Volgende bijlagen staan op de digitale versie bijgevoegd in deze masterproef. Bijlagen A-E Bijlage F: alle data gekregen van de FSA Bijlage G: de grote dataset gebruikt in deze masterproef Bijlage H: de volledige Java-code Bijlage I: ILOG code voor eerste fase van de heuristische methode Bijlage J: Excel macro Bijlage K: feasible oplossing van de eerste fase van de heuristische methode Bijlage L: straf FSA rooster

80