Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

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.

Link to Published Version:
*Subscription may be required


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.
Item Control Page Item Control Page