A new model and an efficient branch-and-bound solution for cyclic multi-hoist scheduling

This article studies the multi-hoist cyclic scheduling problem in electroplating lines where the processing time of parts in each tank must be within given lower and upper limits and part moves between tanks are allowed in both directions along the line. The problem arises in electroplating lines such as those used in the production of printed circuit boards and has previously been modeled as a mixed-integer linear program. The possible relative positions of any pair of moves are analyzed and a set of linear constraints is derived that expresses the no-collision requirements for hoists. Based on the analysis, a new mixed-integer linear programming model is formulated for the multi-hoist scheduling problem. An efficient branch-and-bound strategy is proposed to solve the problem. Computational results show that the new model can be solved much more quickly than an existing model in the literature and that the proposed solution method is more efficient in solving the problem than a commercial software package.