Single-track multi-hoist scheduling problem: A collision-free resolution based on a branch-and-bound approach

A. Che, C. Chu

Research output: Contribution to journalArticlepeer-review

50 Scopus citations

Abstract

An analytical mathematical model and a branch-and-bound algorithm for single-track cyclic multi-hoist scheduling problems are proposed. The objective is to minimize the cycle time for a given number of hoists. The collision-free single-track constraints are first formulated as disjunctive inequalities. It is then shown that this formulation is a very strict and necessary condition. To be a sufficient and necessary one, two additional properties, like collision-checking rules, must hold in optimal solutions. It is proved that a solution violating these two properties due to their relaxation is always dominated by a collision-free one. Therefore, these two properties are relaxed in the branch-and-bound algorithm. The computation of lower bounds in the branch-and-bound algorithm requires the solution of a specific linear programming problem, which can be solved by using a graph-based polynomial algorithm. Computational results with both benchmark and randomly generated test instances are presented.

Original languageEnglish
Pages (from-to)2435-2456
Number of pages22
JournalInternational Journal of Production Research
Volume42
Issue number12
DOIs
StatePublished - 15 Jun 2004
Externally publishedYes

Fingerprint

Dive into the research topics of 'Single-track multi-hoist scheduling problem: A collision-free resolution based on a branch-and-bound approach'. Together they form a unique fingerprint.

Cite this