Project Management Institute

Resource-based project scheduling

which rules perform best?

University of North Carolina

James H. Patterson

Pennsylvania State University

When project scheduling is conducted under conditions of strictly limited resource availabilities resource “conflicts” often occur which prevent concurrent scheduling of parallel activities requiring the same resources. Under such conditions some of the parallel activities must be delayed beyond their Early Start Times. This can result in the delaying of following activities: the creation of additional conflicts, and subsequent increases in project duration beyond the initially-determined Critical Path Length. The amount of increase is a function of which jobs are delayed and which are given priority at each resource conflict point. The possible number of different activity sequences for realistic problems is typically very large and increases explosively with the number of conflicting activities involved. So it is usually impractical to evaluate all possible sequences and pick the shortest-duration schedule.

Various heuristic (i.e. “rule of thumb”) rules have been developed for choosing which activities to delay in such situations. These heuristics are commonly employed in computer programs for project scheduling under limited resources. In fact, over the years, considerable effort has been expended in developing elaborate, computer-based procedures incorporating one or more sequencing rules — usually these procedures appear as separate modules of a standard PERT/CPM computer program package and today, literally dozens of such packages exist (e.g., see Jenett. 9 ).

In contrast to the efforts spent in developing new heuristics, relatively little effort has gone into their systematic testing and comparison. Also, the results of those tests which have been conducted often appear contradictory and have not been widely published. As a result, considerable confusion exists among both practitioners and researchers as to the effectiveness of particular rules. It is not generally recognized by practitioners, for example, that a particular heuristic which has given generally good results on a few selected problems may, on new problems, suddenly produce much worse results than alternate rules would give. Also — and more pertinent to our study — there has been essentially no useful data available which would help users or researchers judge how close to the optimal (i.e., shortest possible duration) are the results produced with specific heuristics.

Mathematical procedures like Linear Programming have long been demonstrated capable of producing optimal solutions for problems of this sort, but only for very small, trivial-sized problems. Thus optimal solutions for “bench-mark” testing of alternative heuristics have not been available for realistic-sized problems. The few such comparisons which have been made were conducted with limited problems under special conditions such as one resource type per project.

Recently, the development of a new class of mathematical procedures called “branch and bound” has enabled the computation of optimal solutions for problems far larger and more complex than any previously solved by linear programming. While the size of problems capable of solution by these newer procedures has not reached the point of general business applicability, the problems solved are large enough to permit development of more valid conclusions about the effectiveness of particular heuristic procedures relative to the optimal solution. Using a variation of this newer approach we solved a total 83 different hypothetical problems optimally and with each of eight different heuristic sequencing rules to determine which heuristics performed generally best compared with the toptimal durations. The eight heuristic procedures selected for use in the study were chosen partially on the basis of some previous researchers work, as summarized briefly below.

Previous Research

Comparisons of different heuristic rules (relative to one another) for constrained-resource project scheduling have been reported in nine previous studies [1], [2], [7], [8], [10], [11], [12], [13], [14], While many of the same rules were tested in these studies, the particular type of network scheduling problem varied considerably. Table 1 lists these nine previous studies in chronological order and indicates the type of problem examined and the sequencing rule found generally most effective on a measure of project duration (for single-project studies) or project slippage (for multi-project studies).

As can be seen from Table 1, two broadly different categories of heuristics have been reported most effective in minimizing project duration or slippage: (1) heuristics incorporating some measure of time, i.e., activity slack, activity duration or start/finish time, and (2) heuristics incorporating some measure of resource usage. For the study described here we selected rules from both of these categories.

How The Test Was Conducted

The test conducted in this study involved successively solving 83 different project scheduling problems, first with a mathematically exact procedure [5] to obtain the optimum schedule duration, then with each of a selected group of eight different heuristic rules using a modification of the “MPSP” program [14]. In this way, both an optimal duration schedule and eight heuristic-based schedule durations produced by each heuristic were obtained for each problem, for comparison.

The eight heuristic rules used in the test were selected based on the findings of previous research summarized above and consideration of heuristics used in some commercially-available computer programs. Table 2 lists these heuristics and briefly summarizes the characteristics of each rule. It should be noted that this group includes both rules of the type found effective in some previous study listed in Table 1 plus two chosen for their basically different characteristics (i.e. RAN, MJP). We might also add that the rules were employed within the context of a “parallel” approach to scheduling in which activity priority is determined during the scheduling process rather than before (as in a “serial” approach). Further, all heuristics were of the “ground rule” variety in the sense that they did not include any modifying heuristics of the type investigated by Wiest [15] and included in some commercially-available programs. Ties in activity priority were resolved by lowest job number first, and activities once scheduled were not interrupted.


TABLE I Heuristics Found Most Effective In Previous Research

Researcher Problem Characteristics1 Rule Generally Best for Project Duration or Slippage
Brand, et. al (1964) Single Project,
Multi-Resource
“RSM” Heuristic2
Mize (1964) Multi-Project,
Job-Shop
Complex rules based on
Min. job slack
Pascoe (1965) Single Project,
Multi-Resource
Min. LFT, Min. LST
Knight (1966) Multi-Project,
Multi-Resource,
Linear Networks
Project Resource
Utilization
Mueller-
Mehrbach (1967)
Single Project,
Job-Shop
Min. LST, Min. LFT
Crowston (1968) Single Project,
Multi-Resource
Min. LST
Fendley (1968) Multi-Project
Multi-Resource
Min. Job Slack
Gonguet (1969) Single Project,
Multi-Resource
Min. LFT
Patterson (1973) (a) Multi-Project,
   Multi-Resource
SIO, Min. Job Slack and
Greatest Resource Useage3
(b) Multi-Project,
   Job-Shop
Min. Job Slack

The scheduling problems used in the test involved 57 different hypothetical project networks. These networks were arbitrarily limited in size to between 22 and 27 activities to guarantee ease of optimum solution with the computation procedure used. The activities in each network required various amounts of three different resource types which were constant over activity duration. Some of the networks were assigned more than one pattern of resource characteristics, producing a total of 83 different problems. Figure 1 shows a sample problem with its associated schedule results.

Insofar as the operating characteristics of the different heuristics rules used are concerned, some readers might be interested in the fact that five of the rules examined (MINSLK, LFT, GRD, SIO and RAN) require about the same computer core storage and CPU time to implement . The RSM heuristic requires the same amount of core storage as these, but about twice the amount of CPU time to solve a given problem because of the necessity of making several pair-wise comparisons of activity attributes at each scheduling interval. The two rules GRU and MJP require about twice the amount of storage and about five times the amount of CPU time because an embedded linear programming problem must be solved at each scheduling interval. However even with the larger core storage and computation time requirements of the latter rules, these considerations were not limiting factors in this test.


TABLE 2 Heuristic Scheduling Rules Evaluated

RULE NOTATION OPERATING FEATURES
Minimum Activity Slack MINSLK Schedules first those activities with lowest activity slack time (total float).
Minimum Late finish Time LFT Schedules first those activities with the earliest values of late finish time.
Resource Scheduling Method RSM Priority index calculated on basis of pairwise comparison of activity early finish and late start times. Gives priority to activities roughly in order of increasing Late finish time.
Greatest Resource Demand GRD Schedules first those activities with greatest resource demand in order to complete potential bottleneck activities.
Greatest Resource Utilization GRU Gives priority to that group of activities which results in the minimum amount of idle resources in each scheduling interval. Involves an integer linear programming logarithm.
Shortest Imminent Operations SIO Schedules first those activities with shortest durations in an attempt to complete the greatest number of activities within a given time-span.
Most Jobs Possible MJP Gives priority to the largest possible group of jobs which can be scheduled in an interval. Involves an integer linear programming logarithm.
Random Activity Selection RAN Priority given to jobs selected at random, subject to resource availability limits.

 

Note: The MINSLK rule has been shown equivalent to a minimum-late-start-time rule. See [6].


Figure 1 Example test problem with scheduling results

Example test problem with scheduling results

Source: Management Science, Vol. 21, No. 8, (April, 1975), Page 947

It was recognized from the beginning that the modest size and resource characteristics of problems used in the test might limit the generalization of our findings, since problems encountered in practice are far larger. However at least one researcher found in his comparative study of different heuristics that rules which were most effective in solving a large group of 20-activity networks were also relatively most effective on a smaller group of 100-activity networks [13]. Also, there is no existing evidence that size, per se is a determinant of the relative effectiveness of alternative heuristic sequencing rules. We also controlled the characteristics of the networks generated and their associated pattern of resource requirements to produce problems which were in our opinion at least reasonably similar, on a proportionately smaller basis, to those encountered in practice. Thus we concluded that the results of these tests might logically be extended to larger, more complex problems.

Test Results (A): Heuristics vs. Optimal

The test approach described above produced a set of optimal and heuristically-obtained schedule durations for each of the 83 problems. We first analyzed these results in terms of general performance measures which might be of particular interest to practitioners, using the optimum solution as a base of comparison.

For example, one measure which might be of interest is the proportion of total problems for which optimum solutions were obtained using some heuristic rule. We found, as shown in Figure 2, that fewer than half the 83 problems could be solved optimally using all eight heuristic rules on each problem. The rule which singly produced the greatest number of optimal-duration schedules was MINSLK, with 24 of 83 (29%) problems solved optimally.

Given that 60% of the problems could not be solved optimally with any heuristic, one might also like to know how much longer, on average, were the schedule durations produced by each heuristic rule (including zero increase cases). Figure 3 gives this information, in terms of the percent increase in schedule duration above the optimal duration. As can be seen, the MINSLK rule again performed best, with an average percent increase above optimal of about 6% followed fairly closely by the LFT and RSM rules. In general these three rules performed relatively better in this regard than the random choice rule (RAN), while the other four rules fared worse. Although no one has compared the performance of an experienced human project scheduler with any of the rules tested here, it’s logical to assume such an individual could at least do as well as a procedure which assigns activity priorities randomly. Thus, these results suggest that on this measure of performance, the four poorer-performing rules would be particularly bad choices for project scheduling.

Finally, another measure of interest here is the worst performance of any rule. That is, what was the greatest increase in schedule duration above optimum that was obtained with any of these rules? Figure 4 gives this information and shows, for example, that the GRD rule produced the greatest single percent increase above optimum (about 41%) of any of the rules tested. The RSM rule, in contrast, produced a similar measure only half as great as GRD.

Figure 4 also gives the standard deviation of the percent increase above optimum for each rule, which is a good measure of the variation of percent increase. Using the information given in both Tables 3 and 4, it can be seen that the best-performing rules, relative to optimum, were those having a low average percent increase above optimum, and a small variation about this average with lowest values of maximum percent increase. On this basis, the MINSLK, LFT and RSM rules were again clearly superior to the other five.

Figure 2 Percent of Problems for which Optimal Minimum Duration Solution Obtained

Percent of Problems for which Optimal Minimum Duration Solution Obtained

*Percentages computed include problems in which one or more heuristic sequencing rules produced a minimum duration solution.

Figure 3 Percent increase Above Optimal Duration

Percent increase Above Optimal Duration

Test Results (B): Heuristics vs. One Another

While the primary focus of our study was on the performance of heuristic rules relative to the optimal, the test also produced data on the performance of heuristics relative to one another, and it is useful to see some of these results.

Figure 5, for example, indicates the percent of problems for which each heuristic rule produced the shortest heuristic-based schedule duration (including ties). As might be expected from the previous results, MINSLK performed best in this regard, followed by LFT and RSM. However, in this case GRD came out slightly better than the random choice rule, while SIO, MJP and GRU were considerably worse.

Another point of interest shown in Figure 5 is the percent of problems for which each heuristic produced unique shortest-duration schedule, i.e., a shortest-duration result which was not achieved by any other heuristic. This information is interesting in that it illustrates a point made earlier: generally good-performing heuristics will not always produce the uniquely best results on every problem. As shown in Figure 5, for instance, the MINSLK rule produced a result which was better than that achieved by any other heuristic in about 18% of the cases. But there was still a total of 25% of the problems for which some other heuristic produced a better result!

In most practical situations the project or program manager would likely receive the results of scheduling effort obtained with only one heuristic sequencing rule. In such situations, our advice to him based on the results of this study would be to specify the use of the MINSLK rule if at all possible. That rule, in general, performed best along all dimensions of performance measurement.

However another question arises in situations in which such a manager wishes to obtain several different schedules produced using alternate heuristics. For example, the schedule results produced using the MINSLK rule might be unsatisfactory for some reason. Or the manager might wish in advance to ensure a high probability in obtaining the best possible results for a specific project by specifying the separate, sequential use of several different rules to produce different schedules. In such cases, in which order should the sequencing rules be used: MINSLK first, then RSM, then MJP, or some other order? How many different rules should be used at all? Some insight into the answers to these questions is provided in Figure 6.

Figure 4 Maximum and Standard Deviation of Percent Increase Above Optimal Duration

Maximum and Standard Deviation of Percent Increase Above Optimal Duration

Figure 6 shows the cumulative percentage of problems for which each heuristic rule produced the best relative results. It can be seen from this information that use of the three rules MINSLK, LFT and RSM would produce the best possible results for 87% of the problems. Likewise, if only the two rules MINSLK and LFT were used, about 77% of the problems would be best-solved.

Conclusions

As noted in the discussion of results above, none of the heuristic rules tested in this study performed consistently best on all 83 problems. However, the MINSLK rule, which bases activity priority on activity slack, produced an optimal schedule duration most often and exhibited the lowest average increase above optimum of the rules examined. Two other rules, LFT and RSM, were close in performance to the MINSLK rule, and these three as a group produced generally better results than the other five tested.

Figure 5 Percent of Problems for which Shortest Heuristic-based Solution Produced (Including Ties) and Percent of Time UNIQUE Shortest-duration Solution Produced Best Relative Results

Percent of Problems for which Shortest Heuristic-based Solution Produced (Including Ties) and Percent of Time UNIQUE Shortest-duration Solution Produced Best Relative Results

Figure 6 Cumulative Percent of Minimum-duration Heuristic Results Obtained

Cumulative Percent of Minimum-duration Heuristic Results Obtained

With respect to the relative performance of heuristics, our findings generally agree with those of previous researchers who compared rules for single-project, multi-resource scheduling. Our findings do not support those of researchers who found other rules generally better on other type problems but this simply illustrates a point not often made clear in the literature.

Some rules which are effective in such situations as multi-project scheduling, like GRU and SIO, are not particularly effective in other situations, such as single-project scheduling. We would also add in this regard that the MINSLK rule appears effective in both of these situations.

We commented earlier upon the limited size of problems used in this test and noted that there is no documentary evidence that results based upon problems such as these cannot be extended to larger, more complex problems. We feel in this regard that a much more important consideration than size in the generalization of these and other such findings has to do with project/resource characteristics such as network structure and the pattern of resource requirements and availabilities. Based upon what we know about such relationships, and the fact that the problems used in this test were controlled to exhibit measureable characteristics not unlike those encountered in practice, we believe our results are applicable to much larger problems with similar characteristics.

In closing, we would comment that the whole question of how to measure project network characteristics in useful terms is today, unanswered. Some exploratory research in this area [4], [15], indicates that such relationships as the ratio of resource requirements to availabilities and the profile of resource characteristics over project duration are much more important determinants of schedule durations produced with heuristic sequencing rules than number of project activities and resource types. But further progress in this area is needed — particularly work which would increase our ability to predict accurately in advance of project scheduling which particular heuristic will give the uniquely best schedule duration for a particular problem, in view of that problem’s unique characteristics of network structure and resources. This is an important research area which has all but been ignored in the past and deserves more attention in the literature.

REFERENCES

1. Brand, J. D., W. L. Meyer and L. R. Shaffer, “The Resource Scheduling Method In Construction,” Civil Engineering Studies Report No. 5, University of Illinois, 1964.

2. Crowston, W. B. S., “Decision Network Planning Models,” unpublished Ph.D. thesis, Carnegie-Mellon University, 1968.

3. Davis, E. W., “Project Scheduling Under Resource Constraints — Historical Review and Categorization of Procedures,” AIIE Transactions, December, 1973.

4. Davis, E. W., “Project Network Summary Measures and Constrained-Resource Scheduling, AIIE Transactions, June, 1975.

5. Davis, E. W. and G. E. Heidorn, “Optimal Project Scheduling Under Multiple Resource Constraints,” Management Science, August, 1971.

6. Davis, E. W. and J. H. Patterson, “A Comparison of Optimal and Heuristic Solutions in Resource-Constrained Project Scheduling,” Management Science, April, 1975.

7. Fendley, L. G., “Toward the Development of a Complete Multi-Project Scheduling System,” Journal of Industrial Engineering, October, 1968.

8. Gonguet, L., “Comparison of Three Heuristic Procedures for Allocating Resources and Producing Schedules,” in Project Planning By Network Analysis, North-Holland Press, 1969.

9. Jenett, E. “Availability of CPM Programs,” Project Management Quarterly, July, 1970.

10. Knight, R. M., “Resource Allocation and Multi-Project Scheduling in a Research and Development Environment,” unpublished M. S. thesis, A. P. Sloan School of Management, MIT, June, 1966.

11. Mize, J. H., “A Heuristic Scheduling Model for Multi-Project Organizations,” Unpublished Ph.D. thesis, Purdue University, 1964.

12. Mueller-Mehrbach, H. “Ein Verfahren zur Planung des Optimalen Betriebsmitteleinsatzes bei der Terminierung von Grossprojekten,” AWF-Mitteilungen, Munich. February, 1967.

13. Pascoe, T. L., “An Experimental Comparison of Heuristic Methods for Allocating Resources,” Unpublished Ph.D. thesis, Department of Engineering, Cambridge University, 1965.

14. Patterson, J. H., “Alternate Methods Of Project Scheduling With Limited Resources,” Naval Research Logistics Quarterly, December, 1973.

15. Patterson, J. H., “Project Scheduling: The Effects of Problem Structure On Heuristics Performance,” Naval Research Logistics Quarterly, forthcoming.

16. Wiest, J. D., “A Heuristic Model for Scheduling Large Projects With Limited Resources,” Management Science, February, 1967.



Continued from page 40

References

1. Barndt, Lt. Col. Stephen E. “A Study of the Relationship Between Decision Maker’s Education and Experience and Alternative Choice in Trade Off Decisions.” Technical Report, AU-AFIT-SL-1-75, School of Systems and Logistics, Air Force Institute of Technology (AU), Wright-Patterson AFB, Ohio, 1975.

2. Department of The Air Force. Program Management, Air Force Regulation 800-2. Washington, D. C.: Department of The Air Force, 1972.

3. Freeman, John R. and Harold E. Smalley “Determinants of Hospital Supply Decision,” Nursing Research, Vol. 14, No. 3 (Summer 1965), pp. 244-253.

4. Knorr, Klaus. “On the Cost Effectiveness Approach to Military R & D: A Critique.” Paper presented at the 29th National Meeting of the Operations Research Society of America, Santa Monica, California, (May 1966).

5. Simon, Herbert A. “On the Concept of Organizational Goal,” Administrative Science Quarterly, Vol, 9, No. 1 (June 1964), pp. 1-22.

6. Smythe, Major Ralph E. and Captain William J. McMullan. “An Evaluation of the Major Qualifications Desired of Air Force System Program Managers.” Unpublished Master’s thesis, School of Systems and Logistics, Air Force Institute of Technology (AU), Wright-Patterson AFB, Ohio, 1974.

7. Wilemon, David L. “Project Management and Its Conflicts: A View from Appollo,” Chemical Technology, Vol. 2, No. 9, (September 1972), pp. 527-534.


1Classifications of problem type here are based on Davis [3] and refer to the number and units of resource types and requirements and availabilities

2Involves the comparison of job EFT’s and LST’s; results are essentially equivalent to Min. LFT.

3Each of these three rules was found generally best on different measures of performance.

This material has been reproduced with the permission of the copyright owner. Unauthorized reproduction of this material is strictly prohibited. For permission to reproduce this material, please contact PMI.

Advertisement

Advertisement

Related Content

Advertisement