Favorizovanje predavaca je bio jedini skriveni uslov. Sto se tice ostalih uslova navescu neke kojih se secam jer sam zadnji raspored uradio 2003 a u medjuvremenu mi je CD sa kopijom source koda crk'o
1. Pedagoski uslov: postavi teze predmete na pocetak radnog dana a lakse na kraj - labav uslov
2. Ako je fond casova za dati predmet manji od 4 algoritam je trebao da rasporedi po minimum jedan dan pauze izmedju predavanja. Npr. ako je fond bio 3 casova nedeljeno algoritam se trudio da predavanja iz tog predmeta budu u Pon, Sre i Pet a ako je 2 onda u Uto i Cet. - labav uslov
3. Jedan predavac ne sme da predaje u 2 i vise odeljenja istovremeno. Ovaj uslov je imao izuzetak jer su predavaci stranih jezika mogli da predaju u dva odeljenja istovremeno jer su se odeljenja delila na grupe koje su ucile engleski, nemacki ili francuski. - strog uslov
4. i 5. Zelje predavaca da ne predaju odredjenim danima ili odredjenim casovima su bile podeljene na stroge i labave. Ako je predavac predavao u dve ili vise skola bilo je moguce zabraniti da taj predavac u skoli predaje npr. sredom i petkom jer je tim danima predavao u drugoj skoli. Ovo je bio strog uslov ali je postojala mogucnost da se taj uslov za pojedine predavace definise i kao labav jer je recimo predavac bio putnik pa je izrazio zelju da ne predaje prve casove. U tom slucaju se algoritam trudio da te zelje ispuni kad god je to bilo moguce.
6. Odeljenje ne sme da iz istog predmeta ima vise od 1 casa dnevno sem ako nije u pitanju blok nastava - strog uslov.
7. Odeljenje ne sme da ima manje od unapred definisanog minimalnog broja casova dnevno. Na primer nijedno odeljenje nije smelo da ima manje od 4 casa dnevno da se ne bi desila situacija da ucenici u ponedeljak imaju 3 casa a u petak 7 casova. Ovo je bio strog uslov.
8. Predavaci ne bi trebali da imaju vise od maksimalnog datog broja pauza nedeljeno. Na primer maksimalni broj pauza nedeljno je obicno bio 2 ali je taj broj bio promenjljiv. Na ovaj nacin su pojedini predavaci mogli da se favorizuju. Uslov je bio labav.
9. Predavaci ne bi trebali da imaju manje od minimalnog datog broja pauza nedeljeno. Na primer minimalni broj pauza nedeljno je obicno bio 0 tj. algoritam se trudio da izbaci pauze predavacima ali je taj broj bio promenjljiv jer su direktori nekad trazili da svi predavaci iz nekog predmeta imaju bar po jednu pauzu nedeljno kako ne bi bilo nezadovoljnih predavaca. Uslov je bio labav.
10. Podela sale za fizicko: algoritam se trudio da u salu za fizicko ne stavi vise od maksimalnog datog broja odeljenja koja mogu da imaju fizicko istovremeno i to je obicno bilo 2 odeljenja. Takodje je trebalo izbegavati da ucenici recimo osmog razreda imaju fizicko sa ucenicima petog razreda tj. bilo je pozeljno da ako vec mora da bude vise od jednog odeljenja u sali, to budu sestaci sa osmacima i petaci sa sedmacima. Ovaj uslov je bio labav.
11. Predavac u jednom danu ne sme da ima vise pauza od maksimalnog datog broja pauza dnevno i to je obicno bila jedna pauza dnevno - strog uslov.
12. Rad po smenama: ako je predavac predavao odeljenjima koja su isla u razlicite smene onda je algoritam trebao da se trudi da tog predavaca postavi na kraj prve i pocetak druge smene kako bi predavac imao sto manju pauzu a u suprotnom ta pauza je trebala da bude sto veca jer je predavac u vreme pauze mogao da ode kuci i da se kasnije vrati za predavanje u drugoj smeni - labav uslov.
13. Predavac u jednom danu ne sme da drzi predavanja u dve smene. Ovo bio strog uslov ali manje strog od recimo 3. uslova jer je ponekad bilo nemoguce da ovaj uslov bude 100% ispunjen. Na primer, nastavnici matematike su u odeljenjima drzali predavanja po 5 casova nedeljno tako da ako je nastavnik predavao odeljenjima koja su isla u razlicite smene on je jednostavno morao da radi po smenama. Inace ovaj problem sam, naravno uvek uz dozvolu direktora, resavao tako sto sam takvim predavacima dozvoljavao da odeljenjima drze dvocase. Npr. ako je predavac A imao fond od pet casova nedljeno u odeljenju O1 i pet casova nedeljeno u odeljenju O2 a odeljenja O1 i O2 su bila u razlicitim smenama, onda je predavac A imao po 2 dvocasa u odeljenjima O1 i O2. Predavac je tada imao casove Pon, Sre i Pet u odeljenju O1 a Uto, Cet i Pet u odeljenju O2. Ocigledno je da je u ovom slucaju bilo nemoguce izbeci da predavac bar jednom nedeljeno radi u obe smene (u ovom primeru je to bio petak).
14. Odeljenje ne sme da ima ni jednu pauzu u toku radnog dana - strog uslov.
15. Blok nastava: odeljenje moze da gubi nastavu npr. sredom jer sredom imaju blok nastavu - strog uslov.
Ovo bi bili svi vazni uslovi. Ispunjavanjem ovih uslova algoritam je davao vrlo kvalitetna resenja.
Za optimizaciju sam koristio SA (Simulated Annealing) algoritam koji se inace mnogo koristi u resavanju NP problema. Najpoznatiji NP problem je problem trgovackog putnika ili matematicki receno, problem nalazenja najkraceg Hamiltonovog puta u poptunom digrafu. Moram da kazem da je algoritam izuzetno robustan i efikasan. Pred kraj sam program hteo da prepravim tako da umesto SA koristi GA (genetic algorithm) ali sam od toga odustao jer sam kroz neke testove utvrdio da je GA nesto losiji od SA algoritma.
Inace sve ovo je bilo manje vise jednostavno. Pravi izazov je bio da se odrede tezinski koeficijenti kojim su se mnozile trenutne vrednosti pojedinih uslova u kriterijumskoj funkciji. U pocetku sam to radio tako sto sam pustao probne rasporede, analizirao kvalitet dobijenih resenja i rucno menjao vrednosti tezinskih koeficijenata. Ovaj korak sam ponavljao sve dotle dok algoritam ne pocne da daje zadovoljavajuca resenja (obicno mi je bilo potrebno 5-10 iteracija). Kasnije sam algoritam unapredio tako da je i ovaj korak bio potpuno automatizovan.
Zoran
[Ovu poruku je menjao stepanz dana 04.11.2010. u 08:53 GMT+1]
[Ovu poruku je menjao stepanz dana 04.11.2010. u 09:08 GMT+1]
[Ovu poruku je menjao stepanz dana 04.11.2010. u 09:12 GMT+1]
[Ovu poruku je menjao stepanz dana 04.11.2010. u 09:33 GMT+1]
[Ovu poruku je menjao stepanz dana 04.11.2010. u 09:36 GMT+1]
[Ovu poruku je menjao stepanz dana 04.11.2010. u 09:55 GMT+1]