Adapting Branch-and-Bound for Real-World Scheduling Problems
作者:
VaskoFrancis J.,
WolfF. E.,
StottK. L.,
WoodyattL. R.,
期刊:
Journal of the Operational Research Society
(Taylor Available online 1993)
卷期:
Volume 44,
issue 5
页码: 483-490
ISSN:0160-5682
年代: 1993
DOI:10.1057/jors.1993.84
出版商: Taylor&Francis
关键词: Branch-and-Bound;Depth and Breath Tolerance;Real-World Scheduling;Sequencing
数据来源: Taylor
摘要:
AbstractMany 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.
点击下载:
PDF (3434KB)
返 回