Scheduling-Algorithmus/problem
Ich bin gelangweilt und dieses problem nur mich heimgesucht wieder. Zurück an der Universität, ich Frage mich immer, wie Sie planen Prüfungen. Die Fähigkeit zu planen, 10k Schüler Prüfungen in 2 Wochen und garantieren, dass kein Schüler eine Prüfung in zwei aufeinander folgenden Perioden. Ich gehe davon aus, dass irgendeine form von Heuristiken angewendet werden.
Mir ist langweilig heute Abend, und wenn du mir die richtigen Werkzeuge, ich werde es auf Arbeit heute Abend und bis zum Wochenende
cheers,
dassouki
EDIT 1:
Ich denke, die Annahme wäre, dass alles, was wir wissen, ist die folgende:
- Zahl der Studenten und die Kurse, Sie sind alle eingeschrieben in
- Anzahl der Prüfungszeit spots
- Wenn Sie es tatsächlich tun, dass die Dinge sich geändert haben, seit ich das college besucht-ich hatte auf jeden Fall einige Prüfungen während der aufeinander folgenden Perioden.
- Ich fürchte, es ist noch von hand gemacht, in der überwiegenden Mehrzahl der Fälle. Es ist nicht wie die zehn tausend Studenten haben jeweils ein völlig anderes set von Prüfungen, richtig? Es gibt wahrscheinlich ein paar Dutzend 'Examen Gruppen mit jeweils bis zu ein paar hundert Studenten in der it. Es sollte nicht sein, dass viel von einem problem, zu planen, mit der hand, wenn Sie genug Platz haben.
- Ich ging auf das college vor wenigen Jahren. Obwohl alle unsere scheduling-Systeme wurden elektronische, die Beweislast war auf der hin-und hergerissene Schüler zu lösen widersprüchliche geplanten Zeiten und finden Sie ein administrator neu einplanen. Das system hatte keine Zeitplanung eigene Intelligenz.
- Ich vermutete immer, dass Sie planen 'Ergänzende' - Kurse, so dass Sie nicht in Konflikt. Das heißt, dass ein zweites EE wichtigsten ist wahrscheinlich die Einnahme von beiden 'Elemente der EE" und "Signale & Systeme", so würden Sie nicht planen, Sie zusammen. Obwohl, es wäre sicher zu planen "Signale II' Konflikt, weil ein Neuling würde niemals nehmen. Es ist die Wahlfächer, die Schraube Dinge (und wo Sie in der Regel musste umplanen, eine Prüfung).
Schreibe einen Kommentar
Du musst angemeldet sein, um einen Kommentar abzugeben.
Dies ist der berühmte informatik-problem (die exam scheduling problem), die bekannt ist,NP-schwer. Sie möglicherweise nicht in der Lage, es zu lösen, über ein Wochenende.
Ich weiß, das ist off-topic SO, aber meine Uni einfach geplant die Prüfungen in Blöcken, die aufeinander abgestimmt den Klasse Zeiten. Also, jeder, der hatte eine Klasse MWF bei 1:20 Uhr wurde in einer Klausur am 15. um 1:00 Uhr. Da kann man nicht zwei Klassen zur gleichen Zeit, es war unmöglich, Prüfung von Konflikten.
Dies ist ein Beispiel für eine constraint satisfaction problem, das ist eine schwierige Klasse von Problemen. Einige von Ihnen sind in der Klasse NP. Große kommerzielle software-Pakete gibt es für den Versuch, Probleme zu lösen, wie diese (z.B. CPLEX) - und im Allgemeinen, verwenden Sie einige Mathematik-und viele Heuristiken.
Es ist teuer, aber ich habe gesehen, CPLEX verwendet für ähnliche Arten von Problemen.
Kann das problem tatsächlich ein bisschen mehr Allgemeine als das. Zum Beispiel an meiner Schule, die Prüfungen sind geplant, wenn die Klasse geplant ist - also alle Klassen treffen sich in der gleichen Zeit, die normalerweise während des Semesters, eine Prüfung geplant in einem bestimmten block der die Prüfung in der Woche (nicht unbedingt zur gleichen Zeit wie die reguläre Klasse treffen, jedoch). So werden Konflikte in der Regel nicht vorhanden, da die Schüler wäre nicht die Teilnahme an zwei Klassen in der gleichen Sitzung Zeit, aus offensichtlichen Gründen, und damit würde nicht zwei Prüfungen zur gleichen Zeit.
Dies bedeutet jedoch, dass man dann noch planen müssen Klassen, so dass Sie nicht im Konflikt. 🙂
Benutzte ich die tabu search in meinem master. Die Idee ist nicht allzu kompliziert:
wenn Sie sind blockiert, Sie können "Besuch" von anderen Lösungen, indem Sie wichtige änderungen an der ursprünglichen Lösung.
Wenn ich war ein senior im college war, hatten wir ein fertiges Projekt in unserem AI-Klasse ähnelt. Wir schrieben ein (fast) funktionierendes system zu planen Klassen im Gebäude zu entsprechenden Zeiten. Bestimmte Regeln könnten nicht verletzt werden: wenn der prof. benötigt wird ein multimedia-Klassenzimmer, er hat eins. Wenn es eine CS-Klasse, dann sollte es nicht so angesetzt werden, dass die Kunst am Bau. Profs shoulnd nicht mehr als 2 Stunden zwischen einer Klasse, etc.
Wir mit einem genetischen Algorithmus.
Ein paar Dinge zu machen, das problem einfacher. Sie können sich wahrscheinlich schrumpfen, die Anzahl der "Einheiten zu planen" unten von zig tausend auf ein paar hundert, mit Blick auf die Menschen, die sitzen den gleichen Satz von Prüfungen. Wenn Sie haben 300 Menschen, die alle sitzen "Einführung in die informatik" und "Mathematik für informatik-Studierende", Sie können planen, alle 300 als eine einzige Einheit, weil Sie alle den gleichen Einschränkungen und Sie (vermutlich) nicht wollen, identische Prüfungen werden in mehreren slots.
Drools Planner hat eine Prüfung scheduling-Beispiel (genannt-Prüfung, siehe download-und Referenz-Handbuch). Das problem ist angegeben in die ITC2007 Wettbewerb track 1.
Dies ist eine Anwendung der graph coloring problem. Dieses problem kann dargestellt werden als ein graph, wo jeder Knoten einen Kurs und eine Kante zwischen zwei Knoten bedeutet, dass es ist eine gemeinsame Studierenden in beiden Studiengängen. Das ist also ein graph coloring problem wo minimale Anzahl von Zeitschlitzen ist gleich der minimalen Anzahl von Farben benötigt, für die Färbung der Knoten des Graphen so, daß keine zwei benachbarten vertices teilen sich die gleiche Farbe.