Multihoist cyclic scheduling with fixed processing and transfer times

In this paper, we study the no-wait multihoist cyclic scheduling problem, in which the processing times in the tanks and the transfer times between tanks are constant parameters, and develop a polynomial optimal solution to minimize the production cycle length. We first analyze the problem with a fixed cycle length and identify a group of hoist assignment constraints based on the positions of and the relationships among the part moves in the cycle. We show that the feasibility of the hoist scheduling problem with fixed cycle length is consistent with the feasibility of this group of constraints which can be solved efficiently. We then identify all of the special values of the cycle length at which the feasibility property of the problem may change. Finally, the whole problem is solved optimally by considering the fixed-cycle-length problems at these special values. © 2007 IEEE