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: | Vasko F.J., Wolf F.E., Stott K.L., Woodyatt L.R. |
Keywords: | heuristics, scheduling |
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.