Comparative study of profiled school scheduling programs in Lithuania

LTSpręsti optimalaus mokyklos tvarkaraščio sudarymo problemą yra labai svarbu mokyklos darbo efektyvumo didinimui. Užduotis yra sudaryti patogiausią tvarkaraštį iš visų galimų. Visi nepatogumai yra vertinami baudos taškais. Šio tyrimo tikslas yra išanalizuoti optimizavimo atžvilgiu keletą Lietuvoje paplitusių komercinių mokyklos tvarkaraščio sudarymo programų bei palyginti jas su šiuo metu veikiančia Matematikos ir informatikos instituto (MII) Optimizavimo skyriaus programa. Mūsų tyrimo objektas yra šių programų optimizavimo algoritmų kokybės tyrimas ir palyginimas. Vienas uždavinių yra nustatyti esamas rinkoje mokyklos tvarkaraščio sudarymo programas, kurios tiktų Lietuvos profiliuotoms mokykloms. Kitas uždavinys yra MIMOSA, aSc Timetables ir MII tvarkaraščio sudarymo programų tyrimas ir eksperimentinis palyginimas optimizavimo atžvilgiu. Programų tyrimą vykdėme trimis etapais: 1) tvarkaraštis sudaromas be apribojimų, t.y. leidžiama sudėti iš eilės du vienodus dalykus, maksimalus pamokų skaičius per dieną – 10, mokytojai dirba be laisvų dienų; 2) maksimalus pamokų skaičius per dieną sumažinamas iki 9; 3) realios Vilniaus vidurinės mokyklos tvarkaraščio sudarymas ir optimizavimas.

ENSolution of the problem of optimal school scheduling is very important to make the work of comprehensive schools more effective. Here the sequence of teaching subjects, regarded as tools, can be changed. One needs to reduce the sum of gaps (“empty” hours) in the teacher schedules. There should be no gaps for students. Different classes are considered as different tasks. The classrooms, including the computer and physics rooms and studies, are the limited resources. The most difficult example is scheduling of profiled school. Here eleventh and twelfth grade students are choosing several subjects from the list of available ones. This means that each student works by his own schedule. We search for the most convenient feasible schedule. The inconveniences are evaluated by penalty points. The purpose of the study is to analyze several commercial scheduling programs which are prevalent in Lithuania at the moment and to compare them with existing timetable version of Optimization Department of Lithuanian Institute of Mathematics and Informatics (IMI) from optimal scheduling point of view. Therefore our research object is to study and compare the quality of optimization algorithms of these programs. One of the tasks is to identify existing commercial scheduling programs which might be right for Lithuanian profiled comprehensive schools. Another task is to perform the tentative comparison of scheduling programs MIMOSA, aSc Timetables and IMI timetable version from the point of view of quality of optimal scheduling. We used three stages for study of these programs: 1) scheduling without any confines – it’s allowable to consecutively add two equal subjects, the ultimate number of lessons per day is 10 and teachers are working without day offs; 2) reduction of ultimate number of lessons to 9 lessons per day; 3) optimal scheduling of real Vilnius secondary school.