Solving a Real-Life Stochastic Car Batching and Sequencing Problem With Dynamic Programming Approaches

This paper addresses a real-life stochastic car batching and sequencing problem in the body shop of a vehicle plant. Unlike previous research on similar problems in the paint shop or assembly shop, our problem primarily focuses on production planning in the body shop, with specific constraints on the production sequence (e.g., the bodies of each model cannot be produced individually but must be produced in batches of a specific size) and considers the impact of sampling inspection. Solving this large-scale car batching and sequencing problem in the body shop within an acceptable computation time is challenging. In this paper, several efficient dynamic programming-based algorithms are designed to solve the problem. First, a dynamic programming model is established for the deterministic version of the problem, and the optimal solution can be obtained by the dynamic programming approach. Furthermore, faced with the uncertainty introduced by sampling inspection, a more difficult and practical stochastic car batching and sequencing problem is modeled as a discrete-time Markov decision process. A rollout method-based approximate dynamic programming algorithm is designed to solve this complex problem. Finally, the proposed algorithms’ effectiveness is examined using real-life production data.
Note to Practitioners
—This paper is motivated by our collaboration with a vehicle production plant in Shanghai, China. The plant mainly produces 3
$\sim$
4 electrified models, with an annual output of up to 300,000 units/year. The plant consists of three workshops: the body shop, the paint shop, and the assembly shop. A multi-model flexible production line has been set up in the body shop. In practice, as multiple models are produced on the production line simultaneously, the plant adopts a mode of batch production to batch and sequence the bodies to be produced. Due to the specialty of the batch production mode and the uncertainty brought by the sampling inspection, the stochastic car batching and sequencing problem in the body shop presents a challenge to the plant. This paper proposes dynamic programming and approximate dynamic programming algorithms to effectively solve this stochastic optimization problem. The numerical experiments show the proposed algorithms can solve large-scale problems with near-optimal solutions within a reasonable time span. The algorithm can assist decision-makers in determining the batch size and the production sequence in automobile manufacturing enterprises.