Ansätze gesucht: Schichtverteilung in einem Dienstplan

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
EyDu
User
Beiträge: 4881
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

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.
Das Leben ist wie ein Tennisball.
AlphaX2
User
Beiträge: 53
Registriert: Dienstag 28. Juni 2011, 10:42

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
User
Beiträge: 4881
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

AlphaX2 hat geschrieben:das kann ja an sich nicht sooo furchtbar schwer sein.
Doch, genau das ist es.

AlphaX2 hat geschrieben: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.
Das Leben ist wie ein Tennisball.
mcdwerner
User
Beiträge: 113
Registriert: Donnerstag 7. Juli 2011, 14:27

... 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
User
Beiträge: 485
Registriert: Sonntag 19. Juni 2011, 13:41

@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.
Leonidas
Python-Forum Veteran
Beiträge: 16025
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

EyDu hat geschrieben:Hier ist doch noch niemand vom Thema abgekommen, das sieht dann ganz anders aus ;-)
Richtig, solange keiner eine Lösung in einer zumindest mittelmäßig esoterischen Sprache gepostet hat, ists On-Topic ;)
EyDu hat geschrieben:
AlphaX2 hat geschrieben:das kann ja an sich nicht sooo furchtbar schwer sein.
Doch, genau das ist es.
Du hast eben genau eines der interessanten Probleme gefunden, die einfach wirken, aber schwer sind. Der triviale Ansatz ist natürlich, alle möglichen Kombinationen des Planes zu generieren (du kannst ja mal ausrechnen wie viele es sind) und sie zu testen und gucken wie viele der Constraints verletzt verletzt sind und die Lösungen nach anzahl verletzter Constraints ordnen. Das Problem ist, dass in realistischen Szenarios die Anzahl der Kombinationen riesengroß ist.
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
deets

Ich würde von dem Versuch einer automatischen Problemlösung absehen. Stattdessen - wie ja schon hier erwähnt - nur die constraints für eine gegebene Lösung validieren lassen.

Der Grund ist - neben der inzwischen hoffentlich ersichtlichen Komplexität - dass du ebendiese constraints in ihrer Gänze nie wirst fassen können. Da gibt's dann zb Kollegin A, die ein kleines Kind hat, und darum wenn möglich Konstante Schichten kriegt. Und Kollege B braucht wegen dem Neugebauten Haus die lukrativen nachtschichten.

Deine Mutter wird all dies intuitiv berücksichtigen. Wenn du ihr also helfen willst, dann steckt die Arbeit also in einer intuitiven Oberfläche. Glaub mir - da kannst du Monate dran feilen...

Einen solchen scheduler wirklich zu benutzen lohnt imho nur dann, wenn die Optimierung richtig Geld bringt. Zb flugpläne & wartungszeiten von Flugzeugen. Da geht es um Millionen. Und dementsprechend werden die Menschen & ihre Bedürfnisse halt dem plan unterworfen. Come hell or highwater.
jeremydon
User
Beiträge: 2
Registriert: Donnerstag 23. August 2012, 15:06

hast du das problem lösen können?
Antworten