On Multi-Start Algorithms for Optimization of High School Timetables

Article type: Research Article

Authors: Mockus, Jonas | Pupeikienė, Lina

Affiliations: Vilnius University, Institute of Mathematics and Informatics, Akademijos 4, LT-08663 Vilnius, Lithuania. E-mail: jmockus@gmail.com

Abstract: The paper deals with the problem of high-school time-tabling that is important in applications, but hard for solving. The algorithm is presented for timetabling based on Multi-start and Simulated Annealing with parameters adapted using the Bayes approach. The algorithm proposed is compared with other timetabling algorithms using the web-based software. A multi-start algorithm is a simple way to provide the convergence, if the number of uniformly distributed starting points is large. A disadvantage is slow convergence. Therefore, the first aim of this paper is experimental comparisons of the efficiency of different versions of multi-start algorithms in the optimization of timetables. To obtain representative results, the algorithms should be compatible with the Lithuanian high school practice and flexible enough for adaptation to different high schools. The second aim is a web-based implementation of these algorithms in a way convenient for high schools. The web-based software is important for evaluation and comparison of algorithms by independent experts, as well, since the efficiency of algorithms depends on subjective parameters specific to each school, so on-line calculations are needed to obtain representative data. It is useful for scientific cooperation and applications to different schools. In addition, the software for evaluating of real timetables is included to compare with the results of optimization.

Keywords: timetabling, heuristics, Bayesian, Pareto, java, multi-start

Journal: Informatica, vol. 23, no. 3, pp. 405-425, 2012