基于改进粒子群算法的离散制造车间柔性调度优化*

黎书文，张成龙，周知进

(1.贵州理工学院 机械工程学院，贵阳 550003；2.茅台学院 酿酒工程自动化系，贵州 遵义 564500)

0 引言

随着计算机技术的发展，柔性机器人制造单元(Flexible Robot Manufacturing Cell, FRMC)[1]将工业机器人应用于传统的制造单元替代人工作业方式，通过中央控制计算机智能、高效完成制造过程中的搬运、安装、卸载等环节，如何进行柔性制造单元调度优化，提高生产效率成为研究的关键。

当前生产调度优化广泛应用于电子产品、钢铁冶金、航空航天等工业领域，是先进制造技术和现代管理技术的核心，能够实时响应车间环境变化，提高生产效率、降低生产成本，有利于实现柔性制造系统的高效生产，最终提高企业的经济效益。近年来，群体智能优化算法不断应用于优化车间调度问题，并取得了显著的效果。其中文献[2]提出一种基于混沌粒子群算法的多约束车间作业调度优化方法。文献[3]将蝙蝠算法与量子粒子群算法相结合，克服了粒子群算法收敛过早易陷入局部最优的缺点。文献[4-7]以柔性车间调度优化为目标，对粒子群算法进行改进，优化了机器、工艺路径，提高了车间作业调度的效率。但是上述研究求解模型较为理想，调度约束条件有限，与实际车间调度环境有一定的差异。

因此本文主要针对离散制造车间柔性调度优化，以提高生产线工作效率为目标，建立柔性调度多目标优化模型，并结合现有国内外研究基础，基于粒子群算法优化。针对基本粒子群算法求解过程中收敛性缓慢、稳定性低、易陷入局部最优等缺点，设计了一种改进算法，通过实验结果验证了算法的有效性，同时提高了提升了柔性车间调度的效率。

1 问题描述

1.1 离散制造现状分析

电子元器件等离散制造行业具有生产产品结构复杂，工艺流程多变，物流需求多样等特点，决定了行业生产计划、生产任务具有多变性以及不确定性，因此需要通过柔性机器人制造单元(Flexible Robot Manufacturing Cell, FRMC)等软件设施改进设备、物料供应、生产计划等加工要素的配置合理性，提高行业管理控制水平，促进行业智能化方向发展。

1.2 问题模型

柔性作业车间调度(Flexible Job-shop Scheduling Problem, FJSP)相比传统作业调度(Job-shop Scheduling Problem, JSP)更为接近生产实际，有利于合理安排生产计划和管理控制，直接关系到企业生产效益。

柔性作业车间调度问题模型可作如下描述[6]：假定：①待加工的工件集为{J1,J2, … ,Jn}，车间加工机床集为{Ml,M2, … ,Mm}，其中工件数为n，机床数为m；②每个工件加工工序不同、顺序固定，工序数为Pi，其中i=1, 2, … ,n；③Sijk、Eijk、mijk分别表示工件i的第j道工序在k号机床的开始加工时间、加工完成时间、加工消耗时间，其中k=1, 2, … ,m；④ck表示机床k运行时间，Cmax表示最后完工时间。柔性作业调度目标为均衡机床生产负荷下，合理分配工件加工工序设备，使得生产加工总时间最短，其目标函数为：

minCmax=min{maxck}

(1)

整个加工过程中每道工序可选择任一机床实施加工，整个加工制造过程中同一时刻仅能加工某一道工序，对于任意工序而言，须遵守循序渐进原则，前道工序加工完成才可开始此道工序的加工。因此需满足式(2)～式(4)约束条件：

Eijk-Ei(j-1)k≥mijk,1

(2)

Eabk-EijM≥mabk

(3)

EijM≥mijk

(4)

式(2)表示任一工件相邻加工工序满足顺序约束；式(3)表示任一机床同一时刻仅能加工某一道工序；式(4)表示任一工序加工完成时间应高于其加工消耗时间。

2 基本粒子群算法

粒子群算法(Particle Swarm Optimization, PSO)[8-9]主要用来对各类工业、经济和社会领域的多目标问题、约束问题、动态问题进行求解优化，最早是Russell Eberhart和James Kennedy两位博士在1995年提出。因其自身参数较少、原理简单、易于实现等优点，受到各领域研究人员的青睐，得到广泛的应用与发展。粒子群算法通过迭代进化，更新速度和位置进行空间搜索寻优，其中经典速度和位置更新公式为[10]：

vi(t+1)=ωvi(t)+c1r1(t)[Pi(t)-xi(t)]+
c2r2(t)[Pg(t)-xi(t)]

(5)

xi(t+1)=xi(t)+vi(t+1)

(6)

式中，i=1, 2, …,N，N表示粒子群种群规模大小；ω表示惯性权重因子；r1和r2为服从(0, 1)均匀分布的独立随机变量；c1和c2为非负常数，表示学习因子；xi=(xi1,xi2, … ,xiD)、vi=(vi1,vi2, … ,viD)分别表示粒子空间坐标位置向量和速度向量，vi∈[-vmax,vmax]；Pi=(Pi1,Pi2, … ,PiD)、Pg=(Pg1,Pg2, … ,PgD)分别表示粒子个体最优位置和种群最佳位置。

3 改进粒子群算法

3.1 稳定性分析

粒子群算法提出以来，众多国内外研究人员不断进行改进，试图提高算法性能。其中文献[11]从粒子群稳定性角度开展研究，对式(5)速度、式(6)位置更新公式进行分析，推导得出粒子的速度和位置变化过程的二阶差分方程式(7)、式(8)：

vi(t+2)+(c1+c2-ω-1)vi(t+1)+ωvi(t)=0

(7)

xi(t+2)-(1+ω-c1-c2)xi(t+1)+
ωxi(t)-c1Pi(t)-c2Pg(t)=0

(8)

因此从粒子种群稳定性出发，通过分析式(7)、式(8)二阶差分方程，得出粒子的速度、位置变化过程稳定的条件为1-ω>0且2ω+2-c1-c2>0。

3.2 改进算法设计

因此，根据粒子稳定性条件1-ω>0且2ω+2-c1-c2>0，为提高粒子全局寻优能力，避免算法陷入局部最优，结合惯性权重对粒子行为影响分析结果，提出一种惯性权重余弦自适应调整方法如式(9)所示：

ω(t)=0.1+0.9cos(t/maxgen)

(9)

惯性权重余弦自适应调整可以提高粒子行为的自适应性，算法运行初期具有较大的惯性权重，保证粒子的具有较高的行为发散性，加大搜索范围，提高全局寻优能力、避免算法陷入局部最优；算法运行过程中，惯性权重呈逐渐递减状态，集中粒子行为，减小搜索范围，有利于加速算法收敛，提高算法局部寻优能力。

为避免粒子陷入局部最优，提高粒子学习能力，根据上文所得粒子行为稳定性条件，基于文献[12]提出的学习因子伴随惯性权重自适应调整策略，对学习因子进行修正调整，得出自适应调整学习因子c1、c2公式如下：

(10)

因此，本文设计改进粒子群算法速度和位置更新公式为：

vi(t+1)=ω(t)vi(t)+c1(t)r1(t)[Pi(t)-xi(t)]+
c2(t)r2(t)[Pg(t)-xi(t)]

(11)

xi(t+1)=xi(t)+vi(t+1)

(12)

3.3 改进算法流程

本文设计粒子群算法主要流程如图1所示。

图1 改进粒子群算法流程

4 实验仿真

4.1 实验环境

为验证本文改进后的粒子群算法性能，在Win10/MATLAB(R2010b)实验平台，Intel(R) Core(TM) i5-6500 CPU@3.19GHz, 8.00GB RAM配置计算机64位操作系统下，设计了基于MATLAB的仿真程序，分别选取Kacem、MK等两个经典调度案例集进行仿真验证，并将改进算法的仿真结果与经典粒子群算法、模拟退火算法(Simulated Annealing, SA)的仿真结果进行了对比分析。

4.2 结果分析

本文改进粒子群算法(简称CPSO)、经典粒子群算法(简称PSO)、模拟退火算法(简称SA)三种算法参数设置如下，迭代次数maxgen统一设置为500。其中CPSO、PSO粒子种群规模N设置为50，CPSO惯性权重与学习因子设置分别选取式(9)、式(10)；PSO惯性权重设置为1，学习因子c1=2.05,c2=2.05。三种算法在Kacem、MK两个案例集中仿真实验对比结果分别如表1、表2所示。

表1 Kacem案例集仿真实验对比结果

表2 MK案例集仿真实验对比结果

因此通过表1、表2实验对比结果可以得出，本文改进粒子群算法相比经典粒子群算法、模拟退火算法具有较强的调度优化效果。其中MK01最佳调度结果甘特图如图2所示，最短完工时间为40。

图2 MK01最佳调度甘特图

同时通过图3中三种算法在工件数n=20，机床数m=4时调度优化的加工时间对比曲线可得出，PSO具有较快的收敛速度，但是收敛过早易陷入局部最优；SA全局寻优能力较强，但是运行初期寻优效果较差、收敛缓慢；CPSO提高了算法的全局寻优能力，避免了粒子早熟收敛、易陷入局部最优等缺点，提高了算法优化效果。

图3 三种算法对比曲线

5 结论

本文针对离散制造车间柔性调度优化策略进行研究，建立了一种面向离散制造模式的柔性调度模型，针对柔性调度模型优化求解问题，提出了一种惯性权重、学习因子自适应调整的改进粒子群算法，并进行了仿真实验对比验证。实验结果表明，本文改进算法在优化车间调度问题方面具有较快的收敛速度以及全局搜索能力，能够在一定程度上提升了柔性车间调度的效率，对于均衡企业生产计划与作业计划，提高企业服务质量有着较高的理论与实际价值。