Performance analyses of graph heuristics and selected trajectory metaheuristics on examination timetable problem
Examination timetabling problem is hard to solve due to its NP-hard nature, with a large number of constraints having to be accommodated. To deal with the problem effectually, frequently heuristics are used for constructing feasible examination timetable while meta-heuristics are applied for improvi...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Institute of Advanced Engineering and Science
2020
|
| Subjects: | |
| Online Access: | http://umpir.ump.edu.my/id/eprint/29896/ http://umpir.ump.edu.my/id/eprint/29896/1/Performance%20analyses%20of%20graph%20heuristics%20and%20selected%20trajectory.pdf |
| _version_ | 1848823389647536128 |
|---|---|
| author | Mandal, Ashis Kumar M. N. M., Kahar |
| author_facet | Mandal, Ashis Kumar M. N. M., Kahar |
| author_sort | Mandal, Ashis Kumar |
| building | UMP Institutional Repository |
| collection | Online Access |
| description | Examination timetabling problem is hard to solve due to its NP-hard nature, with a large number of constraints having to be accommodated. To deal with the problem effectually, frequently heuristics are used for constructing feasible examination timetable while meta-heuristics are applied for improving the solution quality. This paper presents the performances of graph heuristics and major trajectory metaheuristics or S-metaheuristics for addressing both capacitated and un-capacitated examination timetabling problem. For constructing the feasible solution, six graph heuristics are used. They are largest degree (LD), largest weighted degree (LWD), largest enrolment degree (LE), and three hybrid heuristic with saturation degree (SD) such as SD-LD, SD-LE, and SD-LWD. Five trajectory algorithms comprising of tabu search (TS), simulated annealing (SA), late acceptance hill climbing (LAHC), great deluge algorithm (GDA), and variable neighborhood search (VNS) are employed for improving the solution quality. Experiments have been tested on several instances of un-capacitated and capacitated benchmark datasets, which are Toronto and ITC2007 dataset respectively. Experimental results indicate that, in terms of construction of solution of datasets, hybridizing of SD produces the best initial solutions. The study also reveals that, during improvement, GDA, SA, and LAHC can produce better quality solutions compared to TS and VNS for solving both benchmark examination timetabling datasets. |
| first_indexed | 2025-11-15T02:56:22Z |
| format | Article |
| id | ump-29896 |
| institution | Universiti Malaysia Pahang |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-15T02:56:22Z |
| publishDate | 2020 |
| publisher | Institute of Advanced Engineering and Science |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | ump-298962020-11-12T03:27:08Z http://umpir.ump.edu.my/id/eprint/29896/ Performance analyses of graph heuristics and selected trajectory metaheuristics on examination timetable problem Mandal, Ashis Kumar M. N. M., Kahar QA76 Computer software Examination timetabling problem is hard to solve due to its NP-hard nature, with a large number of constraints having to be accommodated. To deal with the problem effectually, frequently heuristics are used for constructing feasible examination timetable while meta-heuristics are applied for improving the solution quality. This paper presents the performances of graph heuristics and major trajectory metaheuristics or S-metaheuristics for addressing both capacitated and un-capacitated examination timetabling problem. For constructing the feasible solution, six graph heuristics are used. They are largest degree (LD), largest weighted degree (LWD), largest enrolment degree (LE), and three hybrid heuristic with saturation degree (SD) such as SD-LD, SD-LE, and SD-LWD. Five trajectory algorithms comprising of tabu search (TS), simulated annealing (SA), late acceptance hill climbing (LAHC), great deluge algorithm (GDA), and variable neighborhood search (VNS) are employed for improving the solution quality. Experiments have been tested on several instances of un-capacitated and capacitated benchmark datasets, which are Toronto and ITC2007 dataset respectively. Experimental results indicate that, in terms of construction of solution of datasets, hybridizing of SD produces the best initial solutions. The study also reveals that, during improvement, GDA, SA, and LAHC can produce better quality solutions compared to TS and VNS for solving both benchmark examination timetabling datasets. Institute of Advanced Engineering and Science 2020-03 Article PeerReviewed pdf en cc_by_4 http://umpir.ump.edu.my/id/eprint/29896/1/Performance%20analyses%20of%20graph%20heuristics%20and%20selected%20trajectory.pdf Mandal, Ashis Kumar and M. N. M., Kahar (2020) Performance analyses of graph heuristics and selected trajectory metaheuristics on examination timetable problem. Indonesian Journal of Electrical Engineering and Informatics, 8 (1). pp. 163-177. ISSN 2089-3272. (Published) http://section.iaesonline.com/index.php/IJEEI/article/view/1660 |
| spellingShingle | QA76 Computer software Mandal, Ashis Kumar M. N. M., Kahar Performance analyses of graph heuristics and selected trajectory metaheuristics on examination timetable problem |
| title | Performance analyses of graph heuristics and selected trajectory metaheuristics on examination timetable problem |
| title_full | Performance analyses of graph heuristics and selected trajectory metaheuristics on examination timetable problem |
| title_fullStr | Performance analyses of graph heuristics and selected trajectory metaheuristics on examination timetable problem |
| title_full_unstemmed | Performance analyses of graph heuristics and selected trajectory metaheuristics on examination timetable problem |
| title_short | Performance analyses of graph heuristics and selected trajectory metaheuristics on examination timetable problem |
| title_sort | performance analyses of graph heuristics and selected trajectory metaheuristics on examination timetable problem |
| topic | QA76 Computer software |
| url | http://umpir.ump.edu.my/id/eprint/29896/ http://umpir.ump.edu.my/id/eprint/29896/ http://umpir.ump.edu.my/id/eprint/29896/1/Performance%20analyses%20of%20graph%20heuristics%20and%20selected%20trajectory.pdf |