Please wait a minute...
浙江大学学报(工学版)
Journal of ZheJiang University (Engineering Science)  2022, Vol. 56 Issue (2): 408-418    DOI: 10.3785/j.issn.1008-973X.2022.02.022
    
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
Download: HTML     PDF(1420KB) HTML
Export: BibTeX | EndNote (RIS)      

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     
Received: 24 March 2021      Published: 03 March 2022
CLC:  F 406  
Corresponding Authors: Lu CHEN     E-mail: zxysjtu@sjtu.edu.cn;chenlu@sjtu.edu.cn
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Xin-ying ZHANG
Lu CHEN
Wen-hui YANG
Cite this article:

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.

URL:

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


考虑系统时变效应与预防性维护的平行机调度

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


关键词： 平行机调度,  可靠性,  时变效应,  预防性维护,  学习型遗传算法 
Fig.1 Relationship between actual processing time of a lot and machine reliability
Fig.2 An optimal schedule of example
Fig.3 Flow chart of learnable genetic algorithm
Fig.4 Job exchange operations
Fig.5 Chromosome representation
Fig.6 Knowledge base for preventive maintenance
工作种类 $ {\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 ? ?
Tab.1 Sensitivity factors for different job families
参数 取值 参数 取值
$ {\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
Tab.2 Parameters setting for scheduling and algorithm
|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
Tab.3 Comparison for Lingo and 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
Tab.4 Comparison for optimization results of three algorithms
Fig.7 Comparison of convergence curves of three algorithms
待加工
工件集合 		$ \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
Tab.5 Characteristic of job sets
Fig.8 Impact of characteristic of job sets on scheduling
Fig.9 Impact of PM type on scheduling decision
[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] Xi-ran ZHANG,Shao-kuan CHEN,Bo WANG,Shuang LIU,Zhuo WANG. Emergency allocation optimization model considering reliability of replaceable rescue[J]. Journal of ZheJiang University (Engineering Science), 2021, 55(1): 20-30.
[2] Ge-hui LIU,Shao-kuan CHEN,Hua JIN,Shuang LIU,Hong-qin PENG. Optimum imperfect inspection and maintenance scheduling model considering delay time theory[J]. Journal of ZheJiang University (Engineering Science), 2020, 54(7): 1298-1307.
[3] Li LONG,Shan-suo ZHENG,Yan ZHOU,Jin-chuan HE,Hong-li MENG,Yong-long CAI. Parallel study of seismic reliability analysis of water supply pipe network based on quasi-Monte Carlo method[J]. Journal of ZheJiang University (Engineering Science), 2020, 54(2): 241-247.
[4] Xing-bo HAN,Yong-xu XIA,Yong-dong WANG,Fei YE. Probabilistic degradation model for tunnel lining flexural capacity[J]. Journal of ZheJiang University (Engineering Science), 2019, 53(11): 2175-2184.
[5] ZHANG Hang, LI Hong-shuang. Structural reliability analysis with LCVT-SVR method[J]. Journal of ZheJiang University (Engineering Science), 2018, 52(10): 2035-2042.
[6] WU Ke-xian, JIN Wei-liang, XIA Jin. Influence of load partial factors adjustment on design of masonry structures[J]. Journal of ZheJiang University (Engineering Science), 2018, 52(10): 1901-1910.
[7] QI Xiao-gang, WANG Zhen-yu, LIU Li-fang, LIU Xing-cheng, MA Jiu-long. Reliable and efficient routing of wireless sensors and actuator networks[J]. Journal of ZheJiang University (Engineering Science), 2018, 52(10): 1964-1972.
[8] WANG Wei, WANG Jin, LU Guo-dong. Reliability analysis of manipulator based on fourth-moment estimation[J]. Journal of ZheJiang University (Engineering Science), 2018, 52(1): 1-7.
[9] LI Bing, JIN Tao, CHEN Shuai. Method to improve reliability of SRAM PUFs key generation[J]. Journal of ZheJiang University (Engineering Science), 2018, 52(1): 133-141.
[10] SU Xing, WANG Hui-quan, JIN Zhong-he. Logical architecture design of integrated electronic system with high real-time and reliability in ZDPS-2 pico-satellite[J]. Journal of ZheJiang University (Engineering Science), 2017, 51(3): 628-636.
[11] XIAO Xin hui, LU Nai wei, LIU Yang. Fatigue reliability assessment for highway steel bridges under stochastic traffic flow[J]. Journal of ZheJiang University (Engineering Science), 2016, 50(9): 1777-1783.
[12] 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.
[13] LU Nai wei, LUO Yuan, WANG Qin yong, Noori Mohammad. Dynamic reliability assessment for long-span bridges under vehicle load[J]. Journal of ZheJiang University (Engineering Science), 2016, 50(12): 2328-2335.
[14] LI Qing, HU Zhi hua. Reliable path selection after disaster based on multi objective genetic algorithm[J]. Journal of ZheJiang University (Engineering Science), 2016, 50(1): 33-40.
[15] LIU Yang, LU Nai wei, JIANG You bao. Adaptive support vector regression method for structural system reliability analysis[J]. Journal of ZheJiang University (Engineering Science), 2015, 49(9): 1692-1699.