4. 经典调度算法

在生产排程优化中，经典调度算法是求解器工程的重要基石。它们计算量小、响应快、易于解释，常被用作初始解生成器、滚动排程的实时决策器，或作为元启发式算法的比较基线。本节聚焦四类经典方法：优先规则、分派规则、Johnson算法与CDS启发式，理解它们的适用边界与工程实现方式。

一、核心原理：从单机到流水车间的规则体系

优先规则解决的是“当多道工序竞争同一资源时，先加工谁”的问题。它不追求全局最优，而是通过局部贪心快速构造可行解。常见规则包括：

• SPT（最短加工时间优先）：降低平均流程时间，但长工件易被饿死。
• EDD（最早交货期优先）：降低最大拖期，适合交期敏感场景。
• LPT（最长加工时间优先）：常用于并行机负载均衡。
• CR（临界比）：CR = (交期 - 当前时间) / 剩余加工时间，动态优先级。
• FCFS（先到先服务）：公平但平均流程时间较差。

分派规则是优先规则在具体设备或工位上的执行机制。它通常由“候选队列 + 优先级计算 + 资源可用性判断”组成，在离散事件仿真或APS引擎中按事件驱动方式触发。分派规则可以静态配置，也可以随车间状态动态切换。

二、Johnson算法：两机流水车间的最优解

Johnson算法针对两台机器、所有工件加工顺序相同的流水车间问题，能在多项式时间内得到最小化最大完工期（makespan）的最优解。其核心思想是：让第一台机器尽早开工、第二台机器尽早收尾，避免第二台机器长时间等待。

算法步骤：

1. 列出每个工件在两台机器上的加工时间 (a_i, b_i)。
2. 找出所有未排工件中加工时间最小的一个。
3. 若该最小值出现在第一台机器，则把该工件排在序列最前面；若出现在第二台机器，则排在最后面。
4. 移除该工件，重复直到所有工件排完。

工件   M1   M2
J1     3    6
J2     5    2
J3     1    4
J4     4    3

排序过程：
最小值为 J3 的 M1=1 → 放最前：J3
剩余最小值为 J2 的 M2=2 → 放最后：J2
剩余最小值为 J1 的 M1=3 → 放前部：J3, J1
剩余 J4 放中间：J3, J4, J1, J2
最优 makespan = 16

Johnson算法虽然只适用于两机场景，但它是理解流水车间调度结构的钥匙，也是CDS启发式的基础构件。

三、CDS启发式：从两机到多机的桥梁

CDS（Campbell, Dudek, Smith）启发式把Johnson算法推广到m台机器的流水车间。它不直接求解m机问题，而是构造若干“虚拟两机问题”：把前k台机器合并为第一台虚拟机器，把后k台机器合并为第二台虚拟机器，对每个k调用Johnson算法，最后取makespan最小的排序。

具体流程：

1. 对 k = 1, 2, ..., m-1：
2. 计算虚拟机器时间：A_i = sum_{j=1..k} p_ij，B_i = sum_{j=m-k+1..m} p_ij。
3. 用Johnson算法对 (A_i, B_i) 排序，得到一个候选序列。
4. 计算该序列在真实m台机器上的makespan。
5. 选择所有候选中makespan最小的序列作为最终解。

CDS的计算复杂度约为 O(m·n log n)，非常适合作为大规模流水车间的快速初始解。它的解质量通常优于简单优先规则，但不如精确方法或元启发式。

四、案例场景：某机加工车间排程

某机加工车间有4个工件需要经过车床和铣床两道工序，加工时间如下表。使用Johnson算法排序，并对比SPT规则的效果。

Johnson排序结果为 J3 → J4 → J1 → J2，makespan = 16。若按SPT规则（按M1时间升序）排序为 J3 → J1 → J4 → J2，makespan = 18。可见Johnson算法在两机场景下确实更优。

五、误区与复盘

• 误区一：优先规则等于最优解。优先规则是启发式，只在特定目标下表现良好，不能保证全局最优。
• 误区二：Johnson算法可用于任意车间。它仅适用于两机、所有工件同顺序的流水车间，作业车间或柔性车间需改用其他方法。
• 误区三：CDS一定优于优先规则。CDS在流水车间通常更好，但在作业车间或约束复杂时，简单分派规则可能更稳健。
• 误区四：忽略动态扰动。实际生产中设备故障、插单、物料延迟都会破坏静态排序，需要结合滚动排程与重调度策略。

掌握优先规则、分派规则、Johnson算法与CDS启发式，能够帮助我们在排程系统设计初期快速搭建可运行的原型，并为后续引入更复杂的优化算法提供可靠的基线。理解它们的数学前提与工程边界，比盲目调参更重要。