An efficient heuristic for a two-stage assembly scheduling problem with batch setup times to minimize makespan

• This paper presents a two-stage assembly scheduling problem from a motor factory.
• We develop several properties and a lower bound for the two-stage assembly problem.
• The proposed constructive heuristic outperforms the current scheduling method.
• The proposed heuristic can obtain a near optimal solution in almost zero time.

This paper considers a two-stage assembly scheduling problem of N products with setup times to minimize the makespan. In this problem, there is a machining machine which produces components in the first stage. When the required components are available, a single assembly machine can assemble these components into products in the second stage. A setup time is needed whenever the machining machine starts processing components, or the item of component is switched on the machine. The problem is formulated as a mixed integer programming model, and several properties for finding optimal solutions are developed. Moreover, an efficient heuristic based on these optimal properties is proposed. A lower bound is derived to evaluate the performance of the proposed heuristic. Computational results show that the proposed heuristic can obtain a near optimal solution in almost zero time and the average percentage deviation is only 0.478.