Welcher Algorithmus für die Zuordnung von Verschiebungen (diskretes Optimierungsproblem)

Question

Ich entwickle eine Anwendung, die optimal Verschiebungen zu Krankenschwestern in einem Krankenhaus zuweist. Ich glaube, dies ist ein lineare Programmierung Problem mit diskreten Variablen, und daher wahrscheinlich NP-hard:

• Für jeden Tag, jede Krankenschwester (ca. 15-20) zugeordnet ist, eine Verschiebung
• Es gibt eine kleine Zahl (ca. 6) aus verschiedenen Schichten
• Es gibt eine beträchtliche Anzahl von Einschränkungen und Optimierungskriterien, entweder über einen Tag oder über eine emplyoee, z.B .:
  • Es muss eine Mindestanzahl von Personen zu jeder Schicht jeden Tag
  zugewiesen sein
  • überlappen Einige Verschiebungen, so dass es in Ordnung ist in Frühschicht einer Person weniger zu haben, wenn jemand tut Zwischen Verschiebung gibt es
  • bevorzugen Einige Leute Frühschicht, einige Spätschicht bevorzugen, aber ein Minimum an Schichtwechsel ist erforderlich, um noch die höheren Schichtarbeit Lohn zu erhalten.
  • Es ist nicht für eine Person erlaubt Spätschicht einen Tag zu arbeiten und früh am nächsten Tag verschieben (wegen Mindestruhezeitregelungen)
  • Meeting zugewiesen Arbeitswoche Längen (für verschiedene Personen)
  • ...

Also im Grunde gibt es eine große Anzahl (aout 20 * 30 = 600) Variablen, die jeweils eine kleine Anzahl diskreter Werte annehmen können.

Zur Zeit mein Plan ist eine modifizierte Min-Konflikte Algorithmus verwenden

• beginnen mit zufälligen Zuweisungen
• haben eine Fitness-Funktion für jede Person und jeden Tag
• Wählen Sie die Person oder Tag mit dem schlechtesten Fitness-Wert
• Wählen Sie nach dem Zufallsprinzip einer der Zuweisungen für diesen Tag / Person und stellen Sie den Wert, der in der optimalen Fitness-Wert
Ergebnisse
• wiederholen, bis entweder eine maximale Anzahl von Iterationen erreicht ist oder keine Verbesserung kann für den ausgewählten Tag / Person gefunden werden

Jede bessere Ideen? Ich bin etwas besorgt, dass es in einem lokalen Optimum stecken wird. Sollte ich irgendeine Form von simulierten Glühen ? Oder betrachten sie nicht nur Änderungen in einer Variablen zu einer Zeit, aber speziell schaltet die Verschiebungen zwischen zwei Personen (die Hauptkomponente in dem aktuellen manuellen Algorithmus)? Ich möchte den Algorithmus auf die aktuellen Einschränkungen zu vermeiden, Schneiderei da diese ändern können.

Edit: ist es nicht notwendig, eine streng optimale Lösung zu finden; Die Liste wird derzeit manuell getan, und ich bin mir ziemlich sicher, dass das Ergebnis deutlich suboptimal die meiste Zeit - sollte nicht schwer sein, das zu schlagen. Kurzfristige Anpassung und Handnotbetätigungen werden auch auf jeden Fall notwendig, aber ich glaube nicht das ein Problem sein wird; Kennzeichnung Vergangenheit und manuelle Aufgaben als „fixed“ soll eigentlich die Aufgabe vereinfachen, indem den Lösungsraum zu reduzieren.

Answer 1

Dies ist ein schwieriges Problem auch zu lösen. Es hat viele wissenschaftlichen Arbeiten zu diesem Thema vor allem in den Operations Research Feld gewesen - siehe zum Beispiel Krankenschwester rostering Papiere 2007-2008 oder einfach nur google „Krankenschwester rostering Operationen Forschung". Die Komplexität hängt auch von Aspekten wie zum Beispiel: wie viele Tage zu lösen; welche Art von „Anfragen“ kann die Krankenschwester machen; ist der Dienstplan „zyklisch“; ist es ein Plan langfristig oder braucht es kurzfristig rostering „reparieren“ wie Krankheit und Swaps etc etc.

zu handhaben

Der Algorithmus Sie beschreiben, ist ein heuristische Ansatz. Sie können feststellen, können Sie es zwicken auch des Problems für eine bestimmte Instanz zu arbeiten, aber sobald „etwas“ geändert wird, kann es nicht so gut (zum Beispiel lokale optima, schlechte Konvergenz) arbeiten.

Allerdings ist eine solche Vorgehensweise kann ausreichend sein, Ihre speziellen Geschäftsanforderungen abhängig - z.B. wie wichtig es ist, die optimal Lösung zu erhalten, ist das Problem outline Sie erwartet beschreiben gleich zu bleiben, was das Einsparpotential ist (Geld und Ressourcen), wie wichtig ist die Wahrnehmung der Krankenschwester der Qualität der ihre Dienstpläne, was das Budget für diese Arbeit ist usw.

Answer 2

Umm, wussten Sie, dass einige ILP-Löser machen einen recht guten Job? Versuchen Sie AIMMS, Mathematica oder die GNU Programmier-Kit! 600 Variablen sind natürlich viel mehr als der Lenstra Satz leicht lösen, aber manchmal diese ILP-Löser haben einen guten Griff und in AIMMS, können Sie die Verzweigung Strategie ein wenig verändern. Plus, es ist eine wirklich schnelle 100% -Anpassung für ILPs.

Answer 3

Ich löste eine Verschiebung Zuordnungsproblem für eine große Produktionsstätte vor kurzem. Zunächst haben wir versucht, rein zufälligen Zeitpläne zu erzeugen und eine beliebige Rückkehr, die den is_schedule_valid Test bestanden - den Fehler Algorithmus. Dies war natürlich, langsam und unbestimmt.

Als nächstes werden wir genetische Algorithmen versuchen (wie Sie vorgeschlagen), konnten aber nicht eine gute Fitness-Funktion finden, die auf jeder tragfähigen Lösung geschlossen (weil die kleinste Änderung die gesamten Zeitplan richtig oder falsch machen kann - keine Punkte für fast).

Schließlich wählten wir die folgende Methode (das hat super funktioniert!):

1. Randomize den Eingangssatz (das heißt Arbeitsplätze, verschiebung, Personal, etc.).
2. Erstellen Sie ein gültiges Tupel und fügen Sie es zu Ihrem vorläufigen Zeitplan.
3. Wenn nicht gültig Tupel erzeugt werden kann, Rollbacks (und Erhöhung) die letzte Tupel hinzugefügt.
4. Führen Sie den Teilplan zu einer Funktion, die could_schedule_be_valid Tests, das heißt, könnte dieser Zeitplan gültig, wenn die verbleibenden Tupeln in einer Art und Weise gefüllt wurden
5. Wenn !could_schedule_be_valid, Rollback einfach (und Schrittweite), um die Tupel hinzugefügt in (2).
6. Wenn schedule_is_complete, return schedule
7. Goto (2)

Sie bauen schrittweise eine Teilverschiebung auf diese Weise. Der Vorteil ist, dass einige Tests für gültigen Zeitplan können leicht in Schritt 2 (Pre-Tests) durchgeführt werden, und andere müssen in Schritt 5 (post-Tests) bleiben.

Viel Glück. Wir verschwendeten Tage, um die ersten beiden Algorithmen versuchen, bekam aber den empfohlenen Algorithmus gültig Pläne sofort in weniger als 5 Stunden der Entwicklung erzeugt wird.

Auch wir unterstützten Vorfixierung und Post-Fixierung von Aufgaben, die der Algorithmus würde respektieren. Sie einfach nicht zufällig nicht die Slots in Schritt 1. Sie finden, dass die Lösungen nicht in der Nähe optimal sein muss. Unsere Lösung ist O (N * M) auf ein Minimum, sondern führt in PHP (!) In weniger als einer halben Sekunde für eine gesamte Produktionsanlage. Die Schönheit ist in Ausschluss schlecht Pläne schnell einen guten could_schedule_be_valid Test.

Die Leute, die manuell zu tun, es verwendet werden, egal, ob es eine Stunde dauert -. Sie wissen nur, sie müssen es nicht tun manuell mehr

Answer 4

Mike,

Sie wissen nicht, ob Sie jemals eine gute Antwort auf diese Frage bekam, aber ich bin mir ziemlich sicher, dass Constraint-Programmierung das Ticket. Während ein GA Ihnen eine Antwort geben könnte, ist CP Ihnen viele Antworten zu geben oder Ihnen sagen, wenn es keine praktikable Lösung. Eine Suche auf „Constraint-Programmierung“ und Terminierung sollte viele Informationen bringen. Es ist ein relativ neues Gebiet und CP Methoden auf viele Arten von Problemen gut funktionieren, wo traditionelle Optimierungsmethoden versinken.

Answer 5

Dynamische Programmierung a la Glocke? klingt ein bisschen wie es ein Platz für sie ist. überlappende Teilprobleme, optimale Unterbauten

Answer 6

Eine Sache, die Sie tun können, ist zu versuchen, für Symmetrien in dem Problem zu suchen. Z.B. können Sie alle Krankenschwestern als gleichwertig für die Zwecke des Problems behandeln? Wenn ja, dann müssen Sie nur Krankenschwestern in einer beliebigen Reihenfolge betrachten - Sie Lösungen unter Berücksichtigung vermeiden können, so dass jede Krankenschwester i vor jeder Krankenschwester geplant ist j , wobei i > j . (Sie sagten, dass einzelne Krankenschwestern Schaltzeiten bevorzugt haben, die in diesem Beispiel widerspricht, wenn auch vielleicht ist das ein weniger wichtiges Ziel?)

Answer 7

Ich denke, Sie sollten genetischen Algorithmus verwenden, 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 Strafen Eignung 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 das Programm zu verbringen beabsichtigen, zu lösen ..

  Genetische Algorithmen Definition

  Genetische Algorithmen Tutorial

  Klasse Scheduling-Projekt mit GA

Schauen Sie auch unter: einer ähnlichen Frage und ein anderer

Answer 8

Mit CSP Programmierung Ich habe Programme für die automatische shitfs rostering. zB:

1. 2-Schichten-System - getestet für mehr als 100 Krankenschwestern, 30 Tage Zeithorizont, 10+ Regeln
2. 3-Schichten-System - getestet für 80+ Krankenschwestern, 30 Tage Zeithorizont, 10+ Regeln
3. 3-Schichten-System, 4-Teams - getestet für 365 Tage Horizont, 10+ Regeln,

und ein paar similiar Systeme. Alle von ihnen wurden auf meinem Heim-PC (1,8 GHz Dual-Core) getestet. Ausführungszeiten waren immer akzeptabel dh. 3 / es dauerte etwa 5 min und 300 MB RAM.

Die meisten Fest Teil dieses Problem richtige Löser und richtige Lösungsstrategie auswählen.

Answer 9

Metaheuristics hat sehr gut auf die Internationale Krankenschwester Rostering Competition 2010 .

Für eine Implementierung finden Sie in diesem Video mit einer kontinuierlichen Krankenschwester rostering (Java) .