11.4 Crashing and Time/Cost Tradeoffs

The previous sections discussed the duration of activities as either fixed or random numbers with known characteristics. However, activity durations can often vary depending upon the type and amount of resources that are applied. Assigning more workers to a particular activity will normally result in a shorter duration. Greater speed may result in higher costs and lower quality, however. In this section, we shall consider the impacts of time, cost and quality tradeoffs in activity durations. In this process, we shall discuss the procedure of project crashing as described below.

A simple representation of the possible relationship between the duration of an activity and its direct costs appears in Figure 11-3. Considering only this activity in isolation and without reference to the project completion deadline, a manager would undoubtedly choose a duration which implies minimum direct cost, represented by Dij and Cij in the figure. Unfortunately, if each activity was scheduled for the duration that resulted in the minimum direct cost in this way, the time to complete the entire project might be too long and substantial penalties associated with the late project start-up might be incurred. This is a small example of sub-optimization, in which a small component of a project is optimized or improved to the detriment of the entire project performance. Avoiding this problem of sub-optimization is a fundamental concern of project managers.

Figure 11-3  Illustration of a Linear Time/Cost Tradeoff for an Activity

At the other extreme, a manager might choose to complete the activity in the minimum possible time, Dcij, but at a higher cost Ccij. This minimum completion time is commonly called the activity crash time. The linear relationship shown in the figure between these two points implies that any intermediate duration could also be chosen. It is possible that some intermediate point may represent the ideal or optimal trade-off between time and cost for this activity.

What is the reason for an increase in direct cost as the activity duration is reduced? A simple case arises in the use of overtime work. By scheduling weekend or evening work, the completion time for an activity as measured in calendar days will be reduced. However, premium wages must be paid for such overtime work, so the cost will increase. Also, overtime work is more prone to accidents and quality problems that must be corrected, so indirect costs may also increase. More generally, we might not expect a linear relationship between duration and direct cost, but some convex function such as the nonlinear curve or the step function shown in Figure 11-4. A linear function may be a good approximation to the actual curve, however, and results in considerable analytical simplicity.

Figure 11-4  Illustration of Non-linear Time/Cost Tradeoffs for an Activity

With a linear relationship between cost and duration, the critical path time/cost tradeoff problem can be defined as a linear programming optimization problem. In particular, let Rij represent the rate of change of cost as duration is decreased, illustrated by the absolute value of the slope of the line in Figure 11-3. Then, the direct cost of completing an activity is:

(11.14)

where the lower case cij and dij represent the scheduled duration and resulting cost of the activity ij. The actual duration of an activity must fall between the minimum cost time (Dij) and the crash time (Dcij). Also, precedence constraints must be imposed as described earlier for each activity. Finally, the required completion time for the project or, alternatively, the costs associated with different completion times must be defined. Thus, the entire scheduling problem is to minimize total cost (equal to the sum of the cij values for all activities) subject to constraints arising from (1) the desired project duration, PD, (2) the minimum and maximum activity duration possibilities, and (3) constraints associated with the precedence or completion times of activities. Algebraically, this is:

(11.15)

subject to the constraints:

where the notation is defined above and the decision variables are the activity durations dij and event times x(k). The appropriate schedules for different project durations can be found by repeatedly solving this problem for different project durations PD. The entire problem can be solved by linear programming or more efficient algorithms which take advantage of the special network form of the problem constraints.

One solution to the time-cost tradeoff problem is of particular interest and deserves mention here. The minimum time to complete a project is called the project-crash time. This minimum completion time can be found by applying critical path scheduling with all activity durations set to their minimum values (Dcij). This minimum completion time for the project can then be used in the time-cost scheduling problem described above to determine the minimum project-crash cost. Note that the project crash cost is not found by setting each activity to its crash duration and summing up the resulting costs; this solution is called the all-crash cost. Since there are some activities not on the critical path that can be assigned longer duration without delaying the project, it is advantageous to change the all-crash schedule and thereby reduce costs.

Heuristic approaches are also possible to the time/cost tradeoff problem. In particular, a simple approach is to first apply critical path scheduling with all activity durations assumed to be at minimum cost (Dij). Next, the planner can examine activities on the critical path and reduce the scheduled duration of activities which have the lowest resulting increase in costs. In essence, the planner develops a list of activities on the critical path ranked in accordance with the unit change in cost for a reduction in the activity duration. The heuristic solution proceeds by shortening activities in the order of their lowest impact on costs. As the duration of activities on the shortest path are shortened, the project duration is also reduced. Eventually, another path becomes critical, and a new list of activities on the critical path must be prepared. By manual or automatic adjustments of this kind, good but not necessarily optimal schedules can be identified. Optimal or best schedules can only be assured by examining changes in combinations of activities as well as changes to single activities. However, by alternating between adjustments in particular activity durations (and their costs) and a critical path scheduling procedure, a planner can fairly rapidly devise a shorter schedule to meet a particular project deadline or, in the worst case, find that the deadline is impossible of accomplishment.

This type of heuristic approach to time-cost tradeoffs is essential when the time-cost tradeoffs for each activity are not known in advance or in the case of resource constraints on the project. In these cases, heuristic explorations may be useful to determine if greater effort should be spent on estimating time-cost tradeoffs or if additional resources should be retained for the project. In many cases, the basic time/cost tradeoff might not be a smooth curve as shown in Figure 11-4, but only a series of particular resource and schedule combinations which produce particular durations. For example, a planner might have the option of assigning either one or two crews to a particular activity; in this case, there are only two possible durations of interest.

Example 11-4: Time/Cost Trade-offs

The construction of a permanent transitway on an expressway median illustrates the possibilities for time/cost trade-offs in construction work. One section of 10 miles of transitway was built in 1985 and 1986 to replace an existing contra-flow lane system (in which one lane in the expressway was reversed each day to provide additional capacity in the peak flow direction). Three engineers' estimates for work time were prepared:

975 calendar day, based on 750 working days at 5 days/week and 8 hours/day of work plus 30 days for bad weather, weekends and holidays.

702 calendar days, based on 540 working days at 6 days/week and 10 hours/day of work.

360 calendar days, based on 7 days/week and 24 hours/day of work.

The savings from early completion due to operating savings in the contra-flow lane and contract administration costs were estimated to be $5,000 per day.

In accepting bids for this construction work, the owner required both a dollar amount and a completion date. The bidder's completion date was required to fall between 360 and 540 days. In evaluating contract bids, a $5,000 credit was allowed for each day less than 540 days that a bidder specified for completion. In the end, the successful bidder completed the project in 270 days, receiving a bonus of 5,000*(540-270) = $450,000 in the $8,200,000 contract. However, the contractor experienced fifteen to thirty percent higher costs to maintain the continuous work schedule.

Example 11-5: Time cost trade-offs and project crashing

As an example of time/cost trade-offs and project crashing, suppose that we needed to reduce the project completion time for a seven activity product delivery project first analyzed in Section 10.3 as shown in Table 10-4 and Figure 10-7. Table 11-4 gives information pertaining to possible reductions in time which might be accomplished for the various activities. Using the minimum cost durations (as shown in column 2 of Table 11-4), the critical path includes activities C,E,F,G plus a dummy activity X. The project duration is 32 days in this case, and the project cost is $70,000.

TABLE 11-4  Activity Durations and Costs for a Seven Activity Project

Examining the unit change in cost, Rij shown in column 6 of Table 11-4, the lowest rate of change occurs for activity E. Accordingly, a good heuristic strategy might be to begin by crashing this activity. The result is that the duration of activity E goes from 9 days to 5 days and the total project cost increases by $8,000. After making this change, the project duration drops to 28 days and two critical paths exist: (1) activities C,X,E,F and G, and (2) activities C, D, F, and G.

Examining the unit changes in cost again, activity F has the lowest value of Rijj. Crashing this activity results in an additional time savings of 6 days in the project duration, an increase in project cost of $16,000, but no change in the critical paths. The activity on the critical path with the next lowest unit change in cost is activity C. Crashing this activity to its minimum completion time would reduce its duration by 4 days at a cost increase of $16,000. However, this reduction does not result in a reduction in the duration of the project by 4 days. After activity C is reduced to 7 days, then the alternate sequence of activities A and B lie on the critical path and further reductions in the duration of activity C alone do not result in project time savings. Accordingly, our heuristic corrections might be limited to reducing activity C by only 1 day, thereby increasing costs by $4,000 and reducing the project duration by 1 day.

At this point, our choices for reducing the project duration are fairly limited. We can either reduce the duration of activity G or, alternatively, reduce activity C and either activity A or activity B by an identical amount. Inspection of Table 11-4 and Figure 10-4 suggest that reducing activity A and activity C is the best alternative. Accordingly, we can shorten activity A to its crash duration (from 6 days to 4 days) and shorten the duration of activity C (from 7 days to 5 days) at an additional cost of $6,000 + $8,000 = $14,000. The result is a reduction in the project duration of 2 days.

Our last option for reducing the project duration is to crash activity G from 3 days to 2 days at an increase in cost of $8,000. No further reductions are possible in this time since each activity along a critical path (comprised of activities A, B, E, F and G) are at minimum durations. At this point, the project duration is 18 days and the project cost is $120,000., representing a fifty percent reduction in project duration and a seventy percent increase in cost. Note that not all the activities have been crashed. Activity C has been reduced in duration to 5 days (rather than its 4 day crash duration), while activity D has not been changed at all. If all activities had been crashed, the total project cost would have been $138,000, representing a useless expenditure of $18,000. The change in project cost with different project durations is shown graphically in Figure 11-5.

Figure 11-5  Project Cost Versus Time for a Seven Activity Project

Example 11-8: Mathematical Formulation of Time-Cost Trade-offs

The same results obtained in the previous example could be obtained using a formal optimization program and the data appearing in Tables 10-4 and 11-4. In this case, the heuristic approach used above has obtained the optimal solution at each stage. Using Eq. (11.15), the linear programming problem formulation would be:

Minimize   z
	= [8+3(6-dA)] + [4] + [8+4(8-dC)] + [10+7(5-dD)]
	+ [10+2(9-dE)] + [20+2.7(9-dF)] + [10+2(3-dG)]

subject to the constraints

x(6) = PD x(0) + dA x(2)
x(0) + dC x(1)
x(1) x(3)
x(2) + dB x(4)
x(1) + dD x(4)
x(2) + dE x(4)
x(4) + dF x(5)
x(5) + dG x(6)
x(0) = 0
4 dA 6
1 dB 1
4 dC 8
3 dD 5
5 dE 9
6 dF 12
2 dG 3

which can be solved for different values of project duration PD using a linear programming algorithm or a network flow algorithm. Note that even with only seven activities, the resulting linear programming problem is fairly large.

11.5 Scheduling in Poorly Structured Problems

The previous discussion of activity scheduling suggested that the general structure of the construction plan was known in advance. With previously defined activities, relationships among activities, and required resources, the scheduling problem could be represented as a mathematical optimization problem. Even in the case in which durations are uncertain, we assumed that the underlying probability distribution of durations is known and applied analytical techniques to investigate schedules.

While these various scheduling techniques have been exceedingly useful, they do not cover the range of scheduling problems encountered in practice. In particular, there are many cases in which costs and durations depend upon other activities due to congestion on the site. In contrast, the scheduling techniques discussed previously assume that durations of activities are generally independent of each other. A second problem stems from the complexity of construction technologies. In the course of resource allocations, numerous additional constraints or objectives may exist that are difficult to represent analytically. For example, different workers may have specialized in one type of activity or another. With greater experience, the work efficiency for particular crews may substantially increase. Unfortunately, representing such effects in the scheduling process can be very difficult. Another case of complexity occurs when activity durations and schedules are negotiated among the different parties in a project so there is no single overall planner.

A practical approach to these types of concerns is to insure that all schedules are reviewed and modified by experienced project managers before implementation. This manual review permits the incorporation of global constraints or consideration of peculiarities of workers and equipment. Indeed, interactive schedule revision to accomadate resource constraints is often superior to any computer based heuristic. With improved graphic representations and information availability, man-machine interaction is likely to improve as a scheduling procedure.

More generally, the solution procedures for scheduling in these more complicated situations cannot be reduced to mathematical algorithms. The best solution approach is likely to be a "generate-and-test" cycle for alternative plans and schedules. In this process, a possible schedule is hypothesized or generated. This schedule is tested for feasibility with respect to relevant constraints (such as available resources or time horizons) and desireability with respect to different objectives. Ideally, the process of evaluating an alternative will suggest directions for improvements or identify particular trouble spots. These results are then used in the generation of a new test alternative. This process continues until a satisfactory plan is obtained.

Two important problems must be borne in mind in applying a "generate-and-test" strategy. First, the number of possible plans and schedules is enormous, so considerable insight to the problem must be used in generating reasonable alternatives. Secondly, evaluating alternatives also may involve considerable effort and judgment. As a result, the number of actual cycles of alternative testing that can be accomadated is limited. One hope for computer technology in this regard is that the burdensome calculations associated with this type of planning may be assumed by the computer, thereby reducing the cost and required time for the planning effort. Some mechanisms along these lines are described in Chapter 15.

Example 11-9: Man-machine Interactive Scheduling

An interactive system for scheduling with resource constraints might have the following characteristics:

graphic displays of bar charts, resource use over time, activity networks and other graphic images available in different windows of a screen simultaneously,

descriptions of particular activities including allocated resources and chosen technologies available in windows as desired by a user,

a three dimensional animation of the construction process that can be stopped to show the progress of construction on the facility at any time,

easy-to-use methods for changing start times and allocated resources, and

utilities to run relevant scheduling algorithms such as the critical path method at any time.

Figure 11-6 shows an example of a screen for this system. In Figure 11-6, a bar chart appears in one window, a description of an activity in another window, and a graph of the use of a particular resource over time appears in a third window. These different "windows" appear as sections on a computer screen displaying different types of information. With these capabilities, a project manager can call up different pictures of the construction plan and make changes to accomadate objectives or constraints that are not formally represented. With rapid response to such changes, the effects can be immediately evaluated.

Figure 11-6  Example of a Bar Chart and Other Windows for Interactive Scheduling

11.6 Improving the Scheduling Process

Despite considerable attention by researchers and practitioners, the process of construction planning and scheduling still presents problems and opportunities for improvement. The importance of scheduling in insuring the effective coordination of work and the attainment of project deadlines is indisputable. For large projects with many parties involved, the use of formal schedules is indispensable.

The network model for representing project activities has been provided as an important conceptual and computational framework for planning and scheduling. Networks not only communicate the basic precedence relationships between activities, they also form the basis for most scheduling computations.

As a practical matter, most project scheduling is performed with the critical path scheduling method, supplemented by heuristic procedures used in project crash analysis or resource constrained scheduling. Many commercial software programs are available to perform these tasks. Probabilistic scheduling or the use of optimization software to perform time/cost trade-offs is rather more infrequently applied, but there are software programs available to perform these tasks if desired.

Rather than concentrating upon more elaborate solution algorithms, the most important innovations in construction scheduling are likely to appear in the areas of data storage, ease of use, data representation, communication and diagnostic or interpretation aids. Integration of scheduling information with accounting and design information through the means of database systems is one beneficial innovation; many scheduling systems do not provide such integration of information. The techniques discussed in Chapter 14 are particularly useful in this regard.

With regard to ease of use, the introduction of interactive scheduling systems, graphical output devices and automated data acquisition should produce a very different environment than has existed. In the past, scheduling was performed as a batch operation with output contained in lengthy tables of numbers. Updating of work progress and revising activity duration was a time consuming manual task. It is no surprise that managers viewed scheduling as extremely burdensome in this environment. The lower costs associated with computer systems as well as improved software make "user friendly" environments a real possibility for field operations on large projects.

Finally, information representation is an area which can result in substantial improvements. While the network model of project activities is an extremely useful device to represent a project, many aspects of project plans and activity inter-relationships cannot or have not been represented in network models. For example, the similarity of processes among different activities is usually unrecorded in the formal project representation. As a result, updating a project network in response to new information about a process such as concrete pours can be tedious. What is needed is a much more flexible and complete representation of project information. Some avenues for change along these lines are discussed in Chapter 15.

11.7 References

1. Bratley, Paul, Bennett L. Fox and Linus E. Schrage, A Guide to Simulation, Springer-Verlag, 1973.
2. Elmaghraby, S.E., Activity Networks: Project Planning and Control by Network Models, John Wiley, New York, 1977.
3. Jackson, M.J., Computers in Construction Planning and Control, Allen & Unwin, London, 1986.
4. Moder, J., C. Phillips and E. Davis, Project Management with CPM, PERT and Precedence Diagramming, Third Edition, Van Nostrand Reinhold Company, 1983.