3. 生产排程问题的分类与典型模型

生产排程问题看似千变万化，但学术界和工业界经过几十年梳理，已经形成了一套相对稳定的分类框架。掌握这套框架的价值在于：当你拿到一个实际排产需求时，能迅速判断它属于哪一类问题、有哪些成熟模型可以借鉴、求解难度大概在什么量级。本节围绕机器环境、时间特性、确定性程度、目标函数和复杂度五个维度展开，并给出一个可对照的建模示例。

一、按机器环境分类：五类典型模型

机器环境描述的是工件在哪些资源上加工、以什么顺序经过这些资源。它是排程分类中最基础的一维，通常用三字段记法 α|β|γ 中的 α 表示。

• 单机（1）：所有工件在同一台设备上加工，只需决定加工顺序。它是理解排序规则（如 SPT、EDD）的基准模型，实际中对应单台关键设备、单条灌装线等场景。
• 并行机（P、Q、R）：多台设备功能相同，工件任选其一加工。P 表示同速并行机，Q 表示异速（速度不同），R 表示无关并行机（不同机器加工同一工件耗时不同）。核心决策是“分配给哪台机器 + 机器上的顺序”。
• 流水车间（F、Fm）：每个工件必须依次经过全部机器，且所有工件的加工路线相同。典型如汽车涂装线、PCB 钻孔—电镀—成型线。决策是各机器上的工件排序，目标是减少机器空闲与等待。
• 作业车间（J、Jm）：每个工件有自己固定的加工路线，不同工件路线可以不同，同一工件在不同机器上的顺序受工艺约束。它是五类中最难的一类，经典 Job Shop 基准问题就是它的代表。
• 开放车间（O）：每个工件需在每台机器上加工一次，但加工顺序完全自由，由排程决定。实际中较少见，多用于理论分析和某些检测工序场景。

需要强调：这五类不是互斥的标签，而是建模时的抽象层次。一条实际产线可能同时包含并行机和流水段，建模时往往拆成子问题分别处理，再通过约束耦合。

二、静态与动态、确定性与不确定性

静态排程假设所有工件在排程开始时已知、加工时间固定、排程期内不插入新任务，一次求解即得到完整计划。动态排程则面对工件陆续到达、设备故障、急单插入等扰动，需要滚动排程或重调度策略。工程上常见的做法是“静态基线 + 动态修正”：先按已知订单生成基线计划，再以固定时间窗（如每 4 小时）滚动更新。

确定性排程假设加工时间、到达时间、设备可用性均为已知常数；不确定性排程则承认这些参数存在波动，常用方法包括鲁棒优化（保证最坏情况下可行）、随机规划（以期望为目标）和模糊排程。一个实用的折中是“缓冲时间法”：在关键工序后预留缓冲，用确定性模型求解，再用缓冲吸收波动。

三、常用目标函数

目标函数决定排程“优化什么”，通常用 γ 表示。常见的有：

多目标之间往往冲突：压缩 Cmax 可能增加拖期，降低 WIP 可能牺牲利用率。实际建模时常用加权和、字典序或帕累托前沿来处理，权重需结合业务优先级确定，而不是拍脑袋给定。

四、复杂度与可解性初步认识

排程问题的求解难度差异极大。单机问题在多数正则目标下存在多项式算法（如 EDD 对最大拖期最优）；并行机分配问题部分可多项式求解；而流水车间三台以上机器、作业车间的一般情形，多数属于 NP-hard。这意味着随着工件数 n 和机器数 m 增大，精确算法（分支定界、动态规划）的求解时间呈指数增长。

因此工程上要建立“问题规模—方法选择”的对应意识：小规模（如 n≤20）可用精确算法或约束规划求最优；中等规模用启发式规则（SPT、EDD、Johnson 规则）快速得到可行解；大规模则依赖元启发式（遗传算法、禁忌搜索、模拟退火）在可接受时间内逼近较优解。判断可解性时，先看问题是否属于已知多项式可解的特例，再评估规模是否超出精确算法能力，最后才决定是否引入近似方法。

五、一个可对照的建模示例

设某车间有 3 个工件需依次经过机器 M1、M2（流水车间），加工时间如下（示例假设数据）：

工件   M1   M2
J1     3    2
J2     2    4
J3     4    1

该问题记为 F2||Cmax，属于两台机器流水车间、以最大完工时间为目标。按 Johnson 规则：先找出最短加工时间，若在 M1 则排在最前，若在 M2 则排在最后，逐步确定顺序。本例最短为 J3 在 M2 的 1，故 J3 排最后；剩余 J1、J2 中最短为 J2 在 M1 的 2，排最前；于是顺序为 J2 → J1 → J3。按此顺序在 M1 上依次加工 2、3、4，M2 上依次加工 4、2、1，可算得 Cmax = 10。若换顺序 J1 → J2 → J3，则 Cmax = 11，说明排序决策直接影响目标值。这个例子说明：识别问题类别后，选用对应规则即可快速得到可解释的排程，而不必一上来就动用复杂算法。