Solving the International Timetabling Competition : a Deterministic Approach

• Autorzy: Chavez-Bosquez O. , Pozos-Parra P. , Lengyel F.
• Języki publikacji: EN

Abstrakty

EN

The Course Timetabling Problem consists of the weekly scheduling of lectures of a collection of university courses, subject to certain constraints. The International Timetabling Competitions, ITC-2002 and ITC-2007, have been organized with the aim of creating a common formulation for comparison of solution proposals. This paper discusses the design and implementation of an extendable family of sorting-based mechanisms, called Sort Then Fix (STF) algorithms. ITC-2002 and ITC-2007 Post Enrolment based Course Timetabling problem instances were used in this study. The STF approach is deterministic, and does not require swapping or backtracking. Almost all solutions run in less than 10% of the ITC-2002 and less than 2% of the ITC-2007 benchmark times, respectively.

Słowa kluczowe

EN

Course Timetabling Problem; International Timetabling Competition; STF algorithm; scheduling problem; Deterministic Search

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 113, nr 1
• Strony: 1--18
• Opis fizyczny: Bibliogr. 15 poz., tab.

Twórcy

autor

Chavez-Bosquez O.

autor

Pozos-Parra P.

autor

Lengyel F.

• Department of Informatics and Systems, University of Tabasco, Carretera Cunduacan - Jalpa Km. 1, Tabasco, Mexico,

Bibliografia

• [1] de Werra, D.: An introduction to timetabling, European Journal of Operational Research, (1985)
• [2] Gotlieb, H.: The construction of class-teacher timetables, IFIP Congress, (1963)
• [3] Socha, K., Knowles, J., Sampels, M.: AMAX −MIN Ant System for the University Timetabling Problem. Algorithmic Number Theory. LNCS, 2369 (2002)
• [4] Kostuch, P: The university course timetabling problem with a three-phase approach. PATAT 2004, LNCS, 3616 (2005)
• [5] Rossi-Doria, O., Blum, C., Knowles, J., Sampels, M., Socha, K., Paechter, B.:, A local search for the timetabling problem, PATAT (2002)
• [6] Chiarandini, M., Birattari, M., Socha, K., Rossi-Doria, O.: An effective hybrid approach for the university course timetabling problem. Journal of Scheduling, 9 (2006) 403-432
• [7] di Gaspero, L., Schaerf, A.: Timetabling Competition TTComp 2002: Solver Description, (viewed January, 2010) (updated July 10, 2003), http://www.idsia.ch/Files/ttcomp2002/schaerf.pdf
• [8] Frausto-Solis, J.F., Alonso-Pecina, F., Larre, M. Gonzalez-Segura, C., Gomez-Ramos, J.L.: Solving the timetabling problem with three heuristics. WSEAS Transactions on Computers. 11-5 (2006)
• [9] Kostuch, P. Socha, K.:, Hardness prediction for the University Course Timetabling problem, Proceedings of the Evolutionary Computation in Combinatorial Optimization EvoCOP, (2004)
• [10] Socha, K.: Metaheuristics for the Timetabling Problem. DEA Thesis, Universite Libre de Bruxelles, (2003)
• [11] Rossi-Doria, O., Sampels, M., Birattari, M., Chiarandini, M., Dorigo, M., Gambardello, L.M., Knowles, J., Manfrin, M., Mastrolilli, M., Paechter, B., Paquette, L., Stutzle, T.: A comparison of the performance of dfferent metaheuristics on the timetabling problem. PATAT 2002, LNCS, 2740 (2003) 329-351
• [12] Paechter, B., Gambardella, L.M., Rossi-Doria, O.: International Timetabling Competition Webpage (2003) (viewed January, 2010) (updated July 10, 2003), http://www.idsia.ch/Files/ttcomp2002/
• [13] McCollumn, B.: International Timetabling Competition Webpage (2007) (viewed January, 2010) (updated October 1, 2008), http://www.cs.qub.ac.uk/itc2007/
• [14] Barry McCollum, Andrea Schaerf, Ben Paechter, Paul McMullan, Rhyd Lewis, Andrew J. Parkes, Luca Di Gaspero, Rong Qu, and Edmund K. Burke Setting the Research Agenda in Automated Timetabling: The Second International Timetabling Competition INFORMS JOURNAL ON COMPUTING 2010 22: 120-130, DOI: 10.1287/ijoc.1090.0320.
• [15] Andrea Schaerf. A survey of automated timetabling. Artificial Intelligence Review, 13(2):87-127, (1999