基于并行融合机制的改进遗传算法求解HFSP调度问题

张 源 陶翼飞 王加冕

(昆明理工大学机电工程学院 云南 昆明 650500)

0 引 言

混合流水车间调度问题[1](HFSP)是流水车间[2]调度问题的推广，其特征是在某些工序中存在并行机器，其目的是指在一定时间内对加工工件的排序和加工设备的分配进行优化使某些性能指标达到最优。考虑切换时间的HFSP是指在混合流水车间调度问题的基础上引入了机器依次加工不同工件时的切换准备时间[3]，由于加入了工件之间切换时间的因素[4]，使研究的问题与实际更为接近，成为现阶段混合流水车间调度领域研究的新方向。

引入并行进化机制的遗传算法[5]是对传统遗传算法[6]的优化，可以提高算法的寻优质量。目前引入并行进化机制的遗传算法主要运用于路径规划[7]问题的优化，也有学者将其用于求解车间调度问题。Belkadi等[8]对混合流水车间调度问题，以最大完工时间为目标，采用并行遗传算法进行求解并与标准遗传算法的结果进行比较，证明了该算法可以提高求解质量。Rubiyah等[9]提出了一种求解作业车间调度问题的混合并行遗传算法(PGA)，该算法基于异步群体和自主迁移进行迭代更新，通过对不同规模问题进行仿真实验，证明了该算法能够在一定程度上求解出更优的完工时间。在近几年中的研究中，Luo等[10]针对动态混合流水车间问题，提出一种基于优先级的并行混合遗传算法进行求解，通过仿真实验证明了该算法的优越性。Zhu等[11]针对多目标混合流水车间问题，提出了基于灰熵分析的并行遗传算法进行仿真实验，结果表明该算法能有效解决多目标车间调度优化问题。Fu等[12]提出了一种基于特殊交叉变异策略的多种群并行遗传算法对作业车间调度问题进行求解，实验结果表明该算法能求解出更优的解。

文献研究表明，并行遗传算法在求解HFSP时，能够改善求解质量，但由于缺乏关于遗传算法的改进研究，使得引入并行机制后的算法仍存在收敛速度慢、易陷入局部极值的缺点，且多数文献以完工时间[13](makespan)为目标进行优化，忽略了对加工不同工件时机器切换时间的研究。因此，针对上述问题，本文以考虑工件切换时间的混合流水车间调度问题为研究对象建立仿真模型，优化目标为总工位切换时间(Total Station Switching Time，TSST)，并提出一种基于种群并行融合机制的改进遗传算法(PIGA)进行求解，最终将总工位切换时间(TSST)作为各算法的性能指标进行对比，验证了本文算法的有效性。

1 问题描述

在考虑切换时间的HFSP中，假设共有J个工序组成，其中至少有一个工序存在一台以上的不相关并行机设备，并且相邻工序间存在暂存缓冲区。每个工件需要依次经过J个工序进行加工，工件在每道工序中只能选择该工序中的一台机器进行加工，工件在不同机器上加工时间不同，加工不同工件时机器的切换时间不同，加工相同工件时机器不需要切换时间。已知工件在所有设备上的加工时间和各工件之间的切换时间。为方便描述问题，定义参数如表1所示。

表1 数学模型定义参数

续表1

假设所有设备的切换时间只与加工工件顺序相关；所有设备加工第一个工件时不需要切换准备时间；同一时间每台设备只能加工一个工件；不同工序间有无限暂存区；问题优化目标是求解最小化总工位切换时间，即：

minCmax

(1)

考虑切换时间的混合流水车间调度问题的数学模型存在的约束条件及计算公式如下：

(2)

(3)

Si1,i2>0i1≠i2

(4)

(5)

(6)

式(2)为总工序切换时间计算公式及目标函数；式(3)为各个工序中所有机器的总切换时间；式(4)说明，任意两个不同工件之间的切换时间必须大于0；式(5)说明同一时间，每台机器只能加工一个工件；式(6)表示如果在工序j的机器k上依次加工工件i1和工件i2，那么工件i2在工序j机器k上的完工时间应大于等于工件i1在工序j的机器k上的完工时间、工件i1和工件i2的切换时间、工件i2在工序j的机器k上的加工时间三者之和。

2 并行融合机制的改进遗传算法求解

遗传算法(Genetic algorithm，GA)在HFSP中应用较为广泛，但是标准遗传算法由于在个体选择和交叉变异概率方面的局限性，使算法全局搜索能力降低且出现早熟现象。因此本文结合并行融合拆分机制、精英保留策略[14]和自适应遗传因子[15]对遗传算法进行改进，建立了基于并行融合机制的改进遗传算法，该算法有效克服了传统遗传算法易陷入局部极值的缺点。

2.1 编码和解码

编码采用基于工件编号的实数编码，即染色体中的各元素值代表对应的工件编号。解码的目的是确定工件的加工顺序和各工序设备的分配情况，其中染色体中的元素值序列代表工件进入混合流水车间的初始加工顺序，后续阶段加工工件的排序按前阶段工件完工时间的先后顺序进行加工。工件在各工序并行设备的分配根据先到先服务法则[16](First In First Seved，FIFS)进行安排，即优先安排最早进入暂存区队列等候的工件进行加工。

2.2 种群初始化及适应度函数

初始种群产生的方法为：在均匀分布(Uniform Distribution)中随机产生I个不重复的数字来建立初始种群，种群中的每个染色体由一个一维矩阵组成，染色体长度表示加工工件的个数。

本文优化的目标是最小化总工序的切换时间，但在遗传算法迭代过程中保留的是适应度值最大的个体，应取目标函数的倒数作为适应度函数，由于切换时间以秒为单位计算，目标函数计算结果较大，所以为方便观察比较，在目标函数倒数的基础上再放大100倍，即第g代的第n条染色体的适应度函数为：

fg,n=100/Cg,n

(7)

式中：n∈{1,2,…,N}，N为每代的染色体数目；Cg,n为第g代的第n条染色体的总切换时间。

2.3 并行融合拆分机制

由于随机生成的初始种群增加了算法寻优过程中的不确定因素，使得算法的最优解质量和收敛速度等方面的结果并不理想。因此本文在遗传算法的迭代进化中引入一种基于多种群的并行融合拆分机制，该机制是指对遗传算法进行并行设计，同时在并行计算中加入了种群个体间的融合拆分策略，通过对多个种群的分布式并行处理，不仅提高了算法的求解速度和运行效率，而且由于增加了种群规模和个体间的融合拆分，使得种群个体的多样性得以维持和丰富，增加了算法的求解空间，降低了陷入局部极值的可能性，提高了求解质量。

如图1所示，并行融合拆分机制是指将m个种群个体进行融合，融合后按某种规律重新差分为m个种群的过程。其中：bmn为种群m的第n个染色体；am×n为种群融合后的第m×n个染色体，且fa1≥fa2≥…≥fam×n；Bm为融合拆分后的第m个种群。并行融合拆分机制的具体操作为：

(1) 若满足合并条件，将m个种群的个体进行融合，融合后通过仿真输出所有个体的适应度值并保留最优个体。

(2) 将融合后的种群个体按适应度值大小进行降序排列，并根据排列顺序重新编号，其中a1、am×n分别为融合种群的最优和最差个体。

(3) 将融合种群个体的序号按公差为m的等差数列重新拆分为m个种群，并用最优个体替换各种群中的最差个体，如拆分后种群B1的最差个体为a1+m(n+1)，则将融合种群的最优个体a1与该个体进行替换，其余种群同理进行保优操作。

(4) 保留拆分后的各种群，进行遗传操作。

图1 并行融合拆分机制示意图

2.4 基于精英保留策略的个体选择机制

在传统的遗传算法中，选择操作采用轮盘赌[17]的方式，用适应度值对每代染色体进行评价，适应度值大的染色体被选中的概率也高，但该方法并不代表适应度值低的染色体不会被选中，若适应度值低的染色体被选中进入子代,则会对最终寻优结果的质量产生影响。因此本文采用精英保留策略的方法进行个体选择,该策略是指在种群进化过程中选择适应度值较高的个体进行复制，替换较差个体进行后续遗传操作，并且将适应度最好的精英个体直接保留到下一代的过程。通过对优良个体进行保留复制,增强其繁衍能力，保证种群精英个体的基因序列不被破坏，提高算法的收敛速度和寻优解质量。具体操作为：

(1) 将种群中的染色体按适应度值大小降序排列。

(2) 排列后将前50%的染色体进行复制并替换后50%的染色体组成待配种群，并将最优个体保留到子代中。

(3) 保留选择后的待配种群，进行后续的交叉变异操作。

2.5 改进自适应遗传因子设计

在遗传算法求解不同规模的调度问题时，很难确定最佳的交叉变异概率值，使算法过早收敛无法求解出全局最优解。而自适应交叉变异因子可以根据某些条件自行调整交叉变异概率，以达到或接近其最佳值,从而能较好地改善寻优解质量。因此本文采用基于进化代数和适应度值变化的自适应遗传因子替换固定的交叉变异概率。

当染色体适应度值趋于早熟或多数个体集中于局部最优时，为跳出局部极值并延续优良个体的基因结构,应适当降低交叉概率增加变异概率，以达到快速寻找最优解的目的；当染色体适应度差距较大或种群个体在解空间中分散分布时，为利于优良个体的生存并保持染色体之间的差异性，应适当增加交叉概率减小变异概率[18]，以帮助种群在寻找完最优解后快速收敛。综上所述,本文改进自适应交叉变异概率计算公式如下：

(8)

(9)

式中：Pc为交叉概率；Pcmax、Pcmin分别表示交叉概率的最大值和最小值；Pm为变异概率；Pmmax、Pmmin分别表示变异概率的最大值和最小值；favg为当前种群个体平均适应度值；fg,n为第g代第n个个体的适应度值；fmax为当前种群中最大的适应度值；fmin为当前种群中最小的适应度值；g为当前迭代次数；G为总的迭代次数。

在改进自适应遗传因子中，交叉算子为相邻个体间的PMX交叉，即随机选择两个交叉点，交换染色体之间的片段，交换后的染色体采用部分映射进行修复。变异算子为两点变异法，即在染色体中随机选择两个位置的基因进行互换。

2.6 并行融合机制改进遗传算法步骤及流程

本文在上述改进自适应遗传算法的基础上引入并行融合拆分机制构建最终的改进遗传算法。算法总流程如图2所示，具体步骤如下：

Step1随机生成m个指定规模数量的种群作为改进遗传算法的初始子种群。

Step2分别通过计算机仿真输出m个种群中对应个体的适应度值。

Step3基于精英保留策略对各种群中的优良个体进行选择操作。

Step4基于改进自适应遗传算法进行种群个体的交叉变异操作。

Step5是否满足终止条件，若满足输出优化结果；若不满足转Step 6。

Step6是否满足合并条件，若满足转Step 7；若不满足转Step 2。

Step7将m个种群的个体进行融合，并按适应度值降序排列。排列后序号按公差为m的等差数列重新拆分为m个种群，并转Step 2。

图2 引入并行融合机制的改进遗传算法流程

3 仿真实验

本文进行的仿真实验的混合流水车间实例[19]为某钢铁厂生产企业加工12个工件，加工过程由炼钢、精炼、连钢、轧制四道工序组成，四道工序的并行机数量分别为3、3、2、2。仿真模型在Plant Simulation软件中建立，如图3所示。

图3 混合流水车间仿真优化模型

混合流水车间仿真模型由控制参数、程序仿真和数据统计三个模块组成，其中程序仿真模块中用Simtalk语言编写算法和模型调度程序。数据统计模块将工件之间的切换时间、工件在各机器上的加工时间、算法求解结果等数据进行记录。控制参数模块为仿真运行过程中需要调用的参数，并显示当前种群的实时数据。各工件之间的切换时间服从X(min)～U[1,10]均匀分布如表2所示。

表2 工件切换时间

仿真模型在Plant Simulation软件中运行，PIGA将各初始子种群分配到对应的处理器并行运算，每个处理器完成独立的串行遗传算法。设置并行融合机制的种群数m为2，满足合并条件的迭代次数为100，交叉概率的极值为[0.6,0.9]，变异概率的极值为[0.05,0.15]。各算法的最大迭代次数Gmax为300，每代种群个体数量N为50。

4 结果分析

分别将标准遗传算法(GA)、自适应遗传算法(Adaptive Genetic Algorithm，AGA)和基于种群并行融合机制的改进遗传算法(PIGA)在仿真模型中各运行10次进行比较。表3为对比结果，表中给出了各算法求解的最小值(Min)、平均值(Avg)、最大值(Max)、平均耗时(CPU)和平均收敛代数(Avg-FI)。

表3 各算法性能指标对比结果

如表3所示，由寻优解质量可得，PIGA求解的最小值、平均值和最大值均优于其他两种算法，且最优解的极差仅为2，具有较好的稳定性和寻优能力。由运行时间可得，由于PIGA中引入了并行融合拆分机制，增加了种群数量，使该算法的实现过程更复杂，但PIGA中各子种群是在多个处理器中分布式运行，因此虽然算法的复杂性得到了提升，但运行时间与自适应遗传算法基本一致，且求解质量也得到了改善，表明了该算法在复杂程度更高的情况下，能用相同的时间求解出更优的解，具有较好的运算效率。由收敛代数可得，PIGA的平均收敛代数明显小于其他两种算法，表明该算法在迭代搜索中能快速收敛到最优解，具有较好的收敛性。综上所述，在迭代次数相同的情况下，PIGA具有更优的全局搜索能力、运行效率和收敛速度，从而验证了该算法的有效性和优越性。

图4和图5为各算法的迭代曲线和最优解甘特图。在迭代曲线中,GA和AGA分别在175和165代发生寻优停滞现象，陷入局部极小值。而PIGA在113代就收敛到最优解116，有效避免算法趋于早熟。在甘特图中工件加工时间的条形图下方显示了该工件的切换准备时间，由于各设备加工首个工件时不需要切换准备时间,因此在甘特图中各工位第一个加工时间的条形图下方没有显示切换准备时间。从图5中可得工件的完工时间为343 min，虽然加工时间较长，但优化目标是总工位切换时间，所以该结果反映的是工位切换准备时间最少的情况，即各设备加工时间下方的切换时间条形图最短。

图4 改进前后GA迭代曲线

图5 最优解甘特图

5 结 语

本文在传统遗传算法的基础上引入并行融合拆分机制、精英保留策略和自适应遗传因子，提出一种基于种群并行融合机制的改进遗传算法，并以总工位切换时间为目标对混合流水车间调度问题进行求解。通过仿真结果的对比分析，验证了本文算法的有效性，为并行遗传算法的改进研究和应用提供了一定的参考价值。