双机器调度问题（贪心）

一句话算法

先把“第一台快、第二台慢”的作业放前面，再把“第一台慢、第二台快”的作业放后面，让第二台机器尽量少等待。

问题模型

有 $n$ 个作业，每个作业必须先经过第一台机器 $M_1$，再经过第二台机器 $M_2$。

第 $i$ 个作业有两个加工时间：

• $a_i$：在 $M_1$ 上的加工时间；
• $b_i$：在 $M_2$ 上的加工时间。

现在可以重新排列作业顺序。目标是最小化最后一个作业在 $M_2$ 上完成的时间，也就是最小化整体完工时间。

设某个固定顺序下：

表示第 $i$ 个作业在 $M_1$ 上完成的时间。设 $C_i$ 表示第 $i$ 个作业在 $M_2$ 上完成的时间，则：

其中 $C_0=0$。这个递推也是 luogu-P2123 “皇后游戏”中的核心式子。

核心直觉

第二台机器只有在两个条件都满足时才能加工当前作业：

1. 当前作业已经从 $M_1$ 上出来；
2. $M_2$ 已经完成前一个作业。

所以真正要避免的是：$M_2$ 空在那里等 $M_1$。

对于一个作业 $(a,b)$：

• 若 $a\le b$，它能较快通过 $M_1$，但会在 $M_2$ 上占较久，适合放前面，让 $M_2$ 尽早忙起来。
• 若 $a>b$，它在 $M_1$ 上拖得久，在 $M_2$ 上很快结束，适合放后面，避免一开始就让 $M_2$ 等太久。

于是 Johnson 法则是：

算法步骤

1. 将所有作业分成两类：
   • 第一类：$a_i\le b_i$；
   • 第二类：$a_i>b_i$。
2. 第一类按 $a_i$ 从小到大排序。
3. 第二类按 $b_i$ 从大到小排序。
4. 将第一类放在前面，第二类放在后面。
5. 按这个顺序扫描，使用递推式计算最短完成时间：

也可以每次在未安排作业中找最小的 $\min(a_i,b_i)$。如果最小值来自 $a_i$，就放到序列最前面的空位；如果来自 $b_i$，就放到最后面的空位。这个写法和上面的分类排序等价。

算法证明

证明使用相邻交换法：如果两个相邻作业不符合 Johnson 顺序，交换它们不会使答案变差。不断交换相邻逆序对后，就能得到 Johnson 顺序，因此 Johnson 顺序最优。

难点在于，直接交换相邻两个作业时，后面的 $C_i$ 可能都会变化。为了让交换只影响局部，需要先把目标函数换一种写法。

目标函数变形

展开递推式：

所以：

对固定的 $k$，因为 $b_t$ 都是非负加工时间，$i$ 越往后，$\sum_{t=k}^{i}b_t$ 越大。因此最大值一定在 $i=n$ 处取得：

记：

则：

于是：

$B_n$ 是所有 $b_i$ 的总和，和排列顺序无关。因此原问题等价于最小化：

原来的 $C_i$ 在交换后可能影响一长段后缀；换成 $A_k-B_{k-1}$ 后，交换相邻两项只影响两个位置。这样相邻交换证明才变成局部问题。

相邻交换只影响两个候选值

考虑相邻两个作业：

它们位于第 $i$ 位和第 $i+1$ 位。设前 $i-1$ 个作业中：

对于 $k<i$，前面的作业完全不变，所以 $A_k-B_{k-1}$ 不变。

对于 $k\ge i+2$，不管顺序是 $x,y$ 还是 $y,x$，这些位置之前都已经同时包含 $x$ 和 $y$，所以 $a_x+a_y$ 与 $b_x+b_y$ 都不变。因此后面的候选值也不变。

所以只需要比较第 $i$ 和第 $i+1$ 两个候选值。

若顺序为 $x,y$，局部最大值为：

若顺序为 $y,x$，局部最大值为：

因此 $x$ 放在 $y$ 前面不劣，当且仅当：

推出 Johnson 顺序

下面验证 Johnson 法则中的三种情况。

情况一：两个作业都满足 $a\le b$。

若 $a_x\le b_x$，$a_y\le b_y$，并且 $a_x\le a_y$，则：

又有 $a_x\le a_y$，所以：

而：

故 $x$ 放在 $y$ 前面不劣。第一类内部应按 $a$ 升序。

情况二：两个作业都满足 $a>b$。

若 $a_x>b_x$，$a_y>b_y$，并且 $b_x\ge b_y$，则：

又因为 $a_y>b_y$，所以：

右边最大值中的第二项同时不小于左边最大值中的两项：

因此：

第二类内部应按 $b$ 降序。

情况三：$x$ 满足 $a\le b$，$y$ 满足 $a>b$。

若：

则：

因此：

另一方面，右边：

显然不小于 $a_y$；又因为 $a_y>b_y$，有：

所以右边也不小于 $a_x$。因此：

于是 $x$ 放在 $y$ 前面不劣。所有 $a\le b$ 的作业都应放在所有 $a>b$ 的作业前面。

三种情况合起来，正好得到 Johnson 法则。证明完成。

复杂度分析

排序需要 $O(n\log n)$，排序后扫描计算完成时间需要 $O(n)$。

• 时间复杂度：$O(n\log n)$。
• 空间复杂度：$O(n)$，用于保存作业。

如果只需要答案，不需要输出顺序，仍然需要保存作业用于排序。

代码实现

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

        #include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

struct Job {
    int id;
    long long a;
    long long b;
};

bool johnson_cmp(const Job& x, const Job& y) {
    const bool x_front = x.a <= x.b;
    const bool y_front = y.a <= y.b;

    if (x_front != y_front) return x_front > y_front;
    if (x_front) return x.a < y.a;
    return x.b > y.b;
}

long long finish_time(const vector<Job>& jobs) {
    long long finish_m1 = 0;
    long long finish_m2 = 0;

    for (const Job& job : jobs) {
        finish_m1 += job.a;
        finish_m2 = max(finish_m2, finish_m1) + job.b;
    }

    return finish_m2;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<Job> jobs(n);
    for (int i = 0; i < n; ++i) {
        cin >> jobs[i].a >> jobs[i].b;
        jobs[i].id = i + 1;
    }

    sort(jobs.begin(), jobs.end(), johnson_cmp);

    cout << finish_time(jobs) << '\n';
    for (int i = 0; i < n; ++i) {
        if (i) cout << ' ';
        cout << jobs[i].id;
    }
    cout << '\n';

    return 0;
}
    

测试用例

输入：

5
2 5
4 2
3 3
6 1
1 7

Johnson 分类：

• $a\le b$：作业 $1(2,5)$、$3(3,3)$、$5(1,7)$，按 $a$ 升序得到 5 1 3；
• $a>b$：作业 $2(4,2)$、$4(6,1)$，按 $b$ 降序得到 2 4。

最终顺序：

5 1 3 2 4

逐步计算：

输出：

19
5 1 3 2 4

与皇后游戏的关系

luogu-P2123 “皇后游戏”虽然题面不是机器调度，但它的递推式是：

这和两台机器流水作业调度完全一致：

• $\sum_{j=1}^{i}a_j$ 对应第 $i$ 个作业在 $M_1$ 上完成的时间；
• $c_i$ 对应第 $i$ 个作业在 $M_2$ 上完成的时间；
• $b_i$ 对应第 $i$ 个作业在 $M_2$ 上的加工时间。

所以皇后游戏的排序规则也是：

a <= b 的放前面，按 a 升序
a > b 的放后面，按 b 降序

多组数据时，只需要对每组分别排序并扫描。答案可能很大，使用 long long。

常见误区

一、按 $a_i+b_i$ 升序排序

这个规则只看单个作业总时间，没有考虑两台机器之间的衔接。流水作业调度的关键不是单个作业短不短，而是 $M_2$ 会不会等待。

二、按 $a_i-b_i$ 排序

$a_i-b_i$ 的正负可以帮助分组，但不能直接作为完整排序规则。Johnson 法则是：

先按 a <= b 分前后两类；
前一类按 a 升序；
后一类按 b 降序。

三、套到三台及以上机器

Johnson 法则直接解决的是两台机器流水作业调度。三台及以上机器的调度问题更复杂，不能直接套这个比较器。

应用分类详解

Johnson 法则的本质是：当每个任务都必须经过两个连续阶段时，用相邻交换推出一个全局最优排序。

一、两机流水作业调度

典型模式： 每个任务必须先经过阶段一，再经过阶段二，两个阶段各有一个耗时。

识别信号： 题面出现“两台机器”“先 A 后 B”“流水线”“最后完成时间最小”。

核心建模： 第一阶段的前缀和是到达第二阶段的时间，第二阶段用 max(上一任务完成时间, 当前任务到达时间) 递推。

二、伪装成递推的最值问题

典型模式： 题面给出两个数 $a_i,b_i$，允许重排，并且答案递推含有 max(前一个状态, 前缀和)+b_i。

识别信号： 出现类似 $c_i=\max(c_{i-1},\sum a)+b_i$ 的式子，目标是最小化 $\max c_i$ 或最后的 $c_n$。

核心建模： 把 $\sum a$ 看成第一阶段完成时间，把 $c_i$ 看成第二阶段完成时间。

三、相邻交换证明排序规则

典型模式： 需要安排一个顺序，直接看全局很难，但可以比较相邻两项交换前后的最坏值。

识别信号： “任意排列”“最小化最大值”“相邻交换后前缀和后缀结构可化简”。

核心建模： 先把目标函数化成只受相邻两项影响的局部候选值，再推出比较器。

经典例题

1. luogu-P2123 皇后游戏。题面是奖金递推，本质是两机流水作业调度。重点是识别 $c_i=\max(c_{i-1},A_i)+b_i$。

2. 两台机器流水作业调度 给出 $n$ 个作业的 $(a_i,b_i)$，要求最小化最后完成时间。直接套 Johnson 法则。

3. 排序贪心证明题 如果题目允许重排，并且相邻交换能推出一个比较规则，可以优先尝试相邻交换法。排序不等式是最基础的例子，Johnson 法则是“先变形目标函数再交换”的例子。

参考

• Johnson, S. M. “Optimal two- and three-stage production schedules with setup times included.” Naval Research Logistics Quarterly, 1954.
• luogu-P2123
• 排序不等式