4. 数学建模基础与排程模型表达

生产排程问题要交给求解器处理，第一步是把车间里的“谁在什么时间做什么”翻译成数学语言。这一节围绕四个建模要素展开：决策变量、目标函数、约束条件，以及把它们组织成混合整数线性规划（MILP）的框架，最后讨论模型规模与求解难度的关系。

决策变量：三类基本对象

排程模型的决策变量通常分三类。第一类是开始时间变量，记为 \(S_{ij}\)，表示工件 \(i\) 的第 \(j\) 道工序的开始时刻，它是连续变量。第二类是顺序变量，用于描述同一台机器上两道工序谁先谁后，常用 0-1 变量 \(y_{ijk}\) 表示“工序 \(i,j\) 是否排在工序 \(k,l\) 之前”。第三类是分配变量，当一道工序可以在多台并行机中选择一台加工时，用 0-1 变量 \(x_{ijm}\) 表示工序 \(i,j\) 是否分配到机器 \(m\)。

三类变量的组合决定了模型的表达力。只含开始时间与顺序变量的模型对应经典作业车间排程；加入分配变量后，可覆盖并行机、柔性作业车间等场景。建模时先明确“哪些量是求解器要决定的”，再决定变量类型，避免把可由其他变量推导出的量重复设为决策变量。

目标函数与线性化技巧

最常见的目标是最小化最大完工时间 \(C_{\max}\)，即所有工件完工时刻的最大值。引入辅助变量 \(C_{\max}\)，对每个工件 \(i\) 的末道工序 \(j_i\) 施加 \(C_{\max} \ge S_{ij_i} + p_{ij_i}\)，目标写成 \(\min C_{\max}\)，就把“最大值”转化成了线性约束。这是排程建模中最基础也最常用的线性化手法。

另一类目标是总拖期，形式为 \(\sum_i \max(0, C_i - d_i)\)。max 函数本身非线性，处理方式是引入拖期变量 \(T_i \ge C_i - d_i\) 且 \(T_i \ge 0\)，目标改为 \(\min \sum_i T_i\)。由于最小化会自然把 \(T_i\) 压到恰好等于正部，这一松弛是精确的。

顺序变量与时间变量之间也存在典型的“大 M”线性化。若 \(y_{ijk}=1\) 表示工序 \(i,j\) 先于 \(k,l\) 在同一机器上加工，则约束写成：

S_{kl} >= S_{ij} + p_{ij} - M * (1 - y_{ijk})
S_{ij}  >= S_{kl} + p_{kl} - M * y_{ijk}

其中 \(M\) 是足够大的常数。\(M\) 取值过大会削弱线性松弛的紧致性，导致分支定界效率下降；取值过小则可能误删可行解。工程上通常取“所有加工时间之和”或“时间窗上界”作为 \(M\) 的安全上界，并在小规模算例上验证约束不冲突。

四类核心约束

时间窗约束限定工序只能在允许区间内开始，例如 \(r_{ij} \le S_{ij} \le \bar{d}_{ij} - p_{ij}\)，其中 \(r_{ij}\) 是最早可开工时刻，\(\bar{d}_{ij}\) 是最晚允许完工时刻。它常来自物料到位时间、班次安排或交期倒推。

资源能力约束保证同一时刻一台机器只加工一个工件，或一组资源的总占用不超过容量。对单机不重叠，它由顺序变量与上面的两条大 M 约束共同实现；对多资源容量型问题，则写成按时间离散的累加约束 \(\sum_{ij} a_{ijm} \cdot z_{ijmt} \le Cap_m\)。

工序先后约束描述同一工件内部的工艺路线：\(S_{i,j+1} \ge S_{ij} + p_{ij}\)。这是硬约束，直接决定可行域的骨架。

无重叠约束是排程区别于普通资源分配的关键，它要求同一机器上任意两道工序的加工区间不相交。用析取形式表达就是“要么 \(i,j\) 在 \(k,l\) 之前，要么反之”，再借助 0-1 变量与大 M 转成合取形式，这正是 MILP 能表达排程逻辑的核心机制。

MILP 建模框架的组织顺序

把上述要素组织成模型，建议按固定顺序推进：先定义集合与参数（工件集、工序集、机器集、加工时间、交期、释放时间），再声明决策变量及其类型，然后逐条写出约束并标注每条约束的业务含义，最后写目标函数。这个顺序的价值在于：约束写完后再写目标，可以避免目标函数里出现未定义的中间量；每条约束带注释，则便于后续排障时定位“哪条业务规则导致了不可行”。

一个常见的建模陷阱是把“机器不能同时加工两个工件”和“工件工序不能重叠”混为一谈。前者是机器维度的资源约束，后者是工件维度的工艺约束，二者作用对象不同，约束形式也不同。建模时应分别列出，不要合并成一条含糊的“不重叠约束”。

模型规模与求解难度评估

规模评估先数变量和约束的量级。设工件数为 \(n\)、每工件平均工序数为 \(m\)、机器数为 \(k\)，则开始时间变量约 \(nm\) 个；若每台机器上平均有 \(q\) 道工序，顺序变量约 \(k \cdot q(q-1)/2\) 个，随单机工序数呈平方增长。约束数量同样随工序对数平方增长。这意味着工件数翻倍时，模型规模可能增长到四倍以上。

难度评估不能只看规模。作业车间排程在 \(k \ge 3\) 时已是 NP-hard，规模稍大就可能出现求解时间急剧上升。实践中可用三个信号判断：线性松弛的目标值与整数解差距是否很大（差距大说明大 M 或约束形式偏松）；分支定界节点数是否爆炸；求解器日志中可行解改进是否长期停滞。若出现这些信号，应考虑收紧 \(M\)、增加有效不等式、改用时间索引模型，或对大规模算例退化为启发式求解。

最后需要强调，MILP 模型是排程问题的“精确表达”，但精确不等于高效。建模阶段就应同步考虑求解可行性：能用时间索引模型替代顺序变量时优先替代；能通过预处理固定部分变量时先固定；对超大规模实例，保留 MILP 作为基准与小规模验证工具，用启发式方法承担实际排产，是更务实的工程选择。