Partial examination assignment approaches for solving examination timetabling problems

Mandal, Ashis Kumar (2016) Partial examination assignment approaches for solving examination timetabling problems. Masters thesis, Universiti Malaysia Pahang (Contributors, UNSPECIFIED: UNSPECIFIED).

Partial examination assignment approaches for solving examination timetabling.pdf - Accepted Version

Download (6MB) | Preview


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.

Item Type: Thesis (Masters)
Additional Information: Thesis (Master of Computer Science) -- Universiti Malaysia Pahang – 2016, SV: DR. MOHD NIZAM BIN MOHMAD KAHAR, NO. CD: 11496
Uncontrolled Keywords: Examination timetabling; partial graph heuristic
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
T Technology > T Technology (General)
Faculty/Division: Faculty of Computer System And Software Engineering
Depositing User: Mrs. Sufarini Mohd Sudin
Date Deposited: 26 Jun 2019 03:21
Last Modified: 07 Sep 2021 02:23
Download Statistic: View Download Statistics

Actions (login required)

View Item View Item