Keywords: multi-mode resource-constrained project scheduling, heuristic and metaheuristic techniques, harmony search optimization, hybrid methods, managing projects, computational experiment.

This paper presents a hybrid algorithm for the multi-mode resource-constrained project scheduling problem (MRCPSP). 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 algorithm is based on the "sounds of silence" harmony search metaheuristic developed for MRCPSP by Csébfalvi et al. [1]. The harmony search (HS) metaheuristic was recently developed by Lee and Geem [2] in an analogy with the music improvisation process where music players improvise to obtain better harmony. In the improved algorithm presented the harmony search is combined with a new and effective "head-tail" local search procedure based on a MILP formulation and the originally totally random starting repertoire is replaced by a set of pre-optimized melodies generated from the relaxed solution by random perturbation. The "head-tail" procedure tries to decrease the makespan of the project by reallocation the resources allocated to the starting and finishing activities by the HS procedure. The local search procedure exploits the fact, that using a fast and effective solver a small MILP problem can be solved within a reasonable time. In order to illustrate the essence and viability of the proposed harmony search metaheuristic, we present computational results for the J30MM set from the well-known and popular PSPLIB [3]. To generate the "head-tail" improvements a state-of-the-art callable MILP solver (CPLEX) was used.

1

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.

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

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)