基于改进遗传算法的WBS缓冲区车辆排序调度方法

摘要

本发明公开了一种基于改进遗传算法的WBS缓冲区车辆排序调度方法，包括如下步骤：S1.构建WBS缓冲区车辆排序调度模型；S2.调整WBS缓冲区车辆排序调度模型中各参数的值，使得WBS缓冲区车辆排序调度模型取得最小值，并根据得到最小值时设置的车辆在WBS缓冲区的位置将车辆输送到调整道。本发明的一种基于改进遗传算法的WBS缓冲区车辆排序调度方法，能够有效地提高WBS缓冲区调度效率，可靠性强，降低了生产成本。

权利要求

1.一种基于改进遗传算法的WBS缓冲区车辆排序调度方法，其特征在于：包括如下步骤：

S1.构建WBS缓冲区车辆排序调度模型：其中，n为调整道个数；m为每条调整道能容纳的车辆个数；i为调整道序号；j为调整道中所在列的序号；di,j为车辆生产序号判断标识符；Ni,j为排产计划中为车辆在涂装车间设定的生产序号；Ci,j为车辆型号判断标识符；Bshape为一个生产批次中车辆型号的总种类数目；

S2.基于改进遗传算法调整WBS缓冲区车辆排序调度模型中各参数的值，使得WBS缓冲区车辆排序调度模型取得最小值，并根据得到最小值时设置的车辆在WBS缓冲区的位置将车辆输送到调整道。

2.根据权利要求1所述的基于改进遗传算法的WBS缓冲区车辆排序调度方法，其特征在于：步骤S2中，基于改进遗传算法调整WBS缓冲区车辆排序调度模型中各参数的值，使得WBS缓冲区车辆排序调度模型取得最小值，具体包括：S21.随机产生r个由车辆在涂装车间的生产序号Ni,j组成的序列得到序列集合NS；其中，所述r为序列集合NS的个数，取值为正整数；

S22.确定序列集合NS中第k个序列的适应度fk；

其中，所述适应度 k＝1,2,...,r；

S23.根据第k个序列的适应度fk计算第k个序列被选中的概率pk得到序列集合NS的概率分布P，根据概率分布P从序列集合NS中筛选出t个序列；其中，所述t小于r，t取值为正整数；

S24.从t个序列中任意选择多对序列并对每对序列进行交叉操作得到多对新的序列，将多对新的序列添加到序列集合NS中得到新的序列集合N'S；

S25.从序列集合N'S中任意选择一个序列进行变异操作得到一个新的序列，并将新的序列添加到序列集合N'S中得到新的序列集合N″S；

S26.对序列集合N″S中各序列按照从前到后的顺序以m个序号为一组进行分组，并对序列的每个分组按照序号从小到大顺序进行排序得到新的序列，将新的序列更新到序列集合N″S中得到新的序列集合N″′S；

S27.判断序列集合N″′S中是否存在使得WBS缓冲区车辆排序调度模型取得最小值的序列，若是，则算法结束，若否，进入步骤S28；

S28.判断算法迭代执行次数是否达到设定值，若是，则算法结束，若否，则回到步骤S22更新序列集合为N″′S，并从步骤S22开始继续执行。

3.根据权利要求2所述的基于改进遗传算法的WBS缓冲区车辆排序调度方法，其特征在于：步骤S23中，根据第k个序列的适应度fk计算第k个序列被选中的概率pk得到序列集合NS的概率分布P，具体包括：

S231.确定第k个序列的相对适应度 其中，fmin为序列集合NS中序列适应度的最小值；fmax为序列集合NS中序列适应度的最大值；

S232.确定第k个序列被选中的概率S234.根据第k个序列被选中的概率pk得到序列集合NS的概率分布P＝(p1,p2,...,pr)。

说明书

基于改进遗传算法的WBS缓冲区车辆排序调度方法

技术领域

[0001] 本发明涉及调度领域，具体涉及一种基于改进遗传算法的WBS缓冲区车辆排序调度方法。

背景技术

[0002] 汽车生产制造过程中，历经冲压、焊接、涂装、总装四大车间。其中焊接、涂装为典型的流水作业车间，并且联系紧密。焊接车间的优化目标为减少焊接夹具的切换次数，涂装
车间的优化目标为减少喷涂机器人喷涂颜色的切换次数。车间的优化目标不同，车辆在各
个车间中的加工顺序也不同，因此为了实现车辆的重排序以及保证生产效率，车间之间通
常设立缓冲区，其中，焊接与涂装车间之间的缓冲区为WBS(White Body Storage)。

[0003] 当今车辆制造业的发展迅速，随着订单量的增加，对车辆的生产效率要求就更高。而车间之间缓冲区的调度效率对于车辆的生产效率有着重要的影响，但当前对WBS缓冲区
调度的研究并不多，这就导致了WBS缓冲区的调度主要依赖人工操作，当缓冲区的规模变大
时，调度过程缓慢，调度出错率上升，车辆常常滞留在缓冲区，人工、时间等各种成本会进一
步增加。

[0004] 因此，为解决以上问题，需要一种基于改进遗传算法的WBS缓冲区车辆排序调度方法，能够有效地提高WBS缓冲区调度效率，可靠性强，降低了生产成本。

发明内容

[0005] 有鉴于此，本发明的目的是克服现有技术中的缺陷，提供基于改进遗传算法的WBS缓冲区车辆排序调度方法，能够有效地提高WBS缓冲区调度效率，可靠性强，降低了生产成
本。

[0006] 本发明的基于改进遗传算法的WBS缓冲区车辆排序调度方法，包括如下步骤：

[0007] S1.构建WBS缓冲区车辆排序调度模型：

[0008]

[0009]

[0010] 其中，n为调整道个数；m为每条调整道能容纳的车辆个数；i为调整道序号；j为调整道中所在列的序号；di,j为车辆生产序号判断标识符；Ni,j为排产计划中为车辆在涂装车
间设定的生产序号；Ci,j为车辆型号判断标识符；Bshape为一个生产批次中车辆型号的总种类
数目；

[0011] S2.基于改进遗传算法调整WBS缓冲区车辆排序调度模型中各参数的值，使得WBS缓冲区车辆排序调度模型取得最小值，并根据得到最小值时设置的车辆在WBS缓冲区的位
置将车辆输送到调整道。

[0012] 进一步，步骤S2中，基于改进遗传算法调整WBS缓冲区车辆排序调度模型中各参数的值，使得WBS缓冲区车辆排序调度模型取得最小值，具体包括：

[0013] S21.随机产生r个由车辆在涂装车间的生产序号Ni,j组成的序列得到序列集合NS；其中，所述r为序列集合NS的个数，取值为正整数；

[0014] S22.确定序列集合NS中第k个序列的适应度fk；

[0015] 其中，所述适应度

[0016] S23.根据第k个序列的适应度fk计算第k个序列被选中的概率pk得到序列集合NS的概率分布P，根据概率分布P从序列集合NS中筛选出t个序列；其中，所述t小于r，t取值为正
整数；

[0017] S24.从t个序列中任意选择多对序列并对每对序列进行交叉操作得到多对新的序列，将多对新的序列添加到序列集合NS中得到新的序列集合N′S；

[0018] S25.从序列集合N′S中任意选择一个序列进行变异操作得到一个新的序列，并将新的序列添加到序列集合N′S中得到新的序列集合N″S；

[0019] S26.对序列集合N′S中各序列按照从前到后的顺序以m个序号为一组进行分组，并对序列的每个分组按照序号从小到大顺序进行排序得到新的序列，将新的序列更新到序列
集合N″S中得到新的序列集合N″′S；

[0020] S27.判断序列集合N″′S中是否存在使得WBS缓冲区车辆排序调度模型取得最小值的序列，若是，则算法结束，若否，进入步骤S28；

[0021] S28.判断算法迭代执行次数是否达到设定值，若是，则算法结束，若否，则回到步骤S22更新序列集合为N″′S，并从步骤S22开始继续执行。

[0022] 进一步，步骤S23中，根据第k个序列的适应度fk计算第k个序列被选中的概率pk得到序列集合NS的概率分布P，具体包括：

[0023] S231.确定第k个序列的相对适应度 其中，fmin为序列集合NS中序列适应度的最小值；fmax为序列集合NS中序列适应度的最大值；

[0024] S232.确定第k个序列被选中的概率

[0025] S234.根据第k个序列被选中的概率pk得到序列集合NS的概率分布P＝(p1,p2,...,pr)。

[0026] 本发明的有益效果是：本发明公开的一种基于改进遗传算法的WBS缓冲区车辆排序调度方法，通过构建调度排序模型，使用改进的遗传算法求得调度排序模型的最优解，根
据最优解对应的调度排序序列对处于WBS缓冲区的车辆进行调度，能够有效地提高WBS缓冲
区调度效率，可靠性强，降低了生产成本。

附图说明

[0027] 下面结合附图和实施例对本发明作进一步描述：

[0028] 图1为本发明的方法流程示意图；

[0029] 图2为本发明的改进遗传算法原理示意图。

具体实施方式

[0030] 以下结合说明书附图对本发明做出进一步的说明，如图所示：

[0031] 本发明的基于改进遗传算法的WBS缓冲区车辆排序调度方法，包括如下步骤：

[0032] S1.构建WBS缓冲区车辆排序调度模型：

[0033]

[0034]

[0035] 其中，n为调整道个数；m为每条调整道能容纳的车辆个数；i为调整道序号；j为调整道中所在列的序号；本实施例中，所述调整道为WBS缓冲区的车辆调整道；di,j为车辆生产
序号判断标识符；Ni,j为排产计划中为车辆在涂装车间设定的生产序号，本实施例中，在实
际生产前，首先设定车间的排产计划，其中，预先设定一个生产批次的车辆在涂装车间的生
产序号为一个递增序列(1,2,3,…,Ni,j,…,w)，其中，w为所述序列的车辆个数，一个车辆对
应一个生产序号；Ci,j为车辆型号判断标识符；Bshape为一个生产批次中车辆型号的总种类数
目；本实施例中，WBS缓冲区车辆排序调度是对每个生产批次中生产的所有车辆进行排序调
度处理。

[0036] S2.基于改进遗传算法调整WBS缓冲区车辆排序调度模型中各参数的值，使得WBS缓冲区车辆排序调度模型取得最小值，并根据得到最小值时设置的车辆在WBS缓冲区的位
置(i,j)将车辆输送到对应的调整道。

[0037] 本实施例中，步骤S2中，基于改进遗传算法调整WBS缓冲区车辆排序调度模型中各参数的值，使得WBS缓冲区车辆排序调度模型取得最小值，具体包括：

[0038] S21.随机产生r个由车辆在涂装车间的生产序号Ni,j组成的序列，将r个序列组成一个序列集合NS；其中，所述r为序列集合NS的个数，取值为正整数，本实施例中，r不大于20，
所述序列的车辆个数为w；

[0039] S22.确定序列集合NS中第k个序列的适应度fk；

[0040] 其中，所述适应度

[0041] S23.根据第k个序列的适应度fk计算第k个序列被选中的概率pk得到序列集合NS的概率分布P，根据概率分布P从序列集合NS中筛选出t个序列；其中，所述t小于r，t取值为正
整数；

[0042] 本实施例中，根据概率分布P从序列集合NS中筛选出t个序列，具体包括：

[0043] 使用轮盘赌算法，计算每个序列的累计概率区间，其中，第k个序列的概率区间为具体地，第一个序列的概率区间为[0,p1]，第二个序列的概率
区间为[p1,p1+p2]，第三个序列的概率区间为[p1+p2,p1+p2+p3]，以此类推可以得到序列集合
NS中所有序列的概率区间。

[0044] 产生取值在[0,1]区间内的2个随机数，根据随机数落入的概率区间，选择对应的序列。当随机数落入区间[p1,p1+p2]时，则选择概率为p2对应的序列。如此反复循环t/2次，
最终筛选出t个序列。

[0045] S24.本实施例中，采用部分映射杂交匹配法(PMX)，从t个序列中任意选择多对序列并对每对序列进行交叉操作。具体地，首先产生[1,w]之间的随机数a1和a2，然后将每对序
列中2个序列的位置a1和位置a2之间的数据部分进行交叉互换，由于交叉互换之后的个体序
列中有相同的生产序号，因此需要将不重复的生产序号保留，有冲突的生产序号消除。其
中，利用交叉互换段的映射关系，分别将个体序列中的冲突生产序号进行变更，此为现有技
术，在此不再赘述。多对序列进行所述的交叉互换后，可以得到多对新的序列，将多对新的
序列添加到序列集合NS中得到新的序列集合N′S；

[0046] S25.从序列集合N′S中任意选择一个序列，将序列中的一个生产序号进行变异以产生更优秀的序列。本实施例中，采用的变异方法为单点变异和逆转变异。其中，单点变异
为：产生[1,w]之间的随机数b1和b2，当序列的位置b1和位置b分别对应的生产序号不在WBS
缓冲区的同一调整道中时，就将序列的位置b1和位置b2分别对应的生产序号对调；逆转变异
为：产生[1,w]之间的随机数c1和c2，当序列的位置c1和位置c2分别对应的生产序号不在WBS
缓冲区的同一调整道中时，就将序列的位置c1和位置c2之间的生产序号逆序排列；那么一个
序列变异之后就能得到一个新的序列，然后将新的序列添加到序列集合N′S中得到新的序
列集合N″S；

[0047] S26.对序列集合N″S中各序列进行重新排序，具体地，将序列按照从前到后的顺序以m个序号为一组进行分组，可以得到多个分组，然后对该序列(称为原序列)的每个分组按
照生成序号从小到大顺序进行排序得到新的序列，最后将原序列删除，并将原序列对应的
新序列添加到序列集合N″S中得到新的序列集合N″′S；

[0048] S27.判断序列集合N″′S中是否存在使得WBS缓冲区车辆排序调度模型取得最小值的序列，若是，则算法结束，将最小值对应的序列带入调度模型即可得到最小值；若否，进入
步骤S28；

[0049] S28.判断算法迭代执行次数是否达到设定值，若是，则算法结束；若否，则回到步骤S22更新序列集合为N″′S，并从步骤S22开始继续执行；本实施例中，设定值为10000次。

[0050] 本实施例中，步骤S23中，根据第k个序列的适应度fk计算第k个序列被选中的概率pk得到序列集合NS的概率分布P，具体包括：

[0051] S231.确定第k个序列的相对适应度 其中，fmin为序列集合NS中序列适应度的最小值；fmax为序列集合NS中序列适应度的最大值；

[0052] S232.确定第k个序列被选中的概率

[0053] S234.根据第k个序列被选中的概率pk得到序列集合NS的概率分布P＝(p1,p2,...,pr)。

[0054] 最后说明的是，以上实施例仅用以说明本发明的技术方案而非限制，尽管参照较佳实施例对本发明进行了详细说明，本领域的普通技术人员应当理解，可以对本发明的技
术方案进行修改或者等同替换，而不脱离本发明技术方案的宗旨和范围，其均应涵盖在本
发明的权利要求范围当中。