Simulated annealing variants for solving resource Constrained Project Scheduling Problem: A comparative study

Abstract

Now-a-days different meta-heuristic approaches are being applied for solving Combinatorial Optimization Problems (COP). In this paper Resource Constrained Project Scheduling Problem (RCPSP) has been presented as a COP. This is a common problem for many construction projects. It is highly constrained and is categorized as a NP-hard problem. In our earlier work Simulated Annealing (SA_RCP) outperformed other meta-heuristics, like, Genetic Algorithm, Tabu Search, Particle Swarm Optimization and its variant in solving benchmark instances of this problem. Having been inspired by this result we have further applied new variants of Simulated Annealing for RCPSP. In this work, we have taken three more SA variants and applied them for solving a benchmark instance of this problem. The results show that Simulated Annealing incorporated with Tabu List and Greedy Selection Heuristic (GTSA_RCP) outperforms other methods in getting optimal results with maximum hit and minimum fluctuations.