Constraint-based model for the cyclic multi-hoists scheduling problem

This article presents a method for the resolution of a material handling scheduling problem. The case studied is a real industrial problem. It consists of finding a cyclic schedule for hoist movements in a treatment surface shop. In this kind of facility, several hoists are used for all the handling operations and they have to share common zones. Then it is necessary to control that there is no collision. The mathematical formulation of the problem is based on a combination of disjunctive constraints. The constraints describe either movement schedule or collision avoidance. The resolution procedure presented identifies all the collision configurations and then uses a branch and bound-like algorithm to find the optimal solution of a given problem. The language chosen for our implementation is the constraint logic programming language: Prolog IV, which is able to solve constraints with rational variables. It actively uses the constraint propagation mechanism that can be found in several languages.