Abdul Rahman, Syariza and Sobri, Nur Suriani and Omar, Mohd Faizal and Benjamin, Aida Mauziah and Ramli, Razamin (2014) Graph coloring heuristics for solving examination timetabling problem at Universiti Utara Malaysia. In: 3rd International Conference on Quantitative Sciences and its Applications (ICOQSIA 2014), 12–14 August 2014, Langkawi, Kedah Malaysia.

Full text not available from this repository. (Request a copy)

Abstract

Examination timetabling is a well-studied combinatorial optimization problem involving scheduling a set of examinations into a restricted number of time-slots while satisfying a defined set of constraints.This paper presents a real-world, capacitated examination timetabling problem from Universiti Utara Malaysia (UUM), Malaysia. This dataset differs from the others reported in the literature with respect to its size, complexity and constraints.Until recently, examination timetabling in UUM is done manually with a little guidance from spreadsheet computer software for checking clashes.The propriety system is unable to do the examination timetabling automatically.Besides, the introduced datasets also consider a new constraint that has never been modeled before in timetabling literature, which is lecturer’s preference.Moreover, splitting examination across several rooms and a number of hard constraints such as no mixed duration of examination within individual periods, clashes free schedule and room capacity requirement are also need to be adhered.These constraints provide an additional challenge in solving the examination timetabling problem, mainly at UUM.In this paper, graph coloring heuristics are employed to schedule examinations at each step during timetable construction. We used the concept of bin packing heuristics to assign examination to room with respect to the capacity. Since this is a new dataset and no solutions have been published in the literature yet, we only compare the results with an existing manual solution.It is found that the proposed constructive heuristic able to produce good quality solution for the tested problem.The proposed graph coloring heuristics are proved to be superior to the current method employed by the University and found to perform well in comparison.

Item Type:	Conference or Workshop Item (Paper)
Additional Information:	ISBN: 978-0-7354-1274-3
Subjects:	Q Science > QA Mathematics > QA76 Computer software
Divisions:	School of Quantitative Sciences
Depositing User:	Mrs. Syariza Abdul Rahman
Date Deposited:	02 Mar 2016 06:55
Last Modified:	27 Apr 2016 02:50
URI:	https://repo.uum.edu.my/id/eprint/17407

Actions (login required)

View Item