Algorithmus zur Erstellung eines schulischen Zeitplans
https://stackoverflow.com/questions/2177836
-
24-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich habe mich gefragt, ob es Lösungen für den Algorithmus zur Schaffung eines Schulzeitplans gibt. Grundsätzlich geht es darum, die "Stundedispersion" (sowohl in Lehrern als auch im Klassenfall) für bestimmte Klassen-Subject-Lehrerverbände zu optimieren. Wir können davon ausgehen, dass wir beim Eingang Klassen, Unterrichtsfächer und Lehrer miteinander verbunden sind und dass der Zeitplan zwischen 8 Uhr und 16 Uhr passen sollte.
Ich denke, dafür gibt es wahrscheinlich keinen genauen Algorithmus, aber vielleicht kennt jemand eine gute Annäherung oder einen Hinweis dafür, ihn zu entwickeln.
Lösung
Dieses Problem ist NP-Complete!
Kurz gesagt, man muss alle möglichen Kombinationen untersuchen, um die Liste akzeptabler Lösungen zu finden. Aufgrund der Variationen der Umstände, unter denen das Problem in verschiedenen Schulen auftritt (z. B.: Gibt es Einschränkungen in Bezug auf Klassenzimmer? Sind einige der Klassen in den Untergruppen in der Zeit aufgeteilt? Ist das ein wöchentlicher Zeitplan? usw.) Es gibt keine bekannte Problemklasse, die allen Planungsproblemen entspricht. Vielleicht der Rucksackproblem hat viele Elemente der Ähnlichkeit mit diesen Problemen insgesamt.
Eine Bestätigung, dass dies sowohl ein hartes Problem als auch ein schwieriges Problem ist, für das Menschen ständig nach einer Lösung suchen, ist es, dies zu überprüfen (lang) Liste der (meist kommerziellen) Softwareplanungstools
Aufgrund der großen Anzahl der beteiligten Variablen, deren größte Quelle in der Regel die Wünsche des Fakultätsmitglieds sind;-) ... ist sie normalerweise in der Regel unpraktisch, um alle möglichen Kombinationen aufzählen zu können. Stattdessen müssen wir einen Ansatz auswählen, der eine Teilmenge der Problem-/Lösungsräume besucht.
- Genetische Algorythmen, in einer anderen Antwort zitiert ist (oder, imho, scheint) gut ausgestattet, um diese Art von halbgesteuerter Suche durchzuführen (das Problem, eine gute Bewertungsfunktion für die Kandidaten zu finden, die für die nächste Generation aufbewahrt werden sollen)
- Grafikumschreiben Ansätze sind auch mit dieser Art von kombinatorischen Optimierungsproblemen verwendet.
Ich möchte mich vorschlagen, anstatt sich auf bestimmte Implementierungen eines automatischen Programms für das automatische Zeitplangenerator zu konzentrieren, sondern vorschlagen ein paar Strategien, die angewendet werden können, Auf der Ebene der Definition des Problems.
Die allgemeine Begründung ist, dass bei den meisten Planungsproblemen in der realen Welt einige Kompromisse erforderlich sein werden, nicht alle Einschränkungen, ausgedrückt und impliziert: Sie werden voll und ganz erfüllt sein. Deshalb helfen wir uns selbst durch:
- Definieren und Ranking aller bekannten Einschränkungen
- Reduzierung des Problemraums durch manuell und eine Reihe von Set von zusätzlich Einschränkungen.
Dies mag kontraintuitiv erscheinen, aber zum Beispiel durch die Bereitstellung eines anfänglichen, teilweise ausgefüllten Zeitplans (etwa 30% der Zeitschläge), auf eine Weise, die alle Einschränkungen voll erfüllt, und indem wir diesen teilweisen Zeitplan unveränderlich berücksichtigen, reduzieren wir das erheblich die Zeit/Raum benötigt, um Kandidatenlösungen zu erstellen.
Eine andere Möglichkeit, zusätzliche Einschränkungen zu helfen, ist beispielsweise "künstlich" eine Einschränkung, die das Unterrichten einiger Fächer an einigen Tagen der Woche verhindern (wenn dies ein wöchentlicher Zeitplan ist ...). Diese Art von Einschränkungen führt dazu, die Problem-/Lösungsräume zu verringern, ohne dass sie normalerweise eine erhebliche Anzahl guter Kandidaten ausschließen. - Sicherstellen, dass einige der Einschränkungen des Problems schnell berechnet werden können. Dies wird häufig mit der Auswahl des Datenmodells verbunden, die zur Darstellung des Problems verwendet werden. Die Idee ist, einige der Optionen schnell zu entscheiden (oder zu beschneiden).
- Neudefinition des Problems und ermöglicht einige der Einschränkungen einige Male (typischerweise gegen die Endknoten des Diagramms). Die Idee hier ist, beide zu entfernen etwas von Einschränkungen für das Ausfüllen der letzten Slots im Zeitplan oder für das automatische Programm für das automatische Generatorprogramm, das den gesamten Zeitplan abgeschlossen hat, und uns stattdessen eine Liste von etwa ein Dutzend plausiblen Kandidaten zur Verfügung stellen. Ein Mensch ist oft in einer besseren Position, um das Puzzle zu vervollständigen, wie angegeben, möglicherweise einige der Krankenstäbe unter Verwendung von Informationen, die normalerweise nicht mit der automatisierten Logik geteilt werden (z. B. "Keine Mathematik am Nachmittag", kann gelegentlich gebrochen werden Für die Klasse "Advanced Math and Physics"; oder "Es ist besser, einen der Anforderungen von Herrn Jones zu brechen als eines von Frau Smith ... ;-))
Beim Proof-Lesen dieser Antwort ist mir klar, dass es ziemlich schüchtern ist, eine eindeutige Antwort zu liefern, aber es ist trotzdem voller praktischer Vorschläge. Ich hoffe, dass diese Hilfe mit dem, was schließlich ein "harter Problem" ist.
Andere Tipps
Es ist ein Chaos. ein königliches Durcheinander. Um die Antworten zu ergänzen, die bereits sehr vollständig sind, möchte ich auf meine Familienerfahrung hinweisen. Meine Mutter war Lehrerin und war früher in den Prozess beteiligt.
Es stellt sich heraus, dass es nicht nur schwierig ist, einen Computer zu tun, sondern auch schwierig zu codieren, sondern auch schwierig, da 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 die Lektion dort um 10.30 Uhr beendet, kann er natürlich nicht um 10.30 Uhr in Ihren Räumlichkeiten beginnen, weil er einige Zeit benötigt, um zwischen den Instituten zu pendeln.
- Zwei Lehrer sind verheiratet. Im Allgemeinen gilt es als gute Praxis, zwei verheiratete Lehrer in derselben Klasse nicht 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 spezifischen Klasse unterrichten, in der sich ihr Kind befindet.
- Die Schule verfügt über getrennte Einrichtungen, wie ein Tag, an dem sich die Klasse in einem Institut befindet, und ein anderer Tag ist die Klasse in einem anderen.
- Die Schule hat Laboratorien geteilt, diese Labors sind jedoch nur an bestimmten Wochentagen verfügbar (beispielsweise aus Sicherheitsgründen, in denen zusätzliches Personal erforderlich ist).
- Einige Lehrer haben Vorlieben für den freien Tag: Einige bevorzugen am Montag, einige am Freitag, andere am Mittwoch. Einige bevorzugen es, früh am Morgen zu kommen, andere lieber später.
- Sie sollten keine Situationen haben, in denen Sie in der ersten Stunde eine Lektion über die Geschichte, Geschichte, dann drei Stunden Mathematik, dann eine weitere Stunde Geschichte haben. Es macht weder Sinn für die Schüler noch für den Lehrer.
- Sie sollten die Argumente gleichmäßig verbreiten. Es ist nicht sinnvoll, die ersten Tage in der Woche nur Mathematik zu haben, und dann den Rest der Woche nur Literatur.
- Sie sollten einigen Lehrern zwei aufeinanderfolgende Stunden für die Durchführung von Bewertungstests geben.
Wie Sie sehen können, ist das Problem nicht NP-Complete, sondern NP-Insane.
Sie tun also, dass sie einen großen Tisch mit kleinen Plastikeinsätzen haben und die Einfügungen herum bewegen, bis ein zufriedenstellendes Ergebnis erzielt wird. Sie beginnen nie von vorne: Normalerweise beginnen sie vom Zeitplan des Vorjahres und nehmen Anpassungen vor.
Das Internationaler Zeitplanwettbewerb 2007 Hatte eine Lektionsplanung und eine Prüfung der Planungsplatte. Viele Forscher nahmen an diesem Wettbewerb teil. Viele Heuristiken und Metaheuristiken wurden ausprobiert, aber am Ende schlugen die lokalen Suchmetaheuristik (wie Tabu -Suche und simuliertes Tempern) andere Algorithmen (wie genetische Algorithmen) eindeutig.
Schauen Sie sich die 2 Open -Source -Frameworks an, die einige der Finalisten verwendet haben:
- Jboss Optaplanner (Java, Open Source)
- Einheit (Java, Open Source) - Mehr für Universitäten
Eine meiner Halbzeitaufgaben war eine genetische Algorithmus-School-Tabellenerzeugung.
Ganzer Tisch ist ein "Organismus". Es gab einige Veränderungen und Einschränkungen des generischen genetischen Algorithmenansatzes:
Für "illegale Tabellen" wurden Regeln getroffen: zwei Klassen im selben Klassenzimmer, ein Lehrer, der zwei Gruppen gleichzeitig unterrichtete usw. Diese Mutationen wurden sofort als tödlich eingestuft und ein neuer "Organismus" wurde sofort anstelle des "Verstorbenen" beflutet. Der erste wurde durch eine Reihe von zufälligen Versuchen generiert, eine legale (wenn auch sinnlose) zu erhalten. Letale Mutation wurde nicht auf die Anzahl der Mutationen in der Iteration gezählt.
"Exchange" -Mutationen waren viel häufiger als "modifizieren" Mutationen. Änderungen waren nur zwischen Teilen des Gens, die Sinn machten - kein Lehrer durch ein Klassenzimmer.
Für die Bündelung bestimmter 2 Stunden zusammen wurden kleine Boni zugewiesen, um das gleiche generische Klassenzimmer nach derselben Gruppe zuzuweisen, um die Arbeitszeit des Lehrers und die Last der Klasse kontinuierlich zu halten. Mäßige Boni wurden zugewiesen, um korrekte Klassenzimmer für ein bestimmtes Thema zu geben, die Klassenstunden innerhalb von Bindungen (Morgen- oder Nachmittag) und dergleichen zu halten. Große Boni dienen die Zuweisung der korrekten Anzahl von gegebenem Thema, bei der Arbeitsbelastung für einen Lehrer usw.
Die Lehrer könnten ihre Arbeitsbelastungspläne von "Wunsch zu arbeiten dann" erstellen, "okay, dann zu arbeiten", "funktioniert dann nicht gern", "kann dann nicht funktionieren", mit ordnungsgemäßen Gewichten zugewiesen. Ganz 24h waren juristische 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 in der Lage, es leicht um eine Größenordnung nach oben oder unten zu ändern - und es gab Hunderte oder Tausende von Eigenschaften in einem Organismus. Dies führte zu absolut großen Zahlen als Gewicht und musste als direktes Ergebnis eine Bignum Library (GMP) verwenden, um die Berechnungen durchzuführen. Für einen kleinen Testpase von rund 10 Gruppen, 10 Lehrern und 10 Klassenzimmern begann der erste Satz mit 10^-200-etwas und endet mit 10^+300-etwas. Es war völlig ineffizient, als es flacher war. Auch die Werte wuchsen mit größeren "Schulen" viel größer.
In Bezug auf die Berechnungszeit gab es über einen langen Zeitraum kaum einen Unterschied zwischen einer kleinen Bevölkerung (100) und einer großen Bevölkerung (10 k+) über weniger Generationen. Die Berechnung erzeugte über die gleiche Zeit.
Die Berechnung (bei etwa 1 GHz -CPU) würde etwa 1 Stunden dauern, um fast 10^+300 zu stabilisieren und Zeitpläne zu erzeugen, die ganz gut aussahen, für das 10x10x10 -Testfall.
Das Problem ist leicht zu paralellisierbar, indem Sie die Netzwerkeinrichtung bereitstellen, die die besten Proben zwischen Computern austauschen würde, die die Berechnung ausführen.
Das resultierende Programm hat nie das Tageslicht für das Semester zu einer guten Note für das Semester gemacht. Es zeigte ein gewisses Versprechen, aber ich bekam nie genug Motivation, um eine GUI hinzuzufügen und sie für die Öffentlichkeit nutzbar zu machen.
Dieses Problem ist schwieriger als es scheint.
Wie andere angedeutet haben, ist dies ein NP-Complete-Problem, aber analysieren wir, was das bedeutet.
Grundsätzlich bedeutet dies, dass Sie sich alle möglichen Kombinationen ansehen müssen.
Aber "Schau auf" sagt dir nicht viel, was du tun musst.
Es ist einfach, alle möglichen Kombinationen zu erzeugen. Es könnte eine große Menge an Daten erzeugen, aber Sie sollten nicht viele Probleme haben, die Konzepte dieses Teils des Problems zu verstehen.
Das zweite Problem ist das, 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".
Funktioniert beispielsweise derselbe Lehrer 5 Tage die Woche für x Wochen in Folge? Auch wenn dies eine funktionierende Lösung ist, ist es möglicherweise keine bessere Lösung als zwischen zwei Personen zu wechseln, so dass jeder Lehrer jeweils eine Woche macht. Oh, du hast nicht darüber nachgedacht? Denken Sie daran, dass dies Menschen sind, mit denen Sie es zu tun haben, nicht nur ein Problem der Ressourcenzuweisung.
Selbst wenn ein Lehrer 16 Wochen lang in Vollzeit arbeiten könnte, könnte dies eine suboptimale Lösung sein, verglichen mit einer Lösung, bei der Sie versuchen, sich zwischen den Lehrern zu wechseln, und diese Art des Ausgleichs ist sehr schwer in Software aufzubauen.
Zusammenfassend lässt sich sagen, dass die Herstellung einer guten Lösung für dieses Problem für viele, viele Menschen viel wert sein wird. Daher ist es kein einfaches Problem, zusammenzubrechen und zu lösen. Seien Sie bereit, einige Ziele zu erreichen, die nicht zu 100% sind, und nennen Sie sie "gut genug".
Update: Aus Kommentaren ... sollte auch Heuristiken haben!
Ich würde mit Prolog gehen ... Dann verwenden Sie Ruby oder Perl oder etwas, um Ihre Lösung in eine schönere Form zu bereinigen.
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 (immer noch) im Prozess, etwas Ähnliches wie dieses Problem zu tun, aber den gleichen Weg wie ich gerade erwähnt habe. Prolog (als funktionale Sprache) erleichtert wirklich die Lösung von NP-HART-Problemen.
Genetische Algorithmen werden häufig für eine solche Planung verwendet.
Gefunden Dieses Beispiel (Klassenplan mit genetischer Algorithmus erstellen) Das entspricht ziemlich gut zu Ihren Anforderungen.
Hier sind ein paar Links, die ich gefunden habe:
Stundenplan - listet einige Probleme auf
Mein Zeitplanalgorithmus, der in FET implementiert ist (Free Timetabling Software, http://lalescu.ro/liviu/fet/ , eine erfolgreiche Anwendung):
Der Algorithmus ist heuristisch. Ich nannte es "rekursiver Tausch".
Eingabe: Eine Reihe von Aktivitäten a_1 ... a_n und die Einschränkungen.
Ausgabe: Eine Reihe von Zeiten Ta_1 ... Ta_n (der Zeitfenster jeder Aktivität. Die Räume sind hier zum Einfachheit halber ausgeschlossen). Der Algorithmus muss jede Aktivität zu einem Zeitfenster in Bezug auf Einschränkungen einsetzen. Jeder TA_I ist zwischen 0 (t_1) und max_time_slots-1 (t_m).
Einschränkungen:
C1) Grundlegende: Eine Liste von Aktivitätenpaaren, die nicht gleichzeitig sein können (z. B. A_1 und A_2, weil sie denselben Lehrer oder dieselben Schüler haben);
C2) Viele andere Einschränkungen (hier ausgeschlossen hier, zum Einfachheit halber).
Der Zeitplanalgorithmus (den ich als "rekursives Tausch" bezeichnet habe):
- Sortieren Sie die Aktivitäten zuerst am schwierigsten. Nicht kritischer Schritt, aber beschleunigt den Algorithmus vielleicht 10 Mal oder mehr.
Versuchen Sie, jede Aktivität (A_I) in einen zulässigen Zeitfenster zu platzieren, und folgt jeweils nach der obigen Reihenfolge. Suchen Sie nach einem verfügbaren Slot (T_J) nach A_I, bei dem diese Aktivität auf die Einschränkungen eingestellt werden kann. Wenn mehr Slots verfügbar sind, wählen Sie eine zufällige. Wenn keiner verfügbar ist, tauschen Sie ein rekursives Tausch:
a. Überlegen Sie sich für jeden Zeitfenster T_J, was passiert, wenn Sie A_I in t_j einfügen. Es gibt eine Liste anderer Aktivitäten, die mit diesem Schritt nicht übereinstimmen (zum Beispiel ist Aktivität A_K auf demselben Slot t_J und hat denselben Lehrer oder die gleichen Schüler wie A_I). Führen Sie eine Liste widersprüchlicher Aktivitäten für jeden Zeitfenster T_J.
b. Wählen Sie einen Steckplatz (T_J) mit der niedrigsten Anzahl widersprüchlicher Aktivitäten. Sagen Sie die Liste der Aktivitäten in diesem Slot enthält 3 Aktivitäten: a_p, a_q, a_r.
c. Platzieren Sie a_i bei t_j und machen Sie A_P, a_q, a_r nicht zugewiesen.
d. Versuchen Sie rekursiv, a_p, a_q, a_r (wenn die Rekursion nicht zu groß ist, z. B. 14 und wenn die Gesamtzahl der rekursiven Anrufe, die seit Schritt 2 gezählt wurden) auf A_I begonnen, nicht zu groß ist, sagen wir 2*n). wie in Schritt 2).
e. Wenn Sie erfolgreich a_p, a_q, a_r platziert, kehren Sie mit Erfolg zurück, sonst versuchen Sie es mit anderen Zeitschlitzen (gehen Sie zu Schritt 2 B) und wählen Sie den nächstbesten Zeitfenster).
f. Wenn alle (oder eine angemessene Anzahl von) Zeitfenster erfolglos versucht wurden, kehren Sie ohne Erfolg zurück.
g. Wenn wir auf Stufe 0 sind und keinen Erfolg hatten, a_i zu platzieren, platzieren Sie es wie in den Schritten 2 b) und 2 c), jedoch ohne Rekursion. Wir haben jetzt 3 - 1 = 2 weitere Aktivitäten zu platzieren. Weiter mit Schritt 2) (einige Methoden zur Vermeidung von Radfahren werden hier verwendet).
Ich habe kommerzielle Algorithmen für den Zeitplan für die Klassenzeit und den Zeitpunkt der Prüfung entworfen. Zum ersten Mal habe ich Ganzzahlprogrammierung verwendet; Für die zweite eine Heuristik basierend auf der Maximierung einer objektiven Funktion durch Auswahl von Slot -Swaps, sehr ähnlich dem ursprünglichen manuellen Prozess, der sich entwickelt hatte. Sie wichtige Dinge bei der Annahme solcher Lösungen sind die Fähigkeit, alle Einschränkungen der realen Welt darzustellen. und für den menschlichen Zeitplan, nicht in der Lage zu sein, Wege zu erkennen, um die Lösung zu verbessern. Am Ende war der algorithmische Teil im Vergleich zur Vorbereitung der Datenbanken, der Benutzeroberfläche, der Fähigkeit, über Statistiken wie Raumauslastung, Benutzerausbildung und so weiter zu melden.
Dieses Papier beschreibt das Problem mit dem schulischen Zeitplan und ihre Herangehensweise an den Algorithmus ziemlich gut: "Die Entwicklung des Lehrplans-ein interaktives, einschränkender Scheduler für Schulen und Hochschulen.[PDF
Der Autor informiert mich, dass die Lehrplansoftware hier noch verwendet/entwickelt wird: http://www.scientia.com/uk/
Ich arbeite an einem weit verbreiteten Planungsmotor, der genau das tut. Ja, es ist NP-Complete; Die besten Ansätze versuchen, eine optimale Lösung zu approximieren. Und natürlich gibt es viele verschiedene Möglichkeiten, zu sagen, welche "beste" Lösung ist - ist es wichtiger, dass Ihre Lehrer mit ihren Zeitplänen zufrieden sind oder dass die Schüler beispielsweise in alle ihre Klassen geraten?
Die absolut wichtigste Frage, die Sie früh lösen müssen, ist Was macht eine Möglichkeit, dieses System besser zu planen als eine andere? Wenn ich einen Zeitplan mit Frau Jones habe, unterrichtet Mathematik am 8. und Herr Smith um 9 Uhr, ist das besser oder schlechter als eine, bei der beide mit 10 Mathematik unterrichten? Ist es besser oder schlechter als einer mit Frau Jones unterrichtet um 8 und Herr Jones bei 2? Wieso den?
Der Hauptberat, den ich hier geben würde, besteht darin, das Problem so weit wie möglich aufzuteilen - vielleicht Kurs für Kurs, vielleicht Lehrer des Lehrers, vielleicht Platz für Raum - und zuerst daran zu arbeiten, das Teilproblem zu lösen. Dort sollten Sie mehrere Lösungen zur Auswahl haben und eine als die wahrscheinlichste optimale auswählen. Arbeiten Sie anschließend daran, die "früheren" Unterprobleme zu erstellen, die die Bedürfnisse späterer Unterprobleme bei der Bewertung ihrer potenziellen Lösungen berücksichtigen. Dann arbeiten Sie vielleicht daran, wie Sie sich aus gestrichenen Situationen aus der Ecke bringen können (vorausgesetzt, Sie können diese Situationen in früheren Unterproblemen nicht antizipieren), wenn Sie in einen "No Galy Solutions" -Zustand kommen.
Ein lokaler Optimierungspass wird häufig verwendet, um die Endantwort zu "polieren", um bessere Ergebnisse zu erzielen.
Beachten Sie, dass wir normalerweise mit hochressourcenbezogenen Systemen in der Schulplanung zu tun haben. Die Schulen gehen nicht mit vielen leeren Räumen oder Lehrern durch das Jahr durch, die 75% des Tages in der Lounge sitzen. Ansätze, die in lösungsreichen Umgebungen am besten funktionieren, sind in der Schulplanung nicht unbedingt anwendbar.
Im Allgemeinen ist die Einschränkungsprogrammierung ein guter Ansatz für diese Art von Planungsproblem. Eine Suche nach "Einschränkungsprogrammierung" und Planung oder "Einschränkungsbasierter Planung" sowohl im Stack Overflow als auch bei Google generiert einige gute Referenzen. Es ist nicht unmöglich - es ist nur ein wenig schwer zu denken, wenn traditionelle Optimierungsmethoden wie lineare oder ganzzahlige Optimierung verwendet werden. Eine Ausgabe wäre - gibt es einen Zeitplan, der alle Anforderungen erfüllt? Das ist an sich offensichtlich hilfreich.
Viel Glück !
Sie können es mit genetischen Algorithmen nutzen, ja. Aber du solltest nicht :). Es kann zu langsam sein und die Parameterabstimmung kann zu Zeitkonsum usw. sein usw.
Es gibt erfolgreiche andere Ansätze. Alle in Open Source -Projekten implementiert:
- Einschränkender Ansatz
- Implementiert in Einheit (nicht wirklich für Schulen)
- Sie können auch weiter gehen und die Integer -Programmierung verwenden. Erfolgreich gemacht bei Udine University und auch an der Universität Bayreuth (ich war dort dort) mit der kommerziellen Software (ILOG CPLEX)
- Regelbasierter Ansatz mit Heuristisc - siehe Sabberer Planer
- Verschiedene Heuristiken - Fet und mein eigenes
Siehe hier für a Zeitliste für Zeitpläne
Ich denke, Sie sollten genetischen Algorithmus verwenden, weil:
- Es ist am besten für große Probleminstanzen geeignet.
- Es liefert eine reduzierte Zeitkomplexität für den Preis einer ungenauen Antwort (nicht das ultimative Beste)
- Sie können Einschränkungen und Vorlieben problemlos angeben, indem Sie Fitness -Strafen für nicht erfüllt sind.
- Sie können Zeitlimit für die Programmausführung angeben.
Die Qualität der Lösung hängt davon ab, wie viel Zeit Sie damit verbringen möchten, das Programm zu lösen.
Genetische Algorithmen Definition
Schauen Sie sich auch an:Eine ähnliche Frage und noch einer
Ich weiß nicht, dass jemand diesem Code zustimmen wird, aber ich habe diesen Code mit Hilfe meines eigenen Algorithmus entwickelt und arbeitet für mich in Ruby. Er hilft ihnen, die im folgenden Code die PeriodeFlag, DayFlag, zu helfen Die Subjektflag und die Lehrerflag sind der Hash mit der entsprechenden ID und dem Booleschen Flag -Wert. Jedes Problem 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
@finaltt.timetable_struct_id=@subjectdetail.timetable_struct_id
@finaltt.employee_id=@subjectdetail.employee_id
@finaltt.section_id=section.id
@finaltt.standard_id=standard.id
@finaltt.division_id=division.id
@finaltt.subject_id=@subjectdetail.subject_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
