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...

全面介紹

Saved in:
書目詳細資料
主要作者: Mandal, Ashis Kumar
格式: Thesis
語言:English
出版: 2016
主題:
在線閱讀:http://umpir.ump.edu.my/id/eprint/25157/1/Partial%20examination%20assignment%20approaches%20for%20solving%20examination%20timetabling.pdf
標簽: 添加標簽
沒有標簽, 成為第一個標記此記錄!
實物特徵
總結: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.