Mathematical modeling and heuristic approaches for a multi-stage car sequencing problem

Abstract This paper addresses the scheduling problem in three successive processes in car production including the paint shop, painted body storage (PBS) and the assembly shop. The paint shop, which aims to reduce the costs for color changes, is connected to the final assembly shop, which aims to level the usage of the options. A linear PBS is set in between to change the sequence from the upstream shop to the downstream shop. The joint sequencing problem is formulated as a mixed integer linear programming (MILP) model and some properties including the lower bounds are presented. A structural architecture is designed to solve the large-scale real-life instances, and several meta-heuristic algorithms are embedded in the architecture to enhance the ability of finding good solutions. Numerical experiments validate the quality of the proposed algorithms.