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

作者：Liao Ching Jong; Lee Cheng Hsiung^*; Lee Hong Chieh

来源：COMPUTERS & INDUSTRIAL ENGINEERING, 2015, 88: 317-325.

DOI：10.1016/j.cie.2015.07.018

• Scheduling
• Two-stage assembly
• Setup times
• Common components

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.

• 出版日期2015-10