Algorithmus - Ideale Verteilung zwischen mehreren Workshops und Zeitrahmen

Unsere endgültige Lösung finden Sie hier:

Ссылка

Im Prinzip haben Sie bei solchen Optimierungsproblemen die Wahl zwischen exakten Methoden wie Lineares Programmieren und Constraint Programming und approximativen Methoden wie Heuristiken oder einem beliebigen Ansatz der Local Search (zB Genetische Algorithmen oder Simulated Annealing) / p>

Für die von dir angesprochene Problemgröße würde ich definitiv eine exakte Methode verwenden, da nur diese garantieren, dass du das globale Optimum findest. Mit ungefähren Methoden können Sie nur sicher sein, dass Sie das globale Optimum gefunden haben, wenn das Kostenmaß den Wert Null hat (z. B. keine Einschränkungsverletzungen).

Version 1: Ganzzahlige Programmierung

Ihr Problem kann als eine Variante von Bin Packing gesehen werden. Für diese Art von Problem ist Mixed Integer Programming (eine Variante der linearen Programmierung) meiner Meinung nach die beste Wahl. Sie benötigen einen MIP-Solver, da Sie diesen nicht selbst programmieren wollen. Der wahrscheinlich beste freie ist in der COIN-OR-Bibliothek zu finden: CLP / CBC. Es ist in Ordnung für kleine MIP-Probleme, kann aber Probleme mit größeren Probleme haben. Für reine LP-Probleme ist es ziemlich gut, aber für Ihr spezielles Problem benötigen Sie integrale Entscheidungsvariablen, daher MIP. Für industrielle MIP-Probleme benötigen Sie einen kommerziellen Löser. Wählen Sie zwischen CPLEX, Xpress oder Gurobi. Sie sind alle ausgezeichnet.

Das Problem kann so modelliert werden:

• Für jede Kombination aus Teilnehmer und Workshop führen Sie eine binäre Entscheidungsvariable ein. Die Variable wird eins sein, wenn der Teilnehmer den Workshop besucht. In Ihrem Beispiel gibt es 1800 solcher Variablen.

• Für jeden Teilnehmer ergibt sich die Summe der Entscheidungsvariablen aus der Anzahl der besuchten Workshops. In Ihrem Beispiel sind das drei.

• Für jeden Teilnehmer ist die Summe der sich überschneidenden Workshops höchstens 1.

• Eine Kosteneinheit wird verursacht, wenn ein Teilnehmer eine Reservierungsoption besuchen muss

• Entscheidungsvariablen für Kurse, die ein Teilnehmer nicht ausgewählt hat, werden auf Null gesetzt

Ziel ist es dann, die Gesamtkosten zu minimieren.

Hier ist ein schnell geschriebener Beispielcode in ECLiPSe (eine Variante von Prolog):

Ich habe Teilnehmer und ihre Auswahl zufällig generiert. Die Ausschlussliste ist fest codiert. Hier ist die Ausgabe, die für einen Lauf generiert wurde:

Das heißt, in der Lösung wurde 219 Mal ein Teilnehmer in eine Reserveliste gesetzt. Beachten Sie, dass dies ausschließlich auf Einschränkungen beim Überlappungsausschluss zurückzuführen ist, da die Werkstattgrößen im Modell keine Kapazitätsbeschränkungen aufweisen. Die ausgewählten Workshops für den ersten Teilnehmer waren 2, 3 und 6. Die erste Wahl von [2,3,4] war nicht durchführbar, da sich die Workshops 3 und 4 überschneiden. (Ich habe die restlichen Teilnehmer von der Antwort entfernt)

Für diesen Test habe ich den kostenlosen CLP / CBC-Löser aus der COIN-OR-Bibliothek verwendet, der in der ECLiPSe-Distribution enthalten ist. COIN-OR bietet auch API-Bibliotheken für C ++ und Python.

Version 2: Constraint Logic Programming

Hier ist eine zweite Version, diesmal mit Constraint Logic Programming. Constraint-Programmierung ist eine weitere exakte Lösungsmethode. Hier verwende ich ein anderes Modell:

• Erstellen Sie für jeden Teilnehmer eine Liste mit drei Variablen. Diese Variablen bezeichnen die zugewiesenen Werkstätten und haben somit die Werkstattnummern als Domäne. Alle drei Variablen müssen unterschiedliche Werte haben.

• Um Symmetrien zu brechen, erzwinge ich, dass die Variablen in ihrer Reihenfolge zunehmen müssen.

• Die unerwünschten Workshops werden aus den Domains entfernt.

• Das Binden der Variablen an die reservierten Optionen verursacht Stückkosten

• Wenn Sie einen Workshop für eine der Variablen auswählen, wird jeder überlappende Workshop aus der Domäne der anderen Variablen entfernt.

Der Schlüssel für eine erfolgreiche Constraint-Programmierung ist die Auswahl einer cleveren Markierungsstrategie, bei der die Variablen an Werte gebunden sind. Da in diesem Beispiel keine Kapazitätsengpässe für die Workshops bestehen, kann man einfach bevorzugte Workshops wählen, bis die Bereiche nur Reserve-Workshops enthalten (aufgrund der Ausschlussbeschränkungen). Entscheidend ist hier jedoch die Wertordnung: Man muss mit den Werkstätten mit der geringsten Überlappung beginnen.

Wenn dies gemacht wird, ist keine Optimierung notwendig: die erste Lösung wird optimal sein (dank fehlender Kapazitätsengpässe). Sonst wird man eine Lösung finden, die fast optimal ist, aber dann einen riesigen Suchbaum durchqueren muss, um eine bessere Lösung zu finden.

Hier ist der Code, wieder in ECLiPSe:

Beachten Sie, dass die Problemgenerierungsprädikate die gleichen wie in der MIP-Lösung sind. Hier ist die Ausgabe für einen Lauf:

Wie Sie sehen können, ist es etwas langsamer als die MIP-Lösung. Auch die tatsächliche Lösung ist etwas anders, obwohl es die gleichen Kosten hat.

Welche Version sollten Sie wählen? Es hängt davon ab, welche weiteren Einschränkungen Sie hinzufügen möchten.Wenn es sich um Kapazitätsbeschränkungen handelt, verwenden Sie MIP. Wenn es kompliziertere Einschränkungen wie die Planung von Einschränkungen gibt, ist CLP besser. Mit einem System wie ECLiPSe könnten Sie auch hybride Algorithmen konstruieren.

Einige grundlegende Anweisungen zum Nachschlagen:

Genetische Algorithmen sind ein typischer Weg, um dieses Problem zu lösen. Während sie nicht den bestmöglichen Zeitplan versprechen können. Sie können einen sicherstellen, der gut genug ist.

Dinge, auf die Sie achten sollten. Sie möchten dies ausführen, sobald alle Reservierungen vorgenommen wurden. Sie können dies nicht im Fluge tun, indem Sie jeder neuen Person einen Zeitplan geben, während sie Plätze reservieren. In der Tat wird keine Methode dies erlauben und eine optimale Lösung für das Problem erreichen.

Genetische Programmierung ist auch eine allgemeine Methode für generische Scheduler. Dies ist jedoch wahrscheinlich zu viel Aufwand, da Sie keine generische Lösung benötigen, sondern nur eine für Ihr Konferenzformat.

Wenn man annimmt, dass dies keine Spielzeugversion eines echten Problems ist (d. h. es gibt nur 6 Kurse und 3 Zeitrahmen), würde ich mit erschöpfender Suche fortfahren. Die Anzahl der Gesamtlösungen beträgt 6! / (2! 2! 2!) = 90 verschiedene Planungsoptionen. Für jede dieser Optionen können Sie eine Art von Fitness berechnen und wählen Sie die, die am besten passt.

Wenn es sich jedoch um eine Spielzeugversion eines realen Problems handelt (100s von Kursen und 10s von Zeitrahmen), dann ist das Problem schwierig und eine Kombination aus gieriger Suche und simuliertem Glühen sollte sehr hilfreich sein.

Eine andere Möglichkeit besteht darin, das Nutzerverhalten zu regulieren (durch die Verwendung von Anreizen / Strafen), damit sie auswählen, was gut für Sie ist:)