1.一种基于蚁群算法的工件调度方法,其特征在于,所述方法包括:在当前次迭代时,建立第一预设数量只蚂蚁,并为第一预设数量个蚂蚁中的当前只蚂蚁建立空批;
将建立的所述空批作为所述当前只蚂蚁对应的第一当前批,针对所述第一当前批,从预设的加工设备中,将最先空闲的加工设备作为第一当前批对应的当前加工设备;
将待加工工件中的第一待加工工件调度至所述第一当前批中;
将所述待加工工件中,除所述第一待加工工件之外的第二待加工工件加入所述第一当前批对应的候选列表中,且每一个所述第二待加工工件尺寸不大于所述第一当前批的剩余容量;其中,所述第一当前批的剩余容量为,所述第一当前批的总容量与所述第一待加工工件总尺寸的差;
根据所述候选列表中的每一第二待加工工件的权重和尺寸,计算所述候选列表中的第二待加工工件加入到所述第一当前批中的概率,并根据所述概率将第二待加工工件调度至所述第一当前批中,直至所述第一当前批的剩余容量小于任意一个所述待加工工件的尺寸;为所述当前只蚂蚁建立新的空批,将所述新的空批作为所述当前只蚂蚁对应的第一当前批,并返回执行所述针对所述第一当前批,从预设的加工设备中,将最先空闲的加工设备作为第一当前批对应的当前加工设备的步骤,直至所有所述待加工工件都被调度至所述当前只蚂蚁对应的批中;
将第一预设数量个蚂蚁中除当前只蚂蚁之外的其他蚂蚁中的一个作为当前只蚂蚁,并返回执行所述为第一预设数量个蚂蚁中的当前只蚂蚁建立空批的步骤,直至所述第一预设数量个蚂蚁均具有能够容纳所有待加工工件的批;
根据目标值最小的蚂蚁对应的,加工设备与待加工工件之间的对应关系,获取所述目标值最小的蚂蚁对应的信息素增量值,其中,所述目标值为所有待加工工件被加工完成后对应的加权总完工时间;
根据所述目标值最小的蚂蚁对应的所述信息素增量值、所述目标值最小的蚂蚁对应的信息素值以及信息素蒸发率,更新信息素矩阵,其中,所述目标值为所有待加工工件被加工完成后对应的加权总完工时间;
判断当前次迭代对应的迭代次数是否等于最大迭代次数;
若否,将所述当前次迭代对应的迭代次数与预设值之和作为当前次迭代的下一次迭代的迭代次数,将所述下一次迭代对应的次数作为当前次迭代对应的迭代次数,并返回执行所述在当前次迭代时,建立第一预设数量只蚂蚁,并为第一预设数量个蚂蚁中的当前只蚂蚁建立空批的步骤;
若是,将当前次迭代中目标值最小的蚂蚁对应的,加工设备与待加工工件之间的对应关系作为目标调度方法;
所述根据所述候选列表中的每一第二待加工工件的权重和尺寸,计算所述候选列表中的第二待加工工件加入到所述第一当前批中的概率,并根据所述概率将第二待加工工件调度至所述第一当前批中,包括:
将所述候选列表作为当前候选列表,针对所述当前候选列表中的每一第二待加工工件,根据所述第二待加工工件的权重获取其对应的第一启发式信息;根据所述第二待加工工件的尺寸的倒数获取其对应的第二启发式信息;
根据所述第一待加工工件与第二待加工工件被分到所述第一当前批的期望值之和与所述第一待加工工件的数量的商计算所述第二待加工工件相对于所述第一当前批的信息素值;
根据所述第二待加工工件相对于所述第一当前批的信息素值、所述第一启发式信息以及所述第二启发式信息计算每一第二待加工工件的转移概率;
将所述转移概率最大的第二待加工工件调度至所述第一当前批中;将所述转移概率最大的第二待加工工件与所述第一待加工工件的集合作为第一待加工工件,并将所述待加工工件中,除所述第一待加工工件之外的第二待加工工件加入所述第一当前批对应的候选列表中,并将所述第一当前批对应的候选列表作为所述第一当前批对应的当前候选列表;并返回执行所述根据所述第二待加工工件相对于所述第一当前批的信息素值、所述第一启发式信息以及所述第二启发式信息计算每一第二待加工工件的转移概率的步骤,直至所述第一当前批的剩余容量小于任意一个所述待加工工件的尺寸。
2.根据权利要求1所述的一种基于蚁群算法的工件调度方法,其特征在于,在根据目标值最小的蚂蚁对应的,加工设备与待加工工件之间的对应关系,获取所述目标值最小的蚂蚁对应的信息素增量值的步骤之前,所述方法还包括:针对所有只蚂蚁的每一台加工设备的每一个调度完成所述第二待加工工件的批,按照创建所述调度完成所述第二待加工工件的批的先后顺序进行编号;
将所述当前只蚂蚁对应的所有批中的编号最小的批作为第二当前批,将编号大于所述第二当前批的所有批中权重最大的第三待加工工件,与第二当前批中权重最小的第四待加工工件交换位置,且所述第四待加工工件的尺寸小于所述第三待加工工件所在批删除所述第三待加工工件后对应的剩余容量;所述第三待加工工件的尺寸小于所述第二当前批删除所述第四待加工工件后对应的剩余容量;
再将所述第二当前批的下一个批作为第二当前批,并返回执行所述将编号大于所述第二当前批的所有批中权重最大的第三待加工工件,与第二当前批中权重最小的第四待加工工件交换位置的步骤;直至所述当前只蚂蚁对应的批都被遍历;
将所述当前只蚂蚁的下一只蚂蚁作为当前只蚂蚁,并返回执行所述将所述当前只蚂蚁对应的所有批中的编号最小的批作为第二当前批的步骤,直至所有只蚂蚁都被遍历。
3.根据权利要求1所述的一种基于蚁群算法的工件调度方法,其特征在于,在根据目标值最小的蚂蚁对应的,加工设备与待加工工件之间的对应关系,获取所述目标值最小的蚂蚁对应的信息素增量值的步骤之前,所述方法还包括:针对所有只蚂蚁的每一个调度完成所述第二待加工工件的批,按照创建所述调度完成所述第二待加工工件的批的先后顺序进行编号;
将所述当前只蚂蚁对应的所有批中的编号最小的批作为第三当前批,将编号大于所述第三当前批的其他批中,含有的工件的权重之和最大的批,与所述第三当前批交换位置;
将所述第三当前批的下一个批作为第三当前批,并返回执行所述将所述当前只蚂蚁对应的所有批中的编号最小的批作为第三当前批,将编号大于所述第三当前批的其他批中,含有的工件的权重之和最大的批,与所述第三当前批交换位置的步骤;直至所述当前只蚂蚁对应的批都被遍历;
将所述当前只蚂蚁的下一只蚂蚁作为当前只蚂蚁,并返回执行所述将所述当前只蚂蚁对应的所有批中的编号最小的批作为第三当前批的步骤,直至所有的蚂蚁都被遍历。
4.根据权利要求2所述的一种基于蚁群算法的工件调度方法,其特征在于,所述根据所述第二待加工工件的权重获取其对应的第一启发式信息;根据所述第二待加工工件的尺寸的倒数获取其对应的第二启发式信息,包括:针对每一第二待加工工件,根据所述第二待加工工件的权重,利用公式,计算第一启发式信息,其中,
为编号为i的当前加工设备对应的编号为b的第一当前批对应的候选列表中的第二待加工工件j的第一启发式信息的值;wj为编号为i的当前加工设备对应的编号为b的第一当前批对应的候选列表中的第二待加工工件j的权重;i为所述当前加工设备对应的编号;b为所述第一当前批对应的编号;j为所述第二待加工工件对应的编号;
根据所述第二待加工工件的尺寸的倒数,利用公式, 计算第二启发式信息,其中,
为编号为i的当前加工设备对应的当前候选列表中的编号为j的第二待加工工件的第二启发式信息;sj为编号为i的当前加工设备对应的当前候选列表中的第二待加工工件j的尺寸。
5.根据权利要求4所述的一种基于蚁群算法的工件调度方法,其特征在于,所述根据所述第一待加工工件与第二待加工工件被分到所述第一当前批的期望值之和与所述第一待加工工件的数量的商计算所述第二待加工工件相对于所述第一当前批的信息素值,利用的公式为,
其中,
τjbi为编号为i的当前加工设备对应的编号为j的第二待加工工件相对于所述第一当前批的信息素值,为第二待加工工件j调度至第一当前批中的期望度;φj,x为第一待加工工件Jx和第二待加工工件jj被调度至所述第一当前批中的期望值,且φj,x的初始化值为((1‑ρ)*‑1
LB) ,ρ为预设的介于0和1之间的随机数;LB为预设的加权总完工时间的最小值。
6.根据权利要求5所述的一种基于蚁群算法的工件调度方法,其特征在于,所述根据所述第二待加工工件相对于所述第一当前批的信息素值、所述第一启发式信息以及所述第二启发式信息计算每一第二待加工工件的转移概率,包括:根据所述第二待加工工件相对于所述第一当前批的信息素值、所述第一启发式信息以及所述第二启发式信息,利用公式,
计算每一第二待加工工件的转移概率,其中,
Pjbi为编号为i的当前加工设备对应的编号为b的第一当前批对应的候选列表中的编号为j的第二待加工工件的转移概率;τjbi为编号为i的当前加工设备对应的编号为j的第二待加工工件相对于所述第一当前批的信息素值;τxbi为编号为i的当前加工设备对应的编号为x的第一待加工工件相对于所述第一当前批的信息素值;Lb为第二待加工工件的集合对应的当前候选列表;jj为第j个第二待加工工件。
7.根据权利要求6所述的一种基于蚁群算法的工件调度方法,其特征在于,所述根据目标值最小的蚂蚁对应的,加工设备与待加工工件之间的对应关系,获取所述目标值最小的蚂蚁对应的信息素增量值,利用的公式为,其中,
Δφxj(l)为第l次迭代时所述目标值最小的蚂蚁对应的信息素增量值;Q为是凭经验设定的一个参数,通常置为所有待加工工件的个数n;∑wjcj(l)为全局最优解,所有加权总完工时间的最小值,wj为全局最优解对应的工件j的权重;cj为全局最优解对应的工件j的完工时间;l为迭代次数;x为第一待加工工件;j为第二待加工工件;jj为第j个第二待加工工件;
jx为第x个第一待加工工件。
8.根据权利要求1所述的一种基于蚁群算法的工件调度方法,其特征在于,所述根据所述目标值最小的蚂蚁对应的所述信息素增量值、所述目标值最小的蚂蚁对应的信息素值以及信息素蒸发率,更新信息素矩阵,利用的公式为,φj,x(l+1)=(1‑ρ)*φj,x(l)+mj,x(l)*Δφj,x(l),其中,φj,x(l+1)为第l+1次迭代时对应的信息素矩阵;φj,x(l)为第l次迭代时对应的信息素矩阵;mj,x(l)为第l次迭代时工件j和工件x分在同一批中的频率;Δφj,x(l)为第l次迭代时所述目标值最小的蚂蚁对应的信息素增量值;ρ为信息素蒸发率;其中,所述目标值为所有待加工工件被加工完成后对应的加权总完工时间。
9.一种基于蚁群算法的工件调度装置,其特征在于,所述装置包括:建立模块、第一设置模块、调度模块、计算模块、第二设置模块、获取模块、更新模块、判断模块、第三设置模块和第四设置模块,其中,所述建立模块,用于在当前次迭代时,建立第一预设数量只蚂蚁,并为第一预设数量个蚂蚁中的当前只蚂蚁建立空批;
所述第一设置模块,用于将建立的所述空批作为所述当前只蚂蚁对应的第一当前批,针对所述第一当前批,从预设的加工设备中,将最先空闲的加工设备作为第一当前批对应的当前加工设备;将待加工工件中的第一待加工工件调度至所述第一当前批中;
所述调度模块,用于将所述待加工工件中,除所述第一待加工工件之外的第二待加工工件加入所述第一当前批对应的候选列表中,且每一个所述第二待加工工件尺寸不大于所述第一当前批的剩余容量;其中,所述第一当前批的剩余容量为,所述第一当前批的总容量与所述第一待加工工件总尺寸的差;
所述计算模块,用于根据所述候选列表中的每一第二待加工工件的权重和尺寸,计算所述候选列表中的第二待加工工件加入到所述第一当前批中的概率,并根据所述概率将第二待加工工件调度至所述第一当前批中,直至所述第一当前批的剩余容量小于任意一个所述待加工工件的尺寸;为所述当前只蚂蚁建立新的空批,将所述新的空批作为所述当前只蚂蚁对应的第一当前批,并触发所述第一设置模块,直至所有所述待加工工件都被调度至所述当前只蚂蚁对应的批中;
所述第二设置模块,用于将第一预设数量个蚂蚁中除当前只蚂蚁之外的其他蚂蚁中的一个作为当前只蚂蚁,并触发所述建立模块,直至所述第一预设数量个蚂蚁均具有能够容纳所有待加工工件的批;
所述获取模块,用于根据目标值最小的蚂蚁对应的,加工设备与待加工工件之间的对应关系,获取所述目标值最小的蚂蚁对应的信息素增量值,其中,所述目标值为,所有待加工工件被加工完成后对应的加权总完工时间;
所述更新模块,用于根据所述目标值最小的蚂蚁对应的所述信息素增量值、所述目标值最小的蚂蚁对应的信息素值以及信息素蒸发率,更新信息素矩阵,其中,所述目标值为所有待加工工件被加工完成后对应的加权总完工时间;
所述判断模块,用于判断当前次迭代对应的迭代次数是否等于最大迭代次数;
所述第三设置模块,用于在所述判断模块的判断结果为否的情况下,将所述当前次迭代对应的迭代次数与预设值之和作为当前次迭代的下一次迭代的迭代次数,并触发所述建立模块;
所述第四设置模块,用于在所述判断模块的判断结果为否的情况下,将当前次迭代中目标值最小的蚂蚁对应的,加工设备与待加工工件之间的对应关系作为目标调度方法;
所述根据所述候选列表中的每一第二待加工工件的权重和尺寸,计算所述候选列表中的第二待加工工件加入到所述第一当前批中的概率,并根据所述概率将第二待加工工件调度至所述第一当前批中,包括:
将所述候选列表作为当前候选列表,针对所述当前候选列表中的每一第二待加工工件,根据所述第二待加工工件的权重获取其对应的第一启发式信息;根据所述第二待加工工件的尺寸的倒数获取其对应的第二启发式信息;
根据所述第一待加工工件与第二待加工工件被分到所述第一当前批的期望值之和与所述第一待加工工件的数量的商计算所述第二待加工工件相对于所述第一当前批的信息素值;
根据所述第二待加工工件相对于所述第一当前批的信息素值、所述第一启发式信息以及所述第二启发式信息计算每一第二待加工工件的转移概率;
将所述转移概率最大的第二待加工工件调度至所述第一当前批中;将所述转移概率最大的第二待加工工件与所述第一待加工工件的集合作为第一待加工工件,并将所述待加工工件中,除所述第一待加工工件之外的第二待加工工件加入所述第一当前批对应的候选列表中,并将所述第一当前批对应的候选列表作为所述第一当前批对应的当前候选列表;并返回执行所述根据所述第二待加工工件相对于所述第一当前批的信息素值、所述第一启发式信息以及所述第二启发式信息计算每一第二待加工工件的转移概率的步骤,直至所述第一当前批的剩余容量小于任意一个所述待加工工件的尺寸。