PACT 07/01 任务调度问题

Posted on 2020-07-04 Views:

定义

输入：个任务，第个任务的运行时间为 p_i ，共有个相同的机器（一个任务在每台机器上运行时间都相同）。每台机器同一时间只能运行一个任务，每个任务只能在一台机器上运行（不能拆分）。

目标：合理地调度任务，使得完成所有任务的时间（makespan）最短。

下界估计

自然而然地，我们首先思考 $\mathrm{OPT}$ 的下界。一个比较容易想到的下界是耗时最长的任务所需要的时间：

$\mathrm{OPT} \ge \max_{i} \{p_i\}$

除此以外，考虑如果可以拆分任务，最短的运行时间是多少？自然是 $\frac{\sum_i p_i}{m}$ ，而这在现实中常常是做不到的，因此有：

$\mathrm{OPT} \ge \frac{\sum_i p_i}{m}$

这两个下界对于之后的算法分析非常有用。

算法

将所有的任务随机排成一列。
当一台机器完成了一个任务变得闲置了，马上把列表上的下一项任务安排到这个机器上去执行。
重复步骤2直至所有任务都被执行完毕。

这个算法是非常简单且自然的。

分析

我们算法给出结果的什么？自然是最后一个结束的任务的结束时间。如果我们设最后一个结束的任务为任务，且这个任务开始于 s_l ，那么就有：

$\mathrm{Cost} = s_l+p_l$

接下来我们进行放缩。

考虑 s_l 的上界是什么？

很显然，在时刻，除了即将运行的那台机器，其他机器上必须有任务在运行或者刚刚空下来（如果有机器已经空了一阵子了，那当时就会被安排到那台机器上去跑），因此不难得出 $ms_l \le \sum_{i\neq l} p_i$ ，即

$s_l \le \frac{\sum_{i \neq l}p_i}{m}$

因此

$\begin{aligned} \mathrm{Cost} &= s_l+p_l \\ & \le \frac{\sum_{i \neq l}p_i}{m} + p_l \\ &= \frac{\sum_{i}p_i}{m} + \left(1 - \frac{1}{m}\right) p_l \\ &\le \frac{\sum_{i}p_i}{m} + \left(1 - \frac{1}{m}\right)\max_{i}\{p_i\} \\ &\le \mathrm{OPT} + \left(1 - \frac{1}{m}\right)\mathrm{OPT} \\ &= \left(2 - \frac{1}{m}\right)\mathrm{OPT} \end{aligned}$

我们就证明了我们的算法是一个

倍近似算法！

提升近似比

能不能在这个算法的基础上提升呢？我们注意到将 $\mathrm{OPT}$ 作为 p_l 的上界其实还是太松了。如果我们能够缩短 p_l ，那上界的估计有没有改善的空间呢？

于是我们在原来算法的基础上不妨进行一个改进：与其在一开始将所有任务随机排列，不如将其按照运行时间从大到小的顺序进行排序。这也很符合直觉，一开始就把需要时间很长的任务跑完，之后肯定有些机器空着有些机器还在忙，这个时候就可以用完成时间比较短的小任务来灵活地填补这些空缺了。

这一下让近似比提升了多少呢？

引理：加上排序之后的算法具有 $\frac{3}{2}$ 的近似比。

证明：我们不妨分类讨论，

情形1. $p_l \le \frac{1}{2}\mathrm{OPT}$ ，这个时候按照我们上文分析的路子走直接就可以得到 $\mathrm{Cost} \le \frac{3}{2}\mathrm{OPT}$ ，就做完了。

情形2. $p_l > \frac{1}{2}\mathrm{OPT}$ ，此时所有之前的任务也肯定具有大于 $\frac{1}{2} \mathrm{OPT}$ 的运行时间。注意到我们不需要考虑之后的任务，因为依据定义是最后结束的，后面的任务对于我们的结果没有影响。那之前的任务在最优调度里面是怎么样的呢？反证法可以很快说明：在最优调度里面，每一台机器至多只能处理一件任务（忽略之后的任务）！也就是说事实上以及之前的任务数目加起来不会超过机器数，那再想一想在这种机器充足的情况下，我们的算法在分配这些任务的时候也是一个机器一个任务， p_l 必定是从一开始就执行的，因此 $\mathrm{Cost}=p_l$ ，而显然 $\mathrm{OPT} \ge p_l$ ，因此必有 $\mathrm{Cost} = \mathrm{OPT}$ ，结束。（事实上，由于还是最后结束的任务，不难想通在一机器一任务的情形下，之前的所有任务都一定和花费相同的时间，或就是我们算法分配的第一个任务。）

综上所述，近似比是 $\frac{3}{2}$ 。

进一步提升近似比

通过对于上述论证的些许修改，我们其实可以证明：

引理：加上排序之后的算法具有 $\frac{4}{3}$ 的近似比。

证明：我们故技重施：

情形1. $p_l \le \frac{1}{3}\mathrm{OPT}$ ，这个时候我们直接就可以得到 $\mathrm{Cost} \le \frac{4}{3}\mathrm{OPT}$ 。

情形2. $p_l > \frac{1}{3}\mathrm{OPT}$ ，此时所有之前的任务也肯定具有大于 $\frac{1}{3} \mathrm{OPT}$ 的运行时间。我们同样不考虑之后的任务。可以通过反证证明：在最优调度里，每一台机器至多只能处理两件任务！因此，我们确定有足够的机器让我们的算法得以这样调度任务：

（看着是不是很像双指针？）

具体来说，如果我们把机器按照第一个任务的耗时降序排序，那么它们第二个任务的耗时一定成升序排列。（这并不难证明：第一个任务耗时最短的机器一定能够先领到列表中最长的任务作为第二个任务，之后的机器领到的任务时间递减）

（在这里我们假定一定是第二个任务，如果从头开始运行而且时间特别长的话，参考上一节的证明）

而接下来我们证明这样的分配方式是最优的。

我们采取反证的方法：不妨假设在最优方案中存在两个机器，两个机器上都有两个任务，耗时分别为 (a,b) 和 (c,d) ，且 a>c,b>d 。那么我们把两个机器上的第二个任务互换，变成 (a,d) 和 (c,b) ，不难发现此时完成任务的最短时间会减少，和“最优”矛盾。因此，对于最优方案的任意两台机器 (a,b) 和 (c,d) ，如果 a>c 那么 b<d ：

这正是我们算法所给出的调度方案。因此 $\mathrm{OPT}$ 不会比我们算法的结果更好了。

综上所述，近似比为 $\frac{4}{3}$ 。