Solving Resource Constrained Project Scheduling Problem using Hybrid GA

Abstract

The resource constrained project scheduling problem consist of optimal allocation of scared resources to tasks. RCPSP is solved by a genetic algorithm. Hybrid genetic algorithms have established significant attention in recent years and are being progressively more used to solve real-world problems. A genetic algorithm is able to include other techniques within its framework to produce a hybrid that generates the best from the combination. In this project we deals with the classical resource constrained project scheduling problem (RCPSP). Here, the activities of a project have to be scheduled subject to precedence and resource constraints. The objective is to minimize the makespan of the project. We proposed a new hybrid genetic algorithm to solve the RCPSP. Hybrid Genetic Algorithm combines elements from evolutionary and local search procedure by using priority based crossover, neighborhood swap mutation operation and neighborhood search procedure. The algorithm treats the solution of the RCPSP as activity list and serial schedule generation scheme is used to generate the solution. Performance of the HGA is investigated against other metaheuristics for solving case studies in the PSPLIB library. The results show that HGA is a high quality approach that outperforms all recent algorithms for the RCPSP known by the authors of this paper for the instance sets J30, J60, J90 and J120. And that it is competitive with other heuristics for the instance set J60, J90 and J120.