Best Fit Scheduling Algorithm

Question

Ich schreibe ein Planungsprogramm mit einem schwierigen Programmierproblem. Es gibt mehrere Ereignisse, die jeweils mit mehreren Besprechungszeiten. Ich brauche eine Anordnung von Besprechungszeiten so zu finden, dass jeder Zeitplan jedes gegebene Ereignis genau einmal enthält, über einen Link jeweils mehrere Besprechungszeiten der Veranstaltung.

Natürlich könnte ich Brute-Force verwenden, aber das ist selten die beste Lösung. Ich vermute, das ein relativ grundlegende Informatik Problem ist, das ich lernen werde, sobald ich bin in der Lage Klassen der Informatik zu beginnen. In der Zwischenzeit würde ich alle Links lieber, wo ich auf diese Zeilen lesen konnte, oder auch nur ein Name, den ich könnte Google.

Answer 1

Ich glaube, Sie genetischen Algorithmus verwenden sollten, weil:

• Es ist am besten geeignet für große Probleminstanzen.
• Es ergibt reduzierte Zeit Komplexität auf den Preis von ungenauen Antwort (nicht die ultimative beste)
• Sie können festlegen, Einschränkungen und Einstellungen leicht von Fitness-Strafen für nicht erfüllt diejenigen anpassen.
• Sie können Fristen für die Programmausführung angeben.

• Die Qualität der Lösung hängt davon ab, wie viel Zeit Sie beabsichtigen, das Programm zu verbringen zu lösen ..

  Genetische Algorithmen Definition

  Genetische Algorithmen Tutorial

  Klasse Planungsprojekt mit GA

Answer 2

Es gibt mehrere Möglichkeiten, dieses

zu tun

Ein Ansatz ist die Constraint-Programmierung zu tun. Es ist ein Spezialfall der dynamischen Programmierung von feanor vorgeschlagen. Es ist helful eine Fachbibliothek zu verwenden, die den Begrenzungs und Verzweigung für Sie tun können. (Google für "gecode" oder "Kometen-online" Bibliotheken zu finden)

Wenn Sie mathematisch geneigt sind, dann können Sie auch das Problem der Programmierung verwenden integer zu lösen. Die grundlegende Idee dabei ist, Ihr Problem in einen Satz von linearen Ungleichungen zu übersetzen. (Google für „integer Programmierung Scheduling“ zu viele Beispiele aus der Praxis und Google für „Abacus COIN-OR“ für eine nützliche Bibliothek zu finden)

Meine Vermutung ist, dass Constraint-Programmierung der einfachste Ansatz ist, aber integer Programmierung ist nützlich, wenn Sie an einem gewissen Punkt realer Variablen in ihrem Problem enthalten sein sollen.

Answer 3

Ihre Beschreibung des Problems ist nicht ganz klar, aber wenn alles, was Sie versuchen, einen Zeitplan zu tun zu finden ist, die keine überlappenden Ereignisse hat, dann ist dies eine einfache Problem bipartiter passend .

Sie haben zwei Sätze von Knoten: Ereignisse und Zeiten. Zeichnen Sie eine Kante von jedem Ereignis zu jeder möglichen Besprechungszeit. Anschließend können Sie konstruieren effizient die passende (die größtmögliche Menge von Kanten zwischen den Knoten) mit Augmented Pfade . Dies funktioniert, weil man findet immer einen zweiteiligen Graphen in eine äquivalente Flussgraphen umwandeln.

Ein Beispiel-Code, der dies tut, ist BIM . Standard grafische Darstellung Bibliotheken wie KOBOLD und NetworkX hat auch zweiteilige Matching-Implementierungen.

Answer 4

Das klingt wie könnte dies ein guter Kandidat für einen dynamische Programmierung Lösung, die speziell etwas ähnlich dem Intervall Scheduling Problem.

Es gibt einige Visuals hier für das Intervall Scheduling Problem speziell, was das Konzept klarer machen kann. Hier ein gutes Tutorial auf dynamisch Programmierung insgesamt.