A New Constraint Programming Model and Solving for the Cyclic Hoist Scheduling Problem

Mark Wallace, Neil Yorke-Smith*

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

5 Citations (Scopus)
50 Downloads (Pure)


The cyclic hoist scheduling problem (CHSP) is a well-studied optimisation problem due to its importance in industry. Despite the wide range of solving techniques applied to the CHSP and its variants, the models have remained complicated and inflexible, or have failed to scale up with larger problem instances. This article re-examines modelling of the CHSP and proposes a new simple, flexible constraint programming formulation. We compare current state-of-the-art solving technologies on this formulation, and show that modelling in a high-level constraint language, MiniZinc, leads to both a simple, generic model and to computational results that outperform the state of the art. We further demonstrate that combining integer programming and lazy clause generation, using the multiple cores of modern processors, has potential to improve over either solving approach alone.

Original languageEnglish
Pages (from-to)319-337
Number of pages19
Issue number3-4
Publication statusPublished - 2020


  • Constraint programming
  • Hoist scheduling
  • MiniZinc
  • Modelling

Cite this