流水作业调度问题，我最早接触它是在做一条模拟产线的排产优化时。车间里有若干工件，每个都要依次经过固定的几台机器，怎么安排加工顺序，才能让整批工件最早完工？这个问题看起来像排队，其实藏着非常精巧的算法结论。今天这篇文章围绕“流水作业调度问题”展开，重点讲透两台机器下的经典解法——Johnson法则，包括它的适用条件、推导思路、完整代码、坑点案例，以及往三台机器和更大规模问题延伸时的思路。
1. 流水作业调度问题到底在解决什么
1.1 从一条生产线上的排队故事说起
想象一个零件加工车间：所有工件进门后先上铣床，再上车床，再上磨床，顺序完全固定，谁都不能“跳工序”。工件数量一多，工序之间就会出现互相等待。如果先做加工时间长的工件，后面的工件可能在第一台机器上干等，后面的机器又空转；如果先做后续工序重的工件，前面工序又会阻塞。调度问题的目标，就是找到一种工件的加工顺序，让整批工件完成所有工序的总时间最小。
这个总时间在学术上叫makespan，也就是从第一个工件开始加工，到最后一个工件全部完工的跨度。它直接决定了产能、设备利用率和订单交付周期。在面试算法题里，它通常表现为：给定若干任务、两台机器，每项任务必须先在 M1 上加工，再到 M2 上加工，求最小化总完工时间。
流水作业调度问题是一个典型的组合优化问题。n 个工件就有 n! 种排列，一一枚举在工程上不可行。两台机器的情况之所以适合作为学习起点，是因为它存在一个漂亮的多项式算法，背后的思想还不止能用在流水线上。
1.2 数学建模：n个工件、m台机器、一张加工时间表
把问题写清楚并不复杂。设有 n 个工件 J_1, J_2, ..., J_n，需要依次经过 m 台机器 M_1, M_2, ..., M_m 加工，所有工件在机器上的工艺路线完全一致，也就是说这是一个流水作业（flow shop）环境。每个工件在机器 M_j 上有一个已知的加工时间 p_{i,j}，机器同一时刻只能加工一个工件，工件同一时刻只能在一台机器上加工，不允许抢占。
我们要找一个所有工件共同的加工顺序 π，使得最大完成时间 C_max 最小，即：
C_max(π) = 所有工件完成时刻的最大值
这里有个关键限制值得注意：流水作业调度通常还会区分“置换流水线”和“非置换流水线”。我的代码和下面的推导都默认所有工件在每台机器上保持相同的先后顺序，这叫做置换流水作业调度（permutation flow shop）。如果不要求顺序一致，问题会变得更加复杂，Johnson法则也不适用。
当 m=2 且目标是极小化 makespan 时，1954 年提出的 Johnson 法则给出了精确解法。它的核心思想只有一句话：把“M1 上耗时短、M2 上耗时长”的工件尽量往前放，把“M1 上耗时长、M2 上耗时短”的工件尽量往后放。别小看这句话，它背后是严谨的置换论证。
2. 两台机器的Johnson法则：分组、排序、合并三步走
2.1 适用边界：什么样的流水作业才能用Johnson法则
Johnson法则解决的是两台机器、所有工件同顺序加工、目标是最小化总完工时间的问题。如果满足以下条件，就可以直接使用：
- 只有两台机器 M1、M2。
- 每个工件必须按 M1 → M2 的顺序加工。
- 所有工件在两条机器上的加工时间均已知，且不随排列变化。
- 目标是极小化 makespan。
如果你的场景里出现了交货期约束、优先级权重、并行机器，或者允许不同工件在中间工序形成不同顺序，那么 Johnson 法则的结论就不成立了。很多人踩坑就踩在这儿：问题看起来像两台机器，但细究之下并不是标准的流水作业。
2.2 法则描述：A组升序、B组降序，到底为什么
Johnson法则的操作步骤非常简单，我先把流程写出来：
设工件 i 在 M1 上的加工时间为 a_i，在 M2 上的加工时间为 b_i。
- 把所有满足 a_i ≤ b_i 的工件分到组 A。
- 把所有满足 a_i > b_i 的工件分到组 B。
- 组 A 按 a_i升序排列。
- 组 B 按 b_i降序排列。
- 拼接：组A排好的序列 + 组B排好的序列，就是最优加工顺序。
为什么这样分组？直觉是：M1 小时耗时短的工件应该优先释放，让 M2 尽快跑起来；M2 上耗时长的工件如果出现在队尾，不会因为拖住 M1 而影响整体收尾。用更工程化的说法，A 组代表“M2 是瓶颈”的工件，B 组代表“M1 是瓶颈”的工件。先处理 M2 瓶颈品，把 M1 瓶颈品推到比较靠后的位置，整个系统的空闲时间才会最小。
注意，这个规则不是简单地“按 a 升序”或“按 b 降序”，而是分组后再分别排序。这个细微差别，正是很多人实现时做错的地方。
2.3 交换论证：理解最优性的一把钥匙
要说服自己 Johnson 法则真的最优，光靠直觉不够。这里提供一个经典思路：相邻交换论证。
假设当前有一个可行顺序，其中相邻工件 X 和 Y 满足 X 在 Y 前面。现在交换它们的位置，看看 makespan 会发生什么变化。计算两台机器上的完成时间可以发现，交换只会影响这两段交汇处的空闲时间和收尾位置。如果存在一对相邻工件，交换后 makespan 不增加，那么把这对相邻工件“纠正”成满足 Johnson 排序规则的顺序，就是安全的；反复纠正直到所有相邻对都满足该规则，得到的排列就是最优的。
具体推导时，比较两个方案的 M2 完工时间差值，可以得到一个判据：当 min(a_X, b_Y) ≤ min(a_Y, b_X) 时，X 排在 Y 前面不会比 Y 排在 X 前面差。对全体工件做传递排序后，恰好得到 A 组按 a 升序、B 组按 b 降序的排列。这就是 Johnson 法则的来源。
这个推导的价值在于：它能告诉你哪些排序规则是“靠得住的”，哪些只是近似。比如单纯按 a 升序，虽然能减少 M1 的等待，但可能让 M2 在后期饿死；单纯按 b 降序，又会让 M1 的堆积加大。分组排序之所以最优，是因为它同时兼顾了两台机器的瓶颈。
3. 实操落地：从手算到代码
3.1 手算一个完整案例：五工件两台机器全过程
理论讲多了容易飘，我直接上一个具体例子。有 5 个工件，加工时间如下：
| 工件 | M1 加工时间 a | M2 加工时间 b |
|---|---|---|
| J1 | 5 | 2 |
| J2 | 3 | 4 |
| J3 | 6 | 8 |
| J4 | 4 | 1 |
| J5 | 2 | 5 |
先分组：
- a ≤ b 的工件：J2(3 ≤ 4)、J3(6 ≤ 8)、J5(2 ≤ 5)，进入 A 组。
- a > b 的工件：J1(5 > 2)、J4(4 > 1)，进入 B 组。
A 组按 a 升序：J5(2)、J2(3)、J3(6)。
B 组按 b 降序：J1(2)、J4(1)。
合并结果：J5 → J2 → J3 → J1 → J4。
接下来算这个顺序下的 makespan，验证效果。规则很简单：M1 按顺序累加工件；M2 的完工时间 = max(M2 前序完成时间, 当前工件 M1 完成时间) + b。
| 步骤 | 工件 | M1 完成 | M2 开始 | M2 完成 |
|---|---|---|---|---|
| 1 | J5 | 2 | 2 | 7 |
| 2 | J2 | 5 | 7 | 11 |
| 3 | J3 | 11 | 11 | 19 |
| 4 | J1 | 16 | 19 | 21 |
| 5 | J4 | 20 | 21 | 22 |
最终 makespan = 22。
我随手试另一个顺序 J1 → J4 → J3 → J2 → J5，算出来 makespan = 32。差距非常明显。在这个例子里，Johnson 顺序比一个“随便拍脑袋”的顺序节省了整整 10 个时间单位，这就是调度的价值。
3.2 Python实现：排序加一行makespan计算
Johnson 法则的代码实现极其简洁，核心逻辑就是分组、排序、拼接。下面是可直接运行的 Python 代码：
def johnson_order(jobs): """ jobs: list of tuples, 每个元素为 (id, a, b) 返回最优加工顺序的 id 列表 """ group_a = [] # a <= b group_b = [] # a > b for job in jobs: job_id, a, b = job if a <= b: group_a.append(job) else: group_b.append(job) # A 组按 M1 时间升序 group_a.sort(key=lambda x: x[1]) # B 组按 M2 时间降序 group_b.sort(key=lambda x: x[2], reverse=True) return [job[0] for job in group_a + group_b] def compute_makespan(order, jobs): """给定工件顺序，计算两台机器下的总完工时间""" time_map = {job_id: (a, b) for job_id, a, b in jobs} m1_time = 0 m2_time = 0 for job_id in order: a, b = time_map[job_id] m1_time += a m2_time = max(m1_time, m2_time) + b return m2_time使用方式：
jobs = [ ("J5", 2, 5), ("J2", 3, 4), ("J3", 6, 8), ("J1", 5, 2), ("J4", 4, 1), ] seq = johnson_order(jobs) print("最优顺序:", seq) print("makespan:", compute_makespan(seq, jobs))输出：
最优顺序: ['J5', 'J2', 'J3', 'J1', 'J4'] makespan: 22注意compute_makespan里的更新顺序：m2_time用的是上一步的旧值来和m1_time做 max，再累加当前工件在 M2 上的加工时间。很多人写成m2_time = m1_time + b，那只有在 M2 从不清闲时才成立，是错误写法。
3.3 复杂度分析与工程实现细节
排序的复杂度是 O(n log n)，分组扫描是 O(n)，所以整体算法复杂度就是 O(n log n)。这意味着即使工件数量上万，在普通电脑上也是瞬间完成。
工程实现时有几个细节值得注意：
- 当 a_i = b_i 时，放进 A 组和 B 组都不影响最终最优性，但代码里要选一个固定分支，否则会导致结果不稳定。我习惯用
<=归入 A 组。 - 排序时如果 a 相同，A 组内部的先后顺序不影响最优值，可以把 id 作为次要排序键保持输出稳定。
- 数据量很大时，输入输出用批量读写，避免逐条 print，这个在真实排产系统中经常被忽略。
我之前在实际项目里见过一种错误实现：把所有工件按 a 升序排完，再把 b 大的往前移，来回调整，最后得到的不是最优解。其实老老实实按 Johnson 的分组排序逻辑写，反而代码最短、最正确。
4. 常见问题、边界情况与避坑记录
4.1 并列时间怎么处理：a等于b时该去哪一组
很多初学者卡在 a_i = b_i 这种情况。比如一个工件在 M1 和 M2 上都耗时 3，它应该进 A 组还是 B 组？
按 Johnson 法则的形式化版本，a ≤ b 进 A、a > b 进 B。所以 a = b 会进入 A 组。如果把它放 B 组，也照样是最优解，因为临界条件不会改变相邻交换的优劣关系。实现上选一种并保持一致性即可。
不过有一个真正的坑：如果在实现时用了两个独立条件，比如if a <= b: group_A.append(...)和if a > b: group_B.append(...)，没问题；但如果写成if a < b: group_A.append(...)，等于把相等工件漏到了 B 组，虽然不影响最优值，但排序结果不稳定，后面排查问题会相当崩溃。这种小差异在代码 review 阶段很难一眼发现，需要靠单元测试覆盖边界时间。
4.2 计算makespan时的经典失误
算 makespan 的时候，有一个地方特别容易错：第二台机器的开始时间。
正确公式是：
M2 完成 = max(该工件在 M1 上的完成时间, M2 上前一个工件的完成时间) + b
有人会写成：
m2_time = m1_time + b这在第一个工件上是没错的，因为 M2 当时为空，它确实要等 M1。但从第二个工件开始，M2 可能还在处理前面工件，此时必须取两者较大值。还有更隐蔽的错误：使用更新后的m1_time和更新后的m2_time做 max。举个例子，第二个工件在 M1 完成于第 8 分钟，M2 正在处理第一个工件到第 10 分钟结束，那么第二个工件只能在第 10 分钟上 M2，计算上必须用旧 m2_time=10和新 m1_time=8取最大值。代码里的顺序是先更新m1_time，再用旧m2_time计算，很多脚本语言变量的覆盖顺序会导致算错。
4.3 我的排产顺序是对的，但实际产线还是堵了
这是实施阶段最常遇到的问题。Johnson 法则假设机器不故障、切换零耗时、加工时间确定。但实际产线上会有换刀时间、操作员差异、物料到达延迟。所以你在模型里算出来的最优顺序，落到现场不一定是最优。
我给一个建议：把 Johnson 法则作为一个基础排序器，然后在此基础上做有限度的局部调整。比如先把排序结果算出来，再用模拟退火或邻域搜索做二次优化，保证不跑偏太远。这个方法在好多项目里都验证过，它既保留了理论最优的底线，又给了现场调度灵活性。
4.4 两台机器可以算，三台机器怎么办
到三台机器，一般流水作业调度问题已经变得相当复杂，Johnson 法则不能直接套用。固定机器数大于等于 3 的一般情形，在理论上已经被证明是 NP 难级别的。但有一个特殊的三台机器情形可以降维解决，这个我放到下一节专门聊。在此之前，最稳妥的做法是用分支定界或启发式算法，在可接受时间内找近似最优，而不是追求精确解。
5. 从Johnson法则出发的进阶方向
5.1 三台机器的可解特例：虚拟两台机的降维技巧
三台机器的一般问题虽然难，但有一个经典特例可以精确求解。假设三台机器为 M1、M2、M3，工件在三台机器上的时间分别是 a_i、b_i、c_i。如果满足下面的任一条件：
- min a_i ≥ max b_i
- min c_i ≥ max b_i
也就是说，第二台机器的加工时间被完全“夹”在 M1 或 M3 的时间范围内，不会成为瓶颈，那就可以把三台机器合并成两台虚拟机器：
虚拟机器 V1 的时间 = a_i + b_i
虚拟机器 V2 的时间 = b_i + c_i
然后在虚拟两台机上跑 Johnson 法则。背后的道理是：M2 相对于 M1、M3 永远不需要等待，它的时间轴可以完整嵌入整个加工窗口，因此可以当作“过渡机器”看待。
这个技巧在理论上很好用，但场景约束苛刻。我在实际项目里很少遇到完全满足这种夹逼条件的数据，更多时候它用来给问题做一个上界预估，用来评估启发式算法的解离最优有多远。
5.2 大规模与多目标场景下的退路
当机器数超过三台，或者目标不再只是 makespan，还有平均流经时间、延期惩罚、能耗等多目标，Johnson 法则显然不够用。这时候常用的路数有几种：
- 构造式启发：比如 Palmer 斜率指数（按加工时间的加权趋势给工件打分）、关键工件法（先选出权重影响最大的工件作为锚点），这些方法能在毫秒级给出一组不错的基础序列。
- 元启发式优化：把 Johnson 顺序作为初始解，用遗传算法或邻域搜索继续迭代。工件多、机器多时，这类方法的性价比很高。
- 精确算法兜底：小规模或中等规模（比如 n ≤ 15 左右）可以用分支定界、动态规划精确求解，用来验证启发式的误差率。
比较推荐的做法是先把一个小工具链搭起来：读数据、算初始序列、算 makespan、做局部搜索、输出甘特图。Johnson 法则作为其中的排序引擎之一，既能快速出基线，又能为高级算法提供高质量初始解，属于性价比极高的算法组件。
5.3 延展到现实生产调度系统的几点体会
最后分享一下我把这类算法落地到调度系统中的一些经验。第一，数据清洗往往比算法本身更耗时。加工时间数据不准确，再好的排序算法也是空中楼阁。第二，关键约束不要藏得太深。比如“这个工件必须优先交货”“这台机器不能加工这些物料”，这些约束必须在建模阶段显式写进目标函数或约束集，否则算法会给出理论上最优、现场完全不可用的结果。第三，算法的输出要可视化，甘特图一眼能看出 M2 在哪个时段空闲、哪个工件卡住了下一个工件的开工，定位问题的速度远快于看一堆数字。
我自己的使用习惯是：先用 Johnson 法则给出一个明确的下界，再在它周围加保护性缓冲。比如某条产线理论最优是 100 小时，考虑到设备维护和物料波动，会在排产时留出 5% 的缓冲。这不影响算法本身的正确性，反而提高了方案的可执行度。
流水作业调度问题从 Johnson 法则出发，衍生出了非常多的研究方向。无论你是在做生产排产系统、刷算法题，还是在负责一条真实产线，先把两台机器的 Johnson 法则吃透，都会对“最优调度为什么长这样”有很直观的理解。后面的路，无论是扩展机器数、多目标优化，还是引入不确定因素，都会顺畅很多。实际操作中我最大的体会是：调度算法不是为了把每台机器塞满，而是为了把整批工件的“等待时间”压到最低。明白这一点，再回看 Johnson 法则的分组逻辑，会更有启发。
