作業調度問題

Question

我正在研究一個應用程序，我需要按照輪流計劃自動爲成員安排作業。我不是很擅長解釋規則，所以這裏有一些數據可以幫助您：

職位：職位名稱，每週一星期三和星期三。
類別：一組職位
分組：另一組職位。
成員：在指定日期分配給職位的用戶。

對於本月中的每個日期，成員被分配到職位（均按升序排列）。如果一個成員被分配到一個類別中的一個位置，下一次出現同一類別中的一個位置時，下一個成員按字母順序（或列表的開始）被賦值，例如。

成員：M1，M2，M3，M4
位置在C1類：P1，P2，P3
成員的位置P1：M1，M2，M3，M4
成員的位置P2：M1，M2， M3
位置P2中的成員：M1，M3，M4

如果M1分配給P1，如果P2接下來，M2將被分配。另外一層複雜性被引入，如果P3接下來，M3會被分配。系統必須跟蹤M2被「跳過」的事實，並且如果可用則指定M2，然後指派M4，或者等到它到達M2可用的位置（當跳過許多跳過時，這變得更復雜'成員）。

如果他表示他在該日期不能使用，則會員將被跳過。系統需要優先考慮跳過的成員，當他們出現時以某種方式識別他們，然後跳到列表中的下一個邏輯人員。由於日期衝突，跳過也適用於羣組。

我已經有一個臨時的[和凌亂]的解決方案，我不再理解，即使我有很多意見，在解釋每一步。它的弱點在於處理跳過的成員。

如果你打算編碼，你會怎麼做？我在PHP中實現這一點，但僞代碼也可以。

Answer 1

我的解決方案： 您需要一個PriorityQueue（在SplPriorityQueue下可在PHP中使用）。 PriorityQueue爲您提供優先級降低的元素（按值排序，最小的 值具有最高優先級）。

每個成員都獲得一個指定的值。這個值是一個有n位數字的ASCII碼（爲了方便你可以使用8位數字），用零填充到n個位置。之後，您追加 的名稱。您還可以添加到每個成員可用位置

所以，（N = 5）：

• M1值：99999Albert P1，P2，P3
• M2值：99999Susi P1，P2
• M3值：99999Bob P1，P3

這使得按優先級和名稱對成員進行排序變得容易。

準備：

一個陽光燦爛的日子。您正在檢索給定日期的指定位置和類別。每個成員都加載在一個長列表中。沒有出現在工作中的每個成員都沒有加載，但是他的價值減少了兩分之一。鮑勃不在這裏，所以它的新值得到99997Bob。這意味着Bob將在下次自動選擇。 所有其他成員的價值減去一。

分配給一個特定日的位置被映射（使用SplObjectStorage）：

P1-> M1，M2，M3，M4等 P2->等

的地圖僅包含位置必須在今天進行分配。 之後

篩選器： 您必須查找組並刪除地圖上今天無法分配的任何位置。你的小組描述有點不清楚。

分配：

• 您選擇的位置來分配成員，可以填補該職位從列表
• 刪除現有成員
• 獲取列表，並把它們放到時Queue
• 指定位置通過從PriorityQueue中提取（）（正確分配自動完成 ）。被分配的每個成員的價值都會增加 （因此，如果你在這裏工作，減少和增加水平）。 如果您在這裏，並且因爲任何原因未被分配到某個職位，您將得到一個小罰1。如果你不在這裏，你會得到兩罰。
• 完成後，再次將其餘成員放在列表中，清除PQueue並繼續下一項作業。

注意事項：

• 你必須小心，總是有足夠多的人的位置。

Answer 2

uff。我不遵循你的描述，但在類似的情況下，我用SQL來解決這類問題。如果你使用的PHP我猜你有SQL可用。

我會建議做的是找到一種方法，將這些信息存儲到一組表中，然後找出sql查詢爲您提供的答案。通常在sql中比在過程語言中更簡單。

對於跳過的部分，例如，您可能有一列記錄了上次分配人員的時間，然後按此順序進行排序（以便您可以選擇長時間未分配的人員）。或者，您可以將跳過的次數作爲列和順序。

Answer 3

我的理解是有'm'個成員和'n'個職位。

類別：一組職位 - 在該類別中被分配了一個職位的成員不能擁有另一個職位？

組：一組職位 - 同一組中的職位必須在不同的日期分配。

最後一件事，一個職位有一個成員誰可以填寫它的列表。

從數據結構的角度來看待這個問題，把成員放在一個鏈表中 - 每個成員必須有一個附加的[position，day]列表，他們最終被分配。然後，對於每個職位，都有一份可以填寫該職位的成員的參考列表。將類別作爲另一個引用列表來實現它所處的類別。

實際分配：有一個計數器= 0，並遍歷位置。對於每個位置P，遍歷可以填充它的成員。成員M可填補，如果位置：

• 的任何位置，他填補了P2不P.
• 他充滿了一天P2的任何位置共享類別= daycounter不共用一組P.

如果他可以填寫該位置，則[位置，日期]對被添加到該成員，並且該成員的節點被移動到列表的結尾（這就是爲什麼引用是必要的 - 所有即使節點移動，引用仍然有效）。這確保了「跳過」成員被賦予最高優先級，並且未被到達的成員被賦予次優先級。

一旦一個位置被填滿，轉到下一個位置。如果頭寸與已分配的頭寸共享一組，則跳過該頭寸，遍歷所有頭寸，直到您可以在第1天分配儘可能多的頭寸。然後，增加日計數並重復第2天。這應該會給您所有工作的最大分配（不確定最大值）。提示：將成員移動到成員列表的末尾時，爲了避免必須遍歷列表，請保留對結束的引用 - 對於下一個位置，無論如何都需要從頭開始，所以有沒有一點經歷整個事情。