Keywords: resource-constrained project scheduling, hammock activities, heuristic and metaheuristic techniques, harmony search optimization, hybrid methods, managing projects, bi-objective models, computational experiment.

This paper presents an improved hybrid algorithm for the resource-constrained project scheduling problem with hammock activities. In the applied primary-secondary criteria approach, a project is characterized by its "best" schedule, where best means a makespan minimal resource-constrained schedule for which the total hammock cost (THC) measure is minimal. The algorithm is an improved resource conflict repairing version of the "Sounds of Silence" harmony search metaheuristic developed by Csébfalvi et al. [1,2] and Eliezer and Csébfalvi [3]. The presented hybrid algorithm is a combination of a resource conflict repairing harmony search (HS) metaheuristic and a local search algorithm based on linear programming to optimize the secondary criterion (THC) on the set of resource feasible local solutions. The algorithm exploits the fact that on a resource feasible local solution set the THC minimization can be solved in polynomial time. In the original approach a simple but efficient "rule of thumb" was applied to eliminate the potential resource conflicts. In the improved algorithm we replaced this "rule of thumb" with a secondary criterion specific mixed integer linear programming (MILP) formulation where the binary variables are conflict repairing indicators and the objective function is the "changeable" part of the THC objective in the function of the "movable" starting time variables. The improved algorithm 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 improved algorithm, we present computational results for the J30 set from PSPLIB developed by Kolisch and Sprecher [4]. To generate the optimal solutions and solve the local MILP problems 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 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

O. Eliezer, G. Csébfalvi, "A Hybrid Method for the Resource-Constrained Project Scheduling Problem with Hammock Activities", 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, United Kingdom, paper 1, 2009. doi:10.4203/ccp.92.1

4

R. Kolisch, A. Sprecher, "PSPLIB - a project scheduling library", European Journal of Operational Research, 96, 205-216, 1996.

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 £70 +P&P)