Revisiting branch and bound search strategies for machine scheduling problems

Revisiting branch and bound search strategies for machine scheduling problems

0.00 Avg rating0 Votes
Article ID: iaor2008475
Country: United Kingdom
Volume: 7
Issue: 6
Start Page Number: 429
End Page Number: 440
Publication Date: Nov 2004
Journal: Journal of Scheduling
Authors: , ,
Keywords: scheduling, programming: dynamic
Abstract:

In the design of exact methods for NP-hard machine scheduling problems, branch and bound algorithms have always been widely considered. In this work we revisit the classic search strategies for branch and bound schemes. We consider a systematic application of the well known dynamic programming dominance property for machine scheduling problems. Several conditions concerning the application of the proposed property with respect to best first, depth first, breadth first search strategies and problem characteristics are presented. Computational testing on single machine and flow shop problems validate in practice the efficiency of the considered approach and suggest that the traditional choice of depth first search with respect to best first and breadth first is strongly questionable.

Reviews

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