Abstract
Time/cost trade-offs in project networks have been the subject of extensive research since the development of the critical path method (CPM) in the late 50s. Time/cost behaviour in a project activity basically describes the trade-off between the duration of the activity and its amount of non-renewable resources (e.g., money) committed to it. In the discrete version of the problem (the discrete time/cost trade-off problem), it is generally accepted that the trade-off follows a discrete non-increasing pattern, i.e., expediting an activity is possible by allocating more resources (i.e., at a larger cost) to it. However, due to its complexity, the problem has been solved for relatively small instances.
In this paper we elaborate on three extensions of the well-known discrete time/cost trade-off problem in order to cope with more realistic settings: time/switch constraints, work continuity constraints, and net present value maximization. We give an extensive literature overview of existing procedures for these problem types and discuss a new meta-heuristic approach in order to provide near-optimal heuristic solutions for the different problems. We present computational results for the problems under study by comparing the results for both exact and heuristic procedures. We demonstrate that the heuristic algorithms produce consistently good results for two versions of the discrete time/cost trade-off problem.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Akkan, C., Drexl, A., & Kimms, A. (2000a). Network decomposition for the discrete time/cost trade-off problem, part 1: models and bounding methods. In Proceedings of the seventh international workshop on project management and scheduling (pp. 29–31), Osnabrück, Germany, 17–19 April 2000.
Akkan, C., Drexl, A., & Kimms, A. (2000b). Network decomposition for the discrete time/cost trade-off problem, part 2: network decomposition and computational results. In Proceedings of the seventh international workshop on project management and scheduling (pp. 32–34), Osnabrück, Germany, 17–19 April 2000.
Bianco, L., & Speranza, M. G. (1990). Resource management in project scheduling. In Proceedings of the second international workshop on project management and scheduling, Compiègne, France, 20–22 June 1990.
Billstein, N., & Radermacher, F. J. (1977). Time-cost optimization. Methods of Operations Research, 27, 274–294.
Chen, Y. L., Rinks, D., & Tang, K. (1997). Critical path in an activity network with time constraints. European Journal of Operational Research, 100, 122–133.
Crowston, W. (1970). Network reduction and solution. Operations Research Quarterly, 21, 435–450.
Crowston, W., & Thompson, G. L. (1967). Decision CPM: a method for simultaneous planning, scheduling and control of projects. Operations Research, 15, 407–426.
De, P., Dunne, E. J., Ghosh, J. B., & Wells, C. E. (1995). The discrete time/cost trade-off problem revisited. European Journal of Operational Research, 81, 225–238.
De, P., Dunne, E. J., Ghosh, J. B., & Wells, C. E. (1997). Complexity of the discrete time/cost trade-off problem for project networks. Operations Research, 45, 302–306.
De Boer, R. (1998). Resource-constrained multi-project manage- ment—a hierarchical decision support system. PhD dissertation, Institute for Business Engineering and Technology Application, The Netherlands.
De Reyck, B., & Herroelen, W. (1996). On the use of the complexity index as a measure of complexity in activity networks. European Journal of Operational Research, 91, 347–366.
Deineko, V. G., & Woeginger, G. J. (2001). Hardness of approximation of the discrete time/cost trade-off problem. Operations Research Letters, 29, 207–210.
Demeulemeester, E., Elmaghraby, S. E., & Herroelen, W. (1996). Optimal procedures for the discrete time/cost trade-off problem in project networks. European Journal of Operational Research, 88, 50–68.
Demeulemeester, E., De Reyck, B., Foubert, B., Herroelen, W., & Vanhoucke, M. (1998). New computational results for the discrete time/cost trade-off problem in project networks. Journal of the Operational Research Society, 49, 1153–1163.
El-Rayes, K., & Moselhi, O. (1998). Resource-driven scheduling of repetitive activities. Construction Management and Economics, 16, 433–446.
Elmaghraby, S.E., & Herroelen, W. (1980). On the measurement of complexity in activity networks. European Journal of Operational Research, 5, 223–234.
Elmaghraby, S. E., & Kamburowski, J. (1992). The analysis of activity networks under generalized precedence relations. Management Science, 38, 1245–1263.
Elmaghraby, S. E., & Salem, A. (1982). Optimal project compression under quadratic cost functions. Applications of Management Science, 2, 1–39.
Elmaghraby, S. E., & Salem, A. (1984). Optimal linear approximation in project compression. IIE Transactions, 16(4), 339–347.
Erengüç, S. S., Tufekci, S., & Zappe, C. J. (1993). Solving time/cost trade-off problems with discounted cash flows using generalized Benders decomposition. Naval Research Logistics, 40, 25–50.
Falk, J. E., & Horowitz, J. L. (1972). Critical path problems with concave cost-time curves. Management Science, 19, 446–455.
Ford, L. R., & Fulkerson, D. R. (1962). Flows in networks. New Jersey: Princeton University Press.
Fulkerson, D. R. (1961). A network flow computation for project cost curves. Management Science, 7, 167–178.
Glover, F. (1986). Future paths for integer programming and links to artificial intelligence. Computers and Operations Research, 5, 533–549.
Gong, D. (1997). Optimization of float use in risk analysis-based network scheduling. International Journal of Project Management, 15(3), 187–192.
Goto, E., Joko, T., Fujisawa, K., Katoh, N., & Furusaka, S. (2000). Maximizing net present value for generalized resource constrained project scheduling problem. Working paper Nomura Research Institute, Japan.
Goyal, S. K. (1975). A note on the paper: a simple CPM time/cost trade-off algorithm. Management Science, 21, 718–722.
Harris, R. B., & Ioannou, P. G. (1998). Scheduling projects with repeating activities. Journal of Construction Engineering and Management, 124(4), 269–278.
Herroelen, W., & De Reyck, B. (1999). Phase transitions in project scheduling. Journal of Operational Research Society, 50, 148–156.
Herroelen, W., Demeulemeester, E., & Van Dommelen, P. (1997). Project network models with discounted cash flows: A guided tour through recent developments. European Journal of Operational Research, 100, 97–121.
Herroelen, W., Demeulemeester, E., & De Reyck, B. (1999). A classification scheme for project scheduling problems. In J. Weglarz (Ed.), Handbook on recent advances in project scheduling (Chap. 1, pp. 1–26). Amsterdam: Kluwer Academic.
Hindelang, T. J., & Muth, J. F. (1979). A dynamic programming algorithm for decision CPM networks. Operations Research, 27, 225–241.
Kamburowski, J., Michael, D. J., & Stallmann, M. F. M. (1992). Optimal construction of project activity networks. In Proceedings of the 1992 annual meeting of the Decision Sciences Institute (pp. 1424–1426), San Francisco, USA.
Kapur, K. C. (1973). An algorithm for the project cost/duration analysis problem with quadratic and convex cost functions. IIE Transactions, 5, 314–322.
Kelley, J. E. (1961). Critical path planning and scheduling: Mathematical basis. Operations Research, 9, 296–320.
Kelley, J. E., & Walker, M. R. (1959). Critical path planning and scheduling: an introduction. Ambler: Mauchly Associates.
Kolisch, R., Sprecher, A., & Drexl, A. (1995). Characterization and generation of a general class of resource-constrained project scheduling problems. Management Science, 41, 1693–1703.
Lamberson, L. R., & Hocking, R. R. (1970). Optimum time compression in project scheduling. Management Science, 16, B-597–B-606.
Moder, J. J., Phillips, C. R., & Davis, E. W. (1983). Project management with CPM, PERT and precedence diagramming (3rd ed.). New York: Van Nostrand Reinhold Company.
Patterson, J. H., & Harvey, R. T. (1979). An implicit enumeration algorithm for the time/cost trade-off problem in project network analysis. Foundations of Control Engineering, 6, 107–117.
Reda, R. M. (1990). RPM: repetitive project modelling. Journal of Construction Engineering and Management, 116(2), 316–330.
Robinson, D. R. (1975). A dynamic programming solution to cost/time trade-off for CPM. Management Science, 22, 158–166.
Schrage, L. (1995). LINDO: Optimization software for linear programming. Chicago: LINDO Systems.
Siemens, N. (1971). A simple CPM time/cost trade-off algorithm. Management Science, 17, B-354–B-363.
Siemens, N., & Gooding, C. (1975). Reducing project duration at minimum cost: a time/cost trade-off algorithm. OMEGA, 3, 569–581.
Skutella, M. (1998). Approximation algorithms for the discrete time-cost trade-off problem. Mathematics of Operations Research, 23, 909–929.
Vanhoucke, M. (2005). New computational results for the discrete time/cost trade-off problem with time-switch constraints. European Journal of Operational Research, 165, 359–374.
Vanhoucke, M. (2006). Work continuity constraints in project scheduling. Journal of Construction Engineering and Management, 132, 14–25.
Vanhoucke, M., Demeulemeester, E., & Herroelen, W. (2001). On maximizing the net present value of a project under renewable resource constraints. Management Science, 47, 1113–1121.
Vanhoucke, M., Demeulemeester, E., & Herroelen, W. (2002). Discrete time/cost trade-offs in project scheduling with time-switch constraints. Journal of the Operational Research Society, 53, 741–751.
Vercellis, C. (1990). Multi-project scheduling with time-resource-cost trade-offs: a tactical model. In Proceedings of the second international workshop on project management and scheduling, Compiègne, France, 20–22 June 1990.
Wiest, J. D., & Levy, F. K. (1977). A management guide to PERT/CPM: with GERT/PDM/DCPM and other networks. New Jersey: Prentice-Hall.
Yang, H. H., & Chen, Y. L. (2000). Finding the critical path in an activity network with time-switch constraints. European Journal of Operational Research, 120, 603–613.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Vanhoucke, M., Debels, D. The discrete time/cost trade-off problem: extensions and heuristic procedures. J Sched 10, 311–326 (2007). https://doi.org/10.1007/s10951-007-0031-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10951-007-0031-y