Reducing project duration at minimum cost: A time-cost tradeoff algorithm

The problem of reducing project duration efficiently arises frequently, routinely, and repetitively in government and industry. Siemens [1] has presented an inherently simple time-cost tradeoff algorithm (SAM--for Siemens Approximation Method) for determining which activities in a project network must be shortened to meet an externally imposed (scheduled) completion date (which occurs prior to the current expected completion date). In that paper the network activities of the example problem all have constant cost-slopes. Siemens mentions that the algorithm can be used where the activities have (convex) nonlinear cost-slopes--instead of just one cost-slope and one supply (time available for shortening) for each activity, there can be multiple cost-slope/supply pairs for each activity. This technique is illustrated in this paper. Also illustrated here is an improvement suggested by Goyal [2]. In step 12 of the original algorithm Siemens suggests a review of the solution obtained by the first eleven steps to eliminate any unnecessary shortening. Goyal's modification does this systematically during application of the algorithm by de-shortening (partially or totally) selected activities which were shortened in a prior iteration. He claims that, empirically at least, the technique always yields an optimal solution. Our experience verifies this claim (given the assumption of convex cost functions). The authors have modified the original algorithm so that the requirement for convex cost functions can now be relaxed. Unfortunately, this modification is made only at the expense of simplicity. To further complicate matters we found that Goyal's technique does not always yield an optimal solution when concave functions are involved and thus still another modification was required. These are discussed in detail below. Finally, we discuss the applicability of the algorithm to situations involving discrete time-cost functions.