一种基于蚁群算法的多目标工件调度算法

摘要

本发明公开了一种基于蚁群优化算法的工件调度方法，其特征是使用Pareto的多目标方法，在调度过程中通过工件特征对工件进行有效选择，优先利用低电价时间段进行生产，从而实现优化电力成本A和延迟程度B的两个目标。本发明通过本发明在工业分时电价背景的平行批处理机环境下，计算得到更好的工件调度方案，最大化企业资源的利用率及其对能源的使用效率，达到对企业生产过程中的成本控制和生产效果的优化，从而提高企业的市场竞争力。

说明书

技术领域

本发明属于工业生产调度领域，是一种基于蚁群算法的多目标工件调度算法。

背景技术

在当前市场环境中，制造型企业的核心竞争力不止是简单的制造能力，还要有优秀的生产调度算法来合理利用资源和设备，提高资源和设备的利用率，以此达到降低成本增加竞争力的目的。市场上现有的工件调度算法虽然也能够在一定程度上找到可行解，但是往往对应的问题模型较简单，从而不能完全适用于实际生产环境下的问题，从而因为算法的适用场景较局限，导致找到的解的质量不够高。由于实际计算中工件约束条件较多，对动态阶梯电价下的能源利用效率较弱，并且现存算法往往是针对单个目标进行优化，难以满足企业对多个目标同时优化的需求。

发明内容

本发明为克服现有技术中的不足之处，提供一种基于蚁群算法的多目标工件调度算法，以期在工业分时电价背景平行批处理机环境下，计算得到更好的工件调度方案，以最大化企业资源和能源的利用率，从而达到对企业生产过程中的成本控制和生产效果的优化，并提高企业的市场竞争力。

本发明为解决技术问题采用如下技术方案：

本发明一种基于蚁群优化算法的工件调度方法的特点是应用在分时电价的生产条件下，将n个工件分批调度到K台相同的批处理机器上加工的调度方案中，所述调度方案是以电力成本A和延迟程度B为优化目标；所述分时电价为关于时间的阶梯函数，0时刻为高电价起点，高电价时段长度为U_H，高电价时段电力价格为C_H，低电价时段长度为U_L，低电价价格为C_L，每个高电价时段的结束时刻均为低电价时段的开始时刻，每个低电价时段的结束时刻均为高电价时段的开始时刻；

记第j个工件的尺寸为s_j，第j个工件的到达时间为a_j，第j个工件的加工时长为p_j，第j个工件的截止时间为d_j，第j个工件的权重为w_j；第j个工件的开始加工时间为第j个工件的所在批的开始加工时间；第j个工件的完工时间为第j个工件的所在批的开始加工时间与所在批的加工时长之和；第j个工件的延迟时间为第j个工件完工时间与第j个工件的截止时间之差；当第j个工件的延迟时间为负数时，表示第j个工件未延迟，则令第j个工件延迟时间为“0”；1≤j≤n；

记第b个批的加工时长P_b为第b个批中所有工件加工时长的最大值；第b个批的到达时间A_b为第b个批中所有工件到达时间的最大值；第b个批的完工时间E_b为第b个批的开始加工时间X_b与第b个批的加工时长P_b之和；第b个批的开始加工时间X_b为第b个批所在的批处理机器上的第b-1个批的完工时间E_b-1与第b个批的达到时间之间A_b的较大值；第b个批的截止时间D_b为第b个批中所有工件截止时间的最小值；

记第k台批处理机器的加工功率为H_p，第k台批处理机器的待机功率为H_w，第k台批处理机器的容量记为B；第k台批处理机器的完工时间为第k台批处理机器上的最后一个批的完工时间；1≤k≤K；

以所有工件的延迟时间乘以相应工件的权重之和来表示延迟程度B；以加工电力成本和待机电力成本的总和来表示电力成本A；所述加工电力成本为所有批处理机器的加工功率乘以加工时长乘以分时电价之和；所述待机电力成本为所有批处理机器的待机功率乘以待机时长乘以分时电价之和；

所述工件调度方法是按照如下步骤进行：

步骤1、对n个工件进行预分批，得到以电力成本A为优化目标的预调度方案，并计算相应预调度方案的电力成本值记为L_A；

步骤2、对n个工件进行预分批，得到以延迟程度B为优化目标的预调度方案，并计算相应预调度方案的延迟程度值记为L_B；

步骤3、使用式(3)和式(4)获得以电力成本A为优化目标的信息素的上限和下限

式(3)和式(4)中，ρ为信息素蒸发率，μ为算法所设定的参数值；

同理获得，以延迟程度B为优化目标的信息素的上限和下限

步骤4、初始化蚁群算法的参数：

令L_max表示最大迭代次数，L表示当前迭代的次数；T表示蚂蚁总数，t表示每次迭代中第t只蚂蚁的编号；并初始化为L＝1；

以电力成本值L_A作为从初始化到第L-1次迭代的全局最小电力成本值以电力成本值L_A作为第L-1次迭代的最小电力成本值以延迟程度值L_B作为从初始化到第L-1次迭代的全局最小延迟程度值以延迟程度值L_B作为第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的目标偏好F_t^A和延迟程度B的目标偏好F_t^B，从而获得所有蚂蚁的电力成本A的目标偏好和延迟程度B的目标偏好：

F_t^B＝1-F_t^A>

步骤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＞L_max是否成立，若成立，则输出第L次迭代的解集作为全局最优调度方案；否则，执行步骤5。

本发明所述的工件调度方法的特点也在于，所述步骤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。

所述步骤2中的预分批是按如下过程进行：

步骤3.1将n个工件按照各自的到达时间升序排列，得到排序后的n个工件；

步骤3.2定义批的个数为b；初始化j＝1，b＝1；

步骤3.3构建第b个空批；

步骤3.4判断排序后的第j个工件的到达时间a_j是否小于第b个批的到达时间A_b，若小于，则将第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个工件的尺寸s_j是否大于第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。

所述步骤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个批的选定概率p_Ltkbj：

式(5)中，A_Ltkb表示第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)中，P_Ltkb表示第L次迭代的第t中蚂蚁在第k台机器上的第b个批的加工时长，W_max指工件权重取值范围的最大值；

步骤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)中，Q_Ltkb表示所述第L次迭代的第t个蚂蚁在第k个机器中的第b个批，|Q_Ltkn|表示第L次迭代的第t个蚂蚁在第k个机器中的第b个批Q_Ltkb中的工件总数；

使用式(10)计算工件集合List中第j个工件加入第L次迭代的第t只蚂蚁在第k台机器上的第b个批的概率P_Ltkbj：

式(10)中，α、β和γ为所设定的经验值；|List|表示工件集合List中的工件总数；

利用概率P_Ltkbj通过轮盘赌方法从所述工件集合List中选取工件加入到第L次迭代的第t个蚂蚁在第k个机器中的第b个批Q_Ltkb中，然后将工件集合List、List1、List2和List3中的所有工件加入到工件集合TotalList中，并执行步骤6.7；

步骤6.11判断工件集合List3是否为空集，若为空集则执行步骤6.1，否则选取所述工件集合List3中到达时间最小的工件，记为当前工件；

若当前工件的到达时间小于批Q_Ltkb的截止时间，则将当前工件从工件集合List3中删除并加入到批Q_Ltkb中后，执行步骤6.6，否则执行步骤6.1。

所述步骤7是按如下过程进行：

步骤7.1初始化变量k＝1，b＝1；

步骤7.2计算调度方案中的第k台批处理机器的第b个批Q_kb的剩余空间；

步骤7.3初始化变量u＝1，v＝1；

步骤7.4判断所述调度方案中第u台批处理机器的第v个批Q_uv的开工时间是否小于或等于批Q_kb的开工时间，若是，执行步骤7.5，否则构建工件集合List，从批Q_uv中选出同时满足下列三个条件的工件放入工件集合List中：

条件1：工件的尺寸小于等于批Q_kb的剩余空间；

条件2：工件的到达时间小于等于批Q_kb的开工时间；

条件3：工件的加工时长小于等于批Q_kb的截止时间D_kb与批Q_kb开工时间X_kb之差；

如果List为空，则执行步骤7.5，否则，将工件的截止时间最小的工件从工件集合List中删除并放入批Q_kb中，再将工件集合List中剩余工件放回批Q_uv中后，执行步骤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令Q_k(b-1)表示第k个机器的第b-1个批，如果批Q_kb的完工时间小于批Q_kb的截止时间，则执行步骤7.11，否则，分别计算批Q_k(b-1)与批Q_kb在交换加工顺序前与交换加工顺序后的工件延迟程度之和，若交换加工顺序前的工件延迟程度之和小于交换加工顺序后的工件延迟程度之和，则执行步骤7.11，否则，将交换批Q_k(b-1)与批Q_kb的加工顺序后，执行步骤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个批Q_kb的截止时间是否小于批Q_kb的完工时间，若是，则执行步骤7.19，否则，使用式(11)判断批Q_kb完工时间是否处于低电价区域，若是，则执行步骤7.17，否则，执行步骤7.15；

式(11)中，t为当前时刻，f(t)为t时刻所对应的电价；k表示周期数，k∈{0,1,2,…}；

步骤7.15判断批Q_kb的截止时间是否小于若是，则执行步骤7.19，否则，执行步骤7.16；

步骤7.16判断批Q_kb的截止时间是否大于或等于若是，则将批Q_kb的开工时间改为否则，将批Q_kb的开工时间改为批Q_kb的截止时间D_kb与批Q_kb的处理时长P_kb之差；执行步骤7.19；

步骤7.17利用式(11)判断批Q_kb的开始加工时间是否处于低电价区域，若是，则执行步骤7.19，否则，执行步骤7.18；

步骤7.18使用式(11)判断批Q_kb的截止时间是否大于若是，则将批Q_kb的开工时间改为否则，将批Q_kb的开工时间改为批Q_kb的截止时间与批Q_kb的加工时长P_kb之差；

步骤7.19将b-1赋值给b，如果b不等于0，则执行步骤7.21，否则将k+1赋值给k后，执行步骤7.20；

步骤7.20判断k是否大于K，若是，则表示对于调度方案的优化已经完成，否则，则将第k台批处理机器中的批总数赋值给b后，执行步骤7.21；

步骤7.21判断批Q_kb的截止时间是否小于批Q_kb的完工时间，若是，则执行步骤7.19，否则，执行步骤7.22；

步骤7.22使用式(11)判断批Q_kb的开工时间X_kb是否处于高电价时段，若是，则执行步骤7.23，否则，则执行步骤7.24

步骤7.23判断批Q_kb的截止时间D_kb和批Q_k(b+1)的开工时间X_k(b+1)是否同时大于若是，将批Q_kb的开工时间延迟为min(D_kb,X_k(b+1))-P_kb，执行步骤7.19；否则，直接执行步骤7.19；

步骤7.24判断批Q_kb的完工时间是否处于低电价区域，若是，则执行步骤7.19，若否，则判断批Q_kb的截止时间D_kb和批Q_k(b+1)的开工时间X_k(b+1)是否同时大于若是，则令批Q_kb的开工时间延迟为min(D_kb,X_k(b+1))+P_kb，执行步骤7.19，否则直接执行步骤7.19。

与已有技术相比，本发明的有益效果体现在：

1、目前已有的基于蚁群算法的多目标调度算法都将每个蚂蚁视为相同的个体，并在每次计算工件加入批的转移概率时随机生成信息素偏好，而本发明采用了阶梯式目标信息素偏好，在初始化时为每只蚂蚁设置不同的信息素偏好，而且整个蚁群中的蚂蚁对不同信息素的偏好在整体上呈现阶梯状分布，从而使得每个蚂蚁都是具有不同偏好的个体，在实际寻找解的过程中，这些蚂蚁使用相同的信息素矩阵但是有着不同的目标偏好，使得在寻找解时能够使得最终的解集中的解分布比较均匀，从而满足了决策者多样化的需求。

2、本发明根据问题背景设计了有效的优化方法，包含三个方面：(1)从工件的角度提高了批的空间利用率。即，从开工时间大的批中选择符合条件的工件，将选中的工件从原批中删除并加入开工时间小的批中，从而减小了开工时间小的批的剩余空间，从整体上提高了批的空间利用率，以减少批的总数；(2)从批序列的角度优化了总延迟程度。即，在同一批处理机器上，交换符合条件的两个相邻的批的加工顺序，在到达时间相近的前提下，优先加工截止时间小的批，从而达到了降低总体延迟程度的目的；(3)从分时电价的角度优化了电力成本。即，通过适当延迟批的开工时间，在不增加延迟程度的基础上将批的加工时段尽量往低电价时段移动，从而达到了减少调度方案的电力成本目标的目的。通过以上三个方面的优化，能够在延迟程度和电力成本两个目标上同时优化工件调度方案，提高了算法求解所得调度方案的质量。

3、本发明在计算启发式时，根据工件到达时间与工件截止时间与批开工时间的不同，设计了不同的候选表，并根据不同的候选表设计了不同的启发式信息素，使得算法更加切合使用背景，更加细致，加快了搜索解的进程和提高了搜索解的质量。

4、本发明采用动态信息素取值范围上限τ_max和信息素取值范围下限τ_min的计算方案，首先使用预调度方案的目标值初始化相应信息素矩阵的信息素取值范围上限τ_max和下限τ_min，然后在每次迭代后选择对应目标上全局最优的解更新对应目标的信息素上限τ_max和下限τ_min，解决了由于问题过于复杂导致有效目标下界难以获取，从而难以确定信息素上界和下界的问题。相比于其他蚁群算法采用的固定信息素范围的方法，该策略不仅有助于高效找到质量更好的解，而且有效避免了下界计算不准确而造成的不良后果，使得算法更加灵活和准确。

5、本发明使用每一次迭代中的单目标方向上的最优调度方案的目标值来更新对应信息素矩阵，每次只使用一只单目标上单次迭代最优蚂蚁来更新对应的信息素矩阵，使得信息素矩阵能够得到更准确的进化和更新。

6、本发明使用Pareto多目标方法，在调度过程中通过利用工件特征对工件进行分类调度，优先利用低电价时间段进行生产，实现了双目标的同时优化。

附图说明

图1为本发明算法流程图；

图2为本发明算法与经典多目标算法SPEA2算法运算结果对比图；

图3为优化调度方案中将后加工的批中符合条件的工件移动到先加工的批中的示意图；

图4为优化调度方案中将相邻的批交换加工顺序的示意图；

图5为优化调度方案中将批开工时间后移以此减少电力成本的典型情景示意图。

具体实施方式

本实施例中，一种基于蚁群优化算法的工件调度方法，是应用在分时电价的生产条件下，将n个工件分批调度到K台相同的批处理机器上加工的调度方案中，调度方案是以电力成本A和延迟程度B为优化目标；分时电价为关于时间的阶梯函数，0时刻为高电价起点，高电价时段长度为U_H，高电价时段电力价格为C_H，低电价时段长度为U_L，低电价价格为C_L，每个高电价时段的结束时刻均为低电价时段的开始时刻，每个低电价时段的结束时刻均为高电价时段的开始时刻；

记第j个工件的尺寸为s_j，第j个工件的到达时间为a_j，第j个工件的加工时长为p_j，第j个工件的截止时间为d_j，第j个工件的权重为w_j；第j个工件的开始加工时间为第j个工件的所在批的开始加工时间；第j个工件的完工时间为第j个工件的所在批的开始加工时间与所在批的加工时长之和；第j个工件的延迟时间为第j个工件完工时间与第j个工件的截止时间之差；当第j个工件的延迟时间为负数时，表示第j个工件未延迟，则令第j个工件延迟时间为“0”；1≤j≤n；

记第b个批的加工时长P_b为第b个批中所有工件加工时长的最大值；第b个批的到达时间A_b为第b个批中所有工件到达时间的最大值；第b个批的完工时间E_b为第b个批的开始加工时间X_b与第b个批的加工时长P_b之和；第b个批的开始加工时间X_b为第b个批所在的批处理机器上的第b-1个批的完工时间E_b-1与第b个批的达到时间之间A_b的较大值；第b个批的截止时间D_b为第b个批中所有工件截止时间的最小值；

记第k台批处理机器的加工功率为H_p，第k台批处理机器的待机功率为H_w，第k台批处理机器的容量记为B；第k台批处理机器的完工时间为第k台批处理机器上的最后一个批的完工时间；1≤k≤K；

以所有工件的延迟时间乘以相应工件的权重之和来表示延迟程度B；以加工电力成本和待机电力成本的总和来表示电力成本A；加工电力成本为所有批处理机器的加工功率乘以加工时长乘以分时电价之和；待机电力成本为所有批处理机器的待机功率乘以待机时长乘以分时电价之和；

具体的说，如图1所示，工件调度方法是按照如下步骤进行：

步骤1、对n个工件进行预分批，得到以电力成本A为优化目标的预调度方案，并计算相应预调度方案的电力成本值记为L_A；具体的，

步骤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。

步骤2、对n个工件进行预分批，得到以延迟程度B为优化目标的预调度方案，并计算相应预调度方案的延迟程度值记为L_B；具体的，

步骤2.1将n个工件按照各自的到达时间升序排列，得到排序后的n个工件；

步骤2.2定义批的个数为b；初始化j＝1，b＝1；

步骤2.3构建第b个空批；

步骤2.4判断排序后的第j个工件的到达时间a_j是否小于第b个批的到达时间A_b，若小于，则将第j个工件放入待生产工件集合中，否则，执行步骤2.6；

步骤2.5将j+1赋值给j后，判断j>n是否成立，若成立，则执行步骤2.6；否则，执行步骤3.4；

步骤2.6判断待生产工件集合是否为空集，若为空集，则执行步骤2.7，否则，从待生产工件集合中选择权重最大的工件，并判断权重最大的工件的尺寸是否大于第b个批的剩余空间，若大于，则将b+1赋值给b后，执行步骤2.3；否则，将权重最大的工件从待生产工件集合中删除并加入第b个批中后，执行步骤2.6；

步骤2.7判断第j个工件的尺寸s_j是否大于第b个批的剩余空间，若大于，将b+1赋值给b后，返回步骤2.3；否则，将第j个工件加入第b个批中；

步骤2.8判断j+1>n是否成立，若成立，表示预分批完成，从而得到B2个批，并执行步骤2.9；否则，将j+1赋值给j后，执行步骤2.4；

步骤2.9初始化b＝1；

步骤2.7遍历K台批处理机器并找到完工时间最早的机器，记为当前批处理机器；

步骤2.8将第b个批放入当前批处理机器上生产，从而更新当前批处理机器的完工时间为第b个批的完工时间；将b+1赋值给b，若b>B2成立，则表示B2个批完成生产，得到关于延迟程度的预调度方案；否则，执行步骤2.7。

步骤1和步骤2通过使用简单的调度算法对工件进行调度来生成预调度方案，这里并不要求解是优秀的，仅是为了得到一个与最优解差距不是太大的解以便于步骤3初始化相应信息素矩阵上下限数值，并根据计算出来的信息素上限数值来更新信息素矩阵，后续仍会在每次迭代后各自使用对应全局最优解来更新对应信息素矩阵上下界数值，使本发明算法更加灵活。

步骤3、根据式(3)和式(4)获得以电力成本A为优化目标的信息素的上限和下限

式(3)中ρ为信息素蒸发率，μ为算法所设定的参数值。在本实施例中进行问题实例求解时，设置ρ＝0.08，μ＝0.05

同理获得，以延迟程度B为优化目标的信息素的上限和下限

步骤4、初始化蚁群算法的参数：

令L_max表示最大迭代次数，L表示当前迭代的次数；T表示蚂蚁总数，t表示每次迭代中第t只蚂蚁的编号；并初始化为L＝1；

以电力成本值L_A作为从初始化到第L-1次迭代的全局最小电力成本值以电力成本值L_A作为第L-1次迭代的最小电力成本值以延迟程度值L_B作为从初始化到第L-1次迭代的全局最小延迟程度值以延迟程度值L_B作为第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的目标偏好F_t^A和延迟程度B的目标偏好F_t^B，从而获得所有蚂蚁的电力成本A的目标偏好和延迟程度B的目标偏好：

F_t^B＝1-F_t^A>

传统的多目标蚁群算法在构建调度方案时，会根据针对每个目标单独设置的信息素矩阵，并将每个蚂蚁看作是相同的个体，在计算概率公式时生成一个随机数，并根据随机数确定各个信息素的偏好，从而计算工件加入批中的概率。但是这样便会产生一个问题，如果在计算工件1加入批A的概率时随机权重是偏向目标A的，但是在计算工件2加入本批时随机权重可能就会偏向目标B，容易造成两者的概率没有可比较性。而本发明算法中使用目标偏好F_t^A和F_t^B代替了随机数，将目标偏好当作蚂蚁的一个固定属性，在蚁群中设置阶梯目标偏好，使得每个蚂蚁都与众不同，既可以在计算转移概率时保证其公平性和有效性，也能保证最后生成的调度方案的多样性和差异性，增加帕累托(Pareto)非支配解的数量，得到分布更广的解集。

步骤5、初始化t＝1；

步骤6、构建第L次迭代第t只蚂蚁的调度方案；

步骤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个批的选定概率p_Ltkbj：

式(5)中，A_Ltkb表示第L次次迭代的第t只蚂蚁在第k台机器上第b个批的到达时间；

先采用轮盘赌方法从工件集合List1中选择一个工件，然后将选中的工件从集合List1中删除，并加入第L次迭代的第t只蚂蚁在第k台机器上的第b个批中，然后执行步骤6.6；

步骤6.4判断List2是否为空集，若为空集，则执行步骤6.5，否则，从工件集合List2中随机选择一个工件，然后将选中的工件从集合List2中删除并加入第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)中，P_Ltkb表示第L次迭代的第t中蚂蚁在第k台机器上的第b个批的加工时长，W_max指工件权重取值范围的最大值；

步骤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)中，Q_Ltkb表示第L次迭代的第t个蚂蚁在第k个机器中的第b个批，|Q_Ltkn|表示第L次迭代的第t个蚂蚁在第k个机器中的第b个批Q_Ltkb中的工件总数；

使用式(10)计算工件集合List中第j个工件加入第L次迭代的第t只蚂蚁在第k台机器上的第b个批的概率P_Ltkbj：

式(10)中，α、β和γ为所设定的经验值；|List|表示工件集合List中的工件总数；在本发明算法实例中，设置α＝4，β＝1，γ＝2；

利用概率P_Ltkbj通过轮盘赌方法从工件集合List中选取工件加入到第L次迭代的第t个蚂蚁在第k个机器中的第b个批Q_Ltkb中，然后将工件集合List、List1、List2和List3中的所有工件加入到工件集合TotalList中，并执行步骤6.7；

步骤6.11判断工件集合List3是否为空集，若为空集则执行步骤6.1，否则选取工件集合List3中到达时间最小的工件，记为当前工件；

若当前工件的到达时间小于批Q_Ltkb的截止时间，则将当前工件从工件集合List3中删除并加入到批Q_Ltkb中后，执行步骤6.6，否则执行步骤6.1。

步骤7、对第L次迭代第t只蚂蚁的调度方案进行优化，得到改进的调度方案；

步骤7.1初始化变量k＝1，b＝1；

步骤7.2计算调度方案中的第k台批处理机器的第b个批Q_kb的剩余空间；

步骤7.3初始化变量u＝1，v＝1；

步骤7.4判断调度方案中第u台批处理机器的第v个批Q_uv的开工时间是否小于或等于批Q_kb的开工时间，若是，执行步骤7.5，否则构建工件集合List，从批Q_uv中选出同时满足下列三个条件的工件放入工件集合List中：

条件1：工件的尺寸小于等于批Q_kb的剩余空间；

条件2：工件的到达时间小于等于批Q_kb的开工时间；

条件3：工件的加工时长小于等于批Q_kb的截止时间D_kb与批Q_kb开工时间X_kb之差；

如果List为空，则执行步骤7.5，否则，将工件的截止时间最小的工件从工件集合List中删除并放入批Q_kb中，再将工件集合List中剩余工件放回批Q_uv中后，执行步骤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；

如图3所示，步骤7.1到步骤7.8所做操作为将到达时间较早但是被分配到了开工时间较晚的工件中符合条件的工件挑出来放入先加工的批中，从而能够充分利用批的剩余空间，从而达到减少总加工时间的目的。判断先加工的批的剩余空间，从后面加工的批中查找符合条件的工件。而其中的三个条件则保证了工件可以加入先加工的批中，并且工件加入先加工的批后不会使先加工的批产生新的延迟。在所示的图3中，2号机器的第2批中的6号工件加入了1号机器的1号批中，在未造成新的延迟程度的损失的时候，工件6号提前加工，并且2号机器的第2个批在移出6号工件后的加工时长会变短或者不变，有利于减少整体的总加工时间，从而减少电力成本。

步骤7.9初始化变量k＝1，b＝2；

步骤7.10令Q_k(b-1)表示第k个机器的第b-1个批，如果批Q_kb的完工时间小于批Q_kb的截止时间，则执行步骤7.11，否则，分别计算批Q_k(b-1)与批Q_kb在交换加工顺序前与交换加工顺序后的工件延迟程度之和，若交换加工顺序前的工件延迟程度之和小于交换加工顺序后的工件延迟程度之和，则执行步骤7.11，否则，将交换批Q_k(b-1)与批Q_kb的加工顺序后，执行步骤7.11；

步骤7.11将b+1赋值给b，如果b小于第k个批处理机器上的批数量，则执行步骤7.10，否则，将k+1赋值给k，令b＝2后，判断k≤K是否成立，若成立，则执行步骤7.10，否则，执行步骤7.12；

如图4所示，机器上第1个批与第2个批之间到达时间相差不大，但是第二个批的截止时间远小于第一个批的截止时间，以至于第二个批都已经发生了延迟，在这种情况下我们不妨先计算下这两个批中所有工件的延迟程度之和，然后计算如果将两个批的加工顺序进行交换后两个批中所有工件的延迟程度之和，如果交换后的延迟程度之和小于交换前的延迟程度之和，说明交换是有收益的，则交换加工顺序，否则不交换加工顺序。

步骤7.12初始化变量k＝1；

步骤7.13将第k台批处理机器上的批总数赋值给变量b；

步骤7.14判断第k台处理机器上第b个批Q_kb的截止时间是否小于批Q_kb的完工时间，若是，则执行步骤7.19，否则，使用式(11)判断批Q_kb完工时间是否处于低电价区域，若是，则执行步骤7.17，否则，执行步骤7.15；

式(11)中，t为当前时刻，f(t)为t时刻所对应的电价；k表示周期数，k∈{0,1,2,…}；

步骤7.15判断批Q_kb的截止时间是否小于若是，则执行步骤7.19，否则，执行步骤7.16；

步骤7.16判断批Q_kb的截止时间是否大于或等于若是，则将批Q_kb的开工时间改为否则，则将批Q_kb的开工时间改为批Q_kb的截止时间D_kb与批Q_kb的处理时长P_kb之差；执行步骤7.19；

步骤7.17利用式(11)判断批Q_kb的开始加工时间是否处于低电价区域，若是，则执行步骤7.19，否则，执行步骤7.18；

步骤7.18使用式(11)判断批Q_kb的截止时间是否大于若是，则将批Q_kb的开工时间改为否则，将批Q_kb的开工时间改为批Q_kb的截止时间与批Q_kb的加工时长P_kb之差；

步骤7.19将b-1赋值给b，如果b不等于0，则执行步骤7.21，否则将k+1赋值给k后，执行步骤7.20；

步骤7.20判断k是否大于K，若是，则表示对于调度方案的优化已经完成，否则，则将第k台批处理机器中的批总数赋值给b后，执行步骤7.21；

步骤7.21判断批Q_kb的截止时间是否小于批Q_kb的完工时间，若是，则执行步骤7.19，否则，执行步骤7.22；

步骤7.22使用式(11)判断批Q_kb的开工时间X_kb是否处于高电价时段，若是，则执行步骤7.23，否则，则执行步骤7.24

步骤7.23判断批Q_kb的截止时间D_kb和批Q_k(b+1)的开工时间X_k(b+1)是否同时大于若是，将批Q_kb的开工时间延迟为min(D_kb,X_k(b+1))-P_kb，执行步骤7.19；否则，直接执行步骤7.19；

步骤7.24判断批Q_kb的完工时间是否处于低电价区域，若是，则执行步骤7.19，若否，则判断批Q_kb的截止时间D_kb和批Q_k(b+1)的开工时间X_k(b+1)是否同时大于若是，则令批Q_kb的开工时间延迟为min(D_kb,X_k(b+1))-P_kb，执行步骤7.19，否则直接执行步骤7.19。

因为本问题中的电价背景是阶梯电价，所以在解生成后适当的将后加工的批中的符合条件的工件插入到前面的批中，交换批的加工顺序，延迟批的开工时间将其放入低电价区域加工，可以大大的优化生成的工件调度方案.

如图5所示，实线为移动前的批，虚线为移动后的批，图5展示了两种根据批截止时间的不同，向后移动不同距离的较为典型的优化例子。将批向后移动时，要保证批向后移动后的批的完工时间不得大于后一个批的开工时间和当前批的截止时间中的较小值。而对于每个机器的最后一个批，则要求移动后的批的批完工时间小于等于批截止时间，并且要求移动前的加工能耗小于批向后移动后的加工能耗与因为后移而增加的机器待机功耗之和。

步骤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次迭代的解集；

所谓Pareto被支配解在最小化多目标的问题中，指的是，如果调度方案A在两个目标上的值都小于调度方案B的对应目标值，则称调度方案A支配调度方案B，或调度方案B被调度方案A支配。

步骤12、令L+1赋值给L，并判断L＞L_max是否成立，若成立，则输出第L次迭代的解集作为全局最优调度方案；否则，执行步骤5。

图2所示为本发明算法运算结果与现有求解技术中较为经典的SPEA2算法运算结果对比图，其中，x轴坐标代表电力成本，y轴代表延迟程度。图中每个符号“*”代表由本算法计算得到的一个调度方案，每个符号“Δ”代表由SPEA2算法计算得到的一个调度方案。图2中，所有符号“*”的集合构成了由蚁群算法对问题实例求解所得的解决方案集合(Pareto非支配解集合)，所有符号“Δ”的集合构成了SPEA2算法对问题实例计算所得的解决方案集合(Pareto非支配解集合)。从图2中可看出，本发明算法求解问题所得的解不仅在电力成本和延迟程度的目标值上均优于SPEA2算法所得的解，而且本发明算法所得非劣解集中的解在解空间的分布较SPEA2算法所得非劣解集中的解的分布更加均匀，总体性能更优。