1. 流水作业调度问题到底在解决什么1.1 从一次生产排产说起有段时间我参与一个模拟工厂车间排产工具的开发任务说起来很简单一批零件要依次经过某条产线上的若干台设备每台设备一次只能处理一个零件希望整个批次尽快做完。工程师们习惯用一个朴素经验来排单——谁的总加工时间短谁先做后来发现完全不是那么回事。两个零件在一台设备上耗时相近时先做哪个对最终完工时间影响不大可一旦跨到第二台设备顺序的影响立刻被放大了。这就是流水作业调度问题Flow Shop Scheduling Problem的典型场景。它指的是一批工件按相同的工艺路线依次流经若干台机器目标是找到一个加工顺序让最后一个工件在最后一台机器上完成的时间即总完工时间makespan尽可能小。这个标题里的「算法」两字通常对应的是解决这一类问题的核心方法在只有两台机器的经典情形下有一个非常漂亮的最优解法也就是Johnson算法。本文就把这个问题的定义、算法原理、代码实现和工程落地中的坑一起讲透。1.2 问题定义与两个容易被忽略的前提先给描述补上严谨的数学骨架。假设有 n 个工件编号为 1 到 n按固定工艺依次经过第 1 台、第 2 台机器。每个工件 i 在第 1 台机器的加工时间为 a_i在第 2 台机器的加工时间为 b_i。任意时刻每台机器最多加工一个工件工件在同一台机器上不能拆开加工且工件一定要等上一台机器加工完才能进入下一台。我们要找一个加工顺序 π使得总完工时间最小。这里有两个前提假设经常被新手忽略。第一所有工件的工艺路线完全一致这符合流水车间Flow Shop的定义如果工件可以走不同路线问题就变成作业车间调度Job Shop复杂度完全不同。第二优化目标是总完工时间也就是从第一个工件开始到最后一个工件下线的总跨度。在真实的APS排产系统里目标函数往往还包含延期成本、在制品库存成本等但在算法学习阶段先抓住makespan是最干净也最容易验证的切入点。要判断一个顺序的好坏光看排序规则是不够的必须能算出任意顺序下的完工时间。两台机器下有一个很直观的递推设第 k 个加工的工件在两台机器上的工序时间为 a 和 b那么第 1 台机器的完成时间就是从 0 开始累加 a第 2 台机器的完成时间则是第 1 台机器完成当前工件的时间和第 2 台机器完成上一个工件的时间这两者中取较大值再加上当前工件的 b。这个递推虽简单却是后续所有验证和仿真计算的地基。2. Johnson算法一个靠直觉几乎猜不到的规则2.1 规则本身只有两句话Johnson算法想解决的就是前面说的两台机器、n个工件、最小化总完工时间的问题。它发表于上世纪五十年代几十年过去仍然是这个经典问题的最优解算法。整个规则说起来很短只有两步把工件分成两组凡是 a_i 小于等于 b_i 的工件放进 S1 组凡是 a_i 大于 b_i 的工件放进 S2 组。最终顺序是S1 组的工件按第 1 台机器加工时间 a_i 从小到大排列接上 S2 组的工件按第 2 台机器加工时间 b_i 从大到小排列。也就是说先做第 1 台机器用时短于第 2 台机器的工件且它们内部按照第 1 台机器的时间升序做再做第 1 台机器用时长于第 2 台机器的工件且内部按照第 2 台机器的时间降序做。这个顺序初看会觉得很奇怪为什么不是按总加工时间排为什么两组规则还不一样我第一次接触时也有同样的疑问直到亲手做了几十组随机数据对比才意识到任何看起来更合理的贪心排序都会在某些数据上输掉。2.2 为什么这个规则是对的相邻交换论证Johnson算法正确性的核心靠的是相邻交换论证。思路大概是这样的考虑任意两个相邻的工件 u 和 v假设它们之前的某个时刻两台机器都已经空闲。如果先做 u 再做 v总完工时间与先做 v 再做 u 之间的差异可以通过一个不等式来判断。推导到最后会得到一个非常简洁的结论当 min(a_u, b_v) ≤ min(a_v, b_u) 时u 排在 v 前面不会让总完工时间变大。这个条件的意思是u 在第 1 台机器上的耗时与 v 在第 2 台机器上的耗时这两者的较小值不超过 v 在第 1 台机器上的耗时与 u 在第 2 台机器上的耗时的较小值那么 u 在前更优或至少不差。关键在于这个相邻交换条件具有传递性可以把全体工件排成一个满足条件的全序。Johnson算法正是用一种巧妙方式来构造这个全序——先把 a_i 与 b_i 比大小分成两组组内各按单一关键字排序。因为任意两个 S1 内的工件按 a 升序排列时都能满足交换条件任意两个 S2 内的工件按 b 降序排列时也都满足交换条件而所有 S1 排在 S2 前面时边界处的工件同样满足交换条件。所以只要把「第 1 台机器a更小」的优先并且把「第 2 台机器b更大」的优先为防止工件卡在第 2 台机器上整个顺序就是全局最优的。2.3 直观理解谁先做取决于让谁先闲着抛开代数推导Johnson算法背后有很朴素的直觉。两条机器像两个水池第 1 台机器加工完一个工件就能把接力棒传给第 2 台机器。如果第 1 台机器上有个很快的小工件它做完后让第 2 台机器尽快开工是有利的反过来如果某个工件在第 2 台机器上非常耗时它压在第 2 台机器上会拖累后面所有工件所以这类工件应当靠前放避免它成为收尾的长尾巴。这也是为什么 S2 组要按 b 降序排第 2 台机器上的大块头越早开工越好最后留下那些 b 较小的工件来收尾这样第 2 台机器接近结束时能快速清空。我用大白话来记这个规则第 1 台机器快的先做第 2 台机器慢的先做。两个条件看起来矛盾但正好对应两组工件各自的排序方式。3. 把规则变成可以跑的代码3.1 核心排序实现先给一个最简的 Python 实现输入是每个工件在两台机器上的加工时间列表输出是加工顺序。def johnson_order(times): # times [(a_i, b_i), ...] s1 [] # a_i b_i s2 [] # a_i b_i for idx, (a, b) in enumerate(times): if a b: s1.append((a, b, idx)) else: s2.append((a, b, idx)) s1.sort(keylambda x: x[0]) # 按 a 升序 s2.sort(keylambda x: x[1], reverseTrue) # 按 b 降序 order [item[2] for item in s1 s2] return order这里的实现细节值得说两句。第一分组条件是 a_i b_i等号归入哪组都行但必须保证分组后组内的排序方向正确。第二S1 和 S2 分开排序之后再拼接不要试图在同一个数组上用自定义比较器实现完整的 Johnson 排序虽然 Python 的functools.cmp_to_key可以写复合比较器但没有必要——分组写法不容易出错也更容易向同事解释。第三下标要保留下来因为实际系统里还需要根据工件 ID 回查工艺信息。3.2 完工时间计算要写对算出顺序只是第一步。要验证这个顺序的 makespan需要模拟两台机器的执行过程。下面这个函数是两台机器递推的完整实现它同时也是验证任何启发式算法效果的工具。def compute_makespan(order, times): t_m1 0 t_m2 0 for idx in order: a, b times[idx] t_m1 a # 第二台机器必须等当前工件在第一台完成后才能开始 # 也要等上一个工件在第二台完成。 t_m2 max(t_m1, t_m2) b return t_m2这段代码虽然只有几行但边界条件全在max(t_m1, t_m2)这一步里。t_m1 是当前工件在第 1 台机器的完成时刻t_m2 是第 2 台机器上一轮结束时能开工的最早时刻。两者取最大才得到当前工件真正开始第 2 台机器加工的时间。很多初学的人在写这个递推时会把t_m2 t_m1 b这在某些顺序下恰好碰对了某些顺序下就会偏小导致验证结果失真。记住一个原则流水线调度的完工时间永远是一台机器累加工时与另一台机器累加工时之间的最大-递推关系。3.3 手算验证一个五工件实例理论讲完用一个手算例子演示完整过程。设五个工件在两台机器上的加工时间如下表工件编号第 1 台机器 a第 2 台机器 b154226382435543先用 Johnson 规则分组。a b 的工件有工件 22 ≤ 6、工件 43 ≤ 5它们进入 S1按 a 升序排为 [2, 4]。a b 的工件有工件 1、工件 3、工件 5进入 S2按 b 降序排列。S2 中 b 分别为 4、2、3降序为 [1, 5, 3]。最终顺序为 [2, 4, 1, 5, 3]。接下来用递推计算完工时间。第 1 台机器的完成时刻依次为工件 2 在 2工件 4 在 235工件 1 在 5510工件 5 在 10414工件 3 在 14822。第 2 台机器上工件 2 等第 1 台到 2加工 6完成于 8工件 4 等 max(5, 8)8加工 5完成于 13工件 1 等 max(10, 13)13加工 4完成于 17工件 5 等 max(14, 17)17加工 3完成于 20工件 3 等 max(22, 20)22加工 2完成于 24。所以该顺序的总完工时间为 24。如果只是排完序不算时间就体会不到这个算法的价值。我当时专门写了枚举全排列的程序验证这个例子五工件的全排列共有 120 种最优 makespan 恰好就是 24而按总加工时间降序、升序等常见贪心策略分别得到 25 和 27。这个简单的对照实验比任何证明都更能说服团队里的怀疑派。4. 当机器超过两台精确算法的边界与启发式救场4.1 三台机器的经典结论生产环境中很少只有两台机器更多是五台、八台甚至更多。Johnson 算法能不能直接推广到三台机器答案是一般情况下不能。三台机器最小化 makespan 的流水作业调度问题已经被证明是 NP 难问题不存在多项式时间的最优算法。不过有一个经典的特殊情形可以用归约法处理如果第 1 台机器的最小加工时间不小于第 2 台机器的最大加工时间或者第 3 台机器的最小加工时间不小于第 2 台机器的最大加工时间那么第 2 台机器永远不会成为瓶颈制约。此时可以把第 1 台与第 2 台合并成虚拟机器 A加工时间是两者之和把第 2 台与第 3 台合并成虚拟机器 B再对这两个虚拟时间用 Johnson 算法。这个特殊情形听起来很美但坦白讲真实车间里极少满足这样的加工时间条件。更多时候我们会直接放弃精确算法转向分支定界等精确求解方法处理小规模问题或者在规模稍大时用启发式算法找近似解。这里要明确一个工程判断n 小于等于 10 左右时可以直接用分支定界或动态规划求最优解n 达到几十上百就必须上启发式算法了。4.2 NEH启发式工程里性价比最高的方案多机环境下最经典的启发式算法之一是 NEH 算法。它的思想分两步先用一个初始规则给工件排序然后逐个取出工件插入到当前序列中最优的位置。具体步骤如下计算每个工件在所有机器上的总加工时间按总加工时间从大到小得到一个初始序列。取出初始序列中的第一个工件作为当前部分序列。依次取出下一个工件尝试把它插入当前部分序列的所有可能位置从开头到结尾并计算每个位置对应的部分 makespan选使 makespan 最小的位置插入。重复第 3 步直到所有工件插入完毕。NEH 算法的复杂度大约为 O(m·n^3)不过实际跑起来在数千工件的规模下也很快。这个算法在大量文献和工业实践中都被验证为多机流水调度里效果最好的构造启发式之一很多元启发式算法比如遗传算法、模拟退火也都用 NEH 的结果作为初始种群的一部分。我在某个模拟项目的对比实验里测过NEH 的解通常比按总加工时间直接排序的解好 5% 到 15%而且实现起来不过几十行代码。4.3 其他常用手段Palmer斜率法与CDS除了 NEH还有两个更老的构造启发式值得一提。Palmer 方法定义一个斜率指标对每个工件按机器编号计算加权和与反向加权和的差值然后按这个指标降序排列。CDS 方法则是把多台机器拆分成多组两台机器的子问题对每个子问题分别用 Johnson 算法求解得到若干候选序列最后从中挑 makespan 最小的那个。这两个方法实现简单、运行快适合作为快速下界估算但解的质量通常不如 NEH。如果追求更强的解质量下一步是用邻域搜索对 NEH 结果做改进比如常见的插入邻域和交换邻域不断尝试把一个工件移到另一个位置或者交换两个工件的位置保留更优的解直到无法改进。这本质上就是局部搜索框架10 行到 20 行代码就能写出来对中型规模的调度能再优化 3% 到 8%。5. 真正落地时容易被忽略的坑5.1 makespan最优不等于整个订单系统最优很多排产系统上线后最大的争议不是算法算得不够快而是算出来的最优顺序不符合业务直觉。为什么因为业务方真正关心的指标往往不止 makespan还有订单交付期。举个例子某个工件 a 很小但交期紧急另一个工件 b 很大但不急Johnson 算法为了最小化总完工时间可能把交期急的小工件排到后面业务方立刻就不满意了。处理办法通常是在目标函数里加入惩罚项把顺序调度变成带权目标最大化或最小化。比如目标改成最小化总完工时间 各工件延期惩罚或者把工件按交期紧迫度加权后再做排序。还有一招是老实战派常用的先用 Johnson/NEH 算出候选顺序再人工微调前几个位置观察 makespan 损失是否可接受。工程上损失 2% 的全局效率换取关键订单准时交付往往是比追求数学最优更划算的决策。5.2 数据规模、代码实现和验证细节另一个踩坑点是数据结构和复杂度假设。Johnson 算法本身 O(n log n)非常快但一旦加入局部搜索尤其在 n 达到数千时反复调用 makespan 计算函数会成为性能瓶颈。优化思路无非两种一是增量计算 makespan插入或交换时不必重新计算整个序列二是用预计的上下界剪掉不可能更好的候选位置。我在实践中更倾向于后者因为增量计算在多机情形下的 bug 率非常高为了一点性能引入正确性风险并不划算。验证也是一门功课。拿不到真实生产数据时我会生成多组随机问题实例每组固定一个随机种子把算法结果跟暴力枚举n 较小或商业求解器的结果比较。这个流程能发现大多数隐藏 bug尤其是分组条件、边界相等和下标错位这类问题。建议每位读者优化完调度算法后都花半小时跑一遍随机数据对照测试而不是只在某个拍脑袋想出来的用例上验证。5.3 我的取舍体会做流水作业调度相关项目做到后面最大的体会是Johnson 算法本身只解决两台机器的精确最优但它的价值远超这一个小小的应用场景。它教会我们的是一种分析思维方式——先想清楚交换两个相邻工件会让目标变差还是变好把复杂的问题分解成局部条件来推理再用排序构造满足全序的整体方案。这种思维在后面做 NEH、做局部搜索、甚至设计交货期相关目标函数时都能复用。如果只让我留给读者一句话那就是不要迷信任何单一排序规则一切以 makespan 计算函数为准。任何调度顺序都先写出正确的仿真计算函数再用对照组实验验证最后才谈业务规则。这是我在多次排产项目里踩过坑之后总结出来的最实在的一条经验。正文完最后以自己的实操体会收尾