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: | Chu C., Che A. |
Keywords: | programming: branch and bound |
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.