postoje programi, ali ne znam koliko su "u potpunosti" obradili problem.

ja sam se sa ovim igrao, i analizirao / mozgao u 4. razredu srednje, mada ne toliko da bih pravi program, koliko da bih se izvukao sa casova i igrao na novoj opremi u rc-u :D

znam da je tada u skolu faxom stigla ponuda za prodaju takvog programa, mada ne znam detalje, i nisam video program.

znaci, zakljucak je: resenje postoji, koliko je dobro ne znam.

moj licni zakljucak je da je (prakticno) nemoguce napraviti program koji ce se ponasati logicno, i po zelji svih profesora kao kada se raspored pravi rucno.

nemoguce je predvideti sva moguca resenja za sve moguce probleme u skolama (tipa, postoji samo jedan kabinet za hemiju, a tri profesora, a jedan od njih predaje samo teoriju te godine, itd.).

kao i predvideti sta sve odgovara profesorima (jedan radi pola radnog vremena u ovoj, pola u drugoj skoli, pa mora da se uskladjuje sa rasporedom iz te skole, pa jedan voli da ima uvek poslednje casove, jer mu to vise odgovara, jer voli covek da ide ujutru da peca, itd..)

sa druge strane, kada bi se negde podvukla granica (sta ce program resavati, i koje ce zelje ispunjavati, a sta nece) onda se moze napraviti neki program koji dovoljno aproximira - tj ubrzava rad na rasporedu - koji se na kraju ipak mora rucno doradjivati...

ali može da kontroliše dvostruke unose i da sprečava da dođe do grešaka koje je teško videti na prvi pogled. Moja prof. informatike je napisala tako nesto u pascalu za školu... Znači, sve je ručno i onda možeš da unosiš i menjaš... Program valjda razdeli na početku, a ti onda prenosiš...

to sam i ja rekao, moze da sluzi samo kao pomocni program... sve sam da radi ne moze...

ko bi rekao da takvo nesto jos nije napisano, a naizgled tezi problemi se bez problema rjesavaju na racunaru. valjda ce nekada i to moci da se uradi....

Pravljenje rasporeda casova nije nimalo naivan problem, cak neki kazu da bi nam trebala AI da to resi... Pomenute muzicke zelje po pitanju radnog vremena, ranog ustajanja i nepodnosenja profana samo otezavaju problem. U sustini zadatak takvog softvera je da prema raspolozivim podacima i resursima napravi najbolju mogucu kombinaciju gde ce biti zadovoljeno sto je vise mogucih muzickih zelja (sve se gotovo nikad ne mogu zadovoljiti i to je jedan od problema zasto nema egzaktnog resenja).
Ja ne znam programe (komercijalnog tipa) koji to rade, ali mogu priblizno da objasnim nacin njihovog rada. Svaka stavka za koju bi pozeljno bilo da bude ispunjena se rangira po vaznosti (naravno postoje i prioriteti koji moraju biti ispunjeni, recimo ako ti imas 3 casa hemije nedeljno to mora da ostane 3 a ne 2, 4 ili sta vec). Jedno od resenja koje bi dalo zaista najpovoljniju podelu je gruba sila, ili ispitivanje svih kombinacija, sto nije problem isprogramirati, ali itekako je problem koriscenja procesorskog vremena. Najveci problem kod takvih algoritama je ispitivanje suludih kombinacija ili kombinacija koje definitivno nisu najbolje. Zato se koristi secenje. To je izraz kada u nekom algoritmu zasnovanom na backtrack-u (pretrazivanje sa vracanjem - najcesce primenjivana "gruba sila") jednu granu pretrage jednostavno odbacite (odsecete) jer znate da njeno pretrazivanje nece (ili najverovatnije nece) dovesti do trazenog resenja. Na taj nacin algoritam se ubrzava. S druge strane sledi da je broj odbacenih, a mozda i povoljnih kombinacija obrnuto srazmeran trosenom procesorskom vremenu (koje zna da bude veliko...). Dakle sve sto mozete uraditi je da sto bolje napravite rangiranje zahteva koji se od vas traze i da napravite sto "pametniji" kriterijum secenja, tj. kada ce te u pretrazi reci, e dalje necu ovo je suludo, vracam se da probam druge kombinacije....
To je otprilike osnova rada vecine "rasporedjivaca casova" - dakle jednostavno napravite mustru i racunate najbolju kombinaciju. Naravno valjanost rasporeda zavisi kako od uslova secenja, tako i od pomenutog rangiranja i gotovo je nemoguce ubosti najbolje resenje, ali se moze naci dovoljno dobro, sto je ipak uspeh... Dakle navedeni opis je u sustini heuristika koja vam daje jedno od mogucih resenja prema vasim kriterijumima. Upravo zato se koriste naknadne "inteligentne" dorade od strane profesora ili koga vec...

Pozdrav

caos
pogledaj ovaj sajt: http://www.geocities.com/SiliconValley/Lakes/4929/astar.html
radi se o AIu u igricama, ali mi se cini da je to isto sto i tvoj problem (naci najbolju putanju do necega uz odredjene uslove).

Ali problem je što ti uslovi nisu univerzalni i ma koliku apstrakciju uslova ti pravio, naći će se neki koji tvoj program neće moći da obradi, a onda sve pada u vodu.

Pogledajte svi ovamo -> http://www.tf.zr.ac.yu/aktivnosti/deduc.html
Mislim da je to nesto najnaprednije sto se moze naci u smislu prosirivosti i muzickih zelja.

Da li je neko zainteresovan za rad na sličnom projektu, ali samo uz korišćenje GA metode (Gentetički algoritmi).

Ja duže vreme razmišljam o tome, i mislim da je moguće dobiti prihvatljiv raspored GA metodom, ukoliko se ispravno postavi fitnes funkcija. Jedini problem je što funkcija treba da ima izvestan stepen generalizovanosti, pa da bude moguće koristiti različite uslove.

Možda sam sve ovo nabrojao s brda- s dola....

Bottom line, ... ukoliko je neko zainteresovan za implementaciju u Javi, C++-u, C#-u neka se javi pa da vidimo šta možemo da napravimo.

P.S.

Što se tiče komercijalnih verzija još uvek ne postoji neki paket koji to radi na pravi način. Konkretno moje informacije govore da bi u Belgiji takav sistem imao oko 65% procenata svih škola kao zainteresovane kupce.

Ako skup mogucih resenja (bez nestandardnih uslova o kojima ste pricali) nije neverovatno veliki, mozda bi bilo prostije da program napravi listu svih mogucih rasporeda, a da se lista naknadno "proseje" skupom svih trazenih uslova dok se ne nadju resenja koja ih zadovoljavaju ili blisko zadovoljavaju (u kom slucaju direktor odluci, ili se dogovore, koji manje vazni uslovi mogu da se zrtvuju)

river:
To bi bila samo jos jedna od heuristika za odredjivanje rasporeda. Geneticki algoritmi ne moraju da ti daju tacno, mada uz dobru implementaciju dovoljno dobro resenje. E sada ja bih posebno obratio paznju na nultu generaciju.

Mada, moram priznati, stvarcice koje sam video da rade pomenutom metodom - rade jako fino (i relativno brzo).

Ako mozes opisi malko detaljnije ideju, pa cemo videti sta moze sa tim da se ucini.
Vazno bi bilo obratiti paznju na sledece stvari:

1. U nultoj generaciji MORAJU biti zadovoljeni svi zahtevi (razume se, u razlicitim kombinacijama)
2. U nultoj generaciji bi valjalo da se vise puta ispunjavaju zelje veceg prioriteta (mada se ovo moze regulisati i u procesu same generacije, ispitivanjem neke hijerarhije, ali bolje je ovako krenuti). Primer: ako imamo obavezan zahtev da neko odeljenje ima 3 puta nedeljno matematiku, onda se u svim pocetnim kombinacijama mora naci taj uslov. Na taj nacin necemo ni morati da proverimo da negde usput nismo izgubili neku matematiku za to odeljenje. Naravno tu bi bilo brdo posla u samoj generaciji, tako da nije na odmet kvalitetna organizacija informacija (nazovi to potrebom za "inteligentnom strukturom podataka").
3. Izlaz iz iteracije. Lepo bi bilo da korisnik moze zadati neki minimum uslova sa kojima je zadovoljan. Onda bi se mogla napraviti fina procena na sledeci nacin:
Kada kvalitet rasporeda (po nekom kriterijumu) predje dati minimum tada znamo da ce algoritam dati zadovoljavajuce resenje. Kada kvalitet algoritma pocinje da "konvergira" to je znak za kraj (a ovo ce sigurno da se desi u nekom trenutku, mada nikad nismo sigurni da se posle nekog broja generacija opet pojavi dosta bolje resenje). Ako je presao minimum to je nadjeno resenje u suprotnom algoritam nije dovoljno dobar ili su zahtevi nerealni.

Pozdrav !

Da ali po nekom mom skromnom mišljenju takav pristup bi imao najbolju marketinšku prođu na tržištu škola. Vrlo je lako zainteresovati nekog kad počneš da mu pričaš o genetici u računarstvu, i plus, implementacija uz pomoć GA ima tu osobinu da je raspored u stalnoj doradi. Škole o kojima ja pričam i ovako imaju računare koji rade 24h dnevno, pa je to njima prihvatljiva solucija. Isto tako GA rešavanje ima dosta analogije sa čovekom koji pravi raspored manualno.

O nultoj - početnoj generaciji:

Ukoliko želiš da zadovoljiš uslove u prvoj iteraciji, odnosno postavci problema, ti si u stvari rešio ceo posao. A upravo je to bio kamen spoticanja u svim mojim razmišljanjima na temu. E sada, nešto drugo imam na umu. U generisanju prvog rešenja zadovoljiti samo neke naj-banalnije uslove (Jedan čovek nemože da predaje na dva mesta u isto vreme, i sl), tj. napravio bih analogiju sa manuelnim rešavanjem problema, gde je jedan čovek ispred velike tabele, i ima male čiodice sa imenima profesora.

Mora se imati na umu da želimo da napravimo što fleksibilniji sistem uslova, koji bi imali svoju težinu (korisnik može modifikovati težinu svakog uslova u ukupnom rešenju), te je stoga jasno da će u 80-90% slučajeva biti nemoguće zadovoljiti sve uslove. U tome je i caka. Kada se ručno pravi raspored čovek dođe do nekog rešenja i onda tu stane i kaže e ti ne možeš da ne radiš ponedeljkom, ne uklapa se u raspored. Škole traže upravo to, da samo oslobode profesora (informatike i/ili matematike) posla oko pravljenja rasporeda. Nije im puno bitno da li će računar moći da da najoptimalnije rešenje, dovoljno je da bude barem jednak optimalnosti čoveka.

U glavi imam ideju da svi uslovi idu u bazu, da može da ih ima od 10 do npr 1000 (hardcoded number). Baza bi trebala da bude nešto slučno sistemima za donošenje odluka (DMS). Znači sve parametrizovano.

Ne znam da li je ovo dovoljno informacija, ali posle neprospavane noći teško se koncentrišem

Vrlo interesantan problem. Ovako ja mislim:
prvi deo bi bio da se odrese sve moguce kombinacije, naravno u pocetku se odmah iskljuce one koje su sulude (recimo dva predmeta ili tri predmeta ista u jednom danu) a onda da se svi bruteforce rezultati filtriraju po parametrima koji im se zadaju (tipa razlika izmedju casova hemije mora bit ne manja od 2 dana i slicno.)

Sa jednom godinom zakasnjenja, preporucujem da pogledas www.time-table.net.
Diskusiji o GA ti isuvise paznje posvecuje nultoj generaciji. Ona uopste nije toliko bitna za kvalitet resenja. Kljucna stvar su MUTACIJE!

Radim kao pedagog u osnovnoj skoli i srecem se sa ovim problemom svake godine.
Kod izrade rasporeda casova najbitniji segmenat su ucenici i materijalno tehnicke mogucnosti - muzicke zelje nastavnika i sl. se kao uslov ispunjuavaju samo ako je u skladu sa prvim segmentom. Najbitnija stvar je ravnomerna opterecenost ucenika u toku dana (pozicija lakih i teskih predmeta i sl. - s napomenom da tezak predmet ne mora biti samo matematika - svi znamo da tezina predmeta pored objektivnih cinilaca ima i jedan subjektivni a to je nastavnik koji predaje taj predmet), zatim ravnopravna opterecenost ucenika u toku nedelje kao i pedagoski model koji ce se izabrati za formiranje strukture rasporeda. Vise informacija o pedagoskim principima struktuiranja rasporeda casova mozete vidjeti u knjizi Didaktika I,II i III od Mladena Vilotijevica (izdanje uciteljskog fakulteta).

Postovani kolega, pogledajte www.time-table.net

dosta dobar program za generisanje rasporeda chasova je i programa Prof Dr Petra Hotomskog sa tehnichkog fakulteta u Zr-u. Program se zove Deduc! vishe o programu na tf.zr.ac.yu

 A gde moze da se nabavi taj program (citaj skine?)

A zasto se ne bi npr. upitali svi profesori kada bi voljeli da rade, odnosno njihovo idealno radno vrijeme, koje bi kasnije bio kao jedan veoma bitan parametar u slaganju rasporeda... Zvuci jednostavno, ali vjerujem da bas i ne bi bilo valo izvedivo, ako netko ima nesto reci za ideju, nek slobodno kaze.

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.