A Branch and Bound Algorithm for Minimizing Cost in Project Scheduling

Abstract

This paper presents a “branch and bound” algorithm for the following problem: given a project consisting of a set of activities partially ordered by a set of precedence restrictions, with each activity having a fixed resource requirement over a specified duration, find that set of activity start times which minimizes the combined cost of fluctuations in resource demand and delay of project completion. Cost bounding procedures are augmented by dominance relationships presented as theorems. Initial feasible schedules are generated using a heuristic scheduling rule. Both the heuristic rule and the branch and bound algorithm have been programmed for the computer. Results indicate that while computation time is related to the project network structure, more significant factors are the number of activities and the relative values of the activity parameters, duration and resource requirement. Also, results indicate that the optimal schedule is relatively insensitive to changes in the ratio of the project completion delay cost to the resource level fluctuation cost. Finally, the imposition of an upper limit on resource availability resulted, in most cases, in an increase in the duration and cost of the optimal solution.