ADAPTING BRANCH-AND-BOUND FOR REAL-WORLD SCHEDULING PROBLEMS

Many sequencing and scheduling problems can be formulated as 0-1 integ er 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 incorp orating an intuitive, user-controlled variable-tolerance into a depth- first branch-and-bound algorithm. The tolerance comprises two componen ts: a variable depth tolerance and a variable breadth tolerance. A sam ple scheduling problem is thoroughly analysed to illustrate empiricall y parameter impact on solution quality and execution time. Then, resul ts based on several real-world problems are discussed.