Simulation-based deep reinforcement learning for multi-objective identical parallel machine scheduling problem

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.

Keywords

• Parallel machine scheduling problem
• Deep reinforcement learning
• Discrete-event simulation
• Proximal policy optimization