SCHEDULE FOR HIGH SCHOOL PROFILED CLASSES This program is produced for all high schools who have problems with making schedules. This program will help you to make and optimize your schedule as goog as it can be. ALL DESCRIPTIONS ABOUT ALGORITH AND FUNCTIONNING ONLY IN LITHUANIAN. -------------------------------------------------------------------- PROFILIUOTU KLASIU TVARKARASCIO SUDARYMO PROGRAMA Programa sukurta naudojant Java kalba. Galimi pasirinkimai matomi priklausomai nuo mygtuku busenos (pilkas neaktyvus). Veiksmai: 1. Duomenu failo ".txt" formate persiuntimas i serveri. Sis persiuntimas realizuotas CGI interfeiso pagalba. Failo pasirinkimas atliekamas paspaudus mygtuka "Browse" ir nurodzius norima faila. Tada turi buti paspaustas mygtukas "O.K." ir failas nusiunciamas i serveri. 2. Duomenu nuskaitymas is atsiusto failo. Atlikti si veiksma galima tada kai failas persiustas paspaudus mygtuka "Read data". Tada is serveryje esancio vartotojo duomenu failo programa ji nuskaito. Pasidaro aktyvus pasirinkimai "Restrictions"(apribojimai) ir "Penalty points"(baudos taskai). 3. "Restrictions" (apribojimai) - si skiltis igalina vartotoja pasirinkti norimus apribojimus i kuriuos atsizvelgs programa darydama tvarkarasti. Galimi tokie apribojimai kaip: * "Two continuous lessons" - dvi besitesencios pamokos. Tai reiskia, jog pradiniame tvarkarastyje vartotojo pazymetos pamokos bus sudetos dvi is eiles, viena karta savaiteje. * "Teachers" - pasirinkimas kuriame nurodomi mokytojai ir savaites dienos kada jie turi isseigines. * "Number of lessons" - pasirenkamas maksimalus pamoku skaicius per diena. 4. "Penalty points" (baudos taskai) - siame lange vartotojas turi galimybe nurodyti baudos taskus intervale nuo 0 iki 10 pateiktiems punktams. Tai yra pagal prioriteta vartotojas skiria daugiau baudos tasku pavyzdziui mokiniu langams negu mokytoju langams ir t.t... Pagal nutilejima siulomi baudos taskai lygus 3. Sudarius tvarkarasti ir ji optimizuojant vartotojas gali matyti kiek baudos tasku "surinko" vienas ar kitas tvarkarascio variantas. 5. "Starting schedule" (pradinis tvarkarastis) - sudedamas pradinis tvarkarastis ir isvedamas i lauka "First version". 6. Atlikus 5 punkta tampa aktyvus "Optimization" mygtukas, kuri paspaudus atsiranda langas su dviem pasirinkimais: "Number of iterations" (iteraciju skaicius optimizavimo metu) ir "Probability" - tikimybe su kuria tam tikras dalykas bus keiciamas vietomis. Juos pasirinkus arba palikus siulomus vykdomas "Start" mygtukas - optimizavimo pradzia. 7. Optimizavimui pabaigus darba turetu buti vykdomas "Last schedule" pasirinkimas. Atidaromas langas su mokyklos, visu mokiniu bei mokytoju tvarkarasciais. Si langa galima uzsaugoti savo kompiuteryje. 8. "Help" - pateikti pagrindiniai reikalavimai. 9. "About" - programos darbo aprasymas. -*- Pradinio tvarkarascio sudejimo aprasymas. Nuskaitomas vartotojo duomenu failas i masyva. Atsizvelgiant i nustatytus apribojimus, jei nustatytos tam tikros besitesiancios pamokos jos sudedamos i tvarkarasti pirmos. Jos dedamos pirma, antra i pirmadieni, o likusios ismetomos i kitas dienas. Toliau likusiu pamoku sudejimas vykdomas sekanciai: pasirenkama diena ir pamoka tikrinama ar pamoka gali vykti (ivertinama fiziniai apribojimai) sudedamos visos pamokos kurios gali vykti kartu. Taip pat atliekamas patikrinamas ar makytojas ta diena neturi isseigines (jei nustatyta apribojimuose). Viena pamoka vyksta viena karta per diena jei kitaip nenurodyta apribojimuose. Reikia pastebeti jog formuojant pradini tvarkarasti nera kreipiamas demesys i mokiniu ar mokytoju langu skaiciu o stengiamasi sutalpinti visus dalykus i bendra tvarkarasti. Pradiniu metu tai bandoma sutalpinti i nurodyta maksimalu pamoku skaiciu nurodyta apribojimu punkte "Number of lessons" (pagal nutylejima 9 pamokos per diena), jei tai padaryti nepavyksta tada atliekamas masyvo ismaisymas (eiluciu sukeitimas vietomis) ir vel formuojamas tvarkarastis. Maksimaliai ismaisymas vykdomas 100 kartu taciau nutraukiamas jei visos pamokos tilpo. Jei atlikus ismaisyma 100 kartu visos pamokos netilpo jos dedamos prie nurodyto maksimalaus pamoku skaiciaus pridejus 1. Tokiu atveju uz viena pamoka pridedamas maksimalus baudos tasku kiekis 10. -*- Tvarkarascio optimizavimo aprasymas. Optimizavimas orientuotas i mokiniu langu mazinima. Optimizavimo algoritmas: 1. Iteracijos numeris nustatomas i 1. 2. Keliaujama per mokiniu sarasa. 3. Parenkamas atsitiktinis skaicius x. 4. Jei x didesnis uz musu pasirikta tikimybe (probability), tai atlikinejami pakeitimai mokinio tvarkarastyje, jei x mazenis uz tikimybe, einama prie kito mokinio. 5. Ieskomi parikto mokinio langai. Kai langas surastas, ieskomos kiekvienos dienos pirmos ir paskutines pamokos, kurios gali buti iterptos vietoje lango. Jei tos pacios dienos tinka ir pirma, ir paskutine, atsitiktinio skaiciaus pagalba parenkama viena is ju. 6. Vietoje lango iterpiama rasta pamoka, o vietoje rastos pamokos padaroma laisva vieta. 7. Kai perziurimi visi mokinio langai keliaujama i 3 punkta. 8. Kai perziurimi visi mokiniai, padidinamas iteracijos numeris ir einama i 2 punkta. 9. Kai atliktos visos iteracijos, pateikiamas geriausias tvarkarascio variantas. -*- Baudos tasku skaiciavimas. Baudos taskai apskaiciuojami ivertinant tokius 5 faktorius: langus tarp pamoku vaikams, langus tarp pamoku mokytojams, apribojimu del dvieju besitesenciu pamoku neigyvendinima, apribojimu del mokytoju laisvu dienu neigyvendinima ir per diena vykstanciu pamoku skaicius padidinimas. -*- Geriausio varianto isrinkimas. Ivykdzius visus punktus, geriausias variantas, laikomas tas, kuris turi maziausia skaiciu bendrai apskaiciuotu baudos tasku, o ne tas, kuris atitinka visus apribojimus. Tai daroma todel, kad pavyzdziui kokio nors apribojimo neivykdymas gali labai zenkliai sumazinti mokiniu langu skaiciu. Authors of this program are master of science students of Kaunas University of Technology: Ula Leonaviciute, Mindaugas Kuprys, Marius Cerniauskas. ------ Kaunas University of Technology ------ ------ Kaunas, 2001 ------