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, we 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 we 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 our algorithm is better than Dolev and Warmuth's approach.