資源約束項目調度

Question

我需要你的幫助來解決這個問題。我有一組任務，每個任務都有其執行時間。我有兩種類型的約束。第一類是任務之間的優先關係。第二個約束類型允許同時執行一組任務。例如：我有6個任務和下面的邊緣（T1，T2），（T2，T3），（T4，T3），（T4，T5）和（T6，T5）圖G。假設T1，T4能夠一起執行，還有T1，T6但不是T4，T6。考慮到每個任務的執行時間。如何找到滿足任務之間優先關係的時間表，並考慮到某些任務的並行執行，使時間表的長度最短。

Answer 1

如果排斥約束（「T1，T4能夠一起執行」）不會在那裏（並添加沒有其他約束），你可以只採取一切其之前的最大結束時間啓動各項任務任務。這將是最佳和規模良好。你會自動獲得最短的完工時間。這不是NP-complete/hard，而不是作業車間調度。

不幸的是，排他條件（和潛在的其他任何你在將來添加），把它變成車間作業調度（由拉爾斯提到的），這是一個NP完全/硬。一個開源的Java實現的作業車間調度變種See this video，該演示的，爲什麼有些任務開始比之前的任務完成以後。要解決這個問題，請看啓發式，Metaheuristics（禁忌搜索，...）或其他相關技術。

Answer 2

要保持簡單，您可以使用基於優先級規則的建設性啓發式算法，以及計劃生成計劃或也稱爲SGS，請參見this以供進一步參考。啓發式會根據一些標準生成一個有序的活動列表，SGS將把這個列表作爲輸入並生成計劃。在實施SGS時，您會根據第二個約束來判斷兩個任務是否可以並行執行。

如果你想要的東西更強大的，你可以使用元啓發式，在那裏基本上你會產生一個解決方案（任務列表），並使用本地搜索技術修改這個解決方案，探索您的解決方案的搜索空間。您可以根據優先級規則生成解決方案，並使用SGS實施進行評估。這只是一個關於Metaheuristic如何工作的簡單解釋，有幾個差異。 Metaheuristic的一個很好的例子是模擬退火，適用於RCPSP問題：http://www.sciencedirect.com/science/article/pii/S0377221702007610。