Dolev and Warmuth proposed a dynamic programming approach with time complexity O(nh’(m’¸-1’)’¸+1), where n is the total number of jobs, h is the height of the job precedence graph, and m is the breadth of the time profile, to solve the same problem. In this paper, the authors introduce a branch-and-bound method to solve this problem. The performance of a branch-and-bound algorithm in general, tightly depends on the branching rules and bounding conditions. Therefore the authors suggest five strategies for the branching and bounding rules to reduce the number of nodes traversed in the solution tree. Some of them are heuristic rules and the others are terminating rules. The behavior of these strategies is discussed. Testing results show that the present algorithm is better than Dolev and Warmuth’s approach.
