Optimizavimo metodų tyrimas ir taikymas profiliuotų mokyklų tvarkaraščių sudarymo uždaviniuose

Abstract

Profiliuotos mokyklos tvarkaraščio kūrimas yra aktualus uždavinys tiek Lietuvoje, tiek kitose šalyse. Nėra žinoma polinominių būdų šiai problemai spręsti. Pagrindinis šios daktaro disertacijos objektas yra ištirti euristinius metodus, skirtus profiliuotos mokyklos tvarkaraščio optimizavimui. Tvarkaraščio formavimo kriterijai, kurie yra reikalingi realiame gyvenime, nustatomi vektorinio optimizavimo metodais bei realizuojami nuo operacinės sistemos nepriklausoma programine įranga. Eksperimentinių tyrimų uždavinys – surasti tokius euristinių metodų parametrus, kurie minimizuotų numatytą nuokrypį. Disertacijoje aprašomi keturi optimizavimo metodai: lokalus determinuotas (LD), lokalus atsitiktinis (LA), atkaitinimo modeliavimo (AM) ir AM parametrų optimizavimas naudojant Bayes (BA) metodą. Kombinuotas AM ir Bayes metodas duoda geriausius rezultatus. Pirmajame apžvelgiama su mokyklos tvarkaraščių formavimu susijusi literatūra. Analizuojami tinkamiausi optimizavimo metodų darbo aspektai. Analizuojamos populiariausios programavimo kalbos, tinkančios kurti mokyklų tvarkaraščių optimizavimo programą. Antrajame skyriuje formuluojamas profiliuotų mokyklų tvarkaraščio kūrimo matematinis modelis. Analizuojami profiliuotose mokyklose naudojami euristiniai parametrai. Atlikti populiarių tvarkaraščių programų vertinimai ir analizės. Įvardijami šių programų trūkumai. Trečiajame skyriuje, remiantis 2 skyriaus analize ir išvadomis, pateiktas profiliuotos mokyklos lanksčios tvarkaraščio optimizavimo programos projektavimas. Pateiktas pradinio duomenų failo projektavimas, kuris yra informatyvus ir įvertina daugelį mokyklos nuostatuose apibrėžtų euristinių parametrų. Aptariami suformuluoti siūlymai programos plėtojimui. Disertaciją sudaro trys skyriai, bendrosios išvados ir rekomendacijos, literatūros sąrašas ir autoriaus publikacijų sąrašas. Disertaciją sudaro 124 puslapiai, 53 iliustracijos ir 10 lentelių. Disertacijos temai skaityti pranešimai 5 konferencijose. Paskelbti 2 straipsniai leidiniuose, įtrauktuose į Mokslinės informacijos instituto sąrašą.

The problem of profiled school scheduling is important for Lithuanian schools and for similar schools in many other countries. No polynomial time methods are known for this problem. The objective of this PhD thesis is to investigate heuristic methods for optimization of profiled school schedules. The convenience of application in real-life situations is provided by the vector optimization approach using platform-independent software implementation. The task of experimental investigation is to select such parameters of heuristic methods that minimize expected deviation from the optimum. Four optimization methods were regarded: Local Deterministic (LD), Local Randomized (LR), Simulated Annealing (SA), and SA with parameters optimized using the Bayesian approach (BA). The composite method of AM and BA provided the best results. In Chapter 1 of the dissertation, various aspects of work of optimization methods as well as popular program languages suitable for school schedule optimization are analyzed. Literature about school scheduling is analysed. In Chapter 2, conclusions are drawn how the optimization of heuristic parameters influences the speed and accuracy of finding the optimal solution. A technical rating analysis of popular schedule programs is made and technical disadvantages are listed. Criteria for evaluating the quality of results are proposed that include heuristic parameters in search of optimal schedules. Recommendations are states how to assess the choice and optimization of heuristic parameters and methods of the optimization program used. In Chapter 3, software meant for school schedule optimization in Lithuanian schools program is discussed. Creation of initial data file is described. Proposals for a further development of the program are considered as well. There are three chapters, general conclusions and recommendations, the list of the references, and the list of publications. The thesis contains 124 pages, 53 figures and 10 tables. The results were presented in five conferences and were published in 2 papers in referred scientific journals.