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ą:

^ 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:

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

^ 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.