1.一种基于蚁群优化算法的工件调度方法,其特征是应用在分时电价的生产条件下,将n个工件分批调度到K台相同的批处理机器上加工的调度方案中,所述调度方案是以电力成本A和延迟程度B为优化目标;所述分时电价为关于时间的阶梯函数,0时刻为高电价起点,高电价时段长度为UH,高电价时段电力价格为CH,低电价时段长度为UL,低电价价格为CL,每个高电价时段的结束时刻均为低电价时段的开始时刻,每个低电价时段的结束时刻均为高电价时段的开始时刻;
记第j个工件的尺寸为sj,第j个工件的到达时间为aj,第j个工件的加工时长为pj,第j个工件的截止时间为dj,第j个工件的权重为wj;第j个工件的开始加工时间为第j个工件的所在批的开始加工时间;第j个工件的完工时间为第j个工件的所在批的开始加工时间与所在批的加工时长之和;第j个工件的延迟时间为第j个工件完工时间与第j个工件的截止时间之差;当第j个工件的延迟时间为负数时,表示第j个工件未延迟,则令第j个工件延迟时间为“0”;1≤j≤n;
记第b个批的加工时长Pb为第b个批中所有工件加工时长的最大值;第b个批的到达时间Ab为第b个批中所有工件到达时间的最大值;第b个批的完工时间Eb为第b个批的开始加工时间Xb与第b个批的加工时长Pb之和;第b个批的开始加工时间Xb为第b个批所在的批处理机器上的第b-1个批的完工时间Eb-1与第b个批的达到时间之间Ab的较大值;第b个批的截止时间Db为第b个批中所有工件截止时间的最小值;
记第k台批处理机器的加工功率为Hp,第k台批处理机器的待机功率为Hw,第k台批处理机器的容量记为B;第k台批处理机器的完工时间为第k台批处理机器上的最后一个批的完工时间;1≤k≤K;
以所有工件的延迟时间乘以相应工件的权重之和来表示延迟程度B;以加工电力成本和待机电力成本的总和来表示电力成本A;所述加工电力成本为所有批处理机器的加工功率乘以加工时长乘以分时电价之和;所述待机电力成本为所有批处理机器的待机功率乘以待机时长乘以分时电价之和;
所述工件调度方法是按照如下步骤进行:
步骤1、对n个工件进行预分批,得到以电力成本A为优化目标的预调度方案,并计算相应预调度方案的电力成本值记为LA;
步骤2、对n个工件进行预分批,得到以延迟程度B为优化目标的预调度方案,并计算相应预调度方案的延迟程度值记为LB;
步骤3、使用式(3)和式(4)获得以电力成本A为优化目标的信息素的上限 和下限式(3)和式(4)中,ρ为信息素蒸发率,μ为算法所设定的参数值;
同理获得,以延迟程度B为优化目标的信息素的上限 和下限
步骤4、初始化蚁群算法的参数:
令Lmax表示最大迭代次数,L表示当前迭代的次数;T表示蚂蚁总数,t表示每次迭代中第t只蚂蚁的编号;并初始化为L=1;
以电力成本值LA作为从初始化到第L-1次迭代的全局最小电力成本值 以电力成本值LA作为第L-1次迭代的最小电力成本值 以延迟程度值LB作为从初始化到第L-1次迭代的全局最小延迟程度值 以延迟程度值LB作为第L-1次迭代的最小延迟程度值建立以电力成本A为优化目标的信息素矩阵,并初始化相应信息素矩阵中每个元素的值为 得到第L-1次迭代的电力成本A的信息素矩阵;记第L-1次迭代的电力成本A的信息素矩阵中第i行第j列的元素为 1≤i,j≤n;
建立以延迟程度B为优化目标的信息素矩阵,并初始化相应信息素矩阵中每个元素的值为 得到第L-1次迭代的延迟程度B的信息素矩阵;记第L-1次迭代的延迟程度B的信息素矩阵中第i行第j列的元素为 1≤i,j≤n;
利用式(1)和式(2)分别获得第t只蚂蚁的电力成本A的目标偏好FtA和延迟程度B的目标偏好FtB,从而获得所有蚂蚁的电力成本A的目标偏好和延迟程度B的目标偏好:FtB=1-FtA (2)
步骤5、初始化t=1;
步骤6、构建第L次迭代第t只蚂蚁的调度方案;
步骤7、对第L次迭代第t只蚂蚁的调度方案进行优化,得到改进的调度方案;
步骤8、令t+1赋值给t,并判断t>T是否成立,若成立,则执行步骤9;否则,执行步骤6;
步骤9、分别计算第L次迭代所有蚂蚁的调度方案的电力成本值A和延迟程度值B;
选取第L次迭代中最小的电力成本值 赋值给 并将 与 作比较,选取较小值作为从初始化到第L次迭代的全局最优电力成本 从而根据 利用式(3)和式(4)更新电力成本A的信息素的上限 和下限 得到第L次迭代的电力成本A的信息素的上限和下限选取第L次迭代中最小的延迟程度值 赋值给 并将 与 作比较,选取较小值作为从初始化到第L次迭代的全局最优延迟程度 从而根据 同理获得,第L次迭代的延迟程度B的信息素的上限 和下限步骤10、以所述第L次迭代的电力成本A的信息素的上限 和下限 的约束下,利用更新第L-1次迭代的电力成本A的信息素矩阵,得到第L次迭代的电力成本A的信息素矩阵;
以所述第L次迭代的延迟程度B的信息素的上限 和下限 的约束下,利用 更新第L-1次迭代的延迟程度B的信息素矩阵,得到第L次迭代的延迟程度B的信息素矩阵;
步骤11、将所述第L次迭代的所有蚂蚁的调度方案加入第L次迭代的解集中,从所述第L次迭代的解集中删除Pareto被支配解对应的工件调度方案,从而更新所述第L次迭代的解集并作为第L+1次迭代的解集;
步骤12、令L+1赋值给L,并判断L>Lmax是否成立,若成立,则输出第L次迭代的解集作为全局最优调度方案;否则,执行步骤5。
2.根据权利要求1所述的工件调度方法,其特征是,所述步骤1中的预分批是按如下过程进行:步骤1.1将n个工件按照各自的到达时间升序排列,得到排序后的n个工件;
步骤1.2定义批的个数为b;初始化j=1,b=1;
步骤1.3构建第b个空批;
步骤1.4将排序后的第j个工件加入第b个批中,判断j+1>n是否成立,若成立,表示预分批完成,从而得到B1个批,并执行步骤1.6,否则,执行步骤1.5;
步骤1.5判断第j+1个工件是否大于第b个批的剩余空间,若大于,则将j+1赋值给j,将b+1赋值给b后,返回步骤1.3;否则,将j+1赋值给j后,返回步骤1.4;
步骤1.6初始化b=1;
步骤1.7遍历K台批处理机器并找到完工时间最早的机器,记为当前批处理机器;
步骤1.8将第b个批放入当前批处理机器上生产,从而更新当前批处理机器的完工时间为第b个批的完工时间;将b+1赋值给b,若b>B1成立,则表示B1个批完成生产,得到预调度方案,否则,执行步骤1.7。
3.根据权利要求1所述的工件调度方法,其特征是,所述步骤2中的预分批是按如下过程进行:步骤3.1将n个工件按照各自的到达时间升序排列,得到排序后的n个工件;
步骤3.2定义批的个数为b;初始化j=1,b=1;
步骤3.3构建第b个空批;
步骤3.4判断排序后的第j个工件的到达时间aj是否小于第b个批的到达时间Ab,若小于,则将第j个工件放入待生产工件集合中,否则,执行步骤3.6;
步骤3.5将j+1赋值给j后,判断j>n是否成立,若成立,则执行步骤3.6;否则,执行步骤
3.4;
步骤3.6判断所述待生产工件集合是否为空集,若为空集,则执行步骤3.7,否则,从所述待生产工件集合中选择权重最大的工件,并判断权重最大的工件的尺寸是否大于第b个批的剩余空间,若大于,则将b+1赋值给b后,执行步骤3.3;否则,将权重最大的工件从所述待生产工件集合中删除并加入第b个批中后,执行步骤3.6;
步骤3.7判断第j个工件的尺寸sj是否大于第b个批的剩余空间,若大于,将b+1赋值给b后,返回步骤3.3;否则,将第j个工件加入第b个批中;
步骤3.8判断j+1>n是否成立,若成立,表示预分批完成,从而得到B2个批,并执行步骤
3.9;否则,将j+1赋值给j后,执行步骤3.4;
步骤3.9初始化b=1;
步骤3.7遍历K台批处理机器并找到完工时间最早的机器,记为当前批处理机器;
步骤3.8将第b个批放入当前批处理机器上生产,从而更新当前批处理机器的完工时间为第b个批的完工时间;将b+1赋值给b,若b>B2成立,则表示B2个批完成生产,得到关于延迟程度的预调度方案;否则,执行步骤3.7。
4.根据权利要求1所述的工件调度方法,其特征是,所述步骤6是按如下过程进行:步骤6.1、遍历K台批处理机器,选择完工时间最小的机器,记为第k台批处理机器;创建第L次迭代的第t只蚂蚁在所述第k台批处理机器上的第b个批;
步骤6.2、构建工件集合List1、List2和List3;
将工件的截止时间小于第b个批的开工时间的所有工件加入所述工件集合List1中;
将工件的到达时间小于等于第b个批的开工时间,且工件的截止时间大于第b个批的开工时间的所有工件加入所述工件集合List2中;
将工件的到达时间大于批的开工时间的所有工件加入所述工件集合List3中;
步骤6.3、判断List1是否为空集,若为空集,则执行步骤6.4,否则,利用式(5)计算所述工件集合List1中第j个工件加入第L次迭代的第t只蚂蚁在第k台机器上第b个批的选定概率pLtkbj:式(5)中,ALtkb表示第L次次迭代的第t只蚂蚁在第k台机器上第b个批的到达时间;
先使用轮盘赌方法从工件集合List1中选择一个工件,然后将选中的工件从集合List1中删除并加入第L次迭代的第t只蚂蚁在第k台机器上的第b个批中,然后执行步骤6.6;
步骤6.4判断List2是否为空集,若为空集,则执行步骤6.5,否则,从所述工件集合List2中随机选一个工件,然后将选中的工件从List1集合中删除并加入第L次迭代的第t只蚂蚁在第k台机器上的第b个批中,然后执行步骤6.6;
步骤6.5判断List3是否为空集,若为空集,则删除第L次迭代的第t只蚂蚁在第k台机器上的第b个批,从而表示完成第L次迭代的第t只蚂蚁的调度方案的构建;否则,从所述工件集合List3中选择达到时间最小的工件,然后将选中工件从List3集合中删除并加入所述第L次迭代的第t只蚂蚁在第k台机器上的第b个批中;
步骤6.6构建工件集合TotalList,将List1、List2和List3中的工件全部加入到工件集合TotaList中;
步骤6.7如果工件集合TotalList为空,则表示完成第L次迭代的第t只蚂蚁的调度方案的构建,否则,将工件集合TotalList中工件尺寸小于等于第k台机器上的第b个批的剩余空间,且工件的截止时间小于等于第k台机器上的第b个批的开工时间的工件加入到工件集合List1中;
将工件集合TotalList中工件尺寸小于等于第k台机器上的第b个批的剩余空间,工件的到达时间小于等于第k台机器上的第b个批的开工时间,且工件的截止时间大于第k台机器上的第b个批的开工时间的工件加入到工件集合List2中;
将工件集合TotalList中工件尺寸小于第k台机器上的第b个批的剩余空间,且工件的到达时间大于第k台机器上的第b个批的开工时间的工件加入到工件集合List3中;
步骤6.8判断集合List1是否为空集,若为空集,则执行步骤6.9,否则,利用式(6)和式(7)计算所述工件加工集合List1中第j个工件加入第L次迭代的第t中蚂蚁在第k台机器上的第b个批的关于电力成本A的启发式信息 和关于延迟程度B的启发式信息 并执行步骤6.10;
式(6)和式(7)中,PLtkb表示第L次迭代的第t中蚂蚁在第k台机器上的第b个批的加工时长,Wmax指工件权重取值范围的最大值;
步骤6.9判断集合List2是否为空集,如果是空集,则执行步骤6.11,否则,使用式(6)和式(8)计算启发式信息 和 并执行步骤6.10;
式(8)中,|List2|表示步骤6.7中的工件集合List2内的工件总数;
步骤6.10设置工件集合List,若工件集合List1不为空,则将List1中的工件全部加入List中,否则将工件集合List2中的工件全部加入到List中;
使用式(9)计算工件集合List中第j个工件加入第L次迭代的第t只蚂蚁在第k台机器上的第b个批的平均信息素值式(9)中,QLtkb表示所述第L次迭代的第t个蚂蚁在第k个机器中的第b个批,|QLtkn|表示第L次迭代的第t个蚂蚁在第k个机器中的第b个批QLtkb中的工件总数;
使用式(10)计算工件集合List中第j个工件加入第L次迭代的第t只蚂蚁在第k台机器上的第b个批的概率PLtkbj:式(10)中,α、β和γ为所设定的经验值;|List|表示工件集合List中的工件总数;
利用概率PLtkbj通过轮盘赌方法从所述工件集合List中选取工件加入到第L次迭代的第t个蚂蚁在第k个机器中的第b个批QLtkb中,然后将工件集合List、List1、List2和List3中的所有工件加入到工件集合TotalList中,并执行步骤6.7;
步骤6.11判断工件集合List3是否为空集,若为空集则执行步骤6.1,否则选取所述工件集合List3中到达时间最小的工件,记为当前工件;
若当前工件的到达时间小于批QLtkb的截止时间,则将当前工件从工件集合List3中删除并加入到批QLtkb中后,执行步骤6.6,否则执行步骤6.1。
5.根据权利要求1所述的工件调度方法,其特征是,所述步骤7是按如下过程进行:步骤7.1初始化变量k=1,b=1;
步骤7.2计算调度方案中的第k台批处理机器的第b个批Qkb的剩余空间;
步骤7.3初始化变量u=1,v=1;
步骤7.4判断所述调度方案中第u台批处理机器的第v个批Quv的开工时间是否小于或等于批Qkb的开工时间,若是,执行步骤7.5,否则构建工件集合List,从批Quv中选出同时满足下列三个条件的工件放入工件集合List中:条件1:工件的尺寸小于等于批Qkb的剩余空间;
条件2:工件的到达时间小于等于批Qkb的开工时间;
条件3:工件的加工时长小于等于批Qkb的截止时间Dkb与批Qkb开工时间Xkb之差;
如果List为空,则执行步骤7.5,否则,将工件的截止时间最小的工件从工件集合List中删除并放入批Qkb中,再将工件集合List中剩余工件放回批Quv中后,执行步骤7.5;
步骤7.5将v+1赋值给v,判断v是否小于第u台批处理机器中的批数量,若是,则执行步骤7.3,否则,执行步骤7.6;
步骤7.6将u+1赋值给u,令v=1,判断u是否小于批处理机器的数量K,若是,则执行步骤
7.3,否则,执行步骤7.7;
步骤7.7将b+1赋值给b,如果b小于第k台批处理机器中的批数量,则执行步骤7.1,否则执行步骤7.8;
步骤7.8将k+1赋值给k,令b=1,判断k是否小于批处理机器的数量K,若小于,则执行步骤7.1,否则执行步骤7.9;
步骤7.9初始化变量k=1,b=2;
步骤7.10令Qk(b-1)表示第k个机器的第b-1个批,如果批Qkb的完工时间小于批Qkb的截止时间,则执行步骤7.11,否则,分别计算批Qk(b-1)与批Qkb在交换加工顺序前与交换加工顺序后的工件延迟程度之和,若交换加工顺序前的工件延迟程度之和小于交换加工顺序后的工件延迟程度之和,则执行步骤7.11,否则,将交换批Qk(b-1)与批Qkb的加工顺序后,执行步骤
7.11;
步骤7.11将b+1赋值给b,如果b小于第k个批处理机器上的批数量,则执行步骤7.10,否则,将k+1赋值给k,令b=2后,判断k≤K是否成立,若成立,则执行步骤7.10,否则,执行步骤
7.12;
步骤7.12初始化变量k=1;
步骤7.13将第k台批处理机器上的批总数赋值给变量b;
步骤7.14判断第k台处理机器上第b个批Qkb的截止时间是否小于批Qkb的完工时间,若是,则执行步骤7.19,否则,使用式(11)判断批Qkb完工时间是否处于低电价区域,若是,则执行步骤7.17,否则,执行步骤7.15;
式(11)中,t为当前时刻,f(t)为t时刻所对应的电价;k表示周期数,k∈{0,1,2,…};
步骤7.15判断批Qkb的截止时间是否小于 若是,则执
行步骤7.19,否则,执行步骤7.16;
步骤7.16判断批Qkb的截止时间是否大于或等于
若是,则将批Qkb的开工时间改为 否则,将批Qkb的开工时
间改为批Qkb的截止时间Dkb与批Qkb的处理时长Pkb之差;执行步骤7.19;
步骤7.17利用式(11)判断批Qkb的开始加工时间是否处于低电价区域,若是,则执行步骤7.19,否则,执行步骤7.18;
步骤7.18使用式(11)判断批Qkb的截止时间是否大于
若是,则将批Qkb的开工时间改为 否则,将批Qkb的开工时间
改为批Qkb的截止时间与批Qkb的加工时长Pkb之差;
步骤7.19将b-1赋值给b,如果b不等于0,则执行步骤7.21,否则将k+1赋值给k后,执行步骤7.20;
步骤7.20判断k是否大于K,若是,则表示对于调度方案的优化已经完成,否则,则将第k台批处理机器中的批总数赋值给b后,执行步骤7.21;
步骤7.21判断批Qkb的截止时间是否小于批Qkb的完工时间,若是,则执行步骤7.19,否则,执行步骤7.22;
步骤7.22使用式(11)判断批Qkb的开工时间Xkb是否处于高电价时段,若是,则执行步骤
7.23,否则,则执行步骤7.24
步骤7.23判断批Qkb的截止时间Dkb和批Qk(b+1)的开工时间Xk(b+1)是否同时大于若是,将批Qkb的开工时间延迟为min(Dkb,Xk(b+1))-Pkb,执行步骤7.19;否则,直接执行步骤7.19;
步骤7.24判断批Qkb的完工时间是否处于低电价区域,若是,则执行步骤7.19,若否,则判断批Qkb的截止时间Dkb和批Qk(b+1)的开工时间Xk(b+1)是否同时大于若是,则令批Qkb的开工时间延迟为min(Dkb,
Xk(b+1))+Pkb,执行步骤7.19,否则直接执行步骤7.19。