A biased random-key genetic algorithm for the project scheduling problem with flexible resources

Bernardo F. Almeida ^[1] ; Isabel Correia ^[2] ; Francisco Saldanha-da-Gama ^[1]
1. [1] Universidade de Lisboa
  
  Universidade de Lisboa
  
  Socorro, Portugal
2. [2] Universidade Nova de Lisboa
  
  Universidade Nova de Lisboa
  
  Socorro, Portugal
Localización: Top, ISSN-e 1863-8279, ISSN 1134-5764, Vol. 26, Nº. 2, 2018, págs. 283-308
Idioma: inglés
DOI: 10.1007/s11750-018-0472-9
Enlaces
- Texto completo (pdf)
Resumen
- In this paper, we investigate a resource-constrained project scheduling problem with flexible resources. This is an NP -hard combinatorial optimization problem that consists of scheduling a set of activities requiring specific resource units of several skills. The goal is to minimize the makespan of the project. We propose a biased random-key genetic algorithm for computing feasible solutions for the referred problem. We study different decoding mechanisms: an already existing method in the literature, a new adapted serial scheduling generation scheme, and a combination of both. The new procedure is tested using a set of benchmark instances of the problem. The results provide strong evidence that the new heuristic is robust and yields high-quality feasible solutions.