Zastosowanie algorytmów genetycznych do układania planów lekcji na przykładzie Szkoły Podstawowej nr 5 w Olkuszu

• Autorzy: Bogumiła Krzeszowska , Tadeusz Trzaskalik , Ewa Nocoń

Warianty tytułu

The Application of Genetic Algorithms in School Timetabling on the Example of the Elementary School no 5 in Olkusz

• Języki publikacji: PL

Abstrakty

Układanie planu szkolnego jest problemem takiego ustalenia sekwencji spotkań nauczycieli ze studentami w określonym przedziale czasu, aby były spełnione różnego typu ograniczenia. Ręczne ułożenie planu, w zależności od stopnia jego złożoności, może zająć od kilku godzin do kilku dni, a plan taki może być niedoskonały pod wieloma względami. Z tego powodu zwrócono uwagę na możliwość automatyzacji procesu układania planów. Głównymi metodami automatycznego planowania są: metody heurystyczne, metody poszukiwania lokalnego oraz redukcja do kolorowania grafów. Praca ma na celu zastosowanie algorytmów genetycznych do ułożenia planu szkolnego. Pomimo dużej złożoności problemu algorytm genetyczny w niedługim czasie znalazł rozwiązanie dopuszczalne. Jako że jest to metoda przybliżona, otrzymany wynik nie musi być rozwiązaniem optymalnym. (abstrakt oryginalny)

EN

The timetabling problem relies on scheduling a sequence of lectures between teachers and students in a prefixed period of time, satisfying a set of constraints of various types. The manual solution of the timetabling problem usually requires many person-days of work. In addition, the solution obtained may be unsatisfactory in some respect. For the above reason, a considerable attention has been devoted to automated timetabling. The most popular techniques for solving this problem are: simulated annealing, heuristics and graph coloring. In this article, genetic algorithms were used to solve the timetabling problem. Genetic algorithms are a solution technique for optimization problems. They are an adaptive heuristic search algorithm premised on the evolutionary ideas of natural selection and genetic. Genetic algorithms have been applied for school timetabling first in early 90s. The purpose of this paper is to use genetic algorithms for the school timetabling problem. The school timetabling problem is difficult to solve (underlying problem is NP-complete), but genetic algorithm found a solution in short period of time. Because genetic algorithms are the approximate methods, the acquired solution is not necessarily an optimal solution. (original abstract)

Słowa kluczowe

PL

Algorytmy genetyczne; Modele optymalizacyjne; Harmonogram; Szkolnictwo podstawowe

EN

Genetic algorithms; Optimizing models; Schedule; Primary education

• Czasopismo: Prace Naukowe Uniwersytetu Ekonomicznego we Wrocławiu
• Rocznik: 2010
• Numer: nr 108 Współczesne tendencje rozwojowe badań operacyjnych
• Strony: 141--152

Twórcy

autor

Bogumiła Krzeszowska

• Akademia Ekonomiczna im. Karola Adamieckiego w Katowicach

autor

Tadeusz Trzaskalik

• Akademia Ekonomiczna im. Karola Adamieckiego w Katowicach

autor

Ewa Nocoń

• Szkoła Podstawowa nr 5 w Olkuszu

Bibliografia

• Colorni A., Dorigo M., Maniezzo V., A genetic algorithm to solve the timetabling problem, Politechnico di Milano 1992 (dostępne na http://www.asap.cs.nott..ac.uk/ASAP/publications).
• De Werra D., An introduction to timetabling, "European Journal of Operation Research" 1985 vol.19 no 2, s. 151-162.
• De Werra D., The combinatorics of timetablig, "European Journal of Operation Research" 1997 vol. 96.
• Goldberg D., Algorytmy genetyczne i ich zastosowania, WNT, Warszawa 2003.
• Jaszkiewicz A., Metaheurystyki w praktyce, [w:] Algorytmy genetyczne, ewolucyjne i metaheurystyki. Wybrane zagadnienia, red. T. Trzaskalik, Wydawnictwo AE, Katowice 2005.
• Jaszuk M., Zastosowanie algorytmów genetycznych do układania planu zajęć, Państwowa Wyższa Szkoła Zawodowa w Chełmie, Chełm 2003.
• Lalescu L., Timetabling experiments using genetic algorithms, Universitatea din Craiova 2003.
• Norberciak M., Przegląd metod automatycznego planowania - przykład wykorzystania algorytmu genetycznego w rozwiązaniu prostego problemu planowania, Prace Naukowe Wydziałowego Zakładu Informatyki Politechniki Wrocławskiej. Zeszyt Sztuczna Inteligencja nr 1, PW, Wrocław 2002.
• Ross P., Corne D., Comparing genetic algorithms, simulated annealing, and stochastic hilliclimbing on timetabling problem, Evolutionary Computing, AISB Workshop, 1995.
• Schaerf A., A survey of automated timetabling, CWI Amsterdam 1995 (dostępne na: http://cwi.nl/ftp//CWIreports/AP).