加权作业调度算法

加权作业调度算法也可以表示为加权活动选择算法。

问题是,鉴于某些工作的开始时间和结束时间,以及你在完成工作时获得的利润,如果没有两个工作可以并行执行,你可以获得的最大利润是多少?

这个看起来像使用贪婪算法的活动选择,但有一个额外的扭曲。也就是说,我们专注于实现最大利润,而不是最大化完成的工作数量。执行的工作数量与此无关。

我们来看一个例子:

+-------------------------+---------+---------+---------+---------+---------+---------+
|          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)

有一点需要记住,如果有多个工作时间表可以给我们带来最大的利润,我们只能通过这个程序找到一个工作时间表。