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

This paper presents an improved harmony search metaheuristic for the multi-mode resource-constrained project scheduling problem (MRCPSP). The presented hybrid metaheuristic is an improved version of the forbidden set oriented "Sounds of Silence" (SoS) harmony search metaheuristic developed by Csébfalvi et al. [1,2] and Szendroi [3]. In the applied primary-secondary criteria approach, the resource-constrained project is characterized by its "best" schedule for which the resource profiles approach the ideal rectangular shape as much as possible. The hybrid algorithm is a combination of a resource conflict repairing harmony search (SoS) metaheuristic and a resource levelling-assigning procedure based on a MILP problem [4] to optimize the secondary criterion on the set of resource feasible solutions.

In the original approach a simple but efficient "rule of thumb" was applied to eliminate the hidden resource conflicts. The result of the applied rule will be a resource-feasible solution set, in which every movable activity can be shifted without affecting the resource feasibility.

It is well-known, that the crucial point of the conflict repairing model is the forbidden set computation. In the improved algorithm to decrease the time requirement of the forbidden set computation and speed up the problem solving process, a fast and efficient pre-processing step was inserted before the forbidden set computation which frequently reduces the solution time dramatically. The process is a modified and simplified version of the model developed by Alvarez-Valdés and Tamarit [5].

The essence of the pre-processing step is very simple: In a cyclically repairable process, the incompatible activity pairs (triplets) are selected which have exactly one conflict repairing relation which is inserted into the precedence relations. The process is terminated when the relation set is empty.

In order to illustrate the essence and viability of the improved algorithm, computational results for the J30MM-14-5 project instance from the PSPLIB [6] benchmark set are presented.

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 F.S. Serifoglu, Ü. Bilge, (Editors), "Project Management and Scheduling 2008", Istanbul, Turkey, 56-59, 2008.

2

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 F.S. Serifoglu, Ü. Bilge, (Editors), "Project Management and Scheduling 2008", Istanbul, Turkey, 60-63, 2008.

3

E. Szendroi, "A Hybrid Method for the Multi-Mode Resource-Constrained Project Scheduling Problem with Strip Packing like Resource Constraints", In B. H. V. Topping, J.M. Adam, F.J. Pallarés, M.L. Romero, (Editors), "Proceedings of the Seventh International Conference on Engineering Computational Technology", Civil-Comp Press, Stirlingshire, United Kingdom, paper 93, 2010. doi:10.4203/ccp.94.93

4

G. Csébfalvi, P. Konstantinidis, "A new exact resource balancing procedure for the multiple resource-constrained project scheduling problem", in Proceedings of APMOD '98, Limasol, Cyprus, 11-13 March 1998.

5

R. Alvarez-Valdés, J.M. Tamarit, "The project scheduling polyhedron: Dimension, facts and lifting theorems", European Journal of Operational Research, 96, 204-220, 1993.

6

R. Kolisch, A. Sprecher, "PSPLIB - a project scheduling library", European Journal of Operational Research, 96, 205-216, 1997. 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 £50 +P&P)