Computational & Technology Resources
an online resource for computational,
engineering & technology publications
Civil-Comp Proceedings
ISSN 1759-3433
CCP: 92
PROCEEDINGS OF THE FIRST INTERNATIONAL CONFERENCE ON SOFT COMPUTING TECHNOLOGY IN CIVIL, STRUCTURAL AND ENVIRONMENTAL ENGINEERING
Edited by: B.H.V. Topping and Y. Tsompanakis
Paper 2

A Hybrid Method for the Resource-Constrained Project Scheduling Problem with Discounted Cash Flows

B. Láng

Corvinus University of Budapest, Hungary

Full Bibliographic Reference for this paper
, "A Hybrid Method for the Resource-Constrained Project Scheduling Problem with Discounted Cash Flows", in B.H.V. Topping, Y. Tsompanakis, (Editors), "Proceedings of the First International Conference on Soft Computing Technology in Civil, Structural and Environmental Engineering", Civil-Comp Press, Stirlingshire, UK, Paper 2, 2009. doi:10.4203/ccp.92.2
Keywords: resource-constrained project scheduling, cash flow models, heuristic and metaheuristic techniques, harmony search optimization, hybrid methods, managing projects, bi-objective models, computational experiment.

Summary
This paper presents a hybrid method for the resource-constrained project scheduling problem with discounted cash flows. In the proposed approach, a resource-constrained project is characterized by its "best" schedule, where best means a makespan minimal resource-constrained schedule for which the net present value (NPV) measure is maximal.

Theoretically the optimal schedule searching process can be formulated as a mixed integer linear programming (MILP) problem, which can be solved for small-scale projects in a reasonable time. The applied hybrid method is a combination of a "conflict repairing" harmony search (HS) metaheuristic and a local search algorithm based on linear programming. The HS metaheuristic was recently developed by Lee and Geem [1] in an analogy with the music improvisation process where music players improvise to obtain better harmony. The applied harmony search algorithm is a conflict repairing version of the "sounds of silence" harmony search metaheuristic developed for the traditional resource-constrained project scheduling problem (RCPSP) by Csébfalvi et al. [2,3].

The hybrid method exploits the fact, that the unconstrained NPV can be solved in polynomial time when a totally unimodular (TU) formulation is used to describe the predecessor-successor relations. To solve the linear programming (LP) problems a state-of-the-art LP solver (BPMPD) developed by Mészáros [4] was used.

In order to illustrate the essence and viability of the proposed harmony search metaheuristic, we present computational results for the J30 set from the well-known and popular PSPLIB [5]. To generate the optimal solutions a state-of-the-art callable MILP solver (CPLEX) was used.

References
1
K.S. Lee, Z.W. Geem, "A new meta-heuristic algorithm for continuous engineering optimization: harmony search theory and practice", Computer Methods in Applied Mechanics and Engineering, 194, 3902-3933, 2005. doi:10.1016/j.cma.2004.09.007
2
G. Csébfalvi, A. Csébfalvi, E. Szendroi, "A harmony search metaheuristic for the resource-constrained project scheduling problem and its multi-mode version", in "Project Management and Scheduling 2008", F.S. Serifoglu, Ü. Bilge, (Editors), Istanbul, Turkey, 56-59, 2008.
3
G. Csébfalvi, O. Eliezer, B. Láng, R. Levi, "A conflict repairing harmony search metaheuristic and its application for bi-objective resource-constrained project scheduling problems", in "Project Management and Scheduling 2008", F.S. Serifoglu, Ü. Bilge, (Editors), Istanbul, Turkey, 60-63, 2008.
4
Cs. Mészáros, "The Efficient Implementation of Interior Point Methods for Linear Programming and their Applications", PhD Thesis, Eötvös Loránd University of Sciences, Hungary, 1996.
5
R. Kolisch, A. Sprecher, "PSPLIB - a project scheduling library", European Journal of Operational Research, 96, 205-216, 1996. doi:10.1016/S0377-2217(96)00170-1

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £78 +P&P)