我的算法书 - 双机器调度问题（贪心）

一句话算法

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

问题模型

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

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

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

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

设某个固定顺序下：

A_i=\sum_{j=1}^{i}a_j

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

C_i=\max(C_{i-1},A_i)+b_i

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

核心直觉

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

当前作业已经从 $M_1$ 上出来；
$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 法则是：

a_i\le b_i \text{ 的作业放前面，按 } a_i \text{ 升序}

a_i>b_i \text{ 的作业放后面，按 } b_i \text{ 降序}

算法步骤

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

C_i=\max(C_{i-1},A_i)+b_i

等价写法

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

算法证明

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

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

目标函数变形

展开递推式：

C_i=\max_{1\le k\le i}\left(A_k+\sum_{t=k}^{i}b_t\right)

所以：

\max_{1\le i\le n}C_i = \max_{1\le i\le n} \max_{1\le k\le i} \left(A_k+\sum_{t=k}^{i}b_t\right)

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

\max_{1\le i\le n}C_i = \max_{1\le k\le n} \left(A_k+\sum_{t=k}^{n}b_t\right)

记：

B_i=\sum_{j=1}^{i}b_j

则：

\sum_{t=k}^{n}b_t=B_n-B_{k-1}

于是：

\max_i C_i = B_n+\max_{1\le k\le n}(A_k-B_{k-1})

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

\max_{1\le k\le n}(A_k-B_{k-1})

为什么这一步重要

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

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

考虑相邻两个作业：

x=(a_x,b_x),\qquad y=(a_y,b_y)

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

D=A_{i-1}-B_{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$ ，局部最大值为：

D+\max(a_x,\ a_x+a_y-b_x)

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

D+\max(a_y,\ a_x+a_y-b_y)

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

\max(a_x,\ a_x+a_y-b_x) \le \max(a_y,\ a_x+a_y-b_y)

推出 Johnson 顺序

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

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

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

a_x+a_y-b_x\le a_y

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

\max(a_x,\ a_x+a_y-b_x)\le a_y

而：

\max(a_y,\ a_x+a_y-b_y)\ge a_y

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

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

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

a_x+a_y-b_x\le a_x+a_y-b_y

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

a_x+a_y-b_y>a_x

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

a_x,\qquad a_x+a_y-b_x

因此：

\max(a_x,\ a_x+a_y-b_x) \le \max(a_y,\ a_x+a_y-b_y)

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

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

若：

a_x\le b_x,\qquad a_y>b_y

则：

a_x+a_y-b_x\le a_y

因此：

\max(a_x,\ a_x+a_y-b_x)\le \max(a_x,a_y)

另一方面，右边：

\max(a_y,\ a_x+a_y-b_y)

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

a_x+a_y-b_y>a_x

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

\max(a_y,\ a_x+a_y-b_y)\ge \max(a_x,a_y)

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

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

复杂度分析

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

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

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

代码实现

C++

cpp

        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;
}

Python

并列作业（比较器判等）的先后不是契约：std::sort 与 Timsort 的稳定性不同，输出顺序可能不同但都合法。

python

        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

        # 两台机器流水作业调度（Johnson 法）：按 min(a, b) 排序后顺序通过两台机器。
# 排序规则：a <= b 的"前段作业"在前（按 a 升序），a > b 的"后段作业"在后（按 b 降序）。
# C++ 用 long long 防止 finish_m1 累加溢出 int；Python int 任意精度，该坑不存在。

from functools import cmp_to_key

type Jobs = list[Job]


class Job:
    """id 是输入顺序（1 开始），仅用于输出加工顺序；a、b 是两台机器的加工时长。"""

    def __init__(self, id: int, a: int, b: int) -> None:
        self.id = id
        self.a = a
        self.b = b


def johnson_cmp(x: Job, y: Job) -> bool:
    # 对应 C++ 的严格弱序比较器：返回 True 表示 x 应排在 y 前面。
    x_front = x.a <= x.b
    y_front = y.a <= y.b

    if x_front != y_front:
        return x_front and not y_front
    if x_front:
        return x.a < y.a
    return x.b > y.b


def sort_jobs(jobs: Jobs) -> None:
    # C++ 的 sort 直接吃“是否更靠前”的严格弱序比较器；cmp_to_key 需要三向比较，
    # 这里用 johnson_cmp(x, y) / johnson_cmp(y, x) 拼出 -1/0/1，保持 johnson_cmp 本身与 C++ 同签名。
    # 并列作业（比较器判等）的先后不是契约：std::sort 不稳定、Timsort 稳定，两边可能不同但都合法。
    def three_way(x: Job, y: Job) -> int:
        if johnson_cmp(x, y):
            return -1
        if johnson_cmp(y, x):
            return 1
        return 0

    jobs.sort(key=cmp_to_key(three_way))


def finish_time(jobs: Jobs) -> int:
    finish_m1 = 0
    finish_m2 = 0
    for job in jobs:
        finish_m1 += job.a
        # 机器 2 必须等：作业上机时刻是 max(finish_m2, finish_m1)，再加工 job.b。
        finish_m2 = max(finish_m2, finish_m1) + job.b
    return finish_m2

测试用例

输入：

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

逐步计算：

位置	作业	$A_i$	$C_i$
1	5	1	8
2	1	3	13
3	3	6	16
4	2	10	18
5	4	16	19

输出：

19
5 1 3 2 4

与皇后游戏的关系

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

c_i=\max(c_{i-1},\sum_{j=1}^{i}a_j)+b_i

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

$\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(上一任务完成时间, 当前任务到达时间) 递推。

应用场景	经典题目	核心思路
两台机器加工	通用 Johnson 模型	$a\le b$ 放前面，按 $a$ 升序； $a>b$ 放后面，按 $b$ 降序

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

典型模式： 题面给出两个数 $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$ 看成第二阶段完成时间。

应用场景	经典题目	核心思路
皇后游戏	luogu-P2123	把奖金递推转成两机流水作业调度

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

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

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

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

应用场景	经典题目	核心思路
Johnson 证明	本文模型	将目标化成 $B_n+\max(A_i-B_{i-1})$ 后做相邻交换
排序贪心证明	排序不等式	用交换前后的差值推出排序方向

经典例题

luogu-P2123 皇后游戏。题面是奖金递推，本质是两机流水作业调度。重点是识别 $c_i=\max(c_{i-1},A_i)+b_i$ 。
两台机器流水作业调度给出 $n$ 个作业的 $(a_i,b_i)$ ，要求最小化最后完成时间。直接套 Johnson 法则。
排序贪心证明题如果题目允许重排，并且相邻交换能推出一个比较规则，可以优先尝试相邻交换法。排序不等式是最基础的例子，Johnson 法则是“先变形目标函数再交换”的例子。

参考

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

一句话算法

问题模型

核心直觉

算法步骤

算法证明

目标函数变形

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

推出 Johnson 顺序

复杂度分析

代码实现

测试用例

与皇后游戏的关系

常见误区

一、按 ai+bia_i+b_iai​+bi​ 升序排序

二、按 ai−bia_i-b_iai​−bi​ 排序

三、套到三台及以上机器

应用分类详解

一、两机流水作业调度

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

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

经典例题

参考

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

二、按 $a_i-b_i$ 排序