[es] - Optimizacija rasporeda

krul
Cardak ni na nebu ...

Član broj: 16060
Poruke: 85
*.bchsia.telus.net.

+1 Profil

^{24.11.2005. u 13:08 - pre 224 meseci}

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?

????

Jednostavnost! Odlika genijalnosti

Odgovor na temu

NrmMyth
Ivan Maček
Split

Član broj: 63456
Poruke: 849
*.cmu.carnet.hr.

Sajt: www.dump.hr

Profil

Re: Optimizacija rasporeda

^{24.11.2005. u 18:44 - pre 224 meseci}

Neznam, pisi sam.

Odgovor na temu

BraMom
Branimir Momcilovic
Niš, Prokuplje

Član broj: 51489
Poruke: 38
*.vdial.verat.net.

Profil

Re: Optimizacija rasporeda

^{25.11.2005. u 10:01 - pre 224 meseci}

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]}

Odgovor na temu

krul
Cardak ni na nebu ...

Član broj: 16060
Poruke: 85
*.bchsia.telus.net.

+1 Profil

Re: Optimizacija rasporeda

^{25.11.2005. u 14:31 - pre 223 meseci}

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.

Jednostavnost! Odlika genijalnosti

Odgovor na temu

BraMom
Branimir Momcilovic
Niš, Prokuplje

Član broj: 51489
Poruke: 38
*.vdial.verat.net.

Profil

Re: Optimizacija rasporeda

^{26.11.2005. u 21:22 - pre 223 meseci}

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.

Odgovor na temu

krul
Cardak ni na nebu ...

Član broj: 16060
Poruke: 85
*.bchsia.telus.net.

+1 Profil

Re: Optimizacija rasporeda

^{26.11.2005. u 23:28 - pre 223 meseci}

Branimire, veliko hvala
Pozdrav

Jednostavnost! Odlika genijalnosti

Odgovor na temu

BraMom
Branimir Momcilovic
Niš, Prokuplje

Član broj: 51489
Poruke: 38
*.vdial.verat.net.

Profil

Re: Optimizacija rasporeda

^{28.11.2005. u 14:03 - pre 223 meseci}

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...

Odgovor na temu