M.N.M. Kahar
Associate Professor Faculty of Computer Systems & Software Engineering, Universiti Malaysia Pahang, Locked Bag 12, Kuantan 25000,

Published : 1 Documents Claim Missing Document
Claim Missing Document
Check
Articles

Found 1 Documents
Search

Performance Analyses of Graph Heuristics and Selected Trajectory Metaheuristics on Examination Timetable Problem Ashis Kumar Mandal; M.N.M. Kahar
Indonesian Journal of Electrical Engineering and Informatics (IJEEI) Vol 8, No 1: March 2020
Publisher : IAES Indonesian Section

Show Abstract | Download Original | Original Source | Check in Google Scholar | Full PDF (759.886 KB) | DOI: 10.52549/ijeei.v8i1.1660

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.