An effective hybrid algorithm for university course timetabling.

*(English)*Zbl 1154.90428Summary: The university course timetabling problem is an optimisation problem in which a set of events has to be scheduled in timeslots and located in suitable rooms. Recently, a set of benchmark instances was introduced and used for an ‘International Timetabling Competition’ to which 24 algorithms were submitted by various research groups active in the field of timetabling. We describe and analyse a hybrid metaheuristic algorithm which was developed under the very same rules and deadlines imposed by the competition and outperformed the official winner. It combines various construction heuristics, tabu search, variable neighbourhood descent and simulated annealing. Due to the complexity of developing hybrid metaheuristics, we strongly relied on an experimental methodology for configuring the algorithms as well as for choosing proper parameter settings. In particular, we used racing procedures that allow an automatic or semi-automatic configuration of algorithms with a good save in time. Our successful example shows that the systematic design of hybrid algorithms through an experimental methodology leads to high performing algorithms for hard combinatorial optimisation problems.

##### MSC:

90B35 | Deterministic scheduling theory in operations research |

##### Keywords:

University course timetabling; Local search methods; Metaheuristics; Hybrid algorithms; Experimental methodology; Algorithm engineering
PDF
BibTeX
XML
Cite

\textit{M. Chiarandini} et al., J. Sched. 9, No. 5, 403--432 (2006; Zbl 1154.90428)

Full Text:
DOI

##### References:

[1] | Arntzen, H. and A. Løkketangen, ”A tabu search heuristic for a university timetabling problem,” in Proceedings of the Fifth Metaheuristics International Conference, Kyoto, Japan (Aug. 2003). |

[2] | Birattari, M., The Problem of Tuning Metaheuristics, as seen from a Machine Learning Perspective. PhD thesis, Université Libre de Bruxelles, Brussels, Belgium (2004). · Zbl 1101.68748 |

[3] | Birattari, M., ”The race package for R. Racing methods for the selection of the best,” Technical Report TR/IRIDIA/2003-37, IRIDIA, Université Libre de Bruxelles, Brussels, Belgium (2003). |

[4] | Birattari, M., T. Stützle, L. Paquete, and K. Varrentrapp, ”A Racing algorithm for configuring metaheuristics,” in W. B. Langdon, E. Cantú-Paz, K. Mathias, R. Roy, D. Davis, R. Poli, K. Balakrishnan, V. Honavar, G. Rudolph, J. Wegener, L. Bull, M.A. Potter, A.C. Schultz, J.F. Miller, E. Burke, and N. Jonoska (eds.), Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2002), pp. 11–18, New York, 2002. Morgan Kaufmann Publishers. |

[5] | Burke, E. K., A. J. Eckersley, B. McCollum, S. Petrovic, and R. Qu., ”Analysing similarity in examination timetabling,” in E. K. Burke and M. Trick, Proceedings of the 5th International Conference on the Practice and Theory of Automated Timetabling. 2004, pp. 557–559. |

[6] | Burke, E. K., C. Beyrouthy, J. D. Landa Silva, B. McCollum, and P. McMullan, ”SpaceMAP-applying meta-heuristics to real world space allocation problems in academic institutions,” in E. K. Burke and M. Trick (eds.), Proceedings of the 5th International Conference on the Practice and Theory of Automated Timetabling. 2004, pp. 441–444. |

[7] | Burke, E. K., D. G. Elliman, and R. F. Weare, ”Specialised recombinative operators for timetabling problems,” in AISB Workshop on Evolutionary Computing, Springer Verlag Notes in Computer Science Volume 993, pp. 75–85. Springer Verlag, Berlin, Germany (1995). |

[8] | Burke, E. K., G. Kendall, and E. Soubeiga, ”A tabu-search hyperheuristic for timetabling and rostering,” Journal of Heuristics, 9(6), 451–470 (2003). · doi:10.1023/B:HEUR.0000012446.94732.b6 |

[9] | Burke, E. K., J. P. Newall, and R. F. Weare, ”A memetic algorithm for university exam timetabling,” in E. K. Burke and P. Ross Practice and Theory of Automated Timetabling, Springer Lecture Notes in Computer Science Volume 1153, pp. 241–250. |

[10] | Burke, E. K. and M. A. Trick (eds.), Practice and Theory of Automated Timetabling V, 5th International Conference, PATAT 2004, vol. 3616 of Lecture Notes in Computer Science. Springer Verlag, Berlin, Germany (2005). |

[11] | Burke, E. K., and M. Trick (eds.), Proceedings of the 5th International Conference on the Practice and Theory of Automated Timetabling. PATAT 2004, Pittsburgh, PA (Aug. 2004). |

[12] | Burke, E. K. and M. W. Carter (eds.), Practice and Theory of Automated Timetabling II, Second International Conference, PATAT 1997, vol. 1408 of Lecture Notes in Computer Science. Springer Verlag, Berlin, Germany (1998). |

[13] | Burke, E. K. and P. de Causmaecker (eds.), Practice and Theory of Automated Timetabling IV, 4th International Conference, PATAT 2002, vol. 2740 of Lecture Notes in Computer Science. Springer Verlag, Berlin, Germany (2003). |

[14] | Burke, E. K. and P. Ross (eds.), Practice and Theory of Automated Timetabling, First International Conference, PATAT 1995, vol. 1153 of Lecture Notes in Computer Science. Springer Verlag, Berlin, Germany, (1996). |

[15] | Burke, E. K. and S. Petrovic. ”Recent research directions in automated timetabling,” European Journal of Operational Research, 140(2), 266–280 (2002). · Zbl 1001.90030 · doi:10.1016/S0377-2217(02)00069-3 |

[16] | Burke, E. K. and W. Erben (eds.), Practice and Theory of Automated Timetabling III, Third International Conference, PATAT 2000, vol. 2079 of Lecture Notes in Computer Science. Springer Verlag, Berlin, Germany (2001). · Zbl 0968.68560 |

[17] | Burke, E. K., Y. Bykov, and S. Petrovic, ”A multicriteria approach to examination timetabling,” in E. K. Burke and W. Erben, Practice and Theory of Automated Timetabling, Springer Lecture Notes in Computer Science Volume 1153, pp. 118–131. · Zbl 0982.68522 |

[18] | Burke, E. K., Y. Bykov, J. Newall, and S. Petrovic, ”A time-predefined approach to course timetabling,” Yugoslav Journal of Operations Research, 13(2), 139–151 (2003). · Zbl 1055.90039 · doi:10.2298/YJOR0302139B |

[19] | Carter, M. W. and G. Laporte, ”Recent developments in practical course timetabling,” in E. K. Burke and M. W. Carter (eds.), Practice and Theory of Automated Timetabling, Springer Lecture Notes in Computer Science Volume 1408, pp. 3–19. |

[20] | Carter, M. W., G. Laporte, and S. Y. Lee, ”Examination timetabling: Algorithmic strategies and applications,” Journal of the Operational Research Society, 47, 373–383 (1996). |

[21] | Chand, A., ”A constraint based generic model for representing complete university timetabling data,” in E. K. Burke and M. A. Trick (eds.), Proceedings of the 5th International Conference on the Practice and Theory of Automated Timetabling. 2004, pp. 125–150. |

[22] | Chiarandini, M. and T. Stützle, ”Experimental evaluation of course timetabling algorithms.” Technical Report AIDA-02-05, Intellectics Group, Computer Science Department, Darmstadt University of Technology, Darmstadt, Germany (April 2002). |

[23] | Chiarandini, M., Stochastic Local Search Methods for Highly Constrained Combinatorial Optimisation Problems. PhD thesis, Computer Science Department, Darmstadt University of Technology, Darmstadt, Germany, (Aug. 2005). |

[24] | Cohen, P. R., Empirical Methods for Artificial Intelligence. MIT Press, Boston (1995). · Zbl 0850.68260 |

[25] | Conover, W. J., Practical Nonparametric Statistics. 3rd edn, John Wiley & Sons, New York, NY, USA (1999). |

[26] | Culberson, J. C., ”Iterated greedy graph coloring and the difficulty landscape,” Technical Report 92-07, Department of Computing Science, The University of Alberta, Edmonton, Alberta, Canada (June 1992). |

[27] | Custers, N. P. De Causmaecker, P. Demeester, and G. V. Berghe, ”Semantic components for timetabling,” in E. K. Burke and M. A. Trick (eds.), Practice and Theory of Automated Timetabling, Springer Lecture Notes in Computer Science Volume 3616, pp. 17–33. |

[28] | De Werra. D., ”An introduction to timetabling,” European Journal of Operational Research, 19(2), 151–162 (1985). · Zbl 0553.90059 · doi:10.1016/0377-2217(85)90167-5 |

[29] | den Besten, M. L. Simple Metaheuristics for Scheduling: An Empirical Investigation into the Application of Iterated Local Search to Deterministic Scheduling Problems with Tardiness Penalties. PhD thesis, Darmstadt University of Technology, Darmstadt, Germany, October (2004). |

[30] | Di Gaspero, L. and A. Schaerf, ”Writing local search algorithms using EASYLOCAL++,” in S. Voß and D.L. Woodruff, (eds.), Optimization Software Class Libraries, pp. 81–154. Kluwer Academic Publishers, Boston, MA, USA (2002). |

[31] | Fink, A. and S. Voß, ”A heuristic optimization framework,” in S. Voß and D.L. Woodruff (eds.), Optimization Software Class Libraries, pp. 81–154. Kluwer Academic Publishers, Boston, MA, USA (2002). |

[32] | Garey, M. R. and D. S. Johnson, Computers and Intractability: A Guide to the Theory of \({\mathcal {NP}}\) -Completeness. Freeman, San Francisco, CA, USA (1979). · Zbl 0411.68039 |

[33] | Hertz, A. and D. de Werra, ”Using tabu search techniques for graph coloring,” Computing, 39(4), 345–351 (1987). · Zbl 0626.68051 · doi:10.1007/BF02239976 |

[34] | Hoos, H. H. and T. Stützle, ”Characterising the behaviour of stochastic local search,” Artificial Intelligence, 112(1–2), 213–232 (1999). · Zbl 0996.68069 · doi:10.1016/S0004-3702(99)00048-X |

[35] | Hoos, H. H., and T. Stützle, ”Evaluating Las Vegas algorithms–Pitfalls and remedies,” in G. F. Cooper and S. Moral (eds.), Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence (UAI-98), pp. 238–245. Morgan Kaufmann Publishers, San Francisco, CA, USA (1998). |

[36] | Johnson, D. S., C. R. Aragon, L. A. McGeoch, and C. Schevon, ”Optimization by simulated annealing: An experimental evaluation; part II, graph coloring and number partitioning,” Operations Research, 39(3), 378–406 (1991). · Zbl 0739.90055 · doi:10.1287/opre.39.3.378 |

[37] | Kostuch, P., ”The university course timetabling problem with a three-phase approach,” in E. K. Burke and M. A. Trick, Practice and Theory of Automated Timetabling, Springer Lecture Notes in Computer Science Volume 3616, pp. 109–125. |

[38] | Kostuch, P., ”University course timetabling,” Transfer Thesis, Oxford University, England (2003). · Zbl 1177.68191 |

[39] | Kostuch, P. and K. Socha, ”Hardness prediction for the university course timetabling problem,” in J. Gottlieb and G. R. Raidl, (eds.), Evolutionary Computation in Combinatorial Optimization, Springer Lecture Notes in Computer Science Volume 3004, pp. 132–141. Springer Verlag, Berlin, Germany (2004). · Zbl 1177.68191 |

[40] | Lourenço, H. R., O. Martin, and T. Stützle, ”Iterated local search,” in F. Glover and G. Kochenberger (eds.), Handbook of Metaheuristics, 321–353. Kluwer Academic Publishers, Norwell, MA, USA (2002). |

[41] | Morgenstern, C. and H. Shapiro, ”Coloration neighborhood structures for general graph coloring,” in Proceedings of the first Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 226–235. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (1990). · Zbl 0800.68609 |

[42] | Newall, J. P., Hybrid Methods for Automated Timetabling. PhD thesis, Department of Computer Science, University of Nottingham, UK, May (1999). |

[43] | Papadimitriou, C. H. and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Inc., Englewood Cliffs, NJ, 1982. · Zbl 0503.90060 |

[44] | Post, G. and B. Veltman. ”Harmonious personnel scheduling,” in E. K. Burke and M. A. Trick (eds.), Proceedings of the 5th International Conference on the Practice and Theory of Automated Timetabling. PATAT 2004, pp. 557–559. |

[45] | Risler, M., M. Chiarandini, L. Paquete, T. Schiavinotto, and T. Stützle, ”An algorithm for the car sequencing problem of the ROADEF 2005 challenge,” Technical Report AIDA-04-06, Intellectics Group, Computer Science Department, Darmstadt University of Technology (2004). |

[46] | Rossi-Doria, O. and B. Paeehter, ”An hyperheuristic approach to course timetabling problem using evolutionary algorithm,” Technical Report CC-00970503, Napier University, Edinburgh, Scotland (2003). |

[47] | Rossi-Doria, O., B. Paechter, C. Blum, K. Socha, and M. Samples, ”A local search for the timetabling problem.” in E. Burke and P. Causmaecker (eds.), Proceedings of the 4th International Conference on the Practice and Theory of Automated Timetabling, PATAT 2002, pp. 124–127 Gent, Belgium (August 2002). |

[48] | Rossi-Doria, O., M. Samples, M. Birattari, M. Chiarandini, M. Dorigo, L. Gambardella, J. Knowles, M. Manfrin, M. Mastrolilli, B. Paechter, L. Paquete, and T. Stützle, ”A comparison of the performance of different metaheuristics on the timetabling problem,” in E. K. Burke and P. De Causmaecker, Practice and Theory of Automated Timetabling, Springer Lecture Notes in Computer Science Volume 2740, pp. 329–351. |

[49] | Schaerf, A., ”A survey of automated timetabling,” Artificial Intelligence Review, 13(2), 87–127 (1999). · Zbl 05467698 · doi:10.1023/A:1006576209967 |

[50] | Sedgewick, R. Algorithms. 2nd edn., Addison-Wesley, Reading, MA, USA (1988). |

[51] | Setubal, J. C., ”Sequential and parallel experimental results with bipartite matching algorithms,” Technical Report EC-96-09, Institute of Computing, University of Campinas, Brasil (1996). |

[52] | Sheskin, D. J., Handbook of Parametric and Nonparametric Statistical Procedures. 2nd edn., Chapman & Hall (2000). · Zbl 0955.62003 |

[53] | Socha, K., ”The influence of run-time limits on choosing ant system parameters,” in Cantu-Paz et al. (eds), Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2003), vol. 2723 of Lecture Notes in Computer Science, pp. 49–60. Springer Verlag, Berlin, Germany (July 2003). · Zbl 1028.68887 |

[54] | Socha, K., M. Sampels, and M. Manfrin, ”Ant algorithms for the university course timetabling problem with regard to the state-of-the-art,” in Günther R. Raidl, Jean-Arcady Meyer, Martin Middendorf, Stefano Cagnoni, Juan J. Romero Cardalda, David Corne, Jens Gottlieb, Agnès Guillot, Emma Hart, Colin G. Johnson, and Elena Marchiori (eds.), Applications of Evolutionary Computing: Proceedings of Evo Workshops 2003, vol. 2611 of Lecture Notes in Computer Science, pp. 334–345. Springer Verlag, Berlin, Germany (2003). |

[55] | Terashima-Marín, H., P. Ross, and M. Valenzuela-Rendón, ”Evolution of constraint satisfaction strategies in examination timetabling,” in W. Banzhaf, J. M. Daida, A. E. Eiben, M. H. Garzon, V. Honavar, M. J. Jakiela, and R. E. Smith (eds.), Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-1999), pp. 635–642. Morgan Kaufmann Publishers, San Francisco, CA, USA (1999). |

[56] | Thompson, J. and K. Dowsland, ”A robust simulated annealing based examination timetabling system,” Computers and Operations Research, 25(7–8), 637–648 (1998). · Zbl 1042.90568 · doi:10.1016/S0305-0548(97)00101-9 |

[57] | Wren, A.,”Scheduling, timetabling and rostering–a special relationship?,” In E. K. Burke and P. Ross (eds.), Practice and Theory of Automated Timetabling, Springer Lecture Notes in Computer Science Volume 1153, pp. 46–75 (1996). |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.