基于遗传算法的板坯入库梁式起重机调度优化

大连理工大学机械工程学院 大连 116024

0 引言

梁式起重机(以下简称天车)被广泛应用于集装箱码头、制造业企业车间等场合。随着2025智能制造的发展，天车在制造业车间中发挥着愈发重要作用，科学合理的天车调度可大大提高作业效率，能最大化利用企业的资源，是智能车间的发展方向[1]。在连铸-热轧炼钢工艺中，天车是核心的起重运输设备。在板坯车间，天车调度是指在满足天车运行空间约束和天车资源约束的条件下，合理分配天车完成板坯的吊运任务，保证连铸区生产任务有序、紧凑的进行，使整体吊运效率与生产目标一致[2]。目前，天车调度问题大多针对码头集装箱的调度[3-5]和制造车间的天车调度，而在连铸-热轧车间的板坯库内的天车调度问题研究较少，实际作业更多依赖调度人员的经验，资源浪费严重。

本文以某大型炼钢厂的连铸-热轧车间的存储车间（以下简称板坯车间）为研究对象，对天车进行合理的调度安排，提高连铸车间的产能，同时提高存储车间的存放量。板坯存储车间是连铸板坯的成品外卖车间同时也是热轧工艺的原料车间。因此，对板坯存储车间的天车合理调度进行研究，能够更好地利用车间内的仓储空间，提高车间的仓储量。在板坯车间内，同一作业跨的轨道上有多台规格同类和不同类型的天车，由连铸作业跨铸造的板坯经辊道运输至板坯库进行储存或者先进行存放等待进一步的热轧工作，需要天车进行搬运作业。受板坯规格不同的影响，天车的运输任务就会多样复杂化，且经常会出现多块板坯进行同时运输的情况，搬运任务无论是在时间上还是在空间上都有很强的随机性，导致天车在作业过程中容易产生冲突，所以板坯在辊道上运至作业跨时，需要对天车进行合理的调度安排。

本文运用遗传算法对天车的板坯入库任务进行分配，可避免天车之间的作业干扰，提高天车的作业效率，有序及时地将辊道运来的板坯进行入库吊运作业。

1 板坯库的概况

图1为某连铸-热轧工厂的板坯车间的其中一跨的布局图，跨位上有数台天车，且只能在同一跨位上进行吊运作业，在仓库的长度方向上同一跨内分为五个作业区，同作业跨的方向，每个作业区会分为若干行，每行上会有两个板坯垛，板坯垛的方向与大车作业方向垂直，需将连铸区生产的板坯经辊道运输至仓储板坯库，选择合适的天车将板坯从辊道上起吊放置在合适的垛位上。

经典的天车调度问题是指：N个工件在M台机床上加工，并且工件的加工顺序及加工时间确定，一个工件同一时刻只能在一台机器上加工，且开始加工后不能中断。因此，可将板坯车间的天车调度问题进行经典调度问题转化，设辊道上来的板坯数M，板坯库内作业天车为N，要将M个板坯用N台天车进行入库吊运，将天车看成机床，入库的板坯看成待加工的工件，每块板坯需要天车吊运一次，并且入库作业进行一次即可。

图1 板坯库某一跨布局简图

1.1 问题描述

给定一个板坯的入库计划M，包括M个板坯吊运任务，板坯吊运任务i（i＝1,2，…，M）由板坯入库的辊道位置Lsi开始和入库的垛位位置Lfi结束，并且要求板坯i在相应的起始时间（Lsi，Lfi）内完成。作业天车的集合为N，包括N台天车，天车k的起始作业位置Lk0,板坯的起吊时间α和放置库内垛位的时间β，以及天车的运输速度v都是根据天车的性能不变的，并且将板坯入库时在垂直方向上的运输时间规划至大车的运输时间内。因此，板坯吊运任务i的处理时间Ti＝α+β+|Lfi-Lsi|/v。同样的，板坯吊运任务i的垛放位置和下一个板坯吊运任务j的开始起吊位置的距离Dij亦可以提前计算出来，在吊运任务i开始的时刻指派相应的天车去吊运，天车吊运板坯任务i后，由板坯吊运结束位置垛位以天车自身运输速度v空载运行至下一块吊运板坯位置处，即板坯入库的辊道处。目标函数为最小化板坯的入库完成时间。

1.2 数学模型

仓储板坯车间的调度问题可以描述为M个待吊运的板坯被N台天车吊运的，其数学模型为：

1）板坯集M＝{M1, M2, …, Mm}，Mi为第i块待吊运的板坯，i＝1，2，…，M ；

2）天车集N={N1, N2, …, Nn}，Nj为第j台作业天车，j=1, 2, … , N ；

其他相关参数：Ψ为吊运板坯之间的优先级集合，表示Mi吊运任务必须在Mj吊运任务之前进行完成，天车集包含有图1中沿X轴正方向依次编号N={1, 2, …, N }，N为跨内天车总数，Lk0为天车k开始作业前的起始位置；Lsi、Lfi为吊运任务i的起始结束作业位置；Lsi、Lfi为任务i的起始、放置作业时间；v为天车的运输速度；δ为保证相邻天车在作业过程中不会发生碰撞危险的最小安全距离；Dij为任务i完成结束后再次到达任务j开始的位置的距离；Tm为计划完成时间；Z为比较大的一个常数，作为任务约束的一个系数。

模型决策因素：tfi为板坯吊运任务i的期望完成时间；Xk（t）表示t时刻天车k在作业跨上的位置。

Yijk取值1表示天车吊运板坯i后吊运下一块板坯j，进行连续的吊运作业；取值0表示天车吊运板坯i后未有下一吊运任务。

建立车间板坯调度模型为

其中，式（1）为目标函数板坯最小入库完成时间；式（2）和式（3）表示板坯的入库作业只能由一台天车吊运一次；式（4）为天车作业中的速度约束；式（5）表示同一作业跨上相邻的两台作业天车的最小距离要大于完全距离，避免相邻天车发生碰撞事故 ；式（6）和式（7）为时间约束，要求板坯的开始吊运时间和吊运过程使用的时间要在板坯的最后计划时间前完成；式（8）表示板坯i的吊运要在板坯j吊运之前完成；式(9)为定义的相应变量的取值范围。

2 遗传算法（GA）设计求解

本文采用遗传算法（GA）作为群体进化方法，进化步骤为：

1)对参数进行初始化设置：假设种群的规模为S，迭代K次完成群体的进化，得到当前群体的最优解Xb，并且种群收敛于最优解，最优解出现的次数Nb，保持上一代的最优解数量Nf，b。

2)对种群进行初始化设置：S（1），设置S′（1）：＝Ø；

For k＝1：K

For i＝ 1：S/2

3）返回输出当代最好的。

2.1 群体的编码和解码

个体s的编码采用单链式编码的方式，取编码的长度为N，如图2所示，其中M为需要入库的板坯的总数，也代表着吊运的任务总数，位置i为第i个需要吊运入库的板坯吊运任务，Ni为吊运板坯i的天车编号。解码的过程就是根据个体s的编码，运用离散事件动态仿真方法执行吊运任务的过程。

图2 个体编码

2.2 初始种群的产生

1)令i＝0，生成[1，N]内的随机数，填入对应的i的位置；

2)令i＝i+1，重复步骤1），填入对应的下一位置，直到满足i＝N，保证每台天车都已填入位置；

3)不断地重复步骤1）和步骤2）直到S次，生成初始种群。

2.3 交叉操作

种群通过交叉操作获得新的染色体，从而实现种群的进化。为了增加种群的多样性，设置一个交叉概率为Pc的交叉算子，并根据式（10）进行自适应的调整，以控制种群的交叉操作。

式中：f为每次个体交叉中最大的目标函数值，fmax、fmin、favg为所随机产生的初始种群中最大、最小和平均目标函数值。交叉算子指在父代的两个个体的编码中，随机选中编码中同一位置的编码，对应位置的编码进行交换，其他位置上的编码不变，形成两个新的子代个体 s＇1和 s＇2。

2.4 变异操作

种群的进化过程中，种群中的个体会出现染色体变异的情况，因此，在求解过程中添加概率为Pm的变异算子，对个体进行变异操作。变异算子是指在当代个体的染色体编码中，有些位置的基因发生突变形成新的变异子代个体s″。

3 算例设计及仿真结果分析

根据实地考察板坯库，板坯库内的工作区域每跨划分成两行垛位，相邻两行垛位的距离为5 m，跨位上有2～3台天车进行板坯的吊运作业，天车在作业跨上作业的起始位置随机设置，天车的运行速度设定为10 m/s，相邻天车间的安全距离为5 m。取该板坯车间8组不同的板坯入库数据，进行仿真测试天车的调度算法设计。算例参数见表1。

表1 算例参数设置

遗传算法（GA）采用个体编码、解码的方式进行编码、解码操作；运用轮盘赌的方法进行选择，采用交叉算子和变异算子进行种群的进化，增加种群的多样性。对遗传算的参数进行设置：种群规模S＝20，进行迭代的次数K＝20，交叉概率Pc＝0.85，变异概率Pm＝0.01，对8组算例进行求解，每组算例运行5次，取其中最优的结果。表2所示，其中，T为算法运行的时间，O为每个算例得到的目标函数的值。

表2 算例的仿真结果

从表2的运行结果中可知，遗传算法能在较短的时间内求得目标函数比较接近的优解，但是随着种群规模的增大，算法的时间也随之加长，二者成正比例的关系，通过对比8个算例的运行结果可以得出结论：1）作业跨上的天车数量保持不变，增加板坯的入库数量，板坯入库的时间就随之增大，二者呈正相关。2）当入库的板坯数量不变的时候，作业跨上的天车增多能够降低板坯入库的时间，但是降低的时间不太显著，这是因为天车运行之间出现干扰，使天车出现较多的空载或被动运输。

如图3所示，遗传算法（GA）的目标函数值迭代曲线在设定的迭代次数内能够平缓的收敛于最优值；而平均函数值在前期会处于震荡的趋势，在迭代到种群规模的最后收敛于最优平均值。

图3 目标函数的最优迭代值和平均迭代值

4 结论

针对钢铁连铸-热轧之间的板坯车间的天车调度问题，对板坯的入库建立作业天车调度的仿真模型，并进行算例的仿真分析。运用遗传算法（GA）对仿真模型进行求解，对板坯入库的特点，进行遗传算法的交叉、变异等操作，对板坯入库的模型进行测试，证明遗传算法能够有效地解决天车调度的问题。