Układanie planów lekcji - algorytm

Na wstępie zaznaczam, że nie chodzi mi o rozwiązanie problemu za mnie ;-)

poszukuję algorytmu wspomagającego układanie planów lekcji bądź realizującego właśnie taką funkcjonalność. moje poszukiwania skończyły się niestety na ofertach komercyjnych produktów, natomiast ja potrzebuję napisać to samemu.

jeśli robiliście kiedyś podobny program lub moglibyście mi doradzić co byłoby skuteczne w tego typu projekcie, byłbym wdzięczny za wszelkie pomysły i sugestie.

dodam tylko, że planuję to zrobić w PHP+MySQL.

P.S. proszę nie pisać postów typu "zrób sieć neuronową" itp.

1. układanie wsyzstkich możliwych i wybranie najlepszego (btw jak określasz warunki końcowe?)
2. algorytmy genetyczne
   no i poczytaj sobie tu http://groups.google.com/groups?q=algorytm+ukladanie+planu+zajec&hl=pl&lr=&ie=UTF-8&oe=UTF-8& oraz http://www.google.com/search?client=opera&rls=pl&q=timetabling+algorithm&sourceid=opera&ie=utf-8&oe=utf-8

ad.1. nie wiem jeszcze jak określić warunki końcowe, na pewno założenie jest takie, żeby było jak najmniej okienek - zarówno dla uczniów, jak i nauczycieli.

no ale musisz pewnie jeszcze uwzględnić sale - np. sala 100, 101, 102 to sale matematyczne, 103 to sala fizyczna... sala 104 to sala polonistyczna pani kowalskiej...

Zdaje mi się, że algorytm do układania planów lekcji można zrobić tylko dla pojedynczego przypadku - konkretnej szkoły... Chyba, że zrobisz, żeby użytkownik mógł sobie wypisać sale, jakie lekcje mogą sie w nich odbywać, jakiego nauczyciela ma klasa... dodatkowo dochodzi ile godz. jednej lekcji mają uczniowie w tygodniu... Musisz tez uwzglednic zeby były w jednym dniu dwie lekcje polskiego pod rząd, oraz żeby nie było np. 3 matematyk jednego dnia... dodatkowo nie moze byc okienek dla uczniow, dla nauczycieli - jak najmniej... lekcje nie mogą się kończyć zbyt późno, uczniowie nie powinni mieć wiecej niz 9 lekcji jednego dnia, musi zostac czas na zajecia dodatkowe........... algorytm rośnie i rośnie - życzę powodzenia ;-P

@lewymati:

1. założenie jest takie, że sale są dowolne (tzn. nie są przypisane ani do przedmiotu, ani do klasy, ani do nauczyciela).
2. reszta rzeczy też jest uwzględniona - do każdej klasy jest przypisane ile godzin jakiego przedmiotu ma dana klasa w tygodniu.
3. lekcje mogą się danego dnia powtarzać.

razor napisał(a)

1. założenie jest takie, że sale są dowolne (tzn. nie są przypisane ani do przedmiotu, ani do klasy, ani do nauczyciela).

Nie przelicz się ;). O ile z matematyką czy polskim problemu nie będzie, o tyle nie zdziw się jak algorytm wrzuci WF do pracowni komputerowej, a informatykę na salę gimnastyczną :P. Musisz niestety uwzględnić takie rzeczy :)

// Dopisane
I jeszcze jedno: uwzględnij, że jak są 2 lekcje tego samego przedmiotu pod rząd, to będą w jednej sali.

thenkles napisał(a)

razor napisał(a)

1. założenie jest takie, że sale są dowolne (tzn. nie są przypisane ani do przedmiotu, ani do klasy, ani do nauczyciela).

Nie przelicz się ;). O ile z matematyką czy polskim problemu nie będzie, o tyle nie zdziw się jak algorytm wrzuci WF do pracowni komputerowej, a informatykę na salę gimnastyczną :P. Musisz niestety uwzględnić takie rzeczy :)

// Dopisane
I jeszcze jedno: uwzględnij, że jak są 2 lekcje tego samego przedmiotu pod rząd, to będą w jednej sali.

ok dzięki ;-) przemyślę to i na pewno wezmę pod uwagę [browar]

Sprawdz algorytm kolorowania grafow (jest mase roznych odmian - metod kolorowania).
Ciebie glownie beda interesowac te w wersji off-line, dla kolorowania wierzcholkow.

Nigel - niezalogowany napisał(a)

Sprawdz algorytm kolorowania grafow (jest mase roznych odmian - metod kolorowania).
Ciebie glownie beda interesowac te w wersji off-line, dla kolorowania wierzcholkow.

może trochę się nie znam, ale co mają grafy do układania planów lekcji ;-)

No to bardzo sie nie znasz :)
Jak troche zapoznasz sie z tematem, to zobaczysz.
Jak nie zapomne, to po powrocie do domu napisze Ci tytul ksiazki, gdzie caly temat jest dosyc dobrze opisany.

@Nigel - byłbym b. wdzięczny.

Zgodnie z obietnica :

"Optymalizacja dyskretna : modele i metody kolorowania grafów / pod. red. Marka Kubale "

Mam nadzieje, ze to rozwiaze Twoj problem.
Powodzenia

Od siebie dodam, że może Cię również zainteresować Metoda Simplex. Garść informacji z przykładami: http://www.republika.pl/simplex/

Nigel - niezalogowany napisał(a)

"Optymalizacja dyskretna : modele i metody kolorowania grafów / pod. red. Marka Kubale "

OT: Mam teraz z autorem tej książki wykłady na uczelni :-)

@makumba, co to za uczelnia? ;-)

Witam
Sam jeszcze bedac 15letnim brzdącem robilem ten program (nieskromnie przyznam ze jak na moje kieszonkowe, ładną monetę na tym zarobiłem sprzedajac po szkolach)
...jednak ograniczylem sie troszke, program nie ukladal do konca planu lekcji całego
W trakcie poszukiwan natknalem sie na prace magisterska dot. dokladnie tego tematu (teoria oraz napisany program, ktorego neistety nie znalazlem)
Praca ta byla napisana na Politechnice Wrocławskiej, zostaly tam podane i opisane 4 metody (chyba najlepiej opisana bo i z tego piszacy korzystal, jakas tam heurystyka) - i to tyle ile pamietam ;/
niestety wiecej nie mam ;/

//
...z moich doswiadczen: jesli interesujesz sie bo chcesz zarobic na tym myslac ze szkoly nie maja takich programow --- odpusc sobie. Tragiczny rynek (brak kasy w budzecie, zacofanie dyrektorow, konkurencja w postaci duuuuzych firm)