, 刘士新1, 王佳2,31. 东北大学 信息科学与工程学院, 辽宁 沈阳 110819;
2. 东北大学 工商管理学院, 辽宁 沈阳 110169;
3. 东北大学秦皇岛分校 经济学院, 河北 秦皇岛 066004
收稿日期：2016-02-04
基金项目：国家自然科学基金资助项目(61573089, 61333006, 71601040)；河北省高等学校社科研究基金资助项目(SQ162004)。
作者简介：王旭(1982-)，男，辽宁沈阳人，东北大学博士研究生;
刘士新(1968-)，男，辽宁调兵山人，东北大学教授，博士生导师。
摘要：研究了钢铁企业板坯库天车调度问题, 考虑了时间和空间以及热轧计划等实际限制, 建立了一个板坯出库天车调度模型.针对天车调度问题具有实时性和不可交叉性的特点, 设计了基于优先关系的天车分配编码方式、离散事件动态仿真解码、自适应交叉算子以及在交叉和变异后进行模拟退火局域搜索的Memetic算法.通过某钢厂板坯出库过程中天车调度的实际数据对模型和算法进行仿真测试, 实验结果表明:该算法具有很高的收敛性和稳定性, 满足实际生产需要.
关键词：板坯库天车调度Memetic算法时空约束离散事件动态仿真
Memetic Algorithm for Crane Scheduling Problem in Slab Yard with Spatial and Temporal Constraints
WANG Xu1
, LIU Shi-xin1, WANG Jia2,31. School of Information Science & Engineering, Northeastern University, Shenyang 110819, China;
2. School of Business Administration, Northeastern University, Shenyang 110169, China;
3. School of Economics, Northeastern University at Qinhuangdao, Qinhuangdao 066004, China
Corresponding author: WANG Xu, E-mail:45065706@qq.com
Abstract: Crane scheduling problem was researched for slab yard in steel plant. Considering the time and space as well as the hot rolling, a crane scheduling model for slab yard was established. According to the characters of real-time and non-crossing for the problem, a Memetic algorithm was designed to solve it, including the crane allocation rule based on the priority relation, the decoding rules based on discrete event dynamic simulation(DEDS), adaptive crossover operator and simulate annealing global search after each crossover and mutation. Simulation experiment was performed with data by crane scheduling for slab out, and the results of simulation experiments showed that the proposed algorithm has high convergence speed and stability, which meets actual production demand.
Key Words: slab yardcrane schedulingMemetic algorithmspatial and temporal constraintsdiscrete event dynamic simulation
板坯库天车调度属于多机多任务调度问题, 由于多台天车在同时执行多个任务, 且天车执行任务中受垛位布局、工艺流程、作业干涉等约束限制, 使板坯库天车调度问题成为典型的组合优化难题, 无法用一个有效的算法在多项式时间内求出最优解[1].
目前, 针对天车调度问题的研究主要集中在集装箱码头天车调度问题[2-4]和制造车间天车调度问题[5-6], 而对冶金行业, 尤其是板坯库天车调度问题研究较少.赵宁等[7]研究了板坯库天车作业具有随机性的问题, 建立了天车作业仿真模型, 采用基于Agent技术的循环仿真方法对模型进行仿真优化, 通过原始仿真模型和改进仿真模型的循环转换以及多档模糊评判寻求优化解.王旭等[8]研究了炼钢-连铸过程中天车调度问题, 考虑时间和空间约束, 建立了天车调度模型, 采用Memetic算法对模型进行求解.Tang等[9]研究了钢厂冷轧车间罩式退火的单天车调度问题, 建立了以最小化钢卷堆垛时间为目标的混合整数规划模型, 采用两阶段算法对模型进行求解.Tanizaki等[10]研究了炼钢过程中多阶段天车调度问题, 考虑天车作业干涉, 建立了天车调度混合整数规划模型, 采用启发式算法对模型进行求解.
以上研究成果通过为每个天车分配任务避免天车出现干扰, 然而没有考虑出现干扰时天车避让情况.本文在已知轧制计划条件下, 根据板坯库的垛位布局, 考虑执行板坯出库任务中的板坯倒垛、天车避让等实际情况, 建立以最小化板坯出库时间为目标的板坯库天车调度模型, 设计了一个Memetic算法(Memetic algorithm, MA)对模型求解.
1 问题描述如图 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.)有开始位置lsi和结束位置lei, 并且要在其时间窗[tei, tli]内完成.天车集合Ψ, 包括K台天车, 天车k的起始位置lk0、吊起和放下板坯的时间μ以及运输板坯的速度v是预先给定的, 且沿垂直作业跨方向的作业由天车上小车完成, 可将小车运动时间归入天车作业时间.因此, 任务i的处理时间ti=2·μ+|lei-lsi|/v.类似地, 任务i的结束位置和任务j的开始位置之间的距离dij, 也可以预先计算出来.在任务开始时刻, 指派天车执行任务，天车执行完任务后, 从当前任务的结束位置以速度v空载到下一任务的开始位置.目标函数为最小化板坯出库的完成时间.
2 数学模型为了清晰表达上面描述的问题, 建立天车调度非线性整数规划模型.引入如下符号:
Ω为出库计划中任务集合, Ω={1, 2, …, N}，N为任务数; Γ为任务之间优先级集合, (i, j)∈Γ表明任务i必须在任务j之前执行; Ψ为天车集合, 按照从左到右的顺序依次进行编号, Ψ={1, 2, …, K}; K为天车数; lk0为天车k的开始位置; lsi为任务i的开始位置; lei为任务i的结束位置; tei为任务i的最早开始时间; tli为任务i的最晚结束时间; ti为任务i的处理时间(包括天车吊起、运行和放下板坯的时间); v为天车运行速度; δ为天车之间的最小距离, 即需要保持的安全距离; dij为天车从任务i的结束位置到任务j的开始位置的距离; Tmax为计划展望期; M为足够大的正数.
决策变量:tfi为任务i的结束时间; xk(t)为天车k在时刻t的位置.
 |
 | (1) |
 | (2) |
 | (3) |
 | (4) |
 | (5) |
 | (6) |
 | (7) |
 | (8) |
 | (9) |
3 MA设计本文MA分别采用遗传算法和模拟退火算法作为群体进化方法和局域搜索方法.具体步骤如下:
1) 参数初始化:种群规模P, 迭代代数G, 当前最优个体Ibest, 相同最好解出现次数nbest, 保持前代最好解数量nf, best, 初始温度θmax, 终止温度θmin, 温降系数c, 温降幅度△t;
2) 初始化种群P(1), 令P′(1):=?;
For k=1 To G
?For i=1 To P/2
??采用轮盘赌方式从P(k)选择两个个体S1和S2;
??应用自适应交叉算子从S1和S2构造两个新个体S1′和S2′;
??应用变异算子从S1′和S2′构造两个新个体S1″和S2″;
??对S1″和S2″分别应用SA局域搜索得到个体S1l和S2l;
???P′(k):=P′(k)∪{S1l, S2l};
??从P′(k)中选择最好个体作为Ibest, 从P(k)∪P′(k)中选择最好的nf, best个个体, 从P(k)∪P′(k)中采用轮盘赌方式选择(P-nf, best)个个体, 生成P″(k);
If相同Ibest出现次数≥nbest, 结束, 输出Ibest;
Else P(k+1):=P″(k);
3) Return输出当代种群最好个体.
3.1 编码和解码个体I编码采用长度为N的单链编码方式, 如图 3所示, 其中N为任务总数, 位置i为第i个执行的任务, Ci为执行任务i的天车编号.解码过程就是根据I编码, 采用离散事件动态仿真方法执行任务的过程.
图 3(Fig. 3)
 | 图 3 个体编码Fig.3 Individual coding |
3.2 初始种群的产生初始种群生成步骤如下:① 令i=0, 生成[1, K]区间的随机整数, 填入位置i; ② 令i=i+1, 重复①, 直到满足i=N为止; ③ 重复①~② 直到P次, 生成初始种群.
3.3 交叉算子采用概率为Pc的两点交叉算子对种群中两个体进行交叉操作.为了增加种群多样性, 根据式(10) 自适应地调整Pc, 控制种群中交叉次数.
 | (10) |
3.4 变异算子采用概率为Pm的变异算子对种群中个体进行变异操作.变异算子描述如下:① 生成区间[0, N]的随机整数i和j(i≠j); ② 交换父代个体S′中位置i和j上的基因, 生成子代个体S″.
3.5 局域搜索算子本文提出一种改进的模拟退火局域搜索算法, 描述如下:① 初始化初始温度θ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△θ, 当
4 算例设计及结果分析本文第3节的MA应用C++语言编写, 运行于Windows7操作系统的Core2/2.67 GHz内存4GB的HP兼容机上.为了测试本文算法的性能, 设计了遗传算法(genetic algorithm, GA)进行对比.
4.1 算例设计板坯库内按照工作区域划分为6行, 相邻两行距离为20 m, 每行中有3个板坯垛.有2~3台天车在作业跨上工作, 天车的初始位置随机分配.天车运行速度为10 m/min, 安全距离为20 m.为了测试算法的有效性, 取国内某钢铁厂热轧计划下8组不同规模的板坯出库实际数据对算法进行测试, 每组算例参数见表 1.
表 1(Table 1)
 表 1 算例参数设置Table 1 Parameters setting
| 表 1 算例参数设置 Table 1 Parameters setting |
4.2 对照算法GA采用3.1节介绍的编码和解码方式, 轮盘赌选择, 采用单点交叉算子和单点变异算子.参数设置如下:种群规模P=20, 迭代数G=20, 交叉率Pc=0.85, 变异率Pm=0.01.
4.3 算法对比分析本文MA参数设置如下:种群规模P=20, 迭代数G=20, 交叉率Pc=0.85, 变异率Pm=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
| 表 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 |
5 结论本文针对钢铁厂板坯库天车调度问题, 考虑了时空约束以及热轧计划的限制, 建立了天车调度优化模型, 采用MA算法对模型进行求解.针对问题的特点, 设计了编码和解码规则、自适应交叉算子、变异算子和模拟退火局域搜索算子.通过板坯库天车调度实际数据对模型和算法进行了测试, 并与GA的求解结果进行对比, 证明该算法是求解板坯库天车调度问题的一种有效算法.
参考文献
| [1] | Dohn A, Clausen J. Optimizing the slab yard planning and crane scheduling problem using a two-stage heuristic[J].International Journal of Production Research, 2010, 48(15): 4585–4608.DOI:10.1080/00207540902998331 |
| [2] | Matsuo H, Shang J S, Sullivan R S. A crane scheduling problem in a computer-integrated manufacturing environment[J].Management Science, 1991, 37(5): 587–606.DOI:10.1287/mnsc.37.5.587 |
| [3] | Kim K H, Park Y M. A crane scheduling method for port container terminals[J].European Journal of Operation Research, 2004, 156(3): 752–768.DOI:10.1016/S0377-2217(03)00133-4 |
| [4] | Jung S H, Kim K H. Load scheduling for multiple quay cranes in port container terminals[J].Journal of Intelligent Manufacturing, 2006, 17(4): 479–492.DOI:10.1007/s10845-005-0020-y |
| [5] | Tamaki H, Murao H.Simulation-based optimization model and meta heuristic solution of multiple crane scheduling problem[C]// IEEE International Conference on Systems, Man and Cybernetic.Shanghai, 2004:1469-1472. |
| [6] | Liu P, Tang L X.The refining scheduling problem with crane non-collision constraint in steelmaking process[C]// IEEE International Conference on Automation and Logistics.Qingdao, 2008:536-541. |
| [7] | ZhaoNing, DuYan-hua, DongShao-hua. Optimization of crane scheduling in slab yard based on cycle simulation[J].Systems Engineering—Theory & Practice, 2012, 32(12): 2925–2830. |
| [8] | WangXu, LiuShi-xin, WangJia. Memetic algorithm for crane scheduling problem with spatial and temporal constraints[J].Journal of Northeastern University(Natural Science), 2014, 35(2): 191–194. |
| [9] | Tang L X, Xie X. Scheduling of a single in batch annealing process[J].Computers and Operation Research, 2009, 36(10): 2835–2865. |
| [10] | Tanizaki T, Tamura T, Sakai H. A heuristic scheduling algorithm for steel making process with crane handling[J].Journal of the Operations Research Society of Japan, 2006, 49(3): 188–201.DOI:10.15807/jorsj.49.188 |
