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

Mark Wallace, Neil Yorke-Smith

Research output: Contribution to journalArticleScientificpeer-review

3 Downloads (Pure)

Abstract

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
Number of pages19
JournalConstraints
DOIs
Publication statusE-pub ahead of print - 2020

Keywords

  • Constraint programming
  • Hoist scheduling
  • MiniZinc
  • Modelling

Fingerprint Dive into the research topics of 'A New Constraint Programming Model and Solving for the Cyclic Hoist Scheduling Problem'. Together they form a unique fingerprint.

Cite this