### The Time-Cost Tradeoff Problem

Participant: |
Martin Skutella |

**Project description:**

The Time-Cost Tradeoff Problem has first been studied almost fourty
years ago by J. E. Kelley and M. R. Walker. It has achieved the
attention of many researchers up to now. Within this context, we
consider projects given by a set of single activities and precedence
constraints on
these activities. The duration of each activity is variable. However,
the shorter the chosen duration is, the higher is the cost caused by
executing the activity. This defines the proper *time-cost
tradeoff*: short project durations correspond to high cost and vice
versa. Given a fixed budget (or deadline), one aims to find shortest
(resp. cheapest) schedules that do not violate the budget
(resp. deadline). In 1961 D. R. Fulkerson and J. E. Kelley gave an
efficient combinatorial algorithm for solving the Linear Time-Cost
Tradeoff Problem where the cost *c_j* of a single activity *j* is an
affine linear function of its chosen duration *x_j*.

Even more relevant for real world applications is the discrete variant
of the problem. In that case there is only a
finite number of alternative durations for each activity to choose
from. The importance of the Discrete Time-Cost Tradeoff Problem gets
evident if we try to model projects with discrete resources like
manpower that have to be assigned to certain processes. Unfortunately, the
problem is known to be *NP*-hard. In the past there have been several
attempts to find good enumerative algorithms to solve the
problem. Using another type of approach, we developed the first
polynomial-time approximation algorithms for the Discrete
Time-Cost Tradeoff Problem with constant performance guarantee on
various special classes of instances.

One main idea behind those algorithms is to construct a linear relaxation
of the problem, to compute its optimum solution and then to apply a somewhat
subtle rounding step which is guided by another linear project in order to get
a provably good solution for the discrete problem. Figure 1 illustrates this
procedure for a single activity *j*.

Specifically, we consider the problem of finding an optimal schedule
for a project with a given budget that must not be overspent. We have found a
polynomial time approximation algorithm with a performance ratio of
*3/2* for projects with alternatives *0/1* or *0/2* for
the duration of each activity. This means that our algorithm computes
a feasible schedule whose duration is bounded by *3/2* times the optimum
duration. Moreover, we can show that this is the best approximation for
the problem that can be found, unless *P=NP*. We also have kind of
generalized our result to arbitrary instances, but it is an
open problem whether or not there exists an approximation algorithm with
constant performance guarantee for arbitrary instances.

We get another type of approximation result (bicriteria approximation) with
constant performance guarantee, if we allow slight violation of a given
budget or deadline. We can, for example, compute schedules that violate a
given budget by a factor of at most *2* and
whose duration is bounded by twice the optimum duration for this budget.

**References:**

- Martin Skutella,
*Approximation Algorithms for the Discrete Time-Cost Tradeoff Problem*, in M. Saks et al., editors, Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, Society of Industrial and Applied Mathematics (1997), 501-508. (click here)