Approximation Algorithms for the Discrete Time-Cost Tradeoff Problem

To appear in Mathematics of Operations Research.

An extended abstract appeared in Michael Saks et al., editors, Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'97). Society of Industrial and Applied Mathematics (1997), 501-508.

not available

not available

Due to its obvious practical relevance, the Time-Cost Tradeoff Problem has achieved the attention of many researchers over the last thirty years. 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.

If the cost of a single activity depends linearly on the chosen duration, the Time-Cost Tradeoff Problem can exactly be solved in polynomial time. However, its discrete variant is known to be NP-hard. Hence, in the past there have been several heuristic attempts to find "good" algorithms to solve this problem. In this paper we present the first polynomial-time approximation algorithms for the Discrete Time-Cost Tradeoff Problem with constant performance guarantee on various special classes of instances.

Specifically, we consider the problem of finding an optimal schedule for a project with a given budget that must not be overspent. We give 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. Moreover, we can show that this is the best approximation that can be found, unless P=NP. Finally, we kind of generalize our result to arbitrary projects by giving an approximation algorithm with a performance guarantee 3}{2}log₂ell+ 7}{2}. Here, ell is the ratio of the maximum difference between allowed durations of any activity to the minimum difference.

Download as [PDF] [ps.gz]