A Schedule Modifying Algorithm for Project Planning with Resource Constraints.
NORTH CAROLINA STATE UNIV RALEIGH DEPT OF INDUSTRIAL ENGINEERING
Pagination or Media Count:
The determination of a minimum duration schedule for a set of activities of known duration with known precedence requirements is easily accomplished by the well known PERTCPM methods, given the assumption that resources are not limited. The more general case of constrained resources has not been solved. A review of the literature shows that several combinatorial algorithms have been developed, each having some advantages and disadvantages relative to the others. However, none of the algorithms is consistently successful in solving general problems with more than thirty activities. A branch and bound algorithm is developed which preserves the CPM model at each descendant node. In a set of twelve problems, the algorithm reaches optimal solutions for eight having less than twenty-five activities, with solution times ranging from 0.90 to 8.16 seconds on an IBM 370165. Also considered in computational study are branching strategies, alternate version of the bounds, and the effect of stronger initial upper bounds. Author
- Administration and Management
- Operations Research