EDF · job sequencing

调度与背包：贪心的边界

前两页给的是判据：交换论证逐题证明，Rado–Edmonds 给出结构上的充要条件。本页把判据用到三组真实问题上，其中两组通过，一组不通过；不通过的那一组会给出具体输入与具体差值，而不是一句「贪心不一定对」。

1 · 最小化最大延迟

单台机器， $n$ 件作业，第 $i$ 件耗时 $t_i$ 、截止时刻 $d_i$ 。机器一次只能做一件、做起来不能中断，排产就是给出一个顺序；第 $i$ 件的延迟定义为完工时刻减截止时刻，可以是负数。目标是让最大延迟最小。

**定义 1.1（minimizing maximum lateness）**给定 $(t_i, d_i)$ ，求一个排列使 $\max_i (C_i - d_i)$ 最小，其中 $C_i$ 是第 $i$ 件在该排列下的完工时刻。

一批看似合理的排法在这道题上全是错的：先做最短的、先做最长的、先做余量最小的。正确的规则是截止时刻升序，即 earliest deadline first。它的证明不走前两页那种「与最优解比对」的路线，而是直接把任一排产改造成 EDF 序。

定理 1.2任一排产都能通过若干次相邻对调变成截止时刻升序的排产，且每次对调都不增加最大延迟。

证明若排产不是截止时刻升序，必存在相邻的一对 $(i, i+1)$ 满足 $d_i > d_{i+1}$ 。对调这两件：其余作业的开始与完工时刻都不变，因为这两件占用的总时长没变。设对调前两件的完工时刻为 $C_i < C_{i+1}$ ，对调后分别为 $C'_{i+1} = C_i + t_{i+1} - t_i$ 与 $C'_i = C_{i+1}$ 。对调后 $i+1$ 号的延迟 $C'_{i+1} - d_{i+1} \le C_{i+1} - d_{i+1}$ ，不超过对调前这两件的最大延迟； $i$ 号的延迟 $C_{i+1} - d_i$ 小于对调前 $i+1$ 号的延迟 $C_{i+1} - d_{i+1}$ （因为 $d_i > d_{i+1}$ ）。两件的延迟最大值没有变大，其余作业不受影响，故整体的最大延迟不增。

每次对调让逆序对减少一个，逆序对有限，所以有限步后到达截止时刻升序的排产。∎

图 1-1 · 从任一起手顺序出发，逐次对调相邻逆序对直到 EDF 序。可切换起手顺序，观察最大延迟与剩余逆序对的变化。

页面的样本是 6 件作业。shortest processing time 起手时最大延迟是 6，消掉 7 个逆序对之后降到 1；longest processing time 同样从 6 降到 1。定理只承诺不增，页面上确实能看到连续几次对调期间数字纹丝不动。

最值得看的是 smallest slack 那一档：它起手的最大延迟已经是 1，与 EDF 相同，却仍留着 1 个逆序对；消掉它，数字原地不动。这提醒一件容易记反的事：「不增」是论证需要的全部，「严格下降」既没有被证明，也不成立。实现里循环的终止条件因此只能挂在逆序对计数上——那才是每步严格减一的量；拿最大延迟当进度指标会写出一个不会停的循环。

2 · 带截止时间的作业排程

换一个目标函数：每件作业耗时都是 1 个单位，各有截止时刻与利润，只有在截止时刻之前完工才拿得到利润，目标是总利润最大。这时能不能做完全部作业已不重要，重要的是挑哪些做。

规则是利润降序：逐个考察，把当前这件排进「不晚于它截止时刻的最大空槽」；没有空槽就丢弃。挑最大的空槽而非最小的，是为了把靠前的槽留给截止时刻更紧的后来者。查找空槽的数据结构是并查集：槽 $s$ 的父指针指向不晚于 $s$ 的最大空槽，占用槽 $s$ 之后令 $s$ 的父指针指向 $s-1$ 的查找结果，此后经过 $s$ 的查找会自动跳过它。

0 号槽是 sentinel，代表「没有空槽」。留这一格不是为了省一次越界判断，而是为了让「找不到」这件事有一个和「找到了」同构的表示——查找的返回值永远是一个槽号，调用方只比较它是否为 0。

图 2-1 · 利润降序逐件排产：并查集查找不晚于截止时刻的最大空槽，父指针在下方逐帧变化。

样本的 5 件作业里两件被丢弃，总利润 142，与暴力枚举全部子集得到的最优值相同。这一次不必再写交换论证：可按期完工的作业集构成一个 matroid（ $S$ 独立当且仅当把 $S$ 按截止时刻升序排后第 $k$ 件的截止时刻不小于 $k$ ），Rado–Edmonds 直接给出结论。这个系统就是那一页 lab 里的 scheduling matroid，两处用的是同一批数据。

3 · 切不动的背包与换不开的零钱

背包问题的贪心规则是单位价值降序。可切割时它是对的：设最优解没有装满单位价值最高的那件，从解里换出等重的一部分低价值物品、换进这一件，总价值不减，反复替换即得贪心解。容量 50、三件物品分别为重 10 值 60、重 20 值 100、重 30 值 120 时，贪心装满全部容量、拿到 240。

不可切割时同一句论证立刻失效：「换出等重的一部分」这个动作不存在。同样的输入下贪心装进前两件、剩下 20 的容量塞不进第三件，得 160；而放弃第一件、装后两件正好装满，得 220。差值 60，是最优值的 27%。

找零问题的失效更隐蔽。面额降序尽量多取，在常见币值上一直是对的，于是很容易被当成定理。实测的结果是： $1, 5, 10, 25$ 这组币值在 1 到 200 分上一次反例都没有；把一枚 20 分插进去变成 $1, 5, 10, 20, 25$ ，1 到 39 分仍然全部无反例，40 分上贪心取 $25 + 10 + 5$ 共 3 枚，而 $20 + 20$ 只要 2 枚。

图 3-1 · 两组对照。背包一侧切换可否切割，找零一侧从 1 分逐格扫到 60 分，停在该组币值下最小的反例上。

警示 ·「规范币值」不是能从币值集合的样子看出来的性质。 $1, 3, 4$ 的最小反例是 6， $1, 7, 10$ 的最小反例是 14，而 $1, 5, 10, 20, 25$ 要扫到 40 才出问题。判断一组币值是否规范存在多项式时间算法，见参考文献第 3 条，它的存在本身说明这件事没有一眼可辨的判据。

三处失败的共同点是目标函数与可行性的耦合方式：分数背包里「装一部分」让任意两个解之间存在连续的中间状态，交换论证有落脚点；0-1 背包与找零的可行解之间是跳跃的，一次替换要动好几个元素。落到结构上，这两者都不是 matroid 上的最大权独立集问题。标准退路是把「已经花掉多少容量 / 已经凑出多少金额」记进状态做递推，即动态规划。

4 · 判断表

问题	贪心规则	最优	依据或反例
interval scheduling（计数）	earliest finish time	是	交换论证，见本系列第一页
interval scheduling（带权）	权重降序	否	区间系统不是 matroid： $10$ 对 $12$
minimum spanning tree	边权升序	是	graphic matroid，即 Kruskal
job sequencing with deadlines	利润降序	是	scheduling matroid
minimizing maximum lateness	截止时刻升序	是	相邻对调，见定理 1.2
Huffman coding	合并两个最小	是	交换论证，见建树
区间图着色	开始时刻升序	是	完美图上 $\chi = \omega$ ，见区间图
分数背包	单位价值降序	是	交换论证
0-1 背包	单位价值降序	否	容量 50 上 $160$ 对 $220$
找零（规范币值）	面额降序	是	需逐组验证
找零（任意币值）	面额降序	否	$1, 3, 4$ 上 6 分要 3 枚而非 2 枚
带权 matching	权重降序	否	matching 系统不是 matroid： $3$ 对 $4$

表里的「是」有两种来源。写着 matroid 的几行是结构性的，一旦验出交换性质，一切非负权函数上的最优性一并成立；写着交换论证的几行是逐题的，换一个目标函数就得重来。真正的差别在改需求的时候才显形：给区间加上权重，第一行立刻塌成第二行，而给生成树的边加上任意权重，第三行纹丝不动。

5 · 参考文献

Jackson, J. R. (1955). Scheduling a production line to minimize maximum tardiness (Research Report 43). Management Science Research Project, University of California, Los Angeles.
Kleinberg, J., & Tardos, É. (2005). Algorithm design (§4.2). Addison-Wesley.
Pearson, D. (2005). A polynomial-time algorithm for the change-making problem. Operations Research Letters, 33(3), 231–234.