Approximation Algorithms for the Discrete Time-Cost Tradeoff Problem

References

• Bertsimas D. , Teo C. , Vohra R. , Cunningham W. H. , McCormick S. T. , Queyranne M. On dependent randomized rounding algorithms. Integer Programming and Combinatorial Optimization (1996) (Springer, Berlin) 330 344 . Vol. 1084 of Lecture Notes in Computer Science Crossref, Google Scholar
• Chekuri C. S. , Motwani R. , Natarajan B. , Stein C. Approximation techniques for average completion time scheduling. Proc. 8th Annual ACM-SIAM Sympos. Discrete Algorithms (1997) 609 618 Google Scholar
• De P. , Dunne E. J. , Ghosh J. B. , Wells C. E. The discrete time-cost tradeoff problem revisited. Eur. J. Oper. Res. (1995) 81 225 238 Crossref, Google Scholar
• De P. , Dunne E. J. , Ghosh J. B. , Wells C. E. Complexity of the discrete time-cost tradeoff problem for project networks. Oper. Res. (1997) 45 302 306 Link, Google Scholar
• Fulkerson D. R. A network flow computation for project cost curves. Management Sci. (1961) 7 167 178 Link, Google Scholar
• Goemans M. X. Improved approximation algorithms for scheduling with release dates. Proc. 8th Annual ACM-SIAM Sympos. on Discrete Algorithms (1997) 591 598 Google Scholar
• Goemans M. X. , Queyranne M. , Schulz A. S. , Skutella M. , Wang Y. Single machine scheduling with release dates. (1998) . (To appear) Google Scholar
• Goldberg A. , Tarjan R. E. A new approach to the maximum flow problem. J. Assoc. Comput. Mach. (1988) 35 921 940 Crossref, Google Scholar
• Harvey R. T. , Patterson J. H. An implicit enumeration algorithm for the time/cost tradeoff problem in project network analysis. Found. Control Engrg. (1979) 4 107 117 Google Scholar
• Hindelang T. J. , Muth J. F. A dynamic programming algorithm for Decision CPM networks. Oper. Res. (1979) 27 225 241 Link, Google Scholar
• Kelley J. E. Critical path planning and scheduling: Mathematical basis. Oper. Res. (1961) 9 296 320 Link, Google Scholar
• Kelley J. E. , Walker M. R. Critical Path Planning and Scheduling: An Introduction (1959) (Mauchly Associates, Inc., Ambler, Pennsylvania) Crossref, Google Scholar
• Krishnamoorthy M. , Deo N. Complexity of the minimum-dummy-activities problem in a PERT network. Networks (1979) 9 189 194 Crossref, Google Scholar
• Möhring R. H. , Radermacher F. J. , Slowinski R. , Weglarz J. The order-theoretic approach to scheduling: The deterministic case. Advances in Project Scheduling (1989) (Elseviers Science Publ., Amsterdam) 29 66 Crossref, Google Scholar
• Padberg M. Linear Optimization and Extensions (1995) (Springer, Berlin) Google Scholar
• Panagiotakopoulos D. A CPM time-cost computational algorithm for arbitrary activity cost functions. INFOR (1977) 15 183 195 Google Scholar
• Phillips S. , Dessouky M. I. Solving the project time/cost tradeoff problem using the minimal cut concept. Management Sci. (1977) 24 393 400 Link, Google Scholar
• Robinson D. R. A dynamic programming solution to cost-time tradeoff for CPM. Management Sci. (1975) 22 158 166 Link, Google Scholar
• Schulz A. S. , Skutella M. , Rolim J. Random-based scheduling: New approximations and LP lower bounds. Randomization and Approximation Techniques in Computer Science (1997) (Springer, Berlin) 119 133 . Vol. 1269 of Lecture Notes in Computer Science Crossref, Google Scholar
• Shmoys D. B. , Tardos E. , Aardal K. I. Approximation algorithms for facility location problems. Proc. 29th Annual ACM Sympos. on t199he Theory of Comput. (1997) 265 274 Google Scholar
• Skutella M. Approximation and randomization in scheduling. (1998) . Ph.D. thesis Technical University of Berlin, Germany Google Scholar