Optimization algorithms in school scheduling programs: study, analysis and results

Abstract

To create good and optimal school schedule is very important and practical task. Currently in Lithuania schools are using two programs for making the school schedule at the moment. But none of these programs is very effective. Optimization Department of Lithuanian Institute of Mathematics and Informatics (IMI) has created "School schedule optimization program". It has three optimization algorithms for making best school schedule. A user can choose not only few optimization options and get few optimal schedules, but some subjective and objectives parameters. The making of initial data file is advanced in this program. XML format is used for creating initial data file and getting all optimal results files. The purpose of this study is to analyze used optimization algorithms used in "School schedule optimization program" and to compare results with two most popular commercial school scheduling programs in Lithuania.

Labai svarbus, sunkus ir svarbus uždavinys profiliuotoje mokykloje yra mokyklos tvarkaraščio kūrimas ir optimizavimas. Šiuo metu yra sukurta daugelis tvarkaraščių sudarymo programų, tačiau nei viena iš jų nėra efektyvi. Jos teturi menkus optimizavimo algoritmus. Kuriama programa turi keletą optimizavimo algoritmų. Juos panaudodamas vartotojas turės galimybę gauti ne vieną, bet keletą optimalių tvarkaraščių variantų. Programoje igyvendintas labai patogus pradinių duomenų failo parengimas XML formatu. Šį formatą puikiausia formuoja MS Excel programa. Vartotojui nebereikės suvedinėti ir grupuoti mokinių rankiniu būdu. Atskiruose MS Excel lapuose įvedęs mokytojus ir kiekvienos klasės mokinių pageidavimus, vartotojas naudodamasis šia programa automatiškai gaus suformuotus mokyklos tvarkaraščius. Programoje buvo įvertinti mokyklos parametrai, o tai leidžia programą pritaikyti mokykloms su skirtingomis vidaus taisyklėmis. Programoje yra įdiegti optimizavimo algoritmai, kurie leis rasti optimalų tvarkaraštį pagal vartotojo pasirinkimus. Tvarkaraščiai bus pateikiami mokyklai mokiniams ir mokytojams atskirai. Visi jie pateikiami tiek ekrane (programos darbo metu), tiek “zip” archyve (jį galima parsisiųsti programai baigus optimizavimo procesą). Kuriant programą buvo naudojamos naujausios JAVA technologijos. Programa lengvai valdoma. Joje pateikiama pagalba kiekviename žingsnyje.