Impact of Changes in Lead-Time and Indirect Cost

For an increase in lead-time of a task beyond its slack, we can expect the project cost to increase. What is the nature of this increase? Of course, with the indirect cost table given in Table 1, the expected cost will be a nondecreasing, nonconvex, piecewise-linear function of lead-time. However, even if indirect cost increases as a linear function of project duration, the following figure illustrates that expected project cost is still a nondecreasing, nonconvex, piecewise-linear function of lead-time.

Table 1: Indirect Cost Table

Days	7	8	9	10	11	12	13	14	15	16
$	200	260	286	288	290	292	296	298	300	304
Days	17	18	19	20	21	22	23	24	25	26
$	316	320	324	326	328	330	340	350	360	368
Days	27	28	29	30	31	32	33	34	35	36
$	374	380	390	400	410	420	432	440	460	480
Days	37	38	39	40	41	42	43
$	500	580	582	584	586	588	600

Consider a modification of the second example where the indirect cost is $30 per day multiplied by project duration. The solution (strategy) that minimizes expected cost is to crash A, B, and C at the beginning of the project, corresponding to an expected cost of $705. This cost is derived as follows. The cost of crashing all three tasks is $225. Since tasks A and B are crashed, if they both realize short durations, task C still cannot start until time six since C's lead-time is six. With this fact, it can be verified that the expected project duration for this strategy is sixteen days, leading to an indirect cost of $480. For this strategy, activity C has a lead-time slack of one, which is evident since activity B's lead-time of six means that C cannot start until day seven at the earliest and since the lead-time of C is six. For increases in C's lead-time beyond seven, cost will increase, as depicted in Figure 5.

The shape of this cost curve can be readily understood. With a lead-time of six for C, tasks A, B, and C are all crashed in a minimum-cost solution. Beyond seven, increases in the lead-time of C will result in an increased project duration in the case when A has a duration of five and B has a duration of one. But this case occurs with a probability of 0.25 and so expected cost will increase at a rate of 0.25($30) = $7.50 per day. Cost will continue increasing at this rate until the lead-time of C is thirteen, at which point the expected cost is $750. At this point delay will occur when B takes on either a long or a short duration, so the cost will begin to increase at 0.5($30) or $15 per day. At the point when lead-time is 13.67 the optimal solution changes to one where only B and C are crashed. Now, with A not crashed, the project length will increase only when the durations of A and B are both short. This occurs with probability of 0.25, and so the rate of increase in expected project cost is again $7.50 per day. This rate will continue until the lead-time is 16 1/3, at which point we have an alternative optimal solution of crashing A and B, but not C. Above this point, C will remain "uncrashed" and so further increases in C's lead-time will not affect the expected project cost. Thus, the expected project cost stays constant at $780, starting at day 16 1/3.

In general, the shape of the expected cost curve, as in Figure 5, can be explained as follows. Consider any path P in some strategy subtree. As the lead-time of an activity j on the path increases, the length of the path will remain constant until its lead-time slack, S(j,P), becomes zero. Then the path length, and hence the cost (under the assumption of linear indirect cost) will increase linearly. Since the expected cost of a solution strategy is the expected cost over each of the paths in its strategy subtree, the expected project cost of each strategy will be a nondecreasing, piecewise-linear, convex function of lead-time. To find an optimal strategy the backward folding of the tree finds the minimum cost solution over all such strategies. Thus, the general shape of the cost curve will be the minimum of these convex functions, which is generally nonconvex. Typically, it will be flat until slack is exhausted, then increase in a piecewise-linear, nonconvex fashion, and then become flat again when the selected task is not crashed in an optimal strategy—hence the "S-shape" in Figure 5.

We now turn our attention to the impact of changes in project indirect/penalty costs. In what follows, we systematically examine the impact of changes in the cost-per-day rate on the overall project cost.

Consider a modification of the second example where crashing costs and lead-times are fixed, but project indirect cost is simply proportional to the project duration, namely it equals an indirect cost rate multiplied by duration. If this rate equals zero, then obviously the optimal solution is to crash nothing and to incur a project cost of zero. As the indirect cost rate increases, crashing of tasks may be optimal. Figure 6 illustrates how expected project cost changes as this indirect cost rate changes. Observe that it is an increasing, concave, piecewise-linear function.

Figure 6: Expected Project Cost and Indirect Cost Rate

The rationale for the shape of Figure 6 is readily apparent. As the indirect cost rate increases from zero, expected project cost will increase with a slope equal to the average project length of twenty-nine under regular, i.e., noncrashed, durations for the tasks. This continues until the indirect rate reaches $14.28 at which point we have an alternative optimal solution, which involves crashing task B. Since under this solution the expected project duration is 25.5, this becomes the slope of the expected project cost until indirect cost reaches $15. Then a new solution of the crashing of tasks B and C becomes optimal with an expected project duration of 20.5, which becomes the new slope until the indirect rate reaches $22.22. After this, the optimal solution is to crash all tasks and the expected project duration, or slope, is 16.

In general, the shape of this cost curve is not surprising. For each strategy the expected cost increases as a linear function. Since the folding back process effectively finds the minimum over all strategy subtrees, it involves taking the minimum of a collection of linear functions—which is an increasing, piecewise-linear, concave function.