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

姚远远 叶春明

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

摘要:TFT-LCD面板生产的阵列制程是可重入混合流水车间调度问题,采用一种改进多目标樽海鞘群算法对其进行优化求解。构建以最大完工时间、总拖期时间和总耗能为优化目标的数学规划模型;针对该问题结构特点,对基本多目标樽海鞘群算法进行了一系列改进操作,包括基于升序排列的随机键编码、PS方法解码、基于Lévy飞行的领导者个体位置更新方式,以及外部档案中非支配个体的变邻域搜索操作,并采用田口方法进行算法参数设置;最后通过对基准算例的数值实验,将改进多目标樽海鞘群算法与基本多目标樽海鞘群算法、多目标粒子群优化算法、快速非支配排序遗传算法进行对比,实验结果表明了改进多目标樽海鞘群算法的有效性。

关键词可重入混合流水车间调度;改进多目标樽海鞘群算法;阵列制程;节能

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

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

1.2 模型建立

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

目标函数:

min Cmax=max Cj

(1)

(2)

min Tec=Pec+Sec

(3)

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

约束条件:

(4)

(5)

M(2-rijkl-rijkl)+M(1-Zjkjk)+(Sjk-Sjk)≥pjk

(6)

i,j<j′,l,OjkUi,OjkUi

M(2-rijkl-rijkl)+MZjkjk+(Sjk-Sjk)≥pjk

(7)

i,j<j′,l,OjkUi,OjkUi

M(2-rijkl-rijkl)+(Sjk-Sjk)≥pjk

(8)

i,k<k′,l,OjkUi,OjkUi

Sjk≥0 ∀j,k

(9)

(10)

CjCmaxj

(11)

(12)

(13)

i,j,k,l

式中,i为工位序号,i=1,2,…,ss为工位总数;l为工位i中的机器序号,l=1,2,…,mik为工件j的工序序号,k=1,2,…,NjNj为工件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.1 A small-sized TFT-LCD array process casemin

加工时间首次加工路径第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/2 j=1,2,…,D

其中,xi,j为第i个樽海鞘个体位置的第j维变量值;Fj为食物源位置的第j维变量值;r是0~1之间的随机数,r<0.5时,xi,jFj的方向靠近,否则远离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,其中,SDG参考文献[20]。由于所测试问题的真实最优Pareto前沿未知,因此将4种算法的全部结果中的非支配解近似作为最优Pareto前沿。

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

i,j=1,2,…,FP

其中,di表示所得Pareto前沿上第i个解与其周围最近解j之间的欧氏距离。上标ij表示所得Pareto前沿上的两个非劣解,下标1~3表示非劣解的目标值维数。为所有di的均值;FP为所得Pareto前沿中非劣解的个数。S越小,非劣解分布的均匀性越好。S的最小取值为0,表示所得Pareto前沿上非劣解等距离均匀分布。

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

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

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

其中,fP表示所得Pareto前沿,表示最优Pareto前沿,为最优Pareto前沿中非劣解的个数,d(x, fP)表示最优Pareto前沿上的解x与所得Pareto前沿中最近解fP之间的欧氏距离。DIG越小,算法性能越好。

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 因子水平设置

Tab.2 Levels of parameters

参数因子水平1234N50100150200β1.21.51.71.9ls051015

表3 直交表和响应特征值

Tab.3 Orthogonal arrays and RV values

实验序号因子NβlsVR实验序号因子NβlsVR11110.148 993130.087 921220.132 0103240.124 231330.172 2113310.111 741440.161 4123420.096 552120.106 1134140.081 362210.157 6144230.190 872340.193 0154320.123 582430.076 5164410.079 8

表4 响应表

Tab.4 ARV values and significance ranks

因子水平Nβls10.153 6250.106 0500.124 50020.133 3000.151 1500.114 52530.105 0750.150 1000.131 85040.118 8500.103 5500.139 975Δ0.048 5500.047 6000.025 450排序123

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

3.5 实验结果与分析

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

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

Tab.5 Results of three metrics obtained by different algorithms

测试问题评价指标IMSSAMSSAMOPSONSGA-Ⅱ均值标准差均值标准差均值标准差均值标准差Sproblem-01-06S0.089 60.100 40.073 60.080 70.052 40.077 00.038 20.053 2DG0.053 40.032 70.106 60.045 50.247 00.106 70.064 90.039 2DIG0.128 80.041 20.170 50.044 20.336 40.085 00.164 50.040 1Sproblem-01-11S0.066 50.064 00.074 70.076 00.097 00.092 40.109 70.096 5DG0.077 50.048 00.148 40.052 20.272 80.109 20.118 70.049 8DIG0.125 00.041 90.243 70.077 90.443 90.108 20.217 30.086 5Sproblem-02-06S0.251 90.247 20.113 90.144 50.066 00.101 10.085 60.178 8DG0.020 20.017 90.063 80.054 60.172 80.113 10.028 30.034 4DIG0.209 60.134 20.334 10.130 40.410 50.113 90.332 40.153 3Sproblem-02-11S0.167 10.110 50.124 10.088 90.112 80.123 30.135 50.122 1DG0.045 40.014 90.063 70.027 10.127 10.034 10.064 50.025 9DIG0.122 70.035 90.162 70.051 90.251 50.040 40.144 70.034 0Sproblem-03-06S0.070 40.088 80.134 40.235 20.042 10.072 60.063 70.097 2DG0.113 80.050 90.205 90.106 50.360 60.159 40.169 10.062 8DIG0.238 20.069 00.340 40.126 60.535 90.136 60.275 50.061 1Sproblem-03-11S0.037 10.063 70.054 50.116 80.018 20.079 50.062 70.120 5DG0.086 80.053 90.233 30.126 50.589 30.268 60.111 20.087 7DIG0.184 30.056 30.374 80.150 90.734 00.282 30.224 30.077 2Sproblem-04-06S0.108 40.119 20.098 90.072 00.111 80.122 30.102 20.069 1DG0.061 50.046 30.117 00.035 80.158 60.039 50.082 70.032 2DIG0.166 10.044 30.259 90.050 90.327 60.059 50.203 00.041 8Sproblem-04-11S0.077 40.051 00.075 50.064 70.108 10.104 30.062 70.047 6DG0.033 80.021 20.100 10.040 70.183 20.067 90.093 60.053 2DIG0.079 80.030 80.222 50.082 90.356 00.082 20.187 30.055 3Sproblem-05-06S0.074 00.033 90.096 70.111 10.066 80.093 50.078 70.060 0DG0.058 10.024 90.115 30.054 90.152 30.081 70.062 00.022 6DIG0.119 70.026 90.213 70.051 20.263 10.080 20.135 30.035 6Sproblem-05-11S0.052 70.048 00.081 40.123 30.066 10.098 30.045 00.063 3DG0.074 90.054 50.129 80.052 80.209 70.083 60.092 40.024 6DIG0.147 00.040 90.205 70.046 20.312 00.108 00.162 30.040 9Sproblem-06-06S0.069 10.023 70.076 50.056 70.062 00.062 20.083 70.060 8DG0.042 10.014 50.105 60.032 80.232 70.111 40.073 20.024 7DIG0.123 20.032 00.263 10.062 70.424 10.133 70.195 60.040 9Sproblem-06-11S0.074 70.050 40.091 60.071 60.102 50.080 70.079 40.076 6DG0.028 70.012 50.094 30.031 70.132 10.042 70.053 60.029 0DIG0.100 50.023 10.219 20.041 00.296 00.060 80.165 70.026 8合计S0.094 90.059 10.091 30.023 40.075 50.030 60.078 90.027 5DG0.058 00.026 80.123 70.051 10.236 50.129 70.084 50.036 6DIG0.145 40.046 10.250 90.067 50.390 90.135 60.200 70.056 7

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

表6 Wilcoxon符号秩检验

Tab.6 Wilcoxon signed-rank test

评价指标SDGDIGMSSAP0.5830.0010.002sgn (P<0.05)NYYMOPSOP0.38800.001sgn (P<0.05)NYYNSGA-ⅡP0.3460.0020.002sgn (P<0.05)NYY

注:显著性水平设为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 不同算法获得的评价指标的箱线图
Fig.4 Boxplots of metrics obtained by different algorithms

4 结论

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

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

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

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

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

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

图5 Sproblem-06-11问题不同算法得到的Pareto前沿
Fig.5 Pareto fronts of Sproblem-06-11 obtained
by different algorithms

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

参考文献

[1] GEN M, ZHANG W, LIN L. Multiobjective Hybrid Genetic Algorithms for Manufacturing Scheduling:Part II Case Studies of HDD and TFT-LCD[C]∥Proceedings of the 9th International Conference on Management Science and Engineering Management (ICMSEM). Berlin:Springer, 2015:27-54.

[2] WANG M Y, SETHI S P, VANDEVELDE S L. Minimizing Makespan in a Class of Reentrant Shops[J]. Operations Research, 1997, 45(5):702-712.

[3] CHOI H S, KIM H W, LEE D H, et al. Scheduling Algorithms for Two-stage Reentrant Hybrid Flow Shops:Minimizing Makespan under the Maximum Allowable Due Dates[J]. International Journal of Advanced Manufacturing Technology, 2009, 42(9/10):963-973.

[4] CHOI H S, KIM J S, LEE D H. Real-time Scheduling for Reentrant Hybrid Flow Shops:a Decision Tree Based Mechanism and Its Application to a TFT-LCD Line[J]. Expert Systems with Applications, 2011, 38(4):3514-3521.

[5] DUGARDIN F, YALAOUI F, AMODEO L. New Multi-objective Method to Solve Reentrant Hybrid Flow Shop Scheduling Problem[J]. European Journal of Operational Research, 2010, 203(1):22-31.

[6] CHO H M, BAE S J, KIM J, et al. Bi-objective Scheduling for Reentrant Hybrid Flow Shop Using Pareto Genetic Algorithm[J]. Computers and Industrial Engineering, 2011, 61(3):529-541.

[7] YING K C, LIN S W, WAN S Y. Bi-objective Reentrant Hybrid Flowshop Scheduling:an Iterated Pareto Greedy Algorithm[J]. International Journal of Production Research, 2014, 52(19):5735-5747.

[8] SHEN J N, WANG L, ZHENG H Y. A Modified Teaching-learning-based Optimization Algorithm for Bi-objective Re-entrant Hybrid Flowshop Scheduling[J]. International Journal of Production Research, 2016, 54(12):3622-3639.

[9] SHEN J N, WANG L, DENG J, et al. A Pareto-based Discrete Harmony Search Algorithm for Bi-objective Reentrant Hybrid Flowshop Scheduling Problem[C]∥Proceedings of the 2nd International Conference on Harmony Search Algorithm. Berlin:Springer, 2016:435-445.

[10] CHO H M, JEONG I J. A Two-level Method of Production Planning and Scheduling for Bi-objective Reentrant Hybrid Flow Shops[J]. Computers and Industrial Engineering, 2017, 106:174-181.

[11] WOLPERT D H, MACREADY W G. No Free Lunch Theorems for Optimization[J]. IEEE Transactions on Evolutionary Computation, 1997, 1(1):67-82.

[12] 王凌, 王晶晶, 吴楚格. 绿色车间调度优化研究进展[J]. 控制与决策, 2018, 33(3):385-391.

WANG Ling, WANG Jingjing, WU Chuge. Advances in Green Shop Scheduling and Optimization[J]. Control and Decision, 2018, 33(3):385-391.

[13] LU C, GAO L, LI X Y, et al. Energy-efficient Permutation Flow Shop Scheduling Problem Using a Hybrid Multi-objective Backtracking Search Algorithm[J]. Journal of Cleaner Production, 2017, 144:228-238.

[14] LEI D M, ZHENG Y L, GUO X P. A Shuffled Frog-leaping Algorithm for Flexible Job Shop Scheduling with the Consideration of Energy Consumption[J]. International Journal of Production Research, 2017, 55(11):3126-3140.

[15] DENG J, WANG L, WU C G, et al. A Competitive Memetic Algorithm for Carbon-efficient Scheduling of Distributed Flow-shop[C]∥Proceedings of the 12th International Conference on Intelligent Computing. Lanzhou, 2016:476-488.

[16] 杜浩, 陈琛. TFT-LCD制造企业节能减排管理模式研究[J]. 环境科学与管理, 2014, 39(12):20-24.

DU Hao, CHEN Chen. Analysis on Energy-saving and Emission-reduction Management Mode of TFT-LCD Manufacturing Enterprise[J]. Environmental Science and Management, 2014, 39(12):20-24.

[17] MIRJALILI S, GANDOMI A H, MIRJALILI S Z, et al. Salp Swarm Algorithm:a Bio-inspired Optimizer for Engineering Design Problems[J]. Advances in Engineering Software, 2017, 114:163-191.

[18] YANG X S. Nature-inspired Metaheuristic Algorithms[M]. 2 ed. Frome:Luniver Press, 2010:16.

[19] COELLO C A C, PULIDO G T, LECHUGA M S. Handling Multiple Objectives with Particle Swarm Optimization[J]. IEEE Transactions on Evolutionary Computation, 2004, 8(3):256-279.

[20] DEB K, PRATAP A, AGARWAL S, et al. A Fast and Elitist Multiobjective Genetic Algorithm:NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2):182-197.

IMSSA for TFT-LCD Panel Array Process Scheduling Problem Considering Energy Saving

YAO Yuanyuan YE Chunming

Business School, University of Shanghai for Science and Technology, Shanghai, 200093

Abstract:Array process of TFT-LCD panel manufacturing was a reentrant hybrid flow shop scheduling problem, and an effective IMSSA was proposed to solve the problem. Firstly, a multi-objective mathematical programming model with makespan, total tardiness, and total energy consumption criteria was formulated. Secondly, considering the characteristics of the problem, a series of improvements were made based on basic multi-objective salp swarm algorithm(MSSA), which included ranked order value based random key encoding, PS decoding methods, updating the position of the leading salps based on Lévy flight, and embedding a variable neighborhood search strategy in external archive. Influences of parameter setting were investigated by means of Taguchi method. Finally, the proposed IMSSA was compared with the basic MSSA, multi-objective particle swarm optimization (MOPSO) and fast nondominated sorting genetic algorithm (NSGA-Ⅱ) based on several benchmarking instances. Experimental results show the effectiveness of IMSSA.

Key words:reentrant hybrid flow shop scheduling; improved multi-objective salp swarm algorithm(IMSSA); array process; energy saving

中图分类号:TP18

DOI:10.3969/j.issn.1004-132X.2019.24.014

收稿日期:2018-05-02

基金项目:国家自然科学基金资助项目(71840003);上海理工大学科技发展基金资助项目(2018KJFZ043)

开放科学(资源服务)标识码(OSID):

(编辑 张 洋)

作者简介:姚远远,女,1989年生,博士研究生。研究方向为复杂车间调度、智能优化算法。发表论文5篇。E-mail:tracy_yao11@163.com。叶春明(通信作者),男,1964年生,教授、博士研究生导师。研究方向为工业工程、生产计划与调度。出版专著3部,发表论文180余篇。E-mail:yechm6464@163.com。