Object Oriented Approach to Timetable Problem Solving Using a Genetic Algorithm

Genetički algoritmi danas predstavljaju moćnu adaptivnu metodu rješavanja mnogih kombinatornih problema i problema optimizacije. Od posebnog je interesa rješavanje složenih, NP teških kombinatornih problema, a jedan od takvih problema je i izrada školskog rasporeda sati. Problem se u osnovi sastoji od smještanja svih (nastavnim planom određenih) predavanja u unaprijed definirani skup vremenskih termina (sati) uz poštivanje određenih ograničenja. U ovom radu načinjen je genetički algoritam i računalni program za izradu školskog rasporeda sati koji uzima u obzir sve specifičnosti hrvatskog školstva. Algoritam je verificiran na realnom slučaju. Za probne podatke uzeta je gimnazija u Bjelovaru s nastavnim programom za 1999/2000. školsku godinu. Cilj je bio pronaći alternativu napornoj ručnoj izradi rasporeda i ocijeniti primjenjivost, učinkovitost i ograničenja genetičkog algoritma na ovoj problematici u realnim uvjetima. Provedeni su pokusi s različitim varijantama genetičke jezgre algoritma, a isprobana je i hibridizacija s nekoliko tehnika lokalne potrage i simulacijom klasičnih metoda. Algoritam je implementiran u objektnom programskom jeziku Smalltalk u kombinaciji s DB2 bazom podataka u okviru razvojnog alata IBM VisualAge for Smalltalk. Rad je podijeljen u nekoliko cjelina. Na početku je ukratko predstavljena povijest genetičkih algoritama, osnovni pojmovi, operatori, teoretska podloga i usporedba s ostalim tehnikama optimizacije. Sljedeće poglavlje općenito opisuje problematiku rasporeda sati uz matematički model i iznosi dosadašnje rezultate u primjeni genetičkih algoritama u rješavanju problematike. Četvrto poglavlje detaljno opisuje problem školskog rasporeda u Hrvatskoj sa svim specifičnostima, oslanjajući se na primjer bjelovarske gimnazije. U petom poglavlju opisan je korišteni algoritam, njegov dizajn i implementacija na računalu. U sljedećem poglavlju prikazani su dobiveni rezultati i performanse algoritma. Sedmo poglavlje donosi ocjenu rezultata i zaključke.Today, genetic algorithms represent a powerful adaptive method in solving many optimization and combinatorial problems. Solving complex, NP hard combinatorial and optimization problems is of particular interest and school timetable problem is one of that kind. The essence of the problem is placing all the lectures (determined by a curriculum) in a set of predefined timeslots without breaking certain constraints at the same time. A genetic algorithm and a computer program for creating a school timetable were developed in this thesis. All specific details of Croatian school system were taken into account and the solution was tested on a real world problem. The curriculum for school year 1999/2000 of Bjelovar grammar school was taken as a test set of data. The goal was to find an alternative solution to hard manual process of creating a school timetable and to estimate usefulness, performance and limitations of genetic algorithms when applied to real timetable problems. Different variations of genetic kernel of algorithm were tested. Hybridization with a few local search techniques and simulated manual methods were also tried. Algorithm was implemented with object oriented programming language Smalltalk and DB2 database within IBM VisualAge for Smalltalk developing environment. The thesis is organized as follows. First of all, a short history of genetic algorithms, basic terms, operators, theoretical background and comparison with other optimization techniques are presented. The next chapter describes the timetable problem in general using a mathematical model. It outlines current achievements in applying genetic algorithms in solving timetable problems. The fourth chapter brings detailed description of the school timetable problem in Croatia with reference to Bjelovar grammar school example. Design and computer implementation of the algorithm are described in the fifth chapter. Obtained results and algorithm performance are presented in the next chapter. The seventh chapter brings the evaluation of obtained results and conclusions