A Tree Characterization of Crashing Options in a Serial Project

Consider a serial project where the durations of each task are either short or long, each occurring with a given probability. In addition to these normal durations, suppose that we have the option to crash each task. In particular, suppose that the crash decision for each task is simple—to crash it or not to crash it. Crashing a task costs a given amount of money, called its crash cost, above and beyond the normal cost of the task. As with normal durations, the durations of a task under crashing are either short or long. For simplicity of presentation, we assume that the probabilities of long and short durations under crashing are the same as in the normal case. However, under crashing, the duration of a task in a "crash mode" is generally smaller than its respective duration in a "normal mode." A decision to crash a task must be made in advance of the start of the task by a minimum amount of time, called its lead-time. Figure 1 illustrates such a situation when lead-times are zero.

Figure 1: Simple Serial Project with Zero Lead-Times

A serial project having three tasks is depicted in Figure 1. To interpret the figure, consider task B. This task will take either two or thirteen days to complete in the normal mode, each with a probability of 0.5. In a crash mode, under which an additional $50 crash cost is incurred, it will take either one or seven days, each again with a probability of 0.5. Since B has a lead-time of zero, a decision to crash B can be made when task B begins.

Figure 2 depicts a decision tree for this example. (Actually because of size constraints, Figure 2 only gives the top half of the tree corresponding to not crashing task A. The bottom half, corresponding to crashing A, is similar.) We illustrate the notation in this tree for task B (with the notation for other tasks being analogous): "B no" designates a decision not to crash B and "B yes" means to crash it; "B NS" designates a normal, short duration and "B NL" designates a normal, long duration; "B CS" designates a short duration under crashing, while "B CL" means a long duration under crashing.

Figure 2: Simple Serial Project with Nonzero Lead-Times

Suppose that the project in Figure 1 has a finishing target time of eighteen days and that a project duration exceeding this target will incur a penalty cost of $30 per day. Further, suppose that there are no other relevant costs and that the objective is to make crash decisions so as to minimize expected total cost. Using standard decision analysis, it can be verified that the optimal solution is to crash task B under all conditions, and only (as a contingency plan) to crash C in the following situations: when the duration of task A is long; or when the duration of task A is short but the duration of task B is long.

Note that each path in the decision tree in Figure 2 has one decision node at the start of every task—namely whether or not to crash it. We now add the possibility of a lead-time requirement that changes this characteristic.

Let everything be the same as in Figure 1 except that the lead-time of task B, as well as task C, is six days. Thus, if a decision to crash C is made at the start of task C then a six-day delay will occur before task C can begin. On the other hand, if you decided to crash C at the beginning of the project, then there might be little or no lead-time delay, but short durations for A and B could make crashing C unnecessary or uneconomical.

As evident from this example, a crashing decision under a lead-time is not just "whether to crash or not to crash", but also "when to crash." Making this decision requires knowing when information is available to the decision-maker about task durations.

In our analysis of such a problem, we assume that the decision-maker does not know which of the two possible task times (long or short) will occur until the short task time of the respective task has elapsed. (However, our modeling approach is valid under other scenarios regarding points in time when it is known which task times will apply.) Under the previous assumption, we have the following result regarding points in time when crash decisions are to be considered.

Sufficiency Result

For each task j, it is sufficient to consider the decision to crash the task at the beginning of the project, and at those points in time represented by the end of short duration completions of each task i preceding task j. Furthermore, crashing task j at a predecessor task i would only be considered if the duration of task i was not short.

This result follows from the fact that new information relevant to a crash decision will occur at only those points in time identified in the result. If the duration of a predecessor task i was short, then this result cannot motivate crashing task j since a short duration is the best outcome that could have occurred. As an illustration, in Figure 2 it will be sufficient to consider the decision to crash task C at the beginning of the project, at the point in time representing a short duration of task A if it happens that the duration of task A is long, and at the point representing a short duration of task B if it happens that the duration of task B is long.

Using the above sufficiency result, we can characterize the set of crashing decisions as a decision tree. Figure 3 denotes a decision tree for a simpler version of Figure 2—an example using only tasks A and B. In addition to the previous notation, we let "B LTD" designate the lead-time delay in the start time of B due to B's lead-time. (We will define the concept of a lead-time delay shortly, but for the moment it is convenient to think of it as a potential delay in project length due to the fact that the crashing decision has a positive lead-time.) Further, we sometimes break a long duration of a task into two components, where the duration of the first component equals the short duration of the task and where the duration of the second component equals the difference between its long and short durations. For example, "A1 CL" is the first component of A under a crash mode and its duration equals five, whereas "A2 CL" is the second component whose duration equals ten (i.e., 15 – 5). Finally, note that the durations of the "tasks" need to be computed in a tree corresponding to lead-time delays of tasks. We address this issue in the next section of the chapter.

Figure 3: Effect of Changes in Lead-Time

Observe that Figure 3 is a general tree for two-activity serial projects (under our assumptions) since it includes all the logical possibilities that can occur. Indeed, this general tree includes all possible choices for probabilities, costs, lead-times, and so on. Furthermore, the pattern of such a general tree is clear for any serial project. At the beginning of the project, crash decisions are made (either to crash or not to crash at this time) for each task in the project. Then, we have the first activity duration. If this duration is short, it is immediately followed by the second activity duration. If the first activity duration is long, this fact will be known only at the point in time representing an early duration. At this point, we reconsider crashing decisions for all future tasks for which we have not decided earlier to crash. We let T denote this general tree.

Not surprisingly the general tree for the three tasks in Figure 2 is much larger and, therefore, is difficult to display in a figure. Figure 4 gives a section of this tree corresponding to when no tasks are crashed at the beginning of the project. Since we can choose to either crash or not to crash each of three tasks at the beginning of the project, observe that Figure 4 represents just one of eight (= 2³) sections of the decision tree for Figure 2.

Figure 4: Effect of Changes in Indirect/Penalty Cost

The tree in Figure 2 can be viewed as a special case of the general tree when lead-times are zero. Further, other choices of lead-times can yield other trees that are special cases of the general tree. In this chapter, we focus on the general tree since it is applicable to any serial problem.