一种新型混合算法在混流装配调度中的应用

娄高翔，蔡宗琰，刘清涛

LOU Gaoxiang,CAI Zongyan,LIU Qingtao

长安大学 工程机械学院，西安 710064

School of Construction Machinery,Chang’an University,Xi’an 710064,China

1 引言

作为制造业中比较常见的一种生产方式，混流装配生产可以在一条流水生产线上同时装配出型号、数量均不同的产品，其具有灵活性高，实用性强的特点。自从1961年由Kilbridge和Wester提出混流装配这个概念后，混流装配线的生产调度问题已经成为该领域的研究热点。李同正等[1]在2012年对一些特殊形式的混装线进行了分析，指出了混装线排序问题需要进一步研究的方向；吕聪颖[2]为解决混流装配调度问题提出了新颖的蚁群算法，定义了信息素的表示方法，但是参数的取值具有一定的局限性；刘琼等[3]针对混流装配线上各工作站内设备闲置成本的不同，提出了一种基于线性混合比率的猫行为模式选择方法，提高了算法前期的全局搜索能力和后期的局部寻优能力；周康渠等[4]针对混流装配调度算法中存在的“早熟”现象，提出了一种混合离散粒子群算法，并通过实例验证了该算法的有效性；鲁建厦等[5]为解决面向云制造的混合车间调度问题，建立了多目标车间调度模型，设计了一种混合生物地理学优化算法，并得到良好验证。

目前的混流装配问题主要是针对多个工序对两个目标进行优化：装配线各工作站上的负荷平衡最优、待组装的主要零部件和原材料的消耗速率最优[1]。近年来对其他因素如最大完工时间[6]、最小化工位[7]、最小化品种切换时间等[8]进行综合考虑，很少有考虑缓冲空间存在储存成本的情况，但是在实际问题中，有些缓冲空间的存储成本需要考虑，且装配生产的成本问题也是需着重考虑的一项重要因素。混流装配调度问题是典型的NP-hard问题，目前解决NP-hard问题的方法主要分为分支定界法[9]、领域搜索算法[10]、遗传算法（GA）[11]、蚁群算法[12]、粒子群优化算法[13]以及一些混合算法[14]等。这些算法都在相关的领域得到了应用验证。且不同算法对连续数据和离散数据的优化效率不同[15-16]。混流装配调度中加工工序和加工数量分别为离散变量和连续变量，为了更有效地处理这两种变量需设计一种更高效的算法，目前对混流装配调度的研究中尚未见能同时高效处理连续变量和离散变量的混合算法。

本文针对车间中存在缓冲区的实际问题，首次对加工工序和加工数量的连续性进行分类，并用新的混合算法解决了缓冲区数量和调度最优时间而形成的目标优化问题。本文将GA有效处理离散变量及DE有效处理连续变量的优点融合，以更好地处理同时具有离散变量和连续变量的情况。

2 问题描述

在连续的两个混流装配车间中，往往布置缓冲区来保证生产平顺性，即通过预先安排好一部分制造资源，来缓解生产过程中不同环节之间生产节拍不一致带来的瓶颈问题。各车间可通过缓冲区的排序功能来调整产品的顺序。

本文要讨论的缓冲区连接两个上下游车间。缓冲区可暂时储存即将进入下游车间生产装配的零部件，某可以看成是一种特殊类型的在制品仓库。考虑到不同车间生产节拍不同，生产中各型号产品会在缓冲区中维持一定的数量。由于所研究车间生产的特殊性，对零部件的生产需分阶段进行，且在生产过程中，上下游车间共用一批操作工人。零部件的油污需要清洗后风干才能进入下一加工阶段，上游车间为零部件的风干车间，下游车间为装配加工车间，上游车间的加工完全可以在下游车间生产过程中同时无人进行，因此可忽略上游车间的加工时间以及加工停顿性，且零部件风干后输入到缓冲区时下游车间需停止生产，该时间远小于下游车间的加工时间，因此可以忽略。单纯作为缓冲区而言，过大的缓冲区可以完全满足车间零部件的缓冲储存需求，但是也大大增加了储存成本。而过小的缓冲区虽然可以降低储存成本，却不能起到真正平衡节拍的功能。因此，此类缓冲区会有一个最低的安全库存值，也会有一个最高的库存值。而下游车间的生产装配工作量也可以根据缓冲区来调整，如果仅仅考虑生产时间最低则需要尽可能少量的生产数量，仅考虑缓冲区的储存成本则需要尽可能多的生产数量。同时考虑二者则会形成一个衡量权重、相互矛盾的目标函数，因此需要综合考虑多方面因素以寻找一个最优的解决方案。另外实践表明，频繁更换不同的产品比连续生产同一种产品具有更低的工作效率[17]。针对上述情况，本文提出了一种在最大化工作效率的前提下能够使生产成本最低的方法，建立了相关的模型，并用新型的算法予以解决。

3 模型建立

为了更加方便地描述以上数学模型，特定义符号如下：

M为所有产品的集合，产品的种类数为为产品的生产序列，产品的总数量为为整个生产序列DT中第m种型号产品的集合，第m种型号产品的数量为，有：Dj为生产序列DT中第j个产品的型号，j=1,2,…,有Dj∈M；sj,m为生产序列DT中第j个位置是否生产第m种产品，其中m∈M，sj,m=0表示否，sj,m=1表示是，显然有：

3.1 目标函数

此调度问题的目标函数是尽量减少生产成本，包括在整个调度范围内生产所有产品的总时间成本和缓冲区的储存成本。

产品的生产时间包括不同种类产品之间的等待时间以及所有产品的加工时间总和。

定义不同种类产品之间的等待时间：

ti,j为生产完i类型产品后j类型产品的准备时间，其中i=1,2,…,m，j=1,2,…,m。

假设ti,i=0，首个生产产品的准备时间定义为ti,i。由于ti,i=0，当计算总的等待时间时，可以将每个类型的产品假设成一个产品，此时原有的生产序列DT可以简化为dt。

等待时间为：

另外，定义t′i为一个产品i的生产时间，其中i=1,2,…,m，生产线上所有产品i的生产总时间ti为：

其中，ni,line为生产线上产品i的数量。

所有产品的生产时间为：

产品总的生产时间为：

时间成本与生产时间呈正相关，因此生产成本为：

其中，kct表示成本C1与时间T之间的正相关系数。

每种类型的产品在缓冲区的数量为ni，其中i=1,2,…,m。

所有产品的数量为：

储存成本与储存数量也呈正相关，因此储存成本为：

其中，kcn表示成本C2与数量N之间的正相关系数。

因此调度问题目标函数为：

其中，q1、q2分别表示生产成本和储存成本的权重系数。

上述在缓冲区的产品数量均为生产线机器运行后的数量。

3.2 约束

（1）缓冲区库存数量。每种型号的缓冲区库存的数量ni需要满足：

其中，ni,min是型号i在缓冲区的安全库存；ni,max是型号i在缓冲区的最大库存。

（2）生产线数量。对于可靠的生产，型号i在生产线上数量ni,line必须满足：

其中，n0,i为生产线开机前型号i的初始数量。

3.3 混合算法框架

图1为遗传算法和差分进化的混合算法框架流程图。该混合算法可以解决调度问题中同时存在的离散排序问题以及连续数量问题。以下是详细的程序：

步骤1设置遗传算法和差分进化算法的初始参数，包括初始种群数量、突变率、交叉率、约束条件和终止条件等。

步骤2设置初始种群。

步骤3根据适应度函数评价个体的适应度。

步骤4选出最优解并记录。

步骤5如果满足终止条件则转到步骤9，如果不满足终止条件则转到步骤6。

步骤6对基因的排序采用遗传算法的选择、交叉、变异操作；同时基因的数量采用差分进化算法的变异、交叉、选择操作。

步骤7根据适应度函数评价新个体的适应度。

步骤8新个体与原个体置换形成下一代个体，并转到步骤4。

步骤9输出最优解。

图1 遗传算法与差分进化算法混合算法流程图

从以上流程图中可以看出，遗传算法解决了生产线上所有产品的排序问题，差分进化算法则解决了产品的生产数量问题。将两种算法结合可以同时更好地解决排序及数量问题。

3.3.1 编码

本文的遗传算法使用字符串编码方式，即每个染色体为一个字符串，一个字符串表示一个生产序列，染色体里面的每个基因代表一个待生产的产品型号。本研究的调度是基于产品的相似度，因此多个相同型号的产品可用一个基因表示。染色体片段如下：

其中A、B、C、D、…、O、P、Q、R等表示生产序列中的一个待生产的产品型号。示例中的加工顺序为：型号A→型号B→型号C→型号D→…→型号O→型号P→型号Q→型号R。

对应于上述遗传算法中每个染色体使用字符串，差分进化算法使用数字串编码方式，数字串表示方式如下：

其中每个数字表示生产序列中待生产产品型号的数量。

3.3.2 适应度函数

本文混合框架中遗传算法和差分进化算法均是通过适应度来衡量个体的优良程度，越接近最优解则适应度越高。较高适应度的个体有更大的概率遗传到下一代，反之亦然。适应度函数为衡量每个个体适应度高低的函数。优化目标是使生产成本最低，为方便计算，适应度函数采用目标函数的变式，即：

其中，fp的含义参考式（10）。

3.3.3 进化策略

在遗传算法中，进入下一代的个体必须是适应度相对理想的，适应度不理想的个体将被淘汰。进化方法一般有精英选择和轮盘赌。精英选择是直接选出适应度强的个体进入下一代。轮盘赌的方式则按照每个个体适应度所占总适应度的比例选择进入下一代。本文选择两者结合的方式，先选出这一代中表现好的m个个体直接进入下一代，这一层选择是精英选择。然后从剩下的个体中采用轮盘赌的方式选择个进入下一代。用Pr(di)表示个体di被选中的概率。

当i≤m时：

这种方式保留了最优个体，同时保证了种群的多样性，更大程度地保证了下一代的质量。

差分进化算法中的进化策略采用的是贪婪算法。通过比较经过变异、交叉完毕的染色体和原有染色体的适应度函数值来选择。其中变异和交叉算子在算子选择部分进行详细介绍。

3.3.4 算子的选择

根据本研究的具体情况，对算子进行了一定的改进。

（1）遗传算法

遗传算法中的交叉算子是产生新个体的主要方法。本文采用顺序交叉的方式，即在父代的一方d1中随机选出一段染色体作为原始后代，再从父代的另一方d2中选出剩余的染色体按照顺序补充到新的子代1染色体上。图2为顺序交叉示例。

图2 遗传算法顺序交叉示例

同理在父代d2中随机选出一段染色体作为原始后代，再从父代d1中补充剩余的片段可以形成新的子代2染色体。

遗传算法的变异运算一般包括反转、插入、移位、互换等，本文采用互换的方式，随机选取基因的两个位置进行互换。图3为变异的示例。

图3 遗传算法变异运算示例

（2）差分进化算法

差分进化算法需先进行变异再进行交叉操作。此算法通过差分策略实现个体变异，可以应用于连续变量中。本研究在种群中随机挑选不同的两个个体，两个个体进行向量差的同比例减小，再与待变异的个体进行合成，即：

其中，F为缩放因子；xi(g)表示第g代中的第i个个体。在变异进化过程中，需判断新产生的中间体是否满足边界条件，如果超出了边界，则要重新生成中间体。若每代种群数量记为N，则会生成N个变异中间体。然后对第g代种群及其变异的中间体进行个体间的交叉操作。

当rand(0,1)≤CR或者j=jrand时：

反之：

其中，CR为交叉概率；j为基因位置，jrand为[1,2,…,D]的随机整数。图4为6个基因位的染色体交叉运算示意图。

图4 差分进化交叉运算示例

3.3.5 终止条件

根据本研究的具体情况，如果算法满足预先设定的迭代数，则迭代会被终止。

4 结果分析

为了验证混合遗传算法对存在缓冲区的混流装配车间调度问题的有效性，采用了具体的生产数据进行验证。

实例为需要生产A、B、C、D、E、F共6种型号的产品，初始状态全部存放于缓冲区中。各种型号产品在缓冲区的初始数量及缓冲区的最高最低库存量如表1所示。

生产不同型号的产品需要一定的转换等待时间，每个型号的产品也需要一定的生产时间。生产不同型号产品的等待时间如表2所示。

表1 缓冲区中各种型号产品数量状态表

表2 各产品之间等待时间

在表2中，先生产A再换型号A的等待时间为0，先生产A再换型号B的等待时间为80 s，先生产A再换型号C的等待时间为60 s，以此类推。需要注意的是先生产A再换型号B的等待时间与先生产B再换型号A的等待时间是不同的。各型号单个产品的生产时间如表3所示。

表3 各型号产品生产时间

按照本文提出的混合遗传算法进行编程，设置初始种群大小为100，迭代次数为100，遗传算法[18]和差分进化算法[19]的交叉概率均为0.9，遗传算法的变异概率为0.02，差分进化算法的变异概率为0.5。鉴于车间的实际情况，根据专家经验设置时间成本和库存成本的系数分别为1、4.5；kcn和kct均取1。图5为混合算法迭代曲线。从图中可以看出，无论是最优目标值还是平均目标值都能够快速地收敛。

图5 混合算法迭代曲线

产品生产状态稳定后各零部件在生产线上的顺序及生产数量如图6。

图6 各产品生产数量和顺序状态

此时最优目标值为10281。各产品在车间2内的生产时间状态如图7。图7中红色区域代表等待时间，黑色区域代表生产时间。先生产E，然后再生产B的时候需要一定的等待转换时间然后再生产B，以此类推。

图7 各产品生产时间状态

本文分别采用传统遗传算法和差分进化算法求解此实例，并将结果与混合遗传算法对比，仿真结果如图8所示。从图8的对比曲线可以看出：遗传算法的收敛速度最快，但在一个相对比较大的目标值处就趋于稳定；差分进化算法趋于稳定的目标值相对遗传算法更低，但其收敛速度较慢；与遗传算法及差分进化算法相比，混合遗传算法的收敛速度相对较快，并能在更低的目标值处趋于稳定。由此可见，对于本文提出的调度问题，混合遗传算法具有收敛速度快，优化能力强，算法可靠等优势。

图8 3种算法仿真结果对比曲线

5 结论

本文针对含有缓冲区混流装配调度问题，建立了以最小时间成本和最小库存成本为优化目标的混流装配生产数学模型，该模型同时含有离散变量和连续变量。为求解该数学模型，本文提出了一种新的混合遗传算法。此混合算法弥补了遗传算法和差分进化算法的缺陷，同时融合了两种传统算法的优点。通过算例表明，与传统算法相比，所设计的混合遗传算法在求解混流装配调度问题中收敛速度相对较快，并能在更低的目标值处趋于稳定，进一步验证了该算法的有效性和优越性。