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

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

0.00 Avg rating0 Votes
Article ID: iaor2005183
Country: United Kingdom
Volume: 42
Issue: 12
Start Page Number: 2435
End Page Number: 2456
Publication Date: Jan 2004
Journal: International Journal of Production Research
Authors: ,
Keywords: programming: branch and bound
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.

Reviews

Required fields are marked *. Your email address will not be published.