Abstract
This work presents a simple graph based heuristic that employs a roulette wheel selection mechanism for solving exam timetabling problems. We arrange exams in non-increasing order of the number of conflicts (degree) that they have with other exams. The difficulty of each exam to be scheduled is estimated based on the degree of exams in conflict. The degree determines the size of a segment in a roulette wheel, with a larger degree giving a larger segment. The roulette wheel selection mechanism selects an exam if the generated random number falls within the exam’s segment. This overcomes the problem of repeatedly choosing and scheduling the same sequence of exams. We utilise the proposed Roulette Wheel Graph Colouring heuristic on the un-capacitated Carter’s benchmark datasets. Results showed that this simple heuristic is capable of producing feasible solutions for all 13 instances.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abdullah, S., Burke, E.K.: A Multi-Start Large Neighbourhood Search Approach with Local Search Methods for Examination Timetabling. In: Long, D., Smith, S.F., Borrajo, D., McCluskey, L. (eds.) ICAPS 2006, Cumbria, UK, pp. 334–337 (2006)
Asmuni, H., Burke, E.K., Garibaldi, J.M., McCollum, B.: Fuzzy multiple heuristic orderings for examination timetabling. In: Burke, E.K., Trick, M.A. (eds.) PATAT 2004. LNCS, vol. 3616, pp. 334–353. Springer, Heidelberg (2005)
Ayob, M., Malik, A.M.A., Abdullah, S., Hamdan, A.R., Kendall, G., Qu, R.: Solving a Practical Examination Timetabling Problem: A Case Study. In: Gervasi, O., Gavrilova, M.L. (eds.) ICCSA 2007, Part III. LNCS, vol. 4707, pp. 611–624. Springer, Heidelberg (2007)
Baker, J.: Reducing Bias and Inefficiency in the Selection Algorithm. In: Proceeding of the Second International Conference on Genetic Algorithms (ICGA 1987), pp. 14–21. L. Erlbaum Associates Inc., Hillsdale (1987)
Burke, E.K., Bykov, Y., Newall, J.P., Petrovic, S.: A Time-Predefined Local Search Approach to Exam Timetabling Problems. IIE Transactions on Operations Engineering 36, 509–528 (2004)
Burke, E.K., Eckersley, A.J., McCollum, B., Petrovic, S., Qu, R.: Hybrid Variable Neighbourhood Approaches to University Exam Timetabling. European Journal of Operational Research (to appear)
Burke, E.K., Elliman, D.G., Weare, R.F.: A Hybrid Genetic Algorithm for Highly Constrained Timetabling Problems. In: Proceedings of the 6th International Conference on Genetic Algorithms (ICGA 1995), pp. 605–610. Morgan Kaufmann, San Francisco (1995)
Burke, E.K., Kingston, J., de Werra, D.: Applications to timetabling. In: Gross, J., Yellen, J. (eds.) Handbook of Graph Theory, pp. 445–474. Chapman Hall/CRC Press, Boca Raton (2004)
Burke, E.K., Landa Silva, J.D.: The Design of Memetic Algorithms for Scheduling and Timetabling Problems. In: Hart, W.E., Krasnogor, N., Smith, J.E. (eds.) Studies in Fuzziness and Soft Computing: Recent Advances in Memetic Algorithms and Related Search Technologies, vol. 166, pp. 289–312. Springer, Heidelberg (2004)
Burke, E.K., McCollum, B., Meisels, A., Petrovic, S., Qu, R.: A Graph-Based Hyper-Heuristic for Educational Timetabling Problems. European Journal of Operational Research 176, 177–192 (2007)
Burke, E.K., Newall, J.: Enhancing timetable solutions with local search methods. In: Burke, E.K., De Causmaecker, P. (eds.) PATAT 2002. LNCS, vol. 2740, pp. 195–206. Springer, Heidelberg (2003)
Burke, E.K., Newall, J.P., Weare, R.F.: A Memetic Algorithm for University Exam Timetabling. In: Burke, E.K., Ross, P. (eds.) PATAT 1995. LNCS, vol. 1153, pp. 241–250. Springer, Heidelberg (1996)
Burke, E.K., Petrovic, S.: Recent Research Directions in Automated Timetabling. European Journal of Operational Research 140, 266–280 (2002)
Caramia, M., Dell’Olmo, P., Italiano, G.F.: New Algorithms for Examination Timetabling. In: Näher, S., Wagner, D. (eds.) WAE 2000. LNCS, vol. 1982, pp. 230–241. Springer, Heidelberg (2001)
Carter, M.W., Laporte, G.: Recent Developments in Practical Examination Timetabling. In: Burke, E.K., Ross, P. (eds.) PATAT 1995. LNCS, vol. 1153, pp. 3–21. Springer, Heidelberg (1996)
Carter, M.W., Laporte, G., Lee, S.Y.: Examination Timetabling: Algorithmic Strategies and Applications. Journal of Operational Research Society 47(3), 373–383 (1996)
Chu, S.C., Chen, Y.T., Ho, J.H.: Timetable Scheduling Using Particle Swarm Optimization. In: Proceedings of the 1st International Conference on Innovation computing, Information and Control, vol. 3, pp. 324–327 (2006)
Corr, P.H., McCollum, B., McGreevy, M.A.J., McMullan, P.: A New Neural Network Based Construction Heuristic for the Examination Timetabling Problem. In: Runarsson, T.P., Beyer, H.-G., Burke, E.K., Merelo-Guervós, J.J., Whitley, L.D., Yao, X. (eds.) PPSN 2006. LNCS, vol. 4193, pp. 392–401. Springer, Heidelberg (2006)
Costa, D., Hertz, A.: Ant can Colour Graphs. Journal of Operational Research Society 48, 295–305 (1997)
de Werra, D.: An Introduction to Timetabling. European Journal of Operational Research 19, 151–162 (1985)
Di Gaspero, L., Schaerf, A.: Tabu search techniques for examination timetabling. In: Burke, E., Erben, W. (eds.) PATAT 2000. LNCS, vol. 2079, pp. 104–117. Springer, Heidelberg (2001)
Dowsland, K., Thompson, J.: Ant Colony Optimisation for the Examination Scheduling Problem. Journal of the Operational Research Society 56, 426–439 (2005)
Eley, M.: Ant Algorithms for the Exam Timetabling Problem. In: Burke, E.K., Rudová, H. (eds.) PATAT 2007. LNCS, vol. 3867, pp. 364–382. Springer, Heidelberg (2007)
Kendall, G., Hussin, N.M.: Tabu Search Hyper-Heuristic Approach to the Examination Timetabling Problem at University Technology MARA. In: Burke, E.K., Trick, M.A. (eds.) PATAT 2004. LNCS, vol. 3616, pp. 199–218. Springer, Heidelberg (2005)
Merlot, L.T.G., Borland, N., Hughes, B.D., Stuckey, P.J.: A Hybrid Algorithm for the Examination Timetabling Problem. In: Burke, E.K., De Causmaecker, P. (eds.) PATAT 2002. LNCS, vol. 2740, pp. 207–231. Springer, Heidelberg (2003)
Qu, R., Burke, E.K., McCollum, B., Merlot, L.T.G., Lee, S.Y.: A Survey of Search Methodologies and Automated System Development for Examination Timetabling. Journal of Scheduling 12(1), 55–89 (2009)
Socha, K., Sampels, M., Manfrin, M.: Ant Algorithms for the University Course Timetabling Problem with Regard to State-of-the-Art. In: Proceedings of the 3rd European Workshop on Evolutionary Computation in Combinatorial Optimisation, Essex, UK, pp. 334–345 (2003)
Thompson, J., Dowsland, K.: A Robust Simulated Annealing Based Examination Timetabling System. Computers Operations Research 25, 637–648 (1998)
White, G.M., Xie, B.S.: Examination Timetables and Tabu Search with Longer-Term Memory. In: Burke, E., Erben, W. (eds.) PATAT 2000. LNCS, vol. 2079, pp. 85–103. Springer, Heidelberg (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sabar, N.R., Ayob, M., Kendall, G., Qu, R. (2009). Roulette Wheel Graph Colouring for Solving Examination Timetabling Problems. In: Du, DZ., Hu, X., Pardalos, P.M. (eds) Combinatorial Optimization and Applications. COCOA 2009. Lecture Notes in Computer Science, vol 5573. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-02026-1_44
Download citation
DOI: https://doi.org/10.1007/978-3-642-02026-1_44
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-02025-4
Online ISBN: 978-3-642-02026-1
eBook Packages: Computer ScienceComputer Science (R0)