In this paper, a car resequencing problem (CRP) for automotive paint shops is considered, whereby a set of cars conveyed from an upstream shop to one of the multiple conveyors is retrieved sequentially before the painting operation. The aim of the CRP is to find a car retrieval sequence that minimizes the sequence-dependent changeover cost, which is the cost that is incurred when two consecutive cars do not share the same color. For this problem, we propose accelerated dynamic programming (ADP) algorithms that utilize strong combinatorial lower bounds and effective upper bounds in a standard dynamic programming framework, thus outperforming existing exact algorithms. Testing of our algorithms over a wide range of instances confirmed that they are more efficient than the existing approaches and are also more applicable in practice.
This work was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education ( NRF-2015R1D1A1A01057719 ). The authors would like to thank the authors of [6] for kindly providing us with their GA-based heuristic code for our computational tests. The authors also would like to thank the editors and anonymous referees for their constructive and helpful comments.
