问题定义
运筹优化与调度解决的是"在多重约束下如何安排资源"的问题。生产计划给出的是目标，调度要把它拆成每一台设备、每一个班次、每一批次的可执行安排，同时处理换型时间、模具与工装、人员资质、物料齐套、交期优先级等相互冲突的约束。
在智能体的能力体系中，这一层对应"规划决策"：把宏观目标分解为子任务，并在产能、成本、时间的多约束环境下生成方案。核心难点在于问题规模（组合爆炸）、不确定性（设备故障、急单插单）与求解时效（计划员等不了两小时）。
核心技术
数学规划（MILP / MINLP）
把调度问题写成目标函数与约束集合，由求解器搜索最优解。混合整数线性规划（MILP）是工业界最成熟的建模方式，求解核心为分支定界配合割平面与启发式。优点是能保证最优性与给出对偶信息，缺点是规模增大时求解时间不可控。
松弛：先解 LP 松弛得下界，再分支；gap = (UB - LB) / UB 用于判断收敛
约束规划（CP）
CP 用区间变量描述任务的开始、持续时间与结束，通过全局约束（如 NoOverlap）表达资源互斥，配合传播与搜索策略求解。对含顺序依赖、换型矩阵、可选工序的排产问题，CP 的建模效率和求解表现通常优于 MILP。
NoOverlap({interval_i})：同一资源上任务互不重叠
OptionalIntervalVar：工序可选，用于工艺路径分支
经典调度模型
Job-Shop（每工件工艺路径不同）、Flow-Shop（路径一致）、Flexible Job-Shop（工序可择机）、RCPSP（资源约束项目调度）。评价指标常见 makespan（最大完工时间）、总流程时间、拖期惩罚、设备利用率。
拖期：T_j = max(0, C_j - d_j)，加权拖期 Σ w_j T_j
析取图：G = (N, C ∪ D)，对析取弧定向即得到一个可行 schedule
元启发式算法
当精确方法在可接受时间内求不出满意解时，使用遗传算法、模拟退火、禁忌搜索、蚁群等。核心在于编码方式与邻域算子设计，而不是算法本身。
模拟退火：接受劣解概率 P = exp(-Δ / T)，T 按降温系数衰减
禁忌搜索：维护禁忌表禁止近期回退，用特赦准则放开优质解
滚动时域与重调度
静态最优解在动态车间里很快失效。常见做法是滚动时域：只执行方案的前一小段，随后根据最新状态重新求解；同时对急单、故障等扰动事件触发局部重调度，而非全局重排。
重调度代价：J = α·性能损失 + β·方案变动度（避免方案频繁抖动）
仿真优化与强化学习
目标函数难以解析表达（含排队、随机故障）时，把仿真器当作评估黑盒，外层用优化算法或强化学习搜索策略。数字孪生提供仿真环境，调度策略在其中低成本试错，再迁移到真实车间。
RL：s_t = 车间状态，a_t = 派工规则选择，r_t = -(完工时间增量)
方法选型对比
| 方法 | 规模适应性 | 最优性 | 建模成本 | 适用 |
|---|---|---|---|---|
| MILP（商业求解器） | 中小规模，数千变量级 | 可证明最优 / 给 gap | 高，需线性化技巧 | 批量计划、配料、产能分配 |
| CP（CP-SAT 等） | 中大规模工序排程 | 给定时间内最优 | 中，表达能力强 | Job-Shop 排产、人员排班 |
| 元启发式 | 大规模 | 无最优性保证 | 中，算子设计靠经验 | 复杂约束、求解时间受限 |
| 派工规则 | 任意规模 | 无 | 低 | 实时派工、基线对照 |
| 仿真优化 | 受仿真成本限制 | 无 | 高，需建仿真模型 | 含随机性、目标不可解析 |
| 强化学习 | 训练成本高，推理快 | 无 | 高，奖励设计敏感 | 高频动态派工、策略类决策 |
工程实践指南
建模要点
- 约束分硬软：物理与安全约束设为硬约束；交期、均衡生产设为软约束并带惩罚权重，避免模型无解
- 先对齐数据再建模：工艺路径、标准工时、换型矩阵、设备日历的准确性决定方案可用性，模型再优也救不了错的基础数据
- 时间粒度选择：分钟级粒度精度高但规模大，班次级粒度求解快但无法指导现场，通常分层——计划层粗、排程层细
求解工程化
- 设时间预算：明确给出求解时限（如 30~120 秒），取当前最优解，保证系统响应可预期
- 热启动：以上一次方案作为初始解，重调度时收敛更快，方案变动也更小
- 监控 gap 与不可行原因：不可行时输出冲突约束集（IIS），让计划员知道该放松什么，而不是只报"无解"
落地集成
- 方案可解释：输出甘特图 + 关键约束说明，让计划员理解"为什么这么排"，这是能否被采用的前提
- 人工可干预：支持锁定部分工序、手工调整后再优化，把系统定位为辅助而非替代
- 与执行层闭环：实际开工/完工时间回流，用于校准标准工时与换型时间，模型才能越用越准
常见误区
- 追求全局最优：车间状态每小时都在变，追求理论最优不如追求"稳定、可解释、可快速重算"
- 忽视方案抖动：每次重排方案大幅变化会让现场无所适从，需显式约束变动度
- 一次性上线整体排产：建议先做单条产线或单工序试点，验证收益后再扩展
开源项目
Google OR-Tools
集成 CP-SAT 约束规划、线性规划与路由求解器，接口友好、无商业授权限制，是排产与车辆路径问题的常用选择（仓库：google/or-tools）。
HiGHS
高性能开源线性与混合整数规划求解器，支持单纯形法与内点法，可作为商业求解器的替代方案。
Pyomo
Python 代数建模语言，把模型描述与求解器解耦，便于在不同求解器之间切换与做原型验证。
Timefold（原 OptaPlanner）
面向排班与车辆路径的约束求解引擎，内置多种启发式与增量评分机制，适合求解规模较大的排程问题。
SimPy
基于进程的离散事件仿真库，适合构建车间仿真模型，用于方案评估、瓶颈分析与仿真优化。
参考文献
- Google OR-Tools Documentation
- Pinedo M. Scheduling: Theory, Algorithms, and Systems（调度理论与算法系统性教材）
- HiGHS — Linear Optimization Software
- Reinforcement Learning for Combinatorial Optimization: A Survey