Ansätze gesucht: Schichtverteilung in einem Dienstplan

[AlphaX2]

Hallo Python-Freunde,

da der Geburtstag meiner Mutter so langsam naht, hatte ich folgende Idee: Sie arbeitet im Krankenhaus und muss dort jeden Monat einen Schichtplan erstellen, was sehr müssig ist und viel Zeit kostet, folglich hab ich überlegt, ob man das nicht vereinfachen kann mit einem Programm.

Der aktuelle Stand:
Bisher habe ich eine PyQt4 GUI geschrieben, in der die Daten-Erfassung funktioniert, es wird gespeichert und steht (soweit) alles zur Verfügung was es an Daten braucht. Nun ging es an den schwersten Teil, einen Scheduling-Alogrithmus zu schreiben, der die verfügbaren Resourcen aufteilt. Vorerst hatte ich versucht es mit relativ einfachen Datenstrukturen anzugehen. Die bisherigen Ergebnisse sind weder stilistisch ideal, noch scheinen sie der noch größer werdenen Komplexität gewachsen..
Mit einem Freund habe ich dann ausgibig diskutiert, er ist der Meinung, dass das Problem mit OOP vielleicht besser zu lösen sei.

Nun dachte ich, ich frag auch hier mal nach Ideen.

Dazu noch was es leisten soll:
- Mitarbeiter die variabel anlegbar sind (im Moment 12)
- und verschiede Stunden arbeiten müssen (kommen 8, sind aber von 6-8 auf alles mögliche angestellt)
- auf drei verschiedene Schichten (Früh, Spät, Nacht)
- sowie einige extra Schichten (Mo.-Fr., Mo, Di, Mi) verteilen
- Nachtschichten sind immer von Mo.-Do. und Fr.-So.
- dabei sollten die Leute etwa 5 Tage am Stück kommen, länger (max. 10) is auch möglich
- dann 2 Tage frei haben, 1x im Monat aber auch 4-5 Tage frei am Stück
- die Schichten sollten möglichst gerecht verteilt werden (also gleiche Zahl früh, spät, nacht)
- Kurzwechsel sind verboten, wer grade noch auf Spätschicht war, darf früh nicht gleich wieder kommen
- nach einer Nacht eine Frühschicht wäre sicher auch nicht "legal"
- Natürlich sollten auch Wünsche / Urlaub berücksicht werden können!

Also wirklich nicht trivial.

Ich bin gespannt auf eure Ideen und Ansätze, Code solls ja noch gar keiner sein, erstmal nur Strukturierung und Abbildungs-Ansätze!

AlphaX2

[BlackJack]

@AlphaX2: Grundsätzlich ist so etwas nicht trivial, der Geburtstag steht also hoffentlich nicht allzu nah an.

Vielleicht ist ein erster, auch für Deine Mutter schon hilfreicher, Schritt das Ganze ohne einen automatischen Scheduler zu machen. Einen Schichtplaner der die ganzen Constraints im Auge behält und den Benutzer auf der einen Seite nichts illegales planen lässt und auf der anderen Seite die Mitarbeiter anzeigt die noch Stunden haben, welche verteilt werden müssen, kann ja auch schon eine Hilfe sein. Je nach dem wie das jetzt gelöst ist, kann das schon besser als der Status Quo sein.

Nötig ist das IMHO so oder so, denn selbst mit Scheduler muss man die Möglichkeit haben Sachen von Hand fest zu legen, die nicht vom Scheduler angetastet werden. Später kannst Du dann einen Scheduler nachrüsten, der hilft die Stunden, welche noch nicht manuell verteilt wurden unter zu bringen.

Was so ein Werkzeug auch können sollte, ist mehrere Alternativpläne zu erstellen. So dass man in der Planungsphase verschiedene Situationen durchspielen kann. Wenn Mitarbeiter A dann Urlaub macht, könnte es so aussehen; wenn er den um eine Woche verschieben kann, dann so; und so weiter.

[heiliga horsd]

Ich weiß, dass an größeren Schulen in deren Software Evolutionäre Algorithmen für die Einteilung der Klassen/Lehrkräfte/Klassenzimmer zum Einsatz kommt, um alles möglichst gut und in absehbarer Laufzeit unter einen Hut kommt. Ob sowas ratsam ist bzw. ob es bessere Möglichkeiten gibt und wie man sowas am besten realisiert können dir die Profis hier aber sicherlich besser sagen.

[AlphaX2]

Hi,

erstmal Danke für eure Rückmeldung.
@BlackJack: ein solcher Planer, der quasi assistiert, wäre sicherlich eine Verbesserung und damit auch eine Hilfe, zumal der Geburtstag ja in 2 Wochen is. Aber das war klar dass es bis dahin nicht werden würde.

Nötig ist das IMHO so oder so, denn selbst mit Scheduler muss man die Möglichkeit haben Sachen von Hand fest zu legen, die nicht vom Scheduler angetastet werden.

Das ist im Grundsatz vorhanden, also zumindest wird eine "Schichtplan" Tabelle auf der GUI erzeugt, die auch Eintragungen zulässt und die theoretisch (noch nicht implementiert) auch einlesen lassen. Auf diese Weise würde er auch die Alternativen planen können, indem man das dort eben verschieden vorgibt.

Wie gesagt, mir ginge es eben um eine OOP Struktur.

Bisher hab ich überlegt:
Vorauslader-Klasse (lädt Daten, stellt sie bereit)
Mitarbeiter-Klasse (Mitarbeiter die entscheiden, ob sie Kapazitäten haben und sich eintragen können)
Scheduler-Klasse (fragt beim Mitarbeiter an, verteilt so die Schichten, is für Ausnahmen und ähnliches zuständig)

Aber so richtig sicher bin ich mir damit nicht.

AlphaX2

[EyDu]

Der Entwurf sollte hier wirklich deine geringste Sorge sein. Im Prinzip hast du einen Bedarf an Ressourcen, zur Verfügung stehende Mittel und Beschränkungen über diese Mittel. Das ganze ist also an sich völlig trivial. Viel wichtiger ist, dass du erstmal überlegst wie du das Problem überhaupt lösen ist. Deine Problemstellung hört sich zwar unglaublich einfach ein, bei einer nicht-optimierten Herangehensweise wird jedoch niemand jemals das Ergebnis erfahren können. Erst wenn du weißt, wo du Näherungen verwenden kannst/willst und wie du diese umsetzen möchtest, musst du dir über eine konkrete Struktur gedanken machen. Dann kann man sich das Leben noch ein wenig vereinfachen.

[mcdwerner]

Hallo!

In meinem früheren Job hab ich mit so einem Tool gearbeitet, das jahrelang von einem Weltkonzern entwickelt worden ist und doch nicht richtig funktioniert hat... Letztlich haben die meisten meiner Kollegen das Programm "als Schreibmaschine missbraucht" will heissen: den Dienstplan doch "zu Fuß" erstellt und dann in die Oberfläche geschrieben.

Ich möchte Dich nicht entmutigen, sondern mein Vorschlag wäre, das Ganze noch kleinschrittiger anzugehen:
Überleg Dir, ähnlich wie von BlackJack vorgeschlagen, welche der Vorgaben für Dich am wichtigsten ist und setze sie Schritt für Schritt um. Vielleicht wäre es auch gut deine Mutter mit ins Boot zu holen (bin mir nicht sicher ob's eine Überraschung sein soll?) und mit ihr das ganze Schritt für Schritt zu entwickeln.

@ EyDu: Durch die komplexen Beziehungen der unterschiedlichen Bedingungen zu einander ist es imho schnell aus mit der Trivialität...

[AlphaX2]

Vielleicht wäre es auch gut deine Mutter mit ins Boot zu holen (bin mir nicht sicher ob's eine Überraschung sein soll?) und mit ihr das ganze Schritt für Schritt zu entwickeln.

Nein, das ist keine Überraschung, dafür hatte ich schon zuviele Fragen und Infos die ich brauchte. Irgendwie hab ich das so langsam schon befürchtet, dass es eben wirklich nicht einfach wird. Eine solche Lösung, wie BlackJack vorgeschlagen hat, dürfte vorerst schon eine Bereicherung sein.

Jedenfalls ist es mir vorerst egal wie "optimal" die Lösung ist, solange sie die Bedingungen erfüllt, denn wenn das an und für sich nur wenige Sekunden/Minuten rechnet, so wären ihr ja schon einige Stunden gespart. Nacharbeiten kann man dann ja immer noch, bzw. weiter entwickeln, so dass es noch besser wird.

AlphaX2

[lunar]

@mcdwerner: Die Bedingungen stehen imho untereinander nicht in Beziehung, es gibt keine "wenn ..., dann ..."-Einschränkungen. Mithin ist eine Lösung, die mit Backtracking unter Berücksichtigung der Bedingungen für gültige Stundenpläne alle möglichen Pläne berechnet, und diese anschließend mithilfe der Kriterien für "gute" Pläne (e.g. möglichst "gerechte" Verteilung") gewichtet, einigermaßen trivial zu schreiben, aber natürlich nicht praktikabel, da die Laufzeit zu schlecht ist.

Ich glaube, dass meinte EyDu mit "völlig trivial", und "niemand [wird] jemals das Ergebnis erfahren können".

[mcdwerner]

@ lunar:
ich kenne das so:
wenn der Mitarbeiter am Vortag Spätschicht hatte dann darf er am nächsten Tag nicht Frühschicht machen, obwohl er vielleicht an diesem Tag abends gerne frei hätte, wenn er aber an dem Tag gar nicht arbeitet dann hätte er wieder zu viel frei und dann wären die Schichten an dem Tag auch unterbesetzt, also müsste ein anderer nochmal mehr arbeiten.

Das Problem ist, dass nicht beliebig Spielraum vorhanden ist zwischen Soll- und Ist-Stunden, man muss häufig irgendwo Abstriche machen (meist bei den Wünschen der Mitarbeiter , dafür braucht es "Fingerspitzengefühl" und ein Algorithmus hilft hier nicht weiter...

[BlackJack]

@mcdwerner: Ich denke lunar meinte es gibt keine Beziehungen *unter* den Einschränkungen. Die kann man noch alle einzeln betrachten und anwenden/prüfen.

[mcdwerner]

@BlackJack und lunar:

das verstehe ich nicht:
Bedingungen "Nachtschicht geht mindestens 3 Tage" und "5 Tage am Stück soll mindestens gearbeitet werden" stehen für mich untereinander in Beziehung:
wenn wir noch davon ausgehen dass nach der Nachtschicht keine beliebige Schicht sein darf evtl. sogar mind. ein freier Tag sein muss und mindestens 2 Tage am Stück frei sein sollen ergibt sich schon folgendes Bild: die Nachtschichten stehen immer am Ende einer Arbeitsperiode eines Mitarbeiter, jetzt wollen noch Wünsche und Urlaub berücksichtigt werden und die Schichten sollen immer ausreichend besetzt sein.

Sehe ich da Beziehungen, die (logisch) gar nicht vorhanden sind?

[BlackJack]

@mcdwerner: Die beiden Bedingungen *gelten* unabhängig voneinander. Wenn Du einen Schichtplan hast, kannst Du erst die Erste und dann die Zweite getrennt voneinander prüfen. Was anderes wäre es wenn es eine Bedingung gäbe wie B0: "Wenn ein Mitarbeiter an einem Sonntag arbeitet, dann gelten folgende Bedingungen B1, B2, und B3, die sonst *nicht* gelten", dann wären diese drei Bedingungen abhängig von B0.

[mcdwerner]

ok, das habe ich jetzt verstanden
Wenn dann wäre es ein Wunsch eines Mitarbeiters:
"Ich möchte am Sonntag frei haben und wenn ich doch arbeiten muss, dann will ich wenigstens 3 Tage frei haben in dieser Woche" (und von solchen Wünschen gibt es nach meiner Erfahrung viel zu viele, oft nur implizit "Das ist doch klar dass ich da frei haben will, wenn ich dort schon gearbeitet habe...")

PS: Sorry, es könnte sein dass ich von dem Thema ein bisschen frustriert bin

[EyDu]

Man kann sich natürlich nun beliebig komplexe Bedingungen einfallen lassen, die alles mögliche mit allem anderen in Beziehung setzen. Das liegt dann allerdings auf der Seite der Constraints. Es geht kein Weg daran vorbei komplexe Sachverhalte auch komplex zu beschreiben. Dies ändert aber nichts daran, dann die Beziehung zwischen Bedarf, Beschränkungen und Resourcen weiterhin vollkommen einfach zu modellieren ist. Es lässt sich leicht nachvollziehen, welche Einheit mit welcher anderen in Verbindung steht und ob Anforderungen verletzt werden. Mit beliebig viel Zeit (und einer existierenden Lösung) wird man aber immer ein Optimum finden können.

Erst wenn es darum geht, dass das Problem in einer vorgegebenen Zeit gelöst werden soll wird es interessant. Erst bei diesen Schritt lohnt es sich überhaupt auf die Beschränkungen zu schauen und diese bei der Optimierung in Betracht zu ziehen. Deshalb habe ich darauf hingewiesen, dass man sich erst die Gedanken über die Optimierungen machen soll und dann seine Struktur darauf anpasst. Der ganze OOP-Entwurf ist im Gegensatz zu den Gedanken die man sich vorher machen muss trivial.

[AlphaX2]

Okay ich hab das Gefühl, das ganze geht grade etwas von der eigentlichen Sache weg. Im Endeffekt, so scheint mir, mangelt es mir schon an der Strategie, die (relativ) einfachen Beziehungen abzubilden. Folglich bisher ist es mir nicht(mal) gelungen einen grundsätzlich funktionierenden Plan zu erstellen, egal wie optimal.

Jetzt hab ich (wieder mal) darüber nachgedacht, wie ich das anstellen könnte. Sprich, ich wäre schon dabei über eure Hilfen sehr erfreut. Rein vom Ansatz, den Rest würde ich schon selber, zumindest versuchsweise, machen/schaffen.

AlphaX2

[EyDu]

Hier ist doch noch niemand vom Thema abgekommen, das sieht dann ganz anders aus

Die Beziehungen könntest du im einfachsten Fall als eine Liste von Funktionen abbilden. Denen übergibst du einen Plan und prüfst, ob dieser korrekt ist. Theoretisch kannst du jetzt alle Möglichkeiten des Plans durchprobieren (was natürlich unmöglich ist) und dann aufhören, wenn du die beste (wie auch immer du das definierst) Lösung gefunden hast. Das ist der einfache Teil.

Wie du schon selber festgestellt hast, liegt das Problem bereits darin eine gültige Lösung zu finden - und ggf. von dort aus weiter zu optimieren. Daher solltest du dir erstmal überlegen, wie du vorgehen würdest, wenn du den Plan von Hand erstellen müsstest. Dann schaust du dir an, wo es in deinem Plan konflikte gibt und probierst deinen Plan schrittweise zu ändern. Hier gibt es natürlich kein Patentrezept, dass Vorgehen hängt stark vom Problem ab.

Weiter ist es schwierig, eine "gute" Lösung zu finden. Du wirst feststellen, dass du eine Lösung findest, oft gehen diese jedoch stark zum Nachteil einer einzelnen Resource, was in diesem Fall einem Mitarbeiter entsprechen würde. Und natürlich musst du auch festlegen, was überhaupt eine gute Lösung ist. Da du keine konkreten Kosten im Sinne von Geld oder Zeit hast, ist das relativ beliebig und daher fast unmöglich.

Versuche dich mal in die Thematik einzulesen, Scheduling wurde als erster Ansatz ja bereits genannt. Dann musst du selber sehen, wie weit du kommst. Ich möchte dir nicht gleich am Anfang die Motivation nehmen, aber ich habe starke Zweifel, dass du bei deinem Wissenstand (das was man aus den Postings herauslesen kann) das Problem zufriedenstellen lösen kannst (und schon gar nicht in der kurzen Zeit). Ohne vernünftige Grundlagen in Algorithmik ist eine automatische Lösung zu anspruchsvoll.

[AlphaX2]

Die Beziehungen könntest du im einfachsten Fall als eine Liste von Funktionen abbilden. Denen übergibst du einen Plan und prüfst, ob dieser korrekt ist.

Das wäre ja quasi eine Möglichkeit, wenn man einen Assistenten erstellen will, der Fehler aufzeigt etc.

Wie du schon selber festgestellt hast, liegt das Problem bereits darin eine gültige Lösung zu finden...

Wie gesagt, das ist im Moment das was mir am ehesten vorschweben würde. Das wurmt mich einfach dermaßen, dass ich es versuchen will, das kann ja an sich nicht sooo furchtbar schwer sein. Ich hab auch schon einen (eher scheußlichen) Code, der im Moment zufällig Leute wählt und den nötigen Schichten jeden Tag zuordnet und danach, eben diesen Leuten erstmal frei gibt. Das gelbe vom Ei ist es dann aber doch nicht.

Wie gesagt, selbst gröbere Fehler/Unfeinheiten könnte man ja sogar händisch noch ändern.

AlphaX2

[EyDu]

das kann ja an sich nicht sooo furchtbar schwer sein.

Doch, genau das ist es.

Ich hab auch schon einen (eher scheußlichen) Code, der im Moment zufällig Leute wählt und den nötigen Schichten jeden Tag zuordnet und danach, eben diesen Leuten erstmal frei gibt.

Es wurde dir doch jetzt zweimal gesagt, dass du das am besten mit mehr Information (also im besten Fall deiner Mutter) angehst, dann musst du nicht raten. Das richtige Raten einer Lösung in eine so großen Suchraum mit vielen Constraints ist sehr unwahrscheinlich. Du musst zusehen, dass du die Anzahl der möglichen Lösungen massiv einschränkst und dann systematisch vorgehst. Oder du erstellst eine gute Lösung die nicht alle Constraints erfüllt und machst von da aus weiter. Am Ende muss dann noch ein wenig von Hand nachgebessert werden.

Hast du dir eigentlich mal den Wikipedia-Artikel zum Thema angeschaut? Vielleicht implementierst du zunächst mal zwei oder drei der genannten Verfahren, dann bekommst du ein Gefühl für den Aufwand.

[mcdwerner]

... wenn ich den Faden schon ein wenig vom Weg abgebracht habe möchte ich noch was aus meiner Erfahrung beitragen.
Ich würde versuchen den Dienstplan für eine Woche (oder besser einen Monat) mit der Hand zu schreiben, ich denke währenddessen wird dir vieles einfallen, was für das Programm wichtig sein könnte.
Mein Ansatz wäre:
Als erstes alle Wünsche und Urlaube notieren.
Dann würde ich von den Nachtschichten ausgehen, da die am stärksten eingeschränkt sind. Also versuche alle benötigten Nachtschichten so gerecht es geht auf die Mitarbeiter zu verteilen. Zu den Nachtschichten dazu kriegen die Mitarbeiter dann gleich die restlichen 5-10 Arbeitstage zugewiesen. Danach verteilst Du die verbliebenen Leute auf die verbliebenen Schichten und am Ende kommen die "Extra-Schichten". (Immer die Ruhezeiten im Auge behalten
Wie gesagt, so würde ich den Plan von Hand machen, um Ideen, Ansätze für die programmierte Lösung zu finden!

[webspider]

@mcdwerner: Wenn man nach diesem Prinzip vorgeht, wäre ein halb-automatischer Planer eine Idee. D.h. man wählt eine anfängliche Zusammenstellung aus, bekommt weitere Optionen für die logisch nächste Regel (wie dass nach Urlauben Nachtschichten festgelegt werden) angezeigt, wählt eine aus und der Vorgang wird solange wiederholt bis man entweder mit dem ersten Versuch einen guten Plan erstellt hat oder man mangels weiterer Optionen einen Schritt zurückgehen muss (wie beim Backtracking ja auch) und von dort aus einen andere Verzweigung wagt.

Das würde einem natürlich nicht so viel bringen wie eine voll-automatisierte Variante (da es einem eigentlich ja nur die möglichen Verzweigungen aufzeigt), dafür aber umsetzbarer sein und ggf. besser optimieren als ein Ansatz, der menschliche Interaktion so weit wie möglich zu reduzieren versucht.