Partial examination assignment approaches for solving examination timetabling problems

Examination timetabling is one type of scheduling problems faced by academic institutions when allocating examinations into a limited number of time slots and/or rooms. It is obvious that the task of constructing a quality timetable is a challenging and time-consuming due to its NP-hard nature, with a large number of constraints having to be accommodated. It is observed in the literature that most of the reported research starts with constructing the initial feasible timetable(s) by allocating all examinations and then performs an improvement on the timetable. However, these traditional approaches bias toward the initial timetable where the improvement algorithms (sometimes) are affected and unable to produce a quality timetable. This thesis presents partial examination assignment approaches to address the examination timetabling problem. The proposed algorithms work by first ordering all examinations using graph heuristics ordering strategies. After that, partially selected examinations are scheduled, followed by an improvement on the partially scheduled examinations. The entire process runs until all of the examinations are assigned successfully. We have implemented partial graph heuristic with hill climbing (PGH-HC) and partial graph heuristic with modified great deluge algorithm (PGH-mGD) into solving the examination timetabling. The proposed approaches are tested on two benchmark datasets, namely Toronto dataset and the Second International Timetabling Competition (ITC2007) dataset. Experimental results demonstrate that the proposed approaches are able to produce quality solutions compared to traditional approaches for all instances of the datasets. Additionally, while compared with the state-of-the-art algorithms, our proposed approaches generally are able to produce competitive results and even outperform some of the reported results found in the scientific literature