Constraint-Programmierung
Dienst- oder Stundenpläne haben so viele Regeln, dass bereits ein machbarer Plan die Hürde ist. Genau dafür gibt es Constraint-Programmierung.
- Kostenloses 30-Minuten-Gespräch
- Unverbindlich
- Der Code gehört Ihnen
Kurz erklärt: Die Constraint-Programmierung (CP) ist ein Verfahren für Probleme mit vielen harten Bedingungen, etwa Dienstpläne und Stundenpläne. Jede Regel streicht die Möglichkeiten, die nicht gehen, bis nur noch Pläne übrig sind, die keine Regel verletzen.
Das Problem
Sie planen den Dienstplan für den nächsten Monat. Jede Schicht muss besetzt sein, und jede Pflegekraft hat einen Vertrag und freie Tage. Auf eine Nachtschicht darf keine Frühschicht folgen. Die meiste Zeit fliesst in die Suche nach einer Version, die keine Regel verletzt. Ob diese Version auch gut ist, fragt danach kaum jemand.
Was sich ändert
Stand jetzt verschieben Sie Schichten von Hand, bis der Dienstplan endlich alle Regeln einhält. Unser Modell findet einen Plan, der alle Regeln einhält, und verbessert ihn weiter. Sie beginnen mit einem Plan, der schon funktioniert. Ihre Zeit nutzen Sie für die Entscheidungen, die nur Sie treffen können.
So funktioniert es
Constraint-Programmierung (CP) arbeitet anders als gemischt-ganzzahlige Optimierung (MILP nach dem englischen Mixed-Integer Linear Programming). MILP schreibt den Plan als Gleichungen und sucht den günstigsten. CP betrachtet die möglichen Werte jeder Entscheidung, etwa welche Schichten Anna übernehmen kann. Jede Regel streicht schnell die Werte, die nicht gehen. So engt jede Wahl die nächste ein. Am Ende bleiben nur zulässige Pläne übrig: Pläne, die jede Regel einhalten.
Das macht CP stark bei kombinatorischen Problemen wie Dienstplänen, Stundenplänen und Produktkonfigurationen. Dort explodiert die Zahl der Kombinationen, und viele Regeln sind nicht verhandelbar. Wir arbeiten mit OR-Tools CP-SAT (kurz für Constraint Programming mit Boolean Satisfiability) und IBM CP Optimizer. Sie erhalten einen Plan, in dem jede dieser Regeln gilt.
CP-SAT oder ein MILP-Solver?
Die meisten Vergleiche im Internet enden mit «kommt darauf an». Meist kommt es darauf an, wovon Ihre Regeln handeln. CP-SAT ist stark, wenn sich die Regeln um Zeit und Reihenfolge drehen. Eine Schicht oder ein Auftrag wird zum Intervall mit Start, Ende und Dauer. Eine einzige NoOverlap-Regel sagt dann, dass eine Maschine nie zwei Aufträge gleichzeitig bearbeitet. In MILP bräuchte es dafür einen ganzen Stapel Ein-aus-Regeln.
Zwei Haken sollten Sie vorher kennen. Laut Dokumentation von OR-Tools rechnet CP-SAT nur mit ganzen Zahlen. Preise mit Rappen oder Zeiten mit Kommastellen rechnen wir also um, zum Beispiel 2.50 Franken in 250 Rappen. Und die Grösse zählt. Im Forum von INFORMS, dem Fachverband für Operations Research, berichtet ein Praktiker von seinem Problem. CP-SAT bewältigte es, bis es einige hunderttausend Variablen hatte, also einzelne Entscheidungen im Modell.
Die ehrliche Grenze: Manchmal zählt das Ziel mehr als das Einhalten der Regeln, etwa wenn die Kosten am wichtigsten sind. Dann ist MILP oft stärker. MILP berechnet auch eine Schranke, einen Wert, den kein Plan unterbieten kann. Seine Schranke liegt meist näher am besten Plan, darum zeigt MILP früher, dass ein Plan der beste ist. Können wir das nicht im Voraus sagen, rechnen wir beide Verfahren mit Ihren Daten einer Woche und lassen die Ergebnisse entscheiden.
Wann diese Methode nicht passt
Die ehrliche Grenze: Manchmal zählt das Ziel mehr als das Einhalten der Regeln, etwa wenn die Kosten am wichtigsten sind. Dann ist MILP oft stärker.
Häufige Fragen.
Etwas anderes? Fragen Sie uns direkt.
Es optimiert. Eine Antwort auf Operations Research Stack Exchange nennt CP-SAT einen vollwertigen Solver für ganzzahlige Optimierung. Sie zählt dieselben Bausteine auf, die auch MILP-Solver nutzen: Vorverarbeitung, Schnitte und lineare Relaxation. Dieselbe Antwort sagt, dass CP-SAT beim Auflisten aller zulässigen Pläne schwächer ist. Sie rät auch, CP-SAT mit acht Threads rechnen zu lassen, also auf mehreren Prozessorkernen gleichzeitig.
Harte Bedingungen muss der Plan immer einhalten. Weiche Bedingungen sind Wünsche. Für jeden Wunsch, den der Plan nicht erfüllt, zählt das Modell Strafpunkte. Wie viele Punkte ein Wunsch zählt, legen Sie fest. Ein verpasster freier Tag kann zum Beispiel weniger zählen als ungleich verteilte Wochenenden. Der Solver erfüllt dann so viele Wünsche, wie die harten Bedingungen zulassen. Der Bericht zeigt, welche Wünsche er nicht erfüllen konnte.
Selten in einem Stück. Ein Jahr lässt sich meist in Monate oder Wochen teilen, und Jahressummen wie Ferientage werden von Teil zu Teil weitergegeben. Manche sehr grossen Dienstpläne rechnet man als MILP-Modell, also mit Gleichungen. Dafür empfehlen Antworten auf Operations Research Stack Exchange die Spaltengenerierung. Sie baut den Plan aus ganzen Schichtmustern. Wir testen mit Ihren Daten eines Monats, bevor wir das ganze Jahr rechnen.
Weil der Beweis viel länger dauern kann als die Suche. CP-SAT findet einen sehr guten Dienstplan, muss danach aber noch beweisen, dass kein besserer existiert. Die Dokumentation von OR-Tools empfiehlt genau deshalb ein Limit. Läuft die Zeit ab, erhalten Sie den besten bis dahin gefundenen Plan. Wir wählen das Limit nach Ihrem Planungsfenster, nicht nach einer Voreinstellung.
Manchmal schon, und dann sagen wir es. Standardtools sind aber für ein durchschnittliches Problem gebaut. Bei Constraint-Programmierung gehen wir von Ihrem Problem aus: von seiner Grösse, seinen Regeln und den Ausnahmen, die nirgends aufgeschrieben sind. Darum passt der Plan besser zu Ihrem Betrieb.
Für den Start brauchen Sie beides nicht. Wir bauen das Modell aus den Daten, die Sie haben, ob ordentlich oder nicht, und das Aufräumen gehört zur Arbeit. Sie erhalten ein dokumentiertes System, das Ihr Team pflegen kann. Wir schulen Ihr Team, bis es das System auch nach dem Projekt selbst betreut.
Am Anfang steht ein kostenloses 30-Minuten-Gespräch über Ihren Betrieb und das passende Modell. Dann bauen wir einen funktionierenden Prototyp und lassen ihn mit Ihren Zahlen rechnen. Sie sehen Ergebnisse, bevor Sie sich auf etwas Grösseres festlegen.
Ähnliche Seiten.
Begriffe auf dieser Seite
Jede Abkürzung in einfachen Worten erklärt, in unserem Beitrag «Metriken und Methoden».
- MILPGemischt-ganzzahlige lineare Optimierung
- CPConstraint-Programmierung
- CP-SATCP-SAT-Solver
- OR-ToolsGoogle OR-Tools
Erzählen Sie uns, was Sie planen.
In einem kostenlosen 30-Minuten-Gespräch mit einem Spezialisten finden Sie heraus, ob Optimierung Ihnen helfen kann.
- Kostenlos und unverbindlich
- Sie sprechen direkt mit einem Spezialisten
- Ein klares Ja oder Nein