Construction of examination timetables based on ordering heuristics

In this paper, we combine graph coloring heuristics, namely largest degree and saturation degree with the concept of a heuristic modifier under the framework of squeaky wheel optimization for solving a set of examination timetabling problems. Both components interact adaptively to determine the best ordering of examinations to be processed at each iteration. A variety of approaches using different combinations of graph coloring heuristics and heuristic modifiers are investigated on a benchmark of examination timetabling problems. Experimental results show that our approaches can produce high quality solutions that are comparable to the ones obtained from previously proposed constructive methods. We conclude that our approach is simple, yet effective.