东北大学学报:自然科学版  2019, Vol. 40 Issue (3): 403-408  
0

引用本文 [复制中英文]

周炳海, 顾佳颖. 考虑多资源约束的非等效并行机节能调度算法[J]. 东北大学学报:自然科学版, 2019, 40(3): 403-408.
[复制中文]
ZHOU Bing-hai, GU Jia-ying. An Energy-Saving Scheduling Algorithm for Non-identical Parallel Machines with Multi-resource Contraints[J]. Journal of Northeastern University Nature Science, 2019, 40(3): 403-408. DOI: 10.12068/j.issn.1005-3026.2019.03.019.
[复制英文]

基金项目

国家自然科学基金资助项目(71471135)

作者简介

周炳海(1965-),男,浙江浦江人,同济大学教授,博士生导师。

文章历史

收稿日期:2018-01-10
考虑多资源约束的非等效并行机节能调度算法
周炳海, 顾佳颖    
同济大学 机械与能源工程学院, 上海 201804
摘要:针对瓶颈工序光刻过程中考虑能源消耗、多类型多数量的掩膜资源、换模等约束的非等效并行机调度问题, 进行了改进型免疫克隆选择算法的调度方法研究.首先对问题域进行描述, 以最小化总加权完成时间与能源消耗量为优化目标, 建立了数学模型;在此基础上提出了一种带精英策略的多目标免疫克隆选择算法, 该算法融合了非支配排序遗传算法的排序规则, 并引入深度邻域搜索算子、种群更新算子以提高算法搜索性能及挖掘性能.最后, 对算法进行仿真实验, 结果表明该算法是有效的、可行的.
关键词调度    资源    能源消耗    免疫克隆选择算法    多目标    
An Energy-Saving Scheduling Algorithm for Non-identical Parallel Machines with Multi-resource Contraints
ZHOU Bing-hai, GU Jia-ying    
College of Mechanical Engineering, Tongji University, Shanghai 201804, China
Corresponding author: ZHOU Bing-hai, E-mail: bhzhou@tongji.edu.cn
Abstract: A modified immune clone selection algorithm is proposed for the non-identical parallel lithography machine scheduling problem of the bottleneck process with energy consumption, changeover time and resource constraints, where multiple reticles are available for each reticle type. Firstly, the scheduling problem domain is described and mathematical programming formulations are put forward with the objective function of minimizing both the total weighted completion time and the energy consumption. Based on the model, then a modified multi-objective immune clone selection algorithm with elitist strategy is developed. In addition, the depth neighbor search and the population renewal operator are combined to the algorithm to increase and balance the exploration and exploitation ability. Finally, simulation experiments and theory analysis are carried out to evaluate the as-proposed algorithm, and the results indicate that the algorithm is valid and feasible.
Key words: scheduling    resource    energy consumption    immune clone selection algorithm    multi-objective    

受到能源制约、环保要求、消费者需求日趋多样化等因素的影响, 如何在提升生产效率、减少能源消耗之中寻求平衡点成为制造业新的关注点, 近年来越来越多业界、学术界的目光转移到具有节能意识的调度目标上[1-2].

目前, 大多数有关半导体制造系统的并行机调度研究仍停留在传统调度目标, 如Zeidi等[3]研究交货期约束及顺序相关的换模约束下的并行机调度问题, 并以最小化提前/延迟时间为目标.Obeid等[4]以最小化总完成时间与最大化设备加工资格数为目标研究考虑产品族时间约束与准备时间约束的并行光刻机调度问题.

大多数的文献都未考虑辅助资源约束[3-6], 目前仅有一些学者, 如Cakici等[7]和Bitar等[8]考虑了掩膜约束的调度问题, 但是, 作者为了简化研究问题域都将掩膜数量限定为1, 却忽略了实际的多类型、多掩膜情况.为此, 本文将考虑晶圆制造光刻过程中多类型和多数量的掩膜约束、换模约束, 并将非等效光刻并行机运行过程中的能耗考虑进调度问题域中, 进行多目标调度研究, 试图在保证高生产效率的同时尽可能减少能源消耗.

1 问题描述

为有效描述研究问题域的调度问题, 作如下假设:1)有M台光刻并行机, 加工速度越快, 能源消耗越大; 2)有J个相互独立的晶圆(工件), 每个工件需要在特定层进行加工; 3)每台光刻机在每个时刻只能加工1个工件; 4)仅当辅助资源(掩模)与光刻机同时可用时, 工件才可以加工; 5)掩模具有专用性, 一种掩模只可以处理特定的加工层; 6)掩模数量有限, 每种类型掩膜数量为多个; 7)掩模可以在各个光刻机共享; 8)考虑换模时间, 并且考虑在此额外消耗的能源.

为方便形式化描述, 现定义如下.

符号及参数:

m=1, …, M为光刻机序号;

i, j=1, …, J为工件序号;

l=1, …, L为加工层序号;

t=1, …, T为调度时间;

njl为工件j所需的掩模类型的数量;

Pj为加工工件j所需的时间;

Vjm为光刻机m加工工件j的速度;

Epjm为光刻机m加工工件j的能源消耗;

Sjm为光刻机m对工件j换模所需时间;

Esjm为光刻机m对工件j进行换模时的能源消耗;

Eejm为光刻机m闲置时的能源消耗;

Rj为工件j的释放时间.

决策变量:

Xijm为二进制变量, 1表示工件j在光刻机m上紧接着加工工件i, 反之为0;

Zjt为二进制变量, 1表示在时间t时工件j加工完成, 反之为0.

根据问题描述、模型假设以及符号定义, 对考虑辅助资源约束、能源消耗的非等效光刻并行机问题建模如下.

目标函数:

(1)
(2)
(3)

约束:

(4)
(5)
(6)
(7)
(8)
(9)
(10)
(11)
(12)
(13)
(14)

其中:式(1)~式(3)为该调度模型的目标函数; 约束(4), (5)表明工件被分配到M台光刻机中的1台; 约束(6), (7)表明工件分配及同1台光刻机上的加工顺序; 约束(8)表示各工件都会在一个时间点完成加工; 约束(9), (10)是关于完成时间的约束; 约束(11)表示虚拟工件必须在各光刻机的第一个位置; 约束(12)表示资源约束; 约束(13), (14)规定0, 1变量.

2 改进型多目标免疫克隆算法

由于本文的调度问题是NP-hard问题, 采用解析法无法求解中、大规模问题[7], 目前绝大多数解决此类调度问题是基于人工智能的启发式算法来实现.而免疫克隆优化算法作为一种新型智能群体算法, 得到了广泛的应用[9].为此, 本文将构建一种基于精英保留策略的改进型多目标免疫克隆选择算法(MMICA)[10].算法的具体步骤如下, 其种群进化如图 1所示.

图 1 MMICA种群进化 Fig.1 Population evolution of the MMICA

步骤1  编码.根据本文模型的特点及性质, 采用单层实数编码表示各解, 各抗体表示对工件合理分配加工光刻机与辅助资源以及确定工件加工顺序的调度方案.具体编码形式为{A1, A2, …, Aj}, 其中j表示工件数, 如图 2所示, 各变量整数部分表示工件分配的光刻机号, 小数部分第一位表示该工件对应的掩膜类型下的掩膜号, 小数剩余部分映射工件分配顺序, 数字越小代表工件越早加工.

图 2 编码示例 Fig.2 Representation of antibody

实例:抗体{1.237, 2.114, 1.276, 3.193, 3.224, 3.134}表示工件1与5在光刻机2上加工, 使用的掩膜序号分别为特定类型下的第1, 2号掩膜, 加工顺序为工件5、工件1.

步骤2  初始化.设置初始参数:最大迭代数(Gmax), 种群数(Npop), 交叉概率(θc), 变异概率(θm), 模拟二元交叉分布指数(μ)等.

初始化种群:随机生成由Npop个抗体所组成的种群Piter, 并根据已知的光刻机数M及各掩膜类型njl限制抗体各变量的取值范围.

步骤3  亲和度评价.亲和度作为评价抗体性能的指标, 由非支配等级与拥挤距离共同决定, 各抗体按亲和度从大到小的顺序排列生成种群Piter'.非支配等级体现了抗体的性能, 等级值越小, 亲和度越大, 代表抗体的性能越好.对于同一等级层上的抗体, 其亲和度由拥挤距离评价.

其中, fnmaxfnmin分别表示第n个目标函数可获得的最大及最小值, Dn(x)取值如下.

fn(x)=min{fn(x)|xΩ}∪max{fn(x)|xΩ}时, Dn(x)=inf; 其他情况时, Dn(x)={fn(xB)-fn(xA)|xA, xBΩx, fn(xA)<fn(x)<fn(xB)}, 其中Ω表示可行解集合, Ωx表示x所属非支配等级中解的集合.

所以对于xA, xBΩ, 如果D(xA)>D(xB), 那么xA的亲和度大于xB.

步骤4  克隆竞争扩增.根据亲和度大小将抗体从小到大排列, 选择支配等级为1的优势抗体存入记忆库, 并对其进行克隆, 选择的优势抗体数目记作Nc.在当前排序中排在第s位的优势抗体克隆得到的克隆抗体数目记作Nclone,计算公式为Nclone=Nc-s+1.

步骤5  抗体合并及变异.将克隆前的抗体与克隆的抗体合并得到抗体群Ziter, 对其采用模拟二元交叉和多项式变异策略, 对所有抗体进行交叉变异操作得到抗体群Qiter.

模拟二进制交叉算子:

其中, .且ukU[0, 1], μ为交叉分布指数.

多项式变异算子:

其中,

为变异分布指数.

步骤6  种群重组及记忆库更新.将未进行变异操作的原抗体与已变异的抗体合并重组得到抗体群Eiter', 同时将抗体群Miter暂存于人工免疫记忆库, 并在每一次迭代过程中替换掉亲和度低的抗体, 将亲和度较大的抗体加入记忆库中.

步骤7  算法终止判断.若迭代次数达到规定上限Gmax, 则输出记忆库存储的精英解集; 否则, 进入步骤8.

步骤8  深度邻域搜索.引入两种邻域搜索策略:1)交换顺序:随机地交换工件的加工顺序; 2)更换掩膜:随机地选择一个具有多个同类型掩膜的工件改变其使用的掩摸.若所得抗体违背约束(12), 则在目标函数上添加惩罚项.

步骤9  抗体更新.采用轮盘赌选择策略从当前群体中选择Npop个个体进行之后的操作.对抗体进行小比例的初始化, 用新产生的nre个体取代亲和度低的nre个抗体, 以保证抗体的多样性.其中, Nre为重新初始化参数.

选择概率由θp, θpq共同决定,根据θp确定选择的前沿,根据θpq确定前沿中选择的抗体.其中,p表示前沿序号,q表示前沿p内的抗体序号,此外,Ip表示前沿p内的抗体数,NF表示前沿数目,故∀p=1, …, Nf, ∀q=1, …, Ip.那么,选择概率Probt的计算公式为, ∀i=1, …, NF,其中Rankp是表示前沿p的非支配等级. , 其中Rankp, q表示抗体q在前沿p内排序.

3 仿真实验与分析

所有算法都基于MATLAB(2014a)的环境编程下实现, 在主频为2.10 GHz, 内存为4 GB、Intel(R)Core(TM)i5-4200M CPU的PC机上进行仿真实验, 实验结果和分析如下.

3.1 评价指标

将Pareto解的个数(NS)、世代距离(GD)、解间距(SP)、运行时间(CPU)以及求得的Pareto解作为评价算法性能的指标.其中, 世代距离及解间距的定义如下.

世代距离:世代距离越小, 表明算法收敛性越好.

(15)

式中: ; ψ表示算法求得的Pareto解集; P*表示已知Pareto解.

解间距:解间距越小, 表明算法多样性越好.

(16)

式中: , ap, aqψ; d表示所有dp的平均值.

3.2 参数设置

采用田口实验确定各参数值以保证算法的高效性.根据实验得到当Npop=150, Gmax=300, θc=0.5, θm=0.5, μ=10, δ=20, nre=40时, 算法以较高的质量对问题进行求解.

问题的参数参考文献[2]设置, 工件数为4水平, 分别是20, 30, 40, 50, 光刻机数为2水平, 分别为[J/10], [J/10]×2, 掩膜对应的层数为2水平, 分别为[J/5]+1, [J/10]+1.工件j的加工时间PjU[45, 75], 有50%的工件jU[1, 360]内释放, 工件j的权重WjU[1, 20], 工件j在光刻机m换模时间SjU[5, 10], 各台设备的加工速度Vjm在{1, 1.5, 2}中随机选择, 各产品族掩膜版的数量njl为1或2, 设备的加工能源消耗Epjm为3Vm2, 设备的闲置能源消耗Eejm为0.4, 设备的换模能源消耗Esjm为1.因此, 一个n=20, m=2, f=3的问题记为n20m2f3, 并将n≤20, 20<n≤40, n>40的问题分别记为小、中、大规模问题.

3.3 实验分析

将本文提出的改进的多目标免疫克隆算法(MMICA)与目前在解决多目标问题上具有较优性能的经典算法带精英策略的非支配选择遗传算法(NSGA-Ⅱ)、多目标差分进化算法(MODE)进行对比, 测试算法的性能.

由于算法单次运行结果具有一定的随机性, 所以上述3种算法分别对各算例进行20次的独立实验, 实验结果见表 1.

表 1 不同规模问题的实验结果 Table 1 Experimental results of different instances

表 1可知, 当问题规模较小时, MMICA与NSGA-Ⅱ解的个数、世代距离、解间距性能都十分接近, 略优于MODE的相应性能.当问题规模逐渐变大时, MMICA与NSGA-Ⅱ、MODE在解的个数、世代距离、解间距的优势逐渐扩大.

为了更直观观察实验结果, 图 3利用统计盒图作为统计分析工具得出各算法针对不同算例运行多次得到的算法运行时间的指标特性.由图 3可知, 求解时间上, 虽然NSGA-Ⅱ所消耗的时间最短, MMICA算法所用时间相对较长, 但考虑到其他性能上MMICA的优异表现, MMICA的运行时间仍在可接受范围内, 所以在解决此多目标问题上仍然不失为一种高效的算法.

图 3 16个算例的CPU统计盒图 Fig.3 Box plots of 16 problem instances in CPU metric

图 4n50m5l11问题的Pareto解情况, 由图 4可知, 当规模较小时, MMICA、NSGA-Ⅱ求得的解集各有支配, 相互之间互相重合, 并且都支配着MODE求得的解集.而随着规模扩大, MMICA的Pareto解支配NSGA-Ⅱ与MODE的Pareto解, 且分布更为均匀, 证明了MMICA的有效性.其性能优越性归功于它保存了优势抗体并扩大了优势抗体对其他解的影响, 同时种群更新算子与邻域搜索算子扩大了算法的搜索范围, 加强了算法深入搜索的能力.

图 4 算例n50m5l11的Pareto解集 Fig.4 Pareto solution of the 'n50m5l11' problem
4 结论

本文研究了考虑多种资源约束的非等效并行机节能调度问题, 融合NSGA-Ⅱ的排序规则, 提出了改进的多目标非支配免疫克隆选择算法.实验分析可知, MMICA比NSGA-Ⅱ与MODE解的质量更优, Pareto前沿分布更均匀, 验证了此算法的有效性同时丰富了解决此类调度问题的理论方法.调度者可根据不同需求从求得的Pareto前沿中选择不同的调度方案, 在生产效率与能源消耗上寻找到合适的平衡点.未来研究可考虑一些其他影响能源消耗量的因素, 如资源运输过程中的能源消耗.

参考文献
[1]
Gahm C, Decz F, Dirr M, et al. Energy-efficient scheduling in manufacturing companies:a review and research framework[J]. European Journal of Operational Research, 2016, 248(3): 744–757. DOI:10.1016/j.ejor.2015.07.017
[2]
Zhang R, Chiong R. Solving the energy-efficient job shop scheduling problem:a multi-objective genetic algorithm with enhanced local search for minimizing the total weighted tardiness and total energy consumption[J]. Journal of Cleaner Production, 2016, 112: 3361–3375. DOI:10.1016/j.jclepro.2015.09.097
[3]
Zeidi J R, Mohmmadhosseini S. Scheduling unrelated parallel machines with sequence-dependent setup times[J]. The International Journal of Advanced Manufacturing Technology, 2015, 81(9/10/11/12): 1487–1496.
[4]
Obeid A, Dauzere-peres S, Yugma C. Scheduling job families on non-identical parallel machines with time constraints[J]. Annals of Operations Research, 2014, 213(1): 221–234. DOI:10.1007/s10479-012-1107-4
[5]
Jia J, Mason S J. Semiconductor manufacturing scheduling of jobs containing multiple orders on identical parallel machines[J]. International Journal of Production Research, 2009, 47(10): 2565–2585. DOI:10.1080/00207540701725042
[6]
Zhou B H, Hu L M, Zhong Z Y. A hybrid differential evolution algorithm with estimation of distribution algorithm for reentrant hybrid flow shop scheduling problem[J]. Neural Computing and Applications, 2018, 30(1): 193–209. DOI:10.1007/s00521-016-2692-y
[7]
Cakici E, Mason S J. Parallel machine scheduling subject to auxiliary resource constraints[J]. Production Planning and Control, 2007, 18(3): 217–225. DOI:10.1080/09537280601035836
[8]
Bitar A, Dauzere-peres S, Yugma C, et al. A memetic algorithm to solve an unrelated parallel scheduling problem with auxiliary resources in semiconductor manufacturing[J]. Journal of Scheduling, 2016, 19(4): 367–376. DOI:10.1007/s10951-014-0397-6
[9]
Hu Z H. A multiobjective immune algorithm based on a multiple-affinity model[J]. European Journal of Operational Research, 2010, 202(1): 60–72.
[10]
Deb K, Prata A, Agarwal S, et al. A fast and elitist multi-objective genetic algorithm:NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182–197. DOI:10.1109/4235.996017