Maximising the net present value of large resource-constrained projects

Publication Type:
Conference Proceeding
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2012, 7514 LNCS pp. 767 - 781
Issue Date:
Filename Description Size
2012007929OK.pdf Published version507.09 kB
Adobe PDF
Full metadata record
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. © 2012 Springer-Verlag.
Please use this identifier to cite or link to this item: