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.
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.
Fig.1Relationship between actual processing time of a lot and machine reliability
Fig.2An optimal schedule of example
Fig.3Flow chart of learnable genetic algorithm
Fig.4Job exchange operations
Fig.5Chromosome representation
Fig.6Knowledge 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.1Sensitivity 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.2Parameters 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.3Comparison 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.4Comparison for optimization results of three algorithms
Fig.7Comparison 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.5Characteristic of job sets
Fig.8Impact of characteristic of job sets on scheduling
Fig.9Impact 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