| Abstract [eng] |
Timetable scheduling is one of the most common tasks that people face every day. Timetable scheduling problem covers a wide range of tasks such as organizing the timetables of educational institutions; traffic flows; register allocation in microprocessors; finding the solution to the Sudoku puzzle, etc. Scheduling theory is closely related to graph theory - timetable scheduling problem is usually converted into a graph coloring approach, which purpose is to find a way of coloring the vertices of a graph such that no two adjacent vertices are colored using same color. Therefore, various graph coloring algorithms were used in this thesis to create timetables. The following algorithms were implemented to address the issue at hand: brute force, greedy, simulated annealing, genetic and Tabo search. These algorithms were investigated by developing three types of different size synthetic graphs: complete, regular and random. The analysis showed that the greedy algorithm has a fast computational speed. Compared to other heuristic methods this algorithm has always proved to be the fastest, but at the same time providing the worst results. Furthermore, algorithms comparison study found that simulated annealing method provides the most accurate and close to optimal solutions. Genetic algorithm analysis showed that it is enough to generate one new generation to find the optimal solution for complete graphs. Moreover, it was determined that crossover probability has no effect on algorithm accuracy, but it affects the execution time of the algorithm: the higher the value of crossover probability is, the longer the calculation time will be. Finally, a web application was implemented that allows educational institutions to schedule timetables by using the heuristic (simulated annealing) algorithm. |
