Mandal, Ashis Kumar (2016) Partial examination assignment approaches for solving examination timetabling problems. Masters thesis, Universiti Malaysia Pahang (Contributors, UNSPECIFIED: UNSPECIFIED).
|
Pdf
Partial examination assignment approaches for solving examination timetabling.pdf - Accepted Version Download (6MB) | Preview |
Abstract
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 |
| URI: | http://umpir.ump.edu.my/id/eprint/25157 |
| Download Statistic: | View Download Statistics |
Actions (login required)
 |
View Item |