动机
一组作业需要分配到若干台同构机器上,目标是使最后一个作业尽早完成。一个简单的在线规则是:把每个到达的作业分配给当前负载最小的机器。该规则无需知道后续作业,但其最终完工时间始终不超过最优值的两倍。
更精细的分析给出 台机器时的精确因子 ,并给出达到该因子的实例。证明的思路是找出最后完成的那个作业,并结合最优完工时间的两个不同下界。
定义
定义 7.6.1
(调度实例与完工时间)
设 为同构机器的台数。共有 个作业,其处理时间为非负数 。作业按给定顺序分配,并且是非抢占的;每台机器依次处理分配给它的作业。机器的负载是其所有作业处理时间之和;完工时间(makespan)是最大负载。记 ,并记 为所有分配方案中可能的最小完工时间。对于空的作业列表,约定 。
定义 7.6.2
(列表调度)
列表调度(list scheduling)从所有负载为零开始。对于按顺序到来的每个作业,把它分配给当前负载最小的一台机器,平局时任意选择。该规则在作出决定时无需看到后续作业。若没有作业,则返回空调度,其完工时间为零。
定理
定理 7.6.3
(列表调度的近似比)
对于每个输入,
其中 是列表调度所产生的完工时间。
定理 7.6.4
(该因子的紧性)
对于每个整数 ,存在一个有序作业列表,使得列表调度的完工时间为 ,且与它如何在负载相同的机器之间打破平局无关。
若所有处理时间均为零,则保证式两边都为零。该结果以不等式的形式陈述,并不需要除以 。
证明
最优值的两个下界
引理 7.6.5
(最优值的两个下界)
对每个实例, 且 。
证明
(平均负载与最长作业)
每个分配方案的机器总负载都是 ,所以其最大负载至少为 。另外,包含作业 的机器必须完整处理该作业,所以其完工时间至少为 。因此
第一个下界是平均负载论证;第二个是单个作业论证。下面的证明同时需要这两个下界。在此模型中,单个作业不能拆分到多台机器上。
分析最后完成的作业
证明
(把关键的开始时间记到较早的作业上)
假设至少有一个作业的处理时间为正,并选取一个在其所在机器上于最终完工时间完成的作业 。设 为作业 被分配之前该机器的负载。则 ;同一台机器上不可能还有之后的正长度作业,否则会超过最终完工时间。其后的零长度作业不改变该等式。
在分配 的时刻,列表调度选择了一台负载最小的机器。因此每台机器的负载都至少为 。在 之前被分配的作业的总处理时间至少为 。由于 包含这些作业以及作业 ,
于是
最后一步分别应用了平均负载下界与单个作业下界。定理得证。该论证对零长度作业和任意平局处理方式都成立,因为它只使用了关键分配时刻的最小负载性质。
证明透视
把关键开始时间归于先前的作业量
当最后完成的作业被放置时,所有机器已经至少具有它的开始负载。因此先前的作业合计至少贡献了 的工作量。该作业自身的长度由最优值独立地界定,与平均负载界无关。
关键作业不等式的含义
对具体实例而言,估计式 强于最终的近似因子。若关键作业相对于平均负载较小,则调度接近平均负载下界。若该作业较大,则最长作业下界补偿其贡献。两个下界各自不必是紧的;它们对同一个未知的最优值都成立。
该证明是回顾式的:它在调度构造完成之后,才选取最后完成的作业。算法无需预测这个作业。当有多个作业在同一最大负载处完成时,选取其所在机器上正长度作业中最后的任意一个。它之前的负载与最小负载性质仍然给出该不等式。
同样的推理适用于作业列表的每个前缀。若输入在某次分配之后停止,就把该前缀视为一个完整实例,并把它的调度与该前缀的最优调度比较。因此该保证不依赖于事先知道作业的最终个数。该陈述针对的是在分配列表中在线揭示作业长度的情形;它并不对任意的物理释放时间或依赖于机器的处理速度建模。
紧例子为何平衡
从相等的负载出发,把一个单位作业分配给负载最小的机器,会使其中一个最小负载增加一。每经过一块 个单位作业之后,每台机器的负载恰好增加一:在当前较小负载的所有机器都得到一个作业之前,已经增加过的机器负载更大,不会再次被选中。对 块作归纳,得到长作业之前的负载向量为 。这一论证与块内如何打破平局无关。
离线调度利用了对长作业的了解,为它单独保留一台机器。由该作业给出的下界证明没有任何调度能做到小于 的完工时间。结合所构造的离线调度,这就精确地确定了最优值,而不仅仅是其上界。因此列表调度的完工时间 证明了所声称的最坏情形比值。
匹配的下界例子
证明
(单位作业之后接一个长作业)
固定 。给列表调度 个单位长度作业,随后是一个长度为 的作业。在这些单位作业之后,所有负载都是 :最小负载规则使机器均匀填充,且单位作业的个数是 的倍数。最后一个作业被分配到任意一台机器,使其负载升至 。
最优的离线调度把长度为 的作业单独放在一台机器上,并把 个单位作业均匀分配到其余 台机器上,每台 个。其完工时间为 。最长作业下界同样给出 ,所以该调度是最优的。比值为 。
在这些单位作业之后,每一种平局处理方式都得到同样平衡的负载向量,因此该例子证明的是所述规则本身的紧性,而不是某一种特定平局约定下的紧性。
复杂度与实现
以机器当前负载为键的最小优先队列,可以通过取出负载最小的机器并以更新后的负载重新插入来支持每次分配。使用二叉堆时,除了存储输出调度之外,这些分配需要 次比较以及 个机器条目。计入建立初始堆的 时间,总时间为 。
若 ,则把每个作业分配给不同的机器即为最优,其完工时间等于最长的处理时间。直接处理这种情形,可以避免当 以二进制给出且大于作业个数时分配海量的空机器记录。对于非平凡情形 ,堆的大小受显式作业个数所界定。精确的有理数处理时间需要精确的加法与比较;操作次数本身并不是完整的位复杂度界。
该证明适用于所给定的作业顺序。在列表调度之前对作业排序可以改进某些调度,但这会改变在线行为,并且对任何声称的更强因子都需要另行分析。此处的结果不假设输入已排序。
反例模式
贪心调度可能不是最优的
在两台机器上,依次处理作业 。两个单位作业给出负载 ;随后最后一个作业产生负载 。离线调度把长度为二的作业放在一台机器上,把两个单位作业放在另一台机器上,完工时间为二。贪心的比值为 ,恰为 。
边界约定与输出
调度可以通过列出每台机器上按分配顺序排列的作业来表示。当所有作业都可用时,让每台机器的作业连续开始、没有空闲时间,则所述负载就等于完成时间。在此模型中,刻意插入空闲时间不可能改善最大完成时间,所以负载表述刻画了最优值。
零处理时间不造成任何困难。它们可以在不改变负载的情况下被分配,仅由零长度作业构成的实例其完工时间为零。证明在选取正的关键作业之前,先把该情形单独分出。若 ,则因子恰为一,且工作量下界取等号。处理这些情形时,不应除以可能为零的最优值。
例题详解
例题 7.6.6
(两台机器)
对于作业长度 ,列表调度把 和 分配到不同的机器,然后把 分配到负载为 的机器。最终负载为 ,所以完工时间为三。由于 ,该调度是最优的。
例题 7.6.7
(一台机器)
当 时,每个作业都必须在唯一的机器上运行,所以列表调度与最优调度的完工时间都是 。因子 等于一。
例题 7.6.8
(三台机器的紧实例)
对于 ,给出六个单位作业,随后是一个长度为三的作业。六个单位作业产生负载 ,最后的作业使其中一个负载变为五。最优方案把长作业单独放置,并在其他每台机器上放三个单位作业,完工时间为三。比值为 。
例题 7.6.9
(机器多于作业)
对于处理时间 和五台机器,把两个作业分配到不同的机器。完工时间为四,达到最长作业下界,因此是最优的。其他机器可以保持空闲。
常见错误
常见错误
(当前负载与最终负载)
接收关键作业的机器,在该作业被分配时具有最小的当前负载。它的最终负载不一定仍然最小。证明是把该开始时间归于已经分配的工作量,再加上关键作业的长度。
常见错误
(单靠平均负载下界控制不了最后一个作业)
仅有不等式 不足以界定最后一个作业的贡献。单个作业可能远长于平均负载,因此单独的下界 是必不可少的。
常见错误
(该规则并不需要最优值)
最后,该保证是把结果与知道全部作业的离线最优值作比较。列表规则本身不需要该最优值,也不需要未来作业的长度。离线算法在某个具体输入上可能做得更好,这与近似界并不矛盾。
总结
列表调度把每个作业放到负载最小的机器上。在最后完成的作业被分配时,每台机器至少已累积了其开始负载。把这一工作量界与最长作业下界结合,即得 近似,而一列单位作业后接一个长作业的例子表明该因子是紧的。
练习
快速检查
(给出用总处理时间与单个作业表示的 的两个一般下界。)
一个下界与平均有关,另一个与单个作业有关。
解答 · 答案
,因为最大负载至少是平均值;,因为作业不能被拆分到多台机器上。
快速检查
(对作业 在两台机器上运行列表调度,并与最优分配比较。)
逐个作业运行该规则,再试着把两个单位作业放在一起。
解答 · 答案
前两个作业给出负载 ;最后一个作业产生 (机器名称可互换)。把两个单位作业放在一起,最优方案的负载为 ,所以比值为 。
快速检查
(为什么当 时列表调度是最优的?)
作业分配到机器只有一种可能。
解答 · 答案
所有作业都必须分配给唯一的机器,每个调度的完工时间都是 。因此列表调度与最优值相等。
快速检查
(对于 ,描述一个达到比值 的作业列表。)
回想紧例子:先是单位作业,最后是一个长作业。
解答 · 答案
使用六个长度为一的作业,随后是一个长度为三的作业。列表调度得到的完工时间为五;把长作业单独放置,并在其他每台机器上放三个单位作业,得到最优值三。