Heuristic approaches for real world examination timetabling problems
The examination timetabling (exam-timeslot-room assignment) problem involves assigning exams to a specific or limited number of timeslots and rooms, with the aim of satisfying the hard constraints and the soft constraints as much as possible. Most of the techniques reported in the literature have be...
| Main Author: | |
|---|---|
| Format: | Thesis (University of Nottingham only) |
| Language: | English |
| Published: |
2013
|
| Online Access: | https://eprints.nottingham.ac.uk/27677/ |
| _version_ | 1848793412619206656 |
|---|---|
| author | Mohmad Kahar, Mohd Nizam |
| author_facet | Mohmad Kahar, Mohd Nizam |
| author_sort | Mohmad Kahar, Mohd Nizam |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | The examination timetabling (exam-timeslot-room assignment) problem involves assigning exams to a specific or limited number of timeslots and rooms, with the aim of satisfying the hard constraints and the soft constraints as much as possible. Most of the techniques reported in the literature have been applied to solve simplified examination benchmark datasets, available within the scientific literature. In this research we bridge the gap between research and practice by investigating a problem taken from the Universiti Malaysia Pahang (UMP), a real world capacitated examination timetabling problem. This dataset has several novel constraints, in addition to those commonly used in the literature. Additionally, the invigilator scheduling problem (invigilator assignment) was also investigated as it has not received the same level of research attention as the examination scheduling (although it is just as important to educational institutions).
The formal models are defined, and constructive heuristics was developed for both problems in which the overall problems are solved with a two-phase approach which involves scheduling the exam to timeslot and room, and follows with scheduling the invigilator. During the invigilator assignment, we assume that there is already an examination timetable in place (i.e. previously generated). It reveals that the invigilator scheduling solution dependent on the number of rooms selected from the exam-timeslot-room assignment phase (i.e. a lesser number of used rooms would minimises the invigilation duties for staff), this encourages us to further improve the exam-timeslot-room timetable solution. An improvement on the result was carried out using modified extended great deluge algorithm (modified-GDA) and multi-neighbourhood GDA approach (that use more than one neighbourhood during the search). The modified-GDA uses a simple to understand parameter and allows the boundary that acts as the acceptance level, to dynamically change during the search. The propose approaches able to produce good quality solution when compared to the solutions from the proprietary software used by UMP. In addition, our solutions adhere to all hard constraints which the current systems fail to do.
Finally, we extend our research onto investigating the Second International Timetabling Competition (ITC2007) dataset as it also contains numerous constraints much similar to UMP datasets. Our propose approach able to produce competitive solutions when compared to the solutions produced by other reported works in the literature. |
| first_indexed | 2025-11-14T18:59:53Z |
| format | Thesis (University of Nottingham only) |
| id | nottingham-27677 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-14T18:59:53Z |
| publishDate | 2013 |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-276772025-02-28T11:32:04Z https://eprints.nottingham.ac.uk/27677/ Heuristic approaches for real world examination timetabling problems Mohmad Kahar, Mohd Nizam The examination timetabling (exam-timeslot-room assignment) problem involves assigning exams to a specific or limited number of timeslots and rooms, with the aim of satisfying the hard constraints and the soft constraints as much as possible. Most of the techniques reported in the literature have been applied to solve simplified examination benchmark datasets, available within the scientific literature. In this research we bridge the gap between research and practice by investigating a problem taken from the Universiti Malaysia Pahang (UMP), a real world capacitated examination timetabling problem. This dataset has several novel constraints, in addition to those commonly used in the literature. Additionally, the invigilator scheduling problem (invigilator assignment) was also investigated as it has not received the same level of research attention as the examination scheduling (although it is just as important to educational institutions). The formal models are defined, and constructive heuristics was developed for both problems in which the overall problems are solved with a two-phase approach which involves scheduling the exam to timeslot and room, and follows with scheduling the invigilator. During the invigilator assignment, we assume that there is already an examination timetable in place (i.e. previously generated). It reveals that the invigilator scheduling solution dependent on the number of rooms selected from the exam-timeslot-room assignment phase (i.e. a lesser number of used rooms would minimises the invigilation duties for staff), this encourages us to further improve the exam-timeslot-room timetable solution. An improvement on the result was carried out using modified extended great deluge algorithm (modified-GDA) and multi-neighbourhood GDA approach (that use more than one neighbourhood during the search). The modified-GDA uses a simple to understand parameter and allows the boundary that acts as the acceptance level, to dynamically change during the search. The propose approaches able to produce good quality solution when compared to the solutions from the proprietary software used by UMP. In addition, our solutions adhere to all hard constraints which the current systems fail to do. Finally, we extend our research onto investigating the Second International Timetabling Competition (ITC2007) dataset as it also contains numerous constraints much similar to UMP datasets. Our propose approach able to produce competitive solutions when compared to the solutions produced by other reported works in the literature. 2013-03-15 Thesis (University of Nottingham only) NonPeerReviewed application/pdf en arr https://eprints.nottingham.ac.uk/27677/1/598041.pdf Mohmad Kahar, Mohd Nizam (2013) Heuristic approaches for real world examination timetabling problems. PhD thesis, University of Nottingham. |
| spellingShingle | Mohmad Kahar, Mohd Nizam Heuristic approaches for real world examination timetabling problems |
| title | Heuristic approaches for real world examination timetabling problems |
| title_full | Heuristic approaches for real world examination timetabling problems |
| title_fullStr | Heuristic approaches for real world examination timetabling problems |
| title_full_unstemmed | Heuristic approaches for real world examination timetabling problems |
| title_short | Heuristic approaches for real world examination timetabling problems |
| title_sort | heuristic approaches for real world examination timetabling problems |
| url | https://eprints.nottingham.ac.uk/27677/ |