Multicyclic hoist scheduling with constant processing times

This paper proposes an exact algorithm for the multicyclic schedules of hoist moves in a printed circuit board (PCB) electroplating facility, where exactly r(r > 1) parts enter and r parts leave the production line during each cycle, and the processing time at each production stage is a given constant. The multicyclic scheduling problem is transformed into enumeration of intervals for linear functions of decision variables. This enumeration is accomplished with a branch and bound procedure. At each node of the search tree, by solving a linear programming problem (LPP), either the corresponding partial solution is proved to be unable to lead to a feasible solution, or a lower bound is computed. Due to its particular structure, this LPP is equivalent to a cycle time evaluation problem in a bivalued graph which can be solved efficiently. The proposed algorithm is polynomial in the number of tanks for a fixed r, but exponential if r is arbitrary. Computational experience with both benchmark and randomly generated test instances is presented.