Adapting branch-and-bound for real-world scheduling problems

Adapting branch-and-bound for real-world scheduling problems

0.00 Avg rating0 Votes
Article ID: iaor1994291
Country: United Kingdom
Volume: 44
Issue: 5
Start Page Number: 483
End Page Number: 490
Publication Date: May 1993
Journal: Journal of the Operational Research Society
Authors: , , ,
Keywords: heuristics, scheduling
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 the authors 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.

Reviews

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