Scheduling with Resource Constraints and Precedence

Scheduling with Resource Constraints and Precedence

The previous section outlined resource oriented approaches to the scheduling problem. In this section, we shall review some general approaches to integrating both concerns in scheduling.

Two problems arise in developing a resource constrained project schedule. First, it is not necessarily the case that a critical path schedule is feasible. Because one or more resources might be needed by numerous activities, it can easily be the case that the shortest project duration identified by the critical path scheduling calculation is impossible. The difficulty arises because critical path scheduling assumes that no resource availability problems or bottlenecks will arise. Finding a feasible or possible schedule is the first problem in resource constrained scheduling. Of course, there may be a numerous possible schedules which conform with time and resource constraints. As a second problem, it is also desirable to determine schedules which have low costs or, ideally, the lowest cost.

Numerous heuristic methods have been suggested for resource constrained scheduling. Many begin from critical path schedules which are modified in light of the resource constraints. Others begin in the opposite fashion by introducing resource constraints and then imposing precedence constraints on the activities. Still others begin with a ranking or classification of activities into priority groups for special attention in scheduling. One type of heuristic may be better than another for different types of problems. Certainly, projects in which only an occasional resource constraint exists might be best scheduled starting from a critical path schedule. At the other extreme, projects with numerous important resource constraints might be best scheduled by considering critical resources first. A mixed approach would be to proceed simultaneously considering precedence and resource constraints.

A simple modification to critical path scheduling has been shown to be effective for a number of scheduling problems and is simple to implement. For this heuristic procedure, critical path scheduling is applied initially. The result is the familiar set of possible early and late start times for each activity. Scheduling each activity to begin at its earliest possible start time may result in more than one activity requiring a particular resource at the same time. Hence, the initial schedule may not be feasible. The heuristic proceeds by identifying cases in which activities compete for a resource and selecting one activity to proceed. The start time of other activities are then shifted later in time. A simple rule for choosing which activity has priority is to select the activity with the earliest CPM late start time (calculated as LS(i,j) = L(j)-D_ij) among those

activities which are both feasible (in that all their precedence requirements are satisfied) and competing for the resource. This decision rule is applied from the start of the project until the end for each type of resource in turn.

The order in which resources are considered in this scheduling process may influence the ultimate schedule. A good heuristic to employ in deciding the order in which resources are to be considered is to consider more important resources first. More important resources are those that have high costs or that are likely to represent an important bottleneck for project completion. Once important resources are scheduled, other resource allocations tend to be much easier. The resulting scheduling procedure is described in Table 2-14.

The late start time heuristic described in Table 2-14 is only one of many possible scheduling rules. It has the advantage of giving priority to activities which must start sooner to finish the project on time. However, it is myopic in that it doesn't consider trade-offs among resource types nor the changes in the late start time that will be occurring as activities are shifted later in time. More complicated rules can be devised to incorporate broader knowledge of the project schedule. These complicated rules require greater computational effort and may or may not result in scheduling improvements in the end.

Example 2 -10: Additional resource constraints.

As another example, suppose that only one piece of equipment was available for the project. As seen in Figure 2-17, the original schedule would have to be significantly modified in this case. Application of the resource constrained scheduling heuristic proceeds as follows as applied to the original project schedule:

1.  On day 4, activities D and C are both scheduled to begin. Since activity D has a larger value of late start time, it should be re-scheduled.

2.      On day 12, activities D and E are available for starting. Again based on a later value of late start time (15 versus 13), activity

D is deferred.

3.      On day 21, activity E is completed. At this point, activity D is the only feasible activity and it is scheduled for starting.

4.  On day 28, the planner can start either activity G or activity H. Based on the later start time heuristic, activity G is chosen to start.

5.     On completion of activity G at day 30, activity H is scheduled to begin.

The resulting profile of resource use is shown in Figure 10-18. Note that activities F and I were not considered in applying the heuristic since these activities did not require the special equipment being considered. In the figure, activity I is scheduled after the completion of activity H due to the requirement of 4 workers for this activity. As a result, the project duration has increased to 41 days. During much of this time, all four workers are not assigned to an activity. At this point, a prudent planner would consider whether or not it would be cost effective to obtain an additional piece of equipment for the project.