raspored casova

Pogledaj http://www.asctimetables.com/
Program nije los, trial verzija ima punu funkcionalnost kao i full verzija, osim exporta u Excel i HTML. Takodje, program je lokalizovan i na srpski jezik, i ima dobar tutorial, tako da brzo moze sa njim da se radi. Postoji i mogucnost paralelnog generisanja rasporeda sa vise masina preko LAN-a istovremeno ako su ogranicenja dosta kompleksna.
Nije kao profi alati npr. gp Untis, ili Lantiv, ali sve u svemu dosta solidno.

Zar se ovo na neki nacin ne moze rjesiti nelinearnim programiranjem, odnosno optimizacijom neke funkcije cilja? Takvu funkciju bi bilo tesko napraviti, ali opet mi i to izgleda logicnije nego brute force filtriranje.

Nisam baš mnogo o ovome razmišljao ali cini mi se da bi se za rjesenje bar djela problema mogao koristiti Network Flow, kao na primjer kad se radi bipartitativno uparivanje, samo naravno sa vecim izborom.

ps: i tek sad vidim koliko je stara tema... Mislim ajd' zdra'o :-)

---

Znam da je tema poprilicno stara ali cu pokusatai da je ozivim. Jos davne 1992 sam napisao prvu verziju aplikacije koja je potpuno automatski generisala raspored casova. Definisao sam bio 19 uslova i njihovu ispunjenost proveravala posebna kriterijmska funkcija (funkcija cilja). Svaki uslov je imao svoj prioritet (0-7) na osnovu kojih im se izracunavo tezinski koeficijent. Algoritam za optimizaciju je proveravao koliko je koji uslov blizu nule i tezio je da vrednosti svih uslova svede na nulu. Za racunanje ispunjenosti sam koristio posebnu logiku za svaki od uslova. Npr. ako sam zeleo da teze casove stavim na kraj radnog dana a lakse na pocetak svaki predmet je imao koeficijent za tezinu predmeta i formula za ispunjenost pedagoskog uslova je glasila: SUM(ABS(cas-tezina_predmeta). Algoritam se trudio da minimizuje ovu funkciju tako sto je predmete sa tezinom 1 pokusavao da stavlja u prve casove a predmete sa tezinom 7 u sedme casove itd. Naravno ovaj uslov nije bio "strog" uslov tj. nije morao da bude sveden na nulu. Drugi uslovi kao na npr. predavac predaje u dva odeljenja istovremeno je bio "strog" uslov i morao je da bude sveden na nulu jer protivnom resenje nije bilo valjano.
Inace prvu verziju aplikacije sam napisao u Turbo Pascalu 7.0 a vrlo brzo sam je kasnije preradio u Delphi. Na zalost nikad nisam napisao komercijalnu verziju (vizuelno je bila do bola ruzna i imala je par bugova) vec sam program koristio ja i naplacivao skolama izradu rasporeda. Uspesno sam radio rasporede casova za tri osnovne i jednu srednju skolu godinama ali mi je onda to dosadilo i direktorima skola sam preporucio da odu na www.time-table.net i kupe njihovu verziju. Inace mogu da se pohvalim da je moj program u 99% slucajeva davao resenja koja su bila od resenja koje su radili nastavnici rucno (u pocetku sam radio rasporede paralelno sa nastavnikom) a u najgorem slucaju je resenje bilo identicno covekovom. Inace izrada jednog rasporeda je u ono vreme (1992/3 sam imao i386) trajalo oko pola sata do sat (u zavisnosti od velicine skole) da bi kasnije kupovinom pentiuma to vreme palo na svega par minuta.

S obzirom da imam gomilu iskustva sa ovakvim programima ako nekog ineteresuju detalji rado cu mu odgovoriti.

Zoran

Inace program je bi omiljen kod direktora skola jer kad god bi se neki predavac bunio sto ima 1 pauzu nedeljno a njegov kolega koji je mladji nema ni jednu, direktori bi samo slegnuli ramenima i rekli "Sta da radim, takvo resenje je izbacio racunar. Nisam ja kriv." :) Jednom sam imao i bliski susret sa jednom nastavnicom srpskog jezika. Bila jer besna jer je ona jedina od svih nastavnika srpskog jezika imala 1 pauzu u nedelji. Ja sam isto kao i direktori samo slegao ramenima i ponavljao njihove reci "Takvo resenje je izbacio racunar. Nisam ja kriv". Inace sam u aplikaciji imao mogucnost da favorizujem pojedine nastavnike da imaju bolje rasporede tj. manje pauza od nastavnika sa manjim prioritetom ali za tu funkcionalnost su znali samo direktori skola. Obicno sam starijim nastavnicima davao veci prioritet. Doduse desavalo da je raspodela fonda casova i odeljenja po nastavnicima takva da su neki nastavnici jednostavno morali da imaju bar jednu pauzu nedeljno ali je to bas bilo retko.

Zanimljivo. Koji su sve uslovi postojali, koji se to kriterijumi razmatraju u pravljenju rasporeda? Navedi i one skrivene :-)

Na Matematičkom fakultetu u Beogradu se raspredi prave pomoću programa koji je napisao sada docent, a onda asistent Filip Marić. Logika je iskazna. Osnovni iskaz je "Predavač A ima čas u terminu B u učionici C". Želje predavača se formulišu kao iskazne formule (nema ograničenja) i onda program pokušava da ih zadovolji. Prvo se moraju zadovoljiti želje redovnih profesora, pa vanrednih itd. Ako ne može sve da se zadovolji, onda trpe saradnici u nastavi (nekadašnji asistenti-pripravnici).

Program je univerzalan za rešavanje problema zadovoljivosti skupa iskaznih formula (SAT) koji glasi



Na isti način se modelira rešavač zavisnosti paketa na linuksu. Bio sam na Filipovoj odbrani doktorske disertacije koaj se bavi SAT rešavačima. Ako bude zainteresovanih, mogu da napišem nešto o algoritmima rešavanja.

---

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
<sub>[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]</sub>

Setih se jos jednog vrlo bitnog uslova:

16. Predavac ne sme da ima manje od minimalnog datog broja casova dnevno. Minimalni broj casova dnevno je uglavnom bio 2 sem u slucajevim kada je bilo nemoguce naci takvo resenje. Inace ovo je bio labav uslov ali vise strog od ostalih labavih uslova kao npr. 1. uslov. Ovaj uslov je imao veci tezinski koeficijent od ostalih labavih uslova ali manji od strogih.

Inace ovaj uslov je bio vrlo bitan jer direktori nisu dozvoljavali da nastavnici imaju 1 cas dnevno jer su oni taj cas ili premestali u neki drugi dan kao predcas ili ga jednostavno nisu ni drzali. Cesto mi se desavalo da moram da trazim drugo resenje zbog toga sto je npr. neki predavac imao 1 cas sredom.

Pretpostavljam da se pauze iz 8 i 9 zapravo odnose na neradne dane. Kakav to problem nastavnici imaju s neradnim danima?

Inače, ja bih to rešavao demokratski. Neka sve opcije imaju neku cenu u prestižu, i neka svaki profesor ima određeni prestiž. Profesor može da zahteva onoliko uslova koliko mu prestiž dozvoljava, a svaki uslov može dodatno da naglasi "pumpanjem" prestiža. Cilj algoritma je zapravo da pronađe maksimum iskorišćenog prestiža.

Ako postoji mnogo rešenja sa svim prestižom iskorišćenim, onda u celu ekonomiju treba uneti još prestiža, da bi profesori mogli dodatno da biraju. Kada broj mogućih rešenja padne na ispod 5 onda smo iscrpli sve što profesori mogu da izvoljevaju. Svako od tih rešenja je prihvatljivo, pa bi profesori mogli i da glasaju za jedno. Posle glasanja više nema žalbi.

Pauze iz 8 i 9 se odnose na radne dane. Na primer predavac N1 sredom ima prvi, drugi i treci cas, pa pauzu pa peti i sesti. Takve pauze je jedan predavac mogao da ima maksimalno dve u toku nedelje i jednu u toku dana mada je taj uslov bio parametrizovan.
Inace kao sto rekoh taj program sam poceo da pisem 1991 (kada sam bio cetvrta godina srednje matematicke) a prvu upotrebljivu verziju sam imao tek 1993 i to tek kada sam polozio matematiku IV na etf-u kada sam se prvi put i susreo sa pojmom heuristika. Kasnije sam ukapirao da sam mnoge stvari mogao da uradim drugacije i vremenom sam program doradjivao. Na kraju sam i ja dosao do istog zakljucka da je dobro da predavac ima svoj prestiz jer sam tako pojedine predavace dodatno mogao da favorizujem. Inace svaki uslov je imao prioritet koji mogao da se menja u granici od 0-20. Uslovi sa prioritetom 0 su bili uslovi sa najvisim prioritetom i algoritam je tim uslovima dodeljivao najvece tezinske koeficijente. Cak sam planirao da dodam da svaki predavac ima svoja podesavanja prioriteta uslova ali je to bila prevelika izmena u kodu pa sam od toga odustao.

Setih jos dva uslova:
17. 18. Pojedini predavaci nisu smeli da imaju istovremeno casove sa nekim drugim predavacima. Npr. ako u skoli postoji jedan kabinet za hemiju samo je jedan hemicar mogao da ima taj cas sto zanci da je hemicarima bilo zabranjeno da istovremeno drze predavanja. Ovaj uslov sam podelio na dva, labav i strog.
19. 20. Ovaj uslov je suprotan 17 i 18 tj. postojali su predavaci koji su jednostavno morali da imaju istovremeno casove. Recimo predavaci stranog jezik su morali da drze istovremeno predavanja jer u jednom odeljenju moze da bude 10 ucenika koji uce engleski, 10 koji uce francuski i 10 koji uce nemacki. To znaci da su predavaci engleskog, francuskog i nemackog jezika morali istovremeno da drze predavanje. I ovaj uslov je bio podeljen na dva, labav i strog.

Sto se tice glasanja predavaca za najbolje resenje to nije postojalo. Uvek sam izbacivao 5-6 razlicitih rasporeda i onda su se direktor i zamenik direktora odlucivali za jedno od tih resenja i predstavljali ga predavacima na nastavnickom vecu.
<sub>[Ovu poruku je menjao stepanz dana 04.11.2010. u 14:11 GMT+1]

[Ovu poruku je menjao stepanz dana 04.11.2010. u 14:40 GMT+1]

[Ovu poruku je menjao stepanz dana 04.11.2010. u 14:42 GMT+1]</sub>

Pre neki dan sam seo i napisao kratko programce koje koristi SA algoritam za resavanje problema trgovackog putnika (TSP problem) a koji sam koristio kao engine za kreiranje rasporeda casova. Da bi ste ga startovali morate da imate instaliran .NET Framework 2.0. Mislim da uputstvo za koriscenje nije potrebno.