J Shanghai Jiaotong Univ Sci

Journal of Shanghai Jiaotong University(Science) >

2026 , Vol. 31 >Issue 4: 1057 - 1070

DOI: https://doi.org/10.1007/s12204-024-2763-7

Automation & Computer Technologies

Unrelated Parallel-Machine Scheduling Problem with Time-Changing Effects and Dynamic Job Arrivals

Expand
  • School of Mechanical Engineering, Shanghai Jiao Tong University, Shanghai 200240, China

Received date: 2023-12-20

  Accepted date: 2024-03-29

  Online published: 2026-07-22

Fold

Abstract

With machine deterioration, time-changing effects are observed in the ion implantation work center of wafer fabrication. Furthermore, jobs arrive in a dynamic pattern. A mixed integer stochastic programming model is formulated to address the unrelated parallel-machine scheduling problem at the work center. The objective is to minimize the average flow time of wafers. Time-changing effects and dynamic job arrivals are considered simultaneously. A genetic algorithm with a reinforcement learning procedure(GA-RL) is developed to solve real-size problems. The reinforcement learning procedure aims to determine the optimal confidence levels during the search for the best solution. Computational analyses demonstrate the efficiency of the GA-RL. Sensitivity analyses provide valuable managerial insights into actual production processes.

Cite this article

Guan Zhicheng, Zhang Xinying, Chen Lu . Unrelated Parallel-Machine Scheduling Problem with Time-Changing Effects and Dynamic Job Arrivals[J]. Journal of Shanghai Jiaotong University(Science), 2026 , 31(4) : 1057 -1070 . DOI: 10.1007/s12204-024-2763-7

References

[1] STRUSEVICH V A, RUSTOGI K. Scheduling with time-changing effects and rate-modifying activities [M]. Cham: Springer, 2017.
[2] CHENG T C E, SIN C C S. A state-of-the-art review of parallel-machine scheduling research [J]. European Journal of Operational Research, 1990, 47(3): 271-292.
[3] MOKOTOFF E. Parallel machine scheduling problems: A survey [J]. Asia-Pacific Journal of Operational Research, 2001, 18(2): 193-242.
[4] EDIS E B, OGUZ C, OZKARAHAN I. Parallel machine scheduling with additional resources: Notation, classification, models and solution methods [J]. European Journal of Operational Research, 2013, 230(3): 449-463.
[5] 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.
[6] DETTI P, NICOSIA G, PACIFICI A, et al. Robust single machine scheduling with a flexible maintenance activity [J]. Computers & Operations Research, 2019, 107: 19-31.
[7] LUO W C, CHENG T C E, JI M. Single-machine scheduling with a variable maintenance activity [J]. Computers & Industrial Engineering, 2015, 79: 168-174.
[8] JIANG C L, LU Z Q, CUI W W. Heuristics for the identical machine scheduling problem with preventive maintenances [J]. Journal of Shanghai Jiao Tong University (Science), 2016, 21(1): 112-120.
[9] 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 & Operations Research, 2010, 37(8): 1510-1514.
[10] YANG L Y, LU X W. Two-agent scheduling problems with the general position-dependent processing time [J]. Theoretical Computer Science, 2019, 796: 90-98.
[11] RUIZ-TORRES A J, PALETTA G, PÉREZ E. Parallel machine scheduling to minimize the makespan with sequence dependent deteriorating effects [J]. Computers & Operations Research, 2013, 40(8): 2051-2061.
[12] DING J W, SHEN L J, LÜ Z P, et al. Parallel machine scheduling with completion-time-based criteria and sequence-dependent deterioration [J]. Computers & Operations Research, 2019, 103: 35-45.
[13] ALIDAEE B, WOMER N K. Scheduling with time dependent processing times: Review and extensions [J]. Journal of the Operational Research Society, 1999, 50(7): 711-720.
[14] 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.
[15] TANG L X, ZHAO X L, LIU J Y, 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.
[16] GAO Y, YUAN J 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.
[17] CHEN R B, YUAN J J, GENG Z C. ND-agent scheduling of linear-deteriorating tasks with positional due indices to minimize total completion time and maximum cost [J]. Applied Mathematics and Computation, 2020, 365: 124697.
[18] CHEN Q Q, LIN L, TAN Z Y, et al. Coordination mechanisms for scheduling games with proportional deterioration [J]. European Journal of Operational Research, 2017, 263(2): 380-389.
[19] LU S J, LIU X B, 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.
[20] CHENG T C E, KRAVCHENKO S A, LIN B M T. Scheduling step-deteriorating jobs to minimize the total completion time [J]. Computers & Industrial Engineering, 2020, 144: 106329.
[21] LALLA-RUIZ E, VOß S. Modeling the parallel machine scheduling problem with step deteriorating jobs [J]. European Journal of Operational Research, 2016, 255(1): 21-33.
[22] KUO W H, YANG D L. Single-machine scheduling problems with start-time dependent processing time [J]. Computers & Mathematics with Applications, 2007, 53(11): 1658-1664.
[23] ZHAO C L, TANG H Y. Single machine scheduling with past-sequence-dependent setup times and deteriorating jobs [J]. Computers & Industrial Engineering, 2010, 59(4): 663-666.
[24] HUANG X, WANG J J. Machine scheduling problems with a position-dependent deterioration [J]. Applied Mathematical Modelling, 2015, 39(10/11): 2897-2908.
[25] ZHANG X Y, CHEN L, YANG W H. A parallel-machine scheduling problem with time-changing effect and preventive maintenance[J]. Journal of Zhejiang University (Engineering Science), 2022, 56(2): 408-418 (in Chinese).
[26] ZHOU S C, JIN M Z, DU N. Energy-efficient scheduling of a single batch processing machine with dynamic job arrival times [J]. Energy, 2020, 209: 118420.
[27] YAO F S, ZHAO M, ZHANG H. Two-stage hybrid flow shop scheduling with dynamic job arrivals [J]. Computers & Operations Research, 2012, 39(7): 1701-1712.
[28] WANG Z, ZHANG J H, YANG S X. An improved particle swarm optimization algorithm for dynamic job shop scheduling problems with random job arrivals [J]. Swarm and Evolutionary Computation, 2019, 51: 100594.
[29] CALDEIRA R H, GNANAVELBABU A, VAIDYANATHAN T. An effective backtracking search algorithm for multi-objective flexible job shop scheduling considering new job arrivals and energy consumption [J]. Computers & Industrial Engineering, 2020, 149: 106863.
[30] LI Y F, HE Y, WANG Y L, et al. An optimization method for energy-conscious production in flexible machining job shops with dynamic job arrivals and machine breakdowns [J]. Journal of Cleaner Production, 2020, 254: 120009.
[31] ZAROOK Y, REZAEIAN J, MAHDAVI I, et al. Efficient algorithms to minimize makespan of the unrelated parallel batch-processing machines scheduling problem with unequal job ready times [J]. RAIRO - Operations Research, 2021, 55(3): 1501-1522.
[32] AN Y J, CHEN X H, GAO K Z, et al. Multiobjective flexible job-shop rescheduling with new job insertion and machine preventive maintenance [J]. IEEE Transactions on Cybernetics, 2023, 53(5): 3101-3113.
[33] ZHANG H K, BUCHMEISTER B, LI X Y, et al. An efficient metaheuristic algorithm for job shop scheduling in a dynamic environment [J]. Mathematics, 2023, 11(10): 2336.
[34] SUN Z Y, HAN W M, GAO L L. Real-time scheduling for dynamic workshops with random new job insertions by using deep reinforcement learning [J]. Advances in Production Engineering & Management, 2023, 18(2): 137-151.
[35] YANG S L, WANG J Y, XU Z G. Real-time scheduling for distributed permutation flowshops with dynamic job arrivals using deep reinforcement learning [J]. Advanced Engineering Informatics, 2022, 54: 101776.
[36] CHOLETTE M E, CELEN M, DJURDJANOVIC D, et al. Condition monitoring and operational decision making in semiconductor manufacturing [J]. IEEE Transactions on Semiconductor Manufacturing, 2013, 26(4): 454-464.
[37] WALTZ M, FU K. A heuristic approach to reinforcement learning control systems [J]. IEEE Transactions on Automatic Control, 1965, 10(4): 390-398.
[38] NIAN R, LIU J F, HUANG B. A review On reinforcement learning: Introduction and applications in industrial process control [J]. Computers & Chemical Engineering, 2020, 139: 106886.
[39] WATKINS C J C H, DAYAN P. Q-learning [J]. Machine Learning, 1992, 8(3): 279-292.
[40] ZHANG Z C, ZHENG L, LI N, et al. Minimizing mean weighted tardiness in unrelated parallel machine scheduling with reinforcement learning [J]. Computers & Operations Research, 2012, 39(7): 1315-1324.

Options
Outlines

/

〈 〉