一种基于柔性算子的零件成组调度方法

1.本发明涉及车间成组调度技术领域，更具体的说是涉及一种基于柔性算子的零件成组调度方法。


背景技术：

2.多品种、小批量的生产模式下传统制造车间生产中会产生频繁的作业切换，影响了设备利用率和生产效率。作业切换是指一台机器上一种任务加工结束到下一种任务开始加工的准备活动，一般包括更换刀具、工装夹具，安装调试等活动。调研数据显示，在生产不同种类工件时，同一台设备上不同的作业排序会产生不同的作业切换时间。成组调度可以将相似的零件分成一组先后加工，有效缩短作业切换时间、提高设备等资源利用率。
3.传统的成组调度算法只考虑不同组之间的作业切换时间，而认为同一组内不同零件之间不存在作业切换时间，这对组内零件的相似度要求极高，导致不同零件之间难以聚类成组，或计算作业切换时间误差过大，难以有效模拟实际的加工情况。
4.目前基于遗传算法的成组调度算法只考虑不同组之间的交叉、变异，而没有考虑组内不同零件之间的交叉、变异，不利于种群的搜索，容易达到局部最优解。且大多数文献研究的方向为自适应交叉和自适应变异算子，均匀或非均匀的动态改变的交叉和变异概率，来提升算法的整体性能。其本质上，都是在研究改变算子概率对寻优性能的影响，仍然存在一定的局限性。
5.针对上述成组调度算法的不足，本发明提出一种基于柔性算子的零件成组调度方法。


技术实现要素：

6.有鉴于此，本发明提供了一种基于柔性算子的零件成组调度方法，旨在零件成组调度时，考虑组内不同零件之间的切换时间。
7.为了实现上述目的，本发明采用如下技术方案：
8.一种基于柔性算子的柔性车间调度方法，包括：
9.s1、初始化零件分组后的加工序列；
10.s2、评价并获得所述加工顺序的种群状态，根据所述种群状态选择交叉、变异策略，分别进行交叉、变异；
11.s3、根据所述交叉操作和所述变异操作选择自然选择策略，得到新的种群；
12.s4、以最小完工时间为目标函数，判断是否达到最大迭代次数，如否，返回执行步骤s2-s3，如是，输出最小完工时间对应的加工排序。
13.作为优选，步骤s2中，根据如下公式计算种群状态，
[0014][0015]
式中，cs表示种群状态，k为正系数，ps为种群规模，fi代表每个个体的适应度，f
avg
代表种群中的平均适应度。
[0016]
作为优选，当k＝1时，cs的最大阈值为0.03，最小阈值为0.02。
[0017]
作为优选，步骤s2中，所述种群状态，大于最大阈值时，组间组内均采用单点交叉策略；小于最小阈值时，组间组内均采用均匀交叉策略；
[0018]
处于所述最大阈值和所述最小阈值之间时，组间组内均采用两点交叉策略。
[0019]
作为优选，步骤s2中，所述种群状态，大于最大阈值时，采用插入变异；小于最小阈值时，采用逆序变异；处于所述最大阈值和所述最小阈值之间时，采用插入/逆序变异。
[0020]
作为优选，步骤s3中，根据所述交叉操作和所述变异操作，判断当前是否处于强继承策略，若是，采用轮盘赌或者锦标赛机制，若否，采用精英选择算子。
[0021]
作为优选，最小完工时间的表达式为：
[0022]
t＝tj+ts+t0[0023][0024][0025][0026]
其中，tj为组内切换时间，ts为组间切换时间，t0为零件加工时间。p为分组个数，qi为第i组的零件个数，w
j,j+1
为qi组内第j个零件到第j+1个零件需要的作业切换时间，s
p,p+1
为第p组到第p+1组的作业切换时间，n为零件总数，jk为第k个零件的加工时间。
[0027]
经由上述的技术方案可知，与现有技术相比，本发明公开提供了一种基于柔性算子的零件成组调度方法，本发明综合考虑组间作业切换时间和组内作业切换时间，通过减少切换时间缩短零件加工时间，从而提高加工效率。
[0028]
同时，本发明提出基于组的交叉、变异方法，可加快种群搜索速度；提出的种群状态评估方法，可在迭代过程中实时监控种群分布状态，并采取柔性算子策略在种群分散时加强集中，集中时加强分散，从而防止种群在迭代过程中前期过于分散后期过于集中，在保留优秀基因的同时，平衡种群多样性。
[0029]
本发明考虑并根据种群的发展状态，确定交叉变异策略以及确定算子的方案，相较于自适应算子具有更高的概率寻到最优解以及具有更快的收敛速度。
附图说明
[0030]
为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现
有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据提供的附图获得其他的附图。
[0031]
图1为本发明基于柔性算子的柔性车间调度方法流程图；
[0032]
图2为本发明不同排产方法的对比图；
[0033]
图3为本发明基于柔性算子的交叉操作流程图；
[0034]
图4为本发明基于柔性算子的变异操作流程图；
[0035]
图5为本发明组间交叉与组内交叉示意图；
[0036]
图6为本发明组间变异与组内变异示意图；
[0037]
图7为本发明柔性策略算子的选择操作流程图。
具体实施方式
[0038]
下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
[0039]
针对现有技术中，只能考虑组间作业切换时间而无法考虑组内作业切换时间的不足，本技术提出一种基于柔性算子的零件成组调度方法，具体的，本发明提出了一种依据种群状态确定交叉变异策略的理念，并具体公开了评价种群状态的方法，以及根据种群状态选择交叉变异算子，即确定柔性算子的方法。本发明采用自适应的改变交叉及变异算子，还可导致丢失优秀个体基因的问题。
[0040]
本实施例中，基于成组调度的构思，具体为：
[0041]
根据当前种群的状态，当个体在解空间中趋于集中时，种群的多样性下降，为了抑制下降，柔性算子从策略库中选择扰动较大的策略(例如均匀交叉+倒序变异的方案)，以扩散开个体的分布，使算法不容易陷入局部最优；
[0042]
而当个体在解空间中趋于分散时，种群不容易保留优秀基因，为了较好地收敛，柔性算子从策略库中选择继承性较强扰动小的策略(例如单点交叉+插入变异)，以框住个体的分散趋势，使算法能逐渐收敛。这种方法可以兼顾全局搜索性能和局部搜索性能，一定程度上提升了算法的适应性。
[0043]
如图1所示，具体的操作步骤如下：
[0044]
初始化种群；
[0045]
是否达到最大迭代次数，如果是则输出最优个体；如果否依次执行如下步骤：
[0046]
评估种群状态，
[0047]
根据种群状态选择种群交叉策略；
[0048]
根据种群状态选择种群变异策略；
[0049]
基于交叉、变异策略确定种群选择策略；
[0050]
根据目标函数计算个体适应度，保留最小完工时间；
[0051]
返回重新判断是否达到最大迭代次数。
[0052]
如图2所示：传统顺序排产，两个零件之间存在作业切换时间。j1-j6为订单内6个
不同的零件，sij为两个不同零件之间的作业切换时间。传统的成组调度排产，将{j1、j4}，{j2，j6}，{j3、j5}分为三个组，组内零件不考虑作业切换时间，只考虑不同组之间的作业切换时间，s42、s63，此时优化节省的时间为fg2。
[0053]
但实际上，组内零件之间也存在作业切换时间，包括j14、j26、j35，,实际上成组排产后的优化时间为fg。
[0054]
采用本发明公开的成组调度方法，可综合考虑组内切换时间和组件切换时间，通过减少各个环节的切换时间来提高加工效率。且考虑组内切换的成组排产精度比传统成组切换的更高，更接近实际的加工情况，有利于增加车间产能、提高生产效率。
[0055]
为了使本领域普通人员更好地理解本公开的技术方案，下面将结合附图，对本公开实施例中的技术方案进行清楚、完整地描述。
[0056]
s1、随机生成零件分组序列，初始化各分组序列内零件加工顺序；
[0057]
s2、评价并获得所述加工顺序的种群状态，根据所述种群状态选择交叉、变异策略，分别进行交叉、变异；
[0058]
首先，本实施例公开的种群状态的评价方法，公式如下：
[0059][0060]
式中，cs表示种群状态，k为正系数，ps为种群规模，fi代表每个个体的适应度，f
avg
代表种群中的平均适应度。
[0061]
通过cs的值，可以评价种群的离散程度，并且可以在不同数值的样本中进行比较。当cs的数值较大时，反映出种群中个体较为分散；cs的数值小时，反应种群中个体较为集中。cs的数值适中，种群的个体分布较均匀。
[0062]
一种实施例中，种群的平均适应度，通过如下公式获得：
[0063][0064]
且个体适应度的计算公式为：
[0065][0066]
式中，f1为设定的正系数，ci为解的最大完工时间值。
[0067]
本实施例中，经过参数调试，当取1时，设定的阈值在0-0.02为集中，0.02-0.03为均匀，0.3-1为分散，故一种实施例中，将cs的最大阈值为0.03，最小阈值为0.02。
[0068]
进一步，具体选择交叉策略为：当种群状态的值，大于最大阈值时，采用单点交叉策略；小于最小阈值时，采用均匀交叉策略；处于最大阈值和所述最小阈值之间时，采用两点交叉策略。
[0069]
选择变异策略的方法为：当种群状态的值，大于最大阈值时，采用插入变异；小于
最小阈值时，采用逆序变异；处于所述最大阈值和所述最小阈值之间时，采用插入/逆序变异。
[0070]
本实施例中，基于柔性算子策略的交叉操作与变异操作流程图，如图3和图4所示；
[0071]
其中，图5为组内交叉和组间交叉示意图，其中，组件交叉可以以组为单位进行整组交叉，如图组间交叉(1)，将组1与组2进行整体交叉调整；或者组件单个组元素进行交叉，如图组件交叉(2)，将组2中的组元素1与组3中的组元素4进行交叉调整；
[0072]
对于组内交叉，实现的效果如图，如将组1中的组元素0与组元素5进行交叉。
[0073]
图6为组内变异和组间变异示意图，包括，
[0074]
插入变异，即组号变异，如组元素5由组1变异至组3；
[0075]
组数减少变异，将选择一个组元素分散到其他组；
[0076]
组数增多变异，选择一个组元素构成新组。
[0077]
s3、根据所述交叉操作和所述变异操作确定算子选择策略，得到新的种群；
[0078]
一种实施例中，根据交叉操作和所述变异操作，判断当前是否处于强继承策略，若是，采用轮盘赌或者锦标赛机制，若否，采用精英选择算子。具体执行流程如图7所示。
[0079]
本技术在选择算子的策略上，取决于交叉和变异的操作。即当采用较大扰动策略时(如单点交叉、插入变异策略)，使用精英选择算子，以保证算法的效果和收敛：当采用强继承性的策略时(如均匀交叉、逆序变异策略)，使用轮盘赌或者锦标赛机制，以快速筛选种群，加快进化过程。
[0080]
s4、以最小完工时间为目标函数，判断是否达到最大迭代次数，如否，返回执行步骤s2-s3，如是，输出最小完工时间对应的加工排序。
[0081]
其中，目标函数的表达式为：
[0082]
t＝tj+ts+t0[0083][0084][0085][0086]
其中，tj为组内切换时间，ts为组间切换时间，t0为零件加工时间。p为分组个数，qi为第i组的零件个数，wj,j+1为qi组内第j个零件到第j+1个零件需要的作业切换时间，sp,p+1为第p组到第p+1组的作业切换时间，n为零件总数，jk为第k个零件的加工时间。
[0087]
适应度为目标函数的倒数，即，完工时间越少，个体的适应度越大。
[0088]
本发明提出一种基于柔性算子考虑组内零件作业切换时间的成组调度算法。本算法考虑组内零件作业切换时间优化车间调度模型，提出组内与组间基因交叉、变异方法，并根据当前种群情况，根据预设的策略库自主地对交叉、变异和选择的算子的概率进行调整，使遗传算子具备一定的柔性。
[0089]
为使本发明的上述目的、特征和优点能够更加明显易懂，下面结合具体实施对本发明作进一步详细的说明。
[0090]
本实施例是柔性算子在柔性制造车间的应用
[0091]
为了进一步验证本文提出的柔性算子方法，本发明使用brandimarte的标准mk04、mk06、mk09三个不同规模的算例进行测试，设置初始化方式为全局0.6，局部0.3，随机0.1，最高迭代数设置50，种群规模设置50，遗传概率参数设置为交叉概率0.8，变异概率0.01。使用不同的策略与本文提出的柔性策略进行比对。
[0092]
其中，策略1为单点交叉+逆序变异+轮盘赌、策略2为单点交叉+插入变异+锦标赛、策略3为均匀交叉+逆序变异+锦标赛、策略4为均匀交叉+插入变异+轮盘赌。每个策略运行20次，其中cm表示历史最优解的值，av(cm)表示20次运行的最大完工时间平均值，av(a)表示20次算法的平均收敛代数。mk标准算例运行结果对比数据，如表2和表3所示。
[0093]
表2
[0094][0095]
表3
[0096][0097][0098]
实验结果表明：在这三个不同规模的算例上，本文提出的柔性算子策略，最大完工时间最小的最优值和平均值均比策略1-4求得的结果更优；柔性算子策略平均收敛代数较策略1-4大，这是由于柔性算子后期采用的强扰动策略所致，采用精英选择可保证收敛。这个结果也侧面印证了本发明选择算子的设计，在单目标的柔性车间调度中收敛速度更快。综合来看，本文提出的柔性算子策略，利用了算子性能侧重点不同的特性，取长补短，在最终运算结果上较经典遗传算法固定算子优越。
[0099]
本说明书中各个实施例采用递进的方式描述，每个实施例重点说明的都是与其他实施例的不同之处，各个实施例之间相同相似部分互相参见即可。对于实施例公开的装置
而言，由于其与实施例公开的方法相对应，所以描述的比较简单，相关之处参见方法部分说明即可。
[0100]
对所公开的实施例的上述说明，使本领域专业技术人员能够实现或使用本发明。对这些实施例的多种修改对本领域的专业技术人员来说将是显而易见的，本文中所定义的一般原理可以在不脱离本发明的精神或范围的情况下，在其它实施例中实现。因此，本发明将不会被限制于本文所示的这些实施例，而是要符合与本文所公开的原理和新颖特点相一致的最宽的范围。

技术特征：
1.一种基于柔性算子的零件成组调度方法，其特征在于，包括：s1、初始化零件分组后的加工序列；s2、评价并获得所述加工序列的种群状态，根据所述种群状态选择交叉、变异策略，并分别进行交叉、变异；s3、根据交叉操作和变异操作确定算子选择策略，得到新的种群；s4、以最小完工时间为目标函数，同时判断是否达到最大迭代次数，如否，返回执行步骤s1-s3，如是，输出最小完工时间对应的加工排序。2.根据权利要求1所述的一种基于柔性算子的零件成组调度方法，其特征在于，步骤s2中，根据如下公式计算种群状态，式中，cs表示种群状态，k为正系数，ps为种群规模，f
i
代表每个个体的适应度，f
avg
代表种群中的平均适应度。3.根据权利要求2所述的一种基于柔性算子的零件成组调度方法，其特征在于，当k＝1时，cs的最大阈值为0.03，最小阈值为0.02。4.根据权利要求1所述的一种基于柔性算子的零件成组调度方法，其特征在于，步骤s2中，所述种群状态的值，大于最大阈值时，采用单点交叉策略；小于最小阈值时，采用均匀交叉策略；处于所述最大阈值和所述最小阈值之间时，采用两点交叉策略。5.根据权利要求1所述的一种基于柔性算子的零件成组调度方法，其特征在于，步骤s2中，所述种群状态的值，大于最大阈值时，采用插入变异；小于最小阈值时，采用逆序变异；处于所述最大阈值和所述最小阈值之间时，采用插入/逆序变异。6.根据权利要求1所述的一种基于柔性算子的零件成组调度方法，其特征在于，步骤s3中，根据交叉操作和变异操作，判断当前是否处于强继承策略，若是，采用轮盘赌或者锦标赛机制，若否，采用精英选择算子。7.根据权利要求1所述的一种基于柔性算子的零件成组调度方法，其特征在于，最小完工时间的表达式为：t＝t
j
+t
s
+t
000
其中，t
j
为组内切换时间，t
s
为组间切换时间，t0为零件加工时间，p为分组个数，q
i
为第i
组的零件个数，wj,j+1为q
i
组内第j个零件到第j+1个零件需要的作业切换时间，sp,p+1为第p组到第p+1组的作业切换时间，n为零件总数，j
k
为第k个零件的加工时间。

技术总结
本发明公开了一种基于柔性算子的零件成组调度方法，包括：S1、初始化零件分组后的加工序列；S2、评价并获得所述加工顺序的种群状态，根据所述种群状态选择交叉、变异策略，种群根据所选策略进行交叉、变异；S3、根据所述交叉操作和所述变异操作确定种群选择策略，得到自然选择之后的种群；S4，以最小完工时间、最小作业切换时间为目标函数，计算种群个体的适应度，判断是否达到最大迭代次数，如否，返回执行步骤S2-S3，如是，输出最小完工时间对应的加工排序。本申请公开的调度方法，可以同时考虑组内和组间零件切换时间，优化结果更能反映实际加工过程，有利于车间生产计划的落实，提高实际生产效率。生产效率。生产效率。


技术研发人员：李子瑞 仝晓萌 蔡茂林 郎奕宸
受保护的技术使用者：北京航空航天大学
技术研发日：2023.06.06
技术公布日：2023/8/24