Revisiting Branch and Bound Search Strategies for Machine Scheduling Problems

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.