Optimal cyclic scheduling of a hoist and multi-type parts with fixed processing times

Abstract

This paper proposes an exact algorithm to solve a cyclic hoist scheduling problem in a printed circuit board (PCB) electroplating facility, where multi-type parts with fixed processing times are processed in the same time and the parts are not allowed to wait in the tanks or on the hoist. Finding an optimal schedule in such a production line is equivalent to finding two types of related sequences: part input sequence and hoist move sequence. We show that the entering times of the parts are the decision variables of the problem. We formulate our problem using the notion of prohibited intervals and solve it by enumerating the non-prohibited intervals of the decision variables. This enumeration is accomplished more efficiently with a dynamic branch and bound procedure, which utilises relaxed solutions to eliminate redundant non-prohibited intervals in the search process. The proposed algorithm is polynomial in the number of tanks if the number of part types is fixed, but exponential if it is arbitrary. Computational results on randomly generated test instances indicate that the algorithm is effective.

Keywords:

• cyclic hoist scheduling
• multi-type parts
• fixed processing times
• no-wait
• branch and bound algorithm

Acknowledgements

This work was partially supported by the National Natural Science Foundation of China, under grant No. 50605052 and the Program for New Century Excellent Talents in Universities of Ministry of Education, China, under grant No. NCET-06-0875.