Automated examination timetabling with application to Stellenbosch University
Date
2018-12
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH SUMMARY : The examination timetabling problem (ETP) consists of scheduling the examination papers of
students in such a way that no student is required to write two or more examination papers at the same time in an examination period. It is well known that this problem is NP–complete, which makes it an interesting research topic for researcher. There exist many different variants of
the ETP, and the one focused on in this project is the variant that can be applied to Stellenbosch University.
The purpose of this project is to find examination timetables that will spread most students’ examination papers more or less equally over the full duration of the examination period. Stellenbosch
University is used as case study. The primary objective of any algorithm is to satisfy the hard constraints provided by Stellenbosch University. For example, one hard constraint is that certain examination papers must be scheduled on fixed timeslots. Graph colouring is used in a two–phase heuristic algorithm to obtain a feasible initial solution. In the first phase an examination timetable is sought where no student is required to write more
than one examination paper during any timeslot. After the first phase, the number of examination papers scheduled during each timeslot is balanced in the second phase of the algorithm. This is to ensure that amongst others, enough lecture halls are available during each timeslot to
accommodate all students. After a feasible initial solution is obtained, hill climbing and the great deluge algorithm (GDA)
are used to improve upon the equally spread of students’ examination papers as much as possible over the entire examination period. Three moves are defined in this project to move from solution to solution in the solution space. The first move moves one module in the timetable to another timeslots, the second move swaps all of the modules in two timeslots and the third move is to
swap two modules that are in different timeslots. To evaluate how well students’ examination papers are spread over the entire examination period for each timetable, a newly derived cost function is used. The cost function strives to be fair towards all students. Parameter calibration
is done on the parameters used in the cost function and the search algorithms.
The resulting timetables when using hill climbing and the GDA are compared, and it is found that the GDA outperforms hill climbing. Furthermore, the cost function used in this project is compared to the cost function of the 2nd International Timetabling Competition (ITC). Using
Stellenbosch University’s variant of the ETP, it is found that the cost function of this project outperforms the cost function used in the ITC.
AFRIKAANSE OPSOMMING : In die eksamenrooster–probleem (ERP) moet eksamenroosters sAs ingedeel word dat geen student meer as een eksamenvraestel gelyktydig moet skryf nie. Hierdie probleem is NP–volledig en is al deeglik deur navorsers ondersoek. Daar is baie variante van die ERP, en in hierdie projek word daar gefokus op die variant wat op die Universiteit van Stellenbosch (US) van toepassing is. Die doel van hierdie projek is om eksamenroosters op te stel wat studente se eksamenvraestelle so ver as moonlik eweredig oor die hele eskamenperiode versprei. Die US word as gevallestudie gebruik. Die primêre doelwit van enige algoritme is om aan die US se vaste vereistes vir ’n eksamenrooster te voldoen. Een van hierdie vereiste is, byvoorbeeld, dat sekere eksamenvraestelle op spesifieke tydgleuwe geskeduleer moet word. Grafiekkleuring is gebruik in ’n heuristiek wat van twee fases gebruik maak om ’n aanvanklike eksamenrooster wat aan die US se vereistes voldoen, te kry. In die eerste fase word ’n eksamenrooster gesoek waarin daar van geen student verwag word om twee of meer eksamenvraestelle gelyktydig te skryf nie, en in die tweede fase word die hoeveelheid eksamenvraestelle per tydgleuf gebalanseer. Die tweede fase word byvoorbeeld benodig sodat daar ten alle tye genoeg eksamenlokale beskikbaar sal wees om alle studente te akkommodeer. Nadat ’n aanvanklike toelaatbare oplossing verkry is, word hill climbing en the great deluge algoritme (GDA) gebruik om studente se opeenvolgende eksamenvraestelle so ver as moontlik uitmekaar te versprei. Drie eenvoudige skuiwe word in die algoritmes gebruik om sodoende deur die oplossingsruimte te beweeg. Die eerste skuif is om ’n eksamenvraestel te skuif na ’n ander tydgleuf, die tweede skuif is om al die eksamenvraestelle van twee tydgleuwe met mekaar om te ruil en die laatse skuif is om twee eksamenvraestelle wat in twee verskillende tydgleuwe is met mekaar om te ruil. Om ’n aanduiding te kry van hoe goed studente se eksamenrooster ingedeel is, is ’n koste–funksie bepaal. Die doelfunksie handhaaf regverdigheid ten opsigte van die hoeveelheid eksamenvraestelle wat per student geskryf moet word. Die parameters van die doelfunksie en die algoritmes word gekalibreer om sodoende goeie parameterwaardes te bepaal. Die twee algoritmes word met mekaar vergelyk, en daar is bevind dat GDA beter vaar as die hill climbing algoritme. Verder word die koste–funksie van hierdie projek vergelyk met die koste–funksie van die 2de Internationale Roosterindelingskompetisie (ITC). Daar is bevind dat die koste–funksie van hierdie projek beter vertoon om die US se eksamenroosters in te deel as die koste–funksie van die ITC.
AFRIKAANSE OPSOMMING : In die eksamenrooster–probleem (ERP) moet eksamenroosters sAs ingedeel word dat geen student meer as een eksamenvraestel gelyktydig moet skryf nie. Hierdie probleem is NP–volledig en is al deeglik deur navorsers ondersoek. Daar is baie variante van die ERP, en in hierdie projek word daar gefokus op die variant wat op die Universiteit van Stellenbosch (US) van toepassing is. Die doel van hierdie projek is om eksamenroosters op te stel wat studente se eksamenvraestelle so ver as moonlik eweredig oor die hele eskamenperiode versprei. Die US word as gevallestudie gebruik. Die primêre doelwit van enige algoritme is om aan die US se vaste vereistes vir ’n eksamenrooster te voldoen. Een van hierdie vereiste is, byvoorbeeld, dat sekere eksamenvraestelle op spesifieke tydgleuwe geskeduleer moet word. Grafiekkleuring is gebruik in ’n heuristiek wat van twee fases gebruik maak om ’n aanvanklike eksamenrooster wat aan die US se vereistes voldoen, te kry. In die eerste fase word ’n eksamenrooster gesoek waarin daar van geen student verwag word om twee of meer eksamenvraestelle gelyktydig te skryf nie, en in die tweede fase word die hoeveelheid eksamenvraestelle per tydgleuf gebalanseer. Die tweede fase word byvoorbeeld benodig sodat daar ten alle tye genoeg eksamenlokale beskikbaar sal wees om alle studente te akkommodeer. Nadat ’n aanvanklike toelaatbare oplossing verkry is, word hill climbing en the great deluge algoritme (GDA) gebruik om studente se opeenvolgende eksamenvraestelle so ver as moontlik uitmekaar te versprei. Drie eenvoudige skuiwe word in die algoritmes gebruik om sodoende deur die oplossingsruimte te beweeg. Die eerste skuif is om ’n eksamenvraestel te skuif na ’n ander tydgleuf, die tweede skuif is om al die eksamenvraestelle van twee tydgleuwe met mekaar om te ruil en die laatse skuif is om twee eksamenvraestelle wat in twee verskillende tydgleuwe is met mekaar om te ruil. Om ’n aanduiding te kry van hoe goed studente se eksamenrooster ingedeel is, is ’n koste–funksie bepaal. Die doelfunksie handhaaf regverdigheid ten opsigte van die hoeveelheid eksamenvraestelle wat per student geskryf moet word. Die parameters van die doelfunksie en die algoritmes word gekalibreer om sodoende goeie parameterwaardes te bepaal. Die twee algoritmes word met mekaar vergelyk, en daar is bevind dat GDA beter vaar as die hill climbing algoritme. Verder word die koste–funksie van hierdie projek vergelyk met die koste–funksie van die 2de Internationale Roosterindelingskompetisie (ITC). Daar is bevind dat die koste–funksie van hierdie projek beter vertoon om die US se eksamenroosters in te deel as die koste–funksie van die ITC.
Description
Thesis (MCom)--Stellenbosch University, 2018.
Keywords
Examination timetabling problem, Operations research -- Stellenbosch University, UCTD