Abstract
In this paper we propose a forward-backward improvement heuristic for the variant of resource-constrained project scheduling problem aiming to maximise the net present value of a project. It relies on the Lagrangian relaxation method to generate an initial set of schedules which are then improved by the iterative forward/backward scheduling technique. It greatly improves the performance of the Lagrangian relaxation based heuristics in the literature and is a strong competitor to the best meta-heuristics. We also embed this heuristic into a state-of-the-art CP solver. Experimentation carried out on a comprehensive set of test data indicates we compare favorably with the state of the art.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Project Schedule
- Lagrangian Relaxation
- Scatter Search
- Project Schedule Problem
- Constrain Project Schedule
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
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)
Debels, D., Vanhoucke, M.: A decomposition-based genetic algorithm for the resource-constrained project-scheduling problem. Operations Research 55(3), 457–469 (2007)
Gu, H.Y.: Computation of approximate alpha-points for large scale single machine scheduling problem. Computers & OR 35(10), 3262–3275 (2008)
Gu, H., Stuckey, P.J., Wallace, M.G.: Maximising the net present value of large resource-constrained projects. In: Milano, M. (ed.) CP 2012. LNCS, vol. 7514, pp. 767–781. Springer, Heidelberg (2012)
Gu, H., Xi, Y., Tao, J.: Randomized Lagrangian heuristic based on Nash equilibrium for large scale single machine scheduling problem. In: Proceedings of the 22nd IEEE International Symposium on Intelligent Control, pp. 464–468 (2007)
Hartmann, S., Kolisch, R.: Experimental evaluation of state-of-the-art heuristics for resource constrained project scheduling. European Journal of Operational Research 127, 394–407 (2000)
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)
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)
Kolisch, R., Hartmann, S.: Experimental investigation of heuristics for resource-constrained project scheduling: An update. European Journal of Operational Research 174, 23–37 (2006)
Li, K., Willis, R.: An iterative scheduling technique for resource-constrained project scheduling. European Journal of Operational Research 56, 370–379 (1992)
Luby, M., Sinclair, A., Zuckerman, D.: Optimal speedup of Las Vegas algorithms. Inf. Proc. Let. 47(4), 173–180 (1993)
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)
Ohrimenko, O., Stuckey, P.J., Codish, M.: Propagation via lazy clause generation. Constraints 14(3), 357–391 (2009)
Russell, A.H.: Cash flows in networks. Management Science 16(5), 357–373 (1970)
Savelsbergh, M., Uma, R., Wein, J.: An experimental study of LP-based approximation algorithms for scheduling problems. INFORMS J. on Computing 17, 123–136 (2005)
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)
Schutt, A., Feydy, T., Stuckey, P.J.: Explaining time-table-edge-finding propagation for the cumulative resource constraint. In: Gomes, C., Sellmann, M. (eds.) CPAIOR 2013. LNCS, vol. 7874, pp. 234–250. Springer, Heidelberg (2013)
Schutt, A., Feydy, T., Stuckey, P.J., Wallace, M.G.: Explaining the cumulative propagator. Constraints 16(3), 250–282 (2011)
Sprecher, A., Kolisch, R., Drexl, A.: Semi-active, active, and non-delay schedules for the resource-constrained project scheduling problem. European Journal of Operational Research 80, 94–102 (1995)
Vanhoucke, M.: A scatter search heuristic for maximising the net present value of a resource constrained project with fixed activity cash flows. International Journal of Production Research 48(7), 1983–2001 (2010)
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)
Zhu, D., Padman, R.: A metaheuristic scheduling procedure for resource-constrained projects with cash flows. Naval Research Logistics 46, 912–927 (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gu, H., Schutt, A., Stuckey, P.J. (2013). A Lagrangian Relaxation Based Forward-Backward Improvement Heuristic for Maximising the Net Present Value of Resource-Constrained Projects. In: Gomes, C., Sellmann, M. (eds) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. CPAIOR 2013. Lecture Notes in Computer Science, vol 7874. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38171-3_24
Download citation
DOI: https://doi.org/10.1007/978-3-642-38171-3_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38170-6
Online ISBN: 978-3-642-38171-3
eBook Packages: Computer ScienceComputer Science (R0)