1. 课程导入与排程问题界定
在制造现场，排程人员经常面对这样一类任务：一张订单需要经过多道工序，其中某些工序可以同时开工，某些工序必须等待前序全部完成；同时，同一道工序又可能有多台设备都能加工，只是效率、换型时间或可用时段不同。传统的车间排程模型往往假设"每道工序只有一台指定设备、工序之间严格串行"，一旦遇到并行工序与替代设备，这种简化假设就会失效，排出来的计划在现场根本执行不下去。本课程要解决的，正是这类更贴近真实生产的排程问题。
并行工序与替代设备排程的定义
并行工序指同一订单（或同一工件）中，若干道工序之间不存在先后约束，可以同时加工，也可以按任意顺序加工。例如某结构件先做"钻孔"和"铣槽"，两者互不依赖，都完成后才能进入"装配"。这里的钻孔与铣槽就是并行工序，它们共同的前序是下料，共同的后续是装配。
替代设备指同一道工序可以由多台设备中的任意一台完成，这些设备在加工时间、换型时间、精度等级或可用时间窗上存在差异。例如某道"精磨"工序，既可以在高精度磨床A上做（单件8分钟），也可以在普通磨床B上做（单件13分钟），但B的排队更短。选择哪台设备，会直接影响该工序的完工时间，并进一步影响后续工序能否按时开工。
把两者放在一起，排程决策就从"给每道工序定一个开始时间"变成了三个耦合的决策：并行工序的先后与资源分配、每道工序的设备选择、每台设备上多道工序的加工顺序。这三者相互牵制，是问题难度的根源。
典型场景
这类问题在离散制造中非常普遍，几个典型场景如下：
- 机加工车间：同一零件的多面孔位加工可并行；粗加工可在多台加工中心之间选择。
- 注塑与后处理：多副模具并行生产不同零件，去毛刺、检验等后处理工序可在多条产线间分配。
- 电子装配：多块板卡并行贴片，测试工序可在多台测试台之间选择，测试台精度不同导致复测率不同。
- 模具修复与备件加工：紧急插单时，同一修复工序可在不同规格设备上完成，交期压力下必须快速决策。
这些场景的共同特征是：订单有交期、设备有产能上限、工序之间存在并行与汇合结构、设备之间存在可替代性。排程目标通常不是单一指标，而是"交期达成率优先、设备利用率次之、换型次数尽量少"这样的多目标组合。
与经典车间排程的区别
经典作业车间排程（Job Shop）通常假设：每道工序的设备唯一、工序间为严格串行链、设备不重叠加工。与之相比，本节问题有三点本质差异：
| 对比维度 | 经典车间排程 | 并行工序与替代设备排程 |
|---|---|---|
| 工序结构 | 串行链，前后关系唯一 | 含并行分支与汇合节点，形成工序网络 |
| 设备关系 | 工序与设备一一对应 | 一道工序对应多台候选设备，需选择 |
| 决策变量 | 主要为工序开始时间与设备排序 | 增加并行分支的资源分配与设备选择 |
| 约束来源 | 工序先后、设备不重叠 | 再叠加并行分支同步、替代设备能力差异 |
| 求解难度 | 已属NP难 | 解空间更大，需专门建模与启发式方法 |
需要特别强调的是"汇合约束"：并行分支必须全部完成后，后续工序才能开始。这意味着并行分支中耗时最长的那条决定了后续工序的最早开工时间，排程时要优先保证关键分支不被拖延，而不是平均分配资源。
本节核心关系图解
下图用一张工序—设备关系图，把上述概念放在同一个视图里：左侧是订单的工序网络（含并行分支与汇合），右侧是候选设备池，中间的连线表示"该工序可在哪些设备上加工"。通过这张图可以直观看到，排程要同时回答"分支怎么排、设备怎么选、设备上谁先谁后"。
图中绿色虚线表示钻孔、铣槽两道并行工序都可在 MC-1 或 MC-2 上加工，紫色虚线表示精磨可在 GM-A 或 GM-B 上加工。排程时若把钻孔和铣槽都压到 MC-1，虽然单件时间短，但会造成设备排队；若把铣槽放到 MC-2，则两条并行分支的完工时间更接近，汇合点 OP40 能更早开工。这正是"并行分支平衡 + 替代设备选择"的典型权衡。
课程项目任务发布
本课程以一个贯穿全程的排程项目为载体，要求你针对上述结构完成一套可执行的排程方案。项目任务如下：
- 对象：一个含 6 个订单、每单 4～6 道工序的机加工车间，工序网络中存在 2 组并行分支和 1 个汇合点，关键工序有 2～3 台替代设备。
- 输入：订单交期、各工序在每台候选设备上的加工时间与换型时间、设备可用时间窗、工序先后与并行关系。
- 要求：给出每道工序的设备选择、开始与结束时间，以及每台设备上的加工顺序；计算各订单完工时间与交期偏差。
- 目标：在满足工序先后与设备不重叠约束的前提下，优先保证交期达成，其次降低设备空闲与换型次数。
- 交付：一份排程结果表（含工序、设备、开始、结束、是否延期）和一份决策说明，解释关键分支与设备选择理由。