A Tabu search heuristic with efficient diversification strategies for the class/teacher timetabling problem

ABSTRACT

The Class/Teacher Timetabling Problem (CTTP) deals with the weekly scheduling of encounters between teachers and classes of an educational institution. Since CTTP is a NP-hard problem for nearly all of its variants, the use of heuristic methods for its resolution is justified. This paper presents an efficient Tabu Search (TS) heuristic with two different memory based diversification strategies for CTTP. Results obtained through an application of the method to a set of real world problems show that it produces better solutions than a previously proposed TS found in the literature and faster times are observed in the production of good quality solutions.

REFERENCES

• 1: D. Abramson, Constructing school timetables using simulated annealing: sequential and parallel algorithms, Management Science, v.37 n.1, p.98-113, Jan. 1991 [doi>10.1287/mnsc.37.1.98]
• 2: Renata M. Aiex , Mauricio G. C. Resende , Celso C. Ribeiro, Probability Distribution of Solution Time in GRASP: An Experimental Investigation, Journal of Heuristics, v.8 n.3, p.343-373, May 2002 [doi>10.1023/A:1015061802659]
• 3: Bresina, J. 1996. Heuristic-biased stochastic sampling. In AAAI/IAAI, Vol. 1, 271--278.
• 4: Alberto Colorni , Marco Dorigo , Vittorio Maniezzo, Metaheuristics for High School Timetabling, Computational Optimization and Applications, v.9 n.3, p.275-298, March 1, 1998 [doi>10.1023/A:1018354324992]
• 5: Costa, D. 1994. A tabu search algorithm for computing an operational timetable. European Journal of Operational Research Society 76, 98--110.
• 6: Kathryn A. Dowsland, Off-the-Peg or Made-to-Measure? Timetabling and Scheduling with SA and TS, Selected papers from the Second International Conference on Practice and Theory of Automated Timetabling II, p.37-52, August 20-22, 1997
• 7: Even, S., Itai, A., and Shamir, A. 1976. On the complexity of timetabling and multicommodity flow problems. SIAM Journal on Computing 5, 691--703.
• 8: Michel Gendreau , Alain Hertz , Gilbert Laporte, A tabu search heuristic for the vehicle routing problem, Management Science, v.40 n.10, p.1276-1290, Oct. 1994 [doi>10.1287/mnsc.40.10.1276]
• 9: Fred Glover, Future paths for integer programming and links to artificial intelligence, Computers and Operations Research, v.13 n.5, p.533-549, May 1986 [doi>10.1016/0305-0548(86)90048-1]
• 10: Fred Glover , Fred Laguna, Tabu Search, Kluwer Academic Publishers, Norwell, MA, 1997
• 11: Hansen, P. 1986. The steepest ascent mildest descent heuristic for combinatorial programming. In Congress on Numerical Methods in Combinatorial Optimization. Capri.
• 12: Resende, M. and Ribeiro, C. 2003. Greedy randomized adaptive search procedures. In Handbook of Metaheuristics. Kluwer Academic Publ., Boston, MA. 219--249.
• 13: Schaerf, A. 1999. Local search techniques for large high-school timetabling problems. IEEE Trans. on Systems, Man and Cybernetics 29, 6, 368--377.
• 14: Souza, M. 2000. Timetabling in high-schools:approximation by metaheuristics (in portuguese). Ph.D. thesis, Universidade Federal do Rio de Janeiro, Brazil.
• 15: Marcone Jamilson Freitas Souza , Nelson Maculan , Luis Satoru Ochi, A GRASP-tabu search algorithm for solving school timetabling problems, Metaheuristics: computer decision-making, Kluwer Academic Publishers, Norwell, MA, 2004
• 16: Minghe Sun, Solving the uncapacitated facility location problem using tabu search, Computers and Operations Research, v.33 n.9, p.2563-2589, September 2006 [doi>10.1016/j.cor.2005.07.014]
• 17: Peter Wilke , Matthias Gröbner , Norbert Oster, A Hybrid Genetic Algorithm for School Timetabling, Proceedings of the 15th Australian Joint Conference on Artificial Intelligence: Advances in Artificial Intelligence, p.455-464, December 02-06, 2002

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Experimentation

Keywords:
Metaheuristics, tabu search, timetabling