Zastanawiałem się, czy są znane rozwiązania algorytmu tworzenia planu lekcji. Zasadniczo chodzi o optymalizację „rozproszenia godzin” (zarówno w przypadku nauczycieli, jak i klas) dla danych stowarzyszeń klasa-przedmiot-nauczyciel. Można założyć, że na wejściu mamy skojarzone ze sobą zestawy klas, przedmiotów lekcji i nauczycieli, a plan zajęć powinien mieścić się między 8:00 a 16:00.
Chyba nie ma na to dokładnego algorytmu, ale może ktoś zna dobre przybliżenie lub wskazówki jak to zrobić.
Odpowiedzi:
Ten problem jest NP-Complete !
Krótko mówiąc, aby znaleźć listę akceptowalnych rozwiązań, należy zbadać wszystkie możliwe kombinacje. Ze względu na różne okoliczności, w jakich problem pojawia się w różnych szkołach (na przykład: czy istnieją ograniczenia dotyczące sal lekcyjnych ?, Czy niektóre klasy są czasami podzielone na podgrupy ?, Czy jest to tygodniowy harmonogram? itp.) nie ma dobrze znanej klasy problemów, która odpowiada wszystkim problemom związanym z planowaniem. Być może problem plecaka ma wiele elementów podobieństwa do tych problemów w ogóle.
Potwierdzeniem, że jest to zarówno trudny problem, jak i taki, dla którego ludzie nieustannie szukają rozwiązania, jest sprawdzenie tej (długiej) listy (głównie komercyjnych) narzędzi do planowania oprogramowania
Ze względu na dużą liczbę zaangażowanych zmiennych, których największym źródłem są zazwyczaj pragnienia nauczyciela; -) ... zazwyczaj niepraktyczne jest rozważanie wyliczenia wszystkich możliwych kombinacji . Zamiast tego musimy wybrać podejście, które odwiedza podzbiór przestrzeni problemów / rozwiązań.
- Algorytmy genetyczne , cytowane w innej odpowiedzi, są (lub wydaje się , że IMHO ) są dobrze przygotowane do przeprowadzania tego rodzaju wyszukiwania półkierowanego (problem polega na znalezieniu dobrej funkcji oceny kandydatów do zatrzymania na następne pokolenie)
- Wykres Podejścia polegające na przepisywaniu są również przydatne w przypadku tego typu problemów optymalizacji kombinatorycznej.
Zamiast skupiać się na konkretnych wdrożeniach programu automatycznego generatora harmonogramów, chciałbym zaproponować kilka strategii, które można zastosować na poziomie definicji problemu .
Ogólne uzasadnienie jest takie, że w większości rzeczywistych problemów związanych z harmonogramowaniem konieczne będą pewne kompromisy, a nie wszystkie ograniczenia, wyrażone i domniemane: zostaną w pełni spełnione. Dlatego pomagamy sobie:
Podczas korygowania tej odpowiedzi zdaję sobie sprawę, że jest ona dość nieśmiała, aby udzielić konkretnej odpowiedzi, ale jest ona jednak pełna praktycznych sugestii. Mam nadzieję, że to pomoże, mimo wszystko, co jest „trudnym problemem”.
To bałagan. królewski bałagan. Aby dodać do odpowiedzi, już bardzo kompletnych, chcę zwrócić uwagę na moje doświadczenia rodzinne. Moja mama była nauczycielką i brała udział w tym procesie.
Okazuje się, że posiadanie komputera do tego jest nie tylko trudne do kodowania jako takiego, ale jest również trudne, ponieważ istnieją warunki, które są trudne do określenia w gotowym programie komputerowym. Przykłady:
Jak widać, problem nie jest NP-kompletny, to jest NP-szalony.
Robią więc, że mają duży stół z małymi plastikowymi wstawkami i przesuwają wstawki, aż uzyskają satysfakcjonujący wynik. Nigdy nie zaczynają od zera: zwykle rozpoczynają od harmonogramu z poprzedniego roku i wprowadzają poprawki.
Międzynarodowy Konkurs 2007 rozkładów miał ślad lekcja planowania i harmonogramowania egzamin utwór. W konkursie wzięło udział wielu badaczy. Wypróbowano wiele heurystyk i metaheurystyki, ale ostatecznie metaheurystyki wyszukiwania lokalnego (takie jak wyszukiwanie Tabu i symulowane wyżarzanie) wyraźnie pokonały inne algorytmy (takie jak algorytmy genetyczne).
Spójrz na 2 frameworki open source używane przez niektórych finalistów:
Jednym z moich zajęć na pół semestru było generowanie tabel szkolnych z wykorzystaniem algorytmów genetycznych.
Cały stół to jeden „organizm”. Pojawiły się pewne zmiany i zastrzeżenia w podejściu do ogólnych algorytmów genetycznych:
Ustalono zasady dla „nielegalnych stołów”: dwie klasy w tej samej klasie, jeden nauczyciel uczący dwie grupy w tym samym czasie itd. Mutacje te natychmiast uznano za śmiertelne i natychmiast wyrosnął nowy „organizm” w miejsce „zmarłego”. Pierwsza została wygenerowana przez serię przypadkowych prób uzyskania legalnej (choć bezsensownej). Śmiertelna mutacja nie została wliczona do liczby mutacji w iteracji.
Mutacje „wymiany” były znacznie częstsze niż mutacje „modyfikowania”. Zmiany zachodziły tylko między częściami genu, które miały sens - bez zastępowania nauczyciela klasą.
Małe premie zostały przyznane za połączenie pewnych 2 godzin razem, za przydzielenie tej samej ogólnej sali po kolei dla tej samej grupy, za utrzymanie godzin pracy nauczyciela i ciągłego obciążenia klas. Umiarkowane premie były przyznawane za zapewnienie odpowiednich sal lekcyjnych dla danego przedmiotu, przestrzeganie godzin zajęć w terminie (rano lub po południu) i tym podobne. Duże bonusy to przypisanie właściwej liczby podanych przedmiotów, nakład pracy nauczyciela itp.
Nauczyciele mogą tworzyć harmonogramy obciążenia „wtedy chcę pracować”, „w porządku wtedy pracować”, „nie lubi wtedy pracować”, „wtedy nie mogę pracować”, z przypisanymi odpowiednimi wagami. Pełne 24 godziny były legalnymi godzinami pracy, z wyjątkiem pory nocnej była bardzo niepożądana.
Funkcja wagi ... o tak. Funkcja wagi była ogromnym, potwornym iloczynem (jak w przypadku mnożenia) wag przypisanych do wybranych cech i właściwości. Było niezwykle strome, jedna właściwość z łatwością mogła ją zmienić o rząd wielkości w górę lub w dół - a w jednym organizmie były setki lub tysiące właściwości. Spowodowało to absolutnie OGROMNE liczby, ponieważ wagi, a co za tym idzie, konieczność użycia biblioteki bignum (gmp) do wykonywania obliczeń. W przypadku małego testu obejmującego około 10 grup, 10 nauczycieli i 10 sal lekcyjnych, początkowy zestaw zaczynał się od noty 10 ^ -200 czegoś, a kończył 10 ^ + 300 czymś. Był całkowicie nieefektywny, gdy był bardziej płaski. Również wartości znacznie wzrosły wraz z większymi „szkołami”.
Jeśli chodzi o czas obliczeń, różnica między małą populacją (100) w długim okresie a dużą populacją (ponad 10 tys.) W ciągu mniejszych pokoleń była niewielka. Obliczenia w tym samym czasie dały mniej więcej taką samą jakość.
Obliczenia (na niektórych procesorach 1GHz) zajęłyby około 1 godziny, aby ustabilizować się w pobliżu 10 ^ + 300, generując harmonogramy, które wyglądały całkiem nieźle, dla wspomnianego przypadku testowego 10x10x10.
Problem można łatwo sparaliżować przez zapewnienie funkcji sieciowej, która umożliwiłaby wymianę najlepszych próbek między komputerami, na których wykonywane są obliczenia.
Wynikający z tego program nigdy nie ujrzał światła dziennego na zewnątrz, dając mi dobrą ocenę z semestru. Wyglądało to obiecująco, ale nigdy nie miałem wystarczającej motywacji, aby dodać GUI i udostępnić go ogółowi społeczeństwa.
Ten problem jest trudniejszy niż się wydaje.
Jak wspominali inni, jest to problem NP-zupełny, ale przeanalizujmy, co to oznacza.
Zasadniczo oznacza to, że musisz spojrzeć na wszystkie możliwe kombinacje.
Ale „spójrz na” niewiele mówi ci, co musisz zrobić.
Generowanie wszystkich możliwych kombinacji jest łatwe. Może generować ogromną ilość danych, ale nie powinieneś mieć większych problemów ze zrozumieniem koncepcji tej części problemu.
Drugi problem polega na ocenie, czy dana możliwa kombinacja jest dobra, zła lub lepsza od poprzedniego „dobrego” rozwiązania.
W tym celu potrzebujesz czegoś więcej niż tylko „czy to możliwe rozwiązanie”.
Na przykład, czy ten sam nauczyciel pracuje bezpośrednio 5 dni w tygodniu przez X tygodni? Nawet jeśli jest to skuteczne rozwiązanie, może nie być lepszym rozwiązaniem niż naprzemiennie dwie osoby, tak aby każdy nauczyciel pracował po jednym tygodniu. Och, nie pomyślałeś o tym? Pamiętaj, że to ludzie, z którymi masz do czynienia, a nie tylko problem z alokacją zasobów.
Nawet jeśli jeden nauczyciel mógłby pracować w pełnym wymiarze godzin przez 16 tygodni bez przerwy, może to być nieoptymalne rozwiązanie w porównaniu z rozwiązaniem, w którym próbujesz zmieniać nauczycieli na przemian, a tego rodzaju równoważenie jest bardzo trudne do wbudowania w oprogramowanie.
Podsumowując, stworzenie dobrego rozwiązania tego problemu będzie wiele warte dla wielu, wielu ludzi. Dlatego nie jest łatwo rozwiązać i rozwiązać problem. Bądź przygotowany na wyznaczenie celów, które nie są w 100% i nazwanie ich „wystarczająco dobrymi”.
Mój algorytm planowania, zaimplementowany w FET (Free Timetting Software, http://lalescu.ro/liviu/fet/ , udana aplikacja):
Algorytm jest heurystyczny. Nazwałem to „zamianą rekurencyjną”.
Dane wejściowe: zbiór działań A_1 ... A_n i ograniczeń.
Wynik: zestaw czasów TA_1 ... TA_n (przedział czasowy każdej czynności. Pomieszczenia są tutaj wykluczone dla uproszczenia). Algorytm musi umieścić każdą czynność w przedziale czasowym, przestrzegając ograniczeń. Każdy TA_i zawiera się w przedziale od 0 (T_1) do max_time_slots-1 (T_m).
Ograniczenia:
C1) Podstawowe: lista par zajęć, które nie mogą być jednoczesne (na przykład A_1 i A_2, ponieważ mają tego samego nauczyciela lub tych samych uczniów);
C2) Wiele innych ograniczeń (wykluczonych tutaj dla uproszczenia).
Algorytm planowania (który nazwałem „rekurencyjną wymianą”):
Spróbuj umieścić każdą czynność (A_i) w dozwolonym przedziale czasowym, postępując zgodnie z powyższą kolejnością, pojedynczo. Wyszukaj dostępną szczelinę (T_j) dla A_i, w której można umieścić tę czynność z zachowaniem ograniczeń. Jeśli dostępnych jest więcej miejsc, wybierz losowy. Jeśli żadna nie jest dostępna, wykonaj wymianę rekurencyjną:
a . Dla każdego przedziału czasowego T_j zastanów się, co się stanie, jeśli wstawisz A_i do T_j. Pojawi się lista innych zajęć, które nie zgadzają się z tym posunięciem (na przykład działanie A_k znajduje się na tym samym polu T_j i ma tego samego nauczyciela lub tych samych uczniów co A_i). Prowadź listę kolidujących działań dla każdego przedziału czasowego T_j.
b . Wybierz boks (T_j) z najniższą liczbą kolidujących działań. Powiedzmy, że lista działań w tym slocie zawiera 3 aktywności: A_p, A_q, A_r.
c . Umieść A_i w T_j i spraw, aby A_p, A_q, A_r były nieprzydzielone.
d . Rekurencyjnie spróbuj umieścić A_p, A_q, A_r (jeśli poziom rekursji nie jest zbyt duży, powiedzmy 14, i jeśli całkowita liczba wywołań rekurencyjnych liczonych od kroku 2) na A_i rozpoczęta nie jest zbyt duża, powiedzmy 2 * n), jak w kroku 2).
e . Jeśli pomyślnie umieścisz A_p, A_q, A_r, wróć z sukcesem, w przeciwnym razie wypróbuj inne przedziały czasowe (przejdź do kroku 2 b) i wybierz następny najlepszy przedział czasowy).
f . Jeśli wszystkie (lub rozsądna liczba) przedziałów czasowych zostały bezskutecznie wypróbowane, wróć bez powodzenia.
g . Jeśli jesteśmy na poziomie 0 i nie udało nam się umieścić A_i, umieść go tak, jak w krokach 2 b) i 2 c), ale bez rekursji. Mamy teraz 3 - 1 = 2 więcej działań do umieszczenia. Przejdź do kroku 2) (tutaj zastosowano kilka metod unikania jazdy na rowerze).
UPDATE: z komentarzy ... też powinna mieć heurystykę!
Poszedłbym z Prologiem ... potem użył Rubiego lub Perla lub czegoś podobnego, aby uporządkować rozwiązanie do ładniejszej formy.
teaches(Jill,math).
teaches(Joe,history).
involves(MA101,math).
involves(SS104,history).
myHeuristic(D,A,B) :- [test_case]->D='<';D='>'.
createSchedule :- findall(Class,involves(Class,Subject),Classes),
predsort(myHeuristic,Classes,ClassesNew),
createSchedule(ClassesNew,[]).
createSchedule(Classes,Scheduled) :- [the actual recursive algorithm].
Jestem (nadal) w trakcie robienia czegoś podobnego do tego problemu, ale używam tej samej ścieżki, o której właśnie wspomniałem. Prolog (jako język funkcjonalny) naprawdę ułatwia rozwiązywanie problemów NP-Hard.
Do takiego planowania często stosuje się algorytmy genetyczne.
Znalazłem ten przykład (Tworzenie planu zajęć przy użyciu algorytmu genetycznego), który całkiem dobrze pasuje do twoich wymagań.
Oto kilka linków, które znalazłem:
Plan lekcji - zawiera listę niektórych problemów
Ten artykuł dość dobrze opisuje problem związany z planem lekcji w szkole i ich podejście do algorytmu: „ Rozwój SYLLABUS - interaktywny, oparty na ograniczeniach harmonogram dla szkół i uczelni ” [PDF]
Autor informuje mnie, że oprogramowanie SYLLABUS jest nadal używane / rozwijane tutaj: http://www.scientia.com/uk/
Pracuję na powszechnie używanym silniku planowania, który robi dokładnie to. Tak, jest to NP-Complete; Najlepsze podejścia mają na celu przybliżenie optymalnego rozwiązania. I oczywiście istnieje wiele różnych sposobów, aby powiedzieć, które z nich jest „najlepsze” - czy ważniejsze jest, aby nauczyciele byli zadowoleni ze swoich harmonogramów, czy na przykład uczniowie uczestniczyli we wszystkich swoich zajęciach?
Absolutnie najważniejszym pytaniem, które należy rozwiązać na wczesnym etapie, jest to, co sprawia, że jeden sposób planowania tego systemu jest lepszy od innego ? To znaczy, jeśli mam harmonogram z panią Jones uczącą matematyki w wieku 8 lat, a panem Smithem z nauczycielem matematyki w wieku 9 lat, czy to lepiej czy gorzej niż w przypadku, gdy oboje uczą matematyki w wieku 10 lat? Czy jest lepsze czy gorsze niż ten, w którym pani Jones uczy w wieku 8 lat, a pan Jones uczy w wieku 2 lat? Czemu?
Główną radą, jaką tutaj dałbym, jest podzielenie problemu tak bardzo, jak to tylko możliwe - może oczywiście po kursie, może nauczyciel po nauczycielu, może pokój po pokoju - i najpierw popracuj nad rozwiązaniem problemu podrzędnego. Tam powinieneś skończyć z wieloma rozwiązaniami do wyboru i wybrać jedno z najbardziej optymalnych. Następnie pracuj nad tym, aby „wcześniejsze” podproblemy uwzględniały potrzeby późniejszych podproblemów w ocenie ich potencjalnych rozwiązań. Następnie może popracuj nad tym, jak wydostać się z sytuacji wymalowanych w róg (zakładając, że nie możesz ich przewidzieć we wcześniejszych podproblemach), kiedy dojdziesz do stanu „brak ważnych rozwiązań”.
Przebieg optymalizacji wyszukiwania lokalnego jest często używany do „wypolerowania” odpowiedzi końcowej w celu uzyskania lepszych wyników.
Zauważ, że zazwyczaj mamy do czynienia z systemami o bardzo ograniczonych zasobach w planowaniu lekcji. Szkoły nie trwają przez cały rok, gdy przez 75% dnia jest dużo pustych pokoi lub nauczyciele siedzą w salonach. Podejścia, które najlepiej sprawdzają się w środowiskach bogatych w rozwiązania, niekoniecznie mają zastosowanie w planowaniu zajęć w szkole.
Ogólnie programowanie z ograniczeniami jest dobrym podejściem do tego typu problemów związanych z planowaniem. Wyszukiwanie słów „programowanie z ograniczeniami” i planowanie lub „planowanie oparte na ograniczeniach” zarówno w przypadku przepełnienia stosu, jak i w Google wygeneruje dobre odniesienia. Nie jest to niemożliwe - po prostu trochę trudno o tym pomyśleć, korzystając z tradycyjnych metod optymalizacji, takich jak optymalizacja liniowa lub całkowita. Jednym wynikiem byłoby - czy istnieje harmonogram, który spełnia wszystkie wymagania? To samo w sobie jest oczywiście pomocne.
Powodzenia !
Zaprojektowałem komercyjne algorytmy zarówno do planowania zajęć, jak i harmonogramu egzaminów. W pierwszym przypadku użyłem programowania liczb całkowitych; po drugie heurystyka oparta na maksymalizacji funkcji celu poprzez wybór zamiany miejsc, bardzo podobna do pierwotnego procesu ręcznego, który został wyewoluowany. Główną cechą akceptacji takich rozwiązań jest zdolność do reprezentowania wszystkich ograniczeń świata rzeczywistego; a ludzcy planiści nie mogli znaleźć sposobów na ulepszenie rozwiązania. Ostatecznie część algorytmiczna była dość prosta i łatwa do wdrożenia w porównaniu z przygotowaniem baz danych, interfejsem użytkownika, możliwością raportowania statystyk, takich jak wykorzystanie pokoju, edukacja użytkowników i tak dalej.
Możesz to zrobić za pomocą algorytmów genetycznych, tak. Ale nie powinieneś :). Może to być zbyt wolne, a dostrajanie parametrów może być zbyt czasochłonne itp.
Istnieją udane inne podejścia. Wszystko zaimplementowane w projektach open source:
Zobacz tutaj listę programów do planowania
Myślę, że powinieneś użyć algorytmu genetycznego, ponieważ:
Jakość rozwiązania zależy od tego, ile czasu zamierzasz poświęcić na rozwiązywanie programu.
Definicja algorytmów genetycznych
Spójrz też na: podobne pytanie i jeszcze jedno
Nie wiem, kto zgodzi się z tym kodem, ale opracowałem ten kod przy pomocy własnego algorytmu i pracuje dla mnie w języku ruby, mam nadzieję, że pomoże to tym, którzy szukają go w następującym kodzie: periodflag, dayflag subjectflag i teacherflag to hash z odpowiednim identyfikatorem i wartością flagi, która jest wartością logiczną. Jakikolwiek problem, skontaktuj się ze mną ....... (-_-)
periodflag.each do | k2, v2 |
if(TimetableDefinition.find(k2).period.to_i != 0)
subjectflag.each do |k3,v3|
if (v3 == 0)
if(getflag_period(periodflag,k2))
@teachers=EmployeesSubject.where(subject_name: @subjects.find(k3).name, division_id: division.id).pluck(:employee_id)
@teacherlists=Employee.find(@teachers)
teacherflag=Hash[teacher_flag(@teacherlists,teacherflag,flag).to_a.shuffle]
teacherflag.each do |k4,v4|
if(v4 == 0)
if(getflag_subject(subjectflag,k3))
subjectperiod=TimetableAssign.where("timetable_definition_id = ? AND subject_id = ?",k2,k3)
if subjectperiod.blank?
issubjectpresent=TimetableAssign.where("section_id = ? AND subject_id = ?",section.id,k3)
if issubjectpresent.blank?
isteacherpresent=TimetableAssign.where("section_id = ? AND employee_id = ?",section.id,k4)
if isteacherpresent.blank?
@finaltt=TimetableAssign.new
@finaltt.timetable_struct_id=@timetable_struct.id
@finaltt.employee_id=k4
@finaltt.section_id=section.id
@finaltt.standard_id=standard.id
@finaltt.division_id=division.id
@finaltt.subject_id=k3
@finaltt.timetable_definition_id=k2
@finaltt.timetable_day_id=k1
set_school_id(@finaltt,current_user)
if(@finaltt.save)
setflag_sub(subjectflag,k3,1)
setflag_period(periodflag,k2,1)
setflag_teacher(teacherflag,k4,1)
end
end
else
@subjectdetail=TimetableAssign.find_by_section_id_and_subject_id(@section.id,k3)
@finaltt=TimetableAssign.new
@finaltt.timetable_struct_id=@subjectdetail.timetable_struct_id
@finaltt.employee_id=@subjectdetail.employee_id
@finaltt.section_id=section.id
@finaltt.standard_id=standard.id
@finaltt.division_id=division.id
@finaltt.subject_id=@subjectdetail.subject_id
@finaltt.timetable_definition_id=k2
@finaltt.timetable_day_id=k1
set_school_id(@finaltt,current_user)
if(@finaltt.save)
setflag_sub(subjectflag,k3,1)
setflag_period(periodflag,k2,1)
setflag_teacher(teacherflag,k4,1)
end
end
end
end
end
end
end
end
end
end
end