Schichtplanung

[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.