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.
*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.
|Publication Type:||Conference Paper|
|Murdoch Affiliation:||School of Information Technology|
|Copyright:||© 2012 IEEE.|
|Item Control Page|