## Heuristic Techniques

Because of the difficulties with the analytical formulation of realistic problems, major efforts in attacking the resource-constrained multiproject scheduling problem have focused on heuristics. We touched earlier on some of the common general criteria used for scheduling heuristics. Let us now return to that subject.

There are scores of different heuristic-based procedures in existence. A great many of the procedures have been published (see [18] and |40j, for example), and descriptions of some are generally available in commercial computer programs.

The most commonly applied rules were discussed in Section 9.5. The logical basis for these rules predates PERT/CPM. They represent rather simple extensions of well-known approaches to job-shop scheduling. Some additional heuristics for resource allocation have been developed that draw directly on PERT/CPM. All these are commercially available for computers, and most are available from several different software vendors in slightly different versions.

Resource Scheduling Method In calculating activity priority, give precedence to that activity with the minimum value of di( where do= increase in project duration resulting when activity j follows activity i. = Max (0; (EFT,- LST,)|

where

EFTj = early finish time of activity i LST, = latest start time of activity)

The comparison is made on a pairwise basis among all activities in the conflict set.

Minimum Late Finish Time This rule assigns priorities to activities on the basis of activity finish times as determined by PERT/CPM. The earliest late finishers are scheduled first.

Greatest Resource Demand This method assigns priorities on the basis of total resource requirements, with higher priorities given for greater demands on resources. Project or task priority is calculated as:

where dj = duration of activity)

ri( = per period requirement of resource 1 by activity | m = number of resource types

Resource requirements must be stated in common terms, usually dollars. This heuristic is based on an attempt to give priority to potential resource bottleneck activities.

Greatest Resource Utilization This rule gives priority to that combination of activities that results in maximum resource utilization (or minimum idle resources) during each scheduling period. The rule is implemented by solving a 0-1 integer programming problem, as described earlier. This rule was found to be approximately as effective as the minimum slack rule for multiple project scheduling, where the criterion used was project slippage. Variations of this rule are found in commercial computer programs such as RAMPS (see |35)).

Most Possible Jobs Here, priority is given to the set of activities that results in the greatest number of activities being scheduled in any period. This rule also requires the solution of a 0-1 integer program. It differs from the greatest-resource-utilization heuristic in that the determination of the greatest number of possible jobs is made purely with regard to resource feasibility (and not with regard to any measure of resource utilization).

Heuristic procedures for resource-constrained multiproject scheduling represent the only practical means for finding workable solutions to the large, complex multiproject problems normally found in the real world. Let us examine a multiproject heuristic in somewhat more detail.