項目調度基本實例：遺傳算法的染色體

Question

我正在寫一個項目調度優化庫，一個特殊的作業車間調度問題。爲了保持它的簡單，到目前爲止，我的算法將只與工人是該項目的唯一資源工作，只有2個類型的約束到目前爲止：

1）每個工人有什麼項目，他的約束可以工作。 只有一些員工能夠熟練地從事同一個項目（例如：W1，W3，W7員工可以在項目P2上工作; W2，W3，W5可以在項目P3上工作;等等），但同一個員工可以熟練地工作在多個項目上，並允許在不同時間在多個項目上工作（例如：W1連續5天在P1上工作，然後他切換到P2 4天，然後他回到P1等）

2）每個工人對他能有多少小時每天工作的約束 - 這應該代表工人的效率

首先，我創建了一個簡單時間表只包含4個項目和4名工人。

項目：

• P1; 起始：五月一號; 截止日期：：30天; 需要工作時間：300
• P2; 起始：7月1日; 截止日期：60天; 需要工作時間：150
• P3; 起始：5月15日; 截止日期：45天; 需要工作時間：50
• P4; 起始：4月，20日; 截止日期：20天; 工時需要：150

工：

• W1; 效率：10h /天; 可用項目：P1，P2，P3，P4
• W2; 效率：5小時/天; 可用項目：P1，P3
• W3; 效率：8小時/天; 可用項目：P1，P4
• W4; 效率：6h /天; 可的項目：P2，P4

一個問題是建立這樣，在遺傳算法的一個染色體應該看起來怎麼樣，換句話說 - 如何將這些數據轉換成一個GA染色體GA會知道如何處理（計算它的數值適應度）？ Java中的一個例子是完美的。

Answer 1

我想我會帶他們每天工作的工人和項目。 因此，對於計劃的每一天，請爲每個工作人員寫下他們將要處理的項目。

然後，您可以計算每個項目給定分配截止日期之前已完成工作的百分比。

突變可以在某一天將工作人員的分配更改爲不同的項目。 交叉可以用一個不同的基因組替換一個或多個工作日的工作人員的分配，或者將一天或多天的所有工作人員的完全分配與不同染色體的分配交換可能更有效

Answer 2

直接的解決方案在flup's answer將最有可能導致突變產生幾乎沒有任何有效的時間表。交叉會更糟糕。

問題是，做錯事太容易了。從一個最佳時間安排的員工那裏只需要一個步驟就可以超時安排他們。由於最優化典型地是某個n維多面體的頂點，它接近於無效狀態。

所以，我建議一些染色體部分的間接表示，如「如果可能，將W2分配給P3」。對於您的日程安排的每個小時，您都可以通過染色體部分並儘可能應用其規則。

這可以進行相當簡單的優化，以便您不必每小時處理一次（下一小時的結果通常相同）。

實際上，上述問題最有可能通過觀察只有少數相關時間點，即項目的開始時間和截止時間來完全解決。在他們之間，所有的時間在以下意義上都是相同的：當您將5月1日的日程安排和5月2日的日程安排互換時，您會得到完全相同的結果。使用這種等價性，問題可能會是一種暴力。