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

摘要:

权利要求书:

1.一种基于蚁群算法的平行机批调度方法,其特征在于:包括步骤A:初始化最大迭代次数Tmax、蚂蚁数量AntNum、工件集合J={J1,J2,…,Jn}、容量均为S的机器集合M={M1,M2,…,Mm};当前迭代周期为t=1,蚂蚁序号Ant=1,工件Jx和Jj在第1次迭代中分配在同一批中的期望 均初始化为常数0.05;

步骤B:当前蚂蚁Ant基于机器的完工时间将所有工件依次分配到各机器中,得到一个调度方案;

步骤C:通过局部优化调整步骤B得到的调度方案;

步骤D:如果Ant

步骤E:基于每个调度方案的目标值总加权完工时间确定第t次迭代的局部最优解和截止第t次迭代的全局最优解,利用全局最优解的目标值更新期望步骤F:如果t

步骤B所述的当前蚂蚁Ant基于机器的完工时间将所有工件依次分配到各机器中的方法包括以下步骤:步骤i:构建禁忌列表TB=(1,2,3,…,n),其中TBj=0,表示工件Jj已被选择,TBj≠0,表示工件Jj未被选择;

步骤ii:选择完工时间最早的机器Mi构建新批Bib,如果存在多个满足条件的机器,则选择序号最小的机器构建新批;

步骤iii:构造批Bib的候选列表Lib,如果 则返回步骤ii;

步骤iv:如果 则从候选列表Lib中随机选择一个工件Jj放入批Bib中,否则将候选列表Lib中选择概率最大的工件Jj放入批Bib中;

步骤v:令TBj=0,通过局部期望更新公式更新工件Jj与批Bib中其他工件放入同一批的期望,如果TB≠(0,0,0,…,0),则返回步骤iii,否则输出当前蚂蚁Ant分配的调度方案;

步骤ii所述的机器Mi的完工时间为该机器Mi上所有批的加工时间之和,即PBib=max{pj|Jj∈Bib}

其中,PBib为批Bib的加工时间,pj为工件Jj的加工时间,即批Bib的加工时间PBib等于批Bib中所有工件的最大加工时间;

步骤iii所述的候选列表Lib为满足批Bib剩余容量要求的未分配工件集合,即其中,sj为工件Jj的尺寸;

步骤iii所述的选择概率的计算方法为:

其中选择概率Pibj表示工件Jj放入批Bib的概率,τibj为蚁群算法的信息素,表示工件Jj放入批Bib的期望,|Bib|表示批Bib中的工件总数, 和 为蚁群算法的启发式信息,其中通过工件Jj放入批Bib前后的加权总完工时间的差计算得到,wj为工件Jj的权值,CBib为批Bib的完工时间,其等于前一批的完工时间+当前批的加工时间,即WBib为批Bib的权重,其等于批Bib中所有工件的权重之和,即启发式信息 表示的是工件Jj的单位尺寸权重;α,β1,β2分别为信息素和两个启发式信息的影响因子,为在步骤A中初始化设置的全局变量;

步骤iii所述的局部期望更新公式为

其中ρl为局部信息素蒸发率,其在步骤A中初始化设置为全局变量;

步骤C所述的通过局部优化调整调度方案的方法为:

步骤I:将调度方案中的所有批以单位时间加工权重 从大到小排序,获取批总数B,令当前批序列b=1,b′=b+1,j=1,j′=1;

步骤II:如果满足

BJWbj

步骤III:如果j′<|Bb′|,则j′=j′+1,返回步骤II;否则令j′=1,转至步骤IV;

步骤IV:如果b′

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

步骤VI:如果b

步骤VII:如果BJPb′j′≤PBb且BJSb′j′≤S‑Sb,则将工件BJb′j′放入批Bb中;

步骤VIII:如果j′<|Bb′|,则j′=j′+1,返回步骤VII;否则令j′=1,转至步骤IX;

步骤IX:如果b′

步骤X:如果b

步骤XI:计算所有机器的完工时间,将当前批Bb放入完工时间最早的机器中,如果存在多个符合要求的机器,则将批Bb放入序号最靠前的机器中;

步骤XII:如果b

2.根据权利要求1所述的一种基于蚁群算法的平行机批调度方法,其特征在于:步骤E所述的调度方案的目标值总加权完工时间Q的计算方法为:cj=CBib,Jj∈Bib

其中, 表示第t次迭代中,第Ant只蚂蚁的调度方案的目标值;cj为工件Jj的完工时间;

则局部最优解为当前迭代周期目标值最小的调度方案,其目标值表示为全局最优解为截止当前迭代周期目标值最小的调度方案,其目标值表示为当完成迭代即t=Tmax时,目标值 对应的调度方案即为输出结果。

3.根据权利要求2所述的一种基于蚁群算法的平行机批调度方法,其特征在于:步骤E中更新期望 的全局期望更新公式为其中mxj(t)表示在第t次迭代中工件Jx和Jj分配在同一批中的次数,n为工件数,ρg为全局信息素蒸发率,在步骤A中初始化为全局变量。