A heuristic algorithm for the limited resource problem

The purpose of this study was to develop an improved heuristic scheduling procedure for the resource-constrained CpM/pERT problem. Specifically, a time/cost trade off algorithm was developed to take advantage of scarce resources that remain unused when a "typical" heuristic scheduling algorithm is applied to this type problem. A typical heuristic scheduling algorithm considers only one resource loading and duration (normal) per activity. The algorithm developed in this study provided for two other resource loadings in addition to the normal loading; an increased loading that resulted in a reduction in activity duration (as compared to normal duration) and a reduced loading which produced an increase in activity duration. Each activity, then, had three optional resource loadings and durations which could be used to increase resource utilization during some near-term interval of the schedule and, in turn, offer an opportunity to reduce total schedule duration and costs.

A major concept introduced in the study was the concentration of attention to the near-term interval (generally one to three weeks) of the schedule. The concept was important from two points of view. First, considering a reallocation of resources for only those activities to be scheduled in the near future reduced a large, combinatorial-type problem to one that could be solved with reasonable computational effort. Second, the computational effort was expended on the only segment of the project which contained a reasonable level of certainty.

The scheduling algorithm forms combinations of the activities to be scheduled in some specified near-term interval (up to three at a time), the activities in each combination are reduced in duration, and a new schedule is developed for each combination that includes the total set of activities for the project using a proven heuristic scheduling algorithm. The total number of schedules developed is equal to the number of activity combinations formed. Each activity to be scheduled during the near-term interval and not included in the combination of activities that are reduced in duration are candidates to move to an increased duration if they meet other specified criterion. The total schedule duration achieved for each combination of activities is compared to the duration of a heuristic schedule that considers only normal activity conditions. If the schedule duration provides an improvement, then the new schedule is costed, taking into consideration five components of cost. Ultimately, the lowest cost schedule for all values of project duration generated are identified for each project.

The scheduling algorithm was tested by applying the algorithm to two sets of projects. The first set consisted of 50 small, computer-generated projects that had previously been used to evaluate other limited resource scheduling algorithms. The second set consisted of 14 larger projects that were obtained from texts, articles, and actual industrial applications. Both sets of projects were evaluated to establish whether or not they constituted a representative sample of typical projects.

The scheduling algorithm resulted in a reduction in project duration in over 90 percent of the first set of test projects. A reduction was obtained for all projects of the second set.

Three methods of reducing the number of combinations required to identify a schedule of reduced duration and/or costs were developed and evaluated. The best of the three methods required only one half the number of combinations as compared to considering all possible combinations of up to three (combinations of activities in the near-term interval). This method identified the majority of the opportunities for reduced project duration with practically no loss in accuracy as far as the identification of the global minimum cost schedule.

An analysis of computer time required for the algorithm revealed that any large project of up to 1000 activities could be scheduled within a reasonable amount of processing time. A limited study evaluating additional improvement when combinations of four activities at a time were considered indicated the increased computational requirements were much greater than the anticipated benefits.