Welcher Algorithmus (n) kann dieses Constraint-Programmierung Problem lösen?

Question

Ich brauche einen Job Affektiertheit Problem zu lösen, und ich möchte vorzugsweise effiziente Algorithmen finden, dieses Problem zu lösen.

Nehmen wir an, es gibt einige Arbeiter, die verschiedene Arten von Aufgaben tun. Wir haben auch einen Pool von Aufgaben, die jede Woche getan werden muss. Jede Aufgabe dauert einige Zeit. Jede Aufgabe muss von jemandem genommen werden. Jeder Arbeiter muss eine Woche zwischen N eine P Stunden arbeiten.

Dieser erste Teil des Problems scheint ein guter Kandidat für einen Constraint-Programmierung Algorithmus zu sein.

Aber hier ist die Komplikation: weil ein Arbeiter unterschiedliche Aufgaben ausführen kann sie auch Präferenzen haben können (oder Wünsche). Will man alle Wünsche für alle da befriedigen, ist keine Lösung für das Problem (zu viele Einschränkungen).

Also brauche ich einen Algorithmus dieses Problem zu lösen. Ich will nicht das Rad neu erfinden, wenn das perfekte Rad ist bereits vorhanden.

Der Algorithmus muss fair sein (wenn man dieses Wort definieren kann), so zum Beispiel soll ich in der Lage sein, eine Einschränkung hinzuzufügen, wie „versuchen, mindestens einen Wunsch pro Menschen zu befriedigen“. Ich bin nicht sicher, dass dieses Problem durch Constraint-Hierarchien hier beschriebenen Methoden gelöst werden kann: Constraint Herarchies . In der Tat bin ich nicht sicher, dass „Fairness“ und Wünsche können durch gültige Einschränkungen für diese Kategorie von Algorithmen ausgedrückt werden.

Sie haben einen Constraint-Programmierung Experte mir einige Ratschläge zu geben? Brauche ich ein neues Rad mit einigen Heuristiken anstelle der Verwendung effizienten CP Algorithmen zu entwickeln?

Danke!

Answer 1

Ihr Problem ist komplex genug, dass eine allgemeine Lösung wahrscheinlich Formulierung erfordert als ein linear-integer rel="nofollow Problem. Wenn auf der anderen Seite Sie bestimmte Anforderungen entspannen können, können Sie in der Lage sein, einen einfacheren Ansatz zu verwenden. Zum Beispiel bipartiter passende Ihnen erlauben würde, mehrere Arbeiter mehrere Jobs zu planen und sogar handhaben Vorlieben, sondern allgemein ‚Fairness‘ Einschränkungen erzwingen nicht in der Lage sein. Siehe z.B. diese related SO Frage . Vertex Färbung für die Durchsetzung der Auftragstrennung Zwänge effiziente Algorithmen hat.

Andere Plakate haben erwähnt simplex und Job Shop . Simplex ist ein Optimierungsalgorithmus - es durchläuft einen Lösungsraum eine Zielfunktion maximieren wollen. die Zielfunktion Formulieren kann sicher durchgeführt werden, ist aber nicht trivial. Klassische Job Shop, wie bipartiter Matching, können einige Aspekte des Problems modellieren, aber nicht alle. Es gibt keine Rangfolgeneinschränkungen, zum Beispiel. Es gibt erweiterte Versionen, die einige Einschränkungen umgehen können, zum Beispiel platzieren Zeitschranken auf Aufgaben.

Wenn Sie in bestehenden Implementierungen interessiert sind, die Python NetworkX Bibliothek verfügt über eine Implementierung von dieses Matching-Algorithmus . Ein Beispiel für ein Open-Source-Fahrplan Programm, das von Interesse sein könnte, ist Tablix .

Answer 2

Ich habe getan Fahrplan, die eine Form der Constraint-Programmierung berücksichtigt werden kann. Sie haben hart (unverletzlich) Einschränkungen und Soft Constraints (wie Intervalleinstellungen).

Linear Integer Programming in der Regel unbrauchbar wird nach mehr als 30 Variablen, und dies kann auch über simplex gesagt werden.

Es war Trog domänenspezifische Optimierungen von heuristischen Algorithmen, die eine Lösung gefunden wurde.

Die heuristischen Algorithmen waren simmulated Glühen , genetische Algorithmen , Metaheuristik Algorithmen und ähnliche, aber am Ende war das beste Ergebnis durch eine „intelligente“ Domain angepasst zur Verfügung gestellt gierige Suche Algorithmus.

Im Grunde könnte man ein paar anständigen Ergebnisse mit einem der Heuristik hier, aber das Hauptproblem ist in der Lage, zu erkennen, wenn ein Problem overconstrained wird.

Ein großes Open-Source-Tool für die Forschung ist die HeuristicLab .

Answer 3

Ich bin damit einverstanden mit dem, was hier vorgeschlagen worden. Allerdings MIP (Mixed Integer Programming Probleme) sehr großer Größe (weit über 30 Variablen!) Sind praktisch heutzutage dank kommerzielle Codes (Xpress, Cplex, Gurobi) oder Open-Source (Coin-Oder / Cbc) gelöst. Darüber hinaus Phantasie Modellierungssprachen wie OPL Studio, GAMS, AMPL, Flop ... erlauben leicht anstelle der Verwendung von APIs mathematischen Modelle zu schreiben.

Sie können die Vorteile von NEOS-Server nehmen ( http: //neos.mcs .anl.gov / neos / Löser / index.html ) zu versuchen, sehr esaily MEP zur Verfügung. Sie schicken Ihr Modell in AMPL Format. Obwohl AMPL als kostenlose limitierte Version kommt, kann NEOS unbegrenzte Instanzen behandeln.

Modellierungssprachen gibt es auch für CP (COMET / OPL Studio) und Local Search (COMET).

Sie können ferner in Kontakt treten mit mir durch meine Website www.rostudel.com ( ‚Kontakt‘ Seite)

David

Answer 4

Das klingt wie Job Shop rel="nofollow.