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

Abstract

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.
Pages385-399
Number of pages15
ISBN (Print)3540652248, 9783540652243
DOIs
Publication statusPublished - 1 Jan 1998
Externally publishedYes
Event4th International Conference on Principles and Practice of Constraint Programming, CP 1998 - Pisa, Italy
Duration: 26 Oct 199830 Oct 1998

Publication series

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

Conference

Conference4th International Conference on Principles and Practice of Constraint Programming, CP 1998
CountryItaly
CityPisa
Period26/10/9830/10/98

Cite this

Rodošek, R., & Wallace, M. (1998). A generic model and hybrid algorithm for hoist scheduling problems. In Principles and Practice of Constraint Programming – CP 1998 - 4th International Conference, CP 1998, Proceedings (pp. 385-399). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1520). Springer-Verlag London Ltd.. https://doi.org/10.1007/3-540-49481-2_28
Rodošek, Robert ; Wallace, Mark. / A generic model and hybrid algorithm for hoist scheduling problems. Principles and Practice of Constraint Programming – CP 1998 - 4th International Conference, CP 1998, Proceedings. Springer-Verlag London Ltd., 1998. pp. 385-399 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{b42ea6e06e7c43e6a848d63207d756b5,
title = "A generic model and hybrid algorithm for hoist scheduling problems",
abstract = "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.",
author = "Robert Rodošek and Mark Wallace",
year = "1998",
month = "1",
day = "1",
doi = "10.1007/3-540-49481-2_28",
language = "English",
isbn = "3540652248",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag London Ltd.",
pages = "385--399",
booktitle = "Principles and Practice of Constraint Programming – CP 1998 - 4th International Conference, CP 1998, Proceedings",
address = "Germany",

}

Rodošek, R & Wallace, M 1998, A generic model and hybrid algorithm for hoist scheduling problems. in Principles and Practice of Constraint Programming – CP 1998 - 4th International Conference, CP 1998, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1520, Springer-Verlag London Ltd., pp. 385-399, 4th International Conference on Principles and Practice of Constraint Programming, CP 1998, Pisa, Italy, 26/10/98. https://doi.org/10.1007/3-540-49481-2_28

A generic model and hybrid algorithm for hoist scheduling problems. / Rodošek, Robert; Wallace, Mark.

Principles and Practice of Constraint Programming – CP 1998 - 4th International Conference, CP 1998, Proceedings. Springer-Verlag London Ltd., 1998. p. 385-399 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1520).

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

TY - GEN

T1 - A generic model and hybrid algorithm for hoist scheduling problems

AU - Rodošek, Robert

AU - Wallace, Mark

PY - 1998/1/1

Y1 - 1998/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84957376979&partnerID=8YFLogxK

U2 - 10.1007/3-540-49481-2_28

DO - 10.1007/3-540-49481-2_28

M3 - Conference Paper

SN - 3540652248

SN - 9783540652243

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 385

EP - 399

BT - Principles and Practice of Constraint Programming – CP 1998 - 4th International Conference, CP 1998, Proceedings

PB - Springer-Verlag London Ltd.

ER -

Rodošek R, Wallace M. A generic model and hybrid algorithm for hoist scheduling problems. In Principles and Practice of Constraint Programming – CP 1998 - 4th International Conference, CP 1998, Proceedings. Springer-Verlag London Ltd. 1998. p. 385-399. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/3-540-49481-2_28