A generic model and hybrid algorithm for hoist scheduling problems

Robert Rodošek, Mark Wallace

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

30 Citations (Scopus)


This paper presents a robust approach to solve Hoist Scheduling Problems (HSPs) based on an integration of Constraint Logic Programming (CLP) and Mixed Integer Programming (MIP). By contrast with previous dedicated models and algorithms for solving classes of HSPs, we define only one model and run different solvers. The robust approach is achieved by using a CLP formalism. We show that our models for different classes of industrial HSPs are all based on the same generic model. In our hybrid algorithm search is separated from the handling of constraints. Constraint handling is performed by constraint propagation and linear constraint solving. Search is applied by labelling of boolean and integer variables. Computational experience shows that the hybrid algorithm, combining CLP and MIP solvers, solves classes of HSPs which cannot be handled by previous dedicated algorithms. For example, the hybrid algorithm derives an optimal solution, and proves its optimality, for multiple-hoists scheduling problems.

Original languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming – CP 1998 - 4th International Conference, CP 1998, Proceedings
PublisherSpringer-Verlag London Ltd.
Number of pages15
ISBN (Print)3540652248, 9783540652243
Publication statusPublished - 1 Jan 1998
Externally publishedYes
EventInternational Conference on Principles and Practice of Constraint Programming 1998 - Pisa, Italy
Duration: 26 Oct 199830 Oct 1998
Conference number: 4th
https://link.springer.com/book/10.1007%2F3-540-49481-2 (Conference Proceedings)

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceInternational Conference on Principles and Practice of Constraint Programming 1998
Abbreviated titleCP 1998
Internet address

Cite this