On Multi-Start Algorithms for Optimization of High School Timetables

摘要

Straipsnis nagrin?ja svarb? ta?iau sud?ting? vidurini? mokykl? tvarkara??i? optimizavimo u?davin?. Pateikiamas ?multi-start" (daugelio pradini? ta?k?) algoritmas naudojant ?modeliuojam? atkaitinim?" (SA), kurio parametrai adaptuojami naudojant Bayes'o po?iūr?. ?is algoritmas lyginamas su kitais tvarkara??i? optimizavimo algoritmais. Siūlomas algoritmas u?tikrina konvergavim? didinant pradini? ta?k? skai?i?, ta?iau konverguoja l?tai. Tod?l pirmasis straipsnio tikslas yra eksperimenti?kai palyginti ?vairius ?io algoritmo variantus. Antrasis tikslas yra jo ?gyvendinimas in-terneto aplinkoje taip, kad būt? patogu naudoti mokyklose. Tai duoda galimyb? nepriklausomiems ekspertams atlikti algoritmo bandymus, patikrinant jo efektyvim? konkre?ioje mokykloje. ?i galimyb? svarbi tod?l, kad algoritmo efektyvumas priklauso nuo mokyklos s?lyg? ir jas apibr??ian?i? parametr?. Optimizavimo programos papildytos programine ?ranga esam? tvarkara??i? ?vertinimui.%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.