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

摘要:

权利要求书:

1.一种基于联合蚁群算法的批调度方法,其特征在于:包括以下步骤:S1:初始化最大迭代次数Tmax、蚂蚁数量AntNum、工件数量n,机器数量I,机器容量S,信息素矩阵、信息素蒸发率ρ、工件的库存概率和运输概率,令当前迭代次数t=1,蚂蚁序列Ant=0;

S2:令Ant=Ant+1,初始化禁忌列表TB=(1,2,3,···,n);

S3:当前蚂蚁Ant选择一台机器Mi构建一个空批Bki;

S4:当前蚂蚁Ant随机选择未被分配的工件Jj分配到批Bki,令TBj=0,构建当前批Bki的候选列表Lki;

S5:当 时,当前蚂蚁Ant从候选列表Lki中选择一个工件Jj分配到当前批Bki中,更新TBj=0,转至S6;当 时,转至S7;

S6:更新禁忌列表Lki,返回S5;

S7:如果TB≠(0,0,0,···,0),则返回S3,如果TB=(0,0,0,···,0),则输出当前蚂蚁Ant确定的调度方案;

S8:通过局部优化策略优化调度方案,计算优化后的调度方案的目标值;

S9:如果Ant<AntNum,则返回S2,否则转至S10;

S10:获取全局最优调度方案,如果t<Tmax,则更新库存概率、运输概率和信息素,令t=t+1,Ant=0,返回S2;否则输出全局最优调度方案。

2.根据权利要求1所述的一种基于联合蚁群算法的批调度方法,其特征在于:所述信息素矩阵表示为Γ={τg,j|g,j∈[1,n]},其中τg,j表示工件Jg和Jj分配到同一个批中的期望,S1中将τg,j均初始化为0.1,即将信息素矩阵初始化为数值都是0.1,规模为n*n的二维矩阵。

3.根据权利要求2所述的一种基于联合蚁群算法的批调度方法,其特征在于:S3中蚂蚁Ant选择机器Mi的方法为:将所有机器按完工时间排序,在完工时间最早的机器Mi上构建新批Bki,如果存在多个完工时间最早的机器,则从中随机选择一个机器Mi。

4.根据权利要求3所述的一种基于联合蚁群算法的批调度方法,其特征在于:S4中所述的构建当前批Bki的候选列表Lki的方法为:选择满足当前批Bki容量约束的所有未分批的工件构建得到候选列表Lki,即其中,S表示当前批的总容量,所有机器的容量均为S,sj表示工件Jj的尺寸。

5.根据权利要求4所述的一种基于联合蚁群算法的批调度方法,其特征在于:S5中所述的从候选列表Lki中选择一个工件Jj分配到当前批Bki中方法为:将候选列表Lki中选择概率Wj,ki最大的工件Jj加入到批Bki中其中, 为信息素,表示工件Jj放入批Bki的期望, 为工件Jj放入批Bki的启发式信息,α为信息素的权重,β为启发式信息的权重,|Bki|为批Bki内的工件数量。

6.根据权利要求5所述的一种基于联合蚁群算法的批调度方法,其特征在于:S8所述的局部优化策略包括以下步骤:步骤i:输入当前蚂蚁Ant的调度方案,获取机器数量I和机器Mi上的批数量bi,将每台机器Mi上的所有批按加工时间非递减排序,初始化i=1,v1=0,集合步骤ii:令v1=v1+1,如果v1=bi,则转至步骤vii,否则令v2=v1+1;

步骤iii:将批 中所有加工时间小于批 中任意工件加工时间的工件放入集合N中,x为集合N中的工件数量,令w=1;若 则跳转步骤vi;

步骤iv:判断批 中加工时间最长的工件与批 中处于集合N的第w个位置的工件交换后是否满足批容量约束,如果满足则交换这两个工件,更新批 的加工时间,令返回步骤iii,若交换后不满足批容量约束条件,则不执行交换操作;

步骤v:令w=w+1,如果w≤x,返回步骤iv;

步骤vi:如果v2<bi,令v2=v2+1,返回步骤iii;

步骤vii:如果i<I,令i=i+1,v1=0,返回步骤ii,否则输出优化后的调度方案。

7.根据权利要求6所述的一种基于联合蚁群算法的批调度方法,其特征在于:批Bki的加工时间Pki等于该批Bki中所有工件的最大加工时间,即Pki=max(pj|Jj∈Bki)

pj表示工件Jj的加工时间。

8.根据权利要求7所述的一种基于联合蚁群算法的批调度方法,其特征在于:S8中所述的目标值Q为生产成本W、库存成本I和运输成本D的和,即Q=E+I+D;

所述生产成本E的计算方法为

其中,λ1>0为常数,Ti为机器Mi的加工时间,其等于该机器Mi上所有批的总加工时间。

9.根据权利要求8所述的一种基于联合蚁群算法的批调度方法,其特征在于:S8中计算目标值的方法为:步骤I:输入调整后的调度方案,将所有批按到达时间非递减排序,获取批的总数K,当前批的序号初始化为k=1,初始化库存集合 运输集合 车辆总数H=0;

步骤II:将当前批Bk加入库存集合IB,计算库存集合IB中所有批的库存概率Ub和运输概率Xb,具体为Bb∈IB

其中,qg(t)表示工件Jg的库存概率,fg(t)表示工件Jg的运输概率,每个工件Jg的库存概率Jg在步骤S1中被初始化为(0,1)内的随机实数,fg(1)=1-qg(1);

γ为常数,本实施例中取γ=0.3,Yb为批Bb的库存时间,表示批Bb到当前批Bk的完成时间之差,即步骤III:如果k<K,转至步骤IV,否则转至步骤V;

步骤IV:将当前所有Ub≤Xb的批Bb移出库存集合IB,并加入运输集合DB,将运输集合DB中的所有批分配到车上,得到所需车辆hk,令H=H+hk, 更新库存集合IB,令k=k+1,返回步骤II;

步骤V:将库存集合IB中的所有批移入运输集合DB,将运输集合DB中的所有批分配到车上,得到所需车辆hk,令H=H+hk;

步骤VI:计算运输成本D和库存成本I;

D=λ3H

其中,λ2,λ3均为大于0的实数,Yk为批Bk转入运输集合DB被车运输走时的库存时间;

步骤VII:计算并输出目标值 其中表示第t次迭代时第Ant只蚂蚁的调度方案的目标值,其他字母的含义类似;

其中为运输集合DB中的批分配车辆的方法为:将所有批按照所占空间非递增排序,按照Best-Fit规则依次分配到车上,直到所有批都分配完,得到所需车辆的总数hk。

10.根据权利要求9所述的一种基于联合蚁群算法的批调度方法,其特征在于:S10所述的更新库存概率和运输概率的方法为:qg(t+1)=qg(t)+Δqg(t)

fg(t+1)=fg(t)+Δfg(t)

其中,Imin和Dmin表示从第一次迭代到当前迭代产生的所有调度方案的库存成本和运输成本的最小值, 和 分别是当前调度方案库存成本和运输成本的上限,I和D分别是库存成本和运输成本的下限,Δqg(t)和Δfg(t)分别表示库存成本和运输成本在最优情况下的位置;其中库存成本的下限为0,库存成本的上限为所有批加工完成后统一分车运输情况下的库存成本;运输成本的上限为每个批生产出来后立刻运输,即每个批都单独由一辆车运输的成本,运输成本的下限为批全部生产完之后统一运输的成本。

11.根据权利要求10所述的一种基于联合蚁群算法的批调度方法,其特征在于:S10中所述的更新信息素的方法为:τg,j(t+1)=(1-ρ)·τg,j(t)+mg,j(t)·Δτg,j(t)其中,mg,j(t)表示在第t代时,工件Jg和Jj被分配到同一批的次数,Δτg,j(t)表示信息素的增量,如果在第t代中Jg和Jj未分配到同一批次中,则Δτg,j(t)=0;否则Δτg,j(t)=1/Qbest,Qbest表示当前迭代中全局最优调度方案的目标值。