做调度题时，最容易犯的错是只盯着每个工件的加工时长。真正决定排程好坏的，往往是机器之间空出来的那段时间。

流水车间就是这个现象最简单的模型：每件工件都按同一条路线经过机器，下一道工序必须等上一道结束。换一下工件顺序，等待会被放大，也可能被消掉。这篇笔记只讨论最常见的排列流水车间（permutation flow shop）：所有机器采用同一个工件顺序。

先写出递推式

设有 (n) 件工件、(m) 台机器。工件 (j) 在机器 (k) 上的加工时间为 (p_{j,k})。若排列为

π=(π1,π2,…,πn),\pi = (\pi_1,\pi_2,\ldots,\pi_n),

则第 (i) 个工件在第 (k) 台机器上的完成时刻满足

Cπi,k=max⁡(Cπi−1,k, Cπi,k−1)+pπi,k.C_{\pi_i,k} = \max\left(C_{\pi_{i-1},k},\, C_{\pi_i,k-1}\right) + p_{\pi_i,k}.

这里两个量都不能跳过：(C_{\pi_{i-1},k}) 表示机器何时腾出来，(C_{\pi_i,k-1}) 表示工件何时从上一道工序流出。边界取 (C_{\pi_0,k}=C_{\pi_i,0}=0)。

通常关心的是最后一个工件离开最后一台机器的时刻：

Cmax⁡=Cπn,m.C_{\max}=C_{\pi_n,m}.

这就是 makespan（最大完工时间）。所谓“排得更好”，在这里就是让 (C_{\max}) 更小。

一个三工件的算例

有两台机器，三件工件的加工时间如下。

工件(M_1)(M_2)
A36
B72
C45

若取顺序 (A\to B\to C)，在第二台机器上的完成时刻是

CA,2=max⁡(3,0)+6=9,CB,2=max⁡(10,9)+2=12,CC,2=max⁡(14,12)+5=19.\begin{aligned} C_{A,2} &= \max(3,0)+6=9,\\ C_{B,2} &= \max(10,9)+2=12,\\ C_{C,2} &= \max(14,12)+5=19. \end{aligned}

所以 (C_{\max}=19)。注意 B 在 (M_2) 上只需 2 个时间单位，却不能让总工期变短；瓶颈不在它自身，而在前面留下的衔接关系里。

两台机器：Johnson 法则为什么有效

当机器恰好只有两台，目标是最小化 (C_{\max}) 时，Johnson 法则给出最优排列。做法很短：

  1. 在所有尚未排入序列的加工时间中找最小值；
  2. 最小值若来自 (M_1)，把该工件放到当前序列最左边的空位；
  3. 若来自 (M_2)，把它放到最右边的空位；
  4. 重复直到排完。

这个规则看似反直觉，其实是在处理两端的等待。一个在 (M_1) 上很快的工件，应尽早把后续机器“喂起来”；一个在 (M_2) 上很快的工件，靠后放通常不会拖住尾部。Johnson 的原论文给出了交换论证：如果某个相邻对违背这个安排，把它们交换不会增加最大完工时间。

在上面的数据中，最小加工时间是 (B) 在 (M_2) 上的 2，因此 B 放在末尾；接着 A 放在最前，得到

A→C→B.A\to C\to B.

此时 (C_{\max}=16)，比 (A\to B\to C) 少 3 个时间单位。

def johnson_order(processing_times):
    remaining = dict(processing_times)
    front, back = [], []

    while remaining:
        job, (m1, m2) = min(
            remaining.items(),
            key=lambda item: min(item[1]),
        )
        (front if m1 <= m2 else back).append(job)
        del remaining[job]

    return front + back[::-1]


jobs = {"A": (3, 6), "B": (7, 2), "C": (4, 5)}
print(johnson_order(jobs))  # ['A', 'C', 'B']

多台机器以后，为什么先试 NEH

机器增加到三台或更多时，简单的两端规则不再保证最优。常用记号 (F_m\Vert C_{\max}) 也提醒了这一点：机器数 (m) 是问题的一部分，排列数量会随工件数呈阶乘增长。

NEH 启发式是一个很实用的起点。它先按每件工件的总加工时间降序排序，再逐个插入当前序列的所有可能位置，每次保留 (C_{\max}) 最小的那个位置。它没有神奇地避开组合爆炸；它只是把搜索预算优先给了“加工总量大”的工件。

这个想法和实际排程很接近：先用 NEH 生成一个靠谱初解，再根据换模时间、交期、缓冲区等约束做局部搜索或整数规划。若数据本身不可靠，再精妙的启发式也只是在优化一个错误的模型。

参考文献与延伸阅读

  1. S. M. Johnson, “Optimal Two- and Three-Stage Production Schedules with Setup Times Included,” Naval Research Logistics Quarterly, 1954. 原始论文（DOI）
  2. M. Nawaz, E. E. Enscore, Jr., and I. Ham, “A Heuristic Algorithm for the (m)-Machine, (n)-Job Flow-Shop Sequencing Problem,” Omega, 1983. NEH 原始论文（DOI）
  3. Michael L. Pinedo, Scheduling: Theory, Algorithms, and Systems, 5th ed., Springer, 2016. 书籍页面