加權作業排程演算法

加權作業排程演算法也可以表示為加權活動選擇演算法。

問題是,鑑於某些工作的開始時間和結束時間,以及你在完成工作時獲得的利潤,如果沒有兩個工作可以並行執行,你可以獲得的最大利潤是多少?

這個看起來像使用貪婪演算法的活動選擇,但有一個額外的扭曲。也就是說,我們專注於實現最大利潤,而不是最大化完成的工作數量。執行的工作數量與此無關。

我們來看一個例子:

+-------------------------+---------+---------+---------+---------+---------+---------+
|          Name           |    A    |    B    |    C    |    D    |    E    |    F    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)|  (2,5)  |  (6,7)  |  (7,9)  |  (1,3)  |  (5,8)  |  (4,6)  |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Profit          |    6    |    4    |    2    |    5    |    11   |    5    |
+-------------------------+---------+---------+---------+---------+---------+---------+

這些工作用名稱,開始和結束時間以及利潤來表示。經過幾次迭代後,我們可以看出我們是否執行了 Job-AJob-E ,我們可以獲得 17 的最大利潤。現在如何使用演算法找到它?

我們做的第一件事就是按照非遞減順序對作業進行整理。我們為什麼要做這個?這是因為如果我們選擇一個花費較少時間完成的工作,那麼我們會留出大部分時間來選擇其他工作。我們有:

+-------------------------+---------+---------+---------+---------+---------+---------+
|          Name           |    D    |    A    |    F    |    B    |    E    |    C    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)|  (1,3)  |  (2,5)  |  (4,6)  |  (6,7)  |  (5,8)  |  (7,9)  |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Profit          |    5    |    6    |    5    |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+

我們將有一個大小為 n 的臨時陣列 Acc_Prof (這裡, n 表示作業總數)。這將包含執行作業的最大累計利潤。不明白嗎?等等看。我們將使用每個作業的利潤初始化陣列的值。這意味著, Acc_Prof [i] 將首先保持執行第 i 個工作的利潤。 **** **** **** ****

+-------------------------+---------+---------+---------+---------+---------+---------+
|         Acc_Prof        |    5    |    6    |    5    |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+

現在,讓我們表示位置 2,以及 1 位將被記 Ĵ 。我們的策略是將 j1 迭代到 i-1,並且在每次迭代之後,我們將 i 遞增 1,直到 i 變為 n + 1

                               j        i

+-------------------------+---------+---------+---------+---------+---------+---------+
|          Name           |    D    |    A    |    F    |    B    |    E    |    C    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)|  (1,3)  |  (2,5)  |  (4,6)  |  (6,7)  |  (5,8)  |  (7,9)  |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Profit          |    5    |    6    |    5    |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Acc_Prof        |    5    |    6    |    5    |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+

我們檢查工作[I]工作[J] 重疊,也就是說,如果完成時間工作[J] 大於工作[I] 的開始時間,那麼這兩個作業不能一起做。但是,如果它們不重疊,我們將檢查 Acc_Prof [j] + Profit [i]> Acc_Prof [i] 。如果是這種情況,我們將更新 Acc_Prof [i] = Acc_Prof [j] + Profit [i] 。那是:

if Job[j].finish_time <= Job[i].start_time
    if Acc_Prof[j] + Profit[i] > Acc_Prof[i]
        Acc_Prof[i] = Acc_Prof[j] + Profit[i]
    endif
endif

這裡 Acc_Prof [j] +利潤[i] 代表完成這兩項工作的累計利潤。我們來看看它的例子:

在這裡工作[J] 重疊與作業[I] 。所以這些不能一起完成。由於我們的 j 等於 i-1 ,我們將 i 的值增加到 i + 1 ,即 3 。我們使 j = 1

                               j                   i

+-------------------------+---------+---------+---------+---------+---------+---------+
|          Name           |    D    |    A    |    F    |    B    |    E    |    C    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)|  (1,3)  |  (2,5)  |  (4,6)  |  (6,7)  |  (5,8)  |  (7,9)  |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Profit          |    5    |    6    |    5    |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Acc_Prof        |    5    |    6    |    5    |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+

現在 Job [j]Job [i] 不重疊。通過選擇這兩個工作我們可以獲得的總利潤是: Acc_Prof [j] + Profit [i] = 5 + 5 = 10 ,它大於 Acc_Prof [i] 。所以我們更新 Acc_Prof [i] = 10 。我們也將 j 增加 1.我們得到了,

                                         j         i
 
+-------------------------+---------+---------+---------+---------+---------+---------+
|          Name           |    D    |    A    |    F    |    B    |    E    |    C    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)|  (1,3)  |  (2,5)  |  (4,6)  |  (6,7)  |  (5,8)  |  (7,9)  |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Profit          |    5    |    6    |    5    |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Acc_Prof        |    5    |    6    |    10   |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+

在這裡,作業[j]的重疊與作業[I]Ĵ 也等於 I-1 。所以我們將 i 遞增 1,並使 j = 1 。我們得到了,

                               j                             i
 
+-------------------------+---------+---------+---------+---------+---------+---------+
|          Name           |    D    |    A    |    F    |    B    |    E    |    C    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)|  (1,3)  |  (2,5)  |  (4,6)  |  (6,7)  |  (5,8)  |  (7,9)  |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Profit          |    5    |    6    |    5    |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Acc_Prof        |    5    |    6    |    10   |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+

現在, Job [j]Job [i] 不重疊,我們得到累計利潤 5 + 4 = 9 ,這大於 Acc_Prof [i] 。我們更新 Acc_Prof [i] = 9 並將 j 遞增 1。

                                         j                   i
 
+-------------------------+---------+---------+---------+---------+---------+---------+
|          Name           |    D    |    A    |    F    |    B    |    E    |    C    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)|  (1,3)  |  (2,5)  |  (4,6)  |  (6,7)  |  (5,8)  |  (7,9)  |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Profit          |    5    |    6    |    5    |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Acc_Prof        |    5    |    6    |    10   |    9    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+

同樣工作[J]工作[I] 不重疊。累計利潤為: 6 + 4 = 10 ,大於 Acc_Prof [i] 。我們再次更新 Acc_Prof [i] = 10 。我們將 j 增加 1.我們得到:

                                                   j         i
 
+-------------------------+---------+---------+---------+---------+---------+---------+
|          Name           |    D    |    A    |    F    |    B    |    E    |    C    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)|  (1,3)  |  (2,5)  |  (4,6)  |  (6,7)  |  (5,8)  |  (7,9)  |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Profit          |    5    |    6    |    5    |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Acc_Prof        |    5    |    6    |    10   |    10   |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+

如果我們繼續這個過程,在使用 i 迭代整個表之後,我們的表最終將如下所示:

+-------------------------+---------+---------+---------+---------+---------+---------+
|          Name           |    D    |    A    |    F    |    B    |    E    |    C    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)|  (1,3)  |  (2,5)  |  (4,6)  |  (6,7)  |  (5,8)  |  (7,9)  |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Profit          |    5    |    6    |    5    |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Acc_Prof        |    5    |    6    |    10   |    14   |    17   |    8    |
+-------------------------+---------+---------+---------+---------+---------+---------+

*已跳過幾個步驟以縮短文件。

如果我們遍歷陣列 Acc_Prof ,我們可以找出最大利潤為 17 ! 虛擬碼:

Procedure WeightedJobScheduling(Job)
sort Job according to finish time in non-decreasing order
for i -> 2 to n
    for j -> 1 to i-1
        if Job[j].finish_time <= Job[i].start_time
            if Acc_Prof[j] + Profit[i] > Acc_Prof[i]
                Acc_Prof[i] = Acc_Prof[j] + Profit[i]
            endif
        endif
    endfor
endfor

maxProfit = 0
for i -> 1 to n
    if maxProfit < Acc_Prof[i]
        maxProfit = Acc_Prof[i]
return maxProfit

填充 Acc_Prof 陣列的複雜性為 O(n 2 )。陣列遍歷取 O(n) 。因此該演算法的總複雜度為 O(n 2 )。

現在,如果我們要找出哪些進行的工作,以獲得最大的利潤,我們需要遍歷以相反的順序排列,如果 Acc_Prof 匹配 MAXPROFIT ,我們將推動名字的作業堆疊,並減去利潤的來自 maxProfit 的那份工作。我們將這樣做,直到我們的 maxProfit> 0 或我們到達 Acc_Prof 陣列的起始點。虛擬碼看起來像:

Procedure FindingPerformedJobs(Job, Acc_Prof, maxProfit):
S = stack()
for i -> n down to 0 and maxProfit > 0
    if maxProfit is equal to Acc_Prof[i]
        S.push(Job[i].name
        maxProfit = maxProfit - Job[i].profit
    endif
endfor

該程式的複雜性為: O(n)

有一點需要記住,如果有多個工作時間表可以給我們帶來最大的利潤,我們只能通過這個程式找到一個工作時間表。