A hybrid scatter search approach for resource-constrained project scheduling problem in PERT-type networks

This paper presents a metaheuristic algorithm for resource-constrained project scheduling problem (RCPSP) in PERT networks. A PERT-type project, where activities require resources of various types with random duration, is considered. The problem is to minimize the regular criterion namely project's make-span. The resource project scheduling model is an NP-hard, therefore to obtain a precise solution, a metaheuristic algorithm is suggested namely hybrid scatter search (HSS). The path relinking algorithm and two operators like crossover and prominent permutation-based are applied to solve the problem. The problem has to be solved at each decision point, when at least more than one activity is ready to be operated but the available amount of resources is limited. The metaheuristic model is illustrated by a numerical example. In order to validate the performance of new hybrid metaheuristic algorithm, solutions are compared with "optimal solution" for small networks. Also the efficiency of the proposed algorithm, for real world problems, in terms of solution quality, is compared with well-reported benchmark test problems available on the PSPLIB. The computational results reveal that the proposed algorithm has appropriate results for small networks and real world problems. (C) 2010 Elsevier Ltd. All rights reserved.