Computational & Technology Resources
an online resource for computational,
engineering & technology publications
PROCEEDINGS OF THE SECOND INTERNATIONAL CONFERENCE ON SOFT COMPUTING TECHNOLOGY IN CIVIL, STRUCTURAL AND ENVIRONMENTAL ENGINEERING
Edited by: Y. Tsompanakis, B.H.V. Topping
An Improved Hybrid Algorithm for the Resource-Constrained Project Scheduling Problem with Hammock Activities
O. Eliezer1 and R. Levi2
1Ort Braude Academic College of Engineering, Carmiel, Israel
O. Eliezer, R. Levi, "An Improved Hybrid Algorithm for the Resource-Constrained Project Scheduling Problem with Hammock Activities", in Y. Tsompanakis, B.H.V. Topping, (Editors), "Proceedings of the Second International Conference on Soft Computing Technology in Civil, Structural and Environmental Engineering", Civil-Comp Press, Stirlingshire, UK, Paper 20, 2011. doi:10.4203/ccp.97.20
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 . 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 . To generate the optimal solutions and solve the local MILP problems a state-of-the-art callable MILP solver (CPLEX) was used.
purchase the full-text of this paper (price £20)