TFT-LCD模块组装调度问题的改进灰狼优化算法

姚远远，叶春明，杨 枫

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

1 引 言

TFT-LCD(thin-film transistor-liquid crystal display)，全称“薄膜晶体管液晶显示器”，俗称为“液晶面板”，是液晶显示屏家族中的一个高端品种，广泛应用于手机、平板电脑、笔记本电脑和电视等各类显示领域.TFT-LCD属于半导体显示产业的一种，是资金和技术密集型产业，面对激烈的市场竞争压力，亟需提高生产力和运营效率.模块组装作为TFT-LCD生产的最后一个环节，将直接决定产品能否按时交货，并影响客户满意度.本文将对最小化最大完工时间的TFT-LCD模块组装调度问题进行研究.

Chou和Chien等[1]提出了一种多目标混合遗传算法求解TFT-LCD模块组装调度问题，并考虑了工件交付期和机器准备时间等因素.文献[2]使用布谷鸟搜索算法求解极小化工件最大完工时间为目标的TFT-LCD模块组装调度问题，分析探讨学习效应和遗忘效应对模块组装调度问题的影响.现实中的TFT-LCD模块组装调度问题可以抽象成为一种柔性作业车间调度问题(flexible job-shop scheduling problem，FJSP).FJSP是经典的作业车间调度问题的一种延伸，具有更广泛的应用背景和更大的求解难度，已经被证明是一种具有NP难特性的组合优化问题，该问题的求解算法研究已成为车间调度领域的热点.张腾飞等[3]提出了一种改进遗传算法求解FJSP问题，并证明了其有效性和实用性.

Mirjalili等人[4]在2014年提出了一种新颖的灰狼优化算法(grey wolf optimizer，GWO).通过模拟自然界中灰狼种群的社会领导层级机制和捕食行为机制提出，实验结果表明在求解精度和稳定性上GWO要显著优于PSO、DE和GSA算法.GWO算法目前已被广泛应用于多个领域，其中，在车间调度领域，Lu等人[5，6]将多目标的GWO算法用于求解焊装生产车间中的实际调度问题.

本文将采用灰狼优化算法解决TFT-LCD模块组装调度问题.首先，构建了以最小化最大完工时间为优化目标的TFT-LCD模块组装调度问题数学模型；其次，针对基本GWO算法进行了一系列设计和改进，提出了一种改进灰狼优化算法(IGWO)，并对所设计的IGWO算法的算法复杂度和收敛性进行了分析；然后，通过对FJSP问题的不同规模基准算例的仿真实验，对IGWO算法的计算性能和有效性进行了验证；最后，将所提出的IGWO算法应用于解决实际生产活动中的一个TFT-LCD模块组装调度问题.

2 TFT-LCD模块组装调度问题描述及数学模型

2.1 问题描述

TFT-LCD制造流程主要包括三个阶段：TFT阵列(Array)/彩色滤光(CF，color filter)，液晶成盒(Cell)(也称作LCD组装)，以及模块组装(Module)，如图1所示.其中，TFT Array / CF流程与半导体晶圆制造过程相似，区别是所使用的原材料不同.LCD组装主要是组装薄膜晶体管基板和彩色滤光器基板，并在二者之间注入液晶.Module是TFT-LCD生产的最后一个阶段，在这个过程中需要把LCD面板与其他需要定制的零部件组装成最终产品，Module阶段包含五个工站(见图2)，分别把集成电路、印刷电路板、驱动板、背光源和底盘等组装到LCD面板上，具体操作如下：

图1 TFT-LCD制造流程图Fig.1 TFT-LCD process flow

1)焊接集成电路和印刷电路板：将集成电路和印刷电路板元件焊接到LCD面板上；

2)3D衬底层压：当客户需求的是3D类型面板时，在液晶成盒流程之后，需要先对LCD面板进行3D玻璃衬底层压处理；

3)半成品包装：当客户需求的是半成品时，无需在LCD面板上组装其他的定制电子元器件，只需将半成品进行包装交付给客户；

4)组件装配和测试：在LCD面板上组装其他的定制电子元器件以完成成品装配，并对成品的可靠性进行检测；

5)3D校准：针对3D类型的产品，还必须对其成像情况进行校准.

TFT-LCD模块组装调度问题与FJSP问题相类似.例如，图2所示的模块组装车间中有5个工件在8台机器上加工，每个工件的加工路径各不相同，根据客户需求的不同，工件可分为半成品和成品两种，每个工站有一台或多台不同型的并行机器，各台机器的加工速度不同，工序只需在每个工站的一台机器上加工，且每台机器都可以完成该操作.

图2 TFT-LCD模块组装阶段工件加工路径图Fig.2 Process flow for the TFT-LCD module assembly phase

2.2 数学模型建立

本文涉及的数学符号及其含义如下：

n：工件总数；

m：机器总数；

i，h：工件序号，i，h=1，2，…，n；

j：机器序号，j=1，2，…，m；

ni：工件i的工序总数；

k，g：工序序号，k，g=1，2，…，ni；

Oik：工件i的第k道工序；

Aik：工序Oik的可选加工机器集；

pikj：工序Oik在机器j上的加工时间；

M：一个足够大的正数；

可以将TFT-LCD模块组装调度问题描述为有n个工件需要在m台不同型的平行机上进行加工；每个工件i包含ni道工序，并且各道工序的加工次序事先给定；工件i的第k道工序Oik能够在可选加工机器集Aik中的任何一台机器上完成加工；工序Oik在机器j上的加工时间为pikj.

该问题的求解包括两个方面的子问题(机器选择子问题和工序排序子问题)，其调度目标是为每一道工序选择最合适的加工机器，并确定每一台机器上各道工序的最优加工顺序及开始加工时间，使整个系统的性能指标达到最优.模型中涉及的假设有：

1)每台机器在同一时刻只能加工一道工序；

2)每道工序同一时刻只能在一台机器上加工，且一旦开始加工不能中断；

3)不同工件之间有相同的优先级；

4)不同工件的工序之间没有先后顺序约束，同一工件的工序之间有先后约束；

5)所有工件和机器在零时刻都准备就绪.

最大完工时间关系着各个工件的生产周期，是FJSP研究中应用最广泛的性能指标之一，因此，本文将对最小化最大完工时间的TFT-LCD模块组装调度问题进行研究，在文献[1]的数学模型基础上，给出如下混合整数规划模型.

目标函数：

(1)

约束条件：

(2)

(3)

(4)

xikj≤aikj，∀i，k，j

(5)

(6)

∀i，k，h，g，j，Oik≠Ohg

(7)

(8)

yikhgj+yhgikj=xikjxhgj，∀i，k，h，g，j，Oik≠Ohg

(9)

xikj∈{0，1}，∀i，k，j

(10)

yikhgj∈{0，1}，∀i，k，h，g，j，Oik≠Ohg

(11)

(12)

(13)

公式(1)表示目标函数为最小化最大完工时间；约束(2)定义了最大完工时间Cmax；约束(3)和(4)表示工序次序约束，保证每个工件按照指定的工序次序进行加工；约束(5)和(6)保证每道工序只能被分配到可选加工机器集中的一台机器上加工；约束(7)和(8)是析取约束，规定当工序Oik和Ohg被分配到同一台机器j上加工时，两道工序相互之间不能重叠；另外，当不同工件的两道工序被分配到同一台机器j上加工时，约束(9)决定了两道工序之间的先后顺序；约束(10)、(11)定义了决策变量的取值范围；约束(12)定义了工序Oik的完工时间为非负数；约束(13)定义了工序Oik的加工开始时间.

模型中约束条件的处理主要反映在后文算法的编码和解码过程中，用两段式来对灰狼个体进行编码，机器选择部分采用按工序排列的机器编码，工序排序部分采用随机键编码，解码时对机器选择部分从左到右依次读取并转换成机器顺序矩阵和时间顺序矩阵，对工序排序部分通过对随机数进行升序排列可以得到工件顺序，以及相应的工序顺序，并采用工序插入式方法生成活动调度.通过解码过程，可以得到每台机器上工序的加工顺序，以及相应的加工开始时间和结束时间.

3 改进灰狼优化算法

3.1 基本灰狼优化算法简介

灰狼优化算法是由Mirjalili等人[4]提出的一种基于种群的随机优化算法，作为一种仿生群体智能优化算法，GWO算法通过模仿自然界中灰狼群体的社会领导层级机制和捕食行为提出.首先随机生成一组候选解，每次迭代选出种群中最优的三个解(alpha、beta和delta)，由它们带领整个种群向搜索空间的最优解方向移动.其他灰狼个体omega追随alpha、beta和delta寻找更好的解.灰狼种群的包围捕食行为可以通过下述数学公式描述.

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

(23)

(24)

(25)

上述公式中参数A和C决定灰狼优化算法的全局探索和局部开发，当|A|>1时种群进行全局探索，当|A|<1时进行局部寻优.另外，随机生成参数C可以有效避免算法陷入局部最优值.已有研究表明基本GWO算法具有搜索效率高、收敛速度快，及能够有效避免陷入局部最优等优点[4].

3.2 改进灰狼优化算法求解TFT-LCD模块组装调度问题

3.2.1 编码和解码

本文采用分段编码法来对灰狼个体进行编码，灰狼个体由机器选择部分(machines selection，MS)和工序排序部分(operations sequencing，OS)两部分组成，两部分长度相等均为所有工件的工序总数.如图3所示，MS部分采用按工序排列的机器编码[7]，每个位置用整数表示，分别按照工件和工件工序的顺序进行排列，每个整数代表当前工序选择的加工机器在可选加工机器集中的顺序编号，而不是实际对应的机器号，这样可以保证经过后续操作后产生的解仍是可行解；OS部分采用基于随机键的编码，各元素在[0，1]内任意取值，这种编解码方式能够有效降低算法的求解难度，提高求解效率.

图3 灰狼个体编码Fig.3 Representation of the grey wolf vector

由于灰狼个体由两部分组成，需要分别对这两部分进行解码，主要是将OS部分解码成对应于MS部分的活动调度.首先，对MS部分进行解码，从左到右分别读取并转换成机器顺序矩阵和时间顺序矩阵.其次，针对OS部分通过对随机数进行升序排列可以得到工件顺序，以及相应的工序顺序.最后，采用工序插入式方法[8]将OS部分进一步解码成对应于MS部分的活动调度，已有研究表明对于最大完工时间评价指标，活动调度中一定存在最优调度方案.经过上述解码过程，可以得到每台机器上工序的加工顺序，及其相应的加工开始时间和结束时间.

3.2.2 种群初始化

对算法而言，种群初始化是一个很重要的问题，初始解的好坏对算法的求解速度和质量有非常大影响.根据个体位置向量的表达形式，需要分别对MS和OS部分进行初始化.在MS部分采用文献[9]中提出的一种全局搜索、局部搜索和随机产生相结合的初始化方法，简称GLR初始化方法，并将三者的比例设置为60%、30%和10%；采用文献[10]提出的基于搜索的方法对OS部分进行初始化，具体操作方法是：针对每一个已生成的机器分配方案，随机生成若干个工序排序方案，然后将每一个工序排序方案与该机器分配方案组合，选择其中最优的一个组合作为一个初始调度解，重复上述步骤，直到生成整个初始种群为止.

3.2.3 均匀交叉操作

由于MS部分必须保证每个元素的先后顺序保持不变，因此在灰狼优化算法的迭代过程中，对MS部分进行均匀交叉操作(uniform crossover，UX).如图4所示，在种群中随机选择两个灰狼个体W1和W2，从左到右依次对MS部分的每个位置元素，生成一个随机数rand，如果rand小于XOVR(交叉概率)，则对该位置元素执行交叉操作，否则保持不变，从而产生两个新个体NW1和NW2.接着从剩下的种群里再随机选择两个灰狼个体重复执行上述步骤，直到所有个体完成均匀交叉操作.实验发现交叉概率的取值越小求解效果越好，此处将XOVR取值为0.005.

图4 MS部分均匀交叉操作Fig.4 Illustration of the uniform crossover scheme in machine selection vector

3.2.4 进化种群动态操作

为了找到更好的工序排序方案，对基本GWO算法实施进化种群动态操作(evolutionary population dynamics，EPD)[11].EPD操作就是将种群中差的个体移除，即在每次迭代时，将种群中较差的一半灰狼个体位置移除，并以相等概率在alpha、beta和delta周围，以及搜索空间中的随机位置，重新随机生成灰狼个体的新位置.位置更新式如下：

(26)

(27)

(28)

(29)

(30)

其中，β是一个[1，2]之间的参数，根据文献[12，13]中的设定，取β=1.5，u和v服从正态分布如下所示：

(31)

其中

(32)

3.2.5 IGWO算法流程

为了将灰狼优化算法用于求解TFT-LCD模块组装调度问题，本文对基本GWO算法进行了GLR机器选择部分初始化、基于搜索的方法工序排序部分初始化、工序插入式方法解码、均匀交叉操作和进化种群动态操作五个方面的改进，改进后的灰狼优化算法能够有效解决所研究的问题，将其简称为IGWO.图5展示了运用IGWO求解TFT-LCD模块组装调度问题的算法流程.

图5 IGWO算法流程图Fig.5 Flowchart of the IGWO

3.2.6 算法复杂度和收敛性分析

Mi={x|x∈M，f(x)=Fi}

(33)

其中，i=1，2，…，|F|，于是有：

(34)

对于任意的两个元素xi∈Mi，xj∈Mj，有

(35)

易知，F1可以认为是全局最优解F*，而且适应度等于F*的个体都应该在M1里面.

在算法的迭代过程中，灰狼种群数量N保持不变，P={x1，x2，…，xN}.令P为一个集合，包含所有种群，由于种群中灰狼分为alpha、beta、delta和omega四类，那么可能的种群的数目为

(36)

那么为了判断种群的优劣，可以定义P的适应度函数为

F(P)=max{f(xi)|i=1，2，…，N}

(37)

同样，根据适应度的不同又可以把P划分为|F|个非空子集Pi(i=1，2，…，|F|)，|Pi|表示集合Pi的规模.集合P1包括所有适应度为F1的种群.

令pij(i=1，2，…，|F|;j=1，2，…，|Pi|)表示Pi中第j个种群.在位置更新算式的作用下，pij转移到pkl的概率为Prij，kl，Prij，k表示从pij到pk中任意一个种群的转移概率，Pri，k表示从pi到pk中任意一个种群的转移概率，有

(38)

定义1.一个方阵A∈Rn×n称为：

1)非负矩阵，若aij≥0，∀i，j∈{1，2，…，n}；

2)本原矩阵，若A非负，并且存在一个整数k≥1，使得Ak>0；

定义2.对于进化算法，如果收敛于全局最优解，那么它的充分必要条件是

(39)

其中，Pr表示概率，Pt表示第t代种群.

定理1.改进的灰狼优化算法搜索过程是一个时齐的Markov链.

证明：改进的灰狼优化算法是在有限维的种群空间M中搜索的，下一代种群Pt+1与前面0至t代种群无关，所以一个已知种群到另一个特定种群的条件概率在任何时候都不受原来变化的影响.由Markov链原理可知，改进的灰狼优化算法搜索过程具备Markov的无后效性.因此改进的灰狼优化算法的搜索过程是一个时齐的Markov链.

(40)

定理3.在改进的灰狼优化算法中，对∀i，k∈{1，2，…，|F|}，有

(41)

该定理说明，择优选择策略使得灰狼群体的适应度在进化过程中只能是保持不变或提升，不会出现适应度退化的情况.

定理4.改进的灰狼优化算法全局收敛.

证明：每个Pri，i=1，2，…，|F|可看作是时齐有限Markov链上的一个状态，由定理1可知，算法的转移概率矩阵表示为

(42)

其中，R>0，T≠0，S=1

根据定理2可知

(43)

其中，S∞=1，R∞=(1，1，…，1)T，因此Pr∞就是一个稳定的随机矩阵，且有

(44)

因此，无论当前灰狼种群处于何种适应度状态，经过无穷次进化后都将以概率1收敛到最优适应度状态，所以改进的灰狼优化算法是全局收敛的.

4 实验结果与分析

4.1 算法有效性验证

为了验证所提出的IGWO算法求解TFT-LCD模块组装调度问题的有效性，本文选取与TFT-LCD模块组装调度问题相类似的FJSP问题的Kacem基准算例[14]和Brandimarte基准算例[15]进行计算实验，此处将测试问题的时间单位统一定为min.仿真环境为操作系统Win 7，处理器Intel Core i5-4210M CPU @2.60GHz，内存4GB，采用MATLAB R2012a实施算法编程.算法的相关参数设置如下：将灰狼种群大小设置为50，最大迭代次数MaxT=500，交叉率XOVR=0.005，GS=0.6，LS=0.3，RS=0.1.

首先，通过对Kacem数据的五个不同规模基准算例的仿真测试，对算法中几种改善策略的有效性进行验证.为此专门设计了四种改进算法，分别命名为GWO_1、GWO_2、GWO_3和IGWO，其中IGWO为本文所提出的算法，各个算法中具体包含的改进策略如表1所示.针对不同算例，每种算法各独立运行30次后进行比较，结果如表2所示.其中，BEST表示算法运行30次所获得的最佳结果，AVG表示算法30次运行结果的平均值，RPD表示相对百分比偏差，其计算公式为RPD=100(BEST-C*)/C*，Mean表示五个算例下各算法RPD的平均值.根据表2中结果，通过GWO_1和GWO_2的比较，可以发现GLR机器选择部分初始化方法能够显著改善算法求解性能；GWO_3的数据结果表明均匀交叉操作和进化种群动态操作可以进一步提升算法性能；IGWO的求解结果(尤其是15×10问题)验证了该算法求解FJSP问题的有效性.虽然对于10×7、10×10和15×10这三个问题，IGWO未能找到已知最优值，但是比较接近已知最优值.针对BEST、AVG、RPD和Mean各个评价指标，IGWO在四种改进算法中都是效果最好的.

表1 GWO算法的不同改进策略及命名Table 1 Versions of different improved GWO and names

通过表2中的评价指标只能对各算法求解结果有个整体了解，不能对各算法的每次运行结果进行比较，为了更精确地比较各种算法的优化性能，使用SPSS Statistics 19进行威尔科克森符号秩检验比较两两算法之间是否具有显著差异.分别将IGWO与其它三种改进算法进行两两比较，结果如表3所示，如果P值小于0.05就表明两种算法的优化性能之间具有显著差异.表3结果表明，除了较为简单的4×5问题以外，所提出的IGWO算法的优化性能明显区别于其它三种改进算法.另外，针对这五个基准算例，本文还分别对四种算法的30次运行结果分布情况绘制了箱线图，如图6所示，进一步验证了IGWO算法的有效性.

表2 不同改进策略的算法求解结果对比Table 2 Statistical results of compared approaches over 30 independent runs on Kacem data

注：n表示工件数，m表示机器数，C*表示该问题的已知最优值，“*”表示找到已知最优值，AVG和RPD结果均保留到小数点后2位.

为了进一步验证本文提出的IGWO算法性能，分别将IGWO算法与文献[8]提出的混合和声搜索(HHS)算法，以及文献[16]提出的人工蜂群(ABC)算法进行比较研究，并对Brandimarte的十组数据进行测试.表4给出了IGWO和HHS、ABC算法的十个算例对比结果.其中，BEST是算法30次运行求得的最优值，AVG是算法30次运行结果的均值，SD表示算法运行30次结果的标准偏差，#best表示算法取得最优值的算例个数.从表4可知，在3种对比算法中，HHS求解效果最好，能够获得最优解的算例个数为10个；ABC次之，一共有8个算例取得最优解；然而，本文提出的IGWO算法对其中的4个算例不能获得最优解，虽然没有HHS和ABC算法的效果那么突出，但是针对BEST和AVG指标，IGWO算法的求解结果和其他两种算法相差并不是很大，表明本文提出的IGWO是求解FJSP问题中工件最大完工时间的一种比较有竞争力的算法，从而验证了算法有效性.

表3 威尔科克森符号秩检验P值结果Table 3 P-values obtained from the Wilcoxon signed-rank test

注：N/A表示该算法不能和自己进行对比，显著性水平设为0.05.

4.2 实例验证

通过对不同规模基准算例的仿真实验，验证了所提出的IGWO算法的有效性，接下来进一步将IGWO算法用于解决实际生产活动中的一个TFT-LCD模块组装调度问题实例.本文选取文献[17]中的一个小规模测试问题实例进行算法实用性研究，该测试问题是基于一家台湾TFT-LCD公司的实际生产数据而设计.在该测试问题中，有8个工件(共22道工序)被安排在模块组装车间的8台机器上进行加工，每个工件的加工路径和工序数各不相同，相应的加工路径图、每道工序可选择的机器序号及其对应的加工时间等相关信息可参考文献[17]，加工时间单位为s.

图6 不同算法分别求解Kacem五个算例的箱线图Fig. 6 Box plots of compared approaches over 30 independent runs on Kacem data

表4 Brandimarte数据对比结果Table 4 Results of the ten BRdata instances

注：n表示工件数，m表示机器数，LB表示最优解下界，UB表示最优解上界，“*”表示已知最优解，AVG和SD结果均保留到小数点后2位.

通过IGWO算法求得该实例问题的最小化最大完工时间值为93000s，该结果与文献[17]的实验结果一致，对应的调度方案甘特图如图7所示.通过甘特图可以清楚地看出每个工件的每道工序在哪一台机器上进行加工，及其相应的加工开始时间和完成时间，同时也可以了解到每台机器加工了哪些工件，以及这些工件之间的加工先后顺序.例如，图7中的“101”表示第1个工件的第1道工序，“402”表示第4个工件的第2道工序，其他标号的含义同上；第1台机器加工了3道工序，分别是101、402和601；第7台机器加工了303、803、702、202和403共5道工序.针对该调度方案，804在第8台机器上加工，是最后一道被加工完成的工序，其加工完成时间为第93000s，即该实际案例问题的最小化最大完工时间.

另外，本文还给出了IGWO算法求解实际案例问题的寻优曲线，如图8所示.从图8中可以看出最优灰狼个体的迭代曲线变化情况，以及整个灰狼种群均值的寻优曲线变化情况.在第1000次迭代时，种群均值基本收敛到一个稳定值(108500s左右).从最优灰狼个体的迭代曲线可以看出，最优灰狼个体在迭代之初就表现出很好的求解效果(初始解为98000s)，这是由于IGWO算法中设计了非常有效的种群初始化方法(GLR机器选择部分初始化、基于搜索的方法工序排序部分初始化)；在第222次迭代时，最优灰狼个体找到了最优解93000s，表明了本文提出的IGWO算法具有较快的收敛性，这归功于基本GWO算法高效的灰狼个体位置更新方式、均匀交叉操作和进化种群动态操作.综上所述，本文提出的IGWO算法能有效解决真实的TFT-LCD模块组装调度问题.

图7 IGWO算法求解实际案例问题甘特图Fig.7 Gantt chart of the real-world TFT-LCD module assembly scheduling case obtained by IGWO

图8 IGWO算法求解实际案例问题寻优曲线Fig.8 Convergence curve in solving the real-world TFT-LCD module assembly scheduling case by IGWO

5 结 论

本文设计了一种改进灰狼优化算法解决以最小化最大完工时间为优化目标的TFT-LCD模块组装调度问题，具体包含以下研究内容：

1)采用分段编码方法对灰狼个体进行编码；采用工序插入式方法将工序排序部分解码成对应于机器选择部分的活动调度；使用GLR方法对机器选择部分进行初始化，以及基于搜索的方法对工序排序部分进行种群初始化；在算法迭代过程中，对机器选择部分执行均匀交叉操作，并对工序排序部分进行进化种群动态操作；同时，对所设计的改进灰狼优化算法的计算复杂度和收敛性进行了分析.

2)通过对FJSP问题的Kacem和Brandimarte基准算例的数值实验，验证了所提出的IGWO算法的计算性能和有效性；另外，通过对实际生产活动中的一个TFT-LCD模块组装调度问题实例的测试，进一步表明了本文提出的IGWO算法解决真实TFT-LCD模块组装调度问题的实用性和有效性.

未来将对基于Pareto的多目标灰狼优化算法进行研究，并运用其解决更加复杂的离散车间调度问题.