最小化最大延迟调度算法的探究

问题情景

有一台机器,从时刻 $s$ 起有多个任务需要使用它。每个任务需使用 $t_i$ 的时间才能完成。每个任务有一个截止时刻 $d_i$,如果实际完成时间超过了这个截止时刻,则为延迟。由于只有一台机器,因此这些任务的执行时间不能有重叠。现在的问题是:倘若允许任务有延迟,如何尽可能减小所有任务的最大延迟?求相应的任务时间安排表(t1到t2时间做哪个任务,t2到t3时间又要做哪个任务等等)

所谓“所有任务的最大延迟”,举个例子:一共有A, B, C三个任务,A延迟了3分钟完成,B提前了4分钟完成,C延迟了6分钟,那么,所有任务的最大延迟便是6分钟。更正式地说,对任务$i$,如果它的实际完成时刻为$f_i$,截止时刻为$d_i$,则该任务的延迟为
\[ l_i = \begin{cases} 0 , & \quad f_i \leq d_i\\
f_i - d_i , & \quad f_i > d_i \end{cases} \] 若共有 $n$ 个任务,则所有任务的最大延迟为 $L = max\{l_1, …, l_n\}$. 而$L$就是我们想尽量减小的目标函数。

贪心算法

贪心算法总是由比较简单的规则组成的。比如我们可以选择所需时间短的任务先做,或是选择截止时刻 $d_i$ 和所需时间 $t_i$ 间隔较小的先做,等等。但这些方法都存在反例说明这并不是最优的。对于这个问题,最优的一种方法是根据任务的截止时间 $d_i$来安排,截止时间早的安排在前面 (Earliest Deadline First, 简写为EDF).

伪代码

根据截止时间 $d$ 对任务进行升序排序, 得任务1 到任务n:$d_1 \leq … \leq d_n$
首先,令$f = s$
从任务1到任务n:
   将任务 $i$ 分配给时间间隔 $s(i)=f$ 到 $f(i)=f+t_i$
   $f = f+t_i$
结束
返回任务时间安排列表 $[s(i),f(i)], i=1,…,n$

Java实现

其实按原始的任务顺序排时间更合理,不过按照伪代码的方式比较简单,突出重点

public int[][] earliestDeadlineFirst(int[][] jobs){
        if(jobs == null || jobs.length==0)  return new int[][]{};

        int f = 1; //suppose we start from 1st unit time
        int[][] rst = new int[jobs.length][2];
        // order jobs in order of deadlines
        Arrays.sort(jobs,(a,b) -> a[1] - b[1]);
        for(int i=0; i<jobs.length; i++){
            rst[i][0] = f;
            rst[i][1] = f + jobs[i][0];
            f = rst[i][1];
        }

        return rst;
    }

算法正确性证明

我们的目标是证明 EDF 所求得的任务时间安排表所带来的最大延迟时间是最小(最优)的。 这里用到一个叫 “exchange argument”的技巧,不知中文如何翻译最为得当。总体思想是: 对一个最优解逐步地变换,在每一步变换中保持它的最优性,直至将其变为我们算法所得的解。于是,既然我们的解的最优性和最优解的一样,那我们的解自然就是最优解了。这个证明方法似乎是贪心算法证明的万金油之一。

以下是几个细分的步骤。

首先,EDF算法所安排的各个任务之间是没有间隔,或说是没有空闲时间的,算是最大化利用这台机器了,因此

a. EDF所得到的安排中各任务之间没有间隔

另外,我们可以感觉到

b. 没有间隔的任务安排中肯定存在最优的安排

确实,相比较有间隔的时间安排,没有间隔的最大延迟只会更小,而不会增大。因此,没有间隔的安排中肯定有最优安排。

接着,我们可以发现

c. EDF所得安排表是没有“反序”(inversion)的

所谓反序,就是任务$i$的截止时间在任务$j$之前,但$i$却被安排在$j$之后。因为EDF是根据任务的截止时间的升序进行处理的,所以没有反序。

d. 所有既没有反序也没有空闲间隔的安排都有相同的最大延迟

对两个既没有反序也没空闲的安排,它们的任务顺序不一定一模一样。然而,两者有差别的任务顺序仅限于截止时间相同的那些任务。假设有截止时间 $d$,在两个任务安排中,截止为 $d$ 的任务都是安排在一块儿的(在截止时间比 $d$ 早的任务之后,截止时间比 $d$ 晚的任务之前)对于截止时间为 $d$ 的这些任务,最后完成的那个会带来最大的延迟,而这个延迟与这些任务的顺序无关。

e. 如果一个不含间隔的任务安排存在反序,那么肯定存在相邻的反序。

我们可以想象一下,如果 $d_a < d_b$ ,而任务 $b$ 安排在任务 $a$之前,并且两者隔了几个任务。若从 $b$ 按顺序向后看,那么必然有一处出现任务的截止时间减小。这就是相邻的反序。

接下来是重点:

  交换两个相邻的反序任务
f1. 会使反序任务对总数减一
f2. 不会增加最大延迟

对于 f1 的证明,我们可以考虑至少有一个反序对的任务安排。由步骤 $e$,令 $i$ 和 $j$ 为任务安排中的一组相邻的反序对。如果我们将 $i$ 和 $j$ 交换次序,那么这组反序对就去除了,此外,没有新增反序对。因此反序对总数减一。

对于f2 的证明,如下图,$d_j < d_i$,但是起初 $i$ 排在了 $j$ 的前面。令 $l$ 为交换前的延迟, $l’$为交换后的延迟。

交换前

----------|-------------|------|------------
  |     |      任务i      任务j
 dj     di  



交换后

----------|------|-------------|------------
  |     |   任务j     任务i
 dj     di

我们有

  • $l’_k = l_k$, 所有 $k \neq i, j$

  • $l’_j \leq l_j$ (任务 $j$ 提前了,因此相应延迟只可能减小)

  • 若交换后任务 $i$ 有延迟,则
    $l’_i = f_j - d_i < f_j - d_j = l_j$

第三个式子成立是因为
1. 交换后,任务 $i$ 在原先任务 $j$ 的完成时间完成 $(f’_i=f_j)$
2. 任务 $j$ 的截止时间早于任务 $i$ $(d_j < d_i)$

因为最大延迟时间 $L’\geq l_j > l’_i$,因此,交换没有增大最大延迟。

由步骤b, f1, f2可知:

g. 存在一个既没有反序也没有间隔的最优安排

由a, c (EDF所得安排既没反序也没空闲间隔)g(存在一个既没有反序也没有间隔的最优安排)和d (所有既没有反序也没有空闲间隔的安排都有相同的最大延迟)可知,

h. EDF算法所得任务安排即为最优安排

由此,说明EDF所求为最优解。

时间复杂度

若一共有N个任务,根据截止时间对所有任务进行排序需 $O(NlogN)$,后面对每个任务逐一分配时间段,花费 $O(N)$. 因此该算法时间复杂度为 $O(NlogN)$.

后记

天呐康村这俩老师书里证明写得真是啰里啰嗦的。就这么一个greedy中简单的scheduling的证明看了好几遍才大概明白了它的套路,相比之下 PPT 简洁多了,对总体把握帮助很大。看到 CLRS 上有类似的算法,不过是求延迟总和最小的,而且那本里面还用到一个叫 matroid 的概念…懒得看了…作为一个下学期想上4820的弱鸡突然预感到到时的凄凉…

参考文献

[1] J. Kleinberg and E. Tardos. Algorithm Design. Addison-Wesley, 2005
[2] http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/04GreedyAlgorithmsI.pdf


如有错误欢迎指正,转载请注明出处。

comments powered by Disqus