Algorytm harmonogramu/problem

Question

Jestem znudzony, a ten problem znów mnie prześladował. Po powrocie na uniwersytet zawsze zastanawiałem się, jak planują egzaminy. Możliwość zaplanowania na 10-tygodniową sesję egzaminacyjną w ciągu 2 tygodni i zagwarantowania, że ​​żaden uczeń nie zda egzaminu w dwóch kolejnych okresach. Zakładam, że zastosowana zostanie jakaś forma heurystyki.

dzisiaj jestem znudzony, a jeśli dasz mi odpowiednie narzędzia, będę pracować na nim dzisiaj i aż do weekendu

okrzyki, dassouki

EDIT 1: I Chyba byłoby założenie, że wszyscy wiemy, jest następujący:

1. liczba studentów i kursów, które oni każdy włączonych
2. Liczba miejsc w okresie badania

Answer 1

To jest znany problem z informatyką (exam scheduling problem), który znany jest pod numerem NP-hard. Możesz nie być w stanie rozwiązać go przez weekend.

Answer 2

Jest to kosztowne, ale widziałem CPLEX używane do podobnych typów problemów.

Answer 3

Jest to przykład problemu z ograniczeniem wymagań , który jest trudną klasą problemów. Niektóre z nich znajdują się w klasie NP. Istnieją duże komercyjne pakiety oprogramowania do prób rozwiązywania takich problemów (np. CPLEX) - i generalnie używają trochę matematyki i wielu heurystyk.

Answer 4

Problem może być nieco bardziej ogólny. Na przykład w mojej szkole egzaminy są zaplanowane, kiedy zajęcia są zaplanowane - tj. Wszystkie zajęcia, które spotykają się w tym samym czasie zwykle w trakcie semestru, mają egzamin zaplanowany na określony blok tygodnia egzaminacyjnego (niekoniecznie w tym samym czasie co regularne spotkanie klasowe). Konflikty na ogół nie istnieją, ponieważ uczniowie nie będą uczęszczać na dwie klasy w tym samym czasie spotkania z oczywistych powodów, a zatem nie mieliby dwóch egzaminów w tym samym czasie.

Oznacza to jednak, że należy jeszcze zaplanować klasy klasy, aby nie powodowały konfliktów. :)

Answer 5

Użyłem tabu search podczas mojego mistrza. Pomysł nie jest zbyt skomplikowana:

1. początek z jednym z możliwych rozwiązań (ktokolwiek) i tłuczek do niego (np dać -1000 punktów jeśli student ma dwa egzaminy w tym samym czasie)
2. zmianę, rozwiązanie po prostu zmieniając kilka zadań i przeliczyć ponderation
3. 2. jeśli jest lepszy niż 1. i powtórzyć zaczynając 2. jako rozwiązanie głównego

jeśli zablokowane, można „odwiedzić” inne rozwiązania, dokonując ważne zmiany w początkowym rozwiązaniu.

Answer 6

Wiem, że to nie dotyczy tematu, ale moja uczelnia po prostu zaplanowała egzaminy w blokach, które pasowały do ​​godzin lekcyjnych. Tak więc wszyscy, którzy mieli MWF klasy o 13:20, byli na egzaminie 15 dnia o 13:00. Ponieważ nie możesz wziąć dwóch klas jednocześnie, nie można było mieć konfliktów z egzaminami.

Answer 7

Kiedy byłem starszym kolegium, zrobiliśmy ostateczny projekt w naszej klasie AI podobnej do tej. Napisaliśmy (ledwo) działający system, aby zaplanować zajęcia w budynkach w odpowiednim czasie. Nie można pogwałcić niektórych zasad: jeżeli prof. potrzebował klasy multimedialnej, dostał jedną. Jeśli była to klasa CS, to nie powinna być zaplanowana w budynku Sztuka. Profesi nie mają więcej niż 2 godziny między zajęciami, itd.

Użyliśmy algorytmu genetycznego.

Answer 8

Kilka rzeczy, które sprawiają, że problem jest prostszy. Prawdopodobnie możesz zmniejszyć liczbę "jednostek do harmonogramu" z kilkudziesięciu tysięcy do kilkuset, patrząc na osoby, które mają taki sam zestaw egzaminów. Jeśli masz 300 osób, które wszyscy siedzą "Wprowadzenie do informatyki" i "Matematyka dla uczniów CS", możesz zaplanować wszystkie 300 jako pojedynczą jednostkę, ponieważ wszystkie będą miały te same ograniczenia i prawdopodobnie (nie) będziesz chciał tego samego egzaminy, które należy zdawać w wielu automatach.

Answer 9

Drools Planner ma przykład planowania egzaminu (zwany egzaminem, patrz podręcznik pobierania i odniesienia). Problem jest określony w the ITC2007 competition track 1.

Answer 10

To jest aplikacja graph coloring problem. Ten problem można przedstawić jako wykres, w którym każdy wierzchołek jest kursem, a krawędź między dwoma wierzchołkami oznacza, że ​​istnieje wspólny uczeń zapisany na oba kursy. Jest to więc problem z kolorowaniem wykresu, w którym minimalna liczba szczelin czasowych jest równa minimalnej liczbie kolorów wymaganych do barwienia wierzchołków wykresu w taki sposób, że żadne dwa sąsiednie wierzchołki nie mają tego samego koloru.