[发明专利]基于混合集合蛙跳与变邻域算法的平行机调度方法及系统

摘要

本发明提供了一种基于混合集合蛙跳与变邻域算法的平行机调度方法及系统，针对拟解决的针对多个不相关批处理机器上的工件协同生产加工的问题，依据工件的在不同机器的一般加工时间和恶化情况，将工件分配至各机器并安排工件的组批和加工顺序，从而最小化最大完工时间，依据单机问题的最优解的性质，设计了有效的多机启发式规则，并将改规则融入改进集合蛙跳算法中用于解决该问题。经典集合蛙跳算法的改进策略主要是通过引入变邻域算法改进经典集合蛙跳算法的局部搜索过程，增强了原有算法的收敛速度和寻优能力。

主权项

一种基于混合集合蛙跳与变邻域算法的多个不相关平行批处理机的协同制造方法，其特征在于，包括：步骤1、输入每个工件在每个机器上的一般加工时间，初始化算法参数，包括种群规模N，划分的组数S，当前迭代次数L，RVNS算法最大迭代次数Umax，最大迭代次数Lmax，并设置L＝1；步骤2、初始化种群内各个青蛙的位置，记所述种群为其中表示第L代种群P(L)中的第i个个体，表示个体在第j个维度上的位置，第j个位置对应第j个工件，i＝1,2,…N，j＝1,2,…n，其中n表示工件数量；步骤3、计算种群P(L)中每个个体的适应度值；步骤4、按照适应度值将种群平均划分为S个组，记所述各组集合为表示上述集合中的第s个组，表示组中的第l个个体，s＝1,2,…S，l＝1,2,…(N/S)，设置s＝1；步骤5、计算组中的最优与最差个体，分别记为和随机选择组的一个个体作为RVNS算法的初始解，设置u＝1；步骤6、判断u≤Umax是否成立，若成立，则转到步骤9；步骤7、随机产生一个的第一类邻域个体X_1，判断X_1是否优于若成立，则将X_1赋给将u+1赋给u，转到步骤5；否则，转到步骤8；步骤8、随机产生一个的第二类邻域个体X_2，判断X_2是否优于若成立，则将X_2赋给将u+1赋给u，转到步骤5；否则，转到步骤9；步骤9、随机产生一个的第三类邻域个体X_3，判断X_3是否优于若成立，则将X_3赋给将u+1赋给u，转到步骤5；否则，转到步骤10；步骤10、判断是否优于若成立，则将赋给否则将赋给步骤11、判断s不大于S，若成立，则将s+1赋给s，并转到步骤5；步骤12、判断L不大于Lmax，若成立，则将L+1赋给L，并转到步骤3；否则结束算法，输出每个工件的执行机器和每个机器上的组批和批的加工顺序。