×

Solving time/cost trade-off problems with discounted cash flows using generalized Benders decomposition. (English) Zbl 0766.90055

Summary: We consider a project scheduling problem where there are cash flows throughout the life of the project and where shorter activity duration can be attained by incurring greater direct costs. In particular, the objective of this problem is to determine the activity durations and a schedule of activity start times so that the net present value of cash flows is maximized. We formulate this problem as a mixed-integer nonlinear program which is amenable to solution using the generalized Benders decomposition technique developed by Geoffrion. We test the algorithm on 140 project scheduling problems, the largest of which contains 30 nodes and 64 activities. Our computational results are quite encouraging inasmuch as 123 of the 140 problems require less than 1 CPU second of solution time.

MSC:

90B90 Case-oriented studies in operations research
90C90 Applications of mathematical programming
90B35 Deterministic scheduling theory in operations research
90-08 Computational methods for problems pertaining to operations research and mathematical programming
90C11 Mixed integer programming
90C30 Nonlinear programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aquilano, Journal of Operations Management 1 pp 57– (1980)
[2] Benders, Numerische Mathematik 4 pp 238– (1962)
[3] Doersch, Management Science 23 pp 882– (1977)
[4] and , Flows in Networks, Princeton University Press, Princeton, NJ, 1962.
[5] Geoffrion, Journal of Optimization Theory and Applications 10 pp 237– (1972)
[6] Grinold, Naval Research Logistics Quarterly 19 pp 123– (1972)
[7] and , ”Project Scheduling Problems: A Survey,” unpublished manuscript (1991).
[8] ”Maximizing the Net Present Value in Activity Networks Under Generalized Precedence Relations,” Proceedings of 21st DSI Annual Meeting, San Diego, CA, November 1990.
[9] Russell, Management Science 16 pp 357– (1970)
[10] Russell, Management Science 32 pp 1291– (1986)
[11] ”A Flow-Preserving Algorithm for the Time-Cost Tradeoff Problem,” IIE Transactions, 109–113 (June 1982).
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.