×
De, Prabuddha; Dunne, E. James; Ghosh, Jay B.; Wells, Charles E.

The discrete time-cost tradeoff problem revisited. (English) Zbl 0927.90046

Eur. J. Oper. Res. 81, No. 2, 225-238 (1995).
Summary: In the management of a project, the project duration can often be compressed by accelerating some of its activities at an additional expense. This is the so-called time-cost tradeoff problem which has been studied extensively in the project management literature. However, the discrete version of the problem, encountered frequently in practice and also useful in modeling general time-cost relationships, has received only scant and sporadic attention. Prompted by the present emphasis on time-based competition and recent developments concerning problem complexity and solution, we reexamine this important problem in this paper. We begin by formally describing the problem and discussing the difficulties associated with its solution. We then provide an overview of the past solution approaches, identify their shortcomings, and present a new solution approach. Next, we present network decomposition/ reduction, as a convenient basis for solving the problem and analyzing its difficulty. Finally, we point to several new directions for future research, where we highlight the need for developing and evaluating effective procedures for solving the general time-cost tradeoff problem. To the best of our knowledge, the popular project management software packages do not include provisions for time-cost tradeoff analyses. Our work, we hope, will provide the groundwork and an incentive for alleviating this deficiency.

Cited in 37 Documents

MSC:

90B35 Deterministic scheduling theory in operations research

Keywords:

project duration; project management
PDF BibTeX XML Cite
\textit{P. De} et al., Eur. J. Oper. Res. 81, No. 2, 225--238 (1995; Zbl 0927.90046)
Full Text: DOI

References:

[1] Badiru, A. B., Project Management Tools for Engineering and Management Professionals (1991), Industrial Engineering and Management Press: Industrial Engineering and Management Press Norcross, GA
[2] Bein, W. W.; Kamburowski, J.; Stallmann, M. F.M., Optimal reduction of two-terminal directed acyclic graphs, SIAM Journal on Computing, 21, 1112-1129 (1992) · Zbl 0768.68119
[3] Blackburn, J. D., Time-based Competition: The Next Battleground in American Manufacturing (1991), Irwin: Irwin Homewood, IL
[4] Bockerstette, J. A.; Shell, R. L., Time Based Manufacturing (1993), Industrial Engineering and Management Press: Industrial Engineering and Management Press Norcross, GA
[5] Buer, H.; Möhring, R. H., A fast algorithm for the decomposition of graphs and posets, Mathematics of Operations Research, 8, 170-184 (1983) · Zbl 0517.05057
[6] Butcher, W. S., Dynamic programming for project cost-time curves, (Journal of the Construction Division, Proceedings of the ASCE, 93 (1967)), 59-73
[7] Crowston, W. B., Decision CPM: Network reduction and solution, Operational Research Quarterly, 21, 435-452 (1970) · Zbl 0304.90042
[8] Crowston, W. B.; Thompson, G. L., Decision CPM: A method for simultaneous planning, scheduling, and control of projects, Operations Research, 15, 407-426 (1967)
[9] De, P.; Ghosh, J. B.; Wells, C. E., Heuristic estimation of the efficient frontier for a bicriteria scheduling problem, Decision Sciences, 23, 596-609 (1992)
[10] De, P.; Dunne, E. J.; Ghosh, J. B.; Wells, C. E., Complexity of the discrete time-cost tradeoff problem for project networks, Operations Research (1992), submitted to
[11] Demeulemeester, E.; Herroelen, W.; Elmaghraby, S. E., An optimal procedure for the discrete time/cost trade-off scheduling problem in project networks, (Working Paper #9337 (1993), Department of Applied Economics, Katholieke Universiteit Leuven) · Zbl 0913.90168
[12] Elmaghraby, S. E., Activity Networks: Project Planning and Control by Network Models (1977), Wiley: Wiley New York · Zbl 0385.90076
[13] Elmaghraby, S. E., Resource allocation via dynamic programming in activity networks, European Journal of Operational Research, 64, 199-215 (1993) · Zbl 0769.90049
[14] Fisher, M. L., An applications oriented guide to Lagrangian relaxation, Interfaces, 15, 10-21 (1985)
[15] Fulkerson, D. R., A network flow computation for project cost curves, Management Science, 7, 167-178 (1961) · Zbl 0995.90519
[16] Garey, M. R.; Johnson, d. S., Computers and Intractability (1979), Freeman: Freeman New York · Zbl 0411.68039
[17] Harvey, R. T.; Patterson, J. H., An implicit enumeration algorithm for the time/cost tradeoff problem in project network analysis, Foundations of Control Engineering, 4, 107-117 (1979) · Zbl 0424.90035
[18] Hindelang, T. J.; Muth, J. F., A dynamic programming algorithm for Decision CPM networks, Operations Research, 27, 225-241 (1979) · Zbl 0396.90097
[19] Hopcroft, J.; Karp, R., An \(n^{52}\) algorithm for maximum matchings in bipartite graphs, SIAM Journal on Computing, 2, 225-231 (1973) · Zbl 0266.05114
[20] Kelley, J. E., Critical-path planning and scheduling: Mathematical basis, Operations Research, 9, 296-320 (1961) · Zbl 0098.12103
[21] Meyer, W. L.; Shaffer, L. R., Extending CPM for multiform project time-cost curves, (Journal of the Construction Division, Proceedings of the ASCE, 91 (1965)), 45-65
[22] Moder, J. J.; Phillips, C. R.; Davis, E. W., Project Management with CPM, PERT and Precedence Diagramming (1983), Van Nostrand Reinhold: Van Nostrand Reinhold New York
[23] Muller, J. H.; Spinrad, J., Incremental modular decomposition, Journal of the ACM, 36, 1-19 (1989) · Zbl 0671.68030
[24] Panagiotakopoulos, D., A CPM time-cost computational algorithm for arbitrary activity cost functions, INFOR, 15, 183-195 (1977) · Zbl 0363.90055
[25] Parikh, S. C.; Jewell, W. S., Decomposition of project networks, Management Science, 11, 444-459 (1965) · Zbl 0129.11911
[26] Robinson, D. R., A dynamic programming solution to cost-time tradeoff for CPM, Management Science, 22, 158-166 (1975) · Zbl 0313.90065
[27] Schwarze, J., An algorithm for hierarchical reduction and decomposition of a directed graph, Computing, 25, 47-57 (1980) · Zbl 0419.05043
[28] Sidney, J. B.; Steiner, G., Optimal sequencing by modular decomposition: Polynomial algorithms, Operations Research, 34, 606-612 (1986) · Zbl 0609.90068
[29] Tavares, L. V., A multi-stage non-deterministic model for project scheduling under resource constraints, European Journal of Operational Research, 49, 92-101 (1990) · Zbl 1403.90296
[30] Tufekci, S., On the complexity of time cost tradeoff problems, (Working Paper #93-20 (1993), Department of Industrial and Systems Engineering, University of Florida: Department of Industrial and Systems Engineering, University of Florida Gainesville, FL) · Zbl 0567.90029
[31] Valdes, J.; Tarjan, R. E.; Lawler, E. L., The recognition of series-parallel digraphs, SIAM Journal on Computing, 11, 298-313 (1982) · Zbl 0478.68065
[32] Wu, S. D.; Storer, R. H.; Chang, P. C., One-machine rescheduling heuristics with efficiency and stability as criteria, Computers & Operations Research, 20, 1-14 (1993) · Zbl 0759.90049
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.