Assign Mitarbeiter Daten

Question

Das ist mein Ausgangszustand:

I have a set of employees E1, E2, E3, ... 
I have a set of dates for an activity D1, D2, D3, ... 
For every employee, I know on which dates he is available to perform the activity 
Every employee should perform the activity only once 

Ich brauche die beste Konfiguration zu finden, die jedem Mitarbeiter ermöglichen, wird die Aktivität durchzuführen, um die Anzahl der Tage, zu minimieren und eine maximale Anzahl des Gebens Mitarbeiter pro Tag. Wenn zum Beispiel an einem bestimmten Datum 20 Mitarbeiter arbeiten können, muss ich nur die besten 10 von ihnen verwenden und die anderen 10 an verschiedenen Daten verschieben.

Ich denke, die Lösung könnte ein Algorithmus sein, der sich auf bipartite Graphen bezieht, aber ich kann keinen guten Ansatz finden, um es zu lösen.

Haben Sie eine Idee, wie Sie es lösen können oder ob das Problem in einen bereits bekannten Algorithmus passen könnte?

Vielen Dank, Marco

Answer 1

Dieses Problem scheint ein bekanntes Problem genannt nurse scheduling die NP-hard sein bekannt zu werden. Grundsätzlich entsprechen Ihre Mitarbeiter und Termine Krankenpflegern bzw. Schichten. Ihre harten Bedingungen sind die Tage der Verfügbarkeit der Mitarbeiter und weichen Einschränkungen sind die Qualität ihrer Arbeit, wie Sie erwähnt die besten 10 in Ihrem Beispiel genannt.

Leider glaube ich nicht, dass Sie eine optimale Lösung von oben nach unten denken können. Je nach Größe der Mitarbeiter und Daten kann es schwierig sein, eine solche Lösung zu finden, und ich glaube nicht, dass allein durch die Definition des Problems es möglich wäre, zu sagen, welche Methode dafür geeignet ist Die Planung der Pflegekräfte kann für Ihre Anforderungen am besten geeignet sein.

Nichtsdestoweniger, hier sind ein paar Papiere, die Sie sehen können und sehen, wie sie den spezifischen Anforderungen Ihrer Instanz des Problems entsprechen.

A grasp-knapsack hybrid for a nurse-scheduling problem

A two-phase adaptive variable neighborhood approach for nurse rostering

An Indirect Genetic Algorithm for a Nurse Scheduling Problem