TFT-LCD 制造cell 阶段多目标绿色调度问题研究

刘庭宇， 叶春明， 赵灵玮， 郭 静

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

随着社会生产水平的提高，能源消耗加剧，能源问题成为社会面临的一大问题。《中国制造2025》中指出，全面推行绿色制造，实施绿色制造工程，并将之列入九大战略任务和五大重大工程[1]。据研究，工业生产能耗占全球能源消耗总量的一半左右[2]。薄膜晶体管液晶显示器（thin-film transistorliquid crystal display，TFT-LCD）具有适用范围广、环保特性好、制造成本低、发展潜力巨大等特点，一般用在监视器、显示器、计算机屏幕、手机屏幕等显示领域。TFT-LCD 产品生产流程复杂，生产规模大，加工周期长，制造过程中消耗大量能源。TFT-LCD 工厂中75%的能耗由电力消耗产生，电力消耗中45%～50%的能耗由生产设备产生[3]。因此，生产调度作为TFT-LCD 制造过程中的一大环节，对能耗有着举足轻重的影响。

目前，TFT-LCD 生产过程的研究方向主要包含生产设备布局[4]、需求预测[5]、存货管理[6]、生产调度等。在面板成盒（cell）阶段，Lin 等[7]考虑了批量释放时间和调度规则的影响，并提出了批量释放时间和最大时间不匹配的启发式算法，使cell 阶段生产时间缩短。Tai 等[8]提出了一种混合整数规划模型来求解具有最大等待时间和不等准备时间的液晶注入调度问题，该问题被看成并行机批加工调度问题，目标是最大等待时间限制的条件下使总机器工作量最小。徐峰等[9]以最大完工时间及拖期为目标，提出用不同的遗传策略和解码算法两两组合对cell 阶段进行求解，实验表明，精英保留和贪婪解码相结合的遗传算法取得的效果最好。吴思思等[10]以最大完成时间、机器等待时间和拖期为目标函数，运用布谷鸟搜索算法，解决同时具有学习遗忘效应的TFT-LCD 面板成盒多目标调度问题，并研究了不同学习率和退化因子对调度结果的影响。

车间绿色调度通过对资源的合理分配和优化工件排序，以达到增效、节能、减排、降耗的目的，提高经济效益的同时实现制造过程的绿色化[11]。在车间绿色调度方面，对于不同的问题，研究者给出不同的模型和多种指标的计算方式。针对流水线调度问题，Fang 等[12]提出了一种新的数学方法，除了考虑作业的处理顺序外，还考虑将运行速度作为自变量，通过改变运行速度影响峰值负载和能量消耗。孔琳等[13]提出了一种自适应的交叉、变异和优势保留策略的遗传算法，以最大完工时间、能耗和成本优化为目标，验证了算法的有效性，并提出了高效、节能、经济、综合4 种生产调度模式。刘清涛等[14]建立了以最大完工时间和生产成本为竞争性指标的调度模型及以资源和环境为可持续性指标的评价模型，并使用改进的遗传算法求解，该改进算法能够在保证生产效益的前提下，使生产过程的资源消耗和对环境的影响更小。艾子义等[15]提出了一种结合记忆和全局交换的新型邻域搜索(NSMG)算法，用来解决混合流水车间绿色调度问题。Dai 等[16]以最大完工时间和能耗为目标，提出一种改进的遗传模拟退火算法，结果发现，最大完工时间和能耗之间存在负相关关系。针对并行机调度问题，Li 等[17]提出了一种高效的启发式算法，建立了以能源成本和清理成本之和为约束条件，以最小化最大完工时间为目标的模型，通过实验计算表明，该算法在实际应用中表现良好。Wang 等[18]针对两阶段的并行机调度问题，在考虑经济因素和环境因素的基础上，建立了以最大完成时间为目标的模型，并使用遗传算法来解决该问题。

由上可以看出绿色调度问题有很多学者研究，但是在TFT-LCD 制造cell 阶段调度问题上，无论是单目标调度还是多目标调度，大多数研究只考虑了经济效益，而很少有研究考虑对能耗的影响。因此，本文将构建以最大完工时间、能耗、生产成本为指标的多目标优化调度模型，研究TFT-LCD 制造cell 阶段多目标绿色调度问题，并设计一种改进布谷鸟搜索算法对模型进行求解，并构建Pareto 最优解集。

1 问题描述

1.1 TFT-LCD 生产流程描述

TFT-LCD 主要包括阵列制造（array）、彩色滤光膜（C/F）制造、面板成盒（cell）和模块组装（module）这4 个阶段的生产流程。array 阶段主要负责加工TFT 玻璃基板，在实际生产流程中，彩色滤光膜一般从外部工厂直接购入，cell 阶段主要负责把加工好的同等规格TFT 玻璃基板和彩色滤光膜对位粘合，切割成面板后，注入液晶并粘附偏振片，module 阶段主要根据顾客的要求对成品进行组装。

在TFT-LCD 制造cell 阶段中，玻璃基板(或盒式)被大量运输，盒式由24 片玻璃基板组成。根据玻璃基板的大小，每片玻璃基板包括4 个或6 个LCD 面板单元。大量TFT 玻璃基板和彩色滤光膜分别经过聚酰亚胺(PI) 涂覆和摩擦等工序，然后粘合在一起，经过热加工，切割成面板，最后密封并进行测试。粘合之前属于第一个阶段，粘合及之后属于第二个阶段，cell 阶段的最终产品被称为LCD 面板。TFT-LCD 制造cell 阶段可以看成非等效并行机的混合流水装配作业问题，求解难度较大，cell 阶段生产流程如图1 所示。

图1 TFT-LCD 制造cell 阶段生产流程Fig.1 Production process in the cell stage of TFT-LCD manufacturing

1.2 多目标绿色调度模型

cell 阶段调度是在满足限制条件的基础上，把不同类型的零件合理地分配给不同加工工序的不同机器，即在限制条件下安排最佳的生产排序，使得各目标达到满意的结果。另外，还需满足以下假设：

a. 任一时刻，每台机器只能加工一批工件（在装配工序中，零件A 和零件B 合成一批工件C）；

b. 任一时刻，一批工件只能在一台机器上加工；

c. 各工序一旦开始，生产过程不能被打断；

d. 每批零件的加工路径事先确定；

e. 任一工序，每批工件的加工时间由机器性能和工件类型所决定。

1.2.1 变量说明

基本变量描述如下：n 代表工件类型总数（i=1,2,···,n）；N 代表零件A，B 及装配后的工件总批数；Jr和Jr*代表第r 和第r*批零件或工件（r=1,2,···,N），其中，r 代表零件A，r*代表零件B；Oj代表工件第j 道工序（j=1,2,···,a,a+1,···,b,b+1,···,c），其中j=1,2,···,a代表A 零件批的加工工序，j=a+1,···,b代表B 零件批的加工工序，j=b+1,···,c代表装配后的工序；m 代表当前工序下的第m 台机器（m=1,2,···,M）；trjm代表第r 批工件第j 道工序在第m 台机器上的开始加工时间；Prjm代表第r 批工件第j 道工序在第m 台机器上的加工时间；Drjm代表第r 批工件第j 道工序在第m 台机器上的结束加工时间；Ujm代表第j 道工序第m 台机器上的单位机床使用成本；Wjm代表第j 道工序第m 台机器上的单位加工能耗；ljm代表第j 道工序第m 台机器上的单位空载能耗；Sij代表工序Oj不同类产品之间所需转换的准备时间。

1.2.2 模型建立

绿色调度应当综合考虑时间、能耗和成本等多个目标。生产时间包括机器加工时间和等待时间；生产能耗包括机器加工能耗和空载能耗；生产成本包括生产能耗成本和机床使用成本[13]。因此，本文设置了3 个以最小化为优化方向的目标函数：最大完工时间Tmax、总能耗Etotal和总生产成本Ctotal。以下为多目标绿色调度模型。

目标函数

约束条件

式中，Xrjm与Yjrr'm为决策变量，Z1和Z2为无穷大正数。式（1）中，Tmax代表最大完工时间；式（2）中，Etotal表示加工能耗和空载能耗之和；式（3）中，根据我国工业电价情况取单位能耗成本为0.75 元/（kW·h）[13]，总生产成本Ctotal为能耗成本和机床使用成本之和；式（4）中，当Xrjm=1 时，说明第r 批工件第j 道工序在第m 台机器上加工，否则为0；式（5）中，当Yjrr'm=1 时，说明在第j 道工序上，Jr先于Jr'在第m 台机器上加工，否则为0；式（6）表示在任一时间，一批工件至多在一道工序的一台机器上加工；式（7）表示在任一时间，一台机器最多加工一批工件；式（8）表示任何一批工件在任一工序任一机器加工时，都具有相对应的开始加工时间；式（9）表示必须按照事先确定的加工路径对工件进行加工；式（10）表示第r 批工件第j 道工序在第m 台机器上加工完成后不能超过最大完工时间；式（11）表示一台机器前后两批工件的开始加工时间约束；式（12）、（13）、（14）表示一台机器加工工序关系约束；式（15）、（16）表示装配工序时，零件A 和零件B 合成一批工件C。

2 改进布谷鸟搜索算法

2.1 算法描述

布谷鸟搜索算法（cuckoo search，CS）是Yang等[19]在2009 年提出的一种启发式搜索算法。该算法的灵感来自布谷鸟的繁殖策略。为了解决多维空间寻优问题，在模仿布谷鸟寻找鸟巢的过程中，需要满足以下3 点规则：a. 每只布谷鸟随机寻找鸟巢，并且一次至多能下一只蛋；b. 每次寻找到的最好的鸟巢保留下来，直至找到更好的鸟巢对其进行代替；c. 布谷鸟蛋被宿主察觉的几率为[0，1]，被察觉后，布谷鸟需要寻找新的鸟巢。在上述3 条规则的假设下，得到布谷鸟寻巢路径和位置如下式

但标准CS 算法步长因子为固定数值，若步长因子设置较大，虽然收敛速度较快，但易错过最优解；若步长因子设置较小，会使收敛速度变慢，并且易陷入局部最优解。基于此，本文设计一种改进布谷鸟搜索算法（improved cuckoo search，ICS），在步长因子α0前加入动态系数β0，如下式

式中：T_max 表示最大迭代次数，Times 表示当前迭代次数。由式（19）可以看出，当前迭代次数较小时，动态系数β0较大，有利于在搜索前期更快地找到优质解所在的区域，随着迭代次数的增加，解的质量慢慢提高，动态系数β0慢慢减小，有利于缩小搜索范围，加强对当前周边区域的搜索。由此，改进的布谷鸟寻巢路径和位置如式（20）所示。

2.2 选择多目标问题处理方法

本文建立的多目标绿色调度模型有3 个目标需要优化，并且各个目标之间存在冲突，无法同时达到最优。

解决多目标问题的处理方法一般分为两种。一种是线性加权法，即给每个目标设置权重，目标的结果线性相加，把多目标问题转换为单目标问题求解。该方法虽然降低了多目标优化问题的求解难度，加快了求解速度，但是人为设置权重，无法保证权重的设置具有科学性，而且最终结果十分依赖于各个目标的权重，无法满足所有人的要求。另一种是构建Pareto 最优解集，该方法可以使各个目标值尽可能地接近单个目标的最优解，并且不会遗漏各个目标最优化的情况。因此，本文选择构建Pareto 最优解集来解决多目标问题。

2.3 构建Pareto 最优解集

Pareto 最优解集描述如下：在解集K 中，对于解x、y，若解x 至少存在一个目标函数值优于解y，且其余目标函数值不劣于解y，则称x 支配y，记作x ≺y；若解集K 中不存在任一解有一个目标函数值优于解x，且其余目标函数值不劣于解x，则称解x 为Pareto 最优解集中的一个解。

本文结合双元锦标赛和动态淘汰制两种方法构建Pareto 最优解集。实现过程如下：选择解集K 中的一个解x，将其与剩余解进行比较，若存在解支配x，则直接把解x 从解集K 中删除；若存在解被x 支配，则把该解从解集K 中删除；若剩余解皆不支配x，则把解x 加进Pareto 最优解集中；重复这一步骤，直至解集K 中不存在任何一个解。如果Pareto 最优解集大于规定值N，那么使用聚集距离筛选Pareto 最优解。如果已存在上代Pareto 最优解集，则需将两代Pareto 最优解集合并，继续进行比较。

2.4 算法流程

布谷鸟搜索算法通过不断跳跃形成随机游走过程，该过程服从具有重尾的步长分布。莱维飞行适合于探索性大规模搜索，而改进后的布谷鸟搜索算法在搜索后期加强了搜索深度，使其更易寻得最优解。在结合了双元锦标赛和动态淘汰制两种方法之后，算法的求解步骤如下：

a. 参数初始化。设置布谷鸟种群规模n；最大进化代数T_max；被宿主发现的概率pa；Pareto 解的个数N。

b. 种群初始化并随机选取N 个鸟巢位置。

c. 计算鸟巢位置所对应的目标函数值，构建初始Pareto 最优解集。

d. 根据式（20）得到下一代鸟巢位置，并计算其目标函数值。

e. 每个新鸟巢随机产生一个R，如果R 大于被宿主发现的概率pa，返回步骤d，否则，进入步骤f。

f. 比较两代鸟巢目标函数值，构建新Pareto 最优解集，如果Pareto 最优解集大于N，那么使用聚集距离筛选Pareto 最优解。

g. 若达到最大进化代数T_max，输出最终的Pareto 最优解集，否则，回到步骤d。

改进的布谷鸟搜索算法流程如图2 所示。

图2 改进布谷鸟搜索算法流程图Fig.2 Flow chart of the improved cuckoo search algorithm

3 实验与结果分析

3.1 编码方式

TFT-LCD 制造cell 阶段调度需要考虑当前工件工序机器选择和工件前后加工顺序两个方面，为此，本文设计一种同时考虑当前工件工序机器选择和工件前后加工顺序的两段式编码方式，如图3 所示。

图3 两段式编码方式Fig.3 Two-segment coding

在图3 中，假设有3 台机器：m1，m2，m3，4 个工件：J1，J2，J3，J4，每个工件各有两道工序。在机器编码中，J1 需要先后经过{m1，m2}，J2 需要先后经过{m2，m3}，J3 需要先后经过{m3，m2}，J4 需要先后经过{m3，m2}，该编码确定工件工序机器选择。在工件编码中：上行数字表示工件，排列顺序代表工件前后加工顺序，出现频次代表工序；下行代表使用布谷鸟搜索算法寻找的数字，按升序排列，该编码确定工件的前后加工顺序，两段编码确保所求解可行。

3.2 实验设计和对比算法

机器加工时间不只与工件类型有关，也与机器本身性能有关，基于此，选取文献[10]中的测试实例，产品类型及批量数如表1 所示，工序机器数如表2 所示，不同类型工件在各工序之间转换的准备时间如表3 所示，不同工件工序在机器上的加工时间如表4 所示。需要增加能耗信息和生产成本信息，第j 道工序第m 台机器上的单位加工能耗Wjm∈[9，30]kW/h，第j 道工序第m 台机器上的单位空载能耗ljm∈[1，5]kW/h，第j 道工序第m 台机器上的单位机床使用成本Ujm∈ [0.5，3]元/min。

表1 产品类型及批量数Tab.1 Product type and batch number

表2 工序机器数Tab.2 Number of process machines

表3 不同类型工件之间转换的准备时间Tab.3 Readiness time for the conversion between different types of work piecesmin

表4 工序对应机器加工时间Tab.4 Machine processing time corresponding to operationmin

改进布谷鸟搜索算法参数设计如下：种群规模为50，迭代次数100 次，步长因子为0.1，Pareto解的个数为10。为了验证改进布谷鸟搜索算法在TFT-LCD 制造cell 阶段多目标绿色调度问题上的优越性，本文使用布谷鸟搜索算法和Deb 等[20]提出的带精英策略的快速非支配排序遗传算法（NSGA-II）作为对比算法。布谷鸟搜索算法参数设置与改进布谷鸟搜索算法一致，NSGA-II 算法设置初始种群规模为50，迭代次数100 次，选择概率为0.9，交叉率为0.8，变异率为0.1。为了更好地与改进布谷鸟搜索算法进行比较，构建Pareto最优解集使用本文提到的方法。

3.3 结果分析

上述3 种算法的运行环境：操作系统为Window10，处理器为Intel(R) Core(TM) i5-3210M，主频为2.50 GHz，内存为6 GB，编程环境为Matlab R2018a。

首先对比改进布谷鸟搜索算法和布谷鸟搜索算法，对两种算法的收敛过程进行观察，图4 是两种算法的收敛过程比较图。从图4 可以看出，第1 代种群因为是随机产生，所以两者区别较小；第50 代种群，改进布谷鸟搜索算法因为在搜索前期加大了步长因子，所以收敛速度明显快于布谷鸟搜索算法；第100 代种群，改进布谷鸟搜索算法因为在搜索后期加深了搜索深度，所以结果要好于布谷鸟搜索算法。

图4 收敛过程比较图Fig. 4 Convergence process comparison graph

为了更好地观察改进布谷鸟搜索算法，令ICS，CS，NSGA-II 3 种算法分别运行10 次，对10次运行的结果分别取平均值和最小值，得到表5，为了方便观察，所得数据全部取整。从表5 可以看出，ICS 算法相比于CS 算法，平均最大完工时间减少0.22%，平均总能耗减少1.87%，平均总生产成本减少2.07%，最小最大完工时间减少1.03%，最小总能耗减少1.58%，最小总生产成本减少1.67%；而ICS 算法相比于NSGA-II 算法，平均最大完工时间增加3.72%，平均总能耗减少4.18%，平均总生产成本减少8.85%，最小最大完工时间减少8.33%，最小总能耗减少5.72%，最小总生产成本减少11.05%。可以看出，ICS 算法除了在平均最大完工时间上的数值略大于NSGA-II算法，其他各项均优于CS 和NSGA-II 两种算法。

表5 ICS，CS，NSGA-II 运行结果的平均值和最小值Tab.5 Average and minimum results of ICS, CS, NSGA-II operation

综上所述，在求解TFT-LCD 制造cell 阶段多目标绿色调度问题上，本文提出的ICS 算法相比于CS 算法和NSGA-II 算法更加有效。

4 结论与展望

本文面向TFT-LCD 制造cell 阶段绿色调度问题，建立了以最大完工时间、总能耗、总生产成本为目标的优化模型，并设计了一种改进的布谷鸟搜索算法来求解该模型。基于机器和工序的两段式编码，保证了解的可行性，ICS 算法通过在步长因子前加入动态系数，使其在搜索前期可以更快速地找到优质解的区域。在搜索后期，缩小搜索范围，加强对优质解附近区域进行搜索，提高了算法的求解效率。构建的Pareto 最优解集结合双元锦标赛和动态淘汰制两种方法，保障了所求解的质量。实验分析表明，在求解TFT-LCD 制造cell 阶段绿色调度问题上，ICS 算法要比CS 算法和NSGA-II 算法更加有效。但是，本文所解决的调度问题比较单一，后续作者会使用改进布谷鸟搜索算法来解决其他调度问题，如柔性屏制造调度等，更好地测试和验证该算法。