帶時間懲罰的有向串并聯(lián)圖任務分配問題

打開文本圖片集

摘 要：隨著經濟的快速增長，很多產品的運作生產，往往需要不同的工藝流程。文章考慮了帶有時間懲罰的有向串并聯(lián)圖最小任務分配問題和帶有時間懲罰的有向串并聯(lián)圖最小跨度任務分配問題，根據(jù)有向串并聯(lián)任務優(yōu)先圖結構構建有向串并聯(lián)分配圖。在此基礎上，文章應用時間復雜性更小的特殊結構最短路算法以及收縮方法，分別設計了兩個時間復雜性為O（nm2k2）的多項式算法來解決帶時間懲罰的有向串并聯(lián)圖任務分配問題，其中n為任務數(shù)量，m為處理器數(shù)量，k是時間段限制數(shù)量。（剩余2585字）