A time constrained approach to resource leveling in multi-project scheduling
Oregon State University
Charles J. Willie
In the management of certain projects, it is imperative that a specific completion date be met. The typical approaches to this problem are to incorporate sufficient slack or excessive quantities of resources in order to meet the time constraint. In either case there will be added expense. A need exists, therefore, for a methodology which will observe the time constraint yet minimize the quantity of resources needed. An algorithm is presented which will accomplish this. The algorithm is heuristic in nature, keying on the quantity of a resource needed in each time period and the availability of slack. The algorithm is capable of dealing with numerous concurrent projects each requiring numerous resources. The activities in each project are first scheduled by means of conventional PERT which sets the time constraint for each project. The activities are then segregated according to resource type and those with slack receive adjusted start times. The objective is to produce a level resource requirements profile.
The utility of conventional project management techniques such as PERT and CPM is significantly reduced by certain managerial considerations. Foremost among these are the need to meet a completion date and a desire to minimize resource requirements. The conventional techniques, however, have an implied assumption of unlimited resources thus enabling all activities to begin at their earliest possible start times. The result is an uneven resource requirements profile with large requirements early in the life of a project and low requirements in the later stages. Any effort to reduce peak requirements will usually result in a lengthening of project duration. In addition, many times there will be two or more projects in progress concurrently with two or more resource classifications involved. Under these conditions, the scheduling of individual activities becomes a complex task well beyond the capabilities of conventional techniques. The objective of this study was to develop a methodology which would enable project managers to meet completion dates with a minimum of resources and to do so for concurrent projects.
The focal point of the study was the uneven shape of the resource requirements profile. This drawback of conventional techniques has been known from some time and a preliminary investigation showed that there are two approaches which might be taken: the first sets the existing amount of a resource as the maximum quantity of that resource which will be available for use on all projects. Algorithms which follow this approach establish resource pools from which the specified quantities are withdrawn as activities begin and into which they are placed as activities are completed. If sufficient quantities of a resource are unavailable, activity start times are delayed. The best known example of this approach is contained in (6). The second approach does not have a limit on resources and sets an initial schedule by conventional PERT. Subsequent schedules are developed by reducing the available resource quantity by one unit at a time until further reduction would cause the due date to be exceeded. An example of this approach can be found in (4). The difference between the two approaches is the nature of the constraint under which the algorithm must operate. The first is a resource constraint where the objective is to determine completion dates and the second is a time constraint where the objective is to determine resource requirements.
Although the algorithm in (4) is ostensibly time constrained, in reality it is resource constrained also. As far as can be determined, there are no algorithms available which are truly time constrained. There are, however, many cases where it is imperative that a specific due date be met. It was for these cases that the algorithm to be presented here was developed. Specifically, the objective was to schedule all activities on concurrent projects requiring multiple resources so that a specified completion date will be met and, at the same time, generate a resource profile which is as level as possible.
The proposed algorithm relies heavily on work which has been done previously. The initial scheduling is based on simple PERT and is accomplished by means of a computer program developed by Reiman and Gray (5). The leveling conforms basically to the methodology developed by Burgess and Killebrew (1). The primary output is a series of Gantt charts. The unique aspect of the algorithm is that all these features have been combined and expanded to schedule multiple projects with multiple resource requirements. In addition, the leveling methodology has been modified substantially.
As a result of the initial scheduling, all projects will have completion dates which may not be changed, and of course, the typical uneven resource requirements profile. Following this, it is necessary to generate alternatives to the initial schedule. Inasmuch as the algorithm is constrained by the due dates, activities forming the critical path cannot be altered. Activities not on the critical path, on the other hand, may be shifted within their available slack time. It is possible, therefore, by moving an activity with its resource requirement to a new starting time, the total amount of that resource required may be reduced for that time period.
The result of this shifting can be demonstrated by using Figure 1 which shows the PERT determined schedule for a single project requiring two resources. As scheduled, the resource profile for resource number two is as shown in Figure 2. Taking activity 4-7 which has ten units of slack time and shifting it ten time units to the right, the profile changes to that shown in Figure 3. As can be seen, the maximum required quantity of that resource has been reduced.
Because there will be numerous shifts which can be made, it was necessary to develop a measure of effectiveness for comparing various alternatives. A given shift may either decrease or increase the quantity of the resource so it was necessary to use a squared variable to eliminate the problem of sign. Once again drawing on (1), a sum-of-the-squares measure will be used. For each time period in the life of the project, the quantity of a resource in use is determined, squared, and summed. Referring to Figure 2, the sum of the squares is 762. After shifting activity 4-7, producing the profile of Figure 3, the sum of the squares dropped to 630.
The complete leveling procedure is as follows: the project is scheduled with basic PERT, the resource profile established, and the sum of the squares of resource quantities computed. The earliest activity with slack is then shifted to the right, delaying its start time one time unit and a new sum of the squares computed. The two sums are compared and the smallest value is stored for future comparisons. The right shifting continues until the activity’s total slack has been consumed. Note that an increase in the sum does not terminate the search procedure, hence all possible start times are examined for that activity. Throughout the shifting process, the lowest value for the sum of the squares is stored. After all start times have been examined, the activity is returned to the start time associated with the lowest value. The algorithm proceeds to the next activity with slack and repeats the foregoing procedure. This continues until all activities have been examined. After all activities have been checked by right shifting, the algorithm returns to the beginning of the project and commences a left shift, or moving start times to earlier values. In this way, even more combinations of start times can be examined.
The algorithm is heuristic, keying on slack time and it uses the sum of the squares for determining start times. Obviously, altering the starting time of one activity may affect other activities and the total resource requirement. Only a complete enumeration of all combinations of start times would produce an optimal schedule. At the present time, this is impractical for realistic sized projects. The algorithm does examine, however, a significant number of combinations.
To demonstrate the basic capabilities of the complete algorithm, an analysis will be performed on two concurrent projects. The data for the projects is contained in Table 1. These projects are overly simplified and should not be viewed as limitations on the algorithm. Existing limitations will be noted subsequently. Note that the projects have a different number of activities, different durations, and two resources of varying quantity. Although each activity requires only one resource, two or more per activity can be analyzed simple by creating a fictitious activity for each resource.
The initial phase of the analysis is based on conventional PERT which requires as input the expected duration of each activity. In addition, it is necessary to identify for each activity the project to which it belongs, the resource it needs, and the quntity of that resource. In this phase, the projects are treated independently and a PERT schedule is determined for each one. The resulting critical path duration is used to set the due date for the project and establishes the time constraint. The complete output from this phase for the first project is shown in Table 2. The algorithm stores early and late start times for subsequent use in the leveling phase.
A criticism made of both PERT and CPM concerns the reliability of the time estimates given for the activities. The proposed algorithm utilizes PERT so it might be similarly criticized. To offset this criticism, 21 different time estimating options have been incorporated into the algorithm. They range from a fixed single-point estimate to a probabilistically distributed three point estimate of activity duration. This affords the user the capability of simulating a variety of time estimates thereby performing a type of sensitivity analysis. For the probabilistic estimates, the user has the option of a sampling procedure in which case the project parameter card would indicate the size of the sample and the number of sample sets desired. Finally, the user must indicate if leveling is desired.
If the leveling option has been selected, the algorithm proceeds to the second phase of the analysis. The shifting process then takes place, as described previously, resource by resource. After all resources have been evaluated and no further reductions in resource requirements can be found, the analysis is complete. Activities, with their newly determined start times, are reassigned to their respective projects.
Input Data for Test Projects
|Network 1||Network 2|
The final phase is the generation of two sets of reports. The initial set is concerned with the individual resources with the first report showing when each activity utilizing a resource will start and finish. This listing is shown for resource one in Table 3. The next report in this set presents the same information in Gantt chart form as shown in Table 4. In this format, slack time is also indicated where available. The final report in this set presents a period-by-period quantity requirements for the resource and is shown in Table 5.
Standard PERT Analysis Output Data
|Activities||Duration||Start Times||Finish Times||Slack|
Total Project Time on Critical Path = 43
Resource One Schedule After Leveling
|i||j||Start Time||Finish Time|
Time Schedule for Resource One
Period by Period Resource One Requirements Leveled
This set of reports should prove useful to resource supervisory personnel. The Chief Engineer, for example, whose people are needed on a number of different projects for a variety of tasks, would use the information in Table 3. He would know precisely when and where his people were needed. Table 4 could be used as a control device to monitor the progress being made on the tasks. The information from Table 5 is intended for use in budgetary planning. Because it shows the peak requirements for the resource, it should prove to be a powerful argument in support of specific staffing demands. Without the requested quantity of the resource, it is unlikely that the completion dates would be met.
In the present configuration of the computerized version of the algorithm, another chart, shown in Table 6, is produced. This table shows the resource requirements prior to leveling. Comparing Table 5 with Table 6 shows that the maximum requirement for resource one has been reduced from 24 to 17 units. A similiar comparison for the second resource showed a reduction in the maximum quantity from 20 to 18 units.
Period by Period Resource One Requirements Unleveled
The second set of reports deals with the projects. Once the optimal start times have been determined during the leveling phase and the activities reassigned to their respective projects, a Gantt chart is produced for each project. The result for project one is shown in Table 7. These reports are intended for use by the project manager. Each one provides an overview of the entire project. With this information, he should be able, among other things, to coordinate the various resource or skill centers which are needed to successfully complete his project.
Data Flow Summary
The flow of data from input to output is summarized in flow chart form in Figures 3, 4 and 5. The leveling phase shown in Figure 4 is, perhaps, overly simplified in that the left shifting operation is not explicitly identified. As mentioned previously, however, it does occur in the same sequence of steps indicated in the figure for the right shift.
Job Time Schedule for Project One After Leveling
At the present time, the computer program for implementing the algorithm is capable of evaluating ten projects, each having up to 500 activities, twenty different resource types, and 200 unique paths. This limitation, of course, is a function of the computer capacity which in this case was a CDC 3300 at Oregon State University.
The most significant limitation of the algorithm is its inability to guarantee the optimum schedule. In fact, due to the heuristic nature of the leveling procedure, it is quite likely that the final schedule produced will not be optimal. Several tests were conducted in an effort to determine the effect of this limitation. The measure to determine if the optimum schedule had been generated was again the sum of the squares of the quantity of a resource being used. For small projects, where hand calculation was possible, the final schedules were found to be optimal. For large projects, a sampling procedure was employed to select, at random, alternate combinations of starting times. None of these combinations produced a better schedule. The implication of these tests is, while the algorithm cannot guarantee optimality, there is a high, although unknown, probability of being close to optimal.
In the present configuation, the final schedule depends, to an unknown degree, upon the resource type which is selected first for leveling. After a given resource has been leveled, the activities require that resources are fixed with respect to starting times. This fixing, in many cases, will place additional restrictions on the potential starting times of other activities using other resources which, in turn, will limit the amount of leveling that can take place for those subsequent resources. Thus, the ultimate resource profiles are dependent not only on the technical considerations of the various projects, but also on the order in which the resources are leveled. To minimize the impact of this dependence, resources should be assigned a priority which dictates the order of leveling. The criterion for this priority system might be the relative cost of the various resources, with the most expensive being leveled first.
Another criterion could be the available quantity of a resource, with the resource in shortest supply receiving top priority for leveling.
Finally, the algorithm has no trade-off functions for the relationship between the quantity of a resource and the cost or duration of an activity. The quantity of a resource is determined on the basis of the technical considerations of activity and is a fixed input. Therefore, the resulting schedule may not be the least-cost schedule. The assumption was made that the most level resource profile would approach the minimum-cost schedule. If, in fact, resource quantities are variable, then each quantity and the associated activity duration must be considered individually as a separate run. The user may wish to make several runs so that both resource priority and quantity are varied. In as much as the cost and duration of a given activity is inversely proportional to the quantity of resource applied, the overall duration and cost of a project can be altered in the above manner.
1. Burgess, A. R. and J. B. Killebrew, “Variation in Activity Level on a Cyclical Arrow Diagram,” Journal of Industrial Engineering, Vol. 13, No. 2 (March-April, 1962), pp. 76-83.
2. Clark, E. E., “The Optimum Allocation of Resources Among the Activities on a Network,” Journal of Industrial Engineering, Vol. 12, No. 1 (January-February, 1961), pp. 11-17.
3. Dewitte, L, “Manpower Leveling in PERT Networks,” Data Processing for Science/Engineering, (March-April, 1964).
4. Levy, F. K., G. L. Thompson, and J. D. Wiest, “Multiship, Multishop, Workload-Smoothing Program,” Naval Research Logistics Quarterly, (March, 1963), pp. 37-44.
5. Reiman, R. E. and C. F. Gray, “SIMULATION PERT,” Working Paper No. 13, School of Bsuiness and Technology, Oregon State University, June, 1968.
6. Wiest, J. D., “A Heuristic Model for Scheduling Large Projects with Limited Resources,” Management Science, Vol. 13, No. 6 (February, 1967), pp. 359-377.