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., Johnson, D.S. (1979) Computers and intractability: A guide to the theory of NP-completeness. San Francisco, CA, itd: W.H. Freeman Publishing
Glover, F.W., Laguna, M. (1997) Tabu search. Dordrecht, itd: Kluwer Academic
Hansen, P., Mladenović, N. (2002) Developments of variable neighborhood search. u: Ribeiro C.C., Hansen P. [ur.] Essays and Surveys in Metaheuristics, Kluwer Academic Publishers
Hertz, A., Plumettaz, M., Zufferey, N. (2006) Variable space search for graph coloring. Discrete Applied Mathematics, to appear, GERAD technical report g-2006-81, Montreal
Kernighan, B.W., Lin, S. (1970) An effective heuristic procedure for partitioning graphs. Bell System Technical Journal, 49, 291-307
Kochetov, Y., Levanova, T., Alekseeva, E., Loresh, M. (2005) Large neighborhood local search for the p-median problem. Yugoslav Journal of Operations Research, vol. 15, br. 1, str. 53-63
Mladenović, N., Plastria, F., Urošević, D. (2005) Reformulation descent applied to circle packing problems. Computers & Operations Research, vol. 32, br. 9, str. 2419-2434
Papadimitriou, C.H., Steiglitz, K. (1982) Combinatorial optimization: Algorithm and complexity. Englewood Cliffs, NJ, itd: Prentice Hall
Petrović, S., Burke, E. (2004) University timetabling. u: Leung J.Y.T. [ur.] Handbook of Scheduling: Algorithms, Models, and Performance Analysis, Chapman&Hall/CRC, 45,1-45,23
Santos, H.G., Ochi, L.S., Souza, M.J.F. (2004) A Tabu search heuristic with efficient diversification strategies for the class/teacher timetabling problem. u: Proceedings of the 5th International Conference on the Practice and Theory of Automated Timetabling, Pittsburgh, USA, 343-358
Downloads
Published
Issue
Section
License
Copyright (c) YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
