📚 课程目录第3章排程问题建模

3. 排程问题建模

排程问题的求解效果，往往在建模阶段就已经决定了一半。同一个车间排程场景，用不同的模型范式表达，求解器的搜索空间、约束传播效率和解的质量可能相差几个数量级。本节围绕四种主流建模范式展开：数学规划模型（LP/MILP）、混合整数规划（MIP）、约束规划（CP）以及图模型，帮助你在工程实践中做出正确的建模选择。

一、核心原理：四种建模范式的定位

排程问题的本质是在资源能力、工艺顺序、交期等约束下，为每个工序确定开始时间与占用资源，并优化某个目标函数。不同范式对"约束"和"决策"的表达方式不同：

数学规划（LP）：决策变量连续，约束与目标均为线性表达式，适合处理连续时间、批量分配等松弛问题，但无法直接表达"要么A要么B"的离散选择。
混合整数规划（MIP）：在LP基础上引入整数/0-1变量，可表达机器分配、顺序选择、开机决策等离散逻辑，是排程建模最通用的范式，但大规模问题求解时间可能爆炸。
约束规划（CP）：以变量域和约束传播为核心，天然擅长表达"不重叠""先后顺序""资源容量"等组合约束，在高度离散、约束密集的排程中表现优异。
图模型：用节点表示工序、用有向边表示先后关系或资源冲突，将排程转化为路径、割或匹配问题，适合析取图、网络流等结构化场景。

建模选择的核心判断：如果问题以连续量和线性目标为主，优先LP/MIP；如果问题以离散顺序和资源冲突为主，优先CP；如果问题具有明显的网络结构，优先图模型。

二、方法流程：从场景到模型的落地步骤

识别决策变量：确定哪些是连续变量（如开始时间、加工时长），哪些是整数或0-1变量（如机器选择、顺序指示）。
提取硬约束：工艺路线先后关系、机器不重叠、资源容量、交期窗口等，逐条写成数学表达式或CP约束。
定义目标函数：常见有最小化最大完工时间（makespan）、最小化总拖期、最小化换型次数等，需与业务KPI对齐。
选择求解范式：根据变量类型和约束密度，决定用MIP、CP还是图算法，必要时采用混合求解。
验证与调优：用小规模实例验证模型正确性，再通过对称性破除、有效不等式、搜索策略等提升求解效率。

三、案例场景：三工序两机器的建模对比

假设有3个工件J1、J2、J3，需在机器M1、M2上加工，每个工件有固定的工序顺序。下面给出MIP与CP两种建模片段的核心表达：

# MIP 建模片段（伪代码）
变量:
  x[i][j]  : 工件i在机器j上的开始时间 (连续)
  y[i][k]  : 工件i先于工件k在同一机器上 (0-1)
约束:
  x[i][j+1] >= x[i][j] + p[i][j]        # 工艺顺序
  x[i][j] >= x[k][j] + p[k][j] - M*(1-y[i][k])  # 机器不重叠
目标:
  min Cmax = max(x[i][last] + p[i][last])

# CP 建模片段（伪代码）
变量:
  start[i][j] : 区间变量
约束:
  end_before_start(start[i][j], start[i][j+1])  # 顺序
  no_overlap(machine[j])                         # 资源不重叠
目标:
  minimize makespan

可以看到，MIP需要用大M法线性化"不重叠"逻辑，约束数量随工件数平方增长；而CP直接用no_overlap全局约束，传播效率更高。对于10个工件以内的小规模问题，两者都能快速求解；当工件数超过50时，MIP往往需要数小时，而CP配合搜索策略可在分钟级给出可行解。

四、图模型：析取图与网络流视角

图模型为排程提供了另一种直观表达。析取图（Disjunctive Graph）中，节点是工序，实线边表示工艺顺序，虚线边表示同一机器上的候选顺序。排程问题等价于为每条虚线边选择方向，使图中无环且关键路径最短。这一视角直接催生了移位瓶颈启发式（Shifting Bottleneck）等经典算法。

网络流模型则适合处理资源分配与批量排程，例如将机器时间离散为时间槽，用最小费用流表达工序到时间槽的分配。图模型的优势在于可以复用成熟的图算法库，但表达能力受限于问题是否具有网络结构。

五、常见误区与复盘要点

误区一：认为MIP一定优于CP。实际上在作业车间排程中，CP的no_overlap约束传播往往比MIP的大M线性化快得多，尤其是约束密集时。

误区二：忽略对称性。多个相同机器或相同工件会产生大量等价解，导致求解器反复搜索同一区域。应通过对称性破除约束或变量排序来消除。

复盘建议：建立模型后，先用小规模实例验证约束是否完整、目标是否正确，再逐步放大规模，记录求解时间与间隙（gap）的变化曲线，作为范式选择的量化依据。

范式	决策变量	擅长约束	典型求解器	适用规模
LP	连续	线性资源平衡	Gurobi, CPLEX	大规模松弛
MIP	连续+整数/0-1	分配、顺序、开机	Gurobi, CPLEX, SCIP	中小规模精确
CP	整数域/区间	不重叠、先后、容量	OR-Tools CP-SAT, Choco	中大规模可行解
图模型	节点/边选择	路径、割、匹配	NetworkX, LEMON	结构化问题

综合来看，排程建模没有"万能范式"。工程实践中更常见的做法是混合建模：用MIP处理全局分配与目标优化，用CP处理局部顺序与资源冲突，用图算法快速构造初始解或下界。理解四种范式的表达边界，才能在面对具体排程场景时快速锁定最合适的建模路径。