欢迎来到知嘟嘟! 联系电话:13336804447 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13336804447
知嘟嘟经纪人
收藏
专利号: 2019111789146
申请人: 安徽大学
专利类型:发明专利
专利状态:已下证
专利领域: 计算;推算;计数
更新日期:2026-11-16
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

1.一种基于双信息素蚁群算法的批调度方法,其特征在于:包括以下步骤S1:初始化工件数量n、机器数量M、机器的容量Si(i=1,2,3,...,M)、蚂蚁数量AntNum、最大迭代次数Tmax、信息素的蒸发率ρ,第Ant=1只蚂蚁,当前第t=1迭代;

S2:初始化期望 c1,c2为常数, 为工件Ji和Jj分配到同一批中的期望,为工件Ji排在Jj前面的期望;

S3:当前蚂蚁Ant基于机器的加权完工时间和由期望 确定的信息素 和 将所有工件依次分配到各机器的批中,得到一个分批方案;

其中, 为将工件Jj放入批Bbi中的可能性, 为工件Jj被优先选择的可能性;

S4:通过局部优化策略优化分批方案,并计算当前分批方案的解;

S5:如果Ant<AntNum,令Ant=Ant+1,返回S3,否则获取截止当前迭代周期t的全局最优解,令Ant=1,更新期望 和S6:当t<Tmax时,如果t%TS=0,令t=t+1,返回S2,否则令t=t+1,返回S3,当t≥Tmax时输出全局最优解及对应的分批方案;

其中,TS为期望初始化周期,t%TS表示t除以TS的余数。

2.根据权利要求1所述的一种基于双信息素蚁群算法的批调度方法,其特征在于:S2中所述的常数c1=c2=0.05。

3.根据权利要求2所述的一种基于双信息素益群算法的批调度方法,其特征在于:S3中所述的当前蚂蚁Ant将所有工件依次分配到各机器Mi的批中,得到一个分批方案的方法包括以下步骤:步骤i:初始化禁忌列表DE=(1,2,3,…,n);

步骤ii:计算所有机器的加权完工时间,蚂蚁Ant寻找当前加权完工时间最小的机器Mi,在机器Mi上构建批Bbi,如果存在多个加权完工时间最小的机器,则从这多个加权完工时间最小的机器中选择容量最小的机器,若同时存在多个容量最小的机器,则从中随机选择一个;

步骤iii:根据当前批Bbi剩余空间构建候选列表CLbi,如果 转向步骤vi,否则转向步骤iv;

步骤iv:如果批Bbi内没有工件,即 则从候选列表CLbi中依据首工件策略选择一个工件放入批Bbi中;如果 则将候选列表CLbi中选择概率最大的工件放入批Bbi中;

步骤v:将工件Jj放入批Bbi后,更新禁忌列表DEj=0,返回步骤iii;

步骤vi:如果DE≠(0,0,0,…,0),返回步骤ii,当DE=(0,0,0,…,0)时,输出当前蚂蚁Ant的分批方案。

4.根据权利要求3所述的一种基于双信息素蚁群算法的批调度方法,其特征在于:步骤ii中所述机器Mi的加权完工时间定义为WMi*CMi,其中WMi为机器的权重,定义为当前机器Mi上所有批的权重之和,批的权重为批中所有工件的权重之和,即其中,WBbi为批Bbi的权重,wj为工件Jj的权重;

CMi为机器的完工时间,定义整个分批方案开始处理的时间为0时刻,CMi为机器Mi上最后一个批的完工时刻,批的完工时刻为前一批的完工时刻+当前批的处理时间,即CMi=CBki,k=|Mi|CB(b+1)i=CBbi+PB(b+1)i

PBbi=max{pj|Jj∈Bbi}

其中,|Mi|为机器Mi内的批的总数,CBbi为批Bbi的完工时刻,PBbi为批Bbi的处理时间,pj为工件Jj的处理时间。

5.根据权利要求4所述的一种基于双信息素蚁群算法的批调度方法,其特征在于:步骤iii中所述的候选列表CLbi为尺寸小于当前批Bbi所在机器的剩余容量的未分配工件集合,即:sj为工件Jj的尺寸,Si为机器Mi的容量,即批Bbi的最大尺寸。

6.根据权利要求5所述的一种基于双信息素蚁群算法的批调度方法,其特征在于:步骤iv中所述的首工件选择策略为:计算候选列表CLbi中所有工件的平均wj/sj值,在CLbi中wj/sj值大于该平均值的所有工件中随机选择一个工件,作为批Bbi的第一个工件。

7.根据权利要求5所述的一种基于双信息素蚁群算法的批调度方法,其特征在于:步骤iv中所述的工件选择概率的计算方法为:其中, 为工件Jj放入批Bbi的可能性, 为工件Jj放在候选列表CLbi中其他工件之前的可能性; 和 蚁群算法的第一启发式信息和第二启发式信息,α、β、ω为常数,表示信息素和启发式信息在公式中的权重。

8.根据权利要求7所述的一种基于双信息素蚁群算法的批调度方法,其特征在于:S4所述的局部优化策略包括以下步骤:步骤I:将分批方案中的所有批计算WB/PB并从大到小排序,获取批数量B,和每个批内Bi的工件数量|Bi|,初始化a=c=d=1,b=a+1;

步骤II:如果同时满足

BJWad≤BJWbc和 和

则跳转步骤III,否则跳转步骤IV;

其中,BJWad为批Ba上的第d个工件BJad的权值,BJSad为工件BJad的尺寸;MSBJbc为批Bb中删除第c个工件BJbc之后的剩余空间,BJPad为工件BJad的处理时间;

步骤III:令

X1=WBb*PBb+WBa*PBa

X2=WB′a*PB′a+WB′b*PB′b

其中,BJWad为工件BJad的权值,B′a和B′b是假设工件BJbc与BJad交换后得到的新批;

如果X1>X2,则在批Ba和Bb中交换工件BJad、BJbc,否则跳转步骤IV;

步骤IV:如果d<|Ba|,则d=d+1,返回步骤II,否则令d=1,转向步骤V;

步骤V:如果c<|Bb|,则c=c+1,返回步骤II,否则令c=1,转向步骤VI;

步骤VI:如果b<B,则b=b+1,返回步骤II,否则转向步骤VII;

步骤VII:如果a<B,则a=a+1,b=a+1,返回步骤II,否则记录调整后的分批方案;

步骤VIII:获取步骤VII调整后的分批方案,令a=1,b=a+1,z=1;

步骤IX:如果同时满足MSBa>BJSbz、BJPbz<PBa、BJWbz>WBa,则将工件BJWbz放入批Ba中,其中MSBa为批Ba所在机器的剩余容量;

步骤X:如果z<|Bb|,则z=z+1,返回步骤IX,否则令z=1,转向步骤XI;

步骤XI:如果b<B,则b=b+1,返回步骤IX,否则转向步骤XII;

步骤XII:如果a<B,则a=a+1,b=a+1,返回步骤IX,否则输出优化后的分批方案。

9.根据权利要求8述的一种基于双信息素蚁群算法的批调度方法,其特征在于:S4中所述的分批方案的解Q为分批方案的总加权完工时间,记为cj=CBbi,Jj∈Bbi

其中,cj为工件Jj的完工时刻,其等于工件Jj所属批Bbi的完工时刻。

S5中所述的截止当前迭代周期t的全局最优解 为

其中, 为第r次迭代的局部最优解。

10.根据权利要求9所述的一种基于双信息素蚁群算法的批调度方法,其特征在于:S5中所述的更新信息素的方法为:其中, 表示在第t次迭代中将工件Ji和Jj分配到同一批次的蚂蚁数量; 表示在第t次迭代中将工件Ji和Jj分配到同一批次且Ji在Jj之前的蚂蚁数量; 表示第t次迭代中期望 的增量, 表示第t次迭代中期望 的增量。