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 NPhard. 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 $ for projects with alternatives O/l or O/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 log2e + 5. Here, e is the ratio of the maximum allowed duration of any activity to the minimum allowed non-zero duration of any activity.
For this problem, Skutella REF proposed the first approximation algorithm under budget constraints which achieves an approximation ratio of O (log r ), where r is the ratio of the maximum duration of any activity to the minimum one.
Approximation algorithms for the discrete time-cost tradeoff problem
SODA '97
Computer Science Mathematics