Optimizacija rasporeda

[ krul @ 24.11.2005. 13:08 ] @

Optimizacija rasporeda
Pozdrav, uradio sam sistem koji pomaze skolama da organizuju sastanke Ucitelj-Roditelj. Sistem za svakog ucenika generise pozivnu listu koja sadrzi predmete koje taj ucenik pohadja, podatke o uceniku i vremenom odrzavanja tih sastanaka (sesija). Sesija moze biti vise tako da roditelj ima izbor da bira recimo Utorak 8-10, Utorak 16-20, Sreda 8-10 itd. Znaci roditelj ima mogucnost izbora sesije u zavisnosti s njegovim raspolozivim vremenom. Sad Sesija je razbijena u odredjen broj intervjua. Broj intervjua zavisi od duzine sesije i duzine intervjua. S obzirom na to da ucenik moze da pohadja vise predmeta sto ukljucuje vise ucitelja sistem mora da uzme u obzir vreme potrebno roditelju da dodje sa sastanka A na sastanak B - (travel time). Ono je isto odredjeno prilikom definicije sesije. Kad se jednom roditelj odluci koje ce ucitelje da poseti on popuni listu i klinac je vrati u skolu gde ta lista bude procesirana u smislu da sluzbenik uzme listu i onda locira studenta i izabere jednu ili vise sesija u zavisnosti od roditeljeve raspolozivosti, i pokusava da nadje slobodan prostor u uciteljevom rasporedu (time slot). Zanima me (buduci da planiram opciju gde bi sluzbenik prvo skupio liste svih ucenika unio njihove zahteve i onda prtisnio dugme rasporedi. Ja bih onda trebao da analiziram sve zahteve i rasporedim ih tako da 1. Roditelj sto manje ceka od sastanka do sastanka, 2.Ako roditelj ima vise dece da sistem ne rasporedi dva sastanka u isto vreme. 3.Ako definicija sesije dozvoljava zdruzenost dece stavim bracu/sestre koje imaju zajednickog ucitelja u isti time slot 4.Ako definicija sesije dozvoljava zdruzenost predmeta (jedan ucitelj moze da predaje vise od jednog predmeta) da za ucenika koji ima istog ucitelja za vise predmeta rasporedi sve te sastanke u jedan time slot ili raspored 4.Da sistem ima u vidu kombinacije zdruzenosti.

E ako je iko ista razumio, razumice i moje pitanje koje sledi. Ima li iko algoritam koji bi mogao da predlozi za optimizaciju rasporeda? Neka smernica? Da ne izmisljam toplu vodu.
Prepoznaje li iko pattern u problemu koji sam iznio i moze li eventualno neki savet?

????

[ NrmMyth @ 24.11.2005. 18:44 ] @

Neznam, pisi sam.

[ BraMom @ 25.11.2005. 10:01 ] @

Cini mi se da se tvoj problem svodi na linearnu optimizaciju, znaci trazis linearno programiranje, najjednostavniji metod je simplex.
Probaj po pretrazivacima.

Da probam ukratko da objasnim poentu:

imas nepoznat vektor x=(x1, x2, ..., xn)
linearnu f-ju koju optimizujes (trazis minimum) f(x) = c*x,
(znaci c je transponovani vektor konstanti)
to mu izgleda ovako f(x) = c1*x1 + c2*x2 + ... + cn*xn

sada resavas jednacinu Ax=b, x>=0
tako da je f(x) minimalno

A je mxn matrica, gde je m broj jednacina, tj. ogranicenja koje postavis.

Ako ti trebaju nejednakosti u Ax=b, npr imas uslov x1+2*x2<10, onda dodajes tzv. slobodnu promenljivu x3 pa dobijas x1+2*x+x3=10.

Dobra vest je da se ovakve stvari rade odavno pa imas mnogo toga po netu ili knjigama, losa vest je da su metodi uglavnom numericki i da opsti slucaj, koliko znam, nije uvek resiv.

_{[Ovu poruku je menjao BraMom dana 25.11.2005. u 11:02 GMT+1]}

[ krul @ 25.11.2005. 14:31 ] @

Branimire puno hvala na ogovoru.
Fali mi znanje iz matematike da bi u potpunosti razumeo tvoj odgovor ali je tvoj odgovor ono sam i trazio -smernica. Hmm znaci vektori, matrice itd, jel imas neki link eventualno materijal koji jednostavno razlaze to problematiku? Malo sam u stisci sa vremenom tako da mi treba nesto sto neide previse u dubinu a daje pregled stvari.
Jos jednom puno hvala.

[ BraMom @ 26.11.2005. 21:22 ] @

Rado bih ti pomogao ali skoro sam se preselio tako da nemam knjige i slicno kod sebe.

Na brzinu sam nasao neku knjigu, kosta 400din., verovatno vredni bar toliko:
http://www.indmanager.edu.yu/izd_del/knjige/8.htm

Probaj po fortranskom bibliotekama mozes lako da nadjes uradjenu simplex metodu. Ili probaj na forumu matematika, tu bi trebalo da ima ljudi koji se bave tim.

[ krul @ 26.11.2005. 23:28 ] @

Branimire, veliko hvala
Pozdrav

[ BraMom @ 28.11.2005. 14:03 ] @

Nasao sam neku knjigu, otpakujes zip pa dobijes .djvu,
plugin skini sa:
http://www.lizardtech.com/download/dl_options.php?page=plugins

http://www.zlogics.com/lp/LinearProgramming.zip
oko 2,2mb

Trebalo bi da mozes da je citas, ima i primera, ako imas vremena...

[ krul @ 28.11.2005. 20:23 ] @

Branimire,
Jos jednom hvala. Pregledao sam knjigu, svidja mi se, puna je primera, medjutim ne znam da li cu imati dovoljno vremena da ukapiram i implemntiram to resenje.
U svakom slucaju puno hvala
Pozdrav