A hybrid method for solving timetabling problems based on the evolutionary approach

• Autorzy: Norberciak M.
• Języki publikacji: EN

Abstrakty

EN

Timetabling problems are often difficult and time-consuming to solve. Most of the methods of solving these problems are limited to one problem instance or class. This paper describes a universal method for solving large, highly constrained timetabling problems in various domains. The solution is based on an evolutionary algorithm framework and employs tabu search to quicken the solution finding process. Hyper-heuristics are used to establish the algorithm's operating parameters. The method has been used to solve three timetabling problems with promising results of extensive experiments.

Słowa kluczowe

EN

evolutionary algorithms; hybrid methods; time-table

• Wydawca: Politechnika Gdańska
• Czasopismo: TASK Quarterly : scientific bulletin of Academic Computer Centre in Gdansk
• Rocznik: 2007
• Tom: Vol. 11, No 1-2
• Strony: 137--149
• Opis fizyczny: Bibliogr. 20 poz., tab.

Twórcy

autor

Norberciak M.

• Institute of Applied Informatics, Wroclaw University of Technology, Wybrzeże Wyspiańskiego 27, 50-370 Wroclaw, Poland,

Bibliografia

• [1] Burke E K and Petrovic S 2002 Eur. J. Operational Res. 140 266
• [2] Burke E K, Newall J P and Weare R F 1998 Proc. Int. ICSC Symposium on Engineering of Intelligent Systems, ICSC Academic Press, Nottingham, pp. 574-579
• [3] Myszkowski P and Norberciak M 2003 Annales UMCS, Sectio Informatica, Lublin, I 115
• [4] Yakhno T and Tekin E 2002 Proc. EurAsia-ICT 2002, Teheran, Iran, Springer-Verlag, pp. 11-18
• [5] Colorni A, Dorigo M and Maniezzo V 1990 Proc. 1st Int. Workshop on Parallel Problem Solving from Nature, Lecture Notes in Computer Science 496 55
• [6] Newall J P 1999 Hybrid Methods for Automated Timetabling, PhD Thesis, Department of Computer Science, University of Nottingham
• [7] Ross P and Come D 1995 AISB Workshop, Lecture Notes in Computer Science, Sheffield, UK (Fogarty T, Ed.), Springer- Verlag, 993, pp. 94-102
• [8] Valouxis C and Housos E 2000 Artif. Intell. Med. 20 155
• [9] Carter M W 2001 Proc. PATAT 2000, Constance, Germany (Burke E and Erben W, Eds), Springer- Verlag, pp. 64-84
• [10] McCollum B 1998 Proc. PATAT 1997, Toronto, Canada (Burke E and Carter M, Eds), Springer-Verlag, pp. 237-253
• [11] Ross P, Hart E and Come D 1998 Proc. PATAT 1997, Toronto, Canada (Burke E and Carter M, Eds), Springer- Verlag, pp. 115-129
• [12] Socha K, Knowles J and Sampels M 2002 Proc. ANTS 2002, Brussels, Belgium, Springer-Verlag, pp. 1-13
• [13] 2002 International Timetabling Competition, http://www.idsia.ch/Files/ttcomp2002/
• [14] Norberciak M 2003 Proc. 9th Int. Conf. on Soft Computing MENDEL 2003, Brno, Czech Republic, pp. 19-23
• [15] Michalewicz Z 1996 Genetic Algorithms + Data Structures = Evolution Programs, Springer Verlag
• [16] Come D and Ross P 1995 Proc. 1st Int. Conf. on the Theory and Practice of Automated Timetabling, Napier University, Edinburgh, pp. 227-240
• [17] Come D, Ross P and Fang H-L 1994 Improving Evolutionary Timetabling with Delta Evaluation and Directed Mutation, Parallel Problem Solving from Nature III, Springer Verlag
• [18] Burke E K, Petrovic S, Meisels A and Qu R 2004 Computer Science Technical Report, No. NOTTCS-TR-2004-9, University of Nottingham
• [19] Norberciak M 2004 1. Med. Inform. Technol. 7 83
• [20] Ernst A T, Jiang H, Krishnamoorthy M and Sier D 2004 Eur. J. Operational Res. 153 3