2. 并行工序建模基础

在并行工序与替代设备排程中，排程对象不再是“一条工序链”，而是一张有向网络。网络中的节点代表工序或工序-设备组合，边代表工序之间的先后依赖。只有先把这张网络建准，后续的替代设备选择、资源冲突消解、关键路径识别才有意义。本节围绕四个核心问题展开：工序网络图怎么画、并行路径怎么识别、汇合与分流节点如何处理、时序约束如何写成可计算的数学表达。

一、工序网络图：从工艺路线到有向图

工序网络图由节点集合 V 和边集合 E 构成，记作 G=(V,E)。节点通常表示一道工序，若同一道工序可由多台替代设备完成，则把节点细化为“工序-设备”组合节点，例如 A1 表示工序 A 在设备 1 上加工。边 (i,j) 表示工序 j 必须在工序 i 完成后才能开始，即存在时序依赖。

建模时先确定三件事：一是工序清单及每道工序的可选设备；二是工序之间的工艺先后关系；三是每道工序在每台设备上的加工时间。以某零件加工为例，工序 A（粗加工）可选设备 M1、M2，工序 B（精加工）可选 M2、M3，工序 C（热处理）仅 M4 可用，工序 D（检测）仅 M5 可用。工艺要求 A 完成后才能 B，B 完成后才能 C，C 完成后才能 D。若把替代设备展开，网络节点为 A1、A2、B2、B3、C4、D5，边为 A1→B2、A1→B3、A2→B2、A2→B3、B2→C4、B3→C4、C4→D5。这样一张图既表达了工艺顺序，也表达了设备替代关系。

二、并行路径：网络中的多条可行通道

并行路径指从起点到终点之间，除共享节点外没有共同工序的多条路径。上例中 A1→B2→C4→D5 与 A2→B3→C4→D5 就是两条并行路径，它们在 C4 处汇合。并行路径的存在意味着排程时不能只盯一条链，而要同时考虑多条链上的设备占用与时间窗口。

识别并行路径的实用方法是：先找入度为 0 的起点和出度为 0 的终点，再沿边做深度优先遍历，记录所有从起点到终点的路径；若两条路径除汇合节点外无公共节点，则互为并行路径。并行路径上的工序可以同时推进，但共享设备时会产生资源竞争，这正是替代设备排程要解决的核心矛盾。

三、汇合与分流节点：网络中的同步与分支

汇合节点指有多条入边、一条出边的节点，表示多道前置工序全部完成后，后续工序才能开始。例如 C4 有 B2、B3 两条入边，只有 B2 和 B3 都完成，C4 才能启动。汇合节点的开始时间由所有前置工序完成时间的最大值决定，而不是最小值或平均值。

分流节点指有一条入边、多条出边的节点，表示一道工序完成后可同时触发多道后续工序。例如 A1 完成后可同时触发 B2 和 B3，但实际排程中通常只选择其中一条路径，因为 B2 和 B3 是同一道工序 B 的替代方案，不应同时执行。因此分流节点在替代设备场景下往往带有“择一”语义，建模时需用互斥约束或选择变量表达。

四、时序约束的数学表达

设工序 i 的开始时间为 S_i，加工时间为 p_i，完成时间为 F_i=S_i+p_i。最基本的先后约束为：若工序 j 必须在工序 i 完成后开始，则 S_j ≥ F_i，即 S_j ≥ S_i + p_i。对于汇合节点 k，其开始时间满足 S_k ≥ max(F_i)，i 属于 k 的所有前置工序集合。对于分流节点，若后续工序为互斥替代，则引入 0-1 变量 x_{i,r} 表示工序 i 是否选择设备 r，满足 Σ_r x_{i,r}=1。

设备占用约束可写成：同一设备 r 上任意两道工序 i、j 若都选择 r，则必须满足 S_j ≥ F_i 或 S_i ≥ F_j，二者至少成立一个。引入 0-1 变量 y_{ij}=1 表示 i 先于 j，则 S_j ≥ F_i - M(1-y_{ij})，S_i ≥ F_j - M·y_{ij}，其中 M 为足够大的常数。这样就把“设备不能同时加工两道工序”写成了线性不等式，便于用混合整数规划求解。

五、建模检查要点

完成网络图后，建议做三项检查。第一，检查每个汇合节点的入边是否覆盖了所有必要前置工序，漏掉一条边会导致排程结果偏乐观。第二，检查分流节点是否明确标注了“择一”还是“并行”，前者需要互斥变量，后者需要同时启动。第三，检查时序约束中的 M 值是否足够大，M 过小会错误地截断可行解，M 过大则降低求解效率，通常取所有工序加工时间之和即可。