Abstract
The Resource-constrained Project Scheduling Problem (Rcpsp), in which a schedule must obey resource constraints and precedence constraints between pairs of activities, is one of the most studied scheduling problems. An important variation of this problem (RcpspDc) is to find a schedule which maximises the net present value (discounted cash flow). Large industrial applications can require thousands of activities to be scheduled over a long time span. The largest case we have (from a mining company) includes about 11,000 activities spanning over 20 years. We apply a Lagrangian relaxation method for large RcpspDc to obtain both upper and lower bounds. To overcome the scalability problem of this approach we first decompose the problem by relaxing as fewer as possible precedence constraints, while obtaining activity clusters small enough to be solved efficiently. We propose a hierarchical scheme to accelerate the convergence of the subgradient algorithm of the Lagrangian relaxation. We also parallelise the implementation to make better use of modern computing infrastructure. Together these three improvements allow us to provide the best known solutions for very large examples from underground mining problems.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Boost.org, http://www.boost.org/
Baroum, S., Patterson, J.: The development of cash flow weight procedures for maximizing the net present value of a project. Journal of Operations Management 14, 209–227 (1996)
Brucker, P., Drexl, A., Möhring, R., Neumann, K., Pesch, E.: Resource-constrained project scheduling: Notation, classification, models, and methods. European Journal of Operational Research 112(1), 3–41 (1999)
Chaudhuri, S., Walker, R., Mitchell, J.: Analyzing and exploiting the structure of the constraints in the ilp approach to the scheduling problem. IEEE Trans. Very Large Scale Integration (VLSI) Systems 2, 456–471 (1994)
Cherkassky, B., Goldberg, A.: On implementing push-relabel method for the maximum flow problem. In: IPCO 1995, pp. 157–171 (1995)
Demeulemeester, E.L., Herroelen, W.S.: A branch-and-bound procedure for the multiple resource-constrained project scheduling problem. Management Science 38(12), 1803–1818 (1992)
Demeulemeester, E.L., Herroelen, W.S.: New benchmark results for the resource-constrained project scheduling problem. Management Science 43(11), 1485–1492 (1997)
Doersch, R., Patterson, J.: Scheduling a project to maximize its present value: A zero-one programming approach. Management Science 23, 882–889 (1977)
Dósa, G.: Graham’s example is the only tight one for P||C max . Annales Universitatis Scientarium Budapestiensis de Rolando Eötös nominatae, Sectio Mathematica 47, 207–210 (2004)
Fisher, M.: The lagrangian relaxation method for solving integer programming problems. Management Science 27, 1–18 (1981)
Graham, R.L.: Bounds for certain multiprocessing anomalies. Bell System Tech. J. (45), 1563–1581 (1966)
Hartmann, S., Briskorn, D.: A survey of variants and extensions of the resource-constrained project scheduling problem. European Journal of Operational Research 207(1), 1–14 (2010)
Herroelen, W.S., Demeulemeester, E.L., De Reyck, B.: A classification scheme for project scheduling. In: Weglarz, J. (ed.) Project Scheduling. International Series in Operations Research and Management Science, vol. 14, pp. 1–26. Kluwer Academic Publishers (1999)
Icmeli, O., Erengüç, S.S.: A branch and bound procedure for the resource constrained project scheduling problem with discounted cash flows. Management Science 42(10), 1395–1408 (1996)
Johnson, E., Mehrotra, A., Nemhauser, G.: Min-cut clustering. Mathematical Programming 62, 133–151 (1993)
Karypis, G.: METIS, A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices, Version 5.0 (2011), http://glaros.dtc.umn.edu/gkhome/views/metis
Kimms, A.: Maximizing the net present value of a project under resource constraints using a lagrangian relaxation based heuristic with tight upper bounds. Annals of Operations Research 102, 221–236 (2001)
Möhring, R.H., Schulz, A.S., Stork, F., Uetz, M.: Solving project scheduling problems by minimum cut computations. Management Science 49(3), 330–350 (2003)
Neumann, K., Zimmermann, J.: Exact and truncated branch-and-bound procedures for resource-constrained project scheduling with discounted cash flows and general temporal constraints. Central European Journal of Operations Research 10(4), 357–380 (2002)
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)
Russell, A.H.: Cash flows in networks. Management Science 16(5), 357–373 (1970)
Schutt, A., Chu, G., Stuckey, P.J., Wallace, M.G.: Maximising the Net Present Value for Resource-Constrained Project Scheduling. In: Beldiceanu, N., Jussien, N., Pinson, É. (eds.) CPAIOR 2012. LNCS, vol. 7298, pp. 362–378. Springer, Heidelberg (2012)
Siek, J.G., Lee, L.Q., Lumsdaine, A.: The Boost Graph Library: User Guide and Reference Manual. Addison-Wesley (2001)
Vanhoucke, M., Demeulemeester, E.L., Herroelen, W.S.: On maximizing the net present value of a project under renewable resource constraints. Management Science 47, 1113–1121 (2001)
Zhao, X., Luh, P.B.: New bundle methods for solving lagrangian relaxation dual problems. J. Optim. Theory Appl. 113, 373–397 (2002), http://dx.doi.org/10.1023/A:1014839227049
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gu, H., Stuckey, P.J., Wallace, M.G. (2012). Maximising the Net Present Value of Large Resource-Constrained Projects. In: Milano, M. (eds) Principles and Practice of Constraint Programming. CP 2012. Lecture Notes in Computer Science, vol 7514. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-33558-7_55
Download citation
DOI: https://doi.org/10.1007/978-3-642-33558-7_55
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-33557-0
Online ISBN: 978-3-642-33558-7
eBook Packages: Computer ScienceComputer Science (R0)