Construction of examination timetables based on ordering heuristics

Citation

Rahman SA, Bargiela A, Burke E, Ozcan E & McCollum B (2009) Construction of examination timetables based on ordering heuristics. In: Vural F, Yazici A, Toroslu H, Can T, Senkul P & Sacan A (eds.) 2009 24th International Symposium on Computer and Information Sciences, ISCIS 2009. 2009 24th International Symposium on Computer and Information Sciences, ISCIS 2009, Guzelyurt, Northern Cyprus, 14.09.2009-16.09.2009. Red Hook, NJ, USA: IEEE, pp. 680-685. http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=5291905; https://doi.org/10.1109/ISCIS.2009.5291905

Abstract
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.

Keywords
computational complexity; graph theory; optimisation