式中：AST (vi,pn)-任務vi在處理器pn上的實際開始時間;AFT (vi,pk)-任務vi在處理器pk上的實際完成時間;vpar-最后一個與任務vi通信的任務;Avail(pn)-處理器pn執行完分配到其上的所有任務的時間。

通過對DAG圖的深入研究發現，某層冗余任務的處理在其下一層任務到處理器的映射之后執行效果最好，如對level=1層任務調度完成后對level=0層任務進行冗余判斷，將任務分配到處理器和冗余任務處理兩個過程交替執行，直到冗余任務列表為空。

(2)任務到處理器映射流程任務到處理器映射流程如圖3所示。

(3)任務到處理器映射階段具體步驟

步驟1 初始化level=0,判斷任務調度列表TL在level層的任務是否調度完畢，如果是則跳轉到步驟5;否則向下執行步驟2.

步驟2 取任務調度列表TL的首任務記為vi,遍歷所有處理器，如果處理器存在空閑時間段且滿足vi插入條件，則將vi分配到空閑時間段，并計算其最小最早完成時間，記為EFT1;否則向下執行步驟3.

步驟3 計算將vi分配到所有處理器上的最小最早完成時間，記為EFT2.如果處理器上存在空閑時間段且能使用任務復制技術，則計算在處理器上復制vi的前驅獲得最小最早完成時間，記為EFT3,繼續執行步驟4.

步驟4 選擇EFT1、EFT2、EFT3的最小值，并將任務分配到具有最早完成時間的處理器上，從調度列表中刪除vi,建立冗余任務列表RTL,將被復制的任務加入到RTL中，格式為vi,0~vi,k,vi為被復制的任務節點，k為任務所在處理器的編號。

步驟5 判斷RTL中是否有(level-1)層任務，如果是則跳轉到步驟6;否則跳轉到步驟8.

步驟6 取RTL首任務節點，記為vi,k,判斷刪除任務vi,k后vi,k直接后繼節點的最早開始時間是否延遲，如果延遲，判定任務vi,k非冗余任務，從RTL中刪除vi,k,跳轉到步驟5;否則判定任務vi,k為冗余節點，從RTL中刪除vi,k,從任務映射圖中刪除vi,k,跳轉到步驟7繼續執行。

步驟7 判斷任務vi,k的后繼任務能否提前執行，如果能則將其前移執行，修改任務映射圖，跳轉到步驟5;否則，直接跳轉到步驟5.

步驟8 如果level

2 WPTS算法時間復雜度分析

任務合并過程是對DAG圖進行一次深度優先遍歷，因此其時間復雜度為O (v+e)，v為DAG圖中任務的數量，e為有向邊的數目。任務分層是從上到下計算每個節點的level值，時間復雜度為O (n+e)，n為任務合并后DAG圖中任務的數量。任務權值計算對DAG圖進行廣度優先遍圖3 任務到處理器映射階段流程歷，計算任務節點的weight值和尋找關鍵路徑節點，時間復雜度為O (n2)，因此任務優先級計算階段的時間復雜度為O (v+e)+O (n+e)+O (n2);任務到處理器的映射階段考慮了處理器空閑時間段插入和任務復制技術，因此每層任務被映射到處理器上的時間復雜度為O (kp)，k為每層的任務數量，p為處理器的數量，冗余任務處理的時間復雜度為O (k2)，將所有任務映射到處理器上并完成調度結果優化所需的時間復雜度為O (kpm+k2 m)，m 為任務DAG圖的層數，其在最壞情況下等于任務數量v.

圖3　任務到處理器映射階段流程

綜上所述，WPTS算法的時間復雜度為O (v+e)+O(n+e)+O (n2)+O (kpm+k2 m)，即O (v3)，算法沒有提高時間復雜度，且能有效處理使用任務復制技術帶來的冗余任務，減少任務的調度長度，避免處理器資源的浪費。