分配員工日期

這是我的初始條件：分配員工日期

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

我需要找到將允許每一位員工執行活動的最佳配置，最大限度地減少使用的日期數和給予的最大數量員工每日期。例如，如果在某個特定的日期，我可以有20名員工，我只需要使用其中的最好的10個，在另外的日期移動其他10個。

我認爲解決方案可能是一些與二分圖相關的算法，但我找不到解決它的好方法。

對於如何解決這個問題，或者如果問題可以適用於某些已知的算法，您有任何想法嗎？

非常感謝，馬爾科

來源

2016-03-25 GavynSykes

如果每一個員工進行任何* *一個活動一次，還是應該每一位員工進行*每個*活動只有一次？ – ilim

活動只有一個，它有不同的日期。所以每個員工都應該在任何日期進行活動（只有一個） – GavynSykes

這個問題似乎是一個已知的問題稱爲nurse scheduling這是衆所周知的是NP-hard。基本上你的員工和日期分別對應護士和輪班。你的硬約束是員工可用的日子，軟約束是他們工作的質量，正如你提到在你的例子中挑選最好的10。

不幸的是，我認爲你不能想到一個最佳的解決方案。根據員工和日期集合的大小，找到這樣的解決方案可能會非常棘手，而且我不認爲目前爲止只是通過您對問題的定義，而是告訴您可以使用哪種方法解決護士安排可能是最適合您的要求。儘管如此，您可以查看幾篇論文，看看它們如何適合您問題實例的具體要求。

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

來源

2016-03-25 13:51:20 ilim

好吧，我想我需要從架子上拿出我的工程書：D非常感謝！ – GavynSykes

分配員工日期

回答

相關問題