Paint batching problem on M-to-1 conveyor systems

An M-to-1 conveyor system consists of multiple upstream conveyors and a single downstream conveyor. In this paper, we investigate the paint batching problem on M-to-1 conveyor systems with the objective of minimizing setup costs. Our research is motivated by a vehicle re-sequencing problem at a major Korean automotive manufacturer. Setup costs are incurred when two consecutive jobs in the downstream conveyor do not share the same feature. Re-sequencing flexibility is limited by the precedence relationship among jobs in the upstream conveyors. First, we develop a mixed integer linear programming model and propose an efficient dynamic programming (DP) algorithm for a 2-to-1 conveyor system. However, because the suggested DP cannot guarantee optimality in general settings, we propose two efficient genetic algorithms (GAs) to find near optimal solutions. Specifically, we design the reordering operation for making offspring to satisfy the precedence condition. We show that the proposed GAs perform prominently with respect to optimality gap and computation time; thus, they are amenable to environments where solutions must be obtained within tight time constraints.