两机器流水车间调度与 Johnson 法则：CP-Algorithms 的 O(n log n) 最优排序全解析

本文围绕 cp-algorithms 仓库中 双机器作业调度文档 的核心内容，系统讲解经典的两机器流水车间调度问题（2-machine flow shop scheduling）。你将掌握 Johnson 法则的完整数学推导（从空闲时间模型到相邻交换比较器）、两种等价排序策略，以及仓库中可直接运行的 C++ 实现与测试验证方法，从而在竞赛编程或实际排产场景中快速构造最优调度。

问题定义：每个作业依次经过两台机器

假设有 $n$ 个作业需要在两台机器 $M_1$、$M_2$ 上依次加工，每个作业必须先在第一台机器上处理，然后再到第二台机器上处理，处理过程不可抢占。作业 $i$ 在第一台机器上的耗时记为 $a_i$，在第二台机器上的耗时记为 $b_i$。同时，每台机器在同一时刻只能处理一个作业。

目标是确定作业的最优加工顺序，使得整个流程的最终完成时间（makespan）最小。

该问题的求解方法以 S. M. Johnson 命名，即 Johnson 法则（Johnson's rule）。原文档特别指出一个重要边界：当机器数量超过两台时，问题会退化为 NP-complete 的难题；因此 Johnson 法则的适用前提正是"恰有两台机器、且加工路径固定（先 $M_1$ 后 $M_2$）"的流水车间（flow shop）场景。

算法构造：以最小化第二台机器的总空闲时间为目标

第一步：两机器的作业顺序必须一致

首先可以证明一个简化前提：两台机器上的作业加工顺序应当一致。理由在于，作业只有经过第一台机器后才对第二台机器可用；若此时有多个作业同时可用，第二台机器无论按何种顺序加工它们，总处理时间都等于这些作业的 $b_i$ 之和，与顺序无关。因此，把作业按第一台机器上的完成顺序"原样"送入第二台机器，只会更有利（不会更差）。

第二步：定义第二台机器的空闲时间 $x_i$

考虑与输入顺序一致的作业序列 $1, 2, \dots, n$。定义 $x_i$ 为第二台机器在处理作业 $i$ 之前的空闲时间。目标是最小化总空闲时间：

$$F(x) = \sum x_i ~ \rightarrow \min$$

总空闲时间最小，等价于最终完成时间最小——因为第二台机器从开工到收工的总跨度等于"其加工总时长（固定）＋总空闲时间"。

逐项推导可得：

• 第一个作业：$x_1 = a_1$（第二台机器必须等第一台机器先干完作业 1 才能开工）；
• 第二个作业：作业 $2$ 在第一台机器上的可用时刻为 $a_1 + a_2$，而第二台机器空闲出来的时刻为 $x_1 + b_1$，故 $x_2 = \max\left((a_1 + a_2) - (x_1 + b_1), 0\right)$；
• 一般情形：

$$x_k = \max\left(\sum_{i=1}^k a_i - \sum_{i=1}^{k-1} b_i - \sum_{i=1}^{k-1} x_i, 0 \right)$$

于是总空闲时间 $F(x)$ 可以写成如下简洁形式：

$$F(x) = \max_{k=1 \dots n} K_i, \qquad K_i = \sum_{i=1}^k a_i - \sum_{i=1}^{k-1} b_i$$

其中 $K_i$ 与前面的递推式可借助数学归纳法验证等价（原文档直接给出了该断言，并说明"用归纳法即可轻松验证"）。这个 $K$ 表达式是整个推导的关键——它把复杂的递推空闲时间，化为仅与 $a$、$b$ 前缀和有关的简单量。

第三步：置换法推导相邻交换比较器

接下来使用置换法（permutation method）：交换相邻的两个作业 $j$ 与 $j+1$，考察总空闲时间如何变化。由 $K_i$ 的表达式形式可知，交换只影响 $K_j$ 与 $K_{j+1}$，设交换后的值为 $K_j'$ 与 $K_{j+1}'$。

若交换反而增大了总空闲时间（即原顺序更优），则必有：

$$\max(K_j, K_{j+1}) \le \max(K_j', K_{j+1}')$$

原文档指出：交换两个作业也可能完全不改变结果，因此上式只是充分条件而非必要条件——它用于判定"当前排列可以保证不再被相邻交换改进"。

在不等式两边同时消去公共部分 $\sum_{i=1}^{j+1} a_i - \sum_{i=1}^{j-1} b_i$ 后，化简得到：

$$\max(-a_{j+1}, -b_j) \le \max(-b_{j+1}, -a_j)$$

去掉负号、取负向 min 后，最终得到等价条件：

$$\min(a_j, b_{j+1}) \le \min(b_j, a_{j+1})$$

这就是 Johnson 比较器：对全部作业按该比较器排序后，所得排列中任意相邻两作业都无法通过交换进一步改善最终完成时间，因此该排序即为最优调度。

第四步：比较器的简化解释

原文档给出了一个极具操作性的视角：若已知相邻作业的四段时间 $(a_j, a_{j+1}, b_j, b_{j+1})$，则：

• 若四者中的最小值来自第一台机器（即某个 $a$），则该作业应当排在前面；
• 若最小值来自第二台机器（即某个 $b$），则该作业应当排在后面。

据此可进一步简化排序规则：按 $\min(a_i, b_i)$ 对作业排序；当某个作业满足 $a_i < b_i$（其关键时间来自第一台机器）时，把它放到所有剩余作业之前；否则（$a_i \ge b_i$）放到所有剩余作业之后。

于是问题归结为一次排序，时间复杂度为 $O(n \log n)$。

算法复杂度

无论采用哪种排序实现（基于比较器 $\min(a_j, b_{j+1}) \le \min(b_j, a_{j+1})$，或基于简化后的"按 $\min(a_i, b_i)$ 分组首尾拼接"），Johnson 法则都能在 $O(n \log n)$ 时间内求解——排序是唯一的非平凡开销，其余分组合并均为线性时间。这与原文档的结论一致。

C++ 实现与逐段解读

原文档提供了完整实现（采用上述简化后的"分组拼接"变体）。仓库中该代码块被标注为 {.cpp file=johnsons_rule}，可由 提取脚本 自动抽取为独立的 johnsons_rule.h 头文件，供测试直接 #include 使用，因此可直接复制进你的项目。

struct Job {
    int a, b, idx;

    bool operator<(Job o) const {
        return min(a, b) < min(o.a, o.b);
    }
};

vector<Job> johnsons_rule(vector<Job> jobs) {
    sort(jobs.begin(), jobs.end());
    vector<Job> a, b;
    for (Job j : jobs) {
        if (j.a < j.b)
            a.push_back(j);
        else
            b.push_back(j);
    }
    a.insert(a.end(), b.rbegin(), b.rend());
    return a;
}

pair<int, int> finish_times(vector<Job> const& jobs) {
    int t1 = 0, t2 = 0;
    for (Job j : jobs) {
        t1 += j.a;
        t2 = max(t2, t1) + j.b;
    }
    return make_pair(t1, t2);
}

逐段解读：

• struct Job：封装每个作业的全部信息——第一台机器耗时 a、第二台机器耗时 b、原始编号 idx（idx 用于在需要时还原作业身份）。重载的 < 运算符实现"按 $\min(a_i, b_i)$ 升序"排序，这是简化版比较器的直接落地。
• johnsons_rule：先按上述规则排序；随后把满足 a < b 的作业放入序列 a（对应"关键时间来自第一台机器、应靠前"），其余放入序列 b；最终用 a.insert(a.end(), b.rbegin(), b.rend()) 将 b 倒序拼接到 a 之后——这正是"$\min(a_i,b_i)$ 值越大的后组作业越靠后"的体现，保证后组内部也满足最优顺序。
• finish_times：给定一个调度后，模拟两台机器的推进计算最终完成时间：t1 累加第一台机器的处理时间，t2 = max(t2, t1) + j.b 表示第二台机器要么等当前作业就绪（t1），要么等自己空闲（t2），二者取较大者后再加上 b_j。返回 (t1, t2) 即两台机器各自的完成时刻，其中 t2 就是整个调度的 makespan。

仓库中的自动化验证：测试用例与运行方式

文章里的代码块之所以可靠，是因为 cp-algorithms 为每个含代码的文档配套了可编译测试。对应本主题的测试文件是 test_johnsons_rule.cpp，其用例取自维基百科，包含 5 个作业：

作业	$a_i$（第一台）	$b_i$（第二台）
1	32	42
2	47	15
3	22	50
4	58	40
5	31	28

测试断言 finish_times(schedule) == make_pair(190, 205)，即最优调度下第一台机器于时刻 190 完工、第二台机器于时刻 205 完工。我们可以手工推演验证：

1. 分组：作业 3、1 满足 $a<b$ 进入前组；作业 4、5、2 进入后组；
2. 前组按 $\min(a,b)$ 升序为 $[3, 1]$；后组按 $\min(a,b)$ 升序为 $[2, 5, 4]$，倒序拼接后整体调度为 $[3, 1, 4, 5, 2]$；
3. 逐步模拟：作业 3 → $t_1=22, t_2=72$；作业 1 → $t_1=54, t_2=\max(72,54)+42=114$；作业 4 → $t_1=112, t_2=\max(114,112)+40=154$；作业 5 → $t_1=143, t_2=\max(154,143)+28=182$；作业 2 → $t_1=190, t_2=\max(182,190)+15=205$。

最终得到 $(190, 205)$，与测试断言完全吻合，从侧面印证了推导与实现的正确性。

本地复现整个验证流程的方式如下（仓库为只读，以下仅为查看与运行方法）：

1. 进入 test 目录，运行 extract_snippets.py，它会按正则 ^\s*```\{.cpp\s+file=(\S+)\}$ 扫描 src/ 下所有文档，把 file= 标注的代码块抽取为同名 .h 头文件（本主题即生成 johnsons_rule.h）；
2. 运行 test.sh，脚本会用 g++ -std=c++17 -fsanitize=undefined 逐个编译并执行全部测试文件；test_johnsons_rule.cpp 通过 assert 校验最优性，全部通过即输出 PASSED。

与仓库其他调度主题的关联

在 src/schedules 目录下，本主题属于一个完整的调度问题系列：

• 单机器作业调度（最优调度与惩罚函数）：研究单一机器上按序加工、以等待时间惩罚函数最小化为目标的问题，同样通过置换法推导出"按某个键值排序即可得最优"的结论，并讨论了线性惩罚、指数惩罚与同单调惩罚三种特例（Livshits-Kladov 定理）；
• 给定截止时间与持续时间的作业最优调度：贪心 + 优先队列的 $O(n \log n)$ 方案，目标是完成尽可能多的作业。

三者互补，共同覆盖了竞赛中常见的几类调度模型。本主题（Johnson 法则）的核心方法论——构造目标量 → 置换法考察相邻交换 → 导出可排序的比较器——在单机调度文档中亦有体现，可以作为方法论层面的横向对照。

小结

Johnson 法则解决的是两机器流水车间调度这一经典问题，其关键步骤可以概括为：

1. 论证两台机器的作业顺序可以（且应当）一致；
2. 引入第二台机器的空闲时间 $x_i$，把最小化 makespan 转化为最小化总空闲时间；
3. 将总空闲时间化简为 $K_i$ 前缀和的最大值形式；
4. 用置换法交换相邻作业，导出比较器 $\min(a_j, b_{j+1}) \le \min(b_j, a_{j+1})$；
5. 将比较器等价化为"按 $\min(a_i, b_i)$ 排序、$a_i<b_i$ 前置否则后置"的分组拼接规则；
6. 最终通过一次 $O(n \log n)$ 排序得到最优调度。

配合 test_johnsons_rule.cpp 的维基百科标准用例（期望 makespan 为 205），你可以放心地把这套实现用于竞赛答题或实际的两机排产场景。需要说明的是，一旦机器数超过两台，问题即变为 NP-complete，Johnson 法则不再适用。