Adapting Branch-and-Bound for Real-World Scheduling Problems |
| |
Authors: | Francis J Vasko F E Wolf K L Stott L R Woodyatt |
| |
Institution: | 1.Kutztown University,USA;2.Homer Research Laboratories, Bethlehem Steel Corporation, |
| |
Abstract: | Many sequencing and scheduling problems can be formulated as 0-1 integer programs and, in theory, solved using a branch-and-bound approach. In practice, real-world instances of these problems are usually solved using heuristics. In this paper we demonstrate the benefits of incorporating an intuitive, user-controlled variable-tolerance into a depth-first branch-and-bound algorithm. The tolerance comprises two components: a variable depth tolerance and a variable breadth tolerance. A sample scheduling problem is thoroughly analysed to illustrate empirically parameter impact on solution quality and execution time. Then, results based on several real-world problems are discussed. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|