Please wait a minute...
浙江大学学报(工学版)
浙江大学学报(工学版)  2022, Vol. 56 Issue (2): 408-418    DOI: 10.3785/j.issn.1008-973X.2022.02.022
机械工程     
考虑系统时变效应与预防性维护的平行机调度
张昕莹(),陈璐*(),杨雯惠
上海交通大学 工业工程与管理系，上海 200240
A parallel-machine scheduling problem with time-changing effect and preventive maintenance
Xin-ying ZHANG(),Lu CHEN*(),Wen-hui YANG
Department of Industrial Engineering and Management, Shanghai Jiao Tong University, Shanghai 200240, China
 全文: PDF(1420 KB)   HTML
摘要：

实施预防性维护(PM)能改善晶圆制造厂离子注入工序中设备状态从而改善晶圆卡（lot）加工时间延长的问题，基于此，研究考虑系统时变效应与预防性维护的平行机调度问题. 以最小化最大完工时间为优化目标，建立包括设备可靠性以及工件实际加工时间约束的数学非线性规划模型. 设计求解该模型的学习型遗传算法(LGA)，针对问题特性引入最优支配规则改进变异操作，构建预防性维护知识库指导进化后期预防性维护决策，以提升算法质量. 算例实验结果表明，改进的学习型遗传算法能有效应对系统时变效应对生产调度的影响，减少最大完工时间，具有实用价值. 通过灵敏度分析实验研究晶圆卡对设备状态衰退的敏感程度和预防性维护对调度决策的影响，为实际车间调度提供决策支持.
关键词： 平行机调度;  可靠性;  时变效应;  预防性维护;  学习型遗传算法    
Abstract:

A parallel-machine scheduling problem with time-changing effect and preventive maintenance was studied based on the fact that preventive maintenance (PM) could restore machine condition in the ion implantation process in a wafer fab thus reducing the prolongation of the wafer processing time. A mathematical nonlinear programming model including the machine reliability constraints and the actual job processing time constraints was developed with the objective to minimize the makespan. The learnable genetic algorithm (LGA) was designed to solve the problem. According to the characteristics of the problem, dominance properties were embedded into the LGA to improve the mutation operation and the PM knowledge base was constructed to guide the later stage of evolution to improve the search performance. Computational analyses demonstrate that LGA can effectively deal with the impact of time-changing effect on scheduling, and reduce the makespan. Sensitivity analyses provide valuable information about the impact of job’s dependency on machine deterioration and types of PM on scheduling, which provides decision supports for the real workshop.
Key words: parallel-machine scheduling    reliability    time-changing effect    preventive maintenance    learnable genetic algorithm
收稿日期: 2021-03-24 出版日期: 2022-03-03
CLC:  F 406  
基金资助: 国家自然科学基金资助项目（51775347）
通讯作者: 陈璐     E-mail: zxysjtu@sjtu.edu.cn;chenlu@sjtu.edu.cn
作者简介: 张昕莹（1997—），女，硕士生，从事生产调度方向研究. orcid.org/0000-0002-5685-0368. E-mail: zxysjtu@sjtu.edu.cn
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
作者相关文章　　
张昕莹
陈璐
杨雯惠

引用本文:

张昕莹,陈璐,杨雯惠. 考虑系统时变效应与预防性维护的平行机调度[J]. 浙江大学学报(工学版), 2022, 56(2): 408-418.

Xin-ying ZHANG,Lu CHEN,Wen-hui YANG. A parallel-machine scheduling problem with time-changing effect and preventive maintenance. Journal of ZheJiang University (Engineering Science), 2022, 56(2): 408-418.

链接本文:

https://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2022.02.022    或    https://www.zjujournals.com/eng/CN/Y2022/V56/I2/408

图 1  晶圆卡的实际加工时间与设备可靠性的关系
图 2  示例的最优调度序列
图 3  学习型遗传算法流程图
图 4  工件交换操作
图 5  染色体编码方式
图 6  预防性维护知识库示意图
工作种类 $ {\alpha }_{j} $ 工作种类 $ {\alpha }_{j} $
1 1.0 6 0.5
2 0.9 7 0.2
3 0.9 8 0.1
4 0.6 9 0.1
5 0.6 ? ?
表 1  不同种类工件对应的敏感性因子
参数 取值 参数 取值
$ {\bar{p}}_{i,j} $/min N(20, 0.32) $ \theta $ 0.58
$ {S}_{{f}_{h},{f}_{j}} $/min U(38, 78) $ {N}_{\mathrm{p}\mathrm{o}\mathrm{p}} $ 50
$ {r}_{{\rm{th}}1} $ 0.7 ${P}_{\mathrm{c} }$ 0.8
$ {r}_{{\rm{th}}2} $ 0.4 ${P}_{\mathrm{m} }$ 0.1
$ \lambda $ 0.00035 $ {G}_{\mathrm{m}\mathrm{a}\mathrm{x}} $ 400
$ w $ 2 ${P}_{ {\rm{o} } }$ 0.2
$ {L}_{i,1}^{0} $/min {0, 1000, 1500, 2000} ${P}_{ {\rm{o} } }'$ 0.3
T/min 30 d 12
表 2  调度和算法参数设置
|N| Lingo LGA Dev/%
$C_{\max }^{{\rm{Lingo}}} $/min tCPU/s $C_{\max }^{{\rm{Lingo}}} $/min tCPU/s
5 78.76 25.4 78.76 1.12 0.00
6 88.54 80.6 88.54 1.02 0.00
7 88.55 1884.4 88.55 1.20 0.00
8 96.54 3600.0 94.62 1.27 1.95
9 116.62 3600.0 112.83 1.27 3.25
10 126.85 3600.0 120.10 1.30 5.33
11 128.00 3600.0 117.38 1.27 8.32
12 153.87 3600.0 136.60 1.21 11.21
表 3  Lingo与LGA性能比较
|N| LGA SGA DABC
Cmax/min tCPU/s Cmax/min tCPU/s Cmax/min tCPU/s
50 373.59 1.70 381.14 1.44 385.01 1.49
100 648.25 2.25 658.17 1.97 671.10 2.14
150 909.69 2.83 923.31 2.46 937.58 2.76
200 1171.71 3.64 1192.94 3.03 1212.75 3.38
250 1429.64 4.36 1454.86 3.65 1493.26 4.15
300 1696.91 5.44 1743.19 4.80 1789.49 5.38
表 4  3种算法获得的最优解比较
图 7  3种算法的收敛曲线对比图
待加工
工件集合 		$ \phi $/%
$ {\alpha }_{j} $=1.0 或 0.9 $ {\alpha }_{j} $=0.6 或 0.5 $ {\alpha }_{j} $=0.2 或 0.1
高敏感性 80 10 10
中敏感性 10 80 10
低敏感性 10 10 80
表 5  待加工工件集合特性
图 8  待加工工件集合特性对调度决策的影响
图 9  PM类型对调度决策的影响
1 何科峰 浅谈离子注入机的维护[J]. 中国科技信息, 2013, (18): 137
HE Ke-feng Maintenance of ion implanter[J]. China Science and Technology Information, 2013, (18): 137
doi: 10.3969/j.issn.1001-8972.2013.18.082
2 周炳海, 刘子龙 考虑质量损失的退化系统维护建模[J]. 浙江大学学报: 工学版, 2016, 50 (12): 2270- 2276
ZHOU Bing-hai, LIU Zi-long Maintenance modeling for deteriorating system considering quality loss[J]. Journal of Zhejiang University: Engineering Science, 2016, 50 (12): 2270- 2276
3 曹健 离子注入技术与设备常见故障分析[J]. 电子工业专用设备, 2015, 44 (5): 25- 29
CAO Jian Ion implantation technology and equipment of common fault analysis[J]. Equipment for Electronic Products Manufacturing, 2015, 44 (5): 25- 29
doi: 10.3969/j.issn.1004-4507.2015.05.006
4 PACHECO J, PORRAS S, CASADO S, et al Variable neighborhood search with memory for a single-machine scheduling problem with periodic maintenance and sequence-dependent set-up times[J]. Knowledge-based Systems, 2018, 145: 236- 249
doi: 10.1016/j.knosys.2018.01.018
5 NAJAT A, YUAN C, GURSEL S, et al Minimizing the number of tardy jobs on identical parallel machines subject to periodic maintenance[J]. Procedia Manufacturing, 2019, 38: 1409- 1416
doi: 10.1016/j.promfg.2020.01.147
6 XU D, SUN K, LI H Parallel machine scheduling with almost periodic maintenance and non-preemptive jobs to minimize makespan[J]. Computers and Operations Research, 2008, 35 (4): 1344- 1349
doi: 10.1016/j.cor.2006.08.015
7 LI G, LIU M, SETHI S P, et al Parallel-machine scheduling with machine-dependent maintenance periodic recycles[J]. International Journal of Production Economics, 2017, 186: 1- 7
doi: 10.1016/j.ijpe.2017.01.014
8 DETTI P, NICOSIA G, PACIFICI A, et al Robust single machine scheduling with a flexible maintenance activity[J]. Computers and Operations Research, 2019, 107: 19- 31
doi: 10.1016/j.cor.2019.03.001
9 YOO J, LEE I S Parallel machine scheduling with maintenance activities[J]. Computers and Industrial Engineering, 2016, 101: 361- 371
doi: 10.1016/j.cie.2016.09.020
10 LEI D, LIU M An artificial bee colony with division for distributed unrelated parallel machine scheduling with preventive maintenance[J]. Computers and Industrial Engineering, 2020, 141: 106320
doi: 10.1016/j.cie.2020.106320
11 杨新宇, 胡业发 不确定环境下复杂产品维护、维修和大修服务资源调度优化[J]. 浙江大学学报:工学版, 2019, 53 (5): 852- 861
YANG Xin-yu, HU Ye-fa Maintenance, repair and overhaul/operations service resource scheduling optimization for complex products in uncertain enviroment[J]. Journal of Zhejiang University: Engineering Science, 2019, 53 (5): 852- 861
12 LIU Q, DONG M, CHEN F F, et al Single-machine-based joint optimization of predictive maintenance planning and production scheduling[J]. Robotics and Computer-Integrated Manufacturing, 2019, 55: 173- 182
doi: 10.1016/j.rcim.2018.09.007
13 LU Z, CUI W, HAN X Integrated production and preventive maintenance scheduling for a single machine with failure uncertainty[J]. Computers and Industrial Engineering, 2015, 80: 236- 244
doi: 10.1016/j.cie.2014.12.017
14 DUFFUAA S, KOLUS A, AL-TURKI U, et al An integrated model of production scheduling, maintenance and quality for a single machine[J]. Computers and Industrial Engineering, 2020, 142: 106239
doi: 10.1016/j.cie.2019.106239
15 YANG S J, YANG D L, CHENG T C E Single-machine due-window assignment and scheduling with job-dependent aging effects and deteriorating maintenance[J]. Computers and Operations Research, 2010, 37 (8): 1510- 1514
doi: 10.1016/j.cor.2009.11.007
16 YANG L, LU X Two-agent scheduling problems with the general position-dependent processing time[J]. Theoretical Computer Science, 2019, 796: 90- 98
doi: 10.1016/j.tcs.2019.08.023
17 RUIZ-TORRES A J, PALETTA G, PéREZ E Parallel machine scheduling to minimize the makespan with sequence dependent deteriorating effects[J]. Computers and Operations Research, 2013, 40 (8): 2051- 2061
doi: 10.1016/j.cor.2013.02.018
18 WANG T, BALDACCI R, LIM A, et al A branch-and-price algorithm for scheduling of deteriorating jobs and flexible periodic maintenance on a single machine[J]. European Journal of Operational Research, 2018, 271 (3): 826- 838
doi: 10.1016/j.ejor.2018.05.050
19 GAO Y, YUAN J, NG C T, et al A further study on two-agent parallel-batch scheduling with release dates and deteriorating jobs to minimize the makespan[J]. European Journal of Operational Research, 2019, 273 (1): 74- 81
doi: 10.1016/j.ejor.2018.07.040
20 TANG L, ZHAO X, LIU J, et al Competitive two-agent scheduling with deteriorating jobs on a single parallel-batching machine[J]. European Journal of Operational Research, 2017, 263 (2): 401- 411
doi: 10.1016/j.ejor.2017.05.019
21 LU S, LIU X, PEI J, et al A hybrid ABC-TS algorithm for the unrelated parallel-batching machines scheduling problem with deteriorating jobs and maintenance activity[J]. Applied Soft Computing, 2018, 66: 168- 182
doi: 10.1016/j.asoc.2018.02.018
22 ZHAO C, TANG H Single machine scheduling with past-sequence-dependent setup times and deteriorating jobs[J]. Computers and Industrial Engineering, 2010, 59 (4): 663- 666
doi: 10.1016/j.cie.2010.07.015
[1] 龙立,郑山锁,周炎,贺金川,孟宏立,蔡永龙. 基于拟蒙特卡罗方法的供水管网抗震可靠性分析并行化研究[J]. 浙江大学学报(工学版), 2020, 54(2): 241-247.
[2] 张航, 李洪双. 结构可靠性分析的LCVT-SVR方法[J]. 浙江大学学报(工学版), 2018, 52(10): 2035-2042.
[3] 齐小刚, 王振宇, 刘立芳, 刘兴成, 马久龙. 无线传感器和执行器网络可靠高效路由[J]. 浙江大学学报(工学版), 2018, 52(10): 1964-1972.
[4] 王伟, 王进, 陆国栋. 基于四阶矩估计的机器人运动可靠性分析[J]. 浙江大学学报(工学版), 2018, 52(1): 1-7.
[5] 李冰, 金涛, 陈帅. 提高SRAM PUFs密钥生成可靠性的方法[J]. 浙江大学学报(工学版), 2018, 52(1): 133-141.
[6] 苏星, 王慧泉, 金仲和. 实时高可靠综合电子系统的逻辑架构设计[J]. 浙江大学学报(工学版), 2017, 51(3): 628-636.
[7] 周炳海, 刘子龙. 考虑质量损失的退化系统维护建模[J]. 浙江大学学报(工学版), 2016, 50(12): 2270-2276.
[8] 李清,胡志华. 基于多目标遗传算法的灾后可靠路径选择[J]. 浙江大学学报(工学版), 2016, 50(1): 33-40.
[9] 蒋正文, 万水, 李明鸿, 马磊. 结构可靠度分析中的混合模拟法及应用[J]. 浙江大学学报(工学版), 2015, 49(4): 782-791.
[10] 何忠华,袁一星. 基于剩余能量熵的供水管网可靠性优化设计[J]. 浙江大学学报(工学版), 2014, 48(7): 1188-1194.
[11] 杨文彬, 胡军科, 王子坡. 两级双向液压同步控制系统动态特性仿真[J]. 浙江大学学报(工学版), 2014, 48(6): 1107-1113.
[12] 宁志华,何乐年,胡志成. 一种高压高可靠性开关电源控制芯片[J]. J4, 2014, 48(3): 377-383.
[13] 崔磊, 何勇, 金伟良. 不同海域Semi平台关键节点的疲劳可靠性分析[J]. J4, 2013, 47(8): 1329-1337.
[14] 林晓华, 冯毅雄, 谭建荣. 基于免疫优化的产品系统可靠性参数区间预测方法[J]. J4, 2013, 47(6): 1013-1021.
[15] 潘竹生, 莫毓昌. 冗余可修系统的可靠性分析[J]. J4, 2013, 47(4): 644-649.