钢铁生产流程通常包括原料处理、炼铁、炼钢、连铸、热轧、冷轧等工序。加热炉处于连铸工序和热轧工序之间，起到板坯加热和工序缓冲功能，物流复杂。加热炉板坯输入来源多样，包括：上游的连铸机、保温坑、板坯库，板坯对应有多种加热-运输路径，板坯最早可到达加热炉的时刻不同，运输过程热量损失不同，板坯温度有差异；不同温度和规格的板坯所需加热时长不一样，应尽量减少冷热板坯混装以提高板坯加工质量；加热炉板坯输出去向为下游的热轧机，多个加热炉的整体出坯顺序和节奏需要尽量满足热轧机的连续热轧要求。加热炉能耗高，可优化空间大。对加热炉进行合理的运筹调度，能够降低生产能耗和能源成本，提高板坯加工质量，在整体上进行综合成本优化。面对实际生产过程中存在的不确定性，需进行动态调度来应对调度环境和任务存在不确定扰动，可持续地保证调度方案的可行性、近优性。

当前加热炉相关研究侧重于机器能耗分析、工件加热过程优化、炉温控制^[1-5]，结合连铸-热轧对接需要的加热炉调度研究相对较少。加热炉调度问题属于特殊的混合流水作业问题(flexible flow shop)，衔接连铸工序和热轧工序，具有复杂的工艺约束。其中，混合流水作业问题可描述为：n个工件需要依次经过s个加工阶段，各工件在各加工阶段有若干并行机可选并且需要选择一台并行机进行加工。各加工阶段的工件加工顺序不一定满足先来先服务(first come first served, FCFS)原则^[6]。对于加热炉调度的执行过程，其物流情况如图 1所示，来自上游工序的工件需要先经过选定的并行加热-传输路径进行物流运输或库存缓冲，再经过选定的并行加热炉进行加热或保温，后对接到下游工序。加热-传输路径的选择对工件温度和后续加工情况有较大影响；各加热炉可同时处理多个工件，工件可有序地逐个进入或离开各加热炉。

加热炉调度问题可记作：FFs/Cons/f，FFs为混合流水作业问题，Cons为约束条件(如机器不可用约束：各加热炉在其不可用时段内不能有板坯驻炉)，f为优化目标(如总加工时长)。加热炉系统的构成元素及相互作用情况如图 2所示。

在加热炉调度的相关研究中，宁树实等^[7]考虑板坯加工时长要求和出炉时间间隔约束，最小化板坯达到轧制温度后的驻炉时长，转化为多约束背包问题，设计遗传算法求解；朱柏青等^[8]先进行板坯聚类处理，再考虑板坯装炉重量约束，将板坯装炉问题转化为多背包模型，采用混合蛙跳算法求解；赵珺^[9]假定板坯轧制次序已知，考虑指派约束和冷热板坯装炉要求，最小化板坯加热过程结束的提前/拖后惩罚，构建并行多机提前/拖期调度模型，结合启发规则设计进化算法求解；李铁克等^[10]考虑板坯在加热炉内的先进先出约束和出炉时间间隔要求，最小化最大完工时长和总完工时长的加权和，结合启发式规则(如关键路规则)设计三阶段求解算法来逐步确定板坯排序、加工时长、入炉时刻；丁见亚^[11]考虑加热炉容量约束、冷热混装空炉约束、热轧连续性要求、处于不同加工阶段的板坯决策约束，构建节能调度模型，采用分解优化思路将原问题转化为板坯分配方案决策的主问题和入炉出炉时刻决策子问题进行迭代求解，其中主问题采用变邻域搜索方法求解。

当前关于加热炉调度的研究相对简单，主要侧重于静态调度且考虑的约束条件较少，较少考虑不确定因素的影响、工件加热—传输路径的决策和上下游工序衔接要求，难以满足实际生产需求^[12]。为应对动态事件影响和减少生产中断，有必要进行多类事件建模^[13]和动态调度^[14]，但在加热炉调度中相关研究欠缺。由于加热炉调度问题属于组合优化问题，随着问题规模增加，其解空间呈指数爆炸增长，难以有效求解。已有研究常采用启发式规则或元启发式方法(如变邻域搜索^[11]、遗传算法^{[7, 15-18]}、进化算法^[9]、蚁群算法^[19]、混合蛙跳算法^[8]、多阶段启发式决策^{[10, 20]})进行模型求解，难以控制优化过程和求解效率。

本文主要内容：1) 在建模层面，以板坯总驻炉时长和冷热板坯混装惩罚作为优化目标，考虑实际工艺约束和工序对接要求，采用离散事件点来刻画机器不可用时段与工件加工时段的相对关系并降低变量规模，建立混合整数规划模型。2) 在优化层面，为保证调度结果的实时性和可行性，类比滚动调度的思路对于调度模型进行及时更新、分解与迭代；为平衡求解效率和优化效果，可调整滚动调度范围、衍生影响范围，可尽量复用部分历史决策。3) 建模优化方法相互融合，能适用于加热炉静态调度和动态调度。4) 对于加热炉动态调度，定义动态调度的评价方案，设定常见的动态不确定事件作为测试情景并进行仿真测试。

1 问题描述

在钢铁加热炉系统中，板坯主要来源于上游连铸工序，经过可行的加热-传输路径，送到加热炉中进行加热，再按照一定生产节奏和输出次序对接到下游热轧工序。常用的加热-传输路径包括：

1) 直接热坯装炉轧制(direct hot charge rolling, DHCR)：从上游连铸机出来的板坯直接送入加热炉中进行加热，达到轧制温度后可出炉。此类板坯入炉温度一般为700~1 000 ℃。

2) 热坯装炉轧制(hot charge rolling, HCR)：完成连铸工序的板坯，先进入保温坑中保温和库存缓冲，在合适时段再进入加热炉中加热，达到轧制温度后可出炉。此类板坯入炉温度一般为400~700 ℃。

3) 冷坯装炉轧制(cold charge rolling, CCR)：完成连铸工序的板坯，可送入板坯库中存放，一段时间后再运输到加热炉中加热，达到轧制温度后可出炉。此类板坯温度一般低于400 ℃。

加热炉调度问题可转化为混合整数规划模型(mixed-integer programming, MIP)：对于可调度调整的板坯，需要决策每个板坯的加热-传输路径、加热炉分配情况(离散型决策变量)、入炉时刻、出炉时刻(连续型决策变量)及相关的衍生决策变量，满足约束条件(工艺约束、工序对接约束、取值范围约束、执行进度约束、决策进度约束)，最小化板坯总加热时长和冷热板坯相邻混装惩罚的加权和(可反映板坯加热和保温所需的能源成本、板坯加工质量和不合格产品损失)。其中，对工艺约束和工序对接约束描述如下：

1.1 工艺约束

每个板坯选择一个可行的加热-传输路径和一个会经过的加热炉。

板坯加热时间大于等于其标准加热时间。

各加热炉同时加热的板坯数量不超过额定容量。

各加热炉同时加热的板坯所需加热功率不超过额定峰值功率。

对于步进式加热炉，多个板坯出炉顺序与入炉顺序相同。

各加热炉中相邻板坯入炉时刻的时间间隔不小于对应的相邻入炉最小时间间隔。

在给定加热炉的机器不可用时段内，该加热炉上不能有板坯驻炉。

当前驻炉仍未出炉的板坯的出炉时刻不早于当前时刻。

1.2 工序对接约束

板坯的入炉时刻不早于其上游释放再经过运输的最早可到达加热炉时刻。

板坯的下游轧制顺序预先给定，多个加热炉整体的出坯顺序应与下游轧制顺序一致。

两个相邻板坯的出炉时间间隔不小于单块板坯轧制时长，且不大于单块板坯轧制时长与热轧等待最大时长之和。

2 模型建立

对于加热炉系统调度问题，基于状态参数、决策变量、系统关系和简化假设，可构造数学模型。

2.1 问题参数

$\mathcal{I}$: 加热炉集合。

M: 并行加热炉的数量，即M=|$\mathcal{I}$|。

P_i: 加热炉i∈$\mathcal{I}$的机器不可用时段下标集合，P_i={1, 2, …}(或空集)。

T_ip^M: 加热炉i∈$\mathcal{I}$的第p∈P_i个机器不可用时段的时间长度。

S_ip^M: 加热炉i∈$\mathcal{I}$的第p∈P_i个机器不可用时段(此时工件不能存在机器上)开始时刻。

F_ip^M: 加热炉i∈$\mathcal{I}$的第p∈P_i个机器不可用时段结束时刻。应有：F_ip^M=S_ip^M+T_ip^M。

$\mathcal{J}$: 所有需要加热处理的板坯的集合。该集合中板坯序号j∈$\mathcal{J}$已按照其后道工序所需轧制顺序排序(满足下游工序需求)。假设该集合非空。

N: 加工序列长度，等于集合$\mathcal{J}$中的板坯总数，即：N=|$\mathcal{J}$|。

$\mathcal{J}$^I: 当前驻炉的板坯集合(出炉时刻可小幅度调整，多数决策变量不可调整)。

$\mathcal{J}$^T: 在上游传输路径上(如运输辊道、保温坑、板坯库)待入炉的板坯集合。

$\mathcal{J}$^O: 处于准备阶段尚未出现的板坯集合(需要决策上游传输路径)。

Y_j^P: 0—1型状态参数，表示出现在上游传输路径上待入炉的板坯j∈$\mathcal{J}$^T对应的传输路径P∈{D, H, C}选取情况。当出现在上游传输路径上待入炉的板坯j∈$\mathcal{J}$^T是通过路径P输送至加热炉时为1，否则为0。其中：路径D代表DHCR传输路径，路径H代表HCR传输路径，路径C代表CCR传输路径。通常有：Y_j^D+Y_j^H+Y_j^C=1, ∀j∈$\mathcal{J}$^T。

t_ji^{P, res}、t_ji^{P, rob}、δ_ji^{P, res}、δ_ji^{P, rob}: 连续型状态参数，表示板坯j∈$\mathcal{J}$^T∪$\mathcal{J}$^O通过路径P∈{D, H, C}输送至加热炉i∈$\mathcal{I}$所需剩余运输时长的相关参数。

A_ji^{P, T}: 0—1型状态参数，表示当前待入炉的板坯j∈$\mathcal{J}$^T经过路径P∈{D, H, C}传送到加热炉i∈$\mathcal{I}$的连通情况(可连通传送时取1，否则取0)。

A_ji^{P, O}: 0—1型状态参数，表示当前处于准备阶段尚未出现的板坯j∈$\mathcal{J}$^O通过路径P∈{D, H, C}传送到加热炉i∈$\mathcal{I}$的连通情况。

r_j: 连续型状态参数，表示处于准备阶段的板坯j∈$\mathcal{J}$^O最早出现在上游传输路径时刻。

$\mathcal{J}$^fix: 当前已经决策安排的板坯集合(配合滚动调度过程更新)。

$\mathcal{J}$^dec: 当前需要进行决策安排的板坯集合。

$\mathcal{J}$^eff: 当前决策需要考虑衍生影响的板坯集合。

$\mathcal{J}$^neg: 当前决策暂时忽略且不考虑衍生影响的板坯集合。

E_j: 当前滚动调度阶段板坯j∈$\mathcal{J}$的决策需求存在性(0—1型状态量)，可随着决策过程调整。当板坯j∈$\mathcal{J}$^fix∪$\mathcal{J}$^dec∪$\mathcal{J}$^eff时为1，否则为0。

x_ji⁰、x_ji^{P, 0}、u_jip⁰: 0—1型状态参数，表示当前驻炉的板坯集合$\mathcal{J}$^I已基本固定的决策安排。

s_ji⁰: 连续型状态参数，表示当前驻炉的板坯集合$\mathcal{J}$^I已基本固定的板坯入炉时刻安排情况，即已在第i∈$\mathcal{I}$个加热炉的板坯j∈$\mathcal{J}$^I对应的入炉时刻。

x_ji^fix、x_ji^{P, fix}、u_jip^fix: 0—1型状态参数，表示已经决策安排的板坯集合$\mathcal{J}$^fix的板坯安排情况。

s_ji^fix: 连续型状态参数，表示已经决策安排的板坯集合$\mathcal{J}$^fix的板坯入炉时刻安排情况。

ρ: 目标函数权重系数。

C_jl: 板坯j, l∈$\mathcal{J}$相邻入炉时的惩罚系数(冷热状态板坯交替时惩罚系数较大)。

b_i: 加热炉i∈$\mathcal{I}$的炉容，假定b_i≥1。

a_ji^P: 板坯j∈$\mathcal{J}$通过上游传输路径P∈{D, H, C}运送到加热炉i∈$\mathcal{I}$，在该状态下在加热炉i上的标准(最短)加热时长。

t_j^R: 板坯j∈$\mathcal{J}$在下游热轧工序的轧制时间长度。

δ^R: 相邻板坯轧制之间的最大等待时间长度。

d_jli: 板坯j, l∈$\mathcal{J}$相邻进入同一加热炉i∈$\mathcal{I}$时的最短入炉时间间隔。

τ⁰: 当前时刻。

Q_ji: 板坯j∈$\mathcal{J}$在加热炉i∈$\mathcal{I}$上均匀加热过程单位时间能耗(工件加工功率)大小。

Q_i^m: 加热炉i∈$\mathcal{I}$上单位时间最大总输出功(机器峰值功率)大小，假定Q_i^m≥Q_ij，∀j∈$\mathcal{J}$。

B: 足够大的正数。

ε: 足够小的正数。

2.2 决策变量

x_ji: 0—1变量。当板坯j放置在第i个加热炉时为1，否则为0，其中j∈$\mathcal{J}$, i∈$\mathcal{I}$。

x_ji^P: 0—1变量。当未入炉的板坯j通过上游传输路径P输送至第i个加热炉进行加工时为1，否则为0，其中j∈$\mathcal{J}$^T∪$\mathcal{J}$^O, i∈$\mathcal{I}$, P∈{D, H, C}。当未入炉板坯j通过DHCR路径输送至加热炉i时x_ji^D取1，否则取0；当未入炉板坯j通过HCR路径输送至加热炉i时x_ji^H取1，否则取0；当未入炉板坯j通过CCR路径输送至加热炉i时x_ji^C取1，否则取0。

u_jip: 0—1变量。当第j个工件在炉加工时间段在第i个加热炉的第p个机器维护时间段之后时为1，否则为0，其中j∈$\mathcal{J}$, i∈$\mathcal{I}$, p∈P_i。

v_{j1, j2, i}: 0—1变量。当板坯j₁和j₂均存在且均放置在第i个加热炉上加工且板坯j₂开工时刻在板坯j₁加工时间段内时为1，否则为0，其中j₁, j₂∈$\mathcal{J}$, j₁ < j₂, i∈$\mathcal{I}$。

z_{j1, j2, i}: 0—1变量，此处可松弛为连续型变量。当板坯j₁和j₂分别放置在第i个加热炉中一前一后相邻两个位置时为1，否则为0，其中j₁, j₂∈ $\mathcal{J}$, j₁ < j₂, i∈$\mathcal{I}$。

s_ji: 连续变量。第i个加热炉中板坯j的入炉时刻(如果板坯j没放在该加热炉，则为0)，其中j∈$\mathcal{J}$, i∈$\mathcal{I}$。

f_ji: 连续变量。第i个加热炉中板坯j的出炉时刻(如果板坯j没放在该加热炉，则为0)，其中j∈$\mathcal{J}$, i∈$\mathcal{I}$。

2.3 混合整数规划模型

$ \begin{aligned} \min &\left\{\rho \cdot \sum\limits_{j \in \mathcal{J}} \sum\limits_{i \in \mathcal{I}}\left(f_{j i}-s_{j i}\right)+(1-\rho)\cdot\right. \\ &\left.\sum\limits_{j_{1} \in \mathcal{J}} \sum\limits_{{j}_2 \in \mathcal{J}, j_{2}>j_{1}}\left(C_{j l} \cdot \sum\limits_{i \in \mathcal{I}} z_{j_{1}, j_{2}, i}\right)\right\},\\ &{\rm{subject\ to}} \end{aligned} $

(1)

$ \begin{gathered} s_{j_{2}, i} \leqslant f_{j_{1}, i}-\varepsilon+B \cdot\left(3-v_{j_{1}, j_{2}, i}-x_{j_{1}, i}-x_{j_{2}, i}\right), \\ \forall j_{1}, j_{2} \in \mathcal{J}, j_{1}<j_{2}, \forall i \in \mathcal{I} ; \end{gathered} $

(2)

$ \begin{gathered} s_{j_{2}, i} \geqslant f_{j_{1}, i}-B \cdot v_{j_{1}, j_{2}, i}-B \cdot\left(2-x_{j_{1}}, i-x_{j_{2}, i}\right), \\ \forall j_{1}, j_{2} \in \mathcal{J}, j_{1}<j_{2}, \forall i \in \mathcal{I} ; \end{gathered} $

(3)

$ v_{j_{1}, j_{2}, i} \leqslant x_{j_{1, i}}, \forall j_{1}, j_{2} \in \mathcal{J}, j_{1}<j_{2}, \forall i \in \mathcal{I} ; $

(4)

$ v_{j_{1}, j_{2}, i} \leqslant x_{j_{2}, i}, \forall j_{1}, j_{2} \in \mathcal{J}, j_{1}<j_{2}, \forall i \in \mathcal{I} ; $

(5)

$ \begin{array}{l} 1 + \sum\limits_{{j_1} \in {\cal J},{j_1} < {j_2}} {{v_{{j_1},{j_2},i}}} \le {b_i},\\ \forall {j_2} \in \mathcal{J}\backslash \left\{ 1 \right\},\forall i \in \mathcal{I}; \end{array} $

(6)

$ \begin{gathered} 1+\sum\limits_{j_{1} \in \mathcal{J}, j_{1}<j_{2}} v_{j_{1}, j_{2}, i} \leqslant b_{i}, \\ \forall j_{2} \in \mathcal{J} \backslash\{1\}, \forall i \in \mathcal{I}; \end{gathered} $

(7)

$ \begin{gathered} Q_{j_{2}, i}+\sum\limits_{j_{1} \in \mathcal{J}, j_{1}<j_{2}} Q_{j_{1}, i} \cdot v_{j_{1}, j_{2}, i} \leqslant Q_{i}^{m}, \\ \forall j_{2} \in \mathcal{J} \backslash\{1\}, \forall i \in \mathcal{I}; \end{gathered} $

(8)

$ \begin{gathered} f_{j i}-s_{j i} \geqslant \sum\limits_{P \in\{\mathrm{D}, \mathrm{H}, \mathrm{C}\}} a_{j i}^{P} x_{j i}^{P}, \\ \forall j \in \mathcal{J}, \forall i \in \mathcal{I}; \end{gathered} $

(9)

$ \begin{gathered} f_{j i} \leqslant B \cdot\left(1-x_{j i}+u_{j i p}\right)+S_{i p}^{\mathrm{M}}, \\ \forall j \in \mathcal{J}, \forall i \in \mathcal{I}, \forall p \in P_{i}; \end{gathered} $

(10)

$ \begin{gathered} u_{j_{1}, i, p} \leqslant u_{j_{2}, i, p}+\left(2-x_{j_{1}, i}-x_{j_{2}, i}\right), \\ \forall j_{1}, j_{2} \in \mathcal{J}, j_{1}<j_{2}, \forall i \in \mathcal{I}, \forall p \in P_{i} ; \end{gathered} $

(11)

$ \begin{gathered} u_{j, i, p_{1}} \geqslant u_{j, i, p_{2}}+\left(x_{j, i}-1\right), \forall j \in \mathcal{J} ,\\ \forall i \in \mathcal{I}, \forall p_{1}, p_{2} \in P_{i}, F_{i, p_{1}}^{\mathrm{M}} \leqslant S_{i, p_{2}}^{\mathrm{M}}; \end{gathered} $

(12)

$ \begin{gathered} z_{j_{1}, j_{2}, i} \geqslant 1-\sum\limits_{j=j_{1}+1}^{j_2-1} x_{j i}-\left(2-x_{j_{1}, i}-x_{j_{2}, i}\right) ,\\ \forall j_{1}, j_{2} \in \mathcal{J}, j_{1}<j_{2}, \forall i \in \mathcal{I} ; \end{gathered} $

(13)

$ z_{j_{1}, j_{2}, i} \leqslant 1, \forall j_{1}, j_{2} \in \mathcal{J}, j_{1}<j_{2}, \forall i \in \mathcal{I} $

(14)

$ \begin{gathered} s_{j_{2}, i}-s_{j_{1}, i} \geqslant-B \cdot\left(2-x_{j_{1}, i}-x_{j_{2}, i}+\sum\limits_{j=j_{1}+1}^{j_{2}-1} x_{j i}\right)+ \\ d_{j_{1}, j_{2}, i}, \forall j_{1}, j_{2} \in \mathcal{J}, j_{1}<j_{2}, \forall i \in \mathcal{I}; \end{gathered} $

(15)

$ \begin{gathered} f_{j_{2}, i}-f_{j_{1}, i} \geqslant-B \cdot\left(2-x_{j_{1}, i}-x_{j_{2}, i}\right), \\ \forall j_{1}, j_{2} \in \mathcal{J}, j_{1}<j_{2}, \forall i \in \mathcal{I}; \end{gathered} $

(16)

$ \begin{gathered} \sum\limits_{i \in \mathcal{I}}\left(f_{j i}-f_{j-1, i}\right) \geqslant t_{j-1}^{\mathrm{R}}- \\ B \cdot\left(2-E_{j}-E_{j-1}\right), \forall j \in \mathcal{J} \backslash\{1\}; \end{gathered} $

(17)

$ \begin{gathered} \sum\limits_{i \in \mathcal{I}}\left(f_{j i}-f_{j-1, i}\right) \leqslant t_{j-1}^{\mathrm{R}}+\delta^{R}+ \\ B \cdot\left(2-E_{j}-E_{j-1}\right), \forall j \in \mathcal{J} \backslash\{1\}; \end{gathered} $

(18)

$ \sum\limits_{i \in \mathcal{I}} x_{j i}=1 \cdot E_{j}, \forall j \in \mathcal{J} ; $

(19)

$ s_{j i} \leqslant B \cdot x_{j i}, \forall j \in \mathcal{J}, \forall i \in \mathcal{I} ; $

(20)

$ f_{j i} \leqslant B \cdot x_{j i}, \forall j \in \mathcal{J}, \forall i \in \mathcal{I} ; $

(21)

$ x_{j i}=x_{j i}^{0}, \forall j \in \mathcal{J}^{\mathrm{I}} ; $

(22)

$ x_{j i}^{P}=x_{j i}^{P, 0}, \forall j \in \mathcal{J}^{\mathrm{I}}, \forall P \in\{\mathrm{D}, \mathrm{H}, \mathrm{C}\} ; $

(23)

$ u_{j i p}=u_{j i p}^{0}, \forall j \in \mathcal{J}^{\mathrm{I}}, \forall i \in \mathcal{I}, \forall p \in P_{i}; $

(24)

$ s_{j i}=s_{j i}^{0}, \forall j \in \mathcal{J}^{\mathrm{I}} ; $

(25)

$ \sum\limits_{i \in \mathcal{I}} f_{j i} \geqslant \tau^{0}, \forall j \in \mathcal{J}^{\mathrm{I}} ; $

(26)

$ \begin{gathered} \sum\limits_{i \in \mathcal{I}} x_{j i}^{P}=Y_{j}^{P} \cdot E_{j}, \\ \forall j \in \mathcal{J}^{\mathrm{T}}, \forall P \in\{\mathrm{D}, \mathrm{H}, \mathrm{C}\}; \end{gathered} $

(27)

$ \begin{gathered} x_{j i}^{P} \leqslant A_{j i}^{P, \mathrm{~T}}, \forall j \in \mathcal{J}^{\mathrm{T}}, \\ \forall i \in \mathcal{I}, \forall P \in\{\mathrm{D}, \mathrm{H}, \mathrm{C}\}; \end{gathered} $

(28)

$ \begin{gathered} s_{j i} \geqslant \tau^{0} \cdot x_{j i}+\sum\limits_{P \in\{\mathrm{D}, \mathrm{H}, \mathrm{C}\}} t_{j i}^{\mathrm{P}, \mathrm{res}} \cdot x_{j i}^{P}, \\ \forall j \in \mathcal{J}^{\mathrm{T}}, \forall i \in \mathcal{I} ; \end{gathered} $

(29)

$ \begin{gathered} s_{j i} \leqslant \tau^{0} \cdot x_{j i}+\sum\limits_{P \in\{\mathrm{D}, \mathrm{H}, \mathrm{C}\}}\left(t_{j i}^{P, \mathrm{res}}+\delta_{j i}^{P, \mathrm{res}}\right) \cdot x_{j i}^{P}, \\ \forall j \in \mathcal{J}^{\mathrm{T}}, \forall i \in \mathcal{I}; \end{gathered} $

(30)

$ \sum\limits_{P \in\{\mathrm{D}, \mathrm{H}, \mathrm{C}\}} x_{j i}^{P}=x_{j i}, \forall j \in \mathcal{J}^{\mathrm{O}}, \forall i \in \mathcal{I}; $

(31)

$ \begin{gathered} x_{j i}^{P} \leqslant A_{j i}^{P, \mathrm{O}}, \forall j \in \mathcal{J}^{\mathrm{O}}, \\ \forall i \in \mathcal{I}, \forall P \in\{\mathrm{D}, \mathrm{H}, \mathrm{C}\}; \end{gathered} $

(32)

$ \begin{gathered} s_{j i} \geqslant r_{j} \cdot x_{j i}+\sum\limits_{P \in\{\mathrm{D}, \mathrm{H}, \mathrm{C}\}} t_{j i}^{{P}, \mathrm{rob}} \cdot x_{j i}^{P}, \\ \forall j \in \mathcal{J}^{\mathrm{O}}, \forall i \in \mathcal{I}; \end{gathered} $

(33)

$ \begin{gathered} s_{j i} \leqslant r_{j} \cdot x_{j i}+\sum\limits_{P \in\{\mathrm{D}, \mathrm{H}, \mathrm{C}\}}\left(t_{j i}^{P, \mathrm{rob}}+\delta_{j i}^{P, \mathrm{rob}}\right) \cdot x_{j i}^{P}, \\ \forall j \in \mathcal{J}^{\mathrm{O}}, \forall i \in \mathcal{I}; \end{gathered} $

(34)

$ x_{j i}=x_{j i}^{\mathrm{fix}}, \forall j \in \mathcal{J}^{\text {fix }}, \forall i \in \mathcal{I}; $

(35)

$ \begin{gathered} x_{j i}^{P}=x_{j i}^{P, \text { fix }}, \forall j \in \mathcal{J}^{\text {fix }} \text {, }\\ \forall i \in \mathcal{I}, \forall P \in\{\mathrm{D}, \mathrm{H}, \mathrm{C}\}; \end{gathered} $

(36)

$ u_{j i p}=u_{j i p}^{\mathrm{fix}}, \forall j \in \mathcal{J}^{\mathrm{fix}}, \forall i \in \mathcal{I}, \forall p \in P_{i} ; $

(37)

$ \begin{gathered} z_{j_{1}, j_{2}, i}=x_{j_{1}, i}^{\text {fix }} \cdot x_{j_{2}, i}^{\text {fix }} \cdot I\left(\sum\limits_{j=j_{1}+1}^{j_{2}-1} x_{j i}^{\text {fix }}=0\right), \\ \forall j_{1}, j_{2} \in \mathcal{J}^{\text {fix }}, j_{1}<j_{2}, \forall i \in \mathcal{I}; \end{gathered} $

(38)

$ s_{j i}=s_{j i}^{\mathrm{fix}}, \forall j \in \mathcal{J}^{\text {fix }}, \forall i \in \mathcal{I} ; $

(39)

$ x_{j i}=0, \forall j \in \mathcal{J}^{\mathrm{neg}} ; $

(40)

$ \begin{gathered} x_{j i}^{P}=0, \forall j \in \mathcal{J}^{\mathrm{neg}}, \\ \forall i \in \mathcal{I}, \forall P \in\{\mathrm{D}, \mathrm{H}, \mathrm{C}\}; \end{gathered} $

(41)

$ u_{j i p}=0, \forall j \in \mathcal{J}^{\mathrm{neg}}, \forall i \in \mathcal{I}, \forall p \in P_{i}; $

(42)

$ \begin{gathered} z_{j l i}=0, \forall j \in \mathcal{J}^{\text {neg }}, \forall l \in \mathcal{J}, \forall i \in \mathcal{I} \text { or } \\ \forall l \in \mathcal{J}^{\text {neg }}, \forall j \in \mathcal{J}, \forall i \in \mathcal{I} ; \end{gathered} $

(43)

$ s_{j i}=0, \forall j \in \mathcal{J}^{\mathrm{neg}}, \forall i \in \mathcal{I} ; $

(44)

$ f_{j i}=0, \forall j \in \mathcal{J}^{\mathrm{neg}}, \forall i \in \mathcal{I} ; $

(45)

$ x_{j i} \in\{0,1\}, \forall j \in \mathcal{J}, \forall i \in \mathcal{I} ; $

(46)

$ \begin{array}{c} x_{j i}^{P} \in\{0,1\}, \forall j \in \mathcal{J}, \\ \forall i \in \mathcal{I}, \forall P \in\{\mathrm{D}, \mathrm{H}, \mathrm{C}\} ; \end{array} $

(47)

$ u_{j i p} \in\{0,1\}, \forall j \in \mathcal{J}, \forall i \in \mathcal{I}, \forall p \in P_{i} ; $

(48)

$ \begin{gathered} v_{j_{1}, j_{2}, i} \in\{0,1\}, \forall j_{1}, \\ j_{2} \in \mathcal{J}, j_{1}<j_{2}, \forall i \in \mathcal{I} ; \end{gathered} $

(49)

$ z_{j_{1}, j_{2}, i} \geqslant 0, \forall j_{1}, j_{2} \in \mathcal{J}, j_{1}<j_{2}, \forall i \in \mathcal{I} ; $

(50)

$ s_{j i}, f_{j i} \geqslant 0, \forall j \in \mathcal{J}, \forall i \in \mathcal{I}. $

(51)

目标函数式(1)表示要最小化板坯总加热时长和冷热板坯相邻混装惩罚的加权和。约束函数式(2)—(12)为工艺约束，其中：式(2)—(6)为加热炉的炉容约束，式(7)为加热炉加热功率约束，式(8)为板坯加热时长约束，式(9)—(12)为板坯加热时段与机器不可用时段相互错开的约束。约束函数式(13)—(14)为优化目标关联约束，用于判定2个板坯是否在同一加热炉一前一后相邻两个位置上。约束函数式(15)—(21)为输入输出对接约束，其中：式(15)—(16)为同一加热炉中相邻板坯入炉时空间隔要求和板坯先进先出约束，式(17)—(18)为输出板坯需要满足下游轧制的顺序要求和轧制无间断约束，式(19)为板坯指派约束，每个板坯会被安排到唯一的加热炉进行加工，式(20)—(21)表示当板坯未分配到某加热炉时对应的时空分支进程不演化，便于核算板坯的实际加工时长。约束函数式(22)—(34)为执行进度约束，其中：式(22)—(25)表示对当前处于驻炉状态的板坯进行已有决策固定，式(26)表示当前处于驻炉状态未完工的板坯对应的出炉时刻会晚于当前时刻，式(27)—(30)表示当前已经出现在加热-传输路径上待入炉的板坯的对接安排，式(31)—(34)表示当前处于上游准备阶段尚未出现的板坯需要进行加热—传输路径决策和入炉安排。约束函数式(35)—(45)为决策进度约束，逐阶段更新决策参数，逐步固定和求解决策变量，其中：式(38)中I为示性函数。约束函数式(46)—(51)为决策变量的取值范围约束。

可根据实际需要进一步调整模型，如局部调整优化目标、约束条件和引入衍生参数。特别地，可针对事先选定的不确定参数进行不确定优化(如随机规划、鲁棒优化)，构建的不确定优化调度模型在近似简化后通常可转化为确定性调度模型，进而可采用设计的调度机制进行模型求解，能够生成对于不确定参数的实际波动具有一定抗干扰能力(如鲁棒性)的调度方案。

3 模型求解

对于静态调度和动态调度采用一致的模型求解方法：首先更新模型参数；再确定需要调度的工件集合；然后按照滚动调度的思路对模型的问题域进行分解并生成子问题，分阶段迭代求解子问题；更新模型求解完成后，输出调度方案。其中，在求解子问题时，可采用分支-定界法(branch and bound)对于小规模的混合整数规划模型进行有效求解。分支是将全部可行解空间反复分割为越来越小的子集；定界是对每个子集内的解集计算一个目标下界(针对最小值问题)。在每次分支后，对于目标下界超出已知可行解集目标值的那些子集不再进一步分支。

为提升优化效果，在滚动搜索域中设置了滚动优化范围和衍生影响范围。滚动优化范围和衍生影响范围的工件对应的决策变量需要满足约束条件，处于滚动搜索域前方的已有决策范围的工件对应的主要决策变量取值固定为历史决策值，处于滚动搜索域后方的暂时忽略范围的工件对应的主要决策变量取值固定为给定的合理初始值。求解当前子问题后，当前滚动优化范围内工件的主要决策变量取值记录并固定，衍生影响范围内工件的决策结果不记录。

为便于切入理解，进行关键机制的可视化：决策流程如图 3所示，滚动调度机制如图 4所示。

4 算法步骤

对于较大规模的静态调度问题，采用启发式排序规则进行决策变量的预处理和分组，使用滚动调度思路进行问题分解和迭代；对于较大规模的动态调度问题，考虑对于已有决策结果进行参考和复用，减少已有决策结果的变更，并提升更新问题的求解效率。其中，滚动调度是依据时间先后顺序和滚动窗口把调度过程划分为若干连续的调度区间，对于每个调度区间可基于已有决策结果和更新的模型进行迭代决策。

4.1 静态调度求解算法

基于调度系统整体状态量(包括问题参数、调度执行进度)集合S和所需调度决策变量(主要是0—1离散型决策变量)集合X、调度问题内在规律和简化假设，可构建调度问题对应的数学模型m(X|S)=min{f(X, S)|X∈Ω(S)}。其中f (X, S)为优化目标，Ω(S)为问题可行域。假设数学模型m(X|S) 有可行满意解(可通过实际计算检验)，否则需要调整调度需求。

当决策变量集合X规模较小时，直接使用求解器(或分支定界法)来求解数学模型m(X|S)得到可行满意解(X^*|S)；当决策量集合X规模较大时，为提升求解效率，设计启发式求解算法如图 5所示。

4.2 动态调度求解算法

给定t时段的调度问题，基于t时段系统状态量集合S_t和所需调度决策变量集合X_t、调度问题内在规律和简化假设，构建数学模型m(X_t|S_t)。假设数学模型m(X_t|S_t)有可行满意解(可计算检验)，那么可使用设计的静态调度求解算法给出可行满意解(X_t^*|S_t)；否则需要调整调度需求。

假设在(t+1)时段调度问题发生动态调整，基于(t+1)时段系统状态量集合S_t+1和所需调度决策变量集合X_t+1及参数关系，可构建更新的数学模型m(X_t+1|S_t+1)。假设数学模型m(X_t+1|S_t+1)有可行满意解(可计算检验)，那么可使用设计的静态调度求解算法给出更新的可行满意解(X_t+1^*|S_t+1)；否则需要调整调度需求。

为了减少已有决策方案(X_t^*|S_t)的变更，并提升更新的数学模型m(X_t+1|S_t+1)的求解效率，考虑尽可能地对于已有决策方案(X_t^*|S_t)进行参考和复用(逐步缩小历史决策复用范围，直至找到可行满意解)，设计启发式算法如图 6所示。

5 仿真测试

设置合理参数，进行建模优化，给出仿真结果。对于加热炉静态调度问题，使用不同求解方式进行测试对比；对于加热炉动态调度问题，设置多类不确定事件发生情景和不同求解方式进行测试对比。

5.1 数据来源和参数设置

仿真数据设定参考某钢铁企业的生产数据。仿真实验统一设定5个并行加热炉，板坯数量默认为20；设定CPLEX直接求解时间上限为300 s；设定静态调度求解算法子问题求解时间上限为30 s；设定动态调度求解算法子问题求解时间上限为20 s。

5.2 静态调度的实验仿真和结果分析

可使用商业求解器CPLEX直接求解加热炉调度对应的混合整数规划模型，或使用设计的静态调度求解算法更高效地求解数学模型。在模型有可行解的情况下，模型求解后能得到各板坯的上游传输路径安排情况和加热炉组分配情况，如图 7所示。

由加热炉静态调度的仿真结果(见表 1)可以看出：相对于使用CPLEX直接求解，使用设计的静态调度求解算法能够在明显较短的求解时间内给出满意解且所得解通常更优。

不同规模板坯的调度情况如图 8所示，可以看出：随着所需调度的板坯数量增加，优化目标值逐步增大，问题求解时长也逐步增加。设计的静态调度求解算法在限定的求解时间内通常有更优解，且求解时长随问题规模增加近似呈线性增加。

5.3 动态调度的实验仿真和结果分析

在实际作业过程中，出现动态不确定事件是正常现象。主要的不确定事件包括：生产执行进度波动(如工件最早可加工时刻变化、工件所需加工时长变化、机器不可用时段波动)、加工需求变更(如订单变更、紧急插单、工件取消)、机器不可用时段分布变化(如机器故障、紧急停机、停炉检修)。为进行动态调度可行性验证，考虑设定若干常见的动态不确定事件进行单独测试及联合测试。

5.3.1 仿真测试情景1：生产进度波动

在测试中，假设相对于t时段调度问题，(t+1) 时段的调度问题出现生产执行进度相关参数(如工件最早可达时刻、工件最短加工时长、机器不可用时段)的波动变化，假定参数波动范围为-5%~5%。

5.3.2 仿真测试情景2：加工需求变更

假设(t+1)时段的调度问题出现加工需求变更：2个未驻炉板坯的加工需求取消，3个未驻炉板坯的加工需求改变，增加7个新的板坯加工需求。

5.3.3 仿真测试情景3：机器状态变更

假设(t+1)时段的调度问题出现机器状态变更：假设第1台加热炉增加了一个不可用时段，第3、4、5台加热炉有不可用时段发生变化。

5.3.4 仿真测试情景4：多类不确定事件复合

假设(t+1)时段的调度问题出现多类不确定事件：生产进度波动、加工需求变更、机器状态变更。动态事件设置为前三类测试情景的叠加。

5.3.5 动态调度的方案评价

对动态调度生成的调度方案有如下评价指标：更新的调度方案相对于原有调度方案的变更程度(越少越好)、更新模型的最小化目标值(越小越好)、求解时长(越短越好)。为了量化表示更新的调度方案相对于原有调度方案的变更程度，定义“调度方案差异度”作为刻画指标，定义过程如下：

给定t时段的调度问题，基于t时段系统状态量集合S_t和所需调度决策变量(主要是0-1离散型决策变量)集合X_t，构建数学模型m(X_t|S_t)。假设数学模型m(X_t|S_t)有可行满意解(可通过实际计算检验)，通过求解算法给出求解结果(X_t^*|S_t)。

同理，对(t+1)时段，系统状态量集合记作S_t+1，调度的主要决策变量集合记作X_t+1，数学模型记作m(X_t+1|S_t+1)。假设数学模型m(X_t+1|S_t+1)有可行满意解，通过求解算法给出求解结果(X_t+1^*|S_t+1)。

记集合X_t与集合X_t+1中相同元素构成的集合为M_t：M_t=X_t∩X_t+1。记M_t中决策变量对应于t时段调度结果(X_t^*|S_t)的实际取值为(M_t^*|S_t)；记M_t中决策变量对应于(t+1)时段调度结果(X_t+1^*|S_t+1)的实际取值为(M_t^*|S_t+1)。

定义t时段调度结果(X_t^*|S_t)与(t+1)时段调度结果(X_t+1^*|S_t+1)之间的“调度方案差异度”为：‖(M_t^*|S_t+1)－(M_t^*|S_t)‖₁。

由定义可知，“调度方案差异度”越小，则更新的调度方案相对于原有调度方案在共有决策域M_t上变更程度越小。

5.3.6 动态调度的仿真结果

由不同测试情景下的加热炉动态调度仿真结果(见表 2)可以看出：使用CPLEX直接求解更新的数学模型，所得更新的调度方案与原有调度方案的差异度较大，求解时间较长，在给定求解时间内所得解的优化程度通常较低；相对于CPLEX求解结果，使用设计的静态调度求解算法，所得的调度方案与原有调度方案的差异度更小，求解时间更短，所得解的优化程度较高；相对于前两类求解方式，使用设计的动态调度求解算法，所得的调度方案与原有调度方案的差异度通常最小，求解时间最短，所得解的优化程度通常最高。

对于加热炉动态调度，在更新模型有可行解的情况下，使用设计的动态调度求解算法能够在短时间内给出优化程度高的满意解。

6 结论

本文针对加热炉调度问题，考虑了机器不可用约束、多加热炉指派决策、板坯的上游传输路径决策、板坯的下游热轧衔接约束，以最小化板坯总加热时长和冷热板坯相邻混装惩罚的加权和为优化目标，建立混合整数规划模型。采用滚动调度思路对于加热炉静态调度问题进行有效求解，尽量复用已有决策结果来提升加热炉动态调度问题的求解效率并减少已有调度方案变更。仿真结果验证了模型和算法的有效性。