3、OHT调度问题建模：将OHT调度抽象为数学优化问题
OHT（Overhead Hoist Transport，空中悬挂式搬运系统）调度问题的核心是在满足晶圆盒搬运请求的前提下，为每台OHT小车规划最优的任务执行序列与路径，使得整体搬运效率最大化。本节将OHT调度抽象为混合整数线性规划（MILP）模型，明确决策变量、目标函数与约束条件，为后续算法求解奠定数学基础。
3.1 问题描述与基本假设
考虑一个典型的300mm晶圆厂洁净车间，OHT系统由以下要素构成：
- 轨道网络：由单向/双向轨道、交叉口、直轨段组成的连通图 G = (V, E)，其中 V 为节点集（含装载口、存储库、交叉点），E 为有向边集。
- OHT小车集合：K = {1, 2, ..., m}，每台小车具有额定速度、空载/负载加速度、最大载重等属性。
- 搬运任务集合：J = {1, 2, ..., n}，每个任务 j 包含起点 s_j、终点 t_j、释放时间 r_j、截止时间 d_j。
基本假设：
- 轨道网络为静态拓扑，不考虑动态故障或临时封锁。
- 每台OHT一次只能搬运一个FOUP（晶圆盒），且搬运过程中不可中途卸载。
- 任务一旦开始执行不可抢占，即OHT必须完成当前任务后才能接受新任务。
- 所有OHT小车同质（速度、加速度一致），或可预先按类型分组。
- 时间离散化为等长时隙（如1秒），便于建模。
3.2 决策变量与参数定义
| 符号 | 类型 | 含义 |
|---|---|---|
| xijk | 二进制 | 1 表示任务 j 紧接在任务 i 之后由小车 k 执行；0 否则 |
| yjk | 二进制 | 1 表示任务 j 分配给小车 k；0 否则 |
| tjkstart | 连续 | 小车 k 开始执行任务 j 的时刻 |
| tjkend | 连续 | 小车 k 完成任务 j 的时刻 |
| τij | 参数 | 从任务 i 终点到任务 j 起点的空载行驶时间 |
| pj | 参数 | 任务 j 的负载行驶时间（从起点到终点） |
| M | 参数 | 足够大的正数（Big-M 法使用） |
3.3 目标函数：最小化加权搬运时间
OHT调度通常采用多目标加权方式，将总搬运时间与任务延迟惩罚统一为标量目标：
Minimize Z = α · Σ_{k∈K} Σ_{j∈J} (t_{jk}^{end} - r_j) + β · Σ_{j∈J} max(0, t_{jk}^{end} - d_j)其中：
- 第一项：总搬运时间（任务完成时刻与释放时刻之差），反映系统响应速度。
- 第二项：总延迟惩罚，鼓励任务在截止时间前完成。
- α, β：权重系数，通常 α=1, β=10~100（延迟惩罚权重更高）。
吞吐量最大化等价形式： 若以最大化单位时间完成任务数为目标，可将目标函数改为 Maximize Σk Σj yjk，并增加时间窗约束确保调度可行性。实际工程中常将吞吐量作为硬约束，搬运时间作为优化目标。
3.4 约束条件体系
OHT调度模型的约束可分为四类：任务分配约束、时间连续性约束、资源冲突约束、路径可行性约束。
3.4.1 任务分配约束
Σ_{k∈K} y_{jk} = 1, ∀j ∈ J (1) 每个任务恰好分配给一台小车
Σ_{j∈J} y_{jk} ≤ C_k, ∀k ∈ K (2) 小车容量约束（C_k 通常为1）
Σ_{i∈J∪{0}} x_{ijk} = y_{jk}, ∀j∈J, k∈K (3) 任务前驱关系
Σ_{j∈J∪{n+1}} x_{ijk} = y_{ik}, ∀i∈J, k∈K (4) 任务后继关系其中虚拟任务 0 表示初始位置，虚拟任务 n+1 表示结束位置。
3.4.2 时间连续性约束
t_{jk}^{start} ≥ r_j, ∀j∈J, k∈K (5) 任务开始时间不早于释放时间
t_{jk}^{end} = t_{jk}^{start} + p_j, ∀j∈J, k∈K (6) 负载行驶时间
t_{ik}^{end} + τ_{ij} ≤ t_{jk}^{start} + M·(1 - x_{ijk}), ∀i,j∈J, k∈K (7) 任务间空载行驶3.4.3 资源冲突约束（轨道段互斥）
Σ_{k∈K} Σ_{j∈J} δ_{jke}^{t} ≤ 1, ∀e∈E, ∀t∈T (8) 同一时刻每段轨道最多一辆OHT其中 δjket 为指示变量，表示小车 k 在时刻 t 是否占用轨道段 e。该约束是模型中最复杂的部分，通常通过时间窗离散化或冲突图方法处理。
3.4.4 路径可行性约束
路径选择变量需满足网络流守恒：
Σ_{v∈V} f_{uv}^{jk} - Σ_{v∈V} f_{vu}^{jk} = b_u^{jk}, ∀u∈V, j∈J, k∈K (9)其中 fuvjk 为流量变量，bujk 为节点供需（起点为1，终点为-1，其余为0）。
工程实践注意： 完整 MILP 模型包含 O(|J|²·|K|·|E|·|T|) 量级的变量和约束，对于实际规模（n=100, m=20, |E|=500, |T|=3600）直接求解不可行。工业界通常采用两阶段法：先通过启发式分配任务，再对每台小车做路径规划。
3.5 OHT调度问题形式化总结
| 维度 | 描述 | 数学表示 |
|---|---|---|
| 输入 | 轨道图、小车集合、任务集合（含时间窗） | G, K, J, rj, dj |
| 决策 | 任务分配、执行顺序、路径选择、开始时间 | xijk, yjk, tjkstart, fuvjk |
| 目标 | 最小化加权搬运时间 + 延迟惩罚 | Min Z = α·Σ(tend-r) + β·Σmax(0, tend-d) |
| 约束 | 分配唯一性、时间连续性、轨道互斥、网络流守恒 | 式 (1)~(9) |
| 复杂度 | NP-hard（强NP难） | 归约于带时间窗车辆路径问题（VRPTW） |
3.6 OHT调度模型结构图
下图展示了OHT调度问题的输入、决策变量、约束与目标之间的逻辑关系：
3.7 模型简化与实用化策略
针对完整MILP模型求解困难的问题，工业界采用以下简化策略：
| 策略 | 方法 | 精度损失 | 求解速度提升 |
|---|---|---|---|
| 时间离散化 | 将连续时间划分为秒级时隙，约束(8)变为整数线性约束 | 低（≤1秒误差） | 10~50倍 |
| 任务聚类 | 将空间邻近的任务合并为批次，减少决策变量数量 | 中（5~10%） | 100~1000倍 |
| 滚动时域 | 仅优化未来T时域内的任务，周期性重规划 | 中（依赖时域长度） | 实时可解 |
| 路径预计算 | 离线计算所有OD对的最短路径，在线只做分配 | 低（忽略动态拥堵） | 10~20倍 |
推荐实践： 在MES（制造执行系统）与OHT控制系统之间建立分层调度架构。上层MES以5~10分钟为周期运行滚动时域MILP，生成任务分配方案；下层OHT控制器以秒级周期执行路径规划与避碰，兼顾全局最优性与实时性。
3.8 本章小结
本章将OHT调度问题严格建模为混合整数线性规划，明确了：
- 决策变量：任务分配、执行顺序、开始时间、路径流量。
- 目标函数：最小化加权搬运时间与延迟惩罚，或最大化吞吐量。
- 约束体系：分配唯一性、时间连续性、轨道互斥、网络流守恒。
- 求解复杂度：NP-hard，需结合离散化、聚类、滚动时域等实用化策略。