Wochenstunden Verteilung bei Mitarbeiter

[Larrywayn]

Hallöchen,
eigentlich ein banales Problem.
Es gibt mehrere Mitarbeiter, welche Arbeitszeiten haben und bestimmte Verfügbarkeiten. Zusätzlich gibt es Regeln welche beachtet werden müssen.

Die Aufgabe ist nun diesen Mitarbeitern Zeit an einer Aufgabe zuzuordnen.
Das ganze ist immer nur für eine Woche, also quasi ein Wochenplan für eine Zeitverteilung an einer Aufgabe.

Das bisherige Programm von mir funktioniert eigentlich ganz gut. Jedoch hat es das Problem, dass es nicht wissen kann, welcher Mitarbeiter, von den Möglichen, der günstigste ist, deshalb wählt es aktuell einen zufällig aus.
Dieses führt zu dem Problem, dass es die ersten 3 Tage meistens super funktioniert, aber dann oft nur Mitarbeiter verfügbar sind, welche an den tagen oder zu den Zeiten nicht können.

Nun dachte ich, dass ich für jeden Tag einen Baum erstelle, in dem ich jede Möglichkeit an einem Tag aufschlüssele.
Dann ist mir aber eingefallen, dass das Ergebnis eines Tages, die der Anderen ja total beeinflusst. Was zu dem eigentlichen Problem zurückführt.

Nun meine Frage gibt es dafür einen guten Ansatz, wie man das lösen könnte?

Meine Ideen: Das Dame Problem zur Hand nehmen und gucken ob man es auf dieses Problem projizieren kann oder ob ein zusätzlicher Baum, welcher für jeden Tag jeden anderen Tag durchgeht, genommen wird.
Das wird dann aber ziemlich Speicheraufwendig, weil jedes MitarbeiterObjekt, jede Arbeitszeit und jeder Tag zig mal als Kopie im Speicher gehalten werden muss.
Außerdem wäre es dann auch ziemlich ineffizient weil ich dann ja 5! Kombinationen alleine für de Durchgang der Tage hätte, und das dann für jede Möglichkeit eines tages auch noch.
Montag Dienstag Mittwoch Donnerstag .. Für Lösung A Montag
Montag Dienstag Mittwoch Donnerstag .. Für Lösung B Montag
Montag Dienstag Mittwoch Donnerstag .. Für Lösung C Montag
Montag Mittwoch Dienstag Donnerstag..
Montag Dienstag Donnerstag Mittwoch..
usw. ...

Vielleicht hat ja jemand einen genialen einfachen Ansatz

Grüße Larrywayn

 

[javaDeveloper2011]

Nur eine Anmerkungen:

Wenn ein Baum nicht reicht, braucht man manchmal einen Graphen, durch den "kürzeste Wege" gefunden werden müssen (ist aber nicht gerade mein Spezialgebiet)

 

[Thomas Darimont]

Hallo,

das ist eigentlich eine Variante des klassischen Scheduling Problems (Stundenplan oder Schichtplan Optimierung) mit ein paar Nebenbedingungen (wie Verfügbare Mitarbeiter an dem Tag, verfügbare Arbeitsstunden pro Mitarbeiter pro Tag / Woche / Monat, individuelle Skills der Mitarbeiter, Bewertung der Eignung eines Mitarbeiters für eine Aufgabe, Aufgaben, Anforderungen der Aufgaben, Arbeitsaufwand (je nach Skill-Level) etc.)

Man könnte hier einen klassischen Lösungsalgorithmus für Scheduling Probleme implementieren... oder man verwendet ein spezielles Planungs-/ Optimierungs- Constraint Solver Framework. Da ich persönlich solche Dinge nicht gerne selbst entwickle würde ich dir empfehlen was "von der Stange" zu nehmen.

Welche Technologie verwendest du denn in deinem Projekt? Falls es Java ist:
Schau dir doch mal JBoss Drools im speziellen Drools Planner an (http://www.jboss.org/drools/drools-planner) (Open Source).

Gruß Tom

 

[Larrywayn]

Ein Graph reicht nicht aus, denke ich, jedenfalls soweit ich Graphen verstehe. Kann sein, dass es da eine Möglichkeit gibt, aber ich wüsste in der Hinsicht keinen Ansatz, wie man den Graphen aufstellen könnte, so dass er auch ein Gesamtergebnis liefert.
Um eine unabhängige Lösung für einen Tag zu erstellen reicht er ja, aber die Tage dann noch sinnvoll zu verknüpfen wird zu komplex denke ich :/

Ich hatte inzwischen die Idee, das Problem einfach umzudrehen und nicht jedem Tag die entsprechenden Mitarbeiter zuzuordnen, sondern die Mitarbeiter durchzugehen und sie dann gleich auf die Tage zu verteilen. Das dürfte viel besser skalieren am ende und passen.

Ja ich Programmiere es in Java, da fühl ich mich am wohlsten, obwohl eine Umsetzung in eine anderen Sprache jetzt auch nicht dramatisch wäre.
Aber ja, so ein Problem ist das und eigentlich ja auch etwas recht Alltägliches, möchte man meinen^^
Das andere sieht natürlich sehr gut aus. Da werde ich mich die Tage mal reinfuchsen. Ich hoffe, dass es relativ simpel einzusetzen ist, oder zumindest Ideen liefert.
Aber aus Lernzwecken versuch ich immer lieber alles selber zu machen, anstatt Fertiges zu nehmen. Wenn ich es dann kann, kann ich auch das Fertige nehmen
Vielen Dank schon mal!

Grüße Larrywayn