NETWORK OPTIMIZATION MODELS:A NETWORK MODEL FOR OPTIMIZING A PROJECT’S TIME-COST TRADE-OFF

A NETWORK MODEL FOR OPTIMIZING A PROJECT’S TIME-COST TRADE-OFF

Networks provide a natural way of graphically displaying the flow of activities in a major project, such as a construction project or a research-and-development project. Therefore, one of the most important applications of network theory is in aiding the management of such projects.

In the late 1950s, two network-based OR techniques—PERT (program evaluation and review technique) and CPM (critical path method)—were developed independently to assist project managers in carrying out their responsibilities. These techniques were de- signed to help plan how to coordinate a project’s various activities, develop a realistic schedule for the project, and then monitor the progress of the project after it is under way. Over the years, the better features of these two techniques have tended to be merged into what is now commonly referred to as the PERT/CPM technique. This network approach to project management continues to be widely used today.

One of the supplementary chapters on the book’s website, Chap. 22 (Project Man- agement with PERT/CPM), provides a complete description of the various features of PERT/CPM. We now will highlight one of these features for two reasons. First, it is a network optimization model and so fits into the theme of the current chapter. Second, it illustrates the kind of important applications that such models can have.

The feature we will highlight is referred to as the CPM method of time-cost trade- offs because it was a key part of the original CPM technique. It addresses the follow- ing problem for a project that needs to be completed by a specific deadline. Suppose that this deadline would not be met if all the activities are performed in the normal manner, but that there are various ways of meeting the deadline by spending more money to expedite some of the activities. What is the optimal plan for expediting some activities so as to minimize the total cost of performing the project within the deadline?

The general approach begins by using a network to display the various activities and the order in which they need to be performed. An optimization model then is formulated that can be solved by using either marginal analysis or linear programming. As with the other network optimization models considered earlier in this chapter, the special structure of the problem makes it relatively easy to solve efficiently.

This approach is illustrated below by using the same prototype example that is car- ried through Chap. 22.

A Prototype Example—the Reliable Construction Co. Problem

The RELIABLE CONSTRUCTION COMPANY has just made the winning bid of $5.4 mil- lion to construct a new plant for a major manufacturer. The manufacturer needs the plant to go into operation within 40 weeks.

Reliable is assigning its best construction manager, David Perty, to this project to help ensure that it stays on schedule. Mr. Perty will need to arrange for a number of crews to perform the various construction activities at different times. Table 10.7 shows his list of the various activities. The third column provides important additional information for co- ordinating the scheduling of the crews.

For any given activity, its immediate predecessors (as given in the third col- umn of Table 10.7) are those activities that must be completed by no later than the starting time of the given activity. (Similarly, the given activity is called an immediate successor of each of its immediate predecessors.)

For example, the top entries in this column indicate that

1. Excavation does not need to wait for any other activities.

2. Excavation must be completed before starting to lay the foundation.

3. The foundation must be completely laid before starting to put up the rough wall, and so on.

When a given activity has more than one immediate predecessor, all must be finished be- fore the activity can begin.

In order to schedule the activities, Mr. Perty consults with each of the crew supervi- sors to develop an estimate of how long each activity should take when it is done in the normal way. These estimates are given in the rightmost column of Table 10.7.

Adding up these times gives a grand total of 79 weeks, which is far beyond the dead- line of 40 weeks for the project. Fortunately, some of the activities can be done in paral- lel, which substantially reduces the project completion time. We will see next how the project can be displayed graphically to better visualize the flow of the activities and to determine the total time required to complete the project if no delays occur.

We have seen in this chapter how valuable networks can be to represent and help ana- lyze many kinds of problems. In much the same way, networks play a key role in dealing with projects. They enable showing the relationships between the activities and succinctly displaying the overall plan for the project. They also are helpful for analyzing the project.

Project Networks

A network used to represent a project is called a project network. A project network consists of a number of nodes (typically shown as small circles or rectangles) and a number of arcs (shown as arrows) that connect two different nodes.

As Table 10.7 indicates, three types of information are needed to describe a project:

1. Activity information: Break down the project into its individual activities (at the de- sired level of detail).

2. Precedence relationships: Identify the immediate predecessor(s) for each activity.

3. Time information: Estimate the duration of each activity.

The project network should convey all this information. Two alternative types of project networks are available for doing this.

One type is the activity-on-arc (AOA) project network, where each activity is represented by an arc. A node is used to separate an activity (an outgoing arc) from each of its immediate predecessors (an incoming arc). The sequencing of the arcs thereby shows the precedence relationships between the activities.

The second type is the activity-on-node (AON) project network, where each activity is represented by a node. Then the arcs are used just to show the precedence relationships that exist between the activities. In particular, the node for each activity with immediate predecessors has an arc coming in from each of these predecessors.

The original versions of PERT and CPM used AOA project networks, so this was the conventional type for some years. However, AON project networks have some important advantages over AOA project networks for conveying the same information:

1. AON project networks are considerably easier to construct than AOA project networks.

2. AON project networks are easier to understand than AOA project networks for inex- perienced users, including many managers.

3. AON project networks are easier to revise than AOA project networks when there are changes in the project.

For these reasons, AON project networks have become increasingly popular with practitioners. It appears that they may become the standard format for project networks. There- fore, we will focus solely on AON project networks, and will drop the adjective AON. Figure 10.28 shows the project network for Reliable’s project.2 Referring also to the third column of Table 10.7, note how there is an arc leading to each activity from each of its immediate predecessors. Because activity A has no immediate predecessors, there is an arc leading from the start node to this activity. Similarly, since activities M and N have no immediate successors, arcs lead from these activities to the finish node. There- fore, the project network nicely displays at a glance all the precedence relationships be- tween all the activities (plus the start and finish of the project). Based on the rightmost column of Table 10.7, the number next to the node for each activity then records the estimated duration (in weeks) of that activity.

The Critical Path

How long should the project take? We noted earlier that summing the durations of all the activities gives a grand total of 79 weeks. However, this isn’t the answer to the question because some of the activities can be performed (roughly) simultaneously.

What is relevant instead is the length of each path through the network:

A path through a project network is one of the routes following the arcs from the START node to the FINISH node. The length of a path is the sum of the (estimated) durations of the activities on the path.

The six paths through the project network in Fig. 10.28 are given in Table 10.8, along with the calculations of the lengths of these paths. The path lengths range from 31 weeks up to 44 weeks for the longest path (the fourth one in the table).

So given these path lengths, what should be the (estimated) project duration (the total time required for the project)? Let us reason it out.

Since the activities on any given path must be done in sequence with no overlap, the project duration cannot be shorter than the path length. However, the project duration can be longer because some activity on the path with multiple immediate predecessors might

2Although project networks often are drawn from left to right, we go from top to bottom to better fit on the printed page.

have to wait longer for an immediate predecessor not on the path to finish than for the one on the path. For example, consider the second path in Table 10.8 and focus on activity H. This activity has two immediate predecessors, one (activity G) not on the path and one (activity E ) that is. After activity C finishes, only 4 more weeks are required for ac- tivity E but 13 weeks will be needed for activity D and then activity G to finish. There- fore, the project duration must be considerably longer than the length of the second path in the table.

However, the project duration will not be longer than one particular path. This is the longest path through the project network. The activities on this path can be per- formed sequentially without interruption. (Otherwise, this would not be the longest path.)

Therefore, the time required to reach the FINISH node equals the length of this path. Fur- thermore, all the shorter paths will reach the FINISH node no later than this.

Here is the key conclusion:

The (estimated) project duration equals the length of the longest path through the project network. This longest path is called the critical path.3 (If more than one path tie for the longest, they all are critical paths.)

Thus, for the Reliable Construction Co. project, we have

Critical path: START ---A---B---C---E---F---J---L---N--- FINISH

(Estimated) project duration = 44 weeks.

Therefore, if no delays occur, the total time required to complete the project should be about 44 weeks. Furthermore, the activities on this critical path are the critical bottleneck activities where any delays in their completion must be avoided to prevent delaying proj- ect completion. This is valuable information for Mr. Perty, since he now knows that he should focus most of his attention on keeping these particular activities on schedule in striving to keep the overall project on schedule. Furthermore, to reduce the duration of the project (remember that the deadline for completion is 40 weeks), these are the main activities where changes should be made to reduce their durations.

Mr. Perty now needs to determine specifically which activites should have their du- rations reduced, and by how much, in order to meet the deadline of 40 weeks in the least expensive way. He remembers that CPM provides an excellent procedure for investigat- ing such time-cost trade-offs, so he will use this approach to address this question.

We begin with some background.

Time-Cost Trade-Offs for Individual Activities

The first key concept for this approach is that of crashing:

Crashing an activity refers to taking special costly measures to reduce the dura- tion of an activity below its normal value. These special measures might include us- ing overtime, hiring additional temporary help, using special time-saving materials, obtaining special equipment, etc. Crashing the project refers to crashing a num- ber of activities in order to reduce the duration of the project below its normal value.

The CPM method of time-cost trade-offs is concerned with determining how much (if any) to crash each of the activities in order to reduce the anticipated duration of the project to a desired value.

The data necessary for determining how much to crash a particular activity are given by the time-cost graph for the activity. Figure 10.29 shows a typical time-cost graph. Note the two key points on this graph labeled Normal and Crash:

The normal point on the time-cost graph for an activity shows the time (dura- tion) and cost of the activity when it is performed in the normal way. The crash point shows the time and cost when the activity is fully crashed, i.e., it is fully expedited with no cost spared to reduce its duration as much as possible. As an approximation, CPM assumes that these times and costs can be reliably predicted without significant uncertainty.

For most applications, it is assumed that partially crashing the activity at any level will give a combination of time and cost that will lie somewhere on the line segment between

3Although Table 10.8 illustrates how the enumeration of paths and path lengths can be used to find the critical path for small projects, Chap. 22 describes how PERT/CPM normally uses a considerably more efficient pro- cedure to obtain a variety of useful information, including the critical path.

Crash time Normal time Activity duration

these two points.4 (For example, this assumption says that half of a full crash will give a point on this line segment that is midway between the normal and crash points.) This sim- plifying approximation reduces the necessary data gathering to estimating the time and cost for just two situations: normal conditions (to obtain the normal point) and a full crash (to obtain the crash point).

Using this approach, Mr. Perty has his staff and crew supervisors working on de- veloping these data for each of the activities of Reliable’s project. For example, the su- pervisor of the crew responsible for putting up the wallboard indicates that adding two temporary employees and using overtime would enable him to reduce the duration of this activity from 8 weeks to 6 weeks, which is the minimum possible. Mr. Perty’s staff then estimates the cost of fully crashing the activity in this way as compared to following the normal 8-week schedule, as shown below.

After investigating the time-cost trade-off for each of the other activities in the same way, Table 10.9 gives the data obtained for all the activities.

Which Activities Should Be Crashed?

Summing the normal cost and crash cost columns of Table 10.9 gives Sum of normal costs = $4.55 million,

Sum of crash costs = $6.15 million.

4This is a convenient assumption, but it often is only a rough approximation since the underlying assumptions of proportionality and divisibility may not hold completely. If the true time-cost graph is convex, linear pro- gramming can still be employed by using a piecewise linear approximation and then applying the separable programming technique described in Sec. 13.8.

Recall that the company will be paid $5.4 million for doing this project. This payment needs to cover some overhead costs in addition to the costs of the activities listed in the table, as well as provide a reasonable profit to the company. When developing the win- ning bid of $5.4 million, Reliable’s management felt that this amount would provide a reasonable profit as long as the total cost of the activities could be held fairly close to the normal level of about $4.55 million. Mr. Perty understands very well that it is his re- sponsibility to keep the project as close to both budget and schedule as possible.

As found previously in Table 10.8, if all the activities are performed in the normal way, the anticipated duration of the project would be 44 weeks (if delays can be avoided). If all the activities were to be fully crashed instead, then a similar calculation would find that this duration would be reduced to only 28 weeks. But look at the prohibitive cost ($6.15 million) of doing this! Fully crashing all activities clearly is not a viable option.

However, Mr. Perty still wants to investigate the possibility of partially or fully crashing just a few activities to reduce the anticipated duration of the project to 40 weeks.

The problem: What is the least expensive way of crashing some activities to re- duce the (estimated) project duration to the specified level (40 weeks)?

One way of solving this problem is marginal cost analysis, which uses the last column of Table 10.9 (along with Table 10.8) to determine the least expensive way to reduce project duration 1 week at a time. The easiest way to conduct this kind of analysis is to set up a table like Table 10.10 that lists all the paths through the project network and the current length of each of these paths. To get started, this information can be copied directly from Table 10.8.

Since the fourth path listed in Table 10.10 has the longest length (44 weeks), the only way to reduce project duration by a week is to reduce the duration of the activities on this particular path by a week. Comparing the crash cost per week saved given in the