×

An optimal procedure for the resource-constrained project scheduling problem with discounted cash flows and generalized precedence relations. (English) Zbl 0909.90175

Summary: We consider the resource-constrained project scheduling problem (RCPSP) with discounted cash flows and generalized precedence relations (RCPSPDC-GPR). The RCPSPDC-GPR extends the RCPSP to (a) arbitrary minimal and maximal time lags between the starting and completion times of activities and (b) the non-regular objective function of maximizing the net present value of the project with positive and/or negative cash flows associated with the activities. To the best of our knowledge, the literature on the RCPSPDC-GPR is completely void. We present a depth-first branch-and-bound algorithm in which the nodes in the search tree represent the original project network extended with extra precedence relations which resolve a number of resource conflicts. These conflicts are resolved using the concept of minimal delaying modes, which is an extension of the notion of minimal delaying alternatives originally developed for the RCPSP. An upper bound on the project net present value as well as several dominance rules are used to fathom large portions of the search tree. Extensive computational experience on a randomly generated benchmark problem set is reported.

MSC:

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

References:

[1] Jr., J. E. Kelley; Walker, M. R.: Critical path planning and scheduling. Proceedings of the eastern joint computing conference 16, 160-172 (1959)
[2] Malcolm, D. G.; Roseboom, J. H.; Clark, C. E.; Fazar, W.: Applications of a technique for R and D program evaluation (PERT). Operations research 7, 646-669 (1959) · Zbl 1255.90070
[3] Elmaghraby, S. E.; Kamburowski, J.: The analysis of activity networks under generalized precedence relations. Management science 38, 1245-1263 (1992) · Zbl 0758.90044
[4] Bartusch, M.; Möhring, R. H.; Radermacher, F. J.: Scheduling project networks with resource constraints and time windows. Annals of operations research 16, 201-240 (1988) · Zbl 0693.90047
[5] De Reyck, B.: Project scheduling under generalized precedence relations–A review: part 1 and 2. Research reports 9517 and 9518 (1995)
[6] Neumann, K.; Schwindt, C.: Activity-on-mode networks with minimal and maximal time lags and their application to make-to-order-production. OR spectrum 19, 205-217 (1997) · Zbl 0885.90058
[7] Kerbosh, J. A. G.M.; Schell, H. J.: Network planning by the extended METRA potential method. Report KS-1.1 (1975)
[8] Roy, B.: Graphes et ordonnancement. Revue française de recherche opérationelle, 323-333 (1962)
[9] Crandall, K. C.: Project planning with precedence lead/lag factors. Project managemant quarterly 4, 18-27 (1973)
[10] Elmaghraby, S. E.: Activity networks: project planning and control by network models. (1977) · Zbl 0385.90076
[11] Wiest, J. D.: Precedence diagramming methods: some unusual characteristics and their implications for project managers. Journal of operations management 1, 121-130 (1981)
[12] Moder, J. J.; Phillips, C. R.; Davis, E. W.: 3rd ed. Project management with CPM, PERT and precedence diagramming. Project management with CPM, PERT and precedence diagramming (1983)
[13] Brinkmann, K.; Neumann, K.: Heuristic procedures for resource-constrained project scheduling with minimal and maximal time lags: the minimum project-duration and resource-levelling problem. Journal of decision systems, 129-156 (1996)
[14] Zhan, J.: Heuristics for scheduling resource-constrained projects in MPM networks. European journal of operational research 76, 192-205 (1994) · Zbl 0806.90070
[15] Schwindt, C.: Generation of resource-constrained project scheduling problems with minimal and maximal time lags. Technical report WIOR-489 (1996)
[16] Neumann, K.; Zhan, J.: Heuristics for the minimum project-duration problem with minimal and maximal time lags under fixed resource constraints. Journal of intelligent manufacturing 6, 145-154 (1995)
[17] De Reyck, B.; Herroelen, W.: A branch-and-bound algorithm for the resource-constrained project scheduling problem with generalized precedence relations. European journal of operational research (1997) · Zbl 0948.90077
[18] De Reyck, B.; Herroelen, W.: Computational experience with a branch-and-bound algorithm for the resource-constrained project scheduling problem with generalized precedence relations. Research report 9628 (1996)
[19] De Reyck, B.; Herroelen, W.: An optimal procedure for the unconstrained MAX-npv project scheduling problem with generalized precedence relations. Research report 9642 (1996)
[20] Schwindt, C.; Neumann, K.: A new branch-and-bound-based heuristic for resource-constrained project scheduling with minimal and maximal time lags. Fifth international workshop on project management and scheduling, 212-215 (11–13 April, 1996)
[21] Franck, B.; Neumann, K.: Priority-rule methods for the resource-constrained project scheduling problem with minimal and maximal time lags-an empirical analysis. Fifth international workshop on project management and scheduling, 88-91 (11–13 April, 1996)
[22] Herroelen, W.; Demeulemeester, E.; Van Dommelen, P.: Project network models with discounted cash flows: A guided tour through recent developments. European journal of operational research 100, 97-121 (1997) · Zbl 0947.90583
[23] Russell, A. H.: Cash flows in networks. Management science 16, 357-373 (1970) · Zbl 0187.18201
[24] Grinold, R. C.: The payment scheduling problem. Naval research logistics quarterly 19, 123-136 (1972) · Zbl 0252.90034
[25] Elmaghraby, S. E.; Herroelen, W.: The scheduling of activities to maximize the net present value of projects. European journal of operational research 49, 35-49 (1990) · Zbl 1403.90670
[26] Herroelen, W.; Gallens, E.: Computational experience with an optimal procedure for the scheduling of activities to maximize the net present value of projects. European journal of operational research 65, 274-277 (1993) · Zbl 0775.90232
[27] Kazaz, B.; Sepil, C.: Project scheduling with discounted cash flows and progress payments. Journal of operational research society 47, 1262-1272 (1996) · Zbl 0863.90088
[28] Herroelen, W.; Demeulemeester, E.; Van Dommelen, P.: An optimal recursive search procedure for the deterministic unconstrained MAX-npv project scheduling problem. Research report 9603 (1996)
[29] Doersch, R. H.; Patterson, J. H.: Scheduling a project to maximize its present value: a zero-one programming approach. Management science 23, 882-889 (1977) · Zbl 0354.90043
[30] Smith-Daniels, D. E.; Smith-Daniels, V. L.: Maximizing the net present value of a project subject to materials and capital constraints. Journal of operations management 7, 33-45 (1987)
[31] 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
[32] Patterson, J. H.; Slowinski, R.; Talbot, F. B.; Weglarz, J.: An algorithm for a general class of precedence and resource-constrained scheduling problems. Advances in project scheduling, 3-28 (1990)
[33] Yang, K. K.; Talbot, F. B.; Patterson, J. H.: Scheduling a project to maximize its net present value: an integer programming approach. European journal of operational research 64, 188-198 (1992) · Zbl 0769.90053
[34] Icmeli, O.; Erengüç, S. S.: A branch-and-bound procedure for the resource-constrained project scheduling problem with discounted cash flows. Management science 42, 1395-1408 (1996) · Zbl 0880.90074
[35] Baroum, S.; Patterson, J. H.: An exact solution procedure for maximizing the net present value of cash flows in a network. Fifth international workshop on project management and scheduling, 31-34 (11–13 April, 1996)
[36] Russell, R. A.: A comparison of heuristics for scheduling projects with cash flows and resource restrictions. Management science 32, 291-300 (1986)
[37] Smith-Daniels, D. E.; Aquilano, N. J.: Using a late-start resource-constrained project schedule to improve project net present value. Decision science 18, 617-630 (1987)
[38] Padman, R.; Smith-Daniels, D. E.; Smith-Daniels, V. L.: Heuristic scheduling of resource-constrained projects with cash flows. Naval research logistics 44, 365-381 (1997) · Zbl 0890.90108
[39] Padman, R.; Smith-Daniels, D. E.: Maximizing the net present value of capital-constrained projects: an optimization-guided approach. Working paper 93-56 (1993)
[40] Zhu, D.; Padman, R.: Heuristic selection in resource-constrained project scheduling: experiments with neural networks. Working paper 93-43 (1993)
[41] Icmeli, O.; Erengüç, S. S.: A tabu search procedure for the resource-constrained project scheduling problem with discounted cash flows. Computers and operations research 8, 841-853 (1994) · Zbl 0812.90065
[42] Özdamar, L.; Ulusoy, G.; Bayyigit, M.: A heuristic treatment of tardiness and net present value criteria in resource-constrained project scheduling. Working paper (1994)
[43] Yang, K. K.; Tay, L. C.; Sum, C. C.: A comparison of stochastic scheduling rules for maximizing project net present value. European journal of operational research 85, 327-339 (1995) · Zbl 0912.90184
[44] Ulusoy, G.; Özdamar, L.: A heuristic scheduling algorithm for improving the duration and net present value of a project. International journal of operations and production management 15, 89-98 (1995)
[45] Sepil, C.; Ortaç, N.: Performance of the heuristic procedures for constrained projects with progress payments. Working paper (1995) · Zbl 0894.90082
[46] Lawler, E. L.: Combinatorial optimization: networks and matroids. (1976) · Zbl 0413.90040
[47] Demeulemeester, E.; Herroelen, W.: A branch-and-bound procedure for the multiple resource-constrained project scheduling problem. Management science 38, 1803-1818 (1992) · Zbl 0761.90059
[48] Kolisch, R.; Sprecher, A.; Drexl, A.: Characterization and generation of a general class of resource-constrained project scheduling problems. Management science 41, 1693-1703 (1995) · Zbl 0870.90070
[49] Pascoe, T. L.: Allocation of resources-CPM. Revue française de recherche opérationelle 38, 31-38 (1966)
[50] Mastor, A. A.: An experimental and comparative evaluation of production line balancing techniques. Management science 16, 728-746 (1970) · Zbl 0217.26903
[51] Thesen, A.: Measures of the restrictiveness of project networks. Networks 7, 193-208 (1977) · Zbl 0366.90057
[52] De Reyck, B.: On the use of the restrictiveness as a measure of complexity for resource-constrained project scheduling. Research report 9535 (1995)
[53] Dar-El, E. M.: MALB-A heuristic technique for balancing large single-model assembly lines. AIIE transactions 5, 343-356 (1973)
[54] Kao, E. P. C.; Queyranne, M.: On dynamic programming methods for assembly line balancing. Operations research 30, 375-390 (1982) · Zbl 0481.90043
[55] Demeulemeester, E.; Herroelen, W.: New benchmark results for the resource-constrained project scheduling problem. Management science, 43 (1997) · Zbl 0914.90160
[56] De Reyck, B.; Herroelen, W.: On the use of the complexity index as a measure of complexity in activity networks. European journal of operational research 91, 347-366 (1996) · Zbl 0924.90092
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.