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)
|
Pdf (Open access)
Performance analyses of graph heuristics and selected trajectory.pdf Available under License Creative Commons Attribution. Download (759kB) | Preview |
Abstract
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.
| Item Type: | Article |
|---|---|
| Additional Information: | Indexed by Scopus |
| Uncontrolled Keywords: | Capacitated exam timetabling; Combinatorial optimization; Exam timetabling problems; Graph heuristic; Trajectory meta-heuristics; Un-capacitated exam timetabling |
| Subjects: | Q Science > QA Mathematics > QA76 Computer software |
| Faculty/Division: | Faculty of Computer System And Software Engineering |
| Depositing User: | Mrs Norsaini Abdul Samat |
| Date Deposited: | 12 Nov 2020 03:27 |
| Last Modified: | 12 Nov 2020 03:27 |
| URI: | http://umpir.ump.edu.my/id/eprint/29896 |
| Download Statistic: | View Download Statistics |
Actions (login required)
 |
View Item |