A Schedule Modifying Algorithm for Project Planning with Resource Constraints

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 PERT/CPM methods, given the assumption that resources are not limited. The more general case of constrained resources has not been so...

Full description

Saved in:
Bibliographic Details
Main Authors: Bennington,Gerald E, McGinnis,Leon F
Format: Report
Language:English
Subjects:
Administration and Management
ALGORITHMS
BRANCH AND BOUND METHOD
COMBINATORIAL ANALYSIS
CRITICAL PATH METHOD
DECISION MAKING
MANAGEMENT PLANNING AND CONTROL
MATHEMATICAL PROGRAMMING
Operations Research
PERT
RESOURCE ALLOCATION
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 PERT/CPM 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 370/165. Also considered in computational study are branching strategies, alternate version of the bounds, and the effect of stronger initial upper bounds. (Author)