考虑节能的改进多目标樽海鞘群算法TFT-LCD面板阵列制程调度问题

姚远远 叶春明

上海理工大学管理学院，上海，200093

0 引言

薄膜晶体管液晶显示器(thin-film transistor-liquid crystal display，TFT-LCD)的制造过程主要包括三个阶段：TFT阵列/彩色滤光制程、液晶成盒、模块组装制程[1]。为了减少在制品数量、缩短生产周期，企业通常在阵列制程的每个工位放置多台并行机器。TFT-LCD面板阵列制程的生产过程可归结为可重入混合流水车间(reentrant hybrid flow shop，RHFS)问题，即所有工件在各工位之间具有相同的加工路径，并按照相同的加工顺序重复多次，且至少有一个工位有多台机器。RHFS调度问题是经典的混合流水车间调度与可重入调度的合成体，已被证明是NP难题[2]，不能用传统的数学模型方法求解，因此，开发针对该问题的高效智能优化算法研究是车间调度领域的热点，具有重要的理论意义和实用价值。

CHOI等[3]将TFT-LCD制造简化为两阶段的RHFS调度问题并构建数学模型，以满足最大允许交货期的条件下使最大完工时间最短为调度目标，提出一种分枝定界算法和三种改进的启发式算法(Johnson、CDS和NEH)进行求解。CHOI等[4]研究了需要同时满足系统产出最大，平均运行时间、平均延误时间、总误工工件数最小的多个优化目标的实时动态RHFS调度问题，采用一种基于决策树的实时调度机制来选择合适的调度规则，并将其成功用于实际的TFT-LCD面板生产线。DUGARDIN等[5]提出了一种基于Lorenz支配的多目标遗传算法，求解了以最大化瓶颈机器利用率、最小化最大完工时间为目标的RHFS问题。为求解优化目标是最小化最大完工时间和总拖期时间的RHFS调度问题，CHO等[6]提出了Pareto遗传算法，YING等[7]提出了迭代Pareto贪婪算法，SHEN等[8-9]提出了改进教与学优化算法、基于Pareto的离散和声搜索算法。CHO等[10]针对双目标RHFS调度问题，提出一种双层生产计划与调度方法，并将其用于求解随机生成的问题和真实TFT-LCD生产案例。

目前，针对RHFS调度问题的研究方法主要是精确方法、启发式算法和现代元启发式算法。精确算法在理论上能保证获得最优解，但对问题的建模要求很高，受时间复杂度和空间复杂度的限制，仅适用于小规模问题，且求解效率低。启发式算法基于调度规则构造解，能够保证解的可行性与产生过程的快速性，但求解质量难以保证。元启发式算法能够在合理的计算时间内高效获得满意解，广泛用于各种车间调度问题的求解。尽管各种不同的智能优化算法已经被用于求解RHFS调度问题，但是“没有免费午餐定理”[11]指出不存在一种算法能够解决所有的优化问题。因此，本文采用一种新型的智能优化算法对RHFS调度问题进行求解。

高效的优化调度方法能够有效提高经济效益，实现节能、减排、降耗、降成本，减少对环境的影响，取得经济指标和绿色指标的协同优化[12]。LU等[13]考虑机器调整安装时间和运输时间，构建以最大完工时间和总耗能为目标的数学模型，采用一种混合多目标回溯搜索算法求解考虑节能的置换流水车间调度问题。LEI等[14]提出一种混合蛙跳算法，解决考虑能耗指标、以最小化工作负荷均衡和总耗能为优化目标的柔性作业车间调度问题。DENG等[15]提出一种竞争文化基因算法来求解以最小化最大完工时间和总碳排放量为优化目标的分布式置换流水车间低碳调度问题，并对该问题的性质进行了分析。

TFT-LCD制造企业作为能耗大户，存在较大的节能空间，节能减排工作非常迫切[16]，因此，笔者采用多目标樽海鞘群算法(multi-objective salp swarm algorithm，MSSA)[17]对考虑节能的TFT-LCD面板阵列制程调度问题进行求解，提出一种改进多目标樽海鞘群算法(improved MSSA，IMSSA)，并通过与基本多目标樽海鞘群算法、多目标粒子群优化(MOPSO)算法以及快速非支配排序遗传算法(NSGA-Ⅱ)的数值实验对比，验证了IMSSA解决该问题的有效性。

1 考虑节能的TFT-LCD面板阵列制程调度问题

1.1 问题描述

TFT-LCD面板的阵列制程可抽象为RHFS调度问题，具体描述如下：有n个工件需要在s个串行工位上进行加工；工位i有mi(mi≥1)台相同的并行机器；每道工序可以在每个工位的任何一台机器上以相同的加工时间完成，由于具有可重入特点，所以同一工件可能多次访问某个工位。实际生产过程中，TFT-LCD制造企业既要考虑工件工期、拖期、加工成本等多种经济指标，又要考虑能耗、碳排放等绿色指标。某些经济指标与绿色指标往往相互冲突，因此，本文考虑节能的TFT-LCD面板阵列制程调度问题属于多目标优化问题。本文选取3个优化目标：最大完工时间、总拖期时间和总耗能，其中，最大完工时间为所有工件全部工序的最终完成时间；交付期是企业对客户订单的承诺交付时间；降低总耗能有助于企业节能、减排、降成本，减小对环境的影响，本文只考虑机器的加工耗能和空转耗能。

模型包含的基本约束条件和假设有：①所有工件和机器在零时刻均准备就绪；②全部机器在零时刻启动并在所有工件完成加工后关闭，不考虑停开机耗能；③在任意时刻，每台机器最多加工1个工件，每个工件也最多只能被1台机器加工；④所有工件之间互不影响，工件之间的加工顺序没有先后约束，每个工件的所有工序有先后约束；⑤每个工件的可重入次数、各道工序的加工时间、每个工件的交付期，以及每个工位上机器的单位时间加工耗能和空转耗能是已知且固定的；⑥任意两个连续工位之间的缓冲区容量无限；⑦不允许抢占，工件一旦开始加工，则不能被中断；⑧不考虑机器故障和机器调整安装时间。

1.2 模型建立

本文在文献[6,8]的研究基础之上，给出如下的多目标混合整数规划模型。

目标函数：

minCmax=maxCj

(1)

(2)

minTec=Pec+Sec

(3)

式中，Cmax为最大完工时间目标；Cj为工件j的完工时间，j=1，2，…，n；n为工件总数；Ttd为总拖期时间；dj为工件j的交付期；Tec为总耗能目标，本文所有耗能单位都是kgce，表示千克标准煤当量；Pec为加工总耗能；Sec为空转总耗能。

约束条件：

(4)

(5)

M(2-rijkl-rij′k′l)+M(1-Zjkj′k′)+(Sj′k′-Sjk)≥pjk

(6)

∀i,j

M(2-rijkl-rij′k′l)+MZjkj′k′+(Sjk-Sj′k′)≥pj′k′

(7)

∀i,j

M(2-rijkl-rijk′l)+(Sjk′-Sjk)≥pjk

(8)

∀i,k

Sjk≥0 ∀j,k

(9)

(10)

Cj≤Cmax∀j

(11)

(12)

(13)

∀i,j,k,l

式中，i为工位序号，i=1，2，…，s；s为工位总数；l为工位i中的机器序号，l=1，2，…，mi；k为工件j的工序序号，k=1，2，…，Nj；Nj为工件j的工序总数；Ojk表示工件j的第k道工序；pjk为工序Ojk的加工时间；Sjk为工序Ojk的加工开始时间；Ui为在工位i中加工的所有工序的集合，由于允许可重入，因此同一工件可能在Ui中出现多次；M为一个足够大的正数；Pil为工位i中第l台机器单位时间的加工耗能；Sil为工位i中第l台机器单位时间的空转耗能。

式(1)～式(3)分别表示需要优化的最小化最大完工时间、总拖期时间和总耗能；式(4)确保工序Ojk+1的加工开始时间不早于工序Ojk的加工完成时间；式(5)保证每道工序只能在相应工位中的一台机器上加工；式(6)～式(8)确保每台机器在同一时刻最多加工一道工序；式(9)规定工序Ojk的加工开始时间为非负数；式(10)、式(11)定义了最大完工时间目标；式(12)、式(13)定义了加工总耗能和空转总耗能。

2 改进多目标樽海鞘群算法

MIRJALILI等[17]提出了樽海鞘群算法(salp swarm algorithm，SSA)，并给出了该算法的单目标和多目标的求解方法。SSA将樽海鞘链分成领导者(前半部分)和追随者(后半部分)，将搜索空间中的食物源F作为群体的搜索目标。本文对多目标SSA(multi-objective SSA，MSSA)进行改进，以解决离散的TFT-LCD面板阵列制程调度问题。

2.1 编码和解码机制

由于SSA的个体位置为连续值矢量，无法实现工件排序的更新，因此采用基于升序排列的随机键编码规则，构造从个体位置到工件排序的恰当映射，然后按照文献[6-7]的PS方法进行解码，从而计算出个体位置对应调度方案的目标值。这种转化无需修改算法的进化操作，能够保证调度方案的可行性。

本文选取TFT-LCD面板阵列制程的一个小规模测试问题实例进行解释说明。该测试问题中，3个工件(共14道工序)需要经过阵列制程的2个工位(共3台机器)的加工。第一个工位有1台机器，该工位机器单位时间的加工耗能即能源消耗量的换算指标(千克标准煤当量，kgce)为8 kgce/min，空转耗能为2 kgce/min；第二个工位有2台同速并行机器，每台机器的单位时间加工耗能为7 kgce/min，空转耗能为1 kgce/min。工件1～3的交付期分别是7.5 min、11.5 min和16.0 min。每个工件的各道工序在对应工位上的加工时间如表1所示，如果某次可重入该工件不在此工位上加工，则加工时间用“-”表示。

表1 一个小规模的TFT-LCD阵列制程实例

Tab.1Asmall-sizedTFT-LCDarrayprocesscasemin

加工时间首次加工路径第1次可重入第2次可重入工位1工位2工位1工位2工位1工位2工件12132--工件2222222工件32322--

樽海鞘的个体位置采用基于随机键的编码，个体长度等于工件总数，各元素在0～1内任意取值，如图1所示，这种编码方式能够有效降低算法求解难度，提高求解效率。假设某个樽海鞘的个体位置向量为(0.814 7, 0.127 0, 0.632 4)，通过对各位置元素进行升序排列得到对应的工件排序(2, 3, 1)，即工件加工顺序为2-3-1。接着采用PS方法将该工件排序解码成一个可行调度方案，图2为得到的甘特图。通过解码过程为每道工序在每个工位选取1台合适的机器进行加工，确定每台机器的加工顺序、工序开始时间，求得目标函数值。图2中，首先将工件2的所有工序安排在能最早加工完成的机器上；接着对工件3进行排序，将工件3的各道工序安排在能最早加工完成的机器上，在所分配的机器上，如果工件3的某道工序的加工完成时间不超过已安排工件工序的最早加工开始时间，则将工件3的这道工序安排在已排序工件工序的位置之前，否则将其安排在已排序工件工序的后面，例如工件3的第1道工序(301)安排在工序203之前，工序303安排在工序205的后面；然后依此类推，将工件1的所有工序安排在各台机器上。该调度方案求得的目标函数值为Cmax=17 min，Ttd=10 min，Tec=242 kgce。

图1 樽海鞘个体的表示Fig.1 Representation of salp individual

时间t/min图2 小规模TFT-LCD阵列制程实例的甘特图Fig.2 Gantt chart of a small-sized TFT-LCD array process case

2.2 领导者和追随者的个体位置更新方式

领导者个体的位置更新只与食物源位置相关，由于SSA的领导者个体位置更新方式是为连续函数优化问题设计的，无法直接用于离散问题求解，因此对领导者个体的位置更新方式进行改进：

(14)

c=2exp(-(4t/tmax)2)

(15)

i=1，2，…，N/2j=1，2，…，D

其中，xi,j为第i个樽海鞘个体位置的第j维变量值；Fj为食物源位置的第j维变量值；r是0～1之间的随机数，r<0.5时，xi,j向Fj的方向靠近，否则远离Fj；相关系数c是SSA中最重要的参数，用于平衡全局探索和局部开发，随着迭代过程从2递减到0，大约第60次迭代时，c接近为0。t为当前迭代次数，tmax为种群的最大迭代次数。假设种群中有N个樽海鞘个体，每个个体有D(工件个数)维变量。L为Lévy飞行步长[18]，可有效防止算法早熟收敛，计算方法如下：

L=u/|v|1/β

(16)

σv=1

式中，β为1～2之间的一个参数。

樽海鞘链的后半部分个体为追随者，追随者的个体位置更新只与它前面的樽海鞘个体位置相关：

xi,j=(xi,j+xi-1,j)/2

i=N/2+1,N/2+2,…,N

2.3 外部档案个体变邻域搜索操作

在MSSA中，引入一个外部档案Archive存储当前种群获得的所有最优非支配解集，为了找到更好的Pareto最优前沿，本文对Archive中的每个个体执行变邻域搜索操作，变邻域搜索的最大迭代次数用ls表示。具体操作方法是：对Archive中的每个个体的每维元素以1/D的概率进行变异。变异操作公式如下：

Al′,j=Al,j+εRK

其中，Al,j为Archive中第l个非支配个体位置的第j维变量；Al′,j为变异操作后的Al,j；ε是一个很小的正数，经过测试，ε=0.01算法的寻优效果较好；R是一个服从标准正态分布的随机数；r是0～1之间的随机数，r<1/D时，K为1，否则为0。

如果变异操作后的新个体Al′支配Al，则保留新个体Al′并将其存入Archive中，舍弃原个体Al；否则不保留Al′。每个个体执行ls次变邻域搜索操作。

2.4 IMSSA算法流程

本文在MSSA基础上，引入针对可重入混合流水车间调度问题的编码和解码机制，改进了领导者个体的位置更新方式，并对Archive中的非支配个体进行变邻域搜索操作，设计出一种改进多目标樽海鞘群算法(improved multi-objective salp swarm algorithm，IMSSA)，如图3所示。

图3 IMSSA算法图Fig.3 Diagram of IMSSA

3 数值实验

3.1 实验设置

为验证IMSSA求解TFT-LCD面板阵列制程调度问题的有效性，将其与MSSA、多目标粒子群优化(MOPSO)算法[19]和快速非支配排序遗传算法(NSGA-Ⅱ)[20]进行对比。实验仿真环境如下：操作系统为Windows 7，处理器为Intel i5-4210M @2.60GHz，内存4G，采用MATLAB R2015b实现算法编程。

3.2 测试问题

根据本文模型所提出的假设，所有工件完成加工所需的加工总耗能是固定值，主要由所有机器的空转总耗能的变化决定，因此为了简化计算，对所有机器的空转总耗能进行研究，分析不同调度方案对所有机器的空转总耗能的影响。本文在文献[6]设计的RHFS调度问题的测试算例基础上，增加机器的单位时间空转耗能，以验证IMSSA解决考虑节能的TFT-LCD面板阵列制程调度问题的性能。文献[6]设计了2种类型测试问题——小规模和大规模算例，并在算例设计时考虑了最大完工时间和总拖期时间的相互冲突。本文从小规模测试问题中随机选择12个用于测试，各个算例的交付期的宽松程度不同，数据取整并服从均匀分布，其中，工件数在10～20内取值，工位数在5～10内取值，可重入次数取值范围为1～2，每个工位的并行机器数在1～2内取值，工序加工时间在1～10内取值，每个工位上机器的单位时间空转耗能取值范围在1～5之间。

3.3 性能评价指标

最大完工时间、总拖期时间和总耗能的度量单位不同，为了更合理地对各种算法的性能指标进行评价，采用min-max标准化方法对各个目标值进行数据归一化处理，然后将归一化之后的数据参与性能评价指标计算。本文选取了3个性能评价指标：空间度量指标S、世代距离DG和反向世代距离DIG，其中，S和DG参考文献[20]。由于所测试问题的真实最优Pareto前沿未知，因此将4种算法的全部结果中的非支配解近似作为最优Pareto前沿。

S用于衡量所得Pareto前沿上非劣解分布的均匀性，其计算方法为

i,j=1,2,…,FP

DG用来评价所得Pareto前沿与最优Pareto前沿之间的逼近程度，其计算公式为

其中，bi为所得Pareto前沿上第i个解与最优Pareto前沿中最近解之间的欧氏距离。DG越小，算法的收敛性越好。DG的最小取值为0，表示所得Pareto前沿中的所有非劣解均包含在最优Pareto前沿里。

DIG是DG的一种变形，但该指标更具综合性，能够同时评价所得Pareto前沿的收敛性和非劣解的多样性，其计算公式为

3.4 参数设置

参数设置对元启发式算法的性能有很大影响，本文所设计的IMSSA主要涉及三个关键参数：种群规模N、Lévy飞行步长中的参数β、变邻域搜索的最大迭代次数ls。为了获得最佳的因子水平组合，使用田口方法进行实验设计，研究算法参数对调度结果的影响，将Sproblem-06-11问题作为测试算例。每个参数设置4个因子水平，如表2所示。根据实验的组数、实验因子数、因子水平数，采用L16(43)的直交表，通过较少的实验研究更多的因子。对于直交表中的每个因子水平组合，IMSSA独立运行20次，并记录所得到的非支配解集。由于DIG能够同时评价所得Pareto前沿的收敛性和非劣解的多样性，因此使用DIG表示响应特征值VR，实验结果如表3所示，VR越小，该实验参数组合性能越好。另外，响应特征平均值VAR和每个参数的重要性排序如表4所示。表4中，Δ=max(VAR) -min(VAR)；排序值即按Δ从大到小的顺序，为Δ最大的因子分配秩1，为Δ第二大的因子分配秩2，依此类推。

表2 因子水平设置

表3 直交表和响应特征值

表4 响应表

从表4中可以看出，种群大小N最为显著。N过大，会导致算法收敛非常缓慢；N过小，可能引起算法早熟收敛。β影响Lévy飞行的步长，显著性次之。变邻域搜索的最大迭代次数ls的显著性水平最低，ls过大，会导致计算量过大；ls过小，会使局部搜索不充分。根据上述的实验结果分析，将IMSSA的参数N=150，β=1.9，ls=5作为最佳的因子水平组合进行接下来的计算实验。另外，将其他相关参数设置如下：最大迭代次数tmax=100，外部档案大小为100。

3.5 实验结果与分析

本文选取12个测试问题来比较4种多目标优化算法，针对每个算例，每种算法各独立运行20次，每运行一次都能获得一个S、DG、DIG的组合。表5统计了每种算法20次运行后各个评价指标的均值和标准偏差，每个指标的最优结果用粗体标出。从表5中可以看出，对于DG和DIG，IMSSA所得Pareto前沿上非劣解的收敛性和多样性均是最优的，NSGA-Ⅱ效果次之，接着是MSSA，MOPSO算法性能最差。然而，对于S，各个算法的优势不明显，就所有测试问题而言，MOPSO算法所得Pareto前沿上非劣解分布的均匀性最好。

表5 不同算法得到的三个评价指标结果

均值和标准偏差只能从宏观上展现各个算法的求解效果，为了更深入地判断算法之间是否具有显著差异，采用相关样本的Wilcoxon符号秩检验方法。针对所有测试问题的3个评价指标，分别将IMSSA与其他3种算法进行两两比较。Wilcoxon符号秩检验结果如表6所示，其中P表示假设概率，即在原假设为真的前提下出现观察样本以及更极端情况的概率，P<0.05表明两种算法的优化性能之间具有显著差异。从表6中的结果可以看出，就DG和DIG而言，IMSSA明显优于其他几种算法；对于S，IMSSA与MSSA、MOPSO和NSGA-Ⅱ没有显著性差异，因此这4种算法的分布性水平差异不大。3个评价指标箱线图(图4)进一步验证了该结论。图4中，*表示异常值(远离其他数据值的数据值)，处于1.5～3倍的四分位数间距之间的异常值在图中常用○表示。因此综上所述可以得出结论，本文所设计的IMSSA能有效解决考虑节能的TFT-LCD面板阵列制程调度问题。具体而言，在Pareto前沿上非劣解的收敛性和多样性方面，IMSSA明显优于其他几种算法；在非劣解分布的均匀性方面，4种算法的分布性水平差不多。

表6 Wilcoxon符号秩检验

注：显著性水平设为0.05，sgn(P<0.05)判断P是否小于0.05。

Sproblem-06-11测试问题中，19个工件在13台机器上加工，可重入1次，共有9个加工工位，第1～9个工位上的同速并行机器数量分别是1、1、2、2、1、2、2、1、1，第1～9个工位上机器的单位时间空转耗能分别是4、2、3、3、1、2、1、1、2(单位kgce/min)。4种算法的Pareto前沿如图5所示，可以看出，对于所研究的问题，IMSSA的收敛性最好，NSGA-Ⅱ效果次之，接着是MSSA，而MOPSO收敛性最差。由图5a可以看出，针对所研究的问题，最大完工时间和空转总耗能成正比的线性关系，即要想实现节能目标，就要尽量缩短最大完工时间；最大完工时间缩短时，总拖期时间就会急剧延长，进而影响交货时间和客户满意度水平，三者之间相互冲突，需要企业决策者合理权衡。

(a) S指标

(b) DG指标

(c) DIG指标

4 结论

(1)将TFT-LCD面板阵列制程抽象为可重入混合流水车间调度问题，以最大完工时间、总拖期时间和总耗能作为优化目标，构建了多目标混合整数规划模型。

(2)对多目标樽海鞘群算法(MSSA)进行了一系列改进操作：设计了针对可重入混合流水车间调度问题的编码和解码机制；基于Lévy飞行，对领导者的个体位置更新方式进行了改进；对外部档案中的非支配个体的变邻域进行搜索操作。

(3)通过对一些测试问题的数值实验，将本文改进的MSSA算法(IMSSA)与基本MSSA、多目标粒子群优化(MOPSO)算法和快速非支配排序遗传算法(NSGA-Ⅱ)进行对比研究，结果表明，IMSSA能有效解决考虑节能的TFT-LCD面板阵列制程调度问题。在非劣解的收敛性和多样性方面，IMSSA明显优于其他几种算法；在非劣解分布的均匀性方面，4种算法的分布性水平差不多。

(a)最大完工时间和空转总耗能

(b)最大完工时间和总拖期时间

(c)总拖期时间和空转总耗能

未来将进一步对本文的模型假设进行调整，例如假设同工位的并行机器是异质的，机器具有多种转速，或考虑机器的启停操作等，通过具体的实际生产策略达到降低能耗的目的。在绿色生产指标方面，不仅仅只局限于能耗指标，也可以延伸到对碳排放和污染物排放等指标的优化。