﻿ 基于改进布谷鸟搜索算法的TFT-LCD制造调度方法
 计算机系统应用  2020, Vol. 29 Issue (3): 47-54 PDF

TFT-LCD Manufacturing Scheduling Method Based on Improved Cuckoo Search Algorithm
LIU Ting-Yu, YE Chun-Ming
Business School, University of Shanghai for Science and Technology, Shanghai 200093, China
Foundation item: National Natural Science Foundation of China (71840003); Science and Technology Development Fund of Shanghai University for Science and Technology (2018KJFZ043)
Abstract: Considering the green scheduling problem of TFT-LCD manufacturing cell stage based on improved cuckoo search algorithm, a mathematical model was established aiming at minimization of the maximum completion time and total carbon emissions. By using three-stage coding based on machine selection, speed selection and process selection and using an improved cuckoo search algorithm with dynamic coefficients before step size factor, the Pareto optimal solution set is constructed by combining the dual championship and the dynamic elimination system. The validity of the model and algorithm is verified by simulating the actual production data of a workshop. The simulation results show that the improved cuckoo search algorithm can effectively reduce carbon emissions while guaranteeing the maximum completion time.
Key words: TFT-LCD manufacturing cell stage     machine speed     carbon emissions     improved cuckoo search algorithm     Pareto optimal solution set

1 问题描述 1.1 TFT-LCD装配过程描述

TFT- LCD制造中的cell阶段是将彩色滤光膜(CF)和TFT玻璃基板两个部件组装在一起的组装过程. 通常彩色滤光膜是从外部供应商购买的, 而TFT玻璃基板是由自己的阵列工厂生产的. 在整个组装过程中, TFT玻璃基板和彩色滤光膜分别经过配向膜印刷, 摩擦, 密封胶/隔离子涂布, 粘接, 切割, 填充液晶, 偏振片粘附和检查等11道工序. cell阶段可以看作非等效并行机的混合流水车间问题. cell阶段制造工艺流程如图1所示.

 图 1 TFT-LCD制造cell阶段制造工艺流程

1.2 TFT-LCD制造cell阶段绿色调度模型建立

${{n}}$ : 工件类型数( ${{i}} = 1,2, \cdots ,{{n}}$ );

${{N}}$ : 工件批数, 包括零件A, B及装配后工件C;

${{{J}}_{{r}}}$ / ${{{J}}_{{{{r}}^{\rm{*}}}}}$ : 第 ${{r}}$ /第 ${{{r}}^{\rm{*}}}$ 批零件或工件( ${{r}} = 1,2, \cdots ,{{N}}$ ), 其中, ${{r}}$ 代表零件A, ${{{r}}^{\rm{*}}}$ 代表零件B;

Oj: 工件第j道工序( ${{j}} \!=\! 1,2, \cdots ,{{a}},{{a}} \!+\! 1, \cdots ,{{b}},{{b}} \!+\! 1, \cdots ,$ ${{c}}$ ), 其中零件A批加工工序为 ${{j}} = 1,2, \cdots ,{{a}}$ , 零件B批加工工序为 ${{j}} = {{a}} + 1, \cdots ,{{b}}$ , 装配后工序为 ${{j}} = {{b}} + 1, \cdots ,{{c}}$ ;

m: 当前工序下的第m台机器( ${{m}} = 1,2, \cdots ,{{M}}$ );

${{{v}}_{\rm{l}}}$ : 每台机器的转速( ${{V}} = {{{v}}_1},{{{v}}_2}, \cdots ,{{{v}}_{{l}}}, \cdots ,{{{v}}_{{d}}}$ ), 共 ${\rm{d}}$ 种转速;

trjm: 第r批工件第j道工序在第m台机器上的开始加工时间;

Prjm: 第r批工件第j道工序在第m台机器上的基础加工时间;

Prjml: 第r批工件第j道工序在第m台机器上以转速l加工的时间;

Drjm: 第r批工件第j道工序在第m台机器上的结束加工时间;

Wjml: 第j道工序第m台机器上以转速l加工的单位能耗;

ljm: 第j道工序第m台机器上的单位空载能耗;

Sij: 工序Oj不同类型工件之间转换的准备时间;

Xrjml: 第r批工件第j道工序在第m台机器以转速l加工为1, 否则为0;

Yjrr'm: 在第j道工序, Jr先于Jr'在第m台机器上加工为1, 否则为0.

(1)某一时刻, 每台机器只能加工一批工件(在装配工序中, 零件A和零件B合成一批工件C), 并且加工开始后, 机器转速保持不变.

(2)某一时刻, 一批工件只能在一台机器上加工, 并且加工开始后, 加工过程不能被中断.

(3)所有机器在整个调度期间都是可用的(没有机器故障).

(4)零件A、零件B和装配后工件C的加工路径事先确定.

(5)每道工序的加工时间由机器转速和工件类型共同决定.

 ${{{T}}_{{\rm{max}}}} = \max \left( {{{{t}}_{{{rjm}}}} + {{{P}}_{{{rjml}}}}{{{X}}_{{{rjml}}}}} \right)$ (1)
 \begin{aligned} {C_{\rm{total}}} = &{\varepsilon \mathop \sum \limits_{j = 1}^{O_j} \mathop \sum \limits_{m = 1}^{M} \mathop \sum \limits_{r = 1}^{N} \mathop \sum \limits_{l = 1}^{d}} {\left( {{P_{rjml}}{X_{rjml}}{W_{jml}}} \right.}\\ &+{\left. {\left( {{D_{jm}} - {X_{rjml}}{P_{rjml}} - {t_{jm}}} \right){l_{jm}}} \right) } \\ \end{aligned} (2)

 $\mathop \sum \limits_{j = 1}^{O_j} \mathop \sum \limits_{m = 1}^{M} \mathop \sum \limits_{l = 1}^{d} {X_{rjml}} \le 1$ (3)
 $\mathop \sum \limits_{r = 1}^{N} {X_{rjml}} \le 1$ (4)
 ${{{Z}}_1}{{{X}}_{{{rjml}}}} \ge {{{t}}_{{{rjm}}}}$ (5)
 ${{{t}}_{{{rj'm'}}}} \ge {{{t}}_{{{rjm}}}} + {{{P}}_{{{rjml}}}}{{{X}}_{{{rjml}}}}$ (6)
 ${T_{{\rm{max}}}} = {t_{rjm}} + {P_{rjml}}{X_{rjml}}$ (7)
 ${t_{rjm}} + {P_{rjml}}{X_{rjml}} + {S_{ij}} - {t_{r'jm}} + {Z_2}\left( {{Y_{jrr'm}} - 1} \right) \le 0$ (8)
 $\left( {{{{Y}}_{{{jrr'm}}}} + {{{Y}}_{{{jr'rm}}}}} \right) + {{{Z}}_2}\left( {{{{X}}_{{{rjml}}}} + {{{X}}_{{{r'jml}}}} - 2} \right) \le 1$ (9)
 $\left( {{{{Y}}_{{{jrr'm}}}} + {{{Y}}_{{{jr'rm}}}}} \right) - {{{Z}}_2}\left( {{{{X}}_{{{rjml}}}} + {{{X}}_{{{r'jml}}}}} \right) \le 0$ (10)
 $\left( {{{{Y}}_{{{jrr'm}}}} + {{{Y}}_{{{jr'rm}}}}} \right) - {{{Z}}_2}\left( {{{{X}}_{{{rjml}}}} - {{{X}}_{{{r'jml}}}} + 1} \right) \le 0$ (11)
 ${{{X}}_{{{rjml}}}} = {{{X}}_{{{{r}}^{{*}}}{{jml}}}}\left( {{{j}} = {{b}} + 1} \right)$ (12)
 ${{{t}}_{{{rjm}}}} = {{{t}}_{{{{r}}^{{*}}}{{jm}}}}\left( {{{j}} = {{b}} + 1} \right)$ (13)

2 改进布谷鸟搜索算法 2.1 标准布谷鸟搜索算法描述 2.1.1 布谷鸟繁殖行为

2.1.2 莱维飞行

2.1.3 布谷鸟搜索过程

(1)每只布谷鸟选择一个宿主巢, 然后随机下蛋.

(2)为下一代选择最好的鸟巢.

(3)巢的数量保持不变, 宿主鸟可以以一定的概率 ${{pa}} \in \left[ {0,1} \right]$ 扔掉外来的蛋.

 ${{X}}_{{w}}^{{{p}} + 1} = {{X}}_{{w}}^{{p}} + {{\alpha Levy}}\left( \lambda \right)$ (14)

 ${{Levy}}\left( \lambda \right) \sim {{u}} = {{{p}}^{ - \lambda }} \in \left( {1,3} \right]$ (15)

2.2 改进布谷鸟搜索算法描述

 ${{\beta }} = {{\omega }}\left( {{{T}}\_{max} - {{Times}}} \right) + {{{\beta }}_0}$ (16)

 ${{X}}_{{w}}^{{{p}} + 1} = {{X}}_{{w}}^{{p}} + {{\beta \alpha Levy}}\left( \lambda \right)$ (17)

2.3 构建Pareto最优解集

2.4 改进布谷鸟搜索算法步骤描述

(1)参数初始化. 设置种群规模: z; 最大迭代次数: ${{T}}\_{{max}}$ ; 被宿主发现的概率: pa; Pareto解的个数: Z; 步长因子: ${{\alpha }}$ ; 变化率: ${{\omega }}$ ; 最小动态系数: ${{{\beta }}_0}$ .

(2)种群初始化. 随机选取z个鸟巢位置.

(3)计算鸟巢位置所对应的两个目标函数值, 构建初始Pareto最优解集.

(4)根据式(17)得到下一代鸟巢位置, 并计算其目标函数值.

(5)每个新鸟巢随机产生一个R, 如果R大于被宿主发现的概率pa, 返回步骤(4), 否则, 进入步骤(6).

(6)比较两代鸟巢目标函数值, 构建新Pareto最优解集, 如果Pareto最优解个数大于Z, 那么使用聚焦距离进行筛选.

(7)若达到最大迭代次数 ${{T}}\_{{max}}$ , 输出最终Pareto最优解集, 否则, 回到步骤(4).

3 实验与结果分析 3.1 TFT-LCD制造cell阶段问题编码

TFT-LCD制造cell阶段绿色调度需要同时考虑当前工件工序机器选择、机器转速选择和工件在机器上加工顺序, 为此, 本文设计一种基于机器选择、转速选择和工序选择相结合的三段式编码方式, 如图2所示.

 图 2 三段式编码方式

3.2 测试实例和对比算法

Ding等[16]提出了一种关于加工时间和能耗之间的假设: 对于确定的工序和机器, 随着转速的变大, 加工时间减少, 能耗增加, 即对于 $\forall {{{v}}_{{l}}} > {{{v}}_{{g}}},{{l}},{{g}} \in \left\{ {1,2, \cdots ,{{d}}} \right\}$ 满足 ${{{P}}_{{{rjml}}}} < {{{P}}_{{{rjmg}}}},{{{P}}_{{{rjml}}}} \times {{{W}}_{{{jml}}}} > {{{P}}_{{{rjmg}}}} \times {{{W}}_{{{jmg}}}}$ . 测试实例选取某车间的实际生产数据[8], 产品类型及批量数如表1所示, 工序机器数如表2所示, 不同工件工序在机器上的加工时间如表3所示, 不同类型工件在各工序之间转换的准备时间如表4所示. 需要增加机器转速和能耗信息, ${{v}} = \left\{ {1.00,1.30,1.55,1.80,2.00} \right\}$ , ${{{W}}_{{{jml}}}} = 4 \times {{v}}_{{l}}^2$ , ${{{l}}_{{{jm}}}} =$ 1, 显然加工时间和能耗之间的关系满足上述假设.

3.3 结果分析

 图 3 3种算法Pareto解分布对比

4 结论与展望

 [1] Garetti M, Taisch M. Sustainable manufacturing: Trends and research challenges. Production Planning & Control, 2012, 23(2–3): 83-104. [2] Lee ZY, Pai CC. Operation analysis and performance assessment for TFT-LCD manufacturers using improved DEA. Expert Systems with Applications, 2011, 38(4): 4014-4024. DOI:10.1016/j.eswa.2010.09.063 [3] 程星华, 李强. TFT-LCD工厂能源消费结构及用能特点分析. 液晶与显示, 2014, 29(5): 856-863. [4] Choi HS, Kim JS, Lee DH. Real-time scheduling for reentrant hybrid flow shops: A decision tree based mechanism and its application to a TFT-LCD line. Expert Systems with Applications, 2011, 38(4): 3514-3521. DOI:10.1016/j.eswa.2010.08.139 [5] Hong TY, Chien CF, Wang HK, et al. A two-phase decoding genetic algorithm for TFT-LCD array photolithography stage scheduling problem with constrained waiting time. Computers & Industrial Engineering, 2018, 125: 200-211. [6] Lin JT, Wang FK, Peng CC. Lot release times and dispatching rule for a TFT-LCD cell process. Robotics and Computer-Integrated Manufacturing, 2008, 24(2): 228-238. DOI:10.1016/j.rcim.2006.10.006 [7] Wu HH, Chen CP, Tsai CH, et al. Simulation and scheduling implementation study of TFT-LCD cell plants using Drum-Buffer-Rope system. Expert Systems with Applications, 2010, 37(12): 8127-8133. DOI:10.1016/j.eswa.2010.05.075 [8] 徐峰, 步丰林. 改进遗传算法求解混合流水装配作业调度问题. 微型电脑应用, 2013, 29(9): 58-61. DOI:10.3969/j.issn.1007-757X.2013.09.017 [9] 吴思思, 叶春明, 李瑞婷. 具有学习退化效应的TFT-LCD面板成盒多目标调度问题研究. 上海理工大学学报, 2018, 40(3): 238-248. [10] Chou CW, Chien CF, Gen M. A multiobjective hybrid genetic algorithm for TFT-LCD module assembly scheduling. IEEE Transactions on Automation Science and Engineering, 2014, 11(3): 692-705. DOI:10.1109/TASE.2014.2316193 [11] Gahm C, Denz F, Dirr M, et al. Energy-efficient scheduling in manufacturing companies: A review and research framework. European Journal of Operational Research, 2016, 248(3): 744-757. DOI:10.1016/j.ejor.2015.07.017 [12] Cataldo A, Perizzato A, Scattolini R. Production scheduling of parallel machines with model predictive control. Control Engineering Practice, 2015, 42: 28-40. DOI:10.1016/j.conengprac.2015.05.007 [13] Wang YC, Wang MJ, Lin SC. Selection of cutting conditions for power constrained parallel machine scheduling. Robotics and Computer-Integrated Manufacturing, 2017, 43: 105-110. DOI:10.1016/j.rcim.2015.10.010 [14] Ji M, Wang JY, Lee WC. Minimizing resource consumption on uniform parallel machines with a bound on makespan. Computers & Operations Research, 2013, 40(12): 2970-2974. [15] Li K, Zhang X, Leung JYT, et al. Parallel machine scheduling problems in green manufacturing industry. Journal of Manufacturing Systems, 2016, 38: 98-106. DOI:10.1016/j.jmsy.2015.11.006 [16] Ding JY, Song SJ, Wu C. Carbon-efficient scheduling of flow shops by multi-objective optimization. European Journal of Operational Research, 2016, 248(3): 758-771. DOI:10.1016/j.ejor.2015.05.019 [17] Zhai YX, Biel K, Zhao F, et al. Dynamic scheduling of a flow shop with on-site wind generation for energy cost reduction under real time electricity pricing. CIRP Annals, 2017, 66(1): 41-44. DOI:10.1016/j.cirp.2017.04.099 [18] Huang RH, Yu SC. Two-stage multiprocessor flow shop scheduling with deteriorating maintenance in cleaner production. Journal of Cleaner Production, 2016, 135: 276-283. DOI:10.1016/j.jclepro.2016.06.109 [19] Lu C, Gao L, Li XY, et al. Energy-efficient permutation flow shop scheduling problem using a hybrid multi-objective backtracking search algorithm. Journal of Cleaner Production, 2017, 144: 228-238. DOI:10.1016/j.jclepro.2017.01.011 [20] 赵敏, 张卫国, 余立中. 上海市能源消费碳排放分析. 环境科学研究, 2009, 22(8): 984-989. [21] Yang XS, Deb S. Cuckoo search via Lévy flights. Proceedings of World Congress on Nature & Biologically Inspired Computing. Coimbatore, India. 2009. 210–214. [22] Brown CT, Liebovitch LS, Glendon R. Levy flights in Dobe Ju/’hoansi foraging patterns. Human Ecology, 2007, 35(1): 129-138. DOI:10.1007/s10745-006-9083-4 [23] Yang XS, Deb S. Cuckoo search: Recent advances and applications. Neural Computing and Applications, 2014, 24(1): 169-174. DOI:10.1007/s00521-013-1367-1 [24] Deb K, Pratap A, Agarwal S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197. DOI:10.1109/4235.996017