Conference paper
A pure graph coloring constructive heuristic in timetabling
2012 International Conference on Computer & Information Science (ICCIS), pp.307-312
IEEE
International Conference on Computer and Information Science, ICCIS 2012 - A Conference of World Engineering, Science and Technology Congress, ESTCON 2012 (Kuala Lumpur, Malaysia, 12/06/2012–14/06/2012)
2012
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.
Details
- Title
- A pure graph coloring constructive heuristic in timetabling
- Authors/Creators
- T.A. Budiono (Author/Creator) - Murdoch UniversityK.W. Wong (Author/Creator) - Murdoch University
- Publication Details
- 2012 International Conference on Computer & Information Science (ICCIS), pp.307-312
- Conference
- International Conference on Computer and Information Science, ICCIS 2012 - A Conference of World Engineering, Science and Technology Congress, ESTCON 2012 (Kuala Lumpur, Malaysia, 12/06/2012–14/06/2012)
- Publisher
- IEEE
- Identifiers
- 991005542556907891
- Copyright
- © 2012 IEEE.
- Murdoch Affiliation
- School of Information Technology
- Language
- English
- Resource Type
- Conference paper
Metrics
41 Record Views