遺傳算法或模擬退火工作項目調度和優化

Question

我一直致力於改進我公司的基本調度過程，並使其更加數據驅動，高效並簡化。就目前而言，我們目前只是每月總計項目所需的總小時數&將此值與可能的工作時數*員工數量進行比較。我們比較這些結果並確定是否需要提供更多幫助。

我想在這個過程中變得更加精確，所以我開始關注諸如穩定婚姻問題等資源的優化。最後，我偶然發現了遺傳算法和Job-Shop問題的模擬退火，因爲我相信我的問題最終會比多重匹配婚姻問題複雜一點，但我可能是錯的。

我的基本問題是作爲具有許多限制條件的優化任務設置的。

工人：約翰，簡，戴爾等
他們都可以有多個角色太（約翰可以是經理或勞動者）

項目：項目A，項目B，項目C等
項目有開始和結束日期。
理想情況下，我有我想限制的項目的不同階段的子開始日期和結束日期，但總體開始/結束日期將會完成。這些子日期包括每個角色類型所需的小時數（經理8小時，勞動者20小時等）

小時：每位員工不超過45小時。

我的問題是我真的需要利用遺傳算法或模擬退火還是有一個更簡單的過程。此外，我還沒有能夠找到任何這些過程中的任何僞代碼R.

感謝您的任何和所有幫助，我很樂意澄清任何人，如果需要更多的細節！

Answer 1

您可以嘗試使用例如lpSolve軟件包將其建模爲混合整數程序。你必須變量，如john_manager_project_A_week_1（小時數約翰工程項目A作爲一個經理每週1次），其中，解算器，以確定和線性約束像

john_manager_project_A_week_1 + john_manager_project_B_week_1 + ... <= 45 
john_manager_project_A_week_1 + jane_manager_project_A_week_1 + ... >= 8 

這個框架似乎比較有限，但隨着一些建模技巧，你也可以表達這樣的條件，如「約翰不能在第一週在項目A上既作爲經理也作爲工人工作」。

解決這些問題是NP難題，但求解器往往是相當不錯的，如果只有幾十個人，項目和時隙應該是可以解決的。你甚至可以有一個要優化的線性目標函數（例如，用max_work_hours代替上面的「45」，並將其最小化）。