An Improved Hybrid Model for the Generic Hoist Scheduling Problem

Peer-reviewed

The generic hoist scheduling problem is NP-hard and arises from automatedmanufacturing lines. In recent work using the constraint logic programming(CLP) formalism, a uni¯ed model has been developed with the problem descriptionand solution method separated. We provide an improved model and new preprocessingstages where, as before, solutions and proof of optimality are provided bya hybrid CLP{MIP algorithm. The new algorithm is more scalable and robust. Wegive empirical results for a range of problem classes on benchmark problems fromseveral sources.