Formulation space search approach for the teacher/class timetabling problem
DOI:
https://doi.org/10.2298/YJOR0801001KKeywords:
timetable design, metaheuristics, local search, FSS approachAbstract
We consider the well known NP-hard teacher/class timetabling problem. Variable neighborhood search and tabu search heuristics are developed based on idea of the Formulation Space Search approach. Two types of solution representation are used in the heuristics. For each representation we consider two families of neighborhoods. The first family uses swapping of time periods for teacher (class) timetable. The second family bases on the idea of large Kernighan-Lin neighborhoods. Computation results for difficult random test instances show high efficiency of the proposed approach. .References
Garey, M.R., and Johnson, D.S., Computers and Intractability: A Guide to the Theory of NP Completeness, Freeman, San Francisco, CA, 1979.
Glover, F., and Laguna, M., Tabu Search, Kluwer Academic Publishers, Boston–Dordrecht London, 1997.
Hansen, P., Mladenović, N., "Developments of Variable Neighborhood Search", in: Ribeiro, C.C., Hansen, P. (eds.) Essays and Surveys in Metaheuristics, Kluwer Academic Publishers, 2002, 415-440.
Hertz, A., Plumettaz, M., and Zufferey, N., "Variable space search for graph coloring", GERAD technical report g-2006-81, Montreal 2006 (to appear in Discrete Applied Mathematics).
Kernighan, B.W., and Lin, S., "An efficient heuristic procedure for partitioning graphs", Bell System Technical Journal, 49 (1970) 291-307.
Kochetov, Y., Alekseeva, E., Levanova, T., and Loresh, M., "Large neighborhood local search for the p–median problem", Yugoslav Journal of Operations Research, 15 (1) (2005) 53-63.
Mladenović, N., Plastria, F., and Urošević, D., "Reformulation descent applied to circle packing problems”, Computers and Operations Research, 32 (9) (2005) 2419-2434.
Papadimitriou, C.H., and Steiglitz, K., Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, Englewood Cliffs, NJ, 1982.
Petrovic, S., and Burke, E., "University timetabling”, in: J.Y-T. Leung (ed.) Handbook of Scheduling: Algorithms, Models, and Performance Analysis, Chapman&Hall/CRC, 2004, 45.1-45.23.
Santos, H.G., Ochi, L.S., and Souza, M.J.F., "A Tabu search heuristic with efficient diversification strategies for the class/teacher timetabling problem”, Proceedings of the 5th International Conference on the Practice and Theory of Automated Timetabling, Pittsburgh, USA, 2004, 343-358.
Downloads
Published
Issue
Section
License
Copyright (c) 2008 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
