×

Scheduling a project to maximize its net present value: An integer programming approach. (English) Zbl 0769.90053

Summary: We describe an integer programming algorithm for determining scheduled start and finish times for the activities of a project subject to resource limitations during each period of the schedule duration. The objective is to maximize the net present value of the project to the firm. A depth-first branch and bound solution procedure searches over the feasible set of finish or completion times for each of the activities of the project. Fathoming criteria based upon the concept of a network cut originally developed to solve the duration minimization version of this problem are extended in this paper to solve the net present value problem. These fathoming decision rules prevent many potentially inferior solutions from being explicitly evaluated. Computational experience reported demonstrates the efficacy of the approach.

MSC:

90B35 Deterministic scheduling theory in operations research
90C10 Integer programming
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Christofides, N.; Alvarez-Valdes, R.; Tamarit, J. M., Project scheduling with resource constraints: A branch and bound approach, European Journal of Operational Research, 29, 262-273 (1987) · Zbl 0614.90056
[2] Davis, E. W.; Heidorn, G. E., An algorithm for optimal project scheduling under multiple resource constraints, Management Science, 17/12, 803-816 (August 1971)
[3] Davis, E. W.; Patterson, J. H., A comparison of heuristic and optimum solutions in resource-constrained project scheduling, Management Science, 21/8, 944-955 (April 1975)
[4] Doersch, R. H.; Patterson, J. H., Scheduling a project to maximize its net present value: A zero-one programming approach, Management Science, 23/8, 882-889 (1977) · Zbl 0354.90043
[5] Demeulemeester, E.; Herroelen, W., A decision support system for resource-constrained project scheduling (1990), Department of Applied Economic Sciences, Katholieke Universiteit of Leuven: Department of Applied Economic Sciences, Katholieke Universiteit of Leuven Leuven, Belgium
[6] Geoffrion, A. M.; Marsten, R. E., Integer programming algorithms: A framework and state of the art survey, Management Science, 18/9, 465-491 (1972) · Zbl 0238.90043
[7] Grinold, R. C., The payment scheduling problem, Naval Research Logistics Quarterly, 19/1, 123-136 (1972) · Zbl 0252.90034
[8] Padman, R.; Smith-Daniels, D. W.; Smith-Daniels, V. L., Heuristic scheduling of resource-constrained projects with cash flows: An optimization-based approach, (Working Paper 90-6 (1990), School of Urban and Public Affairs, Carnegie Mellon University) · Zbl 0890.90108
[9] Patterson, J. H., A comparison of exact approaches for solving the multiple constrained resource, project scheduling problem, Management Science, 30/7, 854-867 (1984)
[10] Patterson, J. H.; Roth, G., Scheduling a project under multiple resource constraints: A zero-one programming approach, AIIE Transactions, 8, 449-456 (1976)
[11] Patterson, J. H.; Slowinski, R.; Talbot, F. B.; Weglarz, J., An algorithm for a general class of precedence and resource constrained scheduling problems, (Slowinski, R.; Weglarz, J., Studies in production and Engineering Economics, Volume 9: Advances in Project Scheduling (1989), Elsevier: Elsevier Amsterdam), 3-28
[12] Patterson, J. H.; Slowinski, R.; Talbot, F. B.; Weglarz, J., Computational experience with a backtracking algorithm for solving a general class of precedence and resource constrained scheduling problems, European Journal of Operational Research, 49, 68-79 (1990) · Zbl 1403.90678
[13] Pinder, J. P.; Marucheck, A. S., Maximizing project net present value: categorization of heuristic scheduling performance (1990), School of Business, University of Wisconsin: School of Business, University of Wisconsin Madison, Working Paper
[14] Russell, A. H., Cash flows in networks, Management Science, 16/5, 357-372 (1970) · Zbl 0187.18201
[15] Russell, R. A., A comparison of heuristics for scheduling projects with cash flows and resource restrictions, Management Science, 32/10, 1291-1300 (1986)
[16] Smith-Daniels, D. E.; Smith-Daniels, V. L., Maximizing the net present value of a project subject to material and capital constraints, Journal of Operations Management, 7/1, 33-45 (1987)
[17] Stinson, J. P., A branch and bound algorithm for a general class of resource-constrained scheduling problems, (AIIE Conference Proceedings. AIIE Conference Proceedings, Las Vegas, NV (1975)), 337-342
[18] Stinson, J. P.; Davis, E. W.; Khumawala, B. M., Multiple resource-constrained scheduling using branch and bound, AIIE Transactions, 10/3, 252-259 (1978)
[19] Talbot, F. B., An Integer Programming algorithm for the resource-constrained, project scheduling problem, (Ph.D. Dissertation (1976), Pennsylvania State University)
[20] Talbot, F. B.; Patterson, J. H., An efficient integer programming algorithm with network cuts for solving resource-constrained scheduling problems, Management Science, 24/11, 1163-1174 (1978) · Zbl 0395.90036
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.