Metaheurystyczne metody optymalizacji dyskretnej w problemie układania rozkładów zajęć dla szkół wyższych

• Autorzy: Piwakowski K. , Szyfelbein D.

Warianty tytułu

EN

Metaheuristic methods of discrete optimization for university timetabling problem

• Języki publikacji: PL

Abstrakty

PL

W pracy rozważany jest problem układania rozkładów zajęć dla szkoły wyższej. Do rozwiązania tego zagadnienia wykorzystane zostały następujące metody lokalnego i globalnego przeszukiwania przestrzeni możliwych rozwiązań: symulowane wyżarzanie, przeszukiwanie tabu oraz algorytmy genetyczne. Zaproponowano rozwiązanie polegające na przekształceniu problemu harmonogramowania zajęć w problem kolorowania grafów, który rozwiązywany jest za pomocą każdej z wymienionych metod. W pracy opisane są głównie doświadczenia komputerowe zaprojektowane i wykonane dla rozwiązania problemu układania rozkładów zajęć, mające na celu zarówno gruntowną analizę badanych metod jak i wskazanie tej, której zastosowanie daje najlepsze rezultaty. Doświadczenia te zostały przeprowadzone na danych generowanych w sposób losowy oraz na danych rzeczywistych pobranych z systemu wspomagającego układanie rozkładów zajęć dla Wydziału Elektroniki, Telekomunikacji i Informatyki Politechniki Gdańskiej.

EN

In paper we consider a university timetabling problem. The following methods of local and global search of a solution space are used: simulated annealing, tabu search and genetic algorithms. We propose an approach based on a transformation of the basic problem to a graph coloring problem which is then solved with each of the methods. Mainly, computational tests, which were designed to analyze all methods in depth, are described. We use both randomly generated and real data obtained from a timetabling system used in Electronics Telecommunications and Informatics Faculty at Gdansk University of Technology.

• Wydawca: Wydział Elektroniki, Telekomunikacji i Informatyki Politechniki Gdańskiej
• Czasopismo: Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne
• Rocznik: 2003
• Tom: nr 2
• Strony: 457--464
• Opis fizyczny: Bibliogr. 15 poz., 6 tab.

Twórcy

autor

Piwakowski K.

• Katedra Podstaw Informatyki, Politechnika Gdańska

autor

Szyfelbein D.

• Katedra Podstaw Informatyki, Politechnika Gdańska

Bibliografia

• [1] Abramson D., Dang H., Krishnamoorthy M., Simulated annealing cooling schedules for the school timetabling problem, Management Science 37(1) (1991) 98-113.
• [2] Burke E. K., Newall J. P., Weare R.F, A memetic algorithm for university exam timetabling, Practice and Theory of Automated Timetabling, (ed). Burke E. K. and Ross P., LNCS 1153 (1996) 241-250.
• [3] Coddington P., Elmohamed M. A. S., Fox G., A Comparison of Annealing Techniques for Acadernic Course Scheduling, Practice and Theory of Automated Timetabling, (ed). Burke E. K. and Ross P., LNCS 1408 (1998) 92-114.
• [4] Colorni A., Dorigo M., Maniezzo V., A Genetic Algorithm to Solve the Timetable Problem, Computational Optimization and Application Journal.
• [5] Fang H. L., Genetic algorithms in Timetabling and Scheduling, Department of Artificial intelligence, University of Edinburgh, rozprawa doktorska (1994).
• [6] Gotlieb C. C., The construction of class-teacher timetables, In Popplewell C. M. (Ed.), IFIP congress 62, North Holland (1963) 73-77.
• [7] Hertz A., Tabu search for large scale timetabling problems, EJOR 54 (1991) 39-47.
• [8] Johnson D. S., Aragon C. R., McGeoch L.A., Schevon C., Optimization by simulated annealing: an experimental evaluation; part H. graph coloring and number partitioning, Operations Research 39 (1991) 347-406.
• [9] Kubale M., Szyfelbein D., Two methods for solving timetabling problem. Materiały V Krajowej Konferencji Algorytmy Ewolucyjne i Optymalizacja Globalna, Jastrzębia Góra, 30.05-1.06.2001, (2001) 143-243.
• [10] Schaerf A., Tabu Search Techniques for Large High-School Timetabling Problems, AAAI/IAAAI, vol. 1 (1996) 363-368.
• [11] Szyfelbein D., From interval graph coloring to timetabling via genetic algorithms, Proceedings of the 5th Conference Neural Networks and Soft Computing, PNNS (2000), 651-656.
• [12] Szyfelbein D., Metody lokalnego i globalnego przeszukiwania przestrzeni rozwiązań dla problemu układania rozkładów zajęć, rozprawa doktorska WETI PG (w przygotowaniu).
• [13] Tripathy A., School Timetabling - A case in large binary integer linear programming, Management Science 30(12) (1984) 1473-1489.
• [14] Welsh D. J. A., Powell M. B., An upper bound to the chromatic number of a graph and its application to timetabling problem, The Computer Journal 10 (1967) 85-86.
• [15] de Werra D., Hertz A., Using tabu search technique for graph coloring, Computing 39 (1987) 345-351.