Combinatorial Optimization & Graph Algorithms

The Time-Cost Tradeoff Problem

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.

Figure 1: Constructing provably good solutions by relaxing and rounding

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.

• 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)