A pure graph coloring constructive heuristic in timetabling

Budiono, T.A. and Wong, K.W. (2012) A pure graph coloring constructive heuristic in timetabling. In: International Conference on Computer and Information Science, ICCIS 2012 - A Conference of World Engineering, Science and Technology Congress, ESTCON 2012, 12 - 14 June, Kuala Lumpur, Malaysia pp. 307-312.

Abstract

Finding a feasible timetable efficiently is crucial in a two-stage optimization algorithm. Heuristics adopted from graph coloring theory have been used in many algorithms to solve timetabling problem. While it has been known that the application of these heuristics alone does not guarantee in producing feasible timetables, it will be useful if there exists any indicator of what condition the heuristics will lead to producing feasible timetables. In order to understand this condition, a constructive heuristic based on Least Saturation Degree First (LSDF) graph coloring is proposed in this work. Further, the quality of the generated feasible timetable is improved by a new operator based on a column permutation. These proposed algorithms attempt to solve the timetabling benchmark problems. Results are encouraging and provide useful insight into the solution of timetabling problem.

Item Type:	Conference Paper
Murdoch Affiliation(s):	School of Information Technology
Publisher:	IEEE
Copyright:	© 2012 IEEE.
URI:	http://researchrepository.murdoch.edu.au/id/eprint/11424

Item Control Page