改进PSO-GA算法求解混合流水车间调度问题

于 蒙 刘德汉

(武汉理工大学物流工程学院 武汉 430063)

0 引 言

随着现代制造企业生产规模和生产水平的不断提高，带了一系列的调度难题.如何通过科学而高效的手段安排生产计划、利用现有资源提高工厂产能成为企业关注的热点问题.混合流水车间调度(hybrid flow shop problem,HFSP)是车间调度领域中一个经典问题，其广泛存在于各流水式生产线.HFSP要求在每道工序加工机器不定的情况下，工件在加工之前就确定加工顺序，这使得该问题比传统的流水车间调度问题(flow shop problem,FSP)具有更高的复杂度.同时在调度过程中，企业不同的部门从各自的需求出发，对生产调度决策目标会有多样化的要求，因此需要结合实际的生产情况和不同的需求，同时考虑多个目标进行优化.

目前对多目标HFSP问题的研究主要集中在采用启发式算法、元启发式算法或多个元启发式算法的混合算法求解不同的目标上.Arroyo等[1]较早的针对多目标流水车间调度问题提出了一种遗传局部搜索算法；Kachitvichyanukul等[2]提出了一种两阶段的遗传算法来求解多目标车间调度问题；张超勇等[3]基于遗传算法对非支配排序进行了改进，并将算法应用于柔性流水车间优化问题的求解；陈园园等[4]将PSO优化GA算法应用到离散型流水车间调度的求解.HFSP领域的大量文献表明当前该问题仍需针对不同的求解目标在算法上进行改进，而求解过程中，算法收敛速度与跳出局部最优之间存在对立.

文中通过对汽车制造生产线进行调度优化，将制约成本指标的机器负荷及制约效率指标的交货拖期时间最短作为优化目标建立了多目标优化数学模型，并通过改进型PSO-GA算法作为全局优化算法对一条典型汽车生产线进行了优化，该算法提高了收敛速度并有着较好的跳出局部最优的能力.

1 多目标混合流水车间调度模型建立

1.1 模型描述

混合流水车间是一类常见的制造环境，其模型示意见图1，n个工件(J1,J2,…,Jn)需要在m道工序(Z1,Z2,…,Zm)上顺序进行加工，每个工序有若干个并行的同速加工工位，工件在每个工位上加工时间不一定相同，工序间缓冲区无库存限制，要求确定工件加工顺序及其在并行机上是如何进行分配的，最终目标是使得模型满足实际生产需求.

对混合流水车间做以下假设：①一台机器同一时刻只对应一个工件的加工过程；②一个工件同一时刻不能在不同机器上加工；③每个工序的准备时间与顺序无关，且直接计入加工时间中；④不考虑急件和故障等非确定因素.

图1 混合流水车间示意图

模型中涉及到的参数见表1.

表1 模型参数表

建立0-1混合整数规划模型，主要约束条件如下.

i=1,2,…,n;j=1,2,…,m

(1)

i=1,2,…n;j=1,2,…m;r=l+1

(2)

Cij≤Biv

i=1,2,…n;j=1,2,…m-1;v=j+1 (3)

(4)

i,p=1,2,…,n;j=1,2,…,m;r=p+1 (5)

式(1)表示工件的一道工序只能由唯一一台机器完成；式(2)表示工序不可中断；式(3)表示工件下一工序的开始时间大于等于当前工序的结束时间；式(4)表示约束机器能力，确保任意时间在某工序加工的工件数不超过该工序并行机器数；式(5)表示一个工件选择完机器后，下一个工件才能选择.

1.2 模型评价指标确立

主要考虑的调度性能指标为机器负荷及总拖期时间.将每个工位的总加工时间与所在工序各机器平均总加工时间做方差，以此作为衡量机器负荷平衡的指标f1.

(6)

使用总拖期最小来代表交货期的时间最短，作为另一个目标函数f2.

(7)

通过权向量w将多目标问题转换为单目标，取

(8)

综合目标评价函数f为

f=w1f1+w2f2

(9)

2 改进PSO-GA算法设计

遗传算法(genetic algorithm,GA)是参照自然界优胜劣汰进化法则而诞生的一种进化算法.遗传算法的优点在于优良的全局搜索与并行搜索能力，对于大型复杂问题常常有很好的求解效果.粒子群算法(particle swarm optimization,PSO)是模仿自然界中鸟类寻找食物的过程而产生的一种算法，粒子群算法常常由于其粒子更新达到停滞状态而容易陷入局部最优.遗传算法在搜索精度与信息保留问题上有较多改善空间，且算法后期收敛速度上常常比较缓慢.为了克服两者的缺点，利用粒子群算法收敛速度快、效率高的特点进行初步寻优，再利用遗传算法全局搜索的优势进行种群的筛选，并通过在遗传算法的基础上引入新参数,动态地控制迭代交叉变异比，进而达到提高群体多样性的目的.算法流程图见图2.

图2 改进PSO-GA算法流程图

2.1 染色体编码与解码操作

HSF问题常采用基于工序和机器的编码方式，本文采用编码的前半段确定工件加工的顺序，比如,对于一个三个工件的FSP问题，13212132中第h(0

2.2 适应度计算

为了设计适应度函数，通过权向量将多目标问题转换为单目标，并进行无量纲化处理.

(10)

式中：fi为不同目标函数，i为1或2时分别对应机器负荷指标及总拖期时间指标；fimin、fimax分别为初始种群中当前目标函数的最大与最小值.

适应度函数应同向于优化方向，机器负荷越不均衡、总拖期时间越长时，均与优化方向相反，故适应度函数设置为

(11)

2.3 粒子群寻优操作

采用标准粒子群算法进行初步的搜索，粒子的速度更新、位置更新规则如下

vid(t+1)=w×vid(t)+c1×r1×

(12)

xid(t+1)=xid(t)+vid(t+1)

(13)

粒子群每次更新都舍弃不可行解，将部分较优解保留并替代原种群中对应数目的较劣解.这一更新种群的方式称为迁移，借鉴了生态学的概念[5].

2.4 遗传算法寻优操作

使用轮盘赌方式进行选择操作，使Fit值越大的染色体保留的概率越大，随机选取一定数量的染色体作为新的父代.同时引入精英保留策略，使一定比例的优质解直接进入下一代的迭代过程，以加快种群的收敛.

采用算数交叉法进行交叉操作，为了尽可能的避免交叉过程中进化速度过快或过慢导致的负面效应，定义自适应交叉因子.当适应度变化过大时，改变交叉因子的大小以保证整体进化的质量.定义自适应交叉因子如式.

(14)

式中：Fitmax和Fitavg分别为群体的最大和平均个体适应度;Fit为父代两个体适应度较大[6].

采用高斯变异法进行变异操作，同样仿照交叉过程设置自适应变异因子.

(15)

2.5 非法解修正

基于工序编码常常会带来非法解，因此一次寻优操作完成后后需要对更新后的粒子进行调整，设计了一种非法解的修正方法.步骤如下.

步骤1对编码向下取整数.

步骤2移除编码中仍不合理的粒子

步骤3根据编码规则对步骤二得到的编码进行补完，随机填入空白处得到修正后的最终编码.

3 实例验证及算法对比

为验证本文改进PSO-GA算法性能，对某整车厂焊装车间车前门线体数据进行了仿真测试.该条柔性流水线可以生产6种不同的车门，不同车型对应车门制造的标准工时有所差异，线体符合典型FSP模型，根据本文模型，以设备负荷均衡水平及总拖期时间为优化指标进行实验.线体共6个工序，每个工序有2～3个并行机.现对一批共6个不同的工件进行仿真实验，工件加工工时见表2.

表2 工件加工时间表 单位:s

为了更好的研究分析本文所设计的算法性能，进行了遗传算法、粒子群算法及改进PSO-GA算法的仿真实验.

3.1 参数设置

参数的设置合理与否与问题规模有关，而且会对实验结果有较大影响.遗传算法与粒子群算法的参数设计见表3.

表3 改进PSO-GA算法参数表

结合大量仿真实验结论[7]，本文所提出的改进粒子群-遗传算法与基本遗传算法、粒子群算法采用基本相同的参数，但是配置了不同的交叉因子和变异因子.交叉概率Pc取[0.6，0.9]，变异概率Pm取[0.05，0.1]，并根据改进粒子群-遗传算法参数的取值范围，重新配置了交叉因子、变异因子的自适应调整范围—将精英种群的交叉因子、变异因子采用更小的调整范围，以更好的保持优秀个体.

3.2 实仿真结果分析

仿真实验环境使用Matlab R2018a仿真软件，lntel(R) Core(TM) i5-8400,2.80 GHz处理器，内存为8.00 GB.共进行了20组实验，实验数据见表4，表中数据均已采用文献[8]中的方法进行了无量纲归一化处理.实验中综合目标函数考虑拖期时间与机器负荷均衡，其中拖期时间权重设置为0.7，机器负荷均衡权重设置为0.3.表中数据表明基本粒子群算法与遗传算法均过早的收敛，所输出的最优解为局部最优解.改进PSO-GA算法得到的为更优解，相较于粒子群算法，综合目标评价函数f的平均值改善了13.6%，相较于粒子群算法，综合目标评价函数f平均值改善了10.9%.且改进PSO-GA算法的最差解与最优解结果都好于另外两种算法.

表4 不同算法评价指标表

粒子群算法及遗传算法最优解计算后所得到的工序分别为[3,5,2,6,4,1]及[2,5,3,6,4,1]，改进PSO-GA算法得到最优解的加工顺序为[4,5,2,6,3,1].通过图3的改进PSO-GA算法最优解甘特图展示了机器分配情况，可以看到机器负荷较为均衡，其中工序1～6中各台机器运转负荷率为100%、100%、86.7%、90.0%、100%、97.4%、94.3%、89.7%、85.8%、100%、90.6%，各机器负荷差距较小且负荷率均超过75%时可以认为此生产线负荷较为合理.

图3 实例调度结果甘特图

三种算法最优解的收敛曲线见图4.通过收敛曲线可以看出，在达到收敛时，改进PSO-GA算法不仅在综合评价指标上较优，所需代数显著少于其他两种算法.

图4 综合目标函数随训练代数进化图

4 结 束 语

本文通过对双目标柔性流水车间调度问题进行建模与分析，对遗传-粒子群算法进行了改进，算法在继承了粒子群算法搜索速度快，效率高的特点，同时也具有遗传算法全局搜索能力强的特点，并且在引入动态交叉变异参数后，能较好的提高种群多样性，避免陷入局部极值的情况.

由于本文所使用的算例规模较小，当问题规模扩大时，改进PSO-GA算法收敛速度与精度还有待进一步验证与提高.