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 4

A Hybrid Metaheuristic for a Bi-Objective Resource-Constrained Project Scheduling Problem

R. Levi

Technion, Haifa, Israel

Full Bibliographic Reference for this paper
R. Levi, "A Hybrid Metaheuristic for a Bi-Objective Resource-Constrained Project Scheduling Problem", 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 4, 2009. doi:10.4203/ccp.92.4
Keywords: activity float, resource-constrained project scheduling, heuristic and metaheuristic techniques, harmony search optimization, hybrid methods, managing projects, bi-objective models, robust scheduling, computational experiment.

Summary
The concept of float and criticality plays a central role in project management. However, the recent literature does not offer a general and useful measure for criticality (flexibility) in resource-constrained projects.

This paper presents a resource constrained total free float model to cope with this problem. The presented resource-constrained total free float measure (RCTFF) is defined as the sum of the free floats of activities. The free float is defined as the amount of time that an activity can slip without delaying the start of its successors and while maintaining resource feasibility. In the proposed bi-objective approach, a resource-constrained project is characterized by its "best" schedule, where best means a make span minimal resource-constrained schedule for which the RCTFF measure is maximal. Naturally, this secondary measure can be replaced by any other measure which is able to characterize somehow the scheduling flexibility and can be expressed in the function of the conflict repairing possibilities (see for example Levi [1]). Theoretically the optimal schedule searching process can be formulated as a mixed integer linear programming (MILP) problem with big-M constraints, which can be solved for small-scale projects in reasonable time.

The presented hybrid method is a conflict repairing version of a harmony search (HS) metaheuristic which is combined with a local search algorithm to manage the secondary criterion. The HS metaheuristic was recently developed by Lee and Geem [2] using an analogy with a 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. [3,4]. The presented conflict repairing strategy is practically independent from the applied metaheuristic frame, so it means a more generally applicable new result.

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

References
1
R. Levi, "Criticality in Resource Constrained Projects", PhD Dissertation, University of Pécs, Hungary, 2004.
2
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
3
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.
4
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.

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)