1. 车间里最容易被低估的决定工序排序1.1 两个工件谁先做差的不只是半天做生产计划这些年我最怕听到的一句话不是“交期又延误了”而是“你按老经验随便排一排就行”。工序排序这件事看着只是把几个加工对象前后排个队实际上直接决定了整个车间的产出周期、在制品积压和设备利用率。之前待过的一个机加工车间两条线共用同一组清洗和热处理设备计划员图省事一直按“先下单先排产”的规则安排批次。结果热处理炉前经常排队排到半夜而后道清洗机却是干一会儿停一会儿整个月底交付时间被拖长了两三天。后来把排序逻辑换了同样的订单、同样的工时定额总完工时间硬是压缩了明显一截。这个现象背后的数学工具就是约翰逊法。生产管理领域的读者应该都听过这个名字但很多人对它的理解停留在“有一种排序算法叫Johnson”的层面真要上手算一个具体案例反而不知道从哪一步开始。这篇文章我会从一个小车间的真实场景出发把约翰逊法的适用条件、手算过程、最优性原理、实际落地时容易踩的坑以及如何向三台以上设备推广一层一层拆开讲。1.2 都是“排序”为什么说这个问题有最优解先明确我们到底在排什么。车间里常见的排序问题有几种单台设备上多个作业的排序多台设备上的流水线排序还有多品种混合生产的车间调度。约翰逊法解决的是其中非常特殊、但应用频率极高的一类多个工件按同一个先后顺序依次经过两台设备工序加工每台设备每次只能加工一个工件要求确定一个最优排序让最后一台设备完成所有加工任务的时刻最早。这个“最早”在学术上叫最小化最大完工时间makespan。车间里所有订单全部完成的时间越早交付周期越短设备和人力占用越少资金周转也越快。所以最小化makespan几乎是生产调度最核心的目标之一。有意思的是这个看似简单的问题在数学家眼里并不简单只要设备数变成三台求解难度就会急剧上升属于典型的NP难问题但当设备数限定为两台时1954年约翰逊给出了一套精巧的构造性算法能在多项式时间内找到精确最优解。在离散优化领域这种“少数几个能干净利落求出最优解”的问题非常稀缺。这也是为什么约翰逊法至今仍是各大APS高级计划排产系统软件的基础组件之一。2. 约翰逊法的操作流程从规则到最优排序2.1 先判断你的问题适不适用任何算法都有边界约翰逊法也不例外。开讲之前先对着实际问题做四步检查是不是两个工序/两台设备第二道工序必须紧跟在第一道工序之后且所有工件顺序完全一致。加工时间是否确定且已知是否不随排序变化。一台设备同一时刻是否只能处理一个工件工件是否不能拆批。是否追求最大完工时间最小而不是最小化总延期或平均流经时间。实际生产里第二道工序往往是“清洗”“检验”“热处理”这类辅助工序第一道是机加工或成型工序。只要工件在这两条线上都按同样的方向流动就符合约翰逊法的应用前提。反过来如果车间里有并行设备、有工件可以跳工序加工或者有设备间的转运等待无法忽略那就要谨慎了后面第五章我会专门讲怎么处理这些偏差。2.2 算法核心时间短的去两端时间长的放中间约翰逊法的规则可以浓缩成一句话在所有尚未排序的工件里找出加工时间最小的那个如果这个最小时间落在第一台设备上就把它放到序列的最前面如果落在第二台设备上就把它放到序列的最后面然后把这个工件从候选清单里拿掉重复以上步骤直到所有工件都排完。这里有个小细节必须强调比较的是“全部剩余工件的两列时间”里的全局最小值而不是只看第一台设备或只看第二台设备。很多初学者把规则记成了“第一台时间短的放前面第二台时间长的放前面”结果排序结果和最优解差了十万八千里。约翰逊法的关键思维方式是“两边夹”序列是从前端和后端同时往中间生长的每次把最短时间的工件填充到两端之一。为了让大家看清完整迭代过程我设计一个五工件的案例数据如表所示工件编号第一道工序时间小时第二道工序时间小时J152J219J386J437J543下面开始手算。先把最终序列看成两个空列表前端序列和后端序列。第一轮把所有工件的十个时间扫一遍全局最小值是工件J2第一道工序的1小时。由于它落在第一台设备把J2放到前端序列前端[J2]后端[]。第二轮剩余J1、J3、J4、J5全局最小值是J1第二道工序的2小时。落在第二台设备放到后端序列前端[J2]后端[J1]。第三轮剩余J3、J4、J5全局最小值是J5第二道工序的3小时。落在第二台设备放到后端前端[J2]后端[J5, J1]。第四轮剩余J3、J4注意J4第一道工序3小时J5已被排除所以全局最小是J4第一道工序的3小时。落在第一台设备放到前端前端[J2, J4]后端[J5, J1]。第五轮只剩J3直接填入中间空位最终序列为J2、J4、J3、J5、J1。2.3 平局情况怎么处理制造现场经常出现加工时间相等的情况比如两个工件第二道工序都是3小时那该选谁约翰逊法在这里并不会影响最终的总完工时间。学术上有一条结论当存在多个相同最小值时任意选择都不会改变最大完工时间的最优性最多只是得到一个不同的等价最优解。实操中我的建议是设置一个辅助规则比如优先选工件号小的或者优先选交期更紧的让系统行为可复现后面追踪起来也方便。这里还要补充一个容易误解的点平局时选择的“先后”不会改变完工时间但这只针对两台设备的置换流水车间问题。一旦条件改变比如引入设备准备时间、工件在不同设备上的顺序不一致平局选择就会影响结果那时候要靠仿真而不是拍脑袋。3. 实例验算最优序列到底比“拍脑袋排序”好多少3.1 用调度公式推算最大完工时间排出了序列怎么算出完工时间这里要引入两道工序完成时间的递推逻辑。设第一道工序为A第二道工序为B。工件在A上的完成时间等于上一件在A上的完成时间加上本件A时间工件在B上的完成时间等于“本件在A上的完成时间”和“上一件在B上的完成时间”两者中的较大值再加上本件B时间。写成口算表更直观。按照约翰逊法得到的序列J2、J4、J3、J5、J1逐件计算加工顺序A工序时间B工序时间A完成时间B完成时间J219110J437417J3861223J5431626J1522128第二道工序每件的完成时间核心是盯住“等谁”两个字。J4在A设备上4小时就完成了但它要一直等到10小时才能上B设备因为J2在B设备上要加工到第10小时。J3则在A设备12小时完成此时B设备还在加工J4要等到17小时才能开始。这就是两台设备负荷天然不同步带来的等待。最终最大完工时间为28小时。再看自然顺序J1、J2、J3、J4、J5的完工时间A设备完成时间分别是5、6、14、17、21B设备上J1从5做到7J2从7做到16J3从16做到22J4从22做到29J5从29做到32最大完工时间是32小时。四种典型排序策略对比如下排序策略得到的顺序最大完工时间小时约翰逊法J2-J4-J3-J5-J128先到先排自然顺序J1-J2-J3-J4-J532按首道工序时间升序J2-J4-J5-J1-J328按次道工序时间升序J1-J5-J3-J4-J239同一个车间、同样的零件、同样的工时定额仅仅因为排序不一样最后完工时间能差出11个小时。按B工序时间升序排列的结果最差因为把所有“需要B设备照顾的工件”都放在前面结果A设备的优势没有利用起来B设备反而在最后几件上断断续续等料。这个对比很有代表性计划员凭感觉选了一个看似合理的规则实际效果可能恰恰是最差的之一。3.2 设备空闲时间算清这一笔比硬记公式有用如果只记递推公式换一批数据还是容易算错。我提供一个更直觉的视角B设备的总工作负荷是固定的等于所有工件的B工序时间总和本案例是27小时。最大完工时间等于B设备总负荷加上B设备的总空闲时间。所以最小化最大完工时间本质上就是在最小化B设备的空闲时间。用这个视角重新看最优序列B设备在0到1小时无活可干这是第一件工件在A设备上加工导致的初始空闲之后从第1小时到第28小时B设备几乎满负荷运转中间没有出现设备等待工件的情况。总空闲时间只有1小时正好对应28等于27加1。我后来在现场做排产培训时总爱让计划员先把“B设备总负荷”和“B设备总空闲”两个数算出来再回过头看约翰逊法的序列。一旦你建立了“压空闲就是压完工时间”的思维方式很多排序直觉会自动纠偏。例如你会开始主动把A工序时间短、B工序时间长的工件往前面放因为这样可以快速“喂饱”B设备把A工序时间长、B工序时间短的工件往后放因为它们在A设备上的长时间加工正好可以用来缓冲B设备的排队。3.3 换一台设备视角约翰逊法的拣选逻辑用“压空闲”视角重新理解算法规则会变得很好记。全局最小值如果出现在A工序就说明这个工件在A上特别快理应尽快把它送到B设备那里全局最小值如果出现在B工序就说明这个工件在B上特别短放在哪个位置都不会对B设备产生太大压力那就不如放到最后把B设备的黄金时间让给那些B工序时间长的工件。J5和J1在B工序时间分别只有3小时和2小时所以它们被约翰逊法安排到序列后半段。J2的A工序只有1小时但B工序要9小时是典型的“前快后慢”必须第一个上。这套逻辑绕开了复杂公式车间班组长也能听懂实用性很高。4. 为什么约翰逊法能做到最优从相邻交换看穿本质4.1 两台机器的结构特征与关键不等式很多人用约翰逊法时心里犯嘀咕就凭这么简单的排序规则真的能保证全局最优吗我刚开始也有这个疑问直到看懂了相邻交换论证才算彻底放心。考虑任意一个序列假设其中有两个相邻工件X和YX排在Y前面。此时盯着这两个工件看它们对B设备空闲时间的影响。把X和Y从整个序列中单独提出来假设它们都到达时B设备刚好空闲那么XY的顺序会让B设备完成这两个工件所需的时间是一个表达式如果交换成YX同样能得到一个表达式。两者比较之后会发现只要满足min(X的A时间, Y的B时间)小于等于min(Y的A时间, X的B时间)那么X在前、Y在后的顺序不会比交换后的顺序差。这个不等式就是约翰逊法的本质。它定义了一种全序关系任意两个工件之间谁排在前面应该严格按照这个不等式来判定。约翰逊法的两列最小扫描本质上是在构建一个满足上述相邻条件的完整序列。因为任意相邻工件都满足“不会因为交换而变差”通过一步步相邻交换可以得到全局最优解。这一步推导在运筹学教材里通常只有两三页但它比背下算法步骤重要得多。4.2 为什么三台设备会突然变难理解了相邻交换也就理解了约翰逊法为什么无法简单照搬到三台设备。两台设备时“B设备空闲最小化”这个目标可以转化为明确的优先级判定三台设备时中间设备既是前道工序的“后道”又是后道工序的“前道”两台设备之间的简单比较关系会被打断需要同时考虑三台设备的联动。所以三机问题没有类似的简单排序规则这从数学上决定了它的求解难度。这并不是说三机问题完全没希望。后面第六章我会介绍一种典型的化简思路和启发式方法它们都是基于约翰逊法思想的延伸。4.3 最优性的一个常见误区还需要澄清一个问题约翰逊法保证的是“最大完工时间最小”不代表它同时优化了设备利用率、延期天数、在制品库存等所有指标。比如某种排序让最大完工时间最短但某个交期特别紧的工件反而被排到了后面可能导致该订单延期。实际生产中如果延期惩罚非常严重往往要在这个序列基础上做局部调整或者干脆换用其他目标函数和算法。理解每个优化目标对应什么算法比盲目套用某个“最优算法”更重要。5. 现场落地时容易踩的坑与处置经验5.1 加工时间的数据口径必须统一约翰逊法看起来只需要一张“工件×设备时间”表但生产现场这组数字的统计口径五花八门。最常见的坑是A工序时间按单件工时填写B工序时间按整批工时填写批次又不一样算法出来就是完全错误的排序。以机械加工为例首件准备时间、刀具调整时间、批量加工时间和单件加工时间到底哪一部分进了哪个字段必须提前定死。我的建议是直接用“每批次的整批占用设备时间”也就是从设备开始加工该批次到加工结束的全部时间中间不扣除等待和人员休息。原因很简单约翰逊法调度的是“设备占用顺序”不是“工人操作顺序”时间必须反映设备实际被占用的横截面。如果车间已经上了MES直接从系统取数会更可靠如果靠人工填表至少要保证同一个计划员统一口径。5.2 换型时间与排序相关时的边界标准约翰逊法假设工件的加工时间固定不变。实际注塑、冲压、印刷车间里换模换线时间往往与前后两个工件的组合有关从产品A切换到产品B需要1小时从产品B切换到产品C需要半小时这就破坏了加工时间固定的前提。如果换型时间占比很小不到总工时的5%可以粗略把平均换型时间并入加工时间约翰逊法仍然够用。如果换型时间占比高问题就变成了带顺序相关准备时间的调度问题和旅行商问题同构单纯约翰逊法不再适用。我在一个注塑厂见过类似的项目最后是用遗传算法加规则种子求解把约翰逊法结果作为初始种群的一员既提高了搜索效率也跨过了这个坑。5.3 批次能不能拆一个需要考虑的现实因素标准问题里假设一个工件是一个不可拆分的整体第二道工序必须等这个工件整体完成才能开工。实际生产中如果批量较大可以考虑拆分成更小的传送批次第一台设备加工完一部分先送到第二台设备开始加工不必等整批完成。这种“平行移动”能进一步缩短完工时间。要不要拆批本质上是个权衡拆批可以缩短生产周期但增加了搬运次数、交接记录和现场管理复杂度。如果你们现有信息系统不支持按子批次跟踪报工建议先不拆直接按整批优化顺序。等流程稳定了再评估引入平行移动能带来的收益。约翰逊法本身不处理拆批问题但它的最优顺序可以作为拆批后调度方案的基线用来对比收益。5.4 并行机与多工序车间的降维处理很多车间表面上有多台设备实际并非真正并行。比如有两台一样的数控铣床但分别承担不同型号零件的第一道工序这时可以拆成两条独立的流水线分别排序如果确实有一台设备能加工所有第一道工序第二道工序也有多台可选那就变成了“两台设备但有多个平行机”的问题约翰逊法的适用性就打了折扣。这种情况下我通常建议先用约翰逊法做一次“粗排”把它当成一个优秀的上限参照再用仿真软件或APS系统生成可行排程把约翰逊法结果作为初始解或者下界参考。至少在我经历过的项目里这样做比直接上一套复杂算法稳定得多。5.5 用Excel也能落地给计划员的小工具不是所有工厂都上了APS但几乎所有计划员手里都有Excel。约翰逊法完全可以用Excel实现。先把所有工件按A工序时间升序和B工序时间升序排列然后用INDEX和MATCH配合条件格式逐轮挑选全局最小时间或者用VBA写一个循环按算法规则自动生成排序结果。对于中小规模订单这种简单工具已经能解决80%的问题。更简单的做法是借助Excel的LAMBDA函数或SORTBY函数构建动态排序表。如果对VBA不熟悉就用第五章说的方法先把数据手工按规则跑一遍加深理解再尝试自动化。不要一开始就追求全自动先把排序逻辑吃透自动化只是顺手的事。5.6 一个值得养成的复盘习惯每次用新排序跑完一轮生产建议把实际完工时间和理论计算值做一次对比。如果差异超过10%先别急着怪算法大概率是数据口径出了问题或者现场有等待、返工等非计划因素。把偏差原因找出来并修正数据比反复调整排序算法重要得多。我在车间里推行这套方法时前两周的偏差都在15%以上后来发现是MES里工时漏掉了首检时间修正后偏差降到3%以内。6. 向前一步约翰逊法向三台及以上设备的推广思路6.1 三台可化简的经典条件约翰逊法最自然的推广是三台设备、每个工件都按顺序经过A、B、C三道工序的情况。如果中间设备B的加工时间有一个特殊规律——所有工件在B上的加工时间都不大于它们在A上的最小时间或者都不大于它们在C上的最小时间——三机问题就能化简成二机问题。具体做法是构造两台“虚拟设备”第一台虚拟设备的时间为A工序加B工序时间第二台虚拟设备的时间为B工序加C工序时间然后套用标准约翰逊法排序。这个化简条件在学术上被称为Johnson三机扩展条件。现实中这个条件比较苛刻很少能恰好满足但它提供了一个重要直觉中间工序负荷特别轻的流水线本质上可以等价成两工序系统来排序。6.2 CDS启发式工程上真正常用的推广实际生产中更多见的是四台、五台甚至更多设备的流水线这时候CDS算法Campbell-Dudek-Smith是经典方案。它把多机问题拆成若干个两机子问题第一次只考虑第一台和最后一台设备第二次考虑前两台设备和后两台设备第三次考虑前三台设备和后三台设备以此类推。每一组都套用约翰逊法得到一个候选序列最后把若干个候选序列分别仿真或计算完工时间挑最好的那个作为最终排序。CDS的逻辑是把约翰逊法做成一个“候选序列生成器”覆盖不同瓶颈位置再从中选出最优解。它的计算量小工程实现容易而且效果通常很不错在学术界和工业界应用都很广泛。很多APS软件的排序引擎里CDS就是启动阶段生成初始解的工具之一。6.3 当问题规模变大时约翰逊法扮演什么角色规模再往上走比如几十台设备、几百个订单还附带模具寿命、人员班次、物料齐套等约束就需要上元启发式算法或数学规划求解器了。但即便在这种大型系统里约翰逊法仍然有它的位置一是作为初始可行解让求解器或搜索算法从一个高质量起点出发二是作为下界估计帮助判断启发式解离最优解还有多远三是作为可解释性工具输出一组“为什么这么排”的规则调度员更容易接受。我在推进APS项目的过程中最深的体会是算法再高级最后落地都要靠计划员认可。约翰逊法最大的价值不只是它能算出最优解而是它足够简单、足够透明能让现场的人一眼看懂排序逻辑从而愿意使用它。很多复杂的算法黑箱最后被弃用反而栽在“计划员不信任”上。6.4 从一个两机问题到一套现场调度方法论如果你现在面对的是一个刚开始重视排产的小车间不要一上来就上重武器。先用约翰逊法把两台核心瓶颈设备的排序做起来让计划员看到28小时和32小时之间的差距让班组长理解压空闲时间就是压交付周期。这个习惯建立起来后再逐步引入拆批、换型优化、并行机调度等进阶手段。调度问题的解法从来不是越复杂越好而是越贴现场、越能落地越好。约翰逊法作为运筹学进入生产管理领域最早的成果之一至今没被淘汰恰恰说明它抓住了制造业最本质的两点所有工件共用瓶颈设备所有订单都希望尽快完工。只要这两点存在约翰逊法的思路就有用武之地。我个人在实际项目中还有一个屡试不爽的技巧把约翰逊法算出的序列当作“照妖镜”凡是不符合这个排序方向的现场逻辑都值得追问一句“凭什么”。有些时候你能发现隐藏的约束有些时候你会发现现场只是习惯了旧的错误做法。把这些问题梳理清楚比单纯换一套算法更有价值。
约翰逊法生产调度详解：两设备工序排序如何实现完工时间最短？
1. 车间里最容易被低估的决定工序排序1.1 两个工件谁先做差的不只是半天做生产计划这些年我最怕听到的一句话不是“交期又延误了”而是“你按老经验随便排一排就行”。工序排序这件事看着只是把几个加工对象前后排个队实际上直接决定了整个车间的产出周期、在制品积压和设备利用率。之前待过的一个机加工车间两条线共用同一组清洗和热处理设备计划员图省事一直按“先下单先排产”的规则安排批次。结果热处理炉前经常排队排到半夜而后道清洗机却是干一会儿停一会儿整个月底交付时间被拖长了两三天。后来把排序逻辑换了同样的订单、同样的工时定额总完工时间硬是压缩了明显一截。这个现象背后的数学工具就是约翰逊法。生产管理领域的读者应该都听过这个名字但很多人对它的理解停留在“有一种排序算法叫Johnson”的层面真要上手算一个具体案例反而不知道从哪一步开始。这篇文章我会从一个小车间的真实场景出发把约翰逊法的适用条件、手算过程、最优性原理、实际落地时容易踩的坑以及如何向三台以上设备推广一层一层拆开讲。1.2 都是“排序”为什么说这个问题有最优解先明确我们到底在排什么。车间里常见的排序问题有几种单台设备上多个作业的排序多台设备上的流水线排序还有多品种混合生产的车间调度。约翰逊法解决的是其中非常特殊、但应用频率极高的一类多个工件按同一个先后顺序依次经过两台设备工序加工每台设备每次只能加工一个工件要求确定一个最优排序让最后一台设备完成所有加工任务的时刻最早。这个“最早”在学术上叫最小化最大完工时间makespan。车间里所有订单全部完成的时间越早交付周期越短设备和人力占用越少资金周转也越快。所以最小化makespan几乎是生产调度最核心的目标之一。有意思的是这个看似简单的问题在数学家眼里并不简单只要设备数变成三台求解难度就会急剧上升属于典型的NP难问题但当设备数限定为两台时1954年约翰逊给出了一套精巧的构造性算法能在多项式时间内找到精确最优解。在离散优化领域这种“少数几个能干净利落求出最优解”的问题非常稀缺。这也是为什么约翰逊法至今仍是各大APS高级计划排产系统软件的基础组件之一。2. 约翰逊法的操作流程从规则到最优排序2.1 先判断你的问题适不适用任何算法都有边界约翰逊法也不例外。开讲之前先对着实际问题做四步检查是不是两个工序/两台设备第二道工序必须紧跟在第一道工序之后且所有工件顺序完全一致。加工时间是否确定且已知是否不随排序变化。一台设备同一时刻是否只能处理一个工件工件是否不能拆批。是否追求最大完工时间最小而不是最小化总延期或平均流经时间。实际生产里第二道工序往往是“清洗”“检验”“热处理”这类辅助工序第一道是机加工或成型工序。只要工件在这两条线上都按同样的方向流动就符合约翰逊法的应用前提。反过来如果车间里有并行设备、有工件可以跳工序加工或者有设备间的转运等待无法忽略那就要谨慎了后面第五章我会专门讲怎么处理这些偏差。2.2 算法核心时间短的去两端时间长的放中间约翰逊法的规则可以浓缩成一句话在所有尚未排序的工件里找出加工时间最小的那个如果这个最小时间落在第一台设备上就把它放到序列的最前面如果落在第二台设备上就把它放到序列的最后面然后把这个工件从候选清单里拿掉重复以上步骤直到所有工件都排完。这里有个小细节必须强调比较的是“全部剩余工件的两列时间”里的全局最小值而不是只看第一台设备或只看第二台设备。很多初学者把规则记成了“第一台时间短的放前面第二台时间长的放前面”结果排序结果和最优解差了十万八千里。约翰逊法的关键思维方式是“两边夹”序列是从前端和后端同时往中间生长的每次把最短时间的工件填充到两端之一。为了让大家看清完整迭代过程我设计一个五工件的案例数据如表所示工件编号第一道工序时间小时第二道工序时间小时J152J219J386J437J543下面开始手算。先把最终序列看成两个空列表前端序列和后端序列。第一轮把所有工件的十个时间扫一遍全局最小值是工件J2第一道工序的1小时。由于它落在第一台设备把J2放到前端序列前端[J2]后端[]。第二轮剩余J1、J3、J4、J5全局最小值是J1第二道工序的2小时。落在第二台设备放到后端序列前端[J2]后端[J1]。第三轮剩余J3、J4、J5全局最小值是J5第二道工序的3小时。落在第二台设备放到后端前端[J2]后端[J5, J1]。第四轮剩余J3、J4注意J4第一道工序3小时J5已被排除所以全局最小是J4第一道工序的3小时。落在第一台设备放到前端前端[J2, J4]后端[J5, J1]。第五轮只剩J3直接填入中间空位最终序列为J2、J4、J3、J5、J1。2.3 平局情况怎么处理制造现场经常出现加工时间相等的情况比如两个工件第二道工序都是3小时那该选谁约翰逊法在这里并不会影响最终的总完工时间。学术上有一条结论当存在多个相同最小值时任意选择都不会改变最大完工时间的最优性最多只是得到一个不同的等价最优解。实操中我的建议是设置一个辅助规则比如优先选工件号小的或者优先选交期更紧的让系统行为可复现后面追踪起来也方便。这里还要补充一个容易误解的点平局时选择的“先后”不会改变完工时间但这只针对两台设备的置换流水车间问题。一旦条件改变比如引入设备准备时间、工件在不同设备上的顺序不一致平局选择就会影响结果那时候要靠仿真而不是拍脑袋。3. 实例验算最优序列到底比“拍脑袋排序”好多少3.1 用调度公式推算最大完工时间排出了序列怎么算出完工时间这里要引入两道工序完成时间的递推逻辑。设第一道工序为A第二道工序为B。工件在A上的完成时间等于上一件在A上的完成时间加上本件A时间工件在B上的完成时间等于“本件在A上的完成时间”和“上一件在B上的完成时间”两者中的较大值再加上本件B时间。写成口算表更直观。按照约翰逊法得到的序列J2、J4、J3、J5、J1逐件计算加工顺序A工序时间B工序时间A完成时间B完成时间J219110J437417J3861223J5431626J1522128第二道工序每件的完成时间核心是盯住“等谁”两个字。J4在A设备上4小时就完成了但它要一直等到10小时才能上B设备因为J2在B设备上要加工到第10小时。J3则在A设备12小时完成此时B设备还在加工J4要等到17小时才能开始。这就是两台设备负荷天然不同步带来的等待。最终最大完工时间为28小时。再看自然顺序J1、J2、J3、J4、J5的完工时间A设备完成时间分别是5、6、14、17、21B设备上J1从5做到7J2从7做到16J3从16做到22J4从22做到29J5从29做到32最大完工时间是32小时。四种典型排序策略对比如下排序策略得到的顺序最大完工时间小时约翰逊法J2-J4-J3-J5-J128先到先排自然顺序J1-J2-J3-J4-J532按首道工序时间升序J2-J4-J5-J1-J328按次道工序时间升序J1-J5-J3-J4-J239同一个车间、同样的零件、同样的工时定额仅仅因为排序不一样最后完工时间能差出11个小时。按B工序时间升序排列的结果最差因为把所有“需要B设备照顾的工件”都放在前面结果A设备的优势没有利用起来B设备反而在最后几件上断断续续等料。这个对比很有代表性计划员凭感觉选了一个看似合理的规则实际效果可能恰恰是最差的之一。3.2 设备空闲时间算清这一笔比硬记公式有用如果只记递推公式换一批数据还是容易算错。我提供一个更直觉的视角B设备的总工作负荷是固定的等于所有工件的B工序时间总和本案例是27小时。最大完工时间等于B设备总负荷加上B设备的总空闲时间。所以最小化最大完工时间本质上就是在最小化B设备的空闲时间。用这个视角重新看最优序列B设备在0到1小时无活可干这是第一件工件在A设备上加工导致的初始空闲之后从第1小时到第28小时B设备几乎满负荷运转中间没有出现设备等待工件的情况。总空闲时间只有1小时正好对应28等于27加1。我后来在现场做排产培训时总爱让计划员先把“B设备总负荷”和“B设备总空闲”两个数算出来再回过头看约翰逊法的序列。一旦你建立了“压空闲就是压完工时间”的思维方式很多排序直觉会自动纠偏。例如你会开始主动把A工序时间短、B工序时间长的工件往前面放因为这样可以快速“喂饱”B设备把A工序时间长、B工序时间短的工件往后放因为它们在A设备上的长时间加工正好可以用来缓冲B设备的排队。3.3 换一台设备视角约翰逊法的拣选逻辑用“压空闲”视角重新理解算法规则会变得很好记。全局最小值如果出现在A工序就说明这个工件在A上特别快理应尽快把它送到B设备那里全局最小值如果出现在B工序就说明这个工件在B上特别短放在哪个位置都不会对B设备产生太大压力那就不如放到最后把B设备的黄金时间让给那些B工序时间长的工件。J5和J1在B工序时间分别只有3小时和2小时所以它们被约翰逊法安排到序列后半段。J2的A工序只有1小时但B工序要9小时是典型的“前快后慢”必须第一个上。这套逻辑绕开了复杂公式车间班组长也能听懂实用性很高。4. 为什么约翰逊法能做到最优从相邻交换看穿本质4.1 两台机器的结构特征与关键不等式很多人用约翰逊法时心里犯嘀咕就凭这么简单的排序规则真的能保证全局最优吗我刚开始也有这个疑问直到看懂了相邻交换论证才算彻底放心。考虑任意一个序列假设其中有两个相邻工件X和YX排在Y前面。此时盯着这两个工件看它们对B设备空闲时间的影响。把X和Y从整个序列中单独提出来假设它们都到达时B设备刚好空闲那么XY的顺序会让B设备完成这两个工件所需的时间是一个表达式如果交换成YX同样能得到一个表达式。两者比较之后会发现只要满足min(X的A时间, Y的B时间)小于等于min(Y的A时间, X的B时间)那么X在前、Y在后的顺序不会比交换后的顺序差。这个不等式就是约翰逊法的本质。它定义了一种全序关系任意两个工件之间谁排在前面应该严格按照这个不等式来判定。约翰逊法的两列最小扫描本质上是在构建一个满足上述相邻条件的完整序列。因为任意相邻工件都满足“不会因为交换而变差”通过一步步相邻交换可以得到全局最优解。这一步推导在运筹学教材里通常只有两三页但它比背下算法步骤重要得多。4.2 为什么三台设备会突然变难理解了相邻交换也就理解了约翰逊法为什么无法简单照搬到三台设备。两台设备时“B设备空闲最小化”这个目标可以转化为明确的优先级判定三台设备时中间设备既是前道工序的“后道”又是后道工序的“前道”两台设备之间的简单比较关系会被打断需要同时考虑三台设备的联动。所以三机问题没有类似的简单排序规则这从数学上决定了它的求解难度。这并不是说三机问题完全没希望。后面第六章我会介绍一种典型的化简思路和启发式方法它们都是基于约翰逊法思想的延伸。4.3 最优性的一个常见误区还需要澄清一个问题约翰逊法保证的是“最大完工时间最小”不代表它同时优化了设备利用率、延期天数、在制品库存等所有指标。比如某种排序让最大完工时间最短但某个交期特别紧的工件反而被排到了后面可能导致该订单延期。实际生产中如果延期惩罚非常严重往往要在这个序列基础上做局部调整或者干脆换用其他目标函数和算法。理解每个优化目标对应什么算法比盲目套用某个“最优算法”更重要。5. 现场落地时容易踩的坑与处置经验5.1 加工时间的数据口径必须统一约翰逊法看起来只需要一张“工件×设备时间”表但生产现场这组数字的统计口径五花八门。最常见的坑是A工序时间按单件工时填写B工序时间按整批工时填写批次又不一样算法出来就是完全错误的排序。以机械加工为例首件准备时间、刀具调整时间、批量加工时间和单件加工时间到底哪一部分进了哪个字段必须提前定死。我的建议是直接用“每批次的整批占用设备时间”也就是从设备开始加工该批次到加工结束的全部时间中间不扣除等待和人员休息。原因很简单约翰逊法调度的是“设备占用顺序”不是“工人操作顺序”时间必须反映设备实际被占用的横截面。如果车间已经上了MES直接从系统取数会更可靠如果靠人工填表至少要保证同一个计划员统一口径。5.2 换型时间与排序相关时的边界标准约翰逊法假设工件的加工时间固定不变。实际注塑、冲压、印刷车间里换模换线时间往往与前后两个工件的组合有关从产品A切换到产品B需要1小时从产品B切换到产品C需要半小时这就破坏了加工时间固定的前提。如果换型时间占比很小不到总工时的5%可以粗略把平均换型时间并入加工时间约翰逊法仍然够用。如果换型时间占比高问题就变成了带顺序相关准备时间的调度问题和旅行商问题同构单纯约翰逊法不再适用。我在一个注塑厂见过类似的项目最后是用遗传算法加规则种子求解把约翰逊法结果作为初始种群的一员既提高了搜索效率也跨过了这个坑。5.3 批次能不能拆一个需要考虑的现实因素标准问题里假设一个工件是一个不可拆分的整体第二道工序必须等这个工件整体完成才能开工。实际生产中如果批量较大可以考虑拆分成更小的传送批次第一台设备加工完一部分先送到第二台设备开始加工不必等整批完成。这种“平行移动”能进一步缩短完工时间。要不要拆批本质上是个权衡拆批可以缩短生产周期但增加了搬运次数、交接记录和现场管理复杂度。如果你们现有信息系统不支持按子批次跟踪报工建议先不拆直接按整批优化顺序。等流程稳定了再评估引入平行移动能带来的收益。约翰逊法本身不处理拆批问题但它的最优顺序可以作为拆批后调度方案的基线用来对比收益。5.4 并行机与多工序车间的降维处理很多车间表面上有多台设备实际并非真正并行。比如有两台一样的数控铣床但分别承担不同型号零件的第一道工序这时可以拆成两条独立的流水线分别排序如果确实有一台设备能加工所有第一道工序第二道工序也有多台可选那就变成了“两台设备但有多个平行机”的问题约翰逊法的适用性就打了折扣。这种情况下我通常建议先用约翰逊法做一次“粗排”把它当成一个优秀的上限参照再用仿真软件或APS系统生成可行排程把约翰逊法结果作为初始解或者下界参考。至少在我经历过的项目里这样做比直接上一套复杂算法稳定得多。5.5 用Excel也能落地给计划员的小工具不是所有工厂都上了APS但几乎所有计划员手里都有Excel。约翰逊法完全可以用Excel实现。先把所有工件按A工序时间升序和B工序时间升序排列然后用INDEX和MATCH配合条件格式逐轮挑选全局最小时间或者用VBA写一个循环按算法规则自动生成排序结果。对于中小规模订单这种简单工具已经能解决80%的问题。更简单的做法是借助Excel的LAMBDA函数或SORTBY函数构建动态排序表。如果对VBA不熟悉就用第五章说的方法先把数据手工按规则跑一遍加深理解再尝试自动化。不要一开始就追求全自动先把排序逻辑吃透自动化只是顺手的事。5.6 一个值得养成的复盘习惯每次用新排序跑完一轮生产建议把实际完工时间和理论计算值做一次对比。如果差异超过10%先别急着怪算法大概率是数据口径出了问题或者现场有等待、返工等非计划因素。把偏差原因找出来并修正数据比反复调整排序算法重要得多。我在车间里推行这套方法时前两周的偏差都在15%以上后来发现是MES里工时漏掉了首检时间修正后偏差降到3%以内。6. 向前一步约翰逊法向三台及以上设备的推广思路6.1 三台可化简的经典条件约翰逊法最自然的推广是三台设备、每个工件都按顺序经过A、B、C三道工序的情况。如果中间设备B的加工时间有一个特殊规律——所有工件在B上的加工时间都不大于它们在A上的最小时间或者都不大于它们在C上的最小时间——三机问题就能化简成二机问题。具体做法是构造两台“虚拟设备”第一台虚拟设备的时间为A工序加B工序时间第二台虚拟设备的时间为B工序加C工序时间然后套用标准约翰逊法排序。这个化简条件在学术上被称为Johnson三机扩展条件。现实中这个条件比较苛刻很少能恰好满足但它提供了一个重要直觉中间工序负荷特别轻的流水线本质上可以等价成两工序系统来排序。6.2 CDS启发式工程上真正常用的推广实际生产中更多见的是四台、五台甚至更多设备的流水线这时候CDS算法Campbell-Dudek-Smith是经典方案。它把多机问题拆成若干个两机子问题第一次只考虑第一台和最后一台设备第二次考虑前两台设备和后两台设备第三次考虑前三台设备和后三台设备以此类推。每一组都套用约翰逊法得到一个候选序列最后把若干个候选序列分别仿真或计算完工时间挑最好的那个作为最终排序。CDS的逻辑是把约翰逊法做成一个“候选序列生成器”覆盖不同瓶颈位置再从中选出最优解。它的计算量小工程实现容易而且效果通常很不错在学术界和工业界应用都很广泛。很多APS软件的排序引擎里CDS就是启动阶段生成初始解的工具之一。6.3 当问题规模变大时约翰逊法扮演什么角色规模再往上走比如几十台设备、几百个订单还附带模具寿命、人员班次、物料齐套等约束就需要上元启发式算法或数学规划求解器了。但即便在这种大型系统里约翰逊法仍然有它的位置一是作为初始可行解让求解器或搜索算法从一个高质量起点出发二是作为下界估计帮助判断启发式解离最优解还有多远三是作为可解释性工具输出一组“为什么这么排”的规则调度员更容易接受。我在推进APS项目的过程中最深的体会是算法再高级最后落地都要靠计划员认可。约翰逊法最大的价值不只是它能算出最优解而是它足够简单、足够透明能让现场的人一眼看懂排序逻辑从而愿意使用它。很多复杂的算法黑箱最后被弃用反而栽在“计划员不信任”上。6.4 从一个两机问题到一套现场调度方法论如果你现在面对的是一个刚开始重视排产的小车间不要一上来就上重武器。先用约翰逊法把两台核心瓶颈设备的排序做起来让计划员看到28小时和32小时之间的差距让班组长理解压空闲时间就是压交付周期。这个习惯建立起来后再逐步引入拆批、换型优化、并行机调度等进阶手段。调度问题的解法从来不是越复杂越好而是越贴现场、越能落地越好。约翰逊法作为运筹学进入生产管理领域最早的成果之一至今没被淘汰恰恰说明它抓住了制造业最本质的两点所有工件共用瓶颈设备所有订单都希望尽快完工。只要这两点存在约翰逊法的思路就有用武之地。我个人在实际项目中还有一个屡试不爽的技巧把约翰逊法算出的序列当作“照妖镜”凡是不符合这个排序方向的现场逻辑都值得追问一句“凭什么”。有些时候你能发现隐藏的约束有些时候你会发现现场只是习惯了旧的错误做法。把这些问题梳理清楚比单纯换一套算法更有价值。