Mokyklos pamokų tvarkaraščio optimizavimo uždavinys

Papildė:  Vitalius Marcinkevičius (papildymai, TvarkaAnalyser)

Atliko:  Dalia Švirmickienė (Modelis ir JAVA)
            Aurelija Zakšauskaitė (Duomenys ir modelis)

Priėmė: prof. J.Mockus

Kaunas, 1999

Turinys

1. Užduotis
2. Užduoties analizė
3. Teorinė dalis
4. Duomenų struktūra
5. Tvarkaraščio perstatymo ir įvertinimo algoritmas
6. Instrukcija vartotojui
7. Optimizuojamo tvarkaraščio peržiūra
8. Rezultatai
9. Išvados
10. Literatūra

^ Užduotis

Sudaryti programą, kuri nuskaito iš duomenų failo jau sudarytą vidurinės mokyklos penktų - dvyliktų klasių vienos savaitės pamokų tvarkarastį ir jį optimizuoja (optimizavimas suvedamas į mokytojų langų skaičiaus minimizavimą).

^ Užduoties analizė

Mokyklos tvarkaraščio sudarymas - tai gerai žinomas bendresnės tvarkaraščio problemos pavyzdys. Pagrindinis uždavinio tikslas - optimizuoti tvarkaraštį taip, kad mokytojai turėtų kuo mažiau laukimo valandų, t.y. langų. Pamokų tvarkaraščio uždavinys išsiskiria tuo, kad jam egzistuoja apribojimai, t.y., pamokos tvarkaraštyje išdėstomos pagal tam tikras taisykles:

1. Mokiniai negali turėti langų;
2. Duotu momentu mokytojas gali vesti tik vieną pamoką;
3. Duotu momentu mokinys gali dalyvauti tik vienoje pamokoje;
4. Kai kurios pamokos gali būti sudvejintos (pvz.: dvi lietuvių klb. pamokos iš eilės);
5. Egzistuoja vienos dienos maksimalus pamokų skaičius = 7.

Optimizavimas pradedamas nuo jau sudaryto mokyklos tvarkaraščio.

^ Teorinė dalis

Tvarkaraščio uždavinys yra priskiriamas NP-complete uždavinių klasei. Norint rasti tikslų sprendinį, naudojama formulė T=C*2^m. Pilnas perrinkimas pareikalautų didelių skaičiavimo ir laiko sąnaudų. Kadangi galimų sprendimo variantų yra labai daug, naudojamos tam tikros taisyklės, vadinamos heuristikomis. Naudojant heuristikas peržiūrima tik tam tikra leistinų sprendinių dalis. Iš jų išrenkamas geriausias sprendinys. Pastarasis yra pateikiamas kaip optimaliausias sprendinys.

Tikslas, sprendžiant pamokų tvarkaraščio uždavinį, minimizuoti pamokų tvarkaraščio įvertinimo funkciją. Sprendžiant pamokų tvarkaraščio optimizavimo uždavinį, naudojome šias heuristikas:

1. Monte Carlo metodą: 1/N. Iš galimų sprendinių aibės parenkamas atsitiktinis sprendinys;
2. Kvadratinę priklausomybę: h(n)^2 / sum(h(j))^2;
3. Gryną heuristiką: 1, jei h(n)=min(h(j)); 0 kitu atveju.

^ Duomenų struktūra

Mokyklos savaitės tvarkaraštis saugomas masyve string Mokytojai[M][3+5*7], M=64 - mokytojų skaičius. Čia Mokytojai[i], i=1..M - tai informacija apie i-ąjį mokytoją:

• Mokytojai[i][1] - atitinkamai i-ojo mokytojo pavardė;
• Mokytojai[i][2] - atitinkamai i-ojo mokytojo dėstomo dalyko pavadinimas;
• Mokytojai[i][3] - atitinkamai i-ojo mokytojo kabineto koduotas simbolis, jeigu mokytojo dėstomam dalykui nereikalingas specialaus kabinetas, šioje vietoje rašomas "0".
• Mokytojai [i][j], j=4..38 - atitinkamai i-ojo mokytojo pamokų tvarkaraštis savaitei (savaites diena, pamokos numeris ir klasė, pvz.: P19c - pirmadienis, pirma pamoka 9c kalsei, mokytojo langai žymimi X simboliu, jeigu mokytojas tą dieną neturi pirmųjų ar paskutiniųjų pamokų, tai tokios pamokos nelaikomos langais ir žymimos Q simboliu).
  

^ Tvarkaraščio perstatymo ir įvertinimo algoritmas

1. nuskaityti duomenis Mokytojai[M][38] iš failo
2. suskaičiuoti langų skaičių pradiniame tvarkaraštyje
3. nustatyti pradinį iteracijos numerį  it = 0
4. nustatyti iteracijos numerį  it = it+1, it < K
5. nustatyti pradinį mokytojo numerį  i = -1
6. nustatyti mokytojo numerį  i = i+1
7. jei  i > M-1 eiti į 4 punktą
8. suskaičiuoti langų skaičių einamąjame tvarkaraštyje
9. palyginti langų skaičių einamąjame tvarkaraštyje su langų skaičiumi ankstesniame tvarkaraštyje
10. jei einamasis langų skaičius mažesnis, tai pakeisti ankstesnį tvarkaraštį einamuoju
11. sugeneruoti atsitiktinį skaičių  ksi  tolygiai pasiskirsčiuosį intervale 0..1.
12. jei ksi < x, eiti į 6 punktą
13. išrinkti i-tojo mokytojo pirmą langą
14. išrinkti i-tojo mokytojo paskutinę pamoką  k-tą (k=1,...,5) dieną, jei tokia pamoka yra
15. perkelti šią pamoką į lango vietą
16. patikrinti šio pakeitimo galimumą (turi būti viena pamoka vienu metu) ir eiti į 8 punktą, jei pakeitimas leistinas
17. jei k<5, išrinkti paskutinę k+1 dienos pamoką  ir eiti į 15 punktą
18. perkelti pasirinktą pamoką į paskutinę pamoką k-tą (k=1,...,5) dieną, jei tokia pamoka yra
19. patikrinti šio pakeitimo galimumą (turi būti viena pamoka vienu metu) ir eiti į 8 punktą, jei pakeitimas leistinas
20. jei k<5, išrinkti paskutinę k+1 dienos pamoką  ir eiti į 15 punktą
21. atstatyti ankstesnį mokytojo langą (kai dar nebuvo prieštaravimų)  ir eiti į 8 punktą

^ Instrukcija vartotojui

Šio uždavinio vykdomoji programa yra JAVA applet'as. Applet'o vykdomui reikalinga naršyklė palaikanti JAVA (Netscape Communicator v. 4.06, Internet Explorer 4.0 ar aukštesnės versijos naršyklės). Applet'as paleidžiamas nurodant atitinkama *.html failą.
Pastaba: programą galima paleisti ir naudojant java interpretatorių.

1. Pasirinkite optimizavimo metodą ir nurodykite jo parametrus.
2. Pasirinkti vykdymui užduotį. Tvarkaraščio optimizavimo atveju užduotis vadinasi Tvarka. Pasirinkus užduotį tvarka, atsidaro laukeliai, kuriuose galima nurodyti:
   - pradinių duomenų failą, t.y. failą, kuriame surašytas pradinis tvarkaraštis,
   - iteracijų skaičių K (siūloma: K=2),
   - tikimybės minimalią, maksimalią ir pradinę inicijuojamą reikšmę. Siūlomos reikšmės yra: Min=0.0, Max=1.0 ir Default=0.5.
3. Pradėkite optimizavimą. Tam nuspauskite mygtuką "Run". (optimizavimą galima bet kada sustabdyti, nuspaudus mygtuką "Stop" arba padaryti pauzę skaičiavimuose - mygtukas "Pause").
   Skaičiavimams pasibaigus pateikiami sekantys rezultatai: iteracijų, per kurias metodas sukonvergavo į minimumą, skaičius (galima taip pat pasižiūrėti grafiką), minimali gauta F(x) reikšmė ir gautos atitinkamų taisyklių parinkimo optimizavimo metu prpoprcijos (galima pasižiūrėti jų grafinius vaizdus).

^ Optimizuojamo tvarkaraščio peržiūra

Norint stebėti tvarkaraščio minimizavimo eigą reikia iš "Run analysis" dėžutės pasirinkti "TvarkaAnalyser".
Pasirodo TvarkaAnalyser langas.

Lango viršuje išvedama:
-> Last - paskutinio rezultato iteracija ir reikšmė;
-> Progress - paskutinio pažangaus rezultato iteracija ir reikšmė;
-> Displayed - šiuo metu lange atvaizduojamo rezultato iteracija ir reikšmė.

Žemiau:
->Freeze - užšaldyti lange atvaizduojamą rezultatą (pagal nutylėjimą jei skaičiuojant gaunamas naujas pažangus rezultatas, tai jis automatiškai atvaizduojamas lange);
->Save - išsaugoti tvarkaraštį faile nurodytame įvedimo laukelyje;
->File - išvedamas dialogas, kuriame galite pasirinkti failą, kuriame bus galima išsaugoti tvarkaraštį (Pastaba: dialogas gali neatsirasti, jei jūsų saugumo parametrai neleidžia to padaryti).

Lango apačioje mygtukai:
->Count - suskaičiuoja langų skaičių šiuo metu atvaizduojamame tvarkaraštyje (t.y. simbolių X skaičių tekste);
->Refresh - atnaujina vaizdą;
->Help - išveda pagalbos langą;
->About - išveda informaciją apie sprendžiamą uždavinį.

^ Rezultatai

Optimizuojant pasirinkome Mig1 metodą, iteracijų skaičius K=2, pradinė tikimybė : 0.5.
Pradinis langų skaičius buvo 129.
Vienu atveju buvo pasirinkta 10 iteracijų, kitu - 50.

Pirmu atveju, kai iteracijų skaičius 10,  gauti tokie rezultatai:

• Minimizuojamos funkcijos reikšmė - 17 (gauta 9-oje iteracijoje).

Kai iteracijų skaičius - 50, gauti rezultatai:

• Minimizuojamos funkcijos reikšmė - 14 (gauta 26-oje iteracijoje).

^ Išvados

Šis metodas naudoja atsitiktinumą langų šalinime. Šiame algoritme yra atsitiktinumo faktorius, renkantis tvarkaraščio eilutę ir  konkrečią taisyklę minimumo radimui. Šis algoritmas nepažeidžia pagrindinių tvarkaraščio sudarymo taisyklių, tačiau jo perstatinėjimas nėra pritaikytas kitkam kaip tik mokytojų langų šalinimui. Uždavinys yra konkrečiai taikomas tik mokytojų langų minimizavimui, neatsižvelgiant į mokytojų užimtumą bei galimus kitokius faktorius. Norint tvarkaraščio minimizavimo programą taikyti praktikoje, reikėtų įvertinti daugiau kriterijų: mokytojų užimtumą, pamokų sudėtingumo lygį ir pan.

^ Literatūra

[1] D. Švirmickienė ir A. Zakšauskaitė. Mokyklos pamokų tvarkaraščio uždavinys. Techninė ataskaita, Vytauto Didžiojo Universitetas, Informatikos fakultetas, Lietuva, Kaunas, 1998.
[2] J. Mockus, W. Eddy, A. Mockus, L. Mockus, and G. Reklaitis. Bayesian Heuristic Approach to Discrete and Global Optimization. Kluwer Academic Publishers, Dordrecht-London-Boston, 1997.