Browsing by Author "Van Rooyen, Charles"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Automated examination timetabling with application to Stellenbosch University
    (Stellenbosch : Stellenbosch University, 2018-12) Van Rooyen, Charles; Nieuwoudt, Isabelle; Stellenbosch University. Faculty of Economic and Management Sciences. Dept. of Logistics. Logistics.
    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.