Algorithmus zur Erstellung eines Stundenplans

95

Ich habe mich gefragt, ob es bekannte Lösungen für Algorithmen zur Erstellung eines Stundenplans gibt. Grundsätzlich geht es darum, die "Stundenverteilung" (sowohl bei Lehrern als auch bei Klassen) für bestimmte Klassen-Fach-Lehrer-Vereinigungen zu optimieren. Wir können davon ausgehen, dass Klassen, Unterrichtsfächer und Lehrer am Eingang miteinander verbunden sind und dass der Stundenplan zwischen 8.00 und 16.00 Uhr liegen sollte.

Ich denke, dass es dafür wahrscheinlich keinen genauen Algorithmus gibt, aber vielleicht kennt jemand eine gute Annäherung oder Hinweise für die Entwicklung.

algorithm language-agnostic np cand
quelle
2
Danke für alle Antworten. Es sieht so aus, als ob der Algorithmus weitere Untersuchungen erfordert. Ich würde es als ein gutes Fach für Masterarbeiten oder kleine kommerzielle Anwendungen betrachten. Wenn ich eine schreibe, werde ich dich hier informieren;)
Cand
10
Wie Ian Ringrose von StackOverflow zu einer anderen Frage sagte: "Es gibt immer noch viele Doktoranden in der Planungssoftware."
Reed Debaets

Antworten:

84

Dieses Problem ist NP-vollständig !
Kurz gesagt, man muss alle möglichen Kombinationen untersuchen, um die Liste akzeptabler Lösungen zu finden. Aufgrund der unterschiedlichen Umstände, unter denen das Problem an verschiedenen Schulen auftritt (z. B.: Gibt es Einschränkungen in Bezug auf Klassenräume? Sind einige Klassen manchmal in Untergruppen aufgeteilt? Ist dies ein wöchentlicher Zeitplan? usw.) Es gibt keine bekannte Problemklasse, die allen Planungsproblemen entspricht. Vielleicht hat das Rucksackproblem viele Ähnlichkeitselemente mit diesen Problemen insgesamt.

Eine Bestätigung, dass dies sowohl ein schwieriges Problem ist als auch eines, für das ständig nach einer Lösung gesucht wird, besteht darin, diese (lange) Liste von (meist kommerziellen) Software-Planungstools zu überprüfen

Aufgrund der großen Anzahl der beteiligten Variablen, deren größte Quelle typischerweise die Wünsche des Fakultätsmitglieds sind; -) ..., ist es normalerweise unpraktisch, die Aufzählung aller möglichen Kombinationen in Betracht zu ziehen . Stattdessen müssen wir einen Ansatz wählen, der eine Teilmenge der Problem- / Lösungsräume besucht.
- Genetische Algorithmen , die in einer anderen Antwort zitiert werden, sind (oder scheinen meiner Meinung nach) gut gerüstet, um diese Art der halbgeführten Suche durchzuführen (das Problem besteht darin, eine gute Bewertungsfunktion für die Kandidaten zu finden, die für die nächste Generation aufbewahrt werden sollen)
- Grafik Rewriting- Ansätze sind auch bei dieser Art von kombinatorischen Optimierungsproblemen von Nutzen.

Anstatt mich auf bestimmte Implementierungen eines automatischen Zeitplangenerierungsprogramms zu konzentrieren, möchte ich einige Strategien vorschlagen , die auf der Ebene der Definition des Problems angewendet werden können .
Das allgemeine Grundprinzip ist, dass bei den meisten realen Planungsproblemen einige Kompromisse erforderlich sind, nicht alle Einschränkungen, ausgedrückt und impliziert: vollständig erfüllt werden. Deshalb helfen wir uns durch:

  • Definieren und Ordnen aller bekannten Einschränkungen
  • Reduzieren des Problemraums durch manuelles Bereitstellen einer Reihe zusätzlicher Einschränkungen.
    Dies mag kontraintuitiv erscheinen, aber zum Beispiel, indem wir einen anfänglichen, teilweise gefüllten Zeitplan (etwa 30% der Zeitfenster) so bereitstellen, dass alle Einschränkungen vollständig erfüllt werden, und indem wir diesen Teilplan als unveränderlich betrachten, reduzieren wir den Zeit / Raum für die Erstellung von Kandidatenlösungen.
    Eine andere Möglichkeit, zusätzliche Einschränkungen zu unterstützen, besteht beispielsweise darin, "künstlich" eine Einschränkung hinzuzufügen, die das Unterrichten einiger Fächer an bestimmten Wochentagen verhindert (wenn dies ein wöchentlicher Zeitplan ist ...). Diese Art von Einschränkungen führt zu einer Reduzierung der Problem- / Lösungsräume, ohne dass typischerweise eine signifikante Anzahl guter Kandidaten ausgeschlossen wird.
  • Sicherstellen, dass einige der Einschränkungen des Problems schnell berechnet werden können. Dies hängt häufig mit der Wahl des Datenmodells zusammen, das zur Darstellung des Problems verwendet wird. Die Idee ist, einige der Optionen schnell auswählen (oder ausschneiden) zu können.
  • Definieren Sie das Problem neu und lassen Sie einige der Einschränkungen einige Male aufheben (normalerweise in Richtung der Endknoten des Diagramms). Hier geht es darum, entweder einige Einschränkungen für das Ausfüllen der letzten Zeitnischen im Zeitplan zu beseitigen oder das Programm zur automatischen Erstellung von Zeitplänen zu stoppen, um den gesamten Zeitplan nicht mehr zu vervollständigen, und uns stattdessen eine Liste von etwa einem Dutzend plausiblen Elementen zur Verfügung zu stellen Kandidaten. Ein Mensch ist oft in einer besseren Position, um das Rätsel zu lösen, wie angegeben, und möglicherweise einige der Einschränkungen zu brechen, indem er Informationen verwendet, die normalerweise nicht mit der automatisierten Logik geteilt werden (z. B. kann die Regel "Keine Mathematik am Nachmittag" gelegentlich gebrochen werden für die Klasse "Fortgeschrittene Mathematik und Physik" oder "Es ist besser, eine der Anforderungen von Herrn Jones zu brechen als eine von Frau Smith ... ;-))

Beim Korrekturlesen dieser Antwort stelle ich fest, dass es ziemlich schüchtern ist, eine eindeutige Antwort zu geben, aber dennoch voller praktischer Vorschläge. Ich hoffe diese Hilfe, was schließlich ein "hartes Problem" ist.

mjv
quelle
1
Tolle, genaue und ausführliche Antwort, danke für die Hinweise und die Erwähnung der NP-Vollständigkeit (das war auch meine Vermutung).
Cand
3
Haben Sie ein Zitat, das die NP-Vollständigkeit dieses Problems erklärt?
Don
49

Es ist ein Chaos. ein königliches Durcheinander. Um die bereits sehr vollständigen Antworten zu ergänzen, möchte ich auf meine Familienerfahrung hinweisen. Meine Mutter war Lehrerin und war früher in den Prozess involviert.

Es stellt sich heraus, dass es nicht nur schwierig ist, einen Computer an sich zu haben, sondern auch schwierig, weil es Bedingungen gibt, die für ein vorgebackenes Computerprogramm schwer zu spezifizieren sind. Beispiele:

  • Ein Lehrer unterrichtet sowohl an Ihrer Schule als auch an einem anderen Institut. Wenn er den Unterricht dort um 10.30 Uhr beendet, kann er natürlich nicht um 10.30 Uhr in Ihrem Haus beginnen, da er einige Zeit benötigt, um zwischen den Instituten zu pendeln.
  • Zwei Lehrer sind verheiratet. Im Allgemeinen wird es als gute Praxis angesehen, nicht zwei verheiratete Lehrer in derselben Klasse zu haben. Diese beiden Lehrer müssen daher zwei verschiedene Klassen haben
  • Zwei Lehrer sind verheiratet und ihr Kind besucht dieselbe Schule. Auch hier müssen Sie verhindern, dass die beiden Lehrer in der Klasse unterrichten, in der sich ihr Kind befindet.
  • Die Schule verfügt über separate Einrichtungen, z. B. an einem Tag befindet sich die Klasse in einem Institut und an einem anderen Tag befindet sich die Klasse in einem anderen.
  • Die Schule verfügt über gemeinsame Labors. Diese Labors sind jedoch nur an bestimmten Wochentagen verfügbar (aus Sicherheitsgründen, z. B. wenn zusätzliches Personal erforderlich ist).
  • Einige Lehrer bevorzugen den freien Tag: andere bevorzugen Montag, andere Freitag, andere Mittwoch. Einige kommen lieber früh am Morgen, andere lieber später.
  • Sie sollten keine Situationen haben, in denen Sie eine Lektion in Geschichte haben, Geschichte in der ersten Stunde, dann drei Stunden Mathematik, dann eine weitere Stunde Geschichte. Es macht weder für die Schüler noch für den Lehrer Sinn.
  • Sie sollten die Argumente gleichmäßig verteilen. Es ist nicht sinnvoll, an den ersten Tagen der Woche nur Mathematik und dann den Rest der Woche nur Literatur zu haben.
  • Sie sollten einigen Lehrern zwei aufeinanderfolgende Stunden Zeit geben, um Bewertungstests durchzuführen.

Wie Sie sehen können, ist das Problem nicht NP-vollständig, sondern NP-verrückt.

Sie haben also einen großen Tisch mit kleinen Kunststoffeinsätzen und bewegen die Einsätze, bis ein zufriedenstellendes Ergebnis erzielt wird. Sie beginnen nie bei Null: Sie beginnen normalerweise mit dem Zeitplan des Vorjahres und nehmen Anpassungen vor.

Stefano Borini
quelle
12
"NP-wahnsinnig" - großer Name;) Ich stimme zu, dass es ein wirklich komplexes Problem ist, danke für Kommentare zur "realen" Behandlung dieses Problems. Mein Vater und meine Freundin sind ebenfalls Lehrer, und ich weiß, dass die meisten Schulen Tische mit Plastikeinsätzen haben - das hat mich dazu gebracht, über einen möglichen Algorithmus für dieses Problem nachzudenken -, denn wenn ein Mann es lösen kann, kann er vielleicht schreiben es unten als Algorithmus.
Cand
10
Was Sie schreiben möchten, ist ein Expertensystem: ein System, das aus einer Reihe heuristischer Regeln besteht. Abgesehen von Expertensystemen ist dies ein Bereich, in dem genetische Algorithmen zu den besten Wetten gehören. Die Schwierigkeit liegt nicht nur in der Lösung des Problems. Die Schwierigkeit liegt auch darin, das Problem und seine Einschränkungen darzulegen.
Stefano Borini
1
Sie haben Recht, das Problem erfordert die Bereitstellung komplexer Bedingungen und Einschränkungen, wahrscheinlich mit der Bewertung "akzeptable" Lösung. Ich stimme genetischen Algorithmen zu, sie sollten gut zu diesem Problem passen. Ich denke auch, dass es besser ist, mit einfachen Bedingungen zu beginnen und sie zu verbessern, wenn die richtige Antwort für sie erhalten wird.
Cand
1
Sie können diese Einschränkungen und Ziele auch ziemlich direkt in MAXSAT übersetzen. MAXSAT-Algorithmen sind im Allgemeinen zuverlässiger als genetische Algorithmen, aber es kann zu einer Klauselexplosion kommen, da Ziele wie der Mathematikunterricht über die Woche verteilt sein sollten.
Jules
26

Der Internationale Stundenplanwettbewerb 2007 hatte eine Unterrichtsplanung und eine Prüfungsplanung. Viele Forscher nahmen an diesem Wettbewerb teil. Viele Heuristiken und Metaheuristiken wurden ausprobiert, aber am Ende haben die lokalen Suchmetaheuristiken (wie Tabu Search und Simulated Annealing) andere Algorithmen (wie genetische Algorithmen) deutlich übertroffen.

Schauen Sie sich die 2 Open Source Frameworks an, die von einigen der Finalisten verwendet werden:

Geoffrey De Smet
quelle
17

Eine meiner Aufgaben in der Halbzeit war die Generierung einer Schultabelle mit genetischen Algorithmen.

Der ganze Tisch ist ein "Organismus". Es gab einige Änderungen und Vorbehalte beim Ansatz der generischen genetischen Algorithmen:

  • Es wurden Regeln für "illegale Tische" aufgestellt: zwei Klassen im selben Klassenzimmer, ein Lehrer, der zwei Gruppen gleichzeitig unterrichtet usw. Diese Mutationen wurden sofort als tödlich angesehen und ein neuer "Organismus" wurde sofort anstelle des "Verstorbenen" gekeimt. Der erste wurde durch eine Reihe von zufälligen Versuchen generiert, einen legalen (wenn auch sinnlosen) zu erhalten. Die tödliche Mutation wurde nicht zur Anzahl der Mutationen in der Iteration gezählt.

  • "Exchange" -Mutationen waren viel häufiger als "Modify" -Mutationen. Änderungen waren nur zwischen Teilen des Gens sinnvoll - kein Ersetzen eines Lehrers durch ein Klassenzimmer.

  • Es wurden kleine Prämien vergeben, um bestimmte 2 Stunden zusammen zu bündeln, dasselbe allgemeine Klassenzimmer nacheinander für dieselbe Gruppe zuzuweisen, um die Arbeitszeit des Lehrers und die Klassenbelastung kontinuierlich zu halten. Es wurden moderate Boni für die Bereitstellung korrekter Klassenzimmer für ein bestimmtes Fach, die Einhaltung der Unterrichtsstunden innerhalb der Anleihen (morgens oder nachmittags) und dergleichen vergeben. Große Boni waren für die Zuweisung der richtigen Anzahl von Fächern, die Arbeitsbelastung für einen Lehrer usw.

  • Die Lehrer könnten ihre Arbeitslastpläne erstellen: "Dann arbeiten wollen", "Dann arbeiten", "Dann nicht arbeiten", "Dann nicht arbeiten", wobei die richtigen Gewichte zugewiesen werden. Ganze 24 Stunden waren legale Arbeitszeiten, außer dass die Nacht sehr unerwünscht war.

  • Die Gewichtsfunktion ... oh ja. Die Gewichtsfunktion war ein riesiges, monströses Produkt (wie bei der Multiplikation) von Gewichten, die ausgewählten Merkmalen und Eigenschaften zugewiesen wurden. Es war extrem steil, eine Eigenschaft konnte es leicht um eine Größenordnung nach oben oder unten ändern - und es gab Hunderte oder Tausende von Eigenschaften in einem Organismus. Dies führte zu absolut RIESIGEN Zahlen als Gewichte und als direktes Ergebnis muss eine Bignum-Bibliothek (gmp) verwendet werden, um die Berechnungen durchzuführen. Für einen kleinen Testfall mit etwa 10 Gruppen, 10 Lehrern und 10 Klassenzimmern begann der erste Satz mit einer Note von 10 ^ -200 etwas und endete mit 10 ^ + 300 etwas. Es war völlig ineffizient, wenn es flacher war. Außerdem wuchsen die Werte mit größeren "Schulen" viel weiter.

  • In Bezug auf die Rechenzeit gab es kaum einen Unterschied zwischen einer kleinen Bevölkerung (100) über einen langen Zeitraum und einer großen Bevölkerung (10.000 +) über weniger Generationen. Die Berechnung über die gleiche Zeit ergab ungefähr die gleiche Qualität.

  • Die Berechnung (auf einer 1-GHz-CPU) würde ungefähr 1 Stunde dauern, um sich in der Nähe von 10 ^ + 300 zu stabilisieren, wodurch Zeitpläne generiert würden, die für diesen 10x10x10-Testfall recht gut aussahen.

  • Das Problem kann leicht paralelliert werden, indem eine Netzwerkfunktion bereitgestellt wird, die die besten Proben zwischen Computern austauscht, auf denen die Berechnung ausgeführt wird.

Das resultierende Programm sah nie Tageslicht draußen und brachte mir eine gute Note für das Semester. Es war vielversprechend, aber ich hatte nie genug Motivation, eine grafische Benutzeroberfläche hinzuzufügen und sie für die breite Öffentlichkeit nutzbar zu machen.

SF.
quelle
5
Also öffnen Sie es und machen Sie Werbung dafür und versuchen Sie, einige Akademiker dazu zu bringen? Für weitere Projekte wiederverwenden? Technisch gesehen wäre ein solches Programm für 300 Mitarbeiter allein für Schulen Geld wert, um optimale Stundenpläne zu erstellen, und es macht ihnen nichts aus, ein paar Tage damit zu verbringen, optimale Stundenpläne genetisch zu berechnen. Denken Sie an die Stapelverarbeitung. Hallo Hardware- und Softwareverträge;)
jcolebrand
1
Klingt gut! Ich frage mich, ob die Gewichtsfunktion mit Schwimmern im Bereich 0..1 durchgeführt werden könnte.
Craig McQueen
1
@Craig: Etwas, das flach ist, würde eine Population ergeben, deren Qualität im Laufe der Zeit stagnierte oder sogar degenerierte, da zufällige Mutationen mehr negative Veränderungen beisteuerten, als Zucht / Selektion ausgleichen konnten. Nur eine extrem steile Qualitätsfunktion würde ein stetiges Wachstum ergeben. Sicher, die Funktion könnte normalisiert werden, aber dennoch musste ein "Notch Better" -Gen eine um eine höhere Überlebenschance haben.
SF.
9

Dieses Problem ist schwieriger als es scheint.

Wie andere angedeutet haben, ist dies ein NP-vollständiges Problem, aber analysieren wir, was das bedeutet.

Grundsätzlich bedeutet dies, dass Sie alle möglichen Kombinationen prüfen müssen.

Aber "gucken" sagt dir nicht viel, was du tun musst.

Das Generieren aller möglichen Kombinationen ist einfach. Es kann eine große Datenmenge erzeugen, aber Sie sollten keine großen Probleme haben, die Konzepte dieses Teils des Problems zu verstehen.

Das zweite Problem besteht darin, zu beurteilen, ob eine bestimmte mögliche Kombination gut, schlecht oder besser ist als die vorherige "gute" Lösung.

Dafür brauchen Sie mehr als nur "ist es eine mögliche Lösung".

Arbeitet zum Beispiel derselbe Lehrer 5 Wochen lang 5 Tage die Woche? Selbst wenn dies eine funktionierende Lösung ist, ist es möglicherweise keine bessere Lösung, als zwischen zwei Personen zu wechseln, sodass jeder Lehrer jeweils eine Woche lang arbeitet. Oh, darüber hast du nicht nachgedacht? Denken Sie daran, dass es sich um Personen handelt, mit denen Sie zu tun haben, und nicht nur um ein Problem bei der Ressourcenzuweisung.

Selbst wenn ein Lehrer 16 Wochen lang Vollzeit arbeiten könnte, könnte dies eine suboptimale Lösung sein, verglichen mit einer Lösung, bei der Sie versuchen, zwischen Lehrern zu wechseln, und diese Art des Ausgleichs ist sehr schwer in Software zu integrieren.

Zusammenfassend lässt sich sagen, dass es für viele, viele Menschen viel wert ist, eine gute Lösung für dieses Problem zu finden. Daher ist es kein leichtes Problem, es zu lösen und zu lösen. Seien Sie bereit, einige Ziele abzustecken, die nicht 100% sind, und nennen Sie sie "gut genug".

Lasse V. Karlsen
quelle
1
Nun, ich würde argumentieren, dass es ziemlich schwierig ist, alle Einschränkungen am Anfang zu kennen, es erfordert Erfahrung und Untersuchung der Angelegenheit. Ich würde das Problem lieber in zwei separate Teile teilen und sie gleichzeitig entwickeln. Zunächst wird die allgemeine Algorithmusstruktur beschrieben, in der angegeben wird, wie die "nächste Zeitplangenerierung", eher der Entwurf eines Mechanismus, ohne zu viel "Subjektlogik" (wahrscheinlich genetischer Algorithmus) ausgefüllt werden soll. Der zweite wird ein Regelanbieter mit einer Reihe von Einschränkungen sein, die die "Richtigkeit" des Zeitplans überprüfen - er kann zunächst einfach sein und später erweitert werden.
Cand
8

Mein in FET implementierter Zeitplanalgorithmus (Free Timetabling Software, http://lalescu.ro/liviu/fet/ , eine erfolgreiche Anwendung):

Der Algorithmus ist heuristisch. Ich nannte es "rekursives Tauschen".

Eingabe: eine Reihe von Aktivitäten A_1 ... A_n und die Einschränkungen.

Ausgabe: eine Reihe von Zeiten TA_1 ... TA_n (das Zeitfenster jeder Aktivität. Räume sind hier der Einfachheit halber ausgeschlossen). Der Algorithmus muss jede Aktivität unter Berücksichtigung der Einschränkungen in einen Zeitschlitz versetzen. Jedes TA_i liegt zwischen 0 (T_1) und max_time_slots-1 (T_m).

Einschränkungen:

C1) Grundlegend: eine Liste von Aktivitätspaaren, die nicht gleichzeitig ausgeführt werden können (z. B. A_1 und A_2, weil sie denselben Lehrer oder dieselben Schüler haben);

C2) Viele andere Einschränkungen (der Einfachheit halber hier ausgeschlossen).

Der Zeitplanalgorithmus (den ich "rekursives Austauschen" nannte):

  1. Aktivitäten sortieren, am schwierigsten zuerst. Kein kritischer Schritt, beschleunigt den Algorithmus jedoch möglicherweise um das 10-fache oder mehr.

  2. Versuchen Sie, jede Aktivität (A_i) nacheinander in einem zulässigen Zeitfenster in der oben angegebenen Reihenfolge zu platzieren. Suchen Sie nach einem verfügbaren Slot (T_j) für A_i, in dem diese Aktivität unter Berücksichtigung der Einschränkungen platziert werden kann. Wenn mehr Slots verfügbar sind, wählen Sie einen zufälligen. Wenn keine verfügbar ist, führen Sie einen rekursiven Austausch durch:

    a . Überlegen Sie für jedes Zeitfenster T_j, was passiert, wenn Sie A_i in T_j einfügen. Es wird eine Liste anderer Aktivitäten geben, die mit diesem Schritt nicht übereinstimmen (z. B. befindet sich Aktivität A_k auf demselben Steckplatz T_j und hat denselben Lehrer oder dieselben Schüler wie A_i). Führen Sie für jedes Zeitfenster T_j eine Liste widersprüchlicher Aktivitäten.

    b . Wählen Sie einen Steckplatz (T_j) mit der geringsten Anzahl widersprüchlicher Aktivitäten. Angenommen, die Liste der Aktivitäten in diesem Slot enthält 3 Aktivitäten: A_p, A_q, A_r.

    c . Platziere A_i bei T_j und mache A_p, A_q, A_r nicht zugeordnet.

    d . Versuchen Sie rekursiv, A_p, A_q, A_r (wenn die Rekursionsstufe nicht zu groß ist, sagen wir 14, und wenn die Gesamtzahl der seit Schritt 2 gezählten rekursiven Aufrufe seit Schritt 2 zählt) nicht zu groß auf A_i zu setzen, sagen wir 2 * n). wie in Schritt 2).

    e . Wenn A_p, A_q, A_r erfolgreich platziert wurden, kehren Sie mit Erfolg zurück. Andernfalls versuchen Sie es mit anderen Zeitfenstern (fahren Sie mit Schritt 2 b fort) und wählen Sie das nächstbeste Zeitfenster aus.

    f . Wenn alle (oder eine angemessene Anzahl) Zeitfenster nicht erfolgreich ausprobiert wurden, kehren Sie ohne Erfolg zurück.

    g . Wenn wir uns auf Stufe 0 befinden und A_i nicht erfolgreich platziert wurde, platzieren Sie es wie in Schritt 2 b) und 2 c), jedoch ohne Rekursion. Wir haben jetzt 3 - 1 = 2 weitere Aktivitäten zu platzieren. Weiter mit Schritt 2) (hier werden einige Methoden zur Vermeidung des Radfahrens angewendet).

Liviu Lalescu
quelle
1
FET war für mich sehr nützlich. Danke @Liviu Lalescu!
Noel Llevares
6

UPDATE: aus Kommentaren ... sollte auch Heuristiken haben!

Ich würde mit Prolog gehen ... dann Ruby oder Perl oder etwas anderes verwenden, um Ihre Lösung in eine schönere Form zu bringen.

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

Ich bin (noch) dabei, etwas Ähnliches wie dieses Problem zu tun, aber den gleichen Weg zu verwenden, den ich gerade erwähnt habe. Prolog (als funktionale Sprache) erleichtert die Lösung von NP-Hard-Problemen wirklich.

Reed Debaets
quelle
1
Prolog ist sicherlich eine großartige Sprache, um die erforderlichen Probleme auszudrücken, aber wie Sie hervorheben: Das Problem ist NP-vollständig, wenn nicht NP-schwer. Dies bedeutet, dass Prolog für eine praktische Implementierung möglicherweise nicht schnell genug ist.
Poindexter
3
Wenn es irgendetwas mit NP zu tun hat und wir nicht durch Annäherung zufrieden sind, wird jeder deterministische Algorithmus exponentiell saugen :)
Gabriel Ščerbák
1
Das Ziel ist es dann, effektive Heuristiken zu implementieren ... zum Beispiel dauert ein einfacher 9-Task-Planungsalgorithmus 3.078s, aber mit einer kleinsten implementierten WindowsFirst-Heuristik dauert das gleiche Problem nur: 0.123s
Reed Debaets
2
HAHA, Prolog (alleine) wird das NIEMALS LÖSEN. Entschuldigung für die Großbuchstaben, aber ich hatte vor 10 oder 15 Jahren die gleiche Idee und bin total gescheitert. Nicht dass es langsam gewesen wäre, nein. Es konnte einfach keine realen Fälle lösen;)!
Karussell
3

Ich arbeite an einer weit verbreiteten Scheduling-Engine, die genau dies tut. Ja, es ist NP-vollständig; Die besten Ansätze zielen darauf ab, eine optimale Lösung zu finden. Und natürlich gibt es viele verschiedene Möglichkeiten zu sagen, welche die "beste" Lösung ist - ist es wichtiger, dass Ihre Lehrer mit ihren Stundenplänen zufrieden sind oder dass die Schüler beispielsweise in alle Klassen einsteigen?

Die absolut wichtigste Frage, die Sie frühzeitig lösen müssen, ist, was eine Möglichkeit zur Planung dieses Systems besser macht als eine andere . Das heißt, wenn ich einen Zeitplan habe, in dem Frau Jones mit 8 Mathematik unterrichtet und Herr Smith mit 9 Mathematik unterrichtet, ist das besser oder schlechter als einer, wenn beide mit 10 Mathematik unterrichten? Ist es besser oder schlechter als eins, wenn Frau Jones um 8 Uhr und Herr Jones um 2 Uhr unterrichtet? Warum?

Der wichtigste Rat, den ich hier geben würde, ist, das Problem so weit wie möglich aufzuteilen - vielleicht Kurs für Kurs, vielleicht Lehrer für Lehrer, vielleicht Raum für Raum - und zuerst daran zu arbeiten, das Unterproblem zu lösen. Dort sollten Sie mehrere Lösungen zur Auswahl haben und eine als wahrscheinlichstes Optimum auswählen müssen. Arbeiten Sie dann daran, die "früheren" Unterprobleme so zu gestalten, dass die Bedürfnisse späterer Unterprobleme bei der Bewertung ihrer möglichen Lösungen berücksichtigt werden. Arbeiten Sie dann vielleicht daran, wie Sie aus Situationen herauskommen können, in denen Sie in früheren Unterproblemen nicht vorhersehen können, wenn Sie den Status "Keine gültigen Lösungen" erhalten.

Ein Optimierungsdurchlauf für die lokale Suche wird häufig verwendet, um die Endantwort für bessere Ergebnisse zu "polieren".

Beachten Sie, dass es sich bei der Schulplanung normalerweise um stark ressourcenbeschränkte Systeme handelt. Die Schulen gehen nicht durch das Jahr, wenn 75% des Tages viele leere Räume oder Lehrer in der Lounge sitzen. Ansätze, die in lösungsreichen Umgebungen am besten funktionieren, sind in der Schulplanung nicht unbedingt anwendbar.

Tom Dibble
quelle
2

Ich habe kommerzielle Algorithmen sowohl für den Stundenplan als auch für den Stundenplan entwickelt. Zum ersten Mal habe ich Integer-Programmierung verwendet; für die zweite eine Heuristik, die auf der Maximierung einer Zielfunktion durch Auswahl von Slot-Swaps basiert und dem ursprünglich entwickelten manuellen Prozess sehr ähnlich ist. Die wichtigsten Faktoren für die Akzeptanz solcher Lösungen sind die Fähigkeit, alle realen Einschränkungen darzustellen. und für menschliche Zeitnehmer, die nicht in der Lage sind, Möglichkeiten zur Verbesserung der Lösung zu erkennen. Am Ende war der algorithmische Teil im Vergleich zur Vorbereitung der Datenbanken, der Benutzeroberfläche, der Fähigkeit, über Statistiken wie Raumnutzung, Benutzererziehung usw. zu berichten, recht einfach und leicht zu implementieren.

Meerjungfrau
quelle
1

Im Allgemeinen ist die Einschränkungsprogrammierung ein guter Ansatz für diese Art von Planungsproblemen. Eine Suche nach "Constraint-Programmierung" und -Planung oder "Constraint-basierter Scheduling" sowohl innerhalb des Stapelüberlaufs als auch bei Google wird einige gute Referenzen generieren. Es ist nicht unmöglich - es ist nur ein wenig schwer zu überlegen, wenn traditionelle Optimierungsmethoden wie lineare oder ganzzahlige Optimierung verwendet werden. Eine Ausgabe wäre - gibt es einen Zeitplan, der alle Anforderungen erfüllt? Das an sich ist natürlich hilfreich.

Viel Glück !

Grembo
quelle
1

Sie können es mit genetischen Algorithmen aufnehmen, ja. Aber du solltest nicht :). Es kann zu langsam sein und die Parametereinstellung kann zu zeitaufwändig sein usw.

Es gibt erfolgreiche andere Ansätze. Alle in Open Source-Projekten implementiert:

  • Constraint-basierter Ansatz
    • Implementiert in UniTime (nicht wirklich für Schulen)
    • Sie können auch weiter gehen und die Integer-Programmierung verwenden. Erfolgreich an der Universität Udine und auch an der Universität Bayreuth (ich war dort beteiligt) mit der kommerziellen Software (ILOG CPLEX) durchgeführt
    • Regelbasierter Ansatz mit Heuristisc - Siehe Drools-Planer
  • Unterschiedliche Heuristiken - FET und meine eigene

Hier finden Sie eine Liste der Zeitplansoftware

Karussell
quelle
0

Ich denke, Sie sollten einen genetischen Algorithmus verwenden, weil:

  • Es ist am besten für große Problemfälle geeignet.
  • Dies führt zu einer geringeren zeitlichen Komplexität des Preises für ungenaue Antworten (nicht das ultimative Beste).
  • Sie können Einschränkungen und Präferenzen einfach festlegen, indem Sie die Fitness-Strafen für nicht erfüllte anpassen.
  • Sie können ein Zeitlimit für die Programmausführung festlegen.

  • Die Qualität der Lösung hängt davon ab, wie viel Zeit Sie für die Lösung des Programms aufwenden möchten.

    Definition genetischer Algorithmen

    Tutorial zu genetischen Algorithmen

    Klassenplanungsprojekt mit GA

Schauen Sie sich auch an: eine ähnliche Frage und eine andere

Betamoo
quelle
0

Ich weiß nicht, dass jemand diesem Code zustimmen wird, aber ich habe diesen Code mit Hilfe meines eigenen Algorithmus entwickelt und arbeite für mich in Ruby. Ich hoffe, es hilft denen, die im folgenden Code nach dem Periodflag, Dayflag, suchen subjectflag und Teacherflag sind der Hash mit der entsprechenden ID und dem Booleschen Flag-Wert. Bei Problemen kontaktieren Sie mich ....... (-_-)

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

quelle