Universal Method for Timetable Construction based on Evolutionary Approach

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.

Authors:

• Maciej Norberciak

Keywords:

• Evolutionary algorithms
• tabu search
• timetabling.

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)