Universal Method for Timetable Construction based on Evolutionary Approach

Authors: Maciej Norberciak

Abstract:

Timetabling problems are often hard and timeconsuming to solve. Most of the methods of solving them concern only one problem instance or class. This paper describes a universal method for solving large, highly constrained timetabling problems from different domains. The solution is based on evolutionary algorithm-s framework and operates on two levels – first-level evolutionary algorithm tries to find a solution basing on given set of operating parameters, second-level algorithm is used to establish those parameters. Tabu search is employed to speed up the solution finding process on first level. The method has been used to solve three different timetabling problems with promising results.

Keywords: Evolutionary algorithms, tabu search, timetabling.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1333937

References:

[1] Burke E.K., Petrovic S., Recent research directions in automated timetabling, European Journal of Operational Research 140 (2002)
[2] Burke E. K., Newall J. P., Weare R. F., A Simple Heuristically Guided Search for the Timetable Problem, Proceedings of the International ICSC Symposium on Engineering of Intelligent Systems, ICSC Academic Press, Nottingham (1998)
[3] Newall J. P., Hybrid Methods for Automated Timetabling, PhD Thesis, Department of Computer Science, University of Nottingham (1999)
[4] Do M.B., Kambhampati S., Planning as constraint satisfaction: Solving the planning graph by compiling it into CSP, Artificial Intelligence 132, 2001
[5] Yakhno T., Tekin E.: Application of Constraint Hierarchy to Timetabling Problems, Proceedings of EurAsia-ICT 002, Springer- Verlag, 2002
[6] Colorni A., Dorigo M., Maniezzo V., Genetic Algorithms and Highly Constrained Problems: the Time-Table Case, Proceedings of the First International Workshop on Parallel Problem Solving from Nature, Lecture Notes in Computer Science 496 (1990)
[7] Myszkowski P., Norberciak M., Evolutionary Algorithms for Timetable Problems, Annales UMCS, Sectio Informatica, vol. I, Lublin (2003)
[8] Ross P., Corne D., Comparing GA, SA and Stochastic Hillclimbing on Timetabling Problems. Evolutionary Computing; AISB Workshop, Sheffield 1995, Selected Papers, ed. T. Fogarty, Springer-Verlag Lecture Notes in Computer Science 993 (1995)
[9] Valouxis C., Housos E., Hybrid optimization techniques for the workshift and rest assignment of nursing personnel, Artificial Intelligence in Medicine 20 (2000)
[10] Burke E.K., MacCarthy B., Petrovic S., Qu R., Structured cases in casebased reasoning - re-using and adapting cases for timetabling problems. Knowledge-Based Systems 13 (2000)
[11] Foulds L.R., Johnson D.G., SlotManager: a microcomputer-based decision support system for university timetabling, Decision Support Systems 27, 2000
[12] Lee S.-J., Wu C.-H., CLXPERT: A Rule-Based Scheduling System, Expert Systems With Applications, Vol. 9, No. 2, 1995
[13] Carter M.W., A Comprehensive Course Timetabling and Student Scheduling System at the University of Waterloo, E. Burke, W. Erben (Eds.): Proceedings of PATAT 2000, Springer-Verlag (2001)
[14] McCollum B., The Implementation of a Central Timetabling System in a Large British Civic University, E. Burke, M. Carter (Eds.): Proceedings of PATAT 1997, Springer-Verlag (1998)
[15] Ross P., Hart E., Corne D., Some Observations about GA-Based Exam Timetabling, E. Burke, M. Carter (Eds.): Proceedings of PATAT 1997, Springer-Verlag (1998)
[16] Socha K., Knowles J., Sampels M., A MAX-MIN Ant System for the University Course Timetabling Problem, Proceedings of ANTS 2002, Springer-Verlag (2002)
[17] Norberciak M., Artificial Intelligence Technique for Planning Duties in Hospital , Journal of Medical Informatics & Technologies, Vol. 7 (2004)
[18] International Timetabling Competition, Available: http://www.idsia.ch/Files/ttcomp2002/ (2002)
[19] Norberciak M., Feasible genotype initialization for evolutionary timetabling, Proceedings of 9th International Conference on Soft Computing MENDEL 2003, Brno (2003)
[20] Michalewicz Z., Genetic Algorithms + Data Structures = Evolution Programs, Springer Verlag (1996)
[21] Corne D., Ross P., Peckish Initialisation Strategies for Evolutionary Timetabling. Proceedings of the First International Conference on the Theory and Practice of Automated Timetabling, Napier University, Edinburgh (1995).
[22] Corne D., Ross P., Fang H.-L., Improving Evolutionary Timetabling with Delta Evaluation and Directed Mutation, Parallel Problem Solving from Nature III, Springer Verlag (1994)
[23] Burke E.K., Petrovic S., Meisels A., Qu R., A Graph-Based Hyper Heuristic for Timetabling Problems, Computer Science Technical Report No. NOTTCS-TR-2004-9, University of Nottingham (2004)
[24] Dowsland K.: Nurse scheduling with Tabu Search and Strategic Oscillation. EJOR 106, (1998)
[25] Di Gaspero and Schaerf A. Tabu search techniques for examination timetabling. In: Burke E and Erben W (eds). The Practice and Theory of Automated Timetabling: Selected Papers from the 3rd International Conference. Lecture Notes in Computer Science, Vol. 2079. Springer- Verlag, Berlin, (2000).
[26] Ernst A.T., Jiang H., Krishnamoorthy M., SIER D., Staff scheduling and rostering: A review of applications, methods and models, European Journal of Operational Research 153 (2004)