Tvarkaraščių optimizavimo uždavinių sprendimas
Ramanauskaitė, Simona | Recenzentas / Rewiewer |
Baigiamajame magistro darbe tiriami ligoninės operacijų tvarkaraščių sudarymo uždaviniai ir jų sprendimo būdai. Vertinami apibrėžtos ir neapibrėžtos operacijų trukmės atvejai. Neapibrėžtasis atvejis modeliuojamas pagal diskrečiuosius-tęstinius scenarijus, o sprendimui priimti naudojamas blogiausiojo atvejo optimizavimo metodas. Abu atvejai modeliuojami kaip mišriojo sveikųjų skaičių tiesinio programavimo (angl. Mixed Integer Linear Programming, MILP) uždaviniai. Pateikiamos kelios deterministinės ir randomizuotos euristikos, paremtos nauju deriniu iš trijų prioritetinių sąrašų. Atliekami kompiuteriniai eksperimentai, rodantys, kad randomizuotų euristikų kokybė yra pakankama naudojimui tais atvejais, kai komercinė MILP uždavinius sprendžianti priemonė negali gauti optimalaus sprendinio dėl didelio atminties sunaudojimo ar nepriimtinos skaičiavimų trukmės.Darbą sudarančios dalys: įvadas, literatūros apžvalga, uždavinių formulavimas, euristikos uždaviniams spręsti, kompiuteriniai eksperimentai, išvados, literatūros sąrašas.Darbo apimtis: 50 puslapių, 15 iliustracijų, 8 lentelės, 61 bibliografinis šaltinis.
The final master's thesis deals with hospital operation scheduling. Two cases of certain and uncertain operation durations are considered. The uncertain case is modeled by discrete-continuous scenarios, and the worst-case optimization approach is used for making the decision. Optimization problems arising in both cases are modeled as Mixed Integer Linear Programming (MILP) problems. Several deterministic and randomized heuristics, based on three priority lists, are presented. Computer experiments are conducted which show that randomized heuristic solutions are efficient enough to be used in the case when a commercial MILP solver cannot solve larger instances to optimality due to memory overuse or unacceptable running time.Structure of the thesis: introduction, literature review, problem formulation, heuristic solutions, computer experiments, conclusions, references.The thesis consists of 50 pages, 15 illustrations, 8 tables, 61 references.