Cyclic hoist scheduling based on graph theory

In this paper, we consider a cyclic hoist scheduling problem. This kind of problems often arise in PCB electroplating systems. We propose a model and a algorithm to find an optimal cyclic schedule of the hoist moves. The model shows analytical properties about the problem. These properties allow to eliminate dominated or infeasible solutions, and hence speed up our algorithm which is based on branch and bound technique. The computation of lower bounds and detecting infeasible solutions require the solution of a specific class of linear programming problems. These problems can be transformed into cycle time evaluation problems in bi-valued graphs. We develop a polynomial algorithm to solve these problems. Computational results show that our algorithm outperforms algorithms in the literature