A Local Search Algorithm for the Resource-Constrained Project Scheduling Problem
- 1 November 2022
- journal article
- research article
- Published by Pleiades Publishing Ltd in Journal of Applied and Industrial Mathematics
- Vol. 16 (4) , 672-683
Abstract
We consider the resource-constrained project scheduling problem (RCPSP). The problem accounts for technological constraints of activities precedence together with resource constraints. All resources are renewable. Activities interruptions are not allowed. This problem is NP-hard in the strong sense. We present a new local search algorithm that uses a Tabu-list and two types of neighborhoods. The algorithm is evaluated using three data bases of instances of the problem: 480 instances of 60 activities, 480 of 90, and 600 of 120 activities, respectively, taken from the PSPLIB library available online. Numerical experiments demonstrate that the proposed algorithm produces better results than existing algorithms described in the literature for large-sized instances. For some instances from the dataset j120, the best known heuristic solutions were improved.Keywords
This publication has 37 references indexed in Scilit:
- An effective shuffled frog-leaping algorithm for resource-constrained project scheduling problemComputers & Operations Research, 2012
- New meta-heuristics for the resource-constrained project scheduling problemFlexible Services and Manufacturing Journal, 2011
- An Artificial Immune Algorithm for the project scheduling problem under resource constraintsApplied Soft Computing, 2011
- A genetic algorithm with neighborhood search for the resource-constrained project scheduling problemNaval Research Logistics (NRL), 2011
- A survey of variants and extensions of the resource-constrained project scheduling problemEuropean Journal of Operational Research, 2010
- An efficient hybrid algorithm for resource-constrained project schedulingInformation Sciences, 2010
- A random key based genetic algorithm for the resource constrained project scheduling problemComputers & Operations Research, 2009
- Using an enhanced scatter search algorithm for a resource-constrained project scheduling problemSoft Computing, 2008
- A hybrid genetic algorithm for the resource-constrained project scheduling problemEuropean Journal of Operational Research, 2008
- PSPLIB - A project scheduling problem libraryEuropean Journal of Operational Research, 1997