Schichtplanung

[Rülps]

Hallo zusammen,

ich bin gerade an einem Punkt, wo ich an meine "Sich-einen-Algorithmus-ausdenken"-Grenze gestoßen bin. Ich arbeite seit einem Jahr in einem Krankenhaus, in dem 365 Tage im Jahr 24 Stunden am Tag 2 Service-Engineers anwesend sein müssen. Die Schichtplanung ist eine Katastrophe und meine Chefin ist auch am verzweifeln hier eine Systematik hineinzubekommen.

Vorneweg, ich habe bereits einige Schichtplanungs-Demoversionen getestet. Diese sind für unsere Planung aber nicht geeigent. Naja, zumindest die, die ich ausprobiert habe. Das Problem ist, dass diese schon ein Schichtmodell voraussetzen, um eine automatische Genrierung durchführen zu können. Mir geht es aber darum ein "optimiertes" Schichtmodell zu berechnen.

Die Aufgabe ist 11 Mitarbeiter so zu verplanen, dass für alle drei Schichten (Früh 6:00-14:00, Spät 14:00-22:00, Nacht 22:00-6:00) immer zwei Mitarbeiter vorhanden sind. Die Wochenarbeitstunden dürfen maximal 50 Stunden betragen, wobei hier natürlich ein Ausgleich geschaffen werden muss, d.h. wenn in einer Woche 50 Stunden gearbeitet wurde, in einer anderen dafür nur 30 gearbeitet werden muss. Ein weiteres Optimierungskriterium ist, dass jeder Mitarbeiter soviele Wochenenden wie möglich frei hat. Es gibt noch mehrere "Regeln", die in einen solchen Algorithmus einfließen müssten, wie z.B. die Einhaltung der Ruhepausen, d.h. von einer Spätschicht direkt auf eine Frühschicht wechseln geht nicht, weil dazwischen nur 8 Stunden liegen, aber im Moment geht es mir noch um die Herangehensweise.

Wie geht man dabei vor? Rekursion? Neuronale Netze Wie gesagt, ich habe momentan noch nicht mal einen Ansatz und bin für jede Idee offen.

[BUG]

Prinzipiell würde ich in Richtung Graphentheorie gucken. Scheduling ist da auf jeden Fall ein Thema. Ich würde da an ein Färbungs-Problem denken. Allerdings fällt mir ad-hoc nichts ein, was genau passen würde (Ich bin leider auch kein Experte).

Als ersten Ansatz würde ich die Zeitslots als Knoten modellieren und alle Slots die nicht vom gleichen Mitarbeiter ausgefüllt werden können mit einer Kante verbinden. Dann suchst du eine 11-Färbung des Graphen, so dass alle Farben ungefähr gleich oft vorkommen (insbesondere an den Wochenenden).

Achtung: Färbungsprobleme sind im allgemeinen nicht ganz einfach. Da könntest dir da durchaus ein NP-schweres Problem angelacht haben.

[Robotiker]

Von der Größenordnung her, nur 11 Mitarbeiter, ist das Problem noch in einem Bereich, wo ein Constraint-Solver das hinkriegen müsste.

Für Delphi kenne ich keinen, aber das .net Framework hat einen, also würde Prism gehen.

http://msdn.microsoft.com/en-us/devlabs/hh145003.aspx

[sx2008]

Du könntest eine Monte-Carlo Methode einsetzen.
Jeder Mitarbeiter wird als Objekt modelliert und besitzt einen "Score".
Je höher der Score, umso ungünstiger sind die Arbeitszeiten für den Mitarbeiter.
Bei einer Verletzung einer harten Regel (z.B. >50Std/Woche) ist der Score besonders hoch.

Die Mitarbeiter-Objekte befinden sich in einer Liste und werden auf "Ungleichheit" geprüft.
Dazu wird zuerst der Durchschnitts-Score über alle Mitarbeiter berechnet.
Die Abweichung wird für jeden Mitarbeiter so berechnet: (Score-Durchschnitt)^2
Die Summe dieses Quadrate ist die "Ungleichheit".

Zu Beginn des Algorithmus werden die Arbeitszeiten rein zufällig verteilt.
Dabei ergeben sich natürlich Ungerechtigkeiten und Regelverletzungen.
Es wird die Ungleichheit berechnet.
Führt man dies in einer Schleife aus, dann merkt man sich immer nur den Schichtplan mit der niedrigsten Ungleichheit sowie den Wert der Ungleichheit.

Nach ungefähr 1000 Durchläufen hat man schon einen recht guten Schichtplan.
Dann macht man weiter, aber diesmal werden nur Arbeitszeiten 2er zufälliger Mitarbeiter getauscht und geschaut ob dieser Schichtplan weniger ungleich als der Vorgänger ist.
Falls ja, wird der weniger ungleiche Schichtplan zum aktuellen Kandidaten.

Der Algorithmus bricht ab, falls die Ungleichheit eine untere Schranke erreicht oder vom Benutzer beendet wird.

Dieses Verfahren liefert nicht zwingend den allerbesten Schichtplan aber man ist doch sehr nah an der besten Lösung.
Der Schichtplan wird gerechter sein als wenn er vom Chef vorgegeben würde oder ausgelost wäre.

Der Algorithmus funktioniert auch bei sehr komplexen Regeln wenn andere Algorithmen wegen hohen Anzahl an Schritten längst aufgeben müssen.

[Bummi]

Shima ist mir zuvor gekommen, ich hatte einen ähnlichen Ansatz erwogen.

Die Mitarbeiter können Präferenzen hinterlegen die mit einem Faktor belegt werden:
durchgebende Schichten
Präferenz pro Wochentag
Präferenz für die 3 Schichten
etc.

Die Tabelle
Datum,Schicht,Ma > 1.1.2012,1,11
Datum,Schicht,Ma > 1.1.2012,2,10
Datum,Schicht,Ma > 1.1.2012,3,1
Datum,Schicht,Ma > 2.1.2012,1,11
....
wird vorbelegt mich Wünschen der Mitarbeiter
Danach wird die Tabelle interativ durchgegangen und für jeden Mitarbeiter jedes mal eine Gewichtung berechnet aus Präferenzen unter Berücksichtigung von Tag/Schicht/Schicht Vortag<>durchgehende Schichten/Wochenstunden/2-Wochenstunden(<=80)/Monatsstunden/Urlaub etc.

Der Mitarbeiter mit der höchsten Präferenz wird zugeteilt, nächster Satz gleiches Spiel.

Das Problem wird sein die Gewichtungen sinnvoll zu verrechnen.

[Rülps]

Vielen Dank für die guten Tipps Ich muss mich noch mehr damit beschäftigen, um detaillierter nachfragen zu können, aber generell gefällt mir der Monte-Carlo-Ansatz sehr gut.

Zitat von sx2008:

Die Mitarbeiter-Objekte befinden sich in einer Liste und werden auf "Ungleichheit" geprüft. Dazu wird zuerst der Durchschnitts-Score über alle Mitarbeiter berechnet. Die Abweichung wird für jeden Mitarbeiter so berechnet: (Score-Durchschnitt)^2 Die Summe dieses Quadrate ist die "Ungleichheit".

Ich habe hier ein Verständnisproblem: Mitarbeiter zufällig auf Schichten zu verteilen ist kein Problem. Auch habe ich das mit dem Score prinzipiell verstanden. Was aber umfasst ein Mitarbeiter-Objekt und die Listen. Worüber führe ich eine Schleife aus? Das habe ich nicht so ganz verstanden. Hier habe ich noch einen Knoten im Hirn...

[sx2008]

Zitat von Rülps:

Ich habe hier ein Verständnisproblem: Mitarbeiter zufällig auf Schichten zu verteilen ist kein Problem. Auch habe ich das mit dem Score prinzipiell verstanden. Was aber umfasst ein Mitarbeiter-Objekt und die Listen. Worüber führe ich eine Schleife aus? Das habe ich nicht so ganz verstanden. Hier habe ich noch einen Knoten im Hirn...

Man kann den Algorithmus rein prozedural, also mit Standard-Pascal, oder objekt-orientiert programmieren.
Falls man sich für objekt-orientiert entscheidet, würde man eine Klasse TMitarbeiter erstellen und daraus pro Mitarbeiter ein Objekt erzeugen.
Um die 11 Mitarbeiter-Objekte zu verwalten könnte man diese in einer TObjectList halten. (das war die angesprochene "Liste")
Beim Erzeugen der Mitarbeiter-Objekte könnte man bestimmte Eigenschaften wie z.B. das Alter oder Anzahl der Kinder setzen.
Vielleicht soll auf ältere Mitarbeiter oder Mitarbeiter mit Kindern im Schichtplan besondere Rücksicht genommen werden.
Wie gesagt, man kann das so machen, muss aber nicht.

Mit der Schleife ist gemeint, dass die Schritte des Algorithmus öfters wiederholt werden müssen.
So sieht der 1. Abschnitt des Algorithmus aus, bei dem versucht wird durch blindes Ausprobieren zufälliger Schichtpläne einen möglicht guten Startpunkt zu finden:

Delphi-Quellcode:

ErzeugeZufaelligenSchichtplan(oldplan);
oldscore := BerechneUngleichheitScore(oldplan);
for i := 1 to 1000 do
begin
  ErzeugeZufaelligenSchichtplan(aktplan);
  aktscore := BerechneUngleichheitScore(aktplan);
  if aktscore < oldscore then
  begin
    // besseren Plan gefunden
    CopyPlan(aktplan, oldplan);
    oldscore := aktscore;
  end;
end;

[DanielJ]

Hallo,

wir haben gute Erfahrungen bei der Schichtplanung mit Evolutionären Algorithmen
bei ´nem 150 MA-Callcenter gemacht.

In Anbetracht der Geringen Anzahl an Teilnehmern könnte ich mir vorstellen das auch eine deterministische Lösung im Bereich des Möglichen liegt - so ein Planung kann ja auch über nacht laufen.

LG,
Daniel

[ConstantGardener]

@DanielJ

...jupp in diese Richtung (Genetische Algorithmen) würde ich auch gehen. Das Problem dabei ist halt die Fitnessfunktion und die Gewichte der einzelnen Regeln.

Aber stimmt schon: bei 11 Mitarbeitern vielleicht etwas Overkill.

[shmia]

Zitat von ConstantGardener:

...jupp in diese Richtung (Genetische Algorithmen) würde ich auch gehen. Das Problem dabei ist halt die Fitnessfunktion ...

Wobei man aufpassen muss was optimiert wird.
Sonst gibt es am Ende nur noch einen einzigen Mitarbeiter, der jeden Tag frei hat.
(alle anderen sind den genetischen Tod gestorben)