創建工作清單

Question

假設我有一份工作清單和一份日常工作清單，並且我希望爲接下來一個月的工作人員分配一份工作表，但我必須確保它是「合法」的，含義：

• 工人每天不能做一個以上的工作。
• 一個工人不能做到盡職上次負載之間的兩天休息（如果我打掃週日主辦公室，我不會做任何責任週一和週二。
• 有責任，只有管理者可以做（儘管管理者也可以做任何其他工作，但也有一些只有他們能做到）。

我知道這不是一個簡單的問題，但我正在尋找關於如何處理一些指導這種問題

Answer 1

如果同樣的責任需要每天都在做，問題就比較簡單，只有你d計算三天的時間表，然後根據需要重複。星期天打掃主要辦公室的人也會在週三，週六和下週的週二清理它。

要構建三天日程安排，首先將每個任務轉換爲三個任務，第一天和第二天各一個任務。使用Bipartite Matching將不同的人員與這些任務中的每一個相關聯。該圖將爲每個人和每個任務設定一個頂點。每個人都可以通過邊緣連接任何人都可以完成的任務。每位經理也對每位經理的任務都有優勢。

如果該問題沒有包含每個任務的邊的解決方案，那麼原始問題的前三天就沒有解決方案。