Heuristic project scheduling
University of Wisconsin — Madison
The problem of scheduling activities under limited resources and precedence constraints is a relatively common one that has received considerable attention in the literature. Unfortunately, this problem belongs to a class of problems where, at this time, optimal solution can be found only for unrealistically small problems of marginal practical value.
For larger problems, a number of heuristic algorithms are available. There is considerable conflicting evidence regarding the relative merit of the heuristics used in these algorithms, and there are few if any guidelines available regarding the choice of a heuristic algorithm.
The problem can be described in general as follows:
1) A set of projects is to be scheduled.
2) Each project:
a) consists of a set of activities.
b) has a schedule-dependent duration.
c) once started, should progress at a reasonably consistent rate.
3) Within a project, each activity:
a) has a known duration.
b) may not start until certain predecessor activities have finished.
c) requires a predetermined level of resources of particular kinds to be expended.
d) should have a constant resource level assignment.
e) should be interrupted only under exceptional circumstances.
4) Limited quantities of the different resources are available.
Small problems (i.e., 50 activities or less) can be optimally solved. For larger problems, it is necessary to use heuristic procedures to develop reasonable schedules. Reviews of the current state of the art in these areas are readily available in sources such as Davis .
In addition to the above theoretical problem parameters several important practical considerations are usually involved:
1) Some activities are more important than others. A strict quantitative measure of optimality may not correctly identify the “best” schedule.
2) Most projects have a duration of several months or years. Estimates of activity durations and resource requirements are likely to change several times over the life of the project.
3) Trade-offs between manpower assignments and activity durations are usually available.
4) The project manager usually has special knowledge regarding problem parameters not included in the above formal problem definition.
These considerations suggest that project schedules should be developed in an iterative manner with the project manager reviewing and evaluating schedules, pointing out infeasibilities or undesirable features until a “good” schedule is developed. (In fact, a schedule not endorsed by the project manager will not be implemented.) In this paper we will first review a method whereby such schedules can be generated through heuristic methods then we will discuss the use of a computer program designed for this prupose. Finally, we will present a comparative evaluation of several different heuristic dispatching rules.
A Heuristic Scheduling Algorithm
A flowchart for a heuristic resource constrained scheduling algorithm for project management is shown in Figure 1. This algorithm works on the principle that individual activities are to start as soon as their predecessor activities are finished if sufficient resources are available at that time. If sufficient resources are not available (i.e., the activity requires a plumber and the plumber is busy on another activity), then the activity is placed in a list of activities eligible for scheduling as soon as sufficient resources become available. Later when an activity finishes and thus releases its resources, this list is reviewed to see if an activity is waiting for a released resource. Frequently there will be several activities competing for the same resource. In this case, the activities are ranked in order of their “urgency” and activities are assigned resources and started in decreasing order of their urgency. (An alternative approach that maximizes the aggregated urgency for all activities selected at a given instance is presented in Thesen .)
Unfortunately, there is no single best way to compute an activity’s urgency. However, resource related variables and variables from the project’s critical path network (such as the latest finish time (LFT) and the slack time) frequently work well.
On attractive feature of the algorithm in Figure 1 is the fact that the internally computed urgencies can be easily adjusted or overridden by the user, thus facilitating considerable user control over the final schedule.
WASP — A Heuristic Project Scheduling Program
It is relatively easy to manually apply the above method to the development of a single schedule for a reasonably small (10-20 activity) problem. However, most projects of interest are not this small. Furthermore, heuristic schedules are usually developed in an iterative manner with urgencies being adjusted in each iteration until an acceptable schedule is developed. Under these circumstances a computer based schedule is required.
Several proprietary scheduling programs for this use are available (Davis provides an overview of many of these). Most of these programs are elements of total project management systems performing many tasks in addition to the scheduling function discussed here.
In this section we will discuss another special purpose program designed specifically for use on small computers.
Called WASP (for the Wisconsin Activity Scheduling Program) this program is written in FORTRAN IV and can be implemented on most computers with a FORTRAN compiler. A summary of the program’s capabilities is given in Figure 2. Note the program’s exceptionally low computer resource requirements.
In designing this program, special care was taken to develop a program that was easy to use. Towards this end the following special features are included:
a) Free format is used throughout.
b) Activities are identified by alphabetic names.
c) Activity data cards may appear in any order.
d) Any number of cards may be used to describe an activity.
e) Extensive error checking of input information is performed; this includes (but is not limited to) a check of the logical consistency of the project network.
f) The program may be used for CMP calculation as well as for resource constrained scheduling.
Three classes of input cards are used for this program:
a) The header card contains any useful information to be printed at the head of each output page.
b) The resource cards contain limits for up to three resources.
c) The activity cards contain information in free format as follows:
activity name, duration, resource usage, predecessor namees, ‘*’, optional priority factor
Resource usages must be provided for as many resources as were given limits on the resource limit card. The program will function as a regular CPM program if no resource requirements are specified. The following input cards are prepared for the example in Figure 3.
Simple Resource Constrained Scheduling Problem
ACTIVITY 2,1,2,4,2, ACTIVITY 1, *
ACTIVITY 3,3,1,3,3, ACTIVITY 1, *
ACTIVITY 4,3,2,2,3, ACTIVITY 2, *
ACTIVITY 5,1,4,5,1, ACTIVITY 2, ACTIVITY 3, *
ACTIVITY 6,2,0,0,0, ACTIVITY 4, ACTIVITY 5, *
The program first prints an echo of the input cards. This is followed by a tabular summary of the input data, the unconstrained CPM data and the scheduled start and stop time for each activity. To facilitate planning, graphic displays of the activity schedule (Figure 4) and resource utilization (Figure 5) for the first 31 days of the schedule are also given. Finally, a summary report indicating the count of resources and activities as well as the project duration, resource utilization, etc. is printed.
Evaluation of Scheduling Algorithms
Algorithms can be compared and evaluated on many different levels using a wide variety of different performance criteria. However, due to the scarcity and diversity of performance related information, an in-depth comparison of scheduling algorithms based on published performance data is currently not feasible, nor is it likely that it will be in the near future. In the following paragraphs we describe a hierarchy of three different levels on which such a comparison may be performed.
The majority of writers citing computational experience discuss what might be termed the computational efficiency of their algorithms. Such discussions are centered around the amounts of computing resources (primarily computer time and core but also human resources) required to attain specific schedules. This information is particularly important for large scheduling problems. The main problem attributes affecting computational efficiency appear to be the count of activities, count and availability of resources, and the structure of the project network
Souder  defines analytic effectiveness as a model’s ability to prescribe higher valued courses of action than those prescribed by alternative methods. In the context of project scheduling algorithms, analytic effectiveness will refer to the ability of heuristic algorithms to produce schedules close to those produced by exact algorithms solving the same problem. Measures such as incremental cost or tardiness (in percent as compared to the optimal solution) may be used. When optimal solutions are unavailable, a measure such as the “solution quality” (calculated cost divided by a lower bound of cost) introduced by Ritzman  may be used. Unfortunately, the solution quality does not render itself well to comparisons between problems, as the tightness of this bound will differ between problems. A better way to measure the analytic effectiveness of a scheduling algorithm, therefore, may be to relate the duration of the resulting schedule to the spread of durations obtained using alternative heuristic approaches.
The analytic efficiency of many heuristic dispatching rules has been studied in several simulation studies; however, much work remains to be done in this area before standardized measures of analytic effectiveness are accepted. David  concludes after an extensive review that it is not possible to state a priori at this time that a given scheduling heuristic yields consistently better (shorter) schedules than another scheduling heuristic.
Most resource constrained scheduling projects are concluded when an “answer” to the theoretical scheduling problem has been found. Little regard is given to the practitioner who would benefit from an estimate of the relative impact on his overall problem resulting from the use of different scheduling procedures. Such measures will be of help in selecting the appropriate approach and in justifying its procurement and implementation. Measures of this impact, which will be referred to as the systems effectiveness of a scheduling procedure, should be measured in terms related to the problem at hand (most probably dollars), rather than traditional scheduling parameters. Perhaps more than one measure should be used. At least the following considerations should be reflected:
1) The computational efficiency (i.e., cost of solution).
2) Analytic effectiveness (i.e., quality of solution).
3) Cost of data collection.
4) Effects of errors in collected data.
5) Model validity and complexity.
6) Cost of different schedule durations.
7) Ease of use.
Since all these considerations act together, it is to be expected that, from a user’s point of view, the most effective scheduling approach is not one that excels in one of these areas, but rather one that is consistently good in all areas. We have not seen systems effectiveness evaluations in the literature. This is probably because such evaluations are too context-dependent to be of general interest.
Factors Affecting Efficiency and Effectiveness
It can be shown that the following problem attributes have a substantial effect on the computational and analytic performance of project scheduling algorithms (Thesen ):
1) Number of activities.
2) Number of resources.
3) Tightness of resource constraints.
4) Information content in project network.
In the above cited paper we offered the following observations on the effects of problem attributes on solution time:
1) If everything else remained unchanged, execution time increased linearly with increases in:
a) problem size
b) number of constraints
c) constraint tightness
2) The rate of increase of computer time with constraint tightness was proportional to the information content in the network.
3) The choice of urgency factor has a significant impact on computer time requirements. The spread in solution times for different urgency criteria was particularly wide for problems with tight constraints and a network with limited information content.
4) Computer time requirements for any problem/method combination were in fact so small that available time would normally not be a significant constraint for the solution of problems of the size tested.
In the same study we reported on the quality of solutions obtained using different urgency factors. No dominant factors could be found. However, the CPM slack alone or in combination with a resource related factor usually (but not always) gave best results. We also found that selecting starting activities to maximize the sum of the urgency factors usually yields better schedules than the sequential procedure usually used in heuristic scheduling algorithms. Finally, we observed that the choice of urgency factors was not critical for problems with long drawn out networks as all methods usually yielded identical schedules in such cases.
In this paper we have reviewed some recent progress in the field of resource constrained scheduling and we have presented a computer program designed to carry out such scheduling tasks. We cited research suggesting a new approach to heuristic resource constrained scheduling algorithms. While traditional methods use the sequencing heuristic to determine the order in which activities are to be considered for scheduling at a given instant, this approach selects for scheduling the feasible set of activities with the largest combined value of this heuristic.
A systematic evaluation of a scheduling code based on these suggestions was quoted. The computational efficiency of the code was found to be high but strongly dependent upon problem attributes. The analytic efficiency of the code was also found to be good; however, the likelihood of obtaining unusually good solutions increased with the information content in the project network. It is to be expected that additional research in this area (perhaps exploiting dynamic changes in parameters such as tightness and information content) will yield urgency factors with even better performance. However, we doubt that any single criteria will prove to be best for all problems.
Copies of the program listing are available from the author.
1. Davis, E. W., “Project Scheduling Under Resource Constraints-Historical Review and Categorization of Procedures,” AIIE Transactions (December 1973), pp. 297-313.
2. Ritzman, L. P., “The Efficiency of Computer Algorithms for Plant Layout,” Management Science, Vol. 18, No. 5, Part I (January 1972), pp. 240-248.
3. Souder, W. E., “Analytical Effectiveness of Mathematical Models for R & D Project Selection,” Management Science, Vol. 19, No. 8 (April 1973), pp. 907-923.
4. Thesen, A. and G. Vanic, “WASP Users Guide,” Department of Industrial Engineering, University of Wisconsin-Madison, Technical Report 77-19, 1977.
5. Thesen, A., “Measures of the Restrictiveness of Project Networks,” Network, Vol. 7, No. 4 (1977).
6. Thesen, A., “Heuristic Scheduling of Activities Under Resource and Precedence Restrictions,” Management Science, Vol. 23, No. 4 (December 1976).