Algorytmy i programy automatycznego układania planu zajęć studenckich

Przygotowanie dobrego planu zajęć jest procesem wymagającym czasu oraz dużego doświadczenia osoby podejmującej się tego zadania. Musi ona uwzględnić bardzo dużo różnych zależności jakie zachodzą pomiędzy osobami prowadzającymi zajęcia, grupami studentów, które uczęszczają na te zajęcia oraz pomieszczeniami, w których zajęcia się odbywają. Ze względu na liczne trudności jakie można napotkać podczas przygotowywania grafiku zajęć, pojawiła się potrzeba opracowania programu komputerowego, który mógłby pomóc w tym procesie. Zadaniem takiego programu jest ułożenie na podstawie danych wprowadzonych przez użytkownika jak najbardziej optymalnego harmonogramu zajęć.
Istnieje kilka algorytmów rozwiązywania problemu planu zajęć, których krótkie zestawienie znajduje się w rozdziałach 2 i 3. Rozdział 4 stanowi przegląd programów wspomagających proces układania planu zajęć. W opracowanej aplikacji, która jest opisana w rozdziale 5, został wykorzystany samodzielnie opracowany algorytm bazujący na rozwiązaniach metod heurystycznych. Za takim wyborem przemawiał fakt szybkości działania tych algorytmów oraz wyniki uzyskiwane z ich pomocą.
Aplikacja została przetestowana na przykładzie nieistniejącej szkoły. Jako dane testowe zostały wprowadzone informacje o trzech kierunkach uczęszczających na trzyletnie studia. Na każdym roku dla każdego kierunku istnieją trzy grupy co daje łącznie 27 grup studenckich. Uczęszczają one na 36 różnych zajęć, prowadzonych łącznie przez 16 prowadzący. Zajęcia odbywają się łącznie w 20 pomieszczeniach. Na testowym komputerze wyposażonym w procesor Intel DualCore 1.8 GHz uzyskanie pojedynczego planu zajęło niecałe 10 sekund, natomiast przy uruchomieniu z dwudziestoma pięcioma powtórzeniami program potrzebuje około dwóch minut na uzyskanie wyniku zbliżonego do najbardziej optymalnego.

Preparing good timetable is a very complex and time consuming process. It requires a lot of experience to be done. A lot of dependencies between teachers, study groups and available study rooms should be considered. Because of multiple difficulties which one can meet during the process of preparing timetable, there is a need for a computer program which can help with this task. Goal of this computer program is to prepare the most optimal timetable based on data supplied by user.
There are couple of known algorithms which can be used for this kind of problems, which are reviewed in sections 2 and 3. Section 4 contains reviews of existing programs aiding in timetable preparing process. Section 5 describes algorithm which was used in our program. This solution was based on heuristic methods, which was chosen based on speed and quality of results.
Application was tested with a dataset containing information about three different study specializations on a three-year studies. For each year and specialization there are three groups of students which gives us 27 different study groups. There are 36 different courses and 16 teachers. Classes take place in 20 class rooms. On a test system with Intel DualCore 1.8GHz processor calculations was finished in about 10 seconds. Twenty five repeated test runs was finished in about two minutes providing results close to optimal.