Simulation-based deep reinforcement learning for multi-objective identical parallel machine scheduling problem
2
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
In the shipbuilding industry, traditional optimization studies based on linear programming and constraint programming have been conducted to solve mid-term or long-term scheduling problems. However, due to the extensive computational time, these methods face limitations in addressing short-term scheduling problems for the unit production systems of shipbuilding processes, where various environmental uncertainties must be considered. This study employs a deep reinforcement learning approach to develop a dynamic scheduling algorithm for the welding process in profile shops, considering the random arrival of materials and variability in processing time. The scheduling problems of the welding process are formulated as multi-objective identical parallel machine scheduling problems, aimed at minimizing both setup time and tardiness. This study proposes a novel Markov decision process model for the multi-objective scheduling problems for the welding process, incorporating setup requirements and due date-related constraints into the state representation, action modelling, and reward design. Additionally, based on the proposed Markov decision process model, this study develops a learning environment in which a discrete-event simulation model of the welding process is integrated for state transition considering the uncertainties in the welding process. In the training phase of the scheduling agent, the Proximal Policy Optimization algorithm is applied to learn the scheduling policy, which is approximated by deep neural networks. The performance of the proposed algorithm is validated in comparison to four priority rules (SSPT, ATCS, MDD, and COVERT) for various test scenarios with different workloads and levels of variability in processing time.
Abstract
In the shipbuilding industry, traditional optimization studies based on linear programming and constraint programming have been conducted to solve mid-term or long-term scheduling problems. However, due to the extensive computational time, these methods face limitations in addressing short-term scheduling problems for the unit production systems of shipbuilding processes, where various environmental uncertainties must be considered. This study employs a deep reinforcement learning approach to develop a dynamic scheduling algorithm for the welding process in profile shops, considering the random arrival of materials and variability in processing time. The scheduling problems of the welding process are formulated as multi-objective identical parallel machine scheduling problems, aimed at minimizing both setup time and tardiness. This study proposes a novel Markov decision process model for the multi-objective scheduling problems for the welding process, incorporating setup requirements and due date-related constraints into the state representation, action modelling, and reward design. Additionally, based on the proposed Markov decision process model, this study develops a learning environment in which a discrete-event simulation model of the welding process is integrated for state transition considering the uncertainties in the welding process. In the training phase of the scheduling agent, the Proximal Policy Optimization algorithm is applied to learn the scheduling policy, which is approximated by deep neural networks. The performance of the proposed algorithm is validated in comparison to four priority rules (SSPT, ATCS, MDD, and COVERT) for various test scenarios with different workloads and levels of variability in processing time.
참고문헌 (36)
- Chaudhry, I. A., "Minimisation of total tardiness for identical parallel machine scheduling using genetic algorithm", Sadhana, 42(1), pp.11~21 (2017)[DOI]
- Chen, C. -L., "Hybrid metaheuristics for unrelated parallel machine scheduling with sequence-dependent setup times", Int. J. Adv. Des. Manuf. Technol, 43, pp.161~169 (2009)[DOI]
- Cho, Y. -i., "Locating algorithm of steel stock area with asynchronous advantage actor-critic reinforcement learning", Journal of Computational Design and Engineering, 11(1), pp.230~246 (2024)[DOI]
- Cho, Y. I., "Minimize makespan of permutation flowshop using pointer network", Journal of Computational Design and Engineering, 9(1), pp.51~67 (2022)[DOI]
- Choi, J., "Long-Term Planning Optimization System for Strategic Contracting in Shipyard", SNAME Maritime Convention (2024)
- Chun, D. -H., "Method for collision avoidance based on deep reinforcement learning with path-speed control for an autonomous ship", Int. J. Nav. Archit. Ocean Eng, 16, pp.100579~ (2024)[DOI]
- Ham, J. -H., "Actor-Critic reinforcement learning for optimal design of piping support constraint combinations", Int. J. Nav. Archit. Ocean Eng, 14, pp.100485~ (2022)[DOI]
- Jiang, X., "Exploring the performance impact of soft constraint integration on reinforcement learning-based autonomous vessel navigation : experimental insights", Int. J. Nav. Archit. Ocean Eng, 16, pp.100609~ (2024)[DOI]
- Ju, S., "Integration of long-term planning and mid-term scheduling of shipbuilding", Prod. Plann. Control, 34(6), pp.524~542 (2023)[DOI]
- Julaiti, J., "Stochastic parallel machine scheduling using reinforcement learning", Journal of Advanced Manufacturing and Processing, 4(4), pp.e10119~ (2022)[DOI]
- Kim, D. -W., "Unrelated parallel machine scheduling with setup times and a total weighted tardiness objective", Robot. Comput. Integrated Manuf, 19(1–2), pp.173~181 (2003)[DOI]
- Kwak, D. H., "Optimization of longterm planning with a constraint satisfaction problem algorithm with a machine learning", Int. J. Nav. Archit. Ocean Eng, 14, pp.100442~ (2022)[DOI]
- Lee, C. -H., "A dispatching rule and a random iterated greedy metaheuristic for identical parallel machine scheduling to minimize total tardiness", Int. J. Prod. Res, 56(6), pp.2292~2308 (2018)[DOI]
- Lee, J. -H., "A tabu search algorithm for unrelated parallel machine scheduling with sequence-and machine-dependent setups : minimizing total tardiness", Int. J. Adv. Des. Manuf. Technol, 69, pp.2081~2089 (2013)[DOI]
- Lee, Y. H., "Scheduling jobs on parallel machines with sequencedependent setup times", Eur. J. Oper. Res, 100(3), pp.464~474 (1997)[DOI]
- Li, C., "Deep reinforcement learning in smart manufacturing : a review and prospects", Cirp Journal of Manufacturing Science and Technology, 40, pp.75~101 (2023)[DOI]
- Li, F., "A two-stage RNN-based deep reinforcement learning approach for solving the parallel machine scheduling problem with due dates and family setups", J. Intell. Manuf, 35(3), pp.1107~1140 (2024)[DOI]
- Menda, K., "Deep reinforcement learning for event-driven multi-agent decision processes", IEEE Trans. Intell. Transport. Syst, 20(4), pp.1259~1268 (2018)[DOI]
- Mnih, V., "Human-level control through deep reinforcement learning", Nature, 518(7540), pp.529~533 (2015)[DOI]
- Nam, S. -H., "Development of DES Application for Factory Material Flow Simulation with SimPy", 2022 Winter Simulation Conference (WSC) (2022)
- Paeng, B., "Deep reinforcement learning for minimizing tardiness in parallel machine scheduling with sequence dependent family setups", IEEE Access, 9, pp.101390~101401 (2021)[DOI]
- Panzer, M., "Deep reinforcement learning in production systems : a systematic literature review", Int. J. Prod. Res, 60(13), pp.4316~4341 (2022)[DOI]
- Park, J., "Learning to schedule job-shop problems : representation and policy learning using graph neural network and reinforcement learning", Int. J. Prod. Res, 59(11), pp.3360~3377 (2021)[DOI]
- Roh, M. -I., "A block transportation scheduling system considering a minimisation of travel distance without loading of and interference between multiple transporters", Int. J. Prod. Res, 49(11), pp.3231~3250 (2011)[DOI]
- "High-dimensional continuous control using generalized advantage estimation" (2015)[URL]
- "Proximal policy optimization algorithms" (2017)[URL]
- Shakya, A. K., "Reinforcement learning algorithms : a brief survey", Expert Syst. Appl, 231, pp.120495~ (2023)[DOI]
- Son, J. -R., "A heuristic algorithm for block storage planning in shipbuilding", Journal of the Society of Naval Architects of Korea, 51(3), pp.239~245 (2014)[DOI]
- Stricker, N., "Reinforcement learning for adaptive order dispatching in the semiconductor industry", CIRP Annals, 67(1), pp.511~514 (2018)[DOI]
- Tao, N. -R., "Spatial scheduling and workforce assignment problem in block assembly shop of shipbuilding", Asia Pac. J. Oper. Res, 31(1), pp.1450006~ (2014)[DOI]
- Woo, J. H., "Development of a Reinforcement Learning-Based Adaptive Scheduling Algorithm for Block Assembly Production Line", 2021 Winter Simulation Conference (WSC) (2021)
- Yang, Z., "A multi-objective memetic algorithm for a fuzzy parallel blocking flow shop scheduling problem of panel block assembly in shipbuilding", Journal of ship production and design, 35(2), pp.170~181 (2019)[DOI]
- Yeo, S. -J., "Deep-reinforcement-learning-based hull form optimization method for stealth submarine design", Int. J. Nav. Archit. Ocean Eng, 16, pp.100595~ (2024)[DOI]
- Yuan, B., "Dynamic parallel machine scheduling with random breakdowns using the learning agent", Int. J. Serv. Oper. Inf, 8(2), pp.94~103 (2016)[DOI]
- Zhang, Z., "Minimizing mean weighted tardiness in unrelated parallel machine scheduling with reinforcement learning", Comput. Oper. Res, 39(7), pp.1315~1324 (2012)[DOI]
- Zhang, Z., "Dynamic parallel machine scheduling with mean weighted tardiness objective by Q-Learning", Int. J. Adv. Des. Manuf. Technol, 34, pp.968~980 (2007)[DOI]