周炳海, 顾佳颖
同济大学 机械与能源工程学院, 上海 201804
收稿日期：2018-01-10
基金项目：国家自然科学基金资助项目(71471135)。
作者简介：周炳海(1965-)，男，浙江浦江人，同济大学教授，博士生导师。

摘要：针对瓶颈工序光刻过程中考虑能源消耗、多类型多数量的掩膜资源、换模等约束的非等效并行机调度问题, 进行了改进型免疫克隆选择算法的调度方法研究.首先对问题域进行描述, 以最小化总加权完成时间与能源消耗量为优化目标, 建立了数学模型；在此基础上提出了一种带精英策略的多目标免疫克隆选择算法, 该算法融合了非支配排序遗传算法的排序规则, 并引入深度邻域搜索算子、种群更新算子以提高算法搜索性能及挖掘性能.最后, 对算法进行仿真实验, 结果表明该算法是有效的、可行的.
关键词：调度资源能源消耗免疫克隆选择算法多目标
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: schedulingresourceenergy consumptionimmune clone selection algorithmmulti-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为调度时间;
n_jl为工件j所需的掩模类型的数量;
P_j为加工工件j所需的时间;
V_jm为光刻机m加工工件j的速度;
E_pjm为光刻机m加工工件j的能源消耗;
S_jm为光刻机m对工件j换模所需时间;
E_sjm为光刻机m对工件j进行换模时的能源消耗;
E_ejm为光刻机m闲置时的能源消耗;
R_j为工件j的释放时间.
决策变量:
X_ijm为二进制变量, 1表示工件j在光刻机m上紧接着加工工件i, 反之为0;
Z_jt为二进制变量, 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(Fig. 1)

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

步骤1??编码.根据本文模型的特点及性质, 采用单层实数编码表示各解, 各抗体表示对工件合理分配加工光刻机与辅助资源以及确定工件加工顺序的调度方案.具体编码形式为{A₁, A₂, …, A_j}, 其中j表示工件数, 如图 2所示, 各变量整数部分表示工件分配的光刻机号, 小数部分第一位表示该工件对应的掩膜类型下的掩膜号, 小数剩余部分映射工件分配顺序, 数字越小代表工件越早加工.
图 2(Fig. 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??初始化.设置初始参数:最大迭代数(G_max), 种群数(N_pop), 交叉概率(θ_c), 变异概率(θ_m), 模拟二元交叉分布指数(μ)等.
初始化种群:随机生成由N_pop个抗体所组成的种群P_iter, 并根据已知的光刻机数M及各掩膜类型n_jl限制抗体各变量的取值范围.
步骤3??亲和度评价.亲和度作为评价抗体性能的指标, 由非支配等级与拥挤距离共同决定, 各抗体按亲和度从大到小的顺序排列生成种群P_iter'.非支配等级体现了抗体的性能, 等级值越小, 亲和度越大, 代表抗体的性能越好.对于同一等级层上的抗体, 其亲和度由拥挤距离评价.
其中, f_n^max与f_n^min分别表示第n个目标函数可获得的最大及最小值, D_n(x)取值如下.
f_n(x)=min{f_n(x)|x∈Ω}∪max{f_n(x)|x∈Ω}时, D_n(x)=inf; 其他情况时, D_n(x)={f_n(x_B)-f_n(x_A)|x_A, x_B∈Ω_x, f_n(x_A)＜f_n(x)＜f_n(x_B)}, 其中Ω表示可行解集合, Ω_x表示x所属非支配等级中解的集合.
所以对于x_A, x_B∈Ω, 如果D(x_A)＞D(x_B), 那么x_A的亲和度大于x_B.
步骤4??克隆竞争扩增.根据亲和度大小将抗体从小到大排列, 选择支配等级为1的优势抗体存入记忆库, 并对其进行克隆, 选择的优势抗体数目记作N_c.在当前排序中排在第s位的优势抗体克隆得到的克隆抗体数目记作N_clone，计算公式为N_clone=N_c-s+1.
步骤5??抗体合并及变异.将克隆前的抗体与克隆的抗体合并得到抗体群Z_iter, 对其采用模拟二元交叉和多项式变异策略, 对所有抗体进行交叉变异操作得到抗体群Q_iter.
模拟二进制交叉算子:
其中, .且u_k∈U[0, 1], μ为交叉分布指数.
多项式变异算子:
其中，
为变异分布指数.
步骤6??种群重组及记忆库更新.将未进行变异操作的原抗体与已变异的抗体合并重组得到抗体群E_iter', 同时将抗体群M_iter暂存于人工免疫记忆库, 并在每一次迭代过程中替换掉亲和度低的抗体, 将亲和度较大的抗体加入记忆库中.
步骤7??算法终止判断.若迭代次数达到规定上限G_max, 则输出记忆库存储的精英解集; 否则, 进入步骤8.
步骤8??深度邻域搜索.引入两种邻域搜索策略:1)交换顺序:随机地交换工件的加工顺序; 2)更换掩膜:随机地选择一个具有多个同类型掩膜的工件改变其使用的掩摸.若所得抗体违背约束(12), 则在目标函数上添加惩罚项.
步骤9??抗体更新.采用轮盘赌选择策略从当前群体中选择N_pop个个体进行之后的操作.对抗体进行小比例的初始化, 用新产生的n_re个体取代亲和度低的n_re个抗体, 以保证抗体的多样性.其中, ，N_re为重新初始化参数.
选择概率由θ_p, θ_pq共同决定，根据θ_p确定选择的前沿，根据θ_pq确定前沿中选择的抗体.其中，p表示前沿序号，q表示前沿p内的抗体序号，此外，I_p表示前沿p内的抗体数，N_F表示前沿数目，故?p=1, …, N_f, ?q=1, …, I_p.那么，选择概率Prob_t的计算公式为, ?i=1, …, N_F，其中Rank_p是表示前沿p的非支配等级. , 其中Rank_{p, 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)

式中: , a_p, a_q∈ψ; d表示所有d_p的平均值.
3.2 参数设置采用田口实验确定各参数值以保证算法的高效性.根据实验得到当N_pop=150, G_max=300, θ_c=0.5, θ_m=0.5, μ=10, δ=20, n_re=40时, 算法以较高的质量对问题进行求解.
问题的参数参考文献[2]设置, 工件数为4水平, 分别是20, 30, 40, 50, 光刻机数为2水平, 分别为[J/10], [J/10]×2, 掩膜对应的层数为2水平, 分别为[J/5]+1, [J/10]+1.工件j的加工时间P_j为U[45, 75], 有50%的工件j在U[1, 360]内释放, 工件j的权重W_j为U[1, 20], 工件j在光刻机m换模时间S_j为U[5, 10], 各台设备的加工速度V_jm在{1, 1.5, 2}中随机选择, 各产品族掩膜版的数量n_jl为1或2, 设备的加工能源消耗E_pjm为3V_m², 设备的闲置能源消耗E_ejm为0.4, 设备的换模能源消耗E_sjm为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)

表 1 不同规模问题的实验结果Table 1 Experimental results of different instances 算例 MMICA NSGA-Ⅱ MODE NS GD SP CPU NS GD SP CPU NS GD SP CPU 小规模 n20m2l3 41 280.15 1 376.94 88.1 40 278.26 1 575.57 67.7 33 339.74 1 922.56 85.6 n20m4l3 43 186.03 1 135.51 86.1 39 192.37 1 391.95 68.4 31 343.92 1 702.10 88.5 n20m2l5 41 233.78 1 276.56 86.6 37 237.49 1 393.94 62.9 29 368.54 2 040.45 87.4 n20m4l5 46 236.43 1 155.15 88.9 44 254.64 1 410.17 66.2 27 365.60 2 133.87 84.9 中规模 n30m3l4 54 169.21 1 727.29 93.4 46 284.06 2 249.19 87.1 35 288.84 2 718.85 93.4 n30m6l4 46 208.79 1 768.89 98.0 42 247.07 2 453.93 90.7 38 318.37 2 861.89 95.2 n30m3l7 55 253.23 2 085.23 97.0 44 296.95 2 345.07 90.5 27 347.18 2 924.20 98.8 n30m6l7 42 171.34 1 277.03 105.4 38 279.16 1 715.32 102.8 29 234.93 2 441.95 103.2 n40m4l5 56 297.11 1 954.17 106.6 49 252.46 2 353.87 104.2 31 232.51 2 819.39 104.7 n40m8l5 40 304.25 1 360.98 116.6 36 371.62 2 280.60 112.0 30 395.66 2 672.59 117.0 n40m4l9 61 220.87 1 831.50 106.3 44 282.52 2 310.4 103.5 37 240.64 2 841.01 108.5 n40m8l9 39 172.92 1 189.39 121.6 34 296.37 2 334.39 118.3 35 220.87 2 511.72 131.3 大规模 n50m5l6 47 256.05 1 521.22 119.0 41 324.29 2 829.93 117.2 32 326.12 3 289.15 123.3 n50m10l6 46 320.85 2 135.95 119.2 43 363.47 2 746.46 116.9 34 348.84 3 120.51 122.7 n50m5l11 53 332.45 2 313.56 124.3 45 334.78 2 967.59 120.9 39 402.82 3 534.58 131.9 n50m10l11 49 312.63 2 213.48 127.1 42 302.38 3 172.83 124.6 35 398.64 3 759.90 128.4 均值 47 247.26 1645.18 105.3 42 287.37 2 220.70 97.12 33 323.33 2 704.05 106.6

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

由表 1可知, 当问题规模较小时, MMICA与NSGA-Ⅱ解的个数、世代距离、解间距性能都十分接近, 略优于MODE的相应性能.当问题规模逐渐变大时, MMICA与NSGA-Ⅱ、MODE在解的个数、世代距离、解间距的优势逐渐扩大.
为了更直观观察实验结果, 图 3利用统计盒图作为统计分析工具得出各算法针对不同算例运行多次得到的算法运行时间的指标特性.由图 3可知, 求解时间上, 虽然NSGA-Ⅱ所消耗的时间最短, MMICA算法所用时间相对较长, 但考虑到其他性能上MMICA的优异表现, MMICA的运行时间仍在可接受范围内, 所以在解决此多目标问题上仍然不失为一种高效的算法.
图 3(Fig. 3)

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

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

图 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