板坯库天车调度属于多机多任务调度问题, 由于多台天车在同时执行多个任务, 且天车执行任务中受垛位布局、工艺流程、作业干涉等约束限制, 使板坯库天车调度问题成为典型的组合优化难题, 无法用一个有效的算法在多项式时间内求出最优解^[1].

目前, 针对天车调度问题的研究主要集中在集装箱码头天车调度问题^[2-4]和制造车间天车调度问题^[5-6], 而对冶金行业, 尤其是板坯库天车调度问题研究较少.赵宁等^[7]研究了板坯库天车作业具有随机性的问题, 建立了天车作业仿真模型, 采用基于Agent技术的循环仿真方法对模型进行仿真优化, 通过原始仿真模型和改进仿真模型的循环转换以及多档模糊评判寻求优化解.王旭等^[8]研究了炼钢-连铸过程中天车调度问题, 考虑时间和空间约束, 建立了天车调度模型, 采用Memetic算法对模型进行求解.Tang等^[9]研究了钢厂冷轧车间罩式退火的单天车调度问题, 建立了以最小化钢卷堆垛时间为目标的混合整数规划模型, 采用两阶段算法对模型进行求解.Tanizaki等^[10]研究了炼钢过程中多阶段天车调度问题, 考虑天车作业干涉, 建立了天车调度混合整数规划模型, 采用启发式算法对模型进行求解.

以上研究成果通过为每个天车分配任务避免天车出现干扰, 然而没有考虑出现干扰时天车避让情况.本文在已知轧制计划条件下, 根据板坯库的垛位布局, 考虑执行板坯出库任务中的板坯倒垛、天车避让等实际情况, 建立以最小化板坯出库时间为目标的板坯库天车调度模型, 设计了一个Memetic算法(Memetic algorithm, MA)对模型求解.

如图 1所示, 在某板坯库中有K台天车, 只能在作业跨内运行.沿作业跨方向, 按照工作区域划分为M行, 相邻两行距离为L.每行中有若干个板坯垛, 同一行中板坯垛沿着作业跨的位置相同.天车作业是指天车从开始位置吊起板坯, 运输到结束位置放下板坯的过程.为了避免天车发生碰撞, 相邻天车之间必须保持一个最小的安全距离δ.天车作业根据目标板坯所在板坯垛的位置划分为两种情况:如果目标板坯在顶层, 天车可以将它直接运输到目的位置, 称为运输作业.如果目标板坯上有阻碍板坯(见图 2, 阴影为目标板坯), 直到阻碍板坯被运到其他位置后, 天车才可以将它运输到目的位置.清除阻碍板坯的过程称为倒垛作业.

图 1(Fig. 1)

图 1 板坯库布局 Fig.1 Layout of slab yard

图 2(Fig. 2)

图 2 板坯垛结构 Fig.2 Structure of a slab stack

本文天车调度问题描述如下:给定一个板坯出库计划Ω, 包括N个作业任务, 任务i(i=1, 2, …, N.)有开始位置l_si和结束位置l_ei, 并且要在其时间窗[t_ei, t_li]内完成.天车集合Ψ, 包括K台天车, 天车k的起始位置l_k⁰、吊起和放下板坯的时间μ以及运输板坯的速度v是预先给定的, 且沿垂直作业跨方向的作业由天车上小车完成, 可将小车运动时间归入天车作业时间.因此, 任务i的处理时间t_i=2·μ+|l_ei-l_si|/v.类似地, 任务i的结束位置和任务j的开始位置之间的距离d_ij, 也可以预先计算出来.在任务开始时刻, 指派天车执行任务，天车执行完任务后, 从当前任务的结束位置以速度v空载到下一任务的开始位置.目标函数为最小化板坯出库的完成时间.

为了清晰表达上面描述的问题, 建立天车调度非线性整数规划模型.引入如下符号:

Ω为出库计划中任务集合, Ω={1, 2, …, N}，N为任务数; Γ为任务之间优先级集合, (i, j)∈Γ表明任务i必须在任务j之前执行; Ψ为天车集合, 按照从左到右的顺序依次进行编号, Ψ={1, 2, …, K}; K为天车数; l_k⁰为天车k的开始位置; l_si为任务i的开始位置; l_ei为任务i的结束位置; t_ei为任务i的最早开始时间; t_li为任务i的最晚结束时间; t_i为任务i的处理时间(包括天车吊起、运行和放下板坯的时间); v为天车运行速度; δ为天车之间的最小距离, 即需要保持的安全距离; d_ij为天车从任务i的结束位置到任务j的开始位置的距离; T_max为计划展望期; M为足够大的正数.

决策变量: t_fi为任务i的结束时间; x_k(t)为天车k在时刻t的位置.

建立数学模型如下:

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

其中, 式(1) 为目标函数, 即最小化板坯出库时间; 式(2) 和式(3) 每个任务只能由一台天车执行一次.式(4) 为天车运行速度约束; 式(5) 表示两台天车需保持一定安全距离; 式(6) 和式(7) 表示任务的时间窗约束; 式(8) 表示任务i要在任务j之前完成; 式(9) 定义变量的取值范围.

本文MA分别采用遗传算法和模拟退火算法作为群体进化方法和局域搜索方法.具体步骤如下:

1) 参数初始化:种群规模P, 迭代代数G, 当前最优个体I_best, 相同最好解出现次数n_best, 保持前代最好解数量n_{f, best}, 初始温度θ_max, 终止温度θ_min, 温降系数c, 温降幅度△t;

2) 初始化种群P(1), 令P′(1):=∅;

For k=1 To G

 For i=1 To P/2

  采用轮盘赌方式从P(k)选择两个个体S₁和S₂;

  应用自适应交叉算子从S₁和S₂构造两个新个体S₁^′和S₂^′;

  应用变异算子从S₁^′和S₂^′构造两个新个体S₁^″和S₂^″;

  对S₁^″和S₂^″分别应用SA局域搜索得到个体S₁^l和S₂^l;

   P′(k):=P′(k)∪{S₁^l, S₂^l};

  从P′(k)中选择最好个体作为I_best, 从P(k)∪P′(k)中选择最好的n_{f, best}个个体, 从P(k)∪P′(k)中采用轮盘赌方式选择(P-n_{f, best})个个体, 生成P″(k);

If相同I_best出现次数≥n_best, 结束, 输出I_best;

Else P(k+1):=P″(k);

3) Return输出当代种群最好个体.

个体I编码采用长度为N的单链编码方式, 如图 3所示, 其中N为任务总数, 位置i为第i个执行的任务, C_i为执行任务i的天车编号.解码过程就是根据I编码, 采用离散事件动态仿真方法执行任务的过程.

图 3(Fig. 3)

图 3 个体编码 Fig.3 Individual coding

初始种群生成步骤如下:① 令i=0, 生成[1, K]区间的随机整数, 填入位置i; ② 令i=i+1, 重复①, 直到满足i=N为止; ③ 重复①~② 直到P次, 生成初始种群.

采用概率为P_c的两点交叉算子对种群中两个体进行交叉操作.为了增加种群多样性, 根据式(10) 自适应地调整P_c, 控制种群中交叉次数.

(10)

其中:f为每次交叉个体最大目标函数值; f_max为种群最大目标函数值; f_avg为种群平均目标函数值; f_min为种群最小目标函数值.交叉算子描述如下:① 生成区间[1, N]的随机数i和j(i≠j); ② 交换父代个体S₁和S₂中区间[i, j]上的基因, 其他位置上基因保持不变, 生成子代个体S₁^′和S₂^′.

采用概率为P_m的变异算子对种群中个体进行变异操作.变异算子描述如下:① 生成区间[0, N]的随机整数i和j(i≠j); ② 交换父代个体S′中位置i和j上的基因, 生成子代个体S″.

本文提出一种改进的模拟退火局域搜索算法, 描述如下:① 初始化初始温度θ_max, 截止温度θ_min, 降温幅度△θ, 降温系数c.② 令交叉变异次数i=0, 当前温度θ_i=θ_max.③ 计算△=f(i+1)-f(i), 其中f(i)为第i次交叉和变异后种群中最好个体的目标函数值.若△＜0或△>0且exp(-△/θ_i)>random(0, 1), 接受第i次交叉和变异, 终止算法; 否则, 重新进行交叉变异.④ 令i=i+1, 改变退火温度, 使θ_i+1=θ_i-△θ_i.其中, △θ_i=c△θ, 当时, c=1;当t_i≤时, c=0.8，返回步骤③.⑤ θ_i＜θ_min, 终止算法.

本文第3节的MA应用C++语言编写, 运行于Windows7操作系统的Core2/2.67 GHz内存4GB的HP兼容机上.为了测试本文算法的性能, 设计了遗传算法(genetic algorithm, GA)进行对比.

板坯库内按照工作区域划分为6行, 相邻两行距离为20 m, 每行中有3个板坯垛.有2~3台天车在作业跨上工作, 天车的初始位置随机分配.天车运行速度为10 m/min, 安全距离为20 m.为了测试算法的有效性, 取国内某钢铁厂热轧计划下8组不同规模的板坯出库实际数据对算法进行测试, 每组算例参数见表 1.

表 1(Table 1)

表 1 算例参数设置 Table 1 Parameters setting 算例 天车数 板坯数 任务数 优先关系任务数 1 2 20 28 8 2 3 20 28 8 3 2 30 57 26 4 3 30 57 26 5 2 40 79 40 6 3 40 79 40 7 2 50 91 40 8 3 50 91 40

表 1 算例参数设置 Table 1 Parameters setting

GA采用3.1节介绍的编码和解码方式, 轮盘赌选择, 采用单点交叉算子和单点变异算子.参数设置如下:种群规模P=20, 迭代数G=20, 交叉率P_c=0.85, 变异率P_m=0.01.

本文MA参数设置如下:种群规模P=20, 迭代数G=20, 交叉率P_c=0.85, 变异率P_m=0.01, 初始温度θ_max=80 ℃, 截止温度θ_min=40 ℃, 降温幅度△θ=20 ℃, 降温系数c=1.

采用GA和MA分别对8组算例进行求解, 每组算例运行5次, 取其中最优结果.统计结果如表 2所示, 其中, T表示算法运行时间, O表示目标函数值.

表 2(Table 2)

表 2 两种算法实验结果对比 Table 2 Comparison of results of two algorithms 算例 GA MA T1/T2 O1/O2 T1/s O1 T2/s O2 1 0.73 65 0.74 65 0.99 1.00 2 1.32 60 1.46 59 0.90 1.02 3 3.18 82 3.28 81 0.97 1.01 4 5.51 76 6.23 74 0.88 1.03 5 7.41 129 7.56 127 0.98 1.01 6 11.36 123 13.51 119 0.84 1.03 7 6.38 93 6.75 92 0.95 1.02 8 7.52 88 8.67 85 0.87 1.04

表 2 两种算法实验结果对比 Table 2 Comparison of results of two algorithms

从表 2可以看出，两种算法均能在较短的时间内求得近优解, 随着问题规模的增大, 两种算法的求解时间相应增大.GA的求解时间均比MA的求解时间短, 但GA的求解结果均差于MA的求解结果.通过对比不同规模算例的求解结果得出结论:① 在天车数量保持不变的情况下, 增加任务数量, 板坯出库时间增大, 二者呈线性变化.② 在任务数保持不变的情况下, 增加天车数量可以降低板坯出库时间, 但降幅较小.因为过多天车导致空载增加, 干扰现象增多.③ 随着优先关系任务数与板坯数的比值增加, 导致每块板坯出库时, 天车执行倒垛任务次数增加, 造成板坯出库时间增长.④ 相比于GA, MA在个体搜索后, 嵌入局域搜索, 得到更好解的几率增大.⑤ 相比于GA, MA虽然每次迭代中搜索了更多的空间, 但同时也付出了更大的时间代价.

如图 4所示, 从最优值比较可以看出, GA曲线走势平缓, 经过几次小幅下降后收敛到最好解.而MA走势陡峭, 经过几次大幅下降之后, 才收敛到最好解.这是因为GA只有群体进化, 搜索空间有限, 容易陷入局部最优, 而MA在群体进化后都有局域搜索, 扩展搜索空间, 跳出局部最优的能力增强.从平均值比较可以看出, GA前期一直处于往复震荡状态, 最后趋于稳定.而MA一直处于平稳下降状态, 最后趋于稳定.这是因为GA中群体进化的盲目性, 没有一个定向搜索方向.而MA在群体进化后都有局域搜索, 在种群中最优个体牵引作用下, 由随机搜索转化为定向搜索.

图 4(Fig. 4)

图 4 每次迭代最优值比较和平均值比较 Fig.4 Comparison of the optimal values and the mean values for each iteration (a)—最优目标函数值；(b)—平均目标函数值.

图 5为两种算法求解算例1时每次迭代运行时间比较.MA每次迭代的时间均比GA长, 导致最后收敛时间比GA长.这是因为MA算法每次迭代都要进行局域搜索, 导致目标函数比较次数增多, 增加算法运行时间.

图 5(Fig. 5)

图 5 每次迭代运行时间比较 Fig.5 Comparison of the running time for each iteration

本文针对钢铁厂板坯库天车调度问题, 考虑了时空约束以及热轧计划的限制, 建立了天车调度优化模型, 采用MA算法对模型进行求解.针对问题的特点, 设计了编码和解码规则、自适应交叉算子、变异算子和模拟退火局域搜索算子.通过板坯库天车调度实际数据对模型和算法进行了测试, 并与GA的求解结果进行对比, 证明该算法是求解板坯库天车调度问题的一种有效算法.