粒子群遗传算法在盘卷精整系统调度中的应用

吴翔

盘卷精整系统是典型的柔性制造系统，工艺段较多、回路控制复杂、有较多生产约束。本文提出采用粒子群遗传算法求解盘卷精整系统的调度策略问题。通过Matlab平台设计了基于粒子群遗传算法的盘卷精整系统仿真器。通过实例测试，证明了粒子群遗传算法适用于盘卷精整系统的求解，具有高效率及高稳定性。

【关键词】柔性制造系统 盘卷精整系统 粒子群遗传算法 Matlab仿真

高速线材是钢铁企业中附加值较高的产品，广泛应用于路桥、基建与房地产建设。高速线材的生产工艺可以分为轧制段与精整段。轧制段工艺比较独立，设备通常都是由前至后排布，钢材在设备间高速通过，完成轧制工艺。精整段工艺位于轧制段之后，旧的工艺为单一环路布置，处理设备依次分布在环形输送线上，卷芯架或C型勾输送钢材在设备间流转。旧工艺原理简单、效率低，不适用于多品种、混合生产。近年来，业界提出多环路的盘卷精整系统布局，设备分布于不同的环路上，环路之间可以相互流转。多环路盘卷精整系统满足钢铁企业多品种、混合生产的需求，在增加产能的同时，提高设备利用率。而多环路盘卷精整系统是典型的柔性制造系统，具有处理工序多、输送路径多、转运灵活、控制策略复杂等特点。

由于多环路盘卷精整系统的这些特点，該类系统的调度问题体现出极高的复杂性，引起了学界的重视。学术界提出了很多不同方法。黄学文在《用蚁群算法集成求解多加工路线柔性车间调度问题》中提出用蚁群算法来求解调度问题，算法较新颖，结果也不错。张静在《混合粒子群算法求解多目标柔性作业车间调度问题》中提出混合粒子群算法，效率较高，有一定参考意义。近年来启发式算法在该领域内有很大发展.其中粒子群算法具有编码容易实现、代际间存在记忆能力等优点。但缺点是算法不稳定容易过早收敛。遗传算法具有运算并行性好、编码相对简单，但缺点是收敛速度慢，效率低，容易陷入局部最优。本文提出将粒子群算法与遗传算法相结合，组合为粒子群遗传算法，并将其应用于盘卷精整系统的调度控制问题。

1 盘卷精整系统的数学模型

1.1 盘卷精整段生产工艺与流程

盘卷精整系统的产品有3种类型：普碳钢、马氏体钢及奥氏体钢。普碳钢没有经过任何炉体缓冷，通过转运系统直接打捆、称重，进入仓库。马氏体钢需要在钢体表面生成一层表面晶体，所以在风冷段后需经过马氏体缓冷炉，奥氏体钢则相应需要经过奥氏体缓冷炉。盘卷精整系统主要生产过程如图1所示。

从生产过程可以看出，整个盘卷精整系统有5道工艺流程，第一、第二道工序为钢卷的缓冷处理，钢卷的种类决定了前两道工序的路径。第三、四、五道工艺流程各有2套设备，设备功能相同，可以互用。这里设定工件总数为10，相应的算例为10X5。按照实际的生产经验、设计相应工序约束矩阵J10和加工时间矩阵T10如下：

1.2 模型变量定义

为了更好描述盘卷精整系统的数学模型，这里约定模型的变量。如表1所示。

1.3 数学模型搭建

盘卷精整系统建模优化的目标是：在满足生产约束的条件下确定所有工件的输送路径及投入系统的顺序，为每台机器确定工件的投入加工顺序，为每个工件的每道工序确定加工机器，最小化盘卷精整系统的生产完工时间。

出于方便求解，便于建模考虑。约定模型遵从如下假设：

（1）所有机器在t=0时均是正常可用的，在加工过程中不存在故障导致停机。

（2）不同工件之间具有相同的优先级。

（3）所有工序在不同机器上均按照时间约束矩阵执行，在加工过程中不存在超时或提前完成。

（4）所有机器在生产过程中只能加工一个工件。

（5）工件的加工过程中不允许中断，连续完成该工艺。

（6）所有工件必须按照机器约束矩阵按照顺序加工，在加工过程中不存在改变工序顺序或跳过某一工序。

（7）启动机器的时间和切换工序的时间被忽略。

在符合如上假设及约束下，建立数学模型如下：

1.3.1 数学模型的目标函数

2 粒子群遗传算法求解盘卷精整系统调度问题

2.1 粒子群遗传算法的定义与特点

遗传算法是较早提出，在业界应用广泛。遗传算法的优势在于遗传操作和编码技术相对其他算法简单，个体之间经过交叉、变异和选择操作后，能够保留最优的基因。但遗传算法并非完美，也存在不少缺点：当问题的规模较大时，搜索空间会相应增大，算法搜索时间也会延长。

粒子群算法作为一种新的启发式算法，由于其具有简单的概念、容易编程实现、运行效率高等优点。但由于初始粒子群是随机产生的，粒子群分布较广，导致该算法在前期迭代中搜索效率很低。

为了克服粒子群算法和遗传算法各自的缺点，发挥各自的长处。本文提出以粒子群算法为框架引入遗传算法的选择、交叉、变异等操作的粒子群遗传算法。新的算法可以防止搜索的过早收敛、跳出局部最优，在保证效率的同时找到更符合期望的最优解。

2.2 粒子群遗传算法的步骤

粒子群遗传算法的基本流程如图2所示。

2.3 粒子群遗传算法在盘卷精整系统输送控制策略的仿真

基于Matlab2.4b进行算法编写。针对工件总数为10的工序约束矩阵J10和加工时间矩阵T10进行仿真，在迭代100次后得到最优解收敛曲线如图3所示。

从图3可以看出，粒子群遗传算法在算法迭代3次后就收敛于最优解91，即所有工件完成所有工序的最短时间为91。

为了更好的比较算法性能，用遗传算法、粒子群算法及粒子群遗传算法基于工件总数为10的算例进行10次计算，三种算法的仿真结果比较如表2。

遗传算法、粒子群算法及粒子群遗传算法均可达到91的最优解，说明在问题规模较小时，三种算法均具有有效性。平均最少迭代数上粒子群遗传算法最小，粒子群次之，遗传算法最高，说明算法效率上粒子群遗传算法最好。平均偏差上三种算法均低于3%，但是粒子群遗传算法平均偏差为0，说明结果最稳定。综合来看，粒子群遗传算法既满足盘卷精整系统的调度控制问题求解，同时有更高的稳定性。

3 结束语

针对盘卷精整系统的调度问题的复杂性，考虑不同算法的优缺点，本文提出将粒子群算法和遗传算法相结合，利用粒子群遗传算法求解盘卷精整系统的调度策略。考虑到粒子群算法收敛速度快的优点，粒子群遗传算法前期采用粒子群算法筛选优化种群空间。之后植入遗传算法，在已经优化过的解空间内，利用遗传算法的变异能力、全局收敛性等优点寻找种群的最优解。通过不同工件数量的算例测试，证明本文提出的算法能够有效地解决盘卷精整系统的调度问题。

参考文献

[1]吴正佳，付先旺，望芸，刘秀凤.求解FJSP的改进元胞粒子群算法[J].三峡大学学报（自然科学版），2017，39（03）：84-88.

[2]黄学文，张晓彤，艾亚晴.用蚁群算法集成求解多加工路线柔性车间调度问题[J/OL].计算机集成制造系统，2017.

[3]屈迟文，傅彦铭，罗明山，林承徳，何伟.求解柔性作业车间调度问题的鸟群算法[J/OL].计算机工程与应用，2017.

[4]梁文杰，王桂棠，陈志盛，吴佳毅.基于混合粒子群算法的汽车零件精冲车间调度研究[J/OL].机电工程技术，2017（09）：6-10.

[5]张静，王万良，徐新黎，介婧.混合粒子群算法求解多目标柔性作业车间调调度度问题[J].控制理论与应用，2012，29（06）：715-722.

[6]白起琛.基于混合粒子群算法多目标柔性作业车间调度问题研究[D].哈尔滨工业大学，2010.

[7]Fattahi P，Fallahi A （2010） Dynamic scheduling in flexible job shop systems by considering simultaneously efficiency and stability.CIRP J ManufSciTechnol 2（02）：114-123.

作者单位

上海交通大学自动化系 上海市 200240