Lehrer Zeitplan Algorithmus

https://stackoverflow.com/questions/210635

03-07-2019
|

Frage

Dies ist ein problem, das ich habe auf meinem Verstand für eine lange Zeit.Als der Sohn eines Lehrers und ein Programmierer, es fiel mir früh auf...aber ich habe immer noch nicht gefunden eine Lösung für Sie.

Das ist also das problem.Man braucht, um erstellen Sie einen Zeitplan für eine Schule, die mit einigen Einschränkungen.Diese sind in der Regel in zwei Kategorien unterteilt:

Sanity Checks

Ein Lehrer nicht lehren zwei Klassen zur gleichen Zeit
Ein student kann nicht Folgen zwei Lektionen zur gleichen Zeit
Einige Lehrer müssen mindestens einen freien Tag in der Woche
Alle Tage der Woche sollte abgedeckt werden durch die Zeit-Tabelle
Thema X darf genau so-und-so Stunden pro Woche
...

Einstellungen

Jeder Lehrer der Zeitplan sollte so kompakt wie möglich sein (d.h.die Lehrer sollten alle Stunden des Tages in einer Reihe mit keine Pausen, wenn möglich)
Lehrer, die haben Tage sollten in der Lage sein, um auszudrücken, eine Vorliebe, die Tag
Lehrer, die Teilzeit arbeiten, sollten in der Lage sein, um auszudrücken, eine Präferenz, ob zur Arbeit, in der Anfang oder das Ende des Schultages.
...

Jetzt, nach ein paar Jahren nicht, eine Lösung zu finden (und zu lernen, eine Sache oder zwei in der Zwischenzeit...), erkannte ich, dass dies riecht wie ein NP-hartes problem.

Ist es erwiesen, die als NP-schwer?

Hat jemand eine Idee, wie man dieses Ding zu knacken?

Suche in diese Frage hat mich zum nachdenken über dieses problem, und ob genetische algorithmen wäre brauchbar, in diesem Fall.Allerdings wäre es ziemlich schwer zu mutieren Möglichkeiten unter Beibehaltung der sanity-check-Regeln.Auch ist es mir nicht klar, wie zu unterscheiden unvereinbare Anforderungen.

Ein kleiner Nachtrag, um besser geben die problem.Dies ist angewendet, um die italienische Schule Stil Klassenzimmer, wo alle Schüler verbunden sind, in verschiedene Klassen (für Beispiel:Jahr 1 Punkt A) und die Lehrer wechseln zwischen den Klassen.Alle Schüler der gleichen Klasse haben den gleichen Zeitplan und haben keine andere Wahl, über die Lektionen zu besuchen.

Lösung

Ich bin einer der Entwickler, dass die arbeiten an der scheduler Teil eines Schüler-Informations-system.Während unsere ursprüngliche Ansatz des scheduling problem, wir haben recherchiert, genetische algorithmen zur Lösung von constraint-satisfaction Problemen, und obwohl wir erfolgreich waren wir zunächst klar, dass es eine weniger komplizierte Lösung für das problem (nach dem Besuch einer Schule scheduling workshop)

Unsere aktuelle Implementierung funktioniert großartig und nutzt brute-force-mit intelligente Heuristik, um ein gültiges Zeitplan in kurzer Zeit.Der master schedule (Zuordnung der Klassen zu den Lehrern) ist die erste gebaut, unter Berücksichtigung aller Einschränkungen, die jeder Lehrer hat, während die Minimierung der Möglichkeit von Konflikten für die Studenten von Ihrem Kurs Anfragen).Die Studierenden sind dann in der geplanten Klassen mit der gleichen Methode.

Dadurch können Sie die Maschine bauen Sie einen master-Zeitplan erste, und dann eine menschliche optimieren ihn bei Bedarf.

Der scheduler die aktuelle Implementierung in perl geschrieben ist, aber auch andere Optionen, die wir besuchten, schon früh wurden Prolog und CLIPS (expert system)

Andere Tipps

Dies ist ein mapping-problem:Sie müssen einen Plan für jede Stunde in einer Woche und jeden Lehrer eine Aktivität (Lehre zu einer bestimmten Klasse oder frei Stunde ).

Teilen Sie die problem:

Erstellen Sie die Liste der Lehrer, Klassen und Einstellungen, dann lassen Sie die user füllen Sie einige der Einstellungen auf eine Karte zu haben, als Ausgangspunkt.
Zufällig nehmen Sie ein element aus der Liste aus und setzen Sie es an einen zufälligen free position auf der Karte wenn es nicht Kreuz alle sanity, bis die Liste leer ist.Wenn Sie zu irgendeinem bestimmten iteration können Sie nicht ein element auf der Karte ohne überschreiten eine sanity-check-shift zwei Positionen auf der Karte und versuchen Sie es erneut.
Wenn die Karte voll ist, versuchen Sie, die Verlagerung von Positionen auf der Karte und optimieren Sie das Ergebnis.

In den Schritten 2 und 3 zeigen in jeder iteration der Benutzer:Elemente, die Links in der Liste, Positionen auf der Karte und die nächsten berechnete bewegen und lassen Sie die Benutzer eingreifen.

Ich habe nicht versucht, diese, aber das wäre mein Erster Ansatz.

Ich angegangen habe ähnliche planning/scheduling-Probleme in der Vergangenheit und auch die AI-Technik, die ist oft am besten geeignet für diese Klasse von problem ist die "Constraint-Based Reasoning".

Es ist im Grunde eine brute-force-Methode wie Laurenty vorgeschlagen, aber der Ansatz beinhaltet die Anwendung von Beschränkungen in einer effizienten Reihenfolge, um die Ursache undurchführbar Lösungen zu scheitern, schnell zu minimieren die Berechnung erforderlich.

Googeln "Constraint-Based Reasoning" bringt eine Menge Ressourcen auf die Technik und Ihre Anwendung auf Probleme planen.

Beantwortung meiner eigenen Frage:

Die FET-Projekt erwähnt gnud verwendet diesen Algorithmus:

Einige Worte über den Algorithmus:FET verwendet eine heuristical Algorithmus, indem die Aktivitäten der Reihe nach, beginnend mit die schwierigsten.Wenn es nicht eine Lösung finden Sie Punkte, die Sie auf den mögliche unmöglich Tätigkeiten, so Sie können Fehler korrigieren.Der Algorithmus swaps Aktivitäten rekursiv, wenn, dass ist möglich, um Platz zu machen für eine neue Aktivität, oder, in extremen Fällen, backtracks und schaltet um von Bewertung.Der wichtigste code ist in src/engine/generate.cpp.Bitte e-mail mich für details oder die mailing Liste.Der Algorithmus ahmt die Betrieb eines menschlichen timetabler, ich denken.

Link

Folgenden die "Constraint-Based Reasoning" führen durch zwingende Software auf Wikipedia führen mich zu diese Seiten die haben einen interessanten Absatz:

Lösung des constraint satisfaction problem auf eine endliche Domäne ist eine NP-vollständige problem im Allgemeinen.Die Forschung hat gezeigt, dass eine Reihe von Polynom-Zeit subcases, meist die durch die Beschränkung entweder auf die erlaubte domains oder Einschränkungen oder die Weg-Einschränkungen können platziert werden über die Variablen.Die Forschung hat auch Beziehung der constraint satisfaction problem Probleme in anderen Bereichen wie der finite - Modell, Theorie und Datenbanken.

Das erinnert mich an dieses blog-post zum planen einer Konferenz, mit video Erklärung hier.

Wie ich es tun würde:

Die Bevölkerung zählen zwei Dinge:

Wer unterrichtet welche Klasse (ich erwarte, dass die Lehrer ein Fach unterrichten).
Was für ein Klasse nimmt auf ein bestimmtes Zeitfenster.

Auf diese Weise können wir nicht haben Konflikte (eine Lehrerin an 2 stellen, oder eine Klasse mit zwei Fächern an der gleichen Zeit).

Die fitness-Funktion zählen:

Wie viele Zeitschlitze jeder Lehrer gibt pro Woche.
Wie viele Zeitschlitze ein Lehrer auf die gleichen Tag (Sie können nicht haben einen ganzen Tag der Lehre, das muss auch ausbalanciert werden).
Wie viele Zeit-slots mit dem gleichen Thema in einer Klasse am gleichen Tag (Sie können nicht ein Tag voller Mathematik!).

Vielleicht nehmen Sie die Standardabweichung für alle von Ihnen, da Sie sollte ausgewogen sein.

Ich bin mir nicht sicher, ob dies deckt den gleichen Boden wie @Strengen Software Antwort (wie der name ist etwas anders), aber ich habe ein paar sehr gute Freunde, die sich der Erforschung der Gegend von Constraint-Programmierung.Erstellen von Fahrplänen ist eine Anwendung Ihrer Forschung.

Dr. Chris Jefferson erstellt ein Programm namens Minion , die Sie können download von SourceForge und ist ein sehr schnelles brute-force-constraint-problem-solver in C++geschrieben

Ich denke, dass Sie möglicherweise fehlen einige Einschränkungen.

Man würde lieber wo möglich, haben die Lehrer, die geplante Klassen, für die Sie zertifiziert sind.

Man würde vermuten, dass die Klassen, die angefordert werden, und die erwartete Zahl der Beschäftigten in den einzelnen bedeutsam wäre.

Ich glaube, der Ort, um zu starten wäre, um eine Liste aller Ihrer Einschränkungen, herauszufinden, eine Daten-Struktur, die Sie zu vertreten.

Dann erstellen Sie eine Art von Motor, baut eine Testversion Lösung, dann wertet es für die fitness, nach den Einschränkungen.

Sie könnten dann werfen Sie den Spaß genetische algorithmen Teil in es und sehen, wenn Sie können, Holen Sie sich die fitness im Laufe der Zeit erhöhen, wie die Gene vermischen.

Beginnen Sie mit einem kleinen Satz von Einschränkungen, und erhöhen Sie Sie, wie Sie den Erfolg sehen (wenn Sie den Erfolg sehen)

Möglicherweise gibt es eine Möglichkeit, die Einschränkungen und Schuhlöffel Sie zusammen mit etwas, das wie ein linearer Programmierung Algorithmus.

Ich Stimme zu.Es klingt wie eine lustige Herausforderung

Eine der schlechtesten open-source-webpages je zuvor, aber das Projekt sieht vielversprechend aus:http://www.lalescu.ro/liviu/fet/

Eine web-basierte Vorgehensweise:
phpScheduleIt (nicht schul-spezifisch)

Blick auf diese Frage gab mir zu denken über dieses problem, und ob genetische algorithmen wäre brauchbar, in in diesem Fall.Allerdings wäre es ziemlich schwer zu mutieren Möglichkeiten die Aufrechterhaltung der sanity-check-Regeln.Auch ist es mir nicht klar, wie zu unterscheiden unvereinbare Anforderungen.

Genetische Algorithmen sind sehr gut geeignet, um Probleme wie diese.Sobald Sie kommen mit eine anständige Darstellung der Chromosomen (in diesem Fall wahrscheinlich einen Vektor repräsentiert alle verfügbaren Klassen-slots) du bist auf dem besten Weg dorthin.

Mach dir keine sorgen über die Aufrechterhaltung sanity-checks während der mutation phase.Mutation ist zufällig.Vernunft und Präferenz überprüft, beide gehören in der phase der Auswahl.Eine fehlgeschlagene überprüfung würde drastisch sinken die fitness eines Individuums, während eine ausgefallene Vorliebe würde nur leicht niedriger die fitness.

Unvereinbare Anforderungen sind einem anderen problem zusammen.Wenn Sie sind völlig nicht kompatibel ist, erhalten Sie eine Bevölkerung, die nicht konvergieren auf etwas nützliches.

Viel Glück.Als der Sohn eines Vaters, der mit dieser Art von problem ist, was mich zu der Gruppe, landete ich in ...

Als ich ein Kind war, war mein Vater geplante match Beamten in einem lokalen Sport-Liga, das hätte eine ähnlich lange Liste von Einschränkungen und ich habe versucht, etwas zu schreiben, zu helfen.Wenn ich auf die Universität kam ich selbst nutzte es als mein letztes Jahr Projekt schließlich ließ sich auf einer Monte-Carlo-Implementierung (unter Verwendung einer Simulierten Annealing-Modell).

Die grundlegende Idee ist, dass, wenn es nicht NP, es ist ziemlich nah, also eher als vorausgesetzt, es gibt eine Lösung, ich würde Sie zu finden, die am besten in einem bestimmten Zeitraum.Ich würde Gewicht all die Einschränkungen, die Kosten für Sie zu brechen:sanity hätte enorme Kosten, die Präferenzen hätte geringere Kosten (aber zunehmend für mehr bricht, so bricht es einmal sein würde, weniger als die Hälfte der Kosten für brechen Sie es zweimal).

Die grundlegende Idee ist, dass ich begann mit einem "zufälligen" Lösung und kostete es;dann die änderungen durch das vertauschen einer kleinen Anzahl von Aufgaben, neu bewertet und dann, probalistically die Annahme oder Ablehnung der änderung.

Nach tausenden von Iterationen, die Sie Zentimeter näher, um eine akzeptable Lösung.

Glauben Sie mir, aber nicht, dass diese Klasse von Problemen mit Forschungs-Gruppen am Laufenden Band, Doktoranden, so sind Sie in guter Gesellschaft sind.

Vielleicht finden Sie auch etwas Interesse in die Lineare Programmierung arena, z.B. simplex und so weiter.

Ja, ich denke, dies ist NP-vollständig - oder zumindest die Suche nach der optimalen Lösung ist NP-vollständig.

Ich arbeitete an einem ähnlichen problem im college, als ich einem Freund erzählte der Vater (er war ein Lehrer), die ich lösen könnte seine scheduling-Probleme für ihn, wenn er nicht das finden eines geeigneten Programms für Sie (dies war 1990 oder so)

Ich hatte keine Ahnung, was ich mir in.Zum Glück für uns alle die ich tun musste, war zu finden eine Lösung, die passt die Einschränkungen.Aber in meinen Tests war ich immer besorgt, und bestimmen, OB eine Lösung überhaupt.Er hatte nie zu viele Einschränkungen und das Programm verwendet verschiedene Heuristiken und zurück tracking.Es war eine Menge Spaß.

Ich denke, Bill Gates arbeitete auch auf ein system wie das in der high school oder das college für seine high-school -.Nicht sicher, obwohl.

Viel Glück.Alle meine Notizen sind verschwunden und ich habe nie rund um die Umsetzung einer Lösung, die ich könnte-Markt.Es war ein Spezial-Projekt, das ich neu codiert als ich lernte neue Sprachen (Basic, das Schema, C, VB, C++)

Haben Spaß mit es

ich sehe, dass dieses problem gelöst werden kann durch Prolog-Programm durch Anschluss an eine Datenbank und das Programm kann den Zeitplan, da eine Reihe von Einschränkungen Lesen abt "Constraint satisfaction Problem prolog"

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow