1.   炼钢-连铸生产重调度问题描述

炼钢-连铸生产过程是现代钢铁企业生产流程中的核心环节, 其生产过程是将液态的高温铁水经过转炉冶炼、精炼炉精炼和连铸机浇铸等三大工序的处理形成最终的固态板坯.首先, 高炉产出的高温铁水通过鱼雷车载运铁水到炼铁厂, 倒入转炉并加入废钢进行吹炼, 把高温条件下的铁水进一步冶炼为含碳量更低的钢水.其次, 转炉产出的钢水倒入钢包并由天车和台车运送到相应的精炼设备调整钢水成分和温度, 进行深脱碳、去硫和去除杂质等处理, 由普通的钢水变成优质钢水.最后, 钢水由台车和行车吊运到指定的连铸机并通过钢包的下水口注入中间包, 通过中间包不断进入结晶器振动冷却后形成板坯.图 1所示为中国某炼钢厂的生产工艺过程, 该生产包括5个加工设备组, 即转炉LD加工设备组、真空循环脱气法精炼炉(Ruhrstahl Heraeus process, RH)加工设备组、粗真空钢包精炼设备(Ladle furnace process, LF)加工设备组、喷吹精炼炉(Injection refining with temperature raising capability, IR-UT)加工设备组和连铸机设备组(Continuous caster, CC), 每个加工设备组均有多台功能相同的加工设备.在炼钢-连铸生产过程中, 钢水的钢种决定了其生产工艺路线.图 1所示是较为主要的三种钢水的生产工艺路线, 均按照1→2→3→4→5的顺序进行加工.图 1(c)生产工艺路线中的2和4经过的加工设备组相同, 其生产工艺路线属于可重入生产线^[20], 这种可重入生产线使得每台RH设备需要加工的钢水数量大幅增加, 增加了钢水在RH设备上的竞争程度, 加大了生产调度的复杂性和调度计划编制的难度.图 1所示包含三种生产工艺路线的调度问题不同于job shop/flow shop/柔性job shop/混合flow shop等调度问题, 是一类特殊的复杂生产调度问题.

图 1  中国某炼钢厂的生产工艺过程

Fig. 1  Production process of steelmaking and continuous casting

下载: 全尺寸图片 幻灯片

在炼钢-连铸生产过程中, 一台转炉内冶炼的一炉钢水, 冶炼后被倒入一个钢包中, 经钢包载运到精炼设备进行精炼, 然后经钢包载运到连铸机进行浇铸.该炉钢水的整个生产过程称之为一个炉次.同一炉次中的钢水具有相同的钢水等级, 且钢水等级决定了炉次的精炼方式.炉次在一个阶段上的一次加工称为炉次的一个操作, 其为炼钢-连铸生产过程中的最小加工单元.在一台连铸机上按照工艺约束不间断连续浇铸的一批炉次的一个有序集合称之为一个浇次.炼钢-连铸生产调度的任务是为每个炉次在每个阶段的加工选择一台加工设备, 并且确定其在加工设备上的开工时间和完工时间.图 2所示为3个炉次的炼钢-连铸生产调度计划甘特图, 纵轴为设备列表, 横轴是时间坐标轴, 每个长方形长度代表炉次在设备上的处理时间长度.该生产调度计划包含3个炉次, 即炉次1、炉次2和炉次3, 且这3个炉次在连铸机上连续浇铸构成一个浇次.每个炉次均经过1LD、1RH、1LF和1CC 4个阶段的加工, 即每个炉次包括4个操作.在进行炼钢-连铸生产调度计划编制时, 同一浇次中相邻炉次在连铸机上必须连续浇铸, 炉次的各个操作必须按照生产工艺路径规定的先后顺序依次进行加工, 同一台设备上加工的相邻操作之间不能出现作业时间冲突, 并且炉次在设备上的处理时间不能小于设备最小处理时间, 也不能大于设备最大处理时间.

图 2  炼钢–连铸生产调度计划甘特图

Fig. 2  Gantt graph of production plan

下载: 全尺寸图片 幻灯片

在炼钢-连铸生产过程中, 转炉冶炼时所需的铁水原料是从高炉冶炼得到的铁水经过混铁车运输到炼钢厂后倒入铁水包, 再从铁水包中倒入转炉中得到的.在混铁车运输铁水过程中, 铁水需要经过前扒渣、脱硫、后扒渣等工艺处理.在此过程中, 由于操作工人的熟练程度、环境参数等随机因素的影响, 使得到达炼钢厂的铁水倒入转炉进行冶炼的开始时间晚于炼钢-连铸生产调度计划中的炉次开始时间, 从而使得炉次在转炉上出现开工时间延迟, 导致初始调度计划发生连铸断浇或者炉次作业时间冲突而无法执行.本文研究的重调度问题就是当某个炉次在转炉的开工时间发生延迟导致初始调度计划发生连铸断浇或者炉次作业时间冲突时, 根据初始调度计划的执行情况, 对初始调度计划中还未完工的炉次进行调整, 保证调度计划的可行性.

重调度时的已知信息包括: 1) 初始调度计划中浇次个数, 以及每个浇次所在的连铸机; 2) 初始调度计划中每个浇次包含的炉次数, 以及这些炉次在浇次内的先后加工顺序; 3) 初始调度计划中每个炉次的操作总数, 以及每个操作的加工设备类型; 4) 初始调度计划中每个操作的加工设备, 以及在设备上的开工时间和完工时间; 5) 每类设备的最小处理时间、标准处理时间和最大处理时间; 6) 设备之间的运输时间; 7) 操作在设备上的加工状态:包括已完工、正在加工和未开工; 8) 在转炉上发生开工时间延迟的操作, 以及该操作在转炉设备上的实际开工时间.

重调度时需要考虑的因素包括: 1) 已完工操作或者正在加工操作的加工设备在重调度时不能进行改变; 2) 已完工操作或者正在加工操作的开工时间在重调度时不能进行改变; 3) 已完工操作的完工时间在重调度时不能进行改变; 4) 操作必须在指定设备类型的设备上加工; 5) 未开工操作的开工时间和完工时间, 以及正在加工操作的完工时间必须大于重调度时刻.

2.   炼钢-连铸生产重调度问题建模

2.1   符号和参数定义

$i$ :浇次序号, $i=1, 2, \cdots, N$ , $N$ 为浇次总个数;

$j$ :炉次序号, $j=1, 2, \cdots, S_{i}$ ,

$S_{i}$ 为第 $i$ 个浇次的炉次总个数;

$L_{ij}$ :第 $i$ 个浇次中在连铸机上第 $j$ 个浇铸的炉次, $i=1, 2, \cdots, N$ , $j=1, 2, \cdots, S_{i}$ ;

$k$ :操作序号, $k=1, 2, \cdots, \varepsilon_{ij}$ , $\varepsilon_{ij}$ 为第 $i$ 个浇次中在连铸机上第 $j$ 个浇铸的炉次的操作总个数;

$o_{ijk}$ :第 $i$ 个浇次中在连铸机上第 $j$ 个浇铸的炉次的第 $k$ 个加工的操作, $i=1, 2, \cdots, N$ , $j=1, 2, \cdots, S_{i}$ , $k=1, 2, \cdots, \varepsilon_{ij}$ ;

$L_{i^{\ast}j^{\ast}}$ :发生转炉开工时间延迟的炉次;

$\Omega^{0}$ :初始调度计划中的所有炉次集合;

$\Omega$ :连铸机上未完工的所有炉次集合, 为重调度的炉次对象;

$\Pi$ :所有设备集合, $\Pi=\{1, 2, \cdots, M\}$ ;

$m$ :设备序号, $m\in\Pi$ ;

$g$ :设备类型, $g=1, 2, \cdots, G$ , $G$ 为设备类型的总个数;

$\Pi_{g}$ :类型 $g$ 的所有设备集合,

$|\Pi_{g}|$ 表示类型 $g$ 的设备总个数;

$p_{ijk}^{U}$ :第 $i$ 个浇次的第 $j$ 个炉次的第 $k$ 个操作的最大处理时间;

$p_{ijk}^{B}$ :第 $i$ 个浇次的第 $j$ 个炉次的第 $k$ 个操作的理想处理时间;

$p_{ijk}^{L}$ :第 $i$ 个浇次的第 $j$ 个炉次的第 $k$ 个操作的最小处理时间;

$T_{ml}$ :设备 $m$ 与设备 $l$ 之间的运输时间, $m, l\in\Pi$ ;

$\beta_{ijk}$ :第 $i$ 个浇次的第 $j$ 个炉次的第 $k$ 个操作的加工状态; $\beta_{ijk}=0$ 表示操作为未开工状态, $\beta_{ijk}=1$ 表示操作为正在加工状态, $\beta_{ijk}=2$ 表示操作为已完工状态;

$t_{r}$ :扰动事件发生后的重调度开始时间;

$\sigma_{ijk}^{0}$ :初始调度计划中第 $i$ 个浇次的第 $j$ 个炉次的第 $k$ 个操作的加工设备类型, $\sigma_{ijk}^{0}\in\{1, 2, \cdots, G\}$ ;

$s_{ijk}^{0}$ :初始调度计划中第 $i$ 个浇次的第 $j$ 个炉次的第 $k$ 个操作的开工时间;

$e_{ijk}^{0}$ :初始调度计划中第 $i$ 个浇次的第 $j$ 个炉次的第 $k$ 个操作的完工时间;

$m_{ijk}^{0}$ :初始调度计划中第 $i$ 个浇次的第 $j$ 个炉次的第 $k$ 个操作的加工设备;

$s_{ijk}^{\ast}$ :初始调度计划中第 $i$ 个浇次的第 $j$ 个炉次的第 $k$ 个操作的实际开工时间.

2.2   决策变量

$x_{ijk}$ :第 $i$ 个浇次的第 $j$ 个炉次的第 $k$ 个操作的开工时间, 为整数变量, $L_{ij}\in\Omega$ ;

$y_{ijk}$ :第 $i$ 个浇次的第 $j$ 个炉次的第 $k$ 个操作的完工时间, 为整数变量, $L_{ij}\in\Omega$ ;

2.3   优化目标

钢水温度是炼钢过程中需要重点控制的工艺参数之一, 对保证连铸生产过程顺利进行、降低原材料和能量消耗、提高铸坯质量均有很大影响.若钢水温度过低则需要通过延长钢水在原精炼设备上的处理时间, 甚至是增加精炼设备来进行升温处理, 从而会增加能耗和物耗, 加长生产周期, 严重影响生产效率.所以在对重调度炉次集合 $\Omega$ 中的炉次进行重调度时必须严格控制炉次在炼钢-连铸生产过程中各工序间的等待时间, 使其要尽量的小.即重调度过程中对 $\Omega$ 中的炉次 $L_{ij}$ 在阶段 $k$ 的开工时间 $x_{ijk}$ 与在阶段 $k-1$ 的完工时间 $y_{i, j, k-1}$ , 以及设备间运输时间 $T_{m_{i, j, k-1}, m_{ijk}}$ 的差值尽量最小, 即建立如下性能指标:

2.4   约束方程

1)  同一浇次内炉次必须按照浇铸顺序在连铸机上满足连续浇铸

对于连铸机来说, 每开启一次需要支出电费、设备调整时间和工具(结晶器、中间包)消耗和辅助材料消耗, 成本很高, 这就需要有更多的炉次在同一连铸机上连续浇铸, 以降低总成本费用.因此, 为了满足同一浇次内炉次在连铸机上连续浇铸, 必须保证 $\Omega$ 中的炉次 $L_{ij}$ 在连铸机上的开工时间 $x_{i, j, \varepsilon_{ij}}$ 与其前一个炉次 $L_{i, j-1}$ 在连铸机上的完工时间 $y_{i, j-1, \varepsilon_{i, j-1}}$ 之间的差值 $x_{i, j, \varepsilon_{ij}}-y_{i, j-1, \varepsilon_{i, j-1}}$ 小于等于 $L_{i, j-1}$ 在连铸机上处理时间的最大可延长值 $p_{i, j-1, \varepsilon_{i, j-1}}^{U}-(y_{i, j-1, \varepsilon_{i, j-1}}-x_{i, j-1, \varepsilon_{i, j-1}})$ , 即保证下式成立:

2)  同一台设备上加工的不同炉次之间不能出现作业时间冲突约束

由于炼钢-连铸生产过程属于非抢占式加工, 即炉次在设备上加工时不允许其他炉次进行抢占, 并且炉次一旦开始加工则不允许中断, 直到加工结束为止.同一个设备上加工的相邻两个炉次, 必须等到前一个炉次在该设备上加工结束之后才能开始下一个炉次的加工, 即同一个设备上加工的不同炉次之间不能出现作业时间冲突.

由于每个炉次在连铸机上的先后浇铸顺序已知, 则可知连铸机上炉次 $L_{ij}$ 与紧后炉次为 $L_{i, j+1}$ 不能产生作业时间冲突的约束可以精确表达为

由于精炼工序和转炉工序均存在多台相同功能的加工设备, 使得炉次在这些工序上具体在哪台设备上加工不确定, 从而进一步导致某台设备上加工的前后相邻炉次不确定, 使得设备上相邻炉次不能产生作业时间冲突的约束无法进行精确数学描述.令与炉次 $L_{ij}$ 在同一设备上加工的炉次为 $L_{i_{1}, j_{1}}$ , $L_{i_{1}, j_{1}}$ 与 $L_{ij}$ 不能发生作业冲突描述如下:

3)  炉次加工顺序约束:炉次加工的各个阶段必须按照生产工艺路径规定的先后顺序依次加工

炉次 $L_{ij}$ 生产工艺路径由工艺部门事先确定, 在生产过程中每个炉次的加工必须严格按照规定的生产工艺路径进行.炉次 $L_{ij}$ 在其生产工艺路径中的后一个阶段的加工必须等到其在前一个阶段加工结束之后才能开始, 也就是说, $L_{ij}$ 在阶段 $k$ 的开工时间 $x_{ijk}$ 与在阶段 $k-1$ 的完工时间 $y_{i, j, k-1}$ , 以及设备间运输时间 $T_{m_{i, j, k-1}, m_{ijk}}$ 的差值必须大于或等于零, 即:

4)  炉次在已完工阶段或者正在加工阶段的加工设备约束

对于炉次正在加工的阶段或者是已完工的工序不再调整其加工设备, 仍然为初始调度计划中的加工设备, 即:

5)  炉次在设备上的处理时间约束

炉次在设备上的处理时间包括允许最小处理时间、标准处理时间和允许最大处理时间.炉次 $L_{ij}$ 在设备上的处理时间必须小于等于允许最大处理时间 $p_{ijk}^{U}$ 和大于等于允许最小处理时间 $p_{ijk}^{L}$ , 即:

6)炉次在每个阶段的加工设备类型约束

炉次在每个阶段必须在指定的加工设备类型上加工, 且只能在一台设备上加工:

7)炉次在连铸工序的加工设备约束

炼钢-连铸的每个浇次均由计划部门指定了其在连铸工序加工的连铸机设备, 在重调度时不能进行改变:

8)同一浇次内的炉次加工顺序约束

每个浇次内的炉次加工顺序由计划部门指定, 在重调度时不能进行改变:

9)炉次在设备上正在加工或者已完工时的开工时间约束

当炉次在设备上正在加工或者已完工时, 其开工时间在重调度时不能再进行改变, 其值等于初始计划中的开工时间:

10)  炉次在设备上已完工时的完工时间约束

当炉次在设备上已完工时, 其完工时间在重调度时不能再进行改变, 其值等于初始计划中的完工时间:

11)决策变量取值约束

2.5   重调度模型

根据上述分析, 建立如下的重调度模型(记为 $MM$ ):

炼钢-连铸生产重调度模型 $MM$ 的设备指派变量 $z_{ijk}^{m}$ 为0-1变量, 开工时间 $x_{ijk}$ 和完工时间 $y_{ijk}$ 为整数变量, 建立的炼钢-连铸生产重调度模型为混合整数规划模型.

3.   开工时间延迟下的炼钢-连铸生产重调度策略

对于混合整数规划模型 $MM$ , 随着调度问题规模的增大, 传统最优化方法的求解难度将急剧增加, 往往不能适应生产实际对实时性的要求.遗传算法等智能方法对于大规模的组合优化问题, 搜索空间大, 搜索时间较长, 往往会出现早熟收敛的情况, 并且对初始种群很敏感, 初始种群选择不好会影响解的质量和算法效率.为了便于炼钢-连铸生产重调度混合整数规划模型求解, 本文分为两个阶段对模型 $MM$ 进行求解.第一阶段以混合整数规划模型 $MM$ 的设备指派变量 $z_{ijk}^{m}$ 为决策变量, 对混合整数规划模型 $MM$ 中的同一台设备上加工的不同炉次之间不能出现作业时间冲突约束进行松弛, 即不考虑式(3)和式(4)的约束, 而将模型 $MM$ 的其他约束作为约束条件建立设备指派子模型 $MM-1$ , 采用启发式方法对设备指派子模型 $MM-1$ 进行求解得到设备指派变量 $z_{ijk}^{m}$ 值, 该解即作为模型 $MM$ 的设备指派变量 $z_{ijk}^{m}$ 值.第二阶段将 $z_{ijk}^{m}$ 值代入模型 $MM$ , 此时因所有的 $z_{ijk}^{m}$ 值均已知, 所以此时模型 $MM$ 其实是以开工时间 $x_{ijk}$ 和完工时间 $y_{ijk}$ 为决策变量, 且部分约束条件也因 $z_{ijk}^{m}$ 值已知且满足约束而不必再考虑, 使得模型 $MM$ 考虑的约束条件也随之减少.本文将此时的模型 $MM$ 记为作业时间决策子模型 $MM-2$ , 采用启发式方法对模型 $MM-2$ 进行求解得到决策变量 $x_{ijk}$ 和 $y_{ijk}$ 值, 该解即作为模型 $MM$ 的作业时间变量 $x_{ijk}$ 和 $y_{ijk}$ 值.通过上述两个阶段求解最终得到混合整数规划模型 $MM$ 的设备决策变量 $z_{ijk}^{m}$ 值和作业时间变量 $x_{ijk}$ 和 $y_{ijk}$ 值.为此, 本文提出图 3所示的开工时间延迟下的炼钢-连铸生产重调度策略:

图 3  开工时间延迟扰动下的炼钢–连铸生产重调度策略

Fig. 3  Rescheduling strategy for the steelmaking and continuous casting

下载: 全尺寸图片 幻灯片

1) 炉次开工延迟时间计算:在生产进行过程中, 一旦有炉次在转炉上开始加工, 则立即获取炉次信息、设备信息、炉次实际开工时间, 根据炉次实际开工时间和炉次在初始调度计划中的开工时间计算炉次开工时间延迟值.

2) 重调度判断:根据炉次在转炉设备上的开工时间延迟值, 判断初始调度计划是否产生了连铸断浇或者是炉次作业时间冲突, 从而确定是否需要对初始调度计划进行重调度.

3) 重调度炉次选择:根据炉次在连铸机上的开工时间, 从初始调度计划中将在连铸机上仍未完工的炉次选取出来作为重调度对象.

4) 炉次设备决策变量求解:建立设备指派子模型, 采用启发式方法对模型求解, 求得炉次在各阶段的加工设备.

5) 炉次作业时间决策变量求解:建立作业时间决策子模型, 采用启发式方法对模型求解, 求得炉次在设备上的开工时间和完工时间.

4.   开工时间延迟下的炼钢-连铸生产重调度方法

4.1   炉次开工延迟时间计算

当初始调度计划 $\Omega^{0}$ 中的某个炉次 $L_{i^{\ast}j^{\ast}}$ 在转炉设备上开工时, 则获取该炉次在转炉设备上的实际开工时间 $s_{i^{\ast}j^{\ast}1}^{\ast}$ , 并根据炉次 $L_{i^{\ast}j^{\ast}}$ 在初始调度计划中的开工时间 $s_{i^{\ast}j^{\ast}1}^{0}$ 计算炉次 $L_{i^{\ast}j^{\ast}}$ 在转炉设备上的开工延迟时间 $\Delta{T}$ :

4.2   重调度判断

当炉次 $L_{i^{\ast}j^{\ast}}$ 在转炉设备上开工延迟 $\Delta{T}$ 时, 因炉次 $L_{i^{\ast}j^{\ast}}$ 要满足其在各工序的先后加工顺序约束, 即 $L_{i^{\ast}j^{\ast}}$ 在其生产工艺路径中在阶段 $k$ 的开工时间 $x_{i^{\ast}j^{\ast}k}$ 与在阶段 $k-1$ 的完工时间 $y_{i^{\ast}, j^{\ast}, k-1}$ , 以及设备间运输时间 $T_{m_{i^{\ast}, j^{\ast}, k-1}^{0}, m_{i^{\ast}j^{\ast}k}^{0}}$ 的差值必须大于或等于零:

为此, 根据炉次 $L_{i^{\ast}j^{\ast}}$ 在转炉设备上开工延迟值 $\Delta{T}$ 重新计算炉次 $L_{i^{\ast}j^{\ast}}$ 在转炉设备上的完工时间:

然后计算炉次 $L_{i^{\ast}j^{\ast}}$ 在转炉后续工序设备上的开工时间和完工时间:

此时炉次 $L_{i^{\ast}j^{\ast}}$ 在各工序的开工时间 $x_{i^{\ast}j^{\ast}k}$ 和完工时间 $y_{i^{\ast}j^{\ast}k}$ 为开工延迟 $\Delta{T}$ 后更新的时间, 而其他炉次 $L_{ij}~(L_{ij}\in\Omega^{0}, L_{ij}\neq L_{i^{\ast}j^{\ast}})$ 的作业时间仍为初始调度计划中的开工时间 $s_{ijk}^{0}$ 和完工时间 $e_{ijk}^{0}$ .初始调度计划中, 浇次 $i^{\ast}$ 在连铸机上的炉次加工顺序集合 $I_{i^{\ast}}$ 已知, 且 $I_{i^{\ast}}=\{L_{i^{\ast}1}, L_{i^{\ast}2}, \cdots, L_{i^{\ast}, S_{i^{\ast}}}\}$ .由此可知炉次 $L_{i^{\ast}j^{\ast}}$ 在连铸机上的紧前炉次为 $L_{i^{\ast}, j^{\ast}-1}$ .当 $L_{i^{\ast}j^{\ast}}$ 更新后的在连铸机上的开工时间 $x_{i^{\ast}, j^{\ast}, \varepsilon_{i^{\ast}j^{\ast}}}$ 与 $L_{i^{\ast}, j^{\ast}-1}$ 在连铸机上的完工时间 $e_{i^{\ast}, j^{\ast}-1, \varepsilon_{i^{\ast}, j^{\ast}-1}}^{0}$ 之间发生断浇时, 则需要对初始调度计划进行重调度, 以保证连续浇铸.当炉次 $L_{i^{\ast}, j^{\ast}-1}$ 和 $L_{i^{\ast}j^{\ast}}$ 在连铸机上的间隔时间, 即 $L_{i^{\ast}j^{\ast}}$ 在连铸机上的开工时间 $x_{i^{\ast}, j^{\ast}, \varepsilon_{i^{\ast}, j^{\ast}}}$ 与 $L_{i^{\ast}, j^{\ast}-1}$ 在连铸机上的完工时间 $e_{i^{\ast}, j^{\ast}-1, \varepsilon_{i^{\ast}, j^{\ast}-1}}^{0}$ 之间的差值 $x_{i^{\ast}, j^{\ast}, \varepsilon_{i^{\ast}j^{\ast}}}-e_{i^{\ast}, j^{\ast}-1, \varepsilon_{i^{\ast}, j^{\ast}-1}}^{0}$ , 大于 $L_{i^{\ast}, j^{\ast}-1}$ 在连铸机上处理时间的最大可延长值 $p_{i^{\ast}, j^{\ast}-1, \varepsilon_{i^{\ast}, j^{\ast}-1}}^{U}-(e_{i^{\ast}, j^{\ast}-1, \varepsilon_{i^{\ast}, j^{\ast}-1}}^{0}-s_{i^{\ast}, j^{\ast}-1, \varepsilon_{i^{\ast}, j^{\ast}-1}}^{0}) $ 时, 将无法通过延长 $L_{i^{\ast}, j^{\ast}-1}$ 在连铸机上的处理时间来将间隔时间消除为零, 则产生断浇.即当下式成立时:

$L_{i^{\ast}, j^{\ast}-1}$ 与 $L_{i^{\ast}j^{\ast}}$ 在连铸机上发生断浇, 需要进行重调度.

另外, 由于炼钢-连铸生产过程属于非抢占式加工, 即炉次在设备上加工时不允许其他炉次进行抢占, 因此同一个设备上加工的相邻两个炉次, 必须等到前一个炉次在该设备上加工结束之后才能开始下一个炉次的加工, 即同一台设备上加工的不同炉次之间不能出现作业时间冲突.初始调度计划中, 炉次 $L_{i^{\ast}j^{\ast}}$ 在设备 $k_{g}$ 加工的紧后炉次为已知信息, 令紧后炉次为 $L_{i_{1}j_{1}}$ .当炉次 $L_{i^{\ast}j^{\ast}}$ 在设备上更新后的作业时间和 $L_{i_{1}j_{1}}$ 在初始调度计划中的作业时间 $s_{i_{1}j_{1}k}^{0}$ 和 $e_{i_{1}j_{1}k}^{0}$ 发生冲突时, 则需要对初始调度计划进行重调度, 以保证同一台设备上加工的不同炉次之间不能出现作业时间冲突.即当下式成立时:

$L_{i^{\ast}j^{\ast}}$ 和 $L_{i_{1}j_{1}}$ 在设备 $k_{g}$ 上的作业时间发生冲突, 需要进行重调度.

综上所述, 当炉次 $L_{i^{\ast}j^{\ast}}$ 在转炉设备上开工延迟 $\Delta{T}$ 时, 若 $L_{i^{\ast}, j^{\ast}-1}$ 与 $L_{i^{\ast}j^{\ast}}$ 在连铸机上发生断浇, 即式(22)成立, 或者 $L_{i^{\ast}j^{\ast}}$ 和 $L_{i_{1}j_{1}}$ 在设备 $k_{g}$ 上的作业时间发生冲突, 即式(23)成立时, 则需要对初始调度计划进行重调度.

4.3   重调度炉次选择

当炉次在转炉开工时间发生延迟导致连铸断浇或者炉次作业时间冲突时需要进行重调度, 此时初始调度计划中炉次的加工状态分为未开工、正在加工和已完工.炉次未开工表示炉次的任何操作均未开始加工.炉次正在加工表示炉次至少有一个操作已开始加工、且炉次在连铸工序未浇铸结束.炉次已完工表示炉次的所有操作都加工结束.对于已完工炉次不再进行重调度, 只对那些未完工炉次在追求更好调度指标下, 通过调整其加工设备和作业时间来应对转炉开工时间延迟所带来的影响, 保证生产顺畅进行.因此重调度对象为未完工炉次, 即发生转炉开工时间延迟时初始调度计划中未开工的炉次和正在加工的炉次.令 $\Omega$ 为初始调度计划集合 $\Omega^{0}$ 中需要进行重调度的炉次集合, 则其重调度炉次选择算法具体如下:

步骤1.  获取初始调度计划集合 $\Omega^{0}$ , 以及 $\Omega^{0}$ 中炉次在连铸工序的加工状态 $\beta_{i, j, \varepsilon_{ij}}$ ; 令重调度炉次集合 $\Omega=\phi$ .

步骤2.  令 $i=1$ .

步骤3.  令 $j=1$ .

步骤4.  若 $\beta_{i, j, \varepsilon_{ij}}=0$ , 则 $\Omega=\Omega+\{L_{ij}\}$ .

步骤5.  若 $j=S_{i}$ , 转至下一步; 否则, $j=j+1$ , 转至步骤4.

步骤6.  若 $i=3$ , 转至下一步; 否则, $i=i+1$ , 转至步骤3.

步骤7.  算法结束, 得到重调度炉次集合 $\Omega$ .

4.4   炉次设备决策变量求解

4.4.1   设备指派子模型建立

若将炉次 $L_{ij}$ 指派到设备进行加工, 在设备上与 $L_{ij}$ 可能发生冲突的炉次记为 $L_{i_{1}, j_{1}}$ .令 $F_{m}$ 为炉次 $L_{ij}$ 和炉次 $L_{i_{1}, j_{1}}$ 在设备 $m$ 上的作业时间冲突值:

当 $F_{m} > 0$ 时, 炉次 $L_{ij}$ 和炉次 $L_{i_{1}, j_{1}}$ 在设备上发生作业时间冲突.为了满足同一台设备上加工的不同炉次之间不出现作业时间冲突约束, 必须通过炉次作业时间平移对作业时间冲突值 $F_{m}$ 进行解消, 可知解消冲突后产生的等待时间值正好等于 $F_{m}$ .因此本文将模型 $MM$ 的以等待时间尽量最小目标式(1)转换为以炉次作业时间冲突最小作为设备指派子模型 $MM-1$ 的目标, 以模型 $MM$ 的设备指派变量 $z_{ijk}^{m}$ 作为设备指派子模型 $MM-1$ 的决策变量, 对混合整数规划模型 $MM$ 中的同一台设备上加工的不同炉次之间不能出现作业时间冲突约束进行松弛, 即不考虑式(3)和式(4)的约束, 而将模型 $MM$ 的其他约束作为模型约束条件, 并将模型 $MM$ 中的变量 $x_{ijk}$ 和 $y_{ijk}$ 分别采用中间变量 $X_{ijk}$ 和 $Y_{ijk}$ 表示, 建立如下的设备指派子模型 $MM-1$ :

s. t.

模型 $MM-1$ 因没有考虑同一台设备上加工的不同炉次之间不能出现作业时间冲突约束, 因此在求解得到决策变量 $z_{ijk}^{m}$ 时, 相应得到的中间变量 $X_{ijk}$ 和 $Y_{ijk}$ 可能会存在着时间冲突.对于模型 $MM-1$ 的求解, 本文采用图 4所示的启发式方法进行求解:

图 4  炉次设备决策变量求解

Fig. 4  Solving the decision variables of charge equipment

下载: 全尺寸图片 幻灯片

4.4.2   基于炉次加工状态确定设备决策的炉次阶段

基于炉次加工状态确定设备决策的炉次阶段是根据炉次在各阶段的加工状态确定炉次可以进行设备调整的加工阶段:对于炉次正在加工的阶段或者是已完工的阶段不再调整其加工设备, 仍然为初始调度计划中的加工设备; 对于炉次未开工的阶段, 则对其进行设备决策变量的确定.令 $\alpha_{ijk}$ 为炉次 $L_{j}$ 在阶段 $k$ 是否可以进设备调整的变量:若可以进行设备调整, 则 $\alpha_{ijk}=1$ ; 否则, $\alpha_{ijk}=0$ .

1)  炉次在连铸工序的加工设备(连铸机)已经指定, 在重调度过程中不能改变, 仍然为初始调度计划中的连铸机:

2)  当炉次在某工序正在加工或者已经完成加工时, 重调度不能再对该炉次在该工序上的加工设备进行改变:

3)  当炉次在非连铸工序未开工时, 重调度可以对该炉次在该工序上的加工设备进行调整, 即当炉次炉次 $L_{ij}$ 在阶段 $k (k\neq\varepsilon_{ij})$ 的加工状态 $\beta_{ijk}=0$ 时, 重调度可以对其设备进行重新指派:

4.4.3   基于炉次开工时间对炉次设备决策顺序排序

在炼钢-连铸生产调度过程中, 调度工件为高温钢水且加工设备均为大型生产设备.在发生转炉开工时间延迟扰动时, 正在加工的高温钢水对温度要求极高, 对其调整不及时则会使得钢水温度下降导致重新升温而增加能耗和物耗, 并严重影响生产效率.因此在进行重调度时, 对重调度炉次对象中已开工的炉次首先进行重调度, 然后再对没有开始生产的炉次进行调整, 从而一方面保证对处于加工状态炉次调整的及时性; 另一方面尽量减少没有开始生产炉次的调整对处于加工状态炉次的影响.

已开工炉次由于其存在着正在加工或已完工的操作, 这些操作在工序上的加工设备和开工时间不能再被修改, 因此在对已开工炉次的未开工操作进行作业时间调整时, 只能将其作业时间向后移动以满足生产约束.所以本文在对已开工炉次进行重调度时, 按照所有已开工炉次的各个操作的开工时间由早到晚的顺序依次对操作的设备决策变量求解.令 $O^{1}$ 为 $\Omega$ 中已开工炉次的所有操作按照开工时间由早到晚的顺序排序得到的操作集合.

对于未开工炉次, 因存在着同一浇次内相邻炉次连续浇铸约束, 所以必须保证未开工炉次在连铸机上的操作的开工时间与同一连铸机上加工的前一个操作的完工时间相等.在对未开工炉次进行重调度时, 首先, 根据连续浇铸约束计算未开工炉次在连铸机上的开工时间和完工时间; 然后, 在此基础上反向计算出未开工炉次在精炼阶段和在转炉阶段的开工时间和完工时间; 最后, 根据未开工炉次在精炼阶段和在转炉阶段的开工时间按照从晚到早的顺序对炉次操作依次进行设备决策变量求解.令 $O^{2}$ 为 $\Omega$ 中未开工炉次的所有操作按照开工时间由晚到早的顺序排序得到的操作集合.

4.4.4   基于冲突最小和运输时间最小规则求解炉次设备指派变量

炉次设备指派变量求解是根据炉次设备决策顺序 $O=O^{1}+O^{2}$ 逐个为炉次加工阶段选择加工设备, 减少炉次在相邻设备间的等待时间.若 $O$ 中的操作 $o_{ijk}$ 的 $\alpha_{ijk}=0$ , 则 $o_{ijk}$ 的加工设备仍然为初始调度计划中的加工设备; 否则, 基于如下规则对其进行设备指派:炉次间作业冲突时间最小规则、运输时间最小规则、加工炉次数最少规则和随机选取规则.

1)  炉次间作业冲突时间最小

通过上述分析可知在炉次设备指派变量求解时, 从可以加工炉次的多台设备中, 选取使得炉次作业时间冲突最小的设备为炉次的加工设备, 可以使得炉次在设备上的等待时间尽量最小, 从而满足同一个炉次在相邻设备之间的等待时间尽量最小的性能指标.基于炉次间作业时间冲突最小规则的炉次设备指派变量求解方法就是从多台设备中选择作业冲突时间 $F_{m}$ 最小的设备为 $o_{ijk}$ 的加工设备, 即:

2)  设备间运输时间最短

若炉次在各阶段指派的加工设备之间的运输时间越小, 则可以减少炉次钢水在运输过程中的温降, 同时可以使得炉次在车间的流程时间最小, 也会使得炉次作业冲突时间 $F_{m}$ 越小.根据上述分析, 当作业冲突时间 $F_{m}$ 越小时, 可以使得炉次在设备上的等待时间尽量最小, 满足同一个炉次在相邻设备之间的加工等待时间尽量最小的性能指标.基于运输时间最短规则的炉次设备决策变量求解方法为从能够加工的多台设备设备中选择与其前道工序的加工设备运输时间最短的设备作为 $o_{ijk}$ 的加工设备, 即:

3)  加工炉次数最少规则

当将炉次指派到加工炉次少的设备上时, 其与其他炉次间发生冲突的可能性较小, 使得炉次在设备上的等待时间尽量小.令 $H_{m}$ 为设备 $m$ 上的加工炉次数.基于加工炉次数最少规则的指派方法为从能够加工操作的设备中选择加工炉次数最少的设备作为 $o_{ijk}$ 的加工设备, 即:

4)  随机选取规则

随机选取规则是指在对 $o_{ijk}$ 进行设备指派时, 从多台设备中随机选择一台设备作为 $o_{ijk}$ 的加工设备, 即:

根据上述设备指派规则, 本文建立如下基于规则优先级的设备指派:冲突时间最小规则、运输时间最短规则、加工炉次数最少规则、随机选取规则.

4.5   炉次作业时间决策变量求解

4.5.1   作业时间决策子模型建立

当求得设备决策变量 $z_{ijk}^{m}$ 值并将 $z_{ijk}^{m}$ 值代入模型 $MM$ 时, 此时因所有的 $z_{ijk}^{m}$ 值均已知, 所以此时模型 $MM$ 其实是以开工时间 $x_{ijk}$ 和完工时间 $y_{ijk}$ 为决策变量, 且部分约束条件(式(6)、式(8) $\sim$ 式(10))也因 $z_{ijk}^{m}$ 值已知且满足约束而不必再考虑, 使得模型 $MM$ 考虑的约束条件也随之减少.此时模型 $MM$ 就转换为了作业时间决策子模型 $MM-2$ .当对设备指派子模型 $MM-1$ 求解得到设备决策变量 $z_{ijk}^{m}$ 值后, 炉次在每个阶段的加工设备就已知, 则可以知道在同一设备上加工的炉次.同时根据相应求得的中间变量 $X_{ijk}$ 和 $Y_{ijk}$ 值可以知道同一设备上炉次之间的先后加工顺序.因此式(4)约束可以精确获得.作业时间决策子模型 $MM-2$ 以设备指派子模型 $MM-1$ 求得的每个炉次 $L_{ij}$ 在各阶段的 $z_{ijk}^{m}$ 为已知信息, 以模型 $MM$ 的开工时间 $x_{ijk}$ 和完工时间 $y_{ijk}$ 为决策变量, 以模型 $MM$ 的目标(式(1))为性能指标, 建立如下的模型 $MM-2$ :

对于模型 $MM-2$ 的求解, 本文采用图 5所示的启发式方法进行求解.

图 5  炉次作业时间决策变量求解

Fig. 5  Solving the decision variables of working time of charges

下载: 全尺寸图片 幻灯片

1)  基于炉次开工时间和完工时间平移启发式方法的作业时间不能冲突约束处理:以等待时间最小为目标, 采用将发生冲突的炉次的开工时间和完工时间平移启发式方法进行冲突解消, 满足炉次作业时间不能冲突约束;

2)  基于炉次处理时间调整启发式方法的连续浇铸约束处理:当连铸机上出现断浇时, 通过采用调整炉次在连铸机、精炼炉和转炉上的处理时间的启发式方法来消除断浇, 满足连续浇铸约束.

4.5.2   基于时间平移启发式方法的作业时间不能冲突约束处理

在对炉次进行设备指派时, 均是按照设备间的标准运输时间计算炉次的理想作业时间, 没有对同一设备上炉次间可能发生的作业时间冲突进行处理.作业时间不能冲突约束处理是对发生作业时间冲突的炉次通过调整其开工时间和完工时间, 使得同一设备上的不同炉次之间不发生作业时间冲突.因为在对处于加工状态的所有炉次进行设备决策顺序排序是按照炉次在各阶段设备上的开工时间从早到晚的顺序进行排序, 而对处于未开工的所有炉次进行设备决策顺序排序是按照炉次在各阶段设备上的开工时间从晚到早的顺序进行排序, 所以对冲突时间的处理也分为以下两种情况:

1) 对处于加工状态 $(\beta_{ij1}\neq0)$ 的炉次 $L_{ij}$ , 如图 6(a)所示炉次 $L_{ij}$ 的操作 $o_{i, j, k-1}$ 正在加工, 操作 $o_{i_{1}j_{1}k_{1}}$ 和 $o_{ijk}$ 均未开工, 且均安排在同一设备上, 产生的冲突时间用 $F_{m}$ 表示, $F_{m}=Y_{i_{1}j_{1}k_{1}}-X_{ijk}$ .因 $o_{i, j, k-1}$ 正在加工无法被修改开工时间进行平移, 且受到加工顺序约束, 只能将操作向后移动进行冲突解消.如果将 $o_{i_{1}j_{1}k_{1}}$ 作业时间向后平移进行冲突解消, 如图 6(b)所示, 则产生等待时间 $w_{i_{1}j_{1}k_{1}}=Y_{ijk}-X_{i_{1}j_{1}k_{1}}$ ; 如果将 $o_{ijk}$ 作业时间向后平移进行冲突解消, 如图 6(c)所示, 则产生等待时间 $w_{ijk}=Y_{i_{1}j_{1}k_{1}}-X_{ijk}$ , 且 $w_{ijk}=F_{m}$ .因为 $Y_{ijk} > Y_{i_{1}j_{1}k_{1}}$ , $X_{i_{1}j_{1}k_{1}} < X_{ijk}$ , 所以 $Y_{ijk}-X_{i_{1}j_{1}k_{1}} > Y_{i_{1}j_{1}k_{1}}-X_{ijk}$ , 即 $w_{i_{1}j_{1}k_{1}} > w_{ijk}$ .因此, 为了使得炉次操作间的等待时间尽量最小, 即追求 $MM-1$ 的目标(式(1)), 本文在针对此种冲突情况进行解消时, 采用图 6(c)所示的冲突解消方法, 将炉次 $L_{ij}$ 的作业时间向后移动 $F_{m}$ 段时间来消除冲突时间:

图 6  处于加工状态的炉次作业时间不能冲突约束处理

Fig. 6  Handling conflict time for charges being processed

下载: 全尺寸图片 幻灯片

2)对处于未开工 $(\beta_{ij1}=0)$ 的炉次 $L_{ij}$ , 如图 7(a)所示炉次 $L_{ij}$ 的操作 $o_{i, j, k+1}$ 已完成指派, 操作 $o_{i_{1}j_{1}k_{1}}$ 和 $o_{ijk}$ 均安排在同一设备上, 产生的冲突时间用 $F_{m}$ 表示, $F_{m}=Y_{ijk}-X_{i_{1}j_{1}k_{1}}$ .因 $o_{i, j, k+1}$ 已完成指派, 若将 $o_{i, j, k+1}$ 向后移进行冲突解消, 则会因受到加工顺序约束使得炉次 $L_{ij}$ 在 $o_{i, j, k+1}$ 之后的操作也要向后平移, 从而导致在连铸机上产生断浇时间, 因此不对 $o_{i, j, k+1}$ 进行作业时间移动.如果将 $o_{i_{1}j_{1}k_{1}}$ 作业时间向前平移进行冲突解消, 如图 7(b)所示, 则产生等待时间 $w_{i_{1}j_{1}k_{1}}=Y_{i_{1}j_{1}k_{1}}-X_{ijk}$ ; 如果将 $o_{ijk}$ 作业时间向前平移进行冲突解消, 如图 7(c)所示, 则产生等待时间 $w_{ijk}=Y_{ijk}-X_{i_{1}j_{1}k_{1}}$ , 且 $w_{ijk}=F_{m}$ .因为 $Y_{ijk} < Y_{i_{1}j_{1}k_{1}}$ , $X_{i_{1}j_{1}k_{1}} > X_{ijk}$ , 所以 $Y_{i_{1}j_{1}k_{1}}-X_{ijk} > Y_{ijk}-X_{i_{1}j_{1}k_{1}}$ , 即 $w_{i_{1}j_{1}k_{1}} > w_{ijk}$ .因此, 为了使得炉次操作间的等待时间尽量最小, 即追求 $MM-1$ 的目标(式(1)), 本文在针对此种冲突情况进行解消时, 采用图 7(c)所示的冲突解消方法, 将炉次 $L_{ij}$ 的作业时间向前移动 $F_{m}$ 段时间来消除冲突时间:

图 7  未开工炉次作业时间不能冲突约束处理

Fig. 7  Handling conflict time for nor started charges

下载: 全尺寸图片 幻灯片

4.5.3   基于炉次处理时间调整启发式方法的连续浇铸约束处理

连续浇铸约束处理是使得同一连铸机上加工的相邻炉次不发生断浇.炉次 $L_{ij}$ 在连铸机上的开工时间和完工时间分别为 $X_{i, j, \varepsilon_{ij}}$ 和 $Y_{i, j, \varepsilon_{ij}}$ , 前一个炉次 $L_{i, j-1}$ 在连铸机上的开工时间和完工时间分别为 $X_{i, j-1, \varepsilon_{i, j-1}}$ 和 $Y_{i, j-1, \varepsilon_{i, j-1}}$ .当:

$L_{ij}$ 与 $L_{i, j-1}$ 之间出现连铸断浇, 仅通过调整 $L_{i, j-1}$ 在连铸机上的处理时间无法消除断浇时间.如果图 8中炉次 $L_{i, j-1}$ 是浇次 $i$ 的第一个炉次, 则可以将操作 $o_{i, j-1, \varepsilon_{i, j-1}}$ 向后平移消除断浇时间, 但会在 $o_{i, j-1, \varepsilon_{i, j-1}}$ 与 $o_{i, j-1, \varepsilon_{i, j-1}-1}$ 之间产生 $X_{i, j, \varepsilon_{ij}}-Y_{i, j-1, \varepsilon_{i, j-1}}$ 大小的等待时间.为了在进行连续浇铸约束处理过程中不新增等待时间, 本文采用基于炉次处理时间调整启发式方法进行连续浇铸约束处理, 主要步骤如下:

图 8  连续浇铸约束处理

Fig. 8  Continuous casting constraint processing

下载: 全尺寸图片 幻灯片

步骤1.  延长炉次 $L_{i, j-1}$ 在连铸机上的处理时间.因为仅通过调整 $L_{i, j-1}$ 在连铸机上的处理时间无法消除断浇时间, 但可以通过调整 $L_{i, j-1}$ 在连铸机上的处理时间来减少断浇时间.即在保持 $L_{i, j-1}$ 在连铸机上开工时间 $X_{i, j-1, \varepsilon_{i, j-1}}$ 不变的基础上, 将 $L_{i, j-1}$ 在连铸机上的处理时间调整到其最大处理时间:

步骤2.  缩短炉次 $L_{ij}$ 在连铸工序的前一道工序上的处理时间.在保持 $o_{i, j, \varepsilon_{ij}-1}$ 的开工时间不变的基础上, 缩短 $o_{i, j, \varepsilon_{ij}-1}$ 的处理时间来处理断浇.令 $\Delta\tau_{i, j, \varepsilon_{ij}-1}^{1}$ 为 $o_{i, j, \varepsilon_{ij}-1}$ 处理时间的缩短值:

则 $o_{i, j, \varepsilon_{ij}-1}$ 的完工时间为

然后更新 $L_{ij}$ 在连铸工序的开工时间和完工时间:

步骤3.  依次延长炉次 $L_{i, j_{1}}(j_{1}=j-2, j-3, \cdots, j^{\sharp})$ 在连铸机上的处理时间.在保持炉次 $L_{i, j_{1}}$ 在连铸工序的开工时间不变的基础上, 延长 $L_{i, j_{1}}$ 在连铸工序的处理时间来处理断浇.令 $\Delta\tau_{i, j_{1}, \varepsilon_{i, j_{1}}}^{2}$ 为 $L_{i, j_{1}}$ 在连铸工序上处理时间的延长值:

因此 $L_{i, j_{1}}$ 在连铸工序上的完工时间为

更新炉次 $L_{i, j_{1}}$ 后续炉次 $L_{i, j_{2}}$ 在连铸机上的开工时间和完工时间:

5.   炼钢-连铸生产重调度方法的仿真实验

5.1   重调度方法设计

将本文提出的重调度排序规则和设备指派规则分别记为Seq1和Assign1.为了对本文提出的重调度方法进行充分研究, 本文与以下不同的重调度排序规则和设备指派规则进行比较:

1) 按照炉次在连铸机上的预开工时间从早到晚的顺序依次选择炉次进行重调度(Seq2):按照炉次在连铸机上的开工时间从早到晚的顺序依次选择炉次进行调度, 并且在对单个炉次进行调度时采取对该炉次逆向逐个调度其操作.

2) 按照炉次在连铸机上的预开工时间从晚到早的顺序依次选择炉次进行重调度(Seq3):按照炉次在连铸机上的开工时间从晚到早的顺序依次选择炉次进行调度, 并且在对单个炉次进行调度时采取对该炉次逆向逐个调度其操作.

3) 设备指派规则优先级2 (Assign2):冲突时间最小规则、加工炉次数最少规则、运输时间最短规则、随机选取规则;

4) 设备指派规则优先级3 (Assign3):运输时间最短规则、冲突时间最小规则、加工炉次数最少规则、随机选取规则;

5) 设备指派规则优先级4 (Assign4):运输时间最短规则、加工炉次数最少规则、冲突时间最小规则、随机选取规则;

6) 设备指派规则优先级5 (Assign5):加工炉次数最少规则、冲突时间最小规则、运输时间最短规则、随机选取规则;

7) 设备指派规则优先级6 (Assign6):加工炉次数最少规则、运输时间最短规则、冲突时间最小规则、随机选取规则.

根据上述重调度排序规则和设备指派规则的不同组合得到多种启发式重调度方法, 见表 1所示.

表 1  各种重调度方法

Table 1  Rescheduling methods

序号	重调度排序	指派规则优先级	重调度方法
1	Seq1	Assign1	H11
2	Seq1	Assign2	H12
3	Seq1	Assign3	H13
4	Seq1	Assign4	H14
5	Seq1	Assign5	H15
6	Seq1	Assign6	H16
7	Seq2	Assign1	H21
8	Seq2	Assign2	H22
9	Seq2	Assign3	H23
10	Seq2	Assign4	H24
11	Seq2	Assign5	H25
12	Seq2	Assign6	H26
13	Seq3	Assign1	H31
14	Seq3	Assign2	H32
15	Seq3	Assign3	H33
16	Seq3	Assign4	H34
17	Seq3	Assign5	H35
18	Seq3	Assign6	H36

下载: 导出CSV 

| 显示表格

5.2   仿真实验参数设计

本文仿真实验时, 每类设备均有3台设备, 同类设备处理时间相同.根据对炼钢-连铸生产过程的分析, 选取如下对重调度性能产生较大影响的参数进行仿真实验:

1) 炉次数规模 $C_{1}$ :表示初始调度计划中的炉次数量的多少程度, $C_{1}=1$ 表示小规模的炉次数, $C_{1}=2$ 表示中等规模的炉次数, $C_{1}=3$ 表示大规模的炉次数.令 $\vartheta_{1}$ 表示炉次数的多少:当 $C_{1}=1$ 时, $\vartheta_{1}\in[15, 30]$ ; 当 $C_{1}=2$ 时, $\vartheta_{1}\in[60, 90]$ ; 当 $C_{1}=3$ 时, $\vartheta_{1}\in[120, 180]$ .

2) 精炼方式 $C_{2}$ :表示炉次的精炼方式, $C_{2}=1$ 表示 $RH\to LF\to IR-UT$ , $C_{2}=2$ 表示 $LF\to RH\to IR-UT$ , $C_{2}=3$ 表示 $RH\to LF\to RH$ , $C_{2}=4$ 表示 $RH\to LF\to IR-UT$ 和 $LF\to RH\to IR-UT$ , $C_{2}=5$ 表示 $RH\to LF\to IR-UT$ 、 $LF\to RH\to IR-UT$ 和 $RH\to LF\to RH$ .

3) 扰动发生时间点 $C_{3}$ :指开工时间延迟扰动发生的时间点相对于整个初始调度计划最大完成时间的早晚程度: $C_{3}=1$ 表示较早的开工时间延迟扰动, $C_{3}=2$ 表示中间位置的开工时间延迟扰动, $C_{3}=3$ 表示较晚的开工时间延迟扰动.令 $T_{LD}^{\rm Max}$ 为整个初始调度计划在转炉工序的最大完成时间, $\vartheta_{3}$ 表示扰动发生的时间点:当 $C_{3}=1$ 时, $\vartheta_{3}\in[0. 05T_{LD}^{\rm Max}, 0. 1T_{LD}^{\rm Max}]$ ; 当 $C_{3}=2$ 时, $\vartheta_{3}\in[0. 2T_{LD}^{\rm Max}, 0. 6T_{LD}^{\rm Max}]$ ; 当 $C_{3}=3$ 时, $\vartheta_{3}\in[0. 7T_{LD}^{\rm Max}, 0. 9T_{LD}^{\rm Max}]$ .

4) 延迟扰动量大小 $C_{4}$ :表示开工时间延迟量的大小程度: $C_{4}=1$ 表示小程度的开工时间延迟量, $C_{4}=2$ 表示中等程度的开工时间延迟量, $C_{4}=3$ 表示大程度的开工时间延迟量.令 $\vartheta_{4}$ 表示开工时间延迟量:当 $C_{4}=1$ 时, $\vartheta_{3}\in[5, 10)$ ; 当 $C_{4}=2$ 时, $\vartheta_{3}\in[10, 30)$ ; 当 $C_{4}=3$ 时, $\vartheta_{3}\in[30, 40)$ .

根据上述对仿真参数的分析可知, 本文设计 $3\times5\times3\times3=135$ 种仿真实例涵盖所有参数范围, 研究重调度方法在各种情况下的优化性能.对每种仿真实例分别随机产生10组实例数据进行仿真实验研究.仿真实验采用Microsoft Visual Studio 2010开发环境下的Visual C $\sharp. $ NET进行开发, 初始调度计划的产生采用Yu等^[21]的调度方法得到.通过重调度实验可以得到1 350个实例数据下18种启发式方法的重调度结果.

5.3   仿真实验结果分析

对于仿真实验结果, 令 $J_{q}^{\delta}$ 为第 $\delta$ 种启发式方法针对第 $q$ 个实例数据得到的性能指标值, 即等待时间值.令 ${\rm RPI}(J_{q}^{\delta})$ (Relative percentage increase, RPI)在第 $q$ 个实例数据下第 $\delta$ 种启发式方法得到计划结果的性能指标值, 计算如下:

其中, $J_{q}^{\ast}$ 为最优性能指标值.由于调度计划最优值无法获得, 此处 $J_{q}^{\ast}$ 选取第 $q$ 个实例数据下所有启发式方法得到的性能指标值中的最优值.令 ${\rm RPI}(J^{\delta})$ 为在 $Q$ 个实例数据情况下 $(q=1, \cdots, Q)$ 第 $\delta$ 种启发式方法的 ${\rm RPI}(J_{q}^{\delta})$ 的平均值:

可以看出, ${\rm RPI}(J^{\delta})$ 值越小, 则说明该调度方法就越好.表 2所示为14种问题下各种启发式方法的 ${\rm RPI}(J^{\delta})$ 值.从表 2可以看出: 1) 随着炉次数规模的增加, 所有启发式方法的性能均下降; 2) 对于各种精炼方式, 所有启发式方法基本均在 $C_{2}=3$ 获得最好的调度性能; 3) 当扰动发生时间点发生在较晚时刻时, 所有启发式方法均获得最好的调度性能; 4) 当在大程度的延迟扰动量时, 大部分启发式方法获得最好的调度效果; 5) 在各种情况下, H11、H21、H22的调度性能较好.

表 2  各种启发式方法的RPI值

Table 2  RPI values of rescheduling methods

问题	参数	H11	H12	H13	H14	H15	H16	H21	H22	H23	H24	H25	H26	H31	H32	H33	H34	H35	H36
P1	$C_{1}=1$	2	3	322	327	33	41	0	0	132	134	2	3	2	2	132	140	7	10
P2	$C_{1}=2$	4	13	102 010	101 702	186	270	6	5	88 560	88 515	6	13	10	15	88 386	88 847	54	51
P3	$C_{1}=3$	30	71	877 070	875 109	422	522	19	20	819 627	819 112	26	37	30	27	820 876	819 229	96	98
P4	$C_{2}=1$	12	65	744 525	735 497	800	818	0	0	694 356	693 395	12	28	12	21	695 642	693 220	188	190
P5	$C_{2}=2$	45	77	885 908	887 138	244	542	0	0	817 767	817 774	3	17	24	26	818 366	818 702	44	43
P6	$C_{2}=3$	1	1	242	279	5	5	8	12	230	249	2	2	18	6	125	247	2	3
P7	$C_{2}=4$	1	1	1 111	1 106	13	16	21	16	1 015	1 020	23	25	9	10	1 016	1 024	16	15
P8	$C_{2}=5$	0	1	553	542	6	7	15	15	497	497	16	18	8	9	508	501	11	14
P9	$C_{3}=1$	29	58	694 030	693 295	303	417	19	19	654 301	654 034	11	22	28	28	654 200	653 089	99	97
P10	$C_{3}=2$	6	25	272 029	270 402	242	313	6	6	244 777	244 773	10	17	12	15	245 962	245 842	48	53
P11	$C_{3}=3$	1	5	13 345	13 440	96	104	0	0	9 241	9 254	13	15	1	1	9 232	9 248	10	9
P12	$C_{4}=1$	2	1	544 354	541 868	464	477	9	10	504 493	504 403	12	15	6	5	505 085	504 079	115	113
P13	$C_{4}=2$	33	84	386 237	386 413	117	257	9	7	358 574	357 953	13	21	23	30	359 090	358 857	27	25
P14	$C_{4}=3$	1	2	48 812	48 857	60	99	7	9	45 253	45 404	9	18	13	9	45 219	45 280	15	22

下载: 导出CSV 

| 显示表格

图 9所示为在各种新情况下的所有启发式方法结果的平均等待时间值.从图 9可以看出: 1) 当炉次数增加时, 设备上炉次之间冲突的可能性增大, 就会产生更多的等待时间, 导致各种启发式方法性能降低; 2) 对于各种精炼方式, 所有启发式方法基本均在 $C_{2}=5$ 产生的等待时间最少; 3) 当扰动发生的时间点处在整个炉次计划较早时刻时, 扰动影响的炉次最多, 导致扰动对整个计划的影响程度最大, 产生的等待时间也最多; 4) 对于延迟扰动量的变化, 在中等程度的延迟扰动量时各个启发式算法产生的等待时间最少; 5) 在所有情况下, 启发式方法H11的调度性能最优.

图 9  不同重调度方法的平均目标值

Fig. 9  Average objective values of rescheduling methods

下载: 全尺寸图片 幻灯片

为了进一步研究启发式方法H11调度效果, 对H11在仿真参数两两变化时的调度性能进行分析.图 10所示为两两仿真参数变化时H11的调度效果: 1) 图 10(a)表示仿真参数 $C_{1}$ 和 $C_{2}$ 之间变化时对等待时间的影响, 在 $C_{2}=3$ 处, 随着 $C_{1}$ 的增大, 等待时间迅速增加. 2) 从图 10(b)可以看出, 在 $C_{1}=[1, 2]$ 和 $C_{3}=[1, 2]$ 这个范围的中心部分, 等待时间达到最大; 在 $C_{1}=[2, 3]$ 和 $C_{3}=[2, 3]$ 这个范围的中心部分, 等待时间变小. 3) 图 10(c)的曲面图与10 (b)相似, 在 $C_{1}=[1, 2]$ 和 $C_{4}=[1, 2]$ 这个范围的中心部分, 等待时间达到最大; 在 $C_{1}=[2, 3]$ 和 $C_{4}=[2, 3]$ 这个范围的中心部分, 等待时间变小. 4) 从图 10(d)可以看出, 在 $C_{2}=3$ 处, 随着 $C_{3}$ 的减小, 等待时间迅速增加. 5) 从图 10(e)可以看出, 在 $C_{2}=3$ 处, 随着 $C_{4}$ 的减小, 等待时间迅速增加. 6) 从图 10(f)看出, 在 $C_{3}=[1, 2]$ 和 $C_{4}=[1, 2]$ 这个范围的中心部分, 等待时间达到最小; 在 $C_{3}=[2, 3]$ 和 $C_{4}=[2, 3]$ 这个范围的中心部分, 等待时间变大.

图 10  仿真参数变化时对启发式方法H11等待时间的影响

Fig. 10  Average objective values of H11 method

下载: 全尺寸图片 幻灯片

Pang等^[22]对与本文相似的大型炼钢-连铸生产重调度问题进行了研究, 其重调度方法与本文不同之处在于:在其前三个阶段的调整过程中, 均是把炉次在设备上的处理时间作为一个常数, 仅在最后一个阶段当发生断浇时, 调整炉次在连铸工序的浇铸时间; 对转炉上已加工炉次, 仅调整其在精炼、连铸工序的开工时间, 不调整炉次在精炼工序的加工设备; 对转炉上未加工炉次进行重调度时, 是以炉次在连铸机上的开工时间先后顺序由前到后正向选择整个炉次进行重调度; 对转炉上未加工炉次在转炉、精炼工序上进行设备指派时, 采用的设备指派规则优先级为作业冲突时间最小、加工炉次数最少、运输时间最小和同类设备中随机选择一台设备.图 11和图 12为本文启发式方法(记为RS-Heu)与Pang方法(记为P-Heu)仿真实验的比较结果, 仿真所用数据为本文第5.2节设计的仿真实验参数和仿真实例.图 11(a)为两种方法的调度结果的平均等待时间指标比较, 图 11(b)为两种方法的调度结果的平均最大完成时间(Makespan)指标比较, 图 11(c)为两种方法的调度结果的平均设备负荷率指标比较.从图 11结果可以看出, 本文启发式方法RS-Heu在平均等待时间(越小越优型指标)、平均最大完成时间(越小越优型指标)和平均设备负荷率(越大越优型指标)三方面指标均优于P-Heu方法.图 12所为示两种方法的调度结果的平均设备负荷均衡率指标(采用标准差表示, 越小越优型指标)比较, 本文启发式方法RS-Heu在IR-UT平均设备负荷均衡率方面优于P-Heu方法, 而在LD、RH和LF的平均设备负荷均衡率方面, P-Heu方法稍占优.

图 11  不同重调度方法的指标比较

Fig. 11  Index comparison of different methods

下载: 全尺寸图片 幻灯片

图 12  不同重调度方法的设备负荷均衡率比较

Fig. 12  Comparison of load balancing rate of equipment for methods

下载: 全尺寸图片 幻灯片

6.   炼钢-连铸生产重调度方法的工业应用

本文以中国上海某大型炼钢厂二炼钢分厂为实际应用背景, 其精炼方式包括一重精炼、二重精炼、三重精炼.在信息化建设方面, 正在使用的有终端过程控制计算机系统(L2)和区域管理计算机系统(L3).由于生产过程中经常会出现各种扰动情况, 因此难以完全按照预调度计划的时间要求、工艺要求温度和工艺要求成分进行.由于缺少便捷、快速、优化的调整方法, 调度人员在编制调度计划时采取"走一步看一步"的做法, 以利于人工调整.炼钢-连铸生产过程中资源相互之间牵扯多, 人工调整会引起资源利用的局部性、短期性、片面性, 存在着调度反应慢、调度结果不优化的问题.本文以该炼钢厂炼钢-连铸生产调度系统的升级改造项目为背景, 结合现场生产的工艺实际情况, 将本文提出的重调度方法进行应用.图 13为基于本文提出的重调度方法在实际现场应用时的炼钢-连铸生产重调度系统界面, 其横坐标表示时间, 纵坐标表示设备.在现场实际应用1个月得到的生产数据进行分析的结果表明:在3座转炉对3台连铸机、日平均炉数为66炉的生产模式下, 平均日冗余等待时间从234分钟下降到166分钟, 日综合平均设备负荷率从 $50. 44 \%$ 上升到 $55. 16 \%$ ; 整个计划的重调度时间从原来的1分钟以上缩短至10秒以内.

图 13  炼钢–连铸生产重调度方法的工业应用

Fig. 13  Industrial application of the proposed method

下载: 全尺寸图片 幻灯片

7.   结论

现代大型炼钢-连铸生产过程都是由多台转炉、多台精炼炉、多台连铸机及大量的精炼方式组成, 并且在某些精炼方式中存在着回环现象, 使得炼钢-连铸生产重调度问题不同于job shop/flow shop/柔性job shop/混合flow shop等调度问题, 是一类特殊的生产调度问题.本文以中国上海某大型炼钢厂的炼钢-连铸生产线为背景, 针对多台转炉、多台精炼炉、多台连铸机及多重精炼方式下的开工时间延迟扰动下的炼钢-连铸生产重调度问题, 以炉次不冲突和不断浇的条件下, 在相邻工序的等待时间总和最小为目标, 建立了炼钢-连铸生产调度的混合整数规划模型, 基于模型分解思想提出了基于启发式方法的炼钢-连铸生产重调度方法.并对各种启发式重调度方法进行了仿真对比研究, 仿真实验结果表明本文提出的重调度方法的有效性.在某大型钢铁企业的工业应用表明所提出的重调度方法在减少炉次加工冗余等待时间方面取得显著成效.