Algorytm tworzenia planu lekcji

96

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

cand
źródło
2
Dzięki za wszystkie odpowiedzi. Wygląda na to, że algorytm wymaga dokładniejszego zbadania. Uznałbym to za dobry temat do pracy magisterskiej lub małego komercyjnego zastosowania. Jeśli piszę jedną dam Wiesz tutaj;)
cand
10
Jak powiedział Ian Ringrose ze StackOverflow, odpowiadając na inne pytanie, „wciąż jest wiele PHD do wykorzystania w oprogramowaniu do planowania”.
Reed Debaets

Odpowiedzi:

89

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:

  • Zdefiniowanie i uszeregowanie wszystkich znanych ograniczeń
  • Zmniejszenie przestrzeni problemowej poprzez ręczne dostarczenie zestawu dodatkowych ograniczeń.
    Może się to wydawać sprzeczne z intuicją, ale na przykład poprzez dostarczenie początkowego, częściowo wypełnionego harmonogramu (powiedzmy około 30% przedziałów czasowych) w sposób, który w pełni spełnia wszystkie ograniczenia, i uznając ten częściowy harmonogram za niezmienny, znacznie zmniejszamy czas / przestrzeń potrzebna do stworzenia potencjalnych rozwiązań.
    Innym sposobem, w jaki pomagają dodatkowe ograniczenia, jest na przykład „sztuczne” dodanie ograniczenia, które uniemożliwia nauczanie niektórych przedmiotów w niektóre dni tygodnia (jeśli jest to harmonogram tygodniowy…); tego typu ograniczenia skutkują redukcją przestrzeni problemów / rozwiązań, zazwyczaj bez wykluczania znacznej liczby dobrych kandydatów.
  • Zapewnienie szybkiego obliczenia niektórych ograniczeń problemu. Jest to często związane z wyborem modelu danych używanego do przedstawienia problemu; Chodzi o to, aby móc szybko wybrać (lub usunąć) niektóre opcje.
  • Ponowne zdefiniowanie problemu i kilkakrotne przełamanie niektórych ograniczeń (zazwyczaj w kierunku końcowych węzłów grafu). Chodzi o to, aby albo usunąć niektóre ograniczenia dotyczące zapełnienia ostatnich kilku miejsc w harmonogramie, albo zatrzymać automatyczny program generatora harmonogramów przed ukończeniem całego harmonogramu, zamiast tego dostarczając nam listę kilkunastu prawdopodobnych kandydatów. Jak wskazano, człowiek jest często w lepszej pozycji do rozwiązania łamigłówki, prawdopodobnie łamiąc kilka ograniczeń, wykorzystując informacje, które zwykle nie są udostępniane automatycznej logice (np. Zasada „Żadnej matematyki po południu” może być czasami złamana na zajęcia z „zaawansowanej matematyki i fizyki” lub „Lepiej jest złamać jedno z wymagań pana Jonesa niż jedno z pani Smith ... ;-))

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

mjv
źródło
1
Świetna, trafna i rozbudowana odpowiedź, dzięki za podpowiedzi i wzmiankę o NP-Kompletności (to też było moje przypuszczenie).
cand
3
Czy masz jakieś cytaty, które wyjaśniają NP-kompletność tego problemu?
Don
50

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:

  • nauczyciel uczy zarówno w Twojej szkole, jak iw innym instytucie. Oczywiście, jeśli kończy tam lekcję o godz. 10.30, nie może rozpocząć u Państwa o godz. 10.30, ponieważ potrzebuje trochę czasu na dojazdy między instytutami.
  • dwóch nauczycieli jest żonaty. Ogólnie uważa się, że dobrą praktyką jest nie mieć dwóch nauczycieli będących w związku małżeńskim w tej samej klasie. Dlatego ci dwaj nauczyciele muszą mieć dwie różne klasy
  • dwoje nauczycieli jest małżeństwem, a ich dziecko uczęszcza do tej samej szkoły. Ponownie, musisz uniemożliwić dwóm nauczycielom nauczanie w konkretnej klasie, w której jest ich dziecko.
  • szkoła ma oddzielne pomieszczenia, tak jak jednego dnia klasa jest w jednym instytucie, a innego dnia w innym.
  • szkoła ma wspólne laboratoria, ale są one dostępne tylko w określone dni powszednie (ze względów bezpieczeństwa, na przykład, gdy wymagany jest dodatkowy personel).
  • niektórzy nauczyciele wolą dzień wolny: niektórzy wolą poniedziałek, niektórzy w piątek, niektórzy w środę. Niektórzy wolą przyjść wcześnie rano, inni wolą przyjść później.
  • nie powinieneś mieć sytuacji, w których masz lekcję, powiedzmy, historię w pierwszej godzinie, potem trzy godziny matematyki, a potem kolejną godzinę historii. Nie ma to sensu ani dla uczniów, ani dla nauczyciela.
  • powinieneś równomiernie rozłożyć argumenty. Nie ma sensu, aby pierwsze dni tygodnia były tylko matematyką, a resztę tygodnia tylko literaturą.
  • powinieneś dać niektórym nauczycielom dwie kolejne godziny na wykonanie testów ewaluacyjnych.

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.

Stefano Borini
źródło
12
"NP-insane" - świetna nazwa;) Zgadzam się, że to naprawdę złożony problem, dziękuję za komentarze dotyczące "prawdziwego" traktowania tego problemu. Mój ojciec i moja dziewczyna też są nauczycielami i wiem, że większość szkół ma tabele z plastikowymi wstawkami - to skłoniło mnie do zastanowienia się nad możliwym algorytmem dla tego problemu - bo skoro mężczyzna może to rozwiązać, to może uda się napisać jako algorytm.
cand
10
chcesz napisać system ekspercki: system złożony z zestawu reguł heurystycznych. Pomijając systemy eksperckie, jest to dziedzina, w której algorytmy genetyczne są jednymi z najlepszych. Trudność nie polega na rozwiązaniu problemu, nie tylko. Trudność polega również na stwierdzeniu problemu i jego ograniczeń.
Stefano Borini
1
Masz rację, problem wymaga podania złożonego zestawu warunków i ograniczeń do spełnienia, prawdopodobnie z oceną rozwiązania „akceptowalnego”. Zgadzam się co do algorytmów genetycznych, powinny dobrze pasować do tego problemu, myślę również, że lepiej będzie zacząć programowanie od prostego zestawu warunków i ulepszać go, gdy uzyskamy na nie poprawną odpowiedź.
cand
1
Możesz również całkiem bezpośrednio przełożyć te ograniczenia i cele na MAXSAT. Algorytmy MAXSAT są generalnie bardziej niezawodne niż algorytmy genetyczne, ale możesz mieć eksplozję klauzul ze względu na cele, takie jak zajęcia matematyczne, które powinny być rozłożone w ciągu tygodnia.
Jules
26

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:

Geoffrey De Smet
źródło
17

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.

SF.
źródło
5
Więc otwórz go, zareklamuj i spróbuj zaangażować w to kilku naukowców? Użyć go ponownie w kolejnych projektach? Technicznie rzecz biorąc, taki program tylko dla 300 pracowników byłby warty pieniędzy dla szkół, aby stworzyć optymalne harmonogramy, i nie mają nic przeciwko spędzeniu kilku dni na genetycznym obliczeniu optymalnych harmonogramów. Pomyśl o przetwarzaniu wsadowym. Witam kontrakty na sprzęt i oprogramowanie;)
jcolebrand
1
Brzmi wspaniale! Zastanawiam się, czy można by wykonać funkcję wagi z pływakami w zakresie 0..1.
Craig McQueen,
1
@Craig: Coś tak płaskiego dałoby populację, która z czasem uległa stagnacji lub nawet zdegenerowała jakość, ponieważ losowe mutacje przyczyniły się do większej liczby negatywnych zmian niż hodowla / selekcja mogłaby zrównoważyć. Tylko bardzo stroma funkcja jakości zapewniłaby stały wzrost. Jasne, że funkcja mogłaby zostać znormalizowana, ale mimo wszystko gen „lepszy o wycięcie” musiał mieć wyższą szansę na przeżycie.
SF.
9

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

Lasse V. Karlsen
źródło
1
Cóż, argumentowałbym, że na początku raczej trudno jest poznać wszystkie ograniczenia, potrzeba doświadczenia i zbadania sprawy. Wolałabym podzielić problem na dwie osobne części i rozwijać je jednocześnie. Pierwszą będzie ogólna struktura algorytmu - mówiąca, jak powinien zapełniać "następne generowanie harmonogramu", a raczej szkic mechanizmu, bez zbytniej "logiki podmiotowej" (prawdopodobnie algorytm genetyczny). Drugi będzie dostawcą reguł z zestawem ograniczeń, które sprawdzają „poprawność” planu lekcji - na początku może być proste, a później rozszerzone.
cand
8

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ą”):

  1. Sortuj czynności, najpierw najtrudniejsze. Nie jest to krok krytyczny, ale przyspiesza algorytm może 10 razy lub więcej.
  2. 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).

Liviu Lalescu
źródło
1
FET był dla mnie bardzo przydatny. Dzięki @Liviu Lalescu!
Noel Llevares
6

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.

Reed Debaets
źródło
1
Prolog jest z pewnością świetnym językiem do wyrażania wymaganych problemów, jednak jak wskazałeś: problem JEST NP-kompletny, jeśli nie NP-trudny. Oznacza to, że Prolog może nie być wystarczająco szybki do praktycznej implementacji.
Poindexter
3
jeśli ma to coś wspólnego z NP i nie zadowoli nas przybliżenie, każdy deterministyczny algorytm będzie do niczego wykładniczo :)
Gabriel Ščerbák
1
Celem jest zatem zaimplementowanie efektywnej heurystyki ... na przykład wykonanie prostego algorytmu planowania z 9 zadaniami zajmuje 3,078 s, ale z najmniejszą zaimplementowaną heurystyką Windows First ten sam problem zajmuje tylko: 0,123 s
Reed Debaets
2
HAHA, prolog (sam) NIGDY tego nie rozwiąże. Przepraszam za wielkie litery, ale miałem ten sam pomysł 10-15 lat temu i całkowicie się nie udało. Nie żeby to było powolne, nie. Po prostu nie można rozwiązać żadnych rzeczywistych przypadków;)!
Karussell
3

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.

Tom Dibble
źródło
2

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 !

Grembo
źródło
2

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.

Permaquid
źródło
2

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:

  • Podejście oparte na ograniczeniach
    • Zaimplementowany w UniTime (raczej nie dla szkół)
    • Możesz także pójść dalej i użyć programowania typu Integer. Pomyślnie zrobione na uniwersytecie w Udine, a także na University Bayreuth (byłem tam zaangażowany) przy użyciu komercyjnego oprogramowania (ILOG CPLEX)
    • Podejście oparte na regułach z heurystyskiem - zobacz planer Drools
  • Różne heurystyki - FET i moja własna

Zobacz tutaj listę programów do planowania

Karussell
źródło
0

Myślę, że powinieneś użyć algorytmu genetycznego, ponieważ:

  • Najlepiej sprawdza się w przypadku dużych problemów.
  • Zapewnia mniejszą złożoność czasową w cenie niedokładnej odpowiedzi (nie jest to najlepsza)
  • Możesz łatwo określić ograniczenia i preferencje, dostosowując kary za przydatność dla tych, które nie zostały spełnione.
  • Możesz określić limit czasu na wykonanie programu.
  • Jakość rozwiązania zależy od tego, ile czasu zamierzasz poświęcić na rozwiązywanie programu.

    Definicja algorytmów genetycznych

    Samouczek dotyczący algorytmów genetycznych

    Projekt planowania zajęć z GA

Spójrz też na: podobne pytanie i jeszcze jedno

Betamoo
źródło
0

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
                                                @[email protected]_struct_id
                                                @[email protected]_id
                                                @finaltt.section_id=section.id
                                                @finaltt.standard_id=standard.id
                                                @finaltt.division_id=division.id
                                                @[email protected]_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

źródło