Welcher Algorithmus zum Generieren der Zeittabelle für Schulen verwendet wird

Question

Ich arbeite an einer einfachen Anwendung, die Zeittabelle (Tagesplaner) für Schulen generieren wird. Ich habe die Grundlagen der Algorithmen gelesen, bin aber nicht sicher, wo ich anfangen soll.

Das Problem:
Weisen Lehrer Klassen unter Berücksichtigung eine Menge von Einschränkungen wie:
1) Thema
2) Expertise von Lehrern
3) Nicht mehr als 2 Klassen kontinuierlich .. etc

Es versteht sich von selbst, dass es keine Überschneidungen geben sollte. Grundsätzlich muss ich N Lehrer zu M Klassen mit einer festen Anzahl von Arbeitsstunden jeden Tag zuweisen (8).

Die Eingänge:
1) Gesamtzahl der Klassen
2) Lehrer zusammen mit ihrer Fachkompetenz
3) Themen/Kurse für jede Klasse
4) Anzahl der Vorträge pro Klasse pro Tag
5) Andere flexible Einschränkungen wie minimale/maximale Arbeitszeit für einen Lehrer pro Tag, pro Woche Gesamtarbeitsstunden pro Lehrer, etc

Meine Fragen:
1) Ist es richtig, um es als ein Zuweisungsproblem mit mehreren Einschränkungen zu betrachten?
2) Welchen Algorithmus sollte ich verwenden? (Ungarischer Algorithmus?)
3) Sollte ich anfangen, indem ich die ganze Menge von Zwängen auf einmal bekomme, und dann die Tabelle erzeuge, oder sollte es in Zwischenschritten gemacht werden?

Ich bin ein Anfänger zum Lernen/Implementieren von Algorithmen, so dass jede Hilfe, um mich in die richtige Richtung zu zeigen, geschätzt! Vielen Dank.

Answer 1

Sie haben sich für ein Problem entschieden. Eine derartige Planungsoptimierung ist NP-vollständig. Es gibt eine Menge von Artikeln darüber, wie man mit solchen Problemen umgehen kann. Die Klasse des Problems ist bekannt als Einschränkung der Zufriedenheit. Sie können eine erschöpfende Suche durchführen, die am einfachsten ist, aber auch sehr zeitaufwendig ist. Wenn Sie mehr als eine Handvoll Klassen haben, wird es nicht funktionieren. Sie können sich Solver Foundation ansehen, eine Suite von Tools für .net, um diese Art von Dingen zu lösen. Scott Hanselman machte einen Podcast darüber hier http://www.hanselminutes.com/default.aspx?showID=209 und Sie können mehr darüber finden Sie hier http://code.msdn.microsoft.com/solverfoundation. Wenn Sie es selbst ausprobieren möchten, versuchen Sie es mit GSAT oder anderen evolutionären Algorithmen, die interessant aussehen http://www.springer.com/engineering/book/978-3-540-48582-7.

Answer 2

Diese Frage kommt hier mindestens einmal pro Woche auf und die Antworten (einschließlich meiner) sind immer die gleichen. Ich denke, wir sollten ein spezielles Tag für Scheduling-Algorithmen erstellen, wenn es einen nicht gibt.

Ich wiederhole, dass die am besten geeignete Lösungstechnik für die Planung solcher Probleme im Bereich der Constraint-Programmierung liegt. Während andere Optimierungstechniken für kleine Probleme in Ordnung sind, ist die Formulierung für einige Einschränkungen oft schmerzhaft. Berücksichtigen Sie alle Integervariablen, die Sie für einige einfache Integritätsbedingungen erstellen müssen. Da das Problem oft eine Reihe praktikabler Zeitpläne erfordert (oder die Unzulässigkeit bestimmen) und nicht eine optimale Lösung, ist CP der bevorzugte Ansatz, da es genau dafür gedacht ist. Die meisten anderen Ansätze erfordern, dass ein Benutzer eine Optimalitätsbedingung für das Problem "erzwingt", wo man nicht wirklich existiert.