动机
区间调度把每项活动的开始与结束时刻作为输入。另一类问题则要求完成所有作业,并允许我们决定它们什么时候开始。一台机器同一时刻只能处理一项作业。把某项作业放在前面会帮助它,却会推迟后面所有作业。因此,最好的顺序取决于这些延迟究竟如何计入目标。
两个常见目标会导出不同的贪心规则。为了控制相对于到期日的最大延误,应先处理到期日较早的作业。为了最小化加权完成时间之和,应比较处理时间与权重的比值。这里更值得掌握的是规则的发现与证明方法:固定其余安排,只比较两项相邻作业的次序。
定义
定义 2.6.1
(作业、调度与延误)
有 项作业。作业 的处理时间为 ,到期日为 ;讨论加权目标时,还给定权重 。所有作业从时刻零起就可处理。可行调度为每项作业指定开始时刻 ,使区间 两两不重叠。处理是不可抢占的:作业一旦开始,就连续运行至完成。记
定义 2.6.2
(目标:最大延误与加权完成时间)
是完成时间, 是延误, 是拖期。延误允许为负,表示提前完成;拖期只计算超过到期日的部分。我们分别研究
所有权重取一时,后者就是完成时间之和。空输入可直接返回空调度,加权代价为零;下面关于最大延误的结论只针对非空输入,以确保最大值有定义。
为什么可以先消除空闲
对任意可行调度,保持作业的先后顺序,让第一项从时刻零开始,以后每项紧接前一项开始。每项作业的开始和完成都不会比原来晚。所有作业在零时刻已经可用,因此这样左移仍然可行。各项延误不会增加;由于权重非负,各项 也不会增加。
所以只需考虑没有空闲的调度。这样的调度完全由作业排列 决定,而且
排列只有有限多个,故两个目标都能取得最小值。这一步既证明最优解存在,也消除了不必要的开始时间决策。如果某项作业要等到较晚才释放,左移便可能不合法。
定理
定理 2.6.3
(按最早到期日排序最小化最大延误)
在上述单机、全部作业从零时刻可用、不可抢占的假设下,任何按到期日非递减顺序执行且没有空闲的调度,都在所有可行调度中最小化 。到期日相同时可任意排序。同一调度也最小化最大拖期 。
定理 2.6.4
(处理时间与权重之比的排序规则)
在相同假设下,先将正权重作业按 非递减排序,再任意排列零权重作业,连续执行所得调度最小化 。正比值相同时可任意排序。特别地,按处理时间从短到长执行,能最小化无权的完成时间之和。
这些结论给出最优调度的充分条件,并不声称每个最优调度都必须具有上述次序。有些逆序交换不会改变目标,零权重还可能产生更多并列最优解。
证明:交换到期日逆序
证明
(交换到期日逆序)
设两项相邻作业原本依次为 ,且 。令这段两作业区间从时刻 开始。交换前,它们的完成时间为 和 ;交换后, 在 完成, 在 完成。
两项作业的总处理时间不变,所以其他作业的完成时间不受影响。变化的两项满足
以及
两个新延误都不超过某个旧延误,因此这对作业的新最大延误不超过旧最大延误。加上未变化的其他作业,整个调度的 不会增加。
从一个最优的无空闲调度出发,反复交换相邻的到期日逆序。每次严格逆序交换都会减少逆序对数,有限次后得到到期日有序的调度,而且仍然最优。若到期日相同,两种次序的最大延误都由该作业对的最后完成时间决定,因此任意交换都不影响结论。
对非空有限作业集,
右边随 非递减,故最早到期日调度也最小化最大拖期。反过来未必成立:多个调度可能都提前完成所有作业,从而最大拖期全为零,但它们的负最大延误仍可不同。
证明透视
哪个旧作业能同时控制两个新延误?
在到期日逆序中, 的到期日较早,却排在后面。把它移到前面会提前完成;把 移到后面,只让它取得这对作业原来的最后完成时间,而它的到期日又比 晚。因此, 原来的延误同时控制两个新延误。只说“较早到期的作业更紧急”,并没有给出这个定量比较。
证明:加权目标的两作业差值
证明
(加权目标的两作业差值)
仍比较从 开始的相邻作业 。其余目标项不变,而这两项在不同次序下的贡献之差为
两权重都正时,把 放在 前面不更差,当且仅当 。开始时刻完全消去,所以这项偏好不依赖这对作业处于调度的哪个位置。交换相邻的比值逆序,便能在不增加代价的情况下排好所有正权重作业。
如果 而 ,差值为 。把 移到前面会严格降低代价:零权重作业自身何时完成不收费,但它占用机器会推迟需要收费的作业。不断交换这样的逆序,就把零权重作业移到最后。两个零权重作业的贡献在两种次序下都为零。由此可把任意最优无空闲调度变成定理所述顺序。正比值相等时差值为零,说明并列可任意处理。
权重全为一时,差值化为 ,所以短作业优先最优。还可以写成
较早作业的处理时间会反复计入许多完成时间。短作业优先把较大的重复次数分配给较小的处理时间;交换证明使这一直觉成为严格论证。
概念视角组合
加权代价的逐对描述
把 写成作业 本身及排在它前面所有作业的处理时间之和,便得到 ,其中 表示 排在 之前。第一个和与顺序无关。每一对无序作业 ,若 在前则贡献 ,若 在前则贡献 ,所以代价是每对作业各出一项的和。互换两项相邻作业只改变其中一对,因此交换差值是 ,比值检验也就是逐对的比较。
例题
例题 2.6.5
(到期日顺序与另一个目标)
令 的 分别为 、、。最早到期日顺序为 ,完成时间为 ,延误为 ,所以 。最短处理时间顺序 的完成时间为 ,延误为 ,最大延误反而为二。
若最小化加权完成时间,比值顺序则为 ,对应 。完成时间为 ,故 。到期日顺序的加权代价却为 。同一顺序可以对一个目标最优,却对另一个目标明显较差。
例题 2.6.6
(相同比值与零权重)
作业 的 分别为 、、。正比值均为 。顺序 的加权代价为 ,顺序 也给出 。若把 放在最前,顺序 的代价增至 。零权重并不表示它推迟其他作业时没有影响。
例题 2.6.7
(最大延误不是总拖期)
取 的 , 的 。最早到期日顺序 的延误为九和九,最大延误为九,总拖期为十八。顺序 的延误为 和十,最大延误更差,但总拖期只有十。最大延误定理并不保证拖期之和最小。
例题 2.6.8
(释放时间为什么改变问题)
设 在零时刻可用,处理需四单位,到期日为一百。 在时刻一才释放,处理需一单位,到期日为二。立即运行当前可用的 ,会让 在时刻五完成,最大延误为三。若主动空闲到时刻一,先把 做到时刻二,再把 做到时刻六,最大延误便为零。消除空闲的论证不适用于这个释放时间模型,上面的证明也就不能直接沿用。
实现与代价
两种规则都先排序,再用一次前缀和扫描计算完成时间。共需 次比较和 次算术运算,包括求目标值。存储作业顺序、完成时间及目标值需 个字;排序实现另外需要的工作空间仍须计入。
正权重时,偏好 等价于 ,可避免近似除法的舍入问题。实际排序比较器应使用严格判断 ,相等时再按固定且唯一的作业编号打破并列;直接使用非严格比较并不是合法的严格排序比较器。零权重必须单独处理,不能除以零。只有数值模型支持时,精确比较与算术才能视为单位代价。若整数输入各至多有 位,交叉乘积可需 位,累积完成时间可需 位。因此,对任意大整数,字操作界并不是常数位操作代价的声明。
常见错误
反例模式
贪心规则必须对应一个目标
断言:既然最早到期日对最大延误最优,同一顺序也使加权完成时间之和最小。取第一个例题的三项作业, 分别为 、 和 。到期日顺序 的完成时间为 ,代价 ;但顺序 的完成时间为 ,代价只有 。反过来,最短处理时间优先的顺序 的最大延误为 ,而到期日顺序的最大延误为 。修正方法是先说明目标:每个目标都有各自的交换不等式,一条规则只对它的两作业差值所排序的那个目标成立。
常见错误
(要求每项作业都变好)
相邻交换不必让每项作业都更好。在到期日证明里,一项作业交换后完成得更晚,但它的新延误仍被旧的最坏延误控制。在加权证明里,一项贡献可以增加,只要另一项减少的量至少一样大。把整体改善误认为逐项改善,会排除证明所需的关键交换。
常见错误
(在模型之外套用同一规则)
假设也不能省略。释放时间可能令左移不可行,先后依赖约束可能令交换非法,多台机器则会改变可行调度集合。只照搬相同的排序规则,并不能处理这些不同模型。
最早到期日与最短处理时间在一般情形下都不能取胜,而且问题是 NP 困难的。
自然的下一个问题
总拖期有交换规则吗?
最早到期日与最短处理时间在一般情形下都不能取胜,而且问题是 NP 困难的。
对总拖期 ,作业 偏向最短优先:总拖期为 ,按到期日排则为 。作业 则偏向按到期日排: 对 。最小化 是 NP 困难的,不过存在伪多项式的动态规划,所以不能指望用成对交换规则解决它。
小结
在全部作业从零时刻可用的单机问题中,消除空闲把调度化为排列。交换到期日逆序不会增加作业对的最坏延误;加权目标的差值 则导出比值顺序。反复进行相邻交换能到达有序排列,同时保持可行且不恶化指定目标,从而得到全局最优性证明。
练习
快速检查
( 的 分别为 。求一个最早到期日顺序、各完成时间及 。)
按到期日排序,再累加处理时间。
解答 · 答案
到期日顺序为 ,完成时间为 ,延误为 ,故 。定理保证此值最小;短作业不一定先做。
快速检查
( 的 分别为 。求加权完成时间最小的顺序及目标值。)
计算正权重作业的 ,并把零权重作业放在最后。
解答 · 答案
的正比值为 , 的为二,故取 。完成时间为 ,加权和为 。
快速检查
(数出每项处理时间出现多少次,证明无权完成时间之和的公式。)
数一数每个处理时间出现在多少个完成时间中。
解答 · 答案
出现在第 项完成时间中,共 次。交换两个有限求和的次序即得公式。
快速检查
(说明最大拖期最小的调度为什么未必令最大延误最小。给出两项到期日充裕的作业,并解释为什么在无空闲调度中,把它们的到期日设为相同不能构成这种反例。)
试取足够大的到期日,使每项作业都提前完成。
解答 · 答案
给一单位作业到期日十,三单位作业到期日二十。短作业优先的延误为 ,最大值为 ;长作业优先的延误为 ,最大值为 。两者最大拖期都为零。若到期日同为 ,任何无空闲顺序中,最后作业的延误最大且均为 ,就无法这样区分两个目标。
快速检查
(加权调度中,相邻正权重作业 满足 。不论这段何时开始,交换次序会使目标减少多少?)
使用两作业差值 。
解答 · 答案
原目标减新目标为 。周围作业与开始时刻均消去,目标减少十四。
快速检查
(增加必须先做 再做 的约束,其中 、。准确指出比值排序证明在哪一步不能用于这个模型。)
先看比值规则偏好哪个顺序,再检查它是否可行。
解答 · 答案
比值规则希望 在 前,因为 ,但这个顺序违反依赖约束。证明中的交换不再是可行操作;本例只有 这个合法顺序。比较两个目标值的公式,并不能保证两个候选顺序都合法。