Skip to main content

Advertisement

SpringerLink
Log in

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

  • Original Paper
  • Published:
TOP Aims and scope Submit manuscript

Abstract

In this paper, we investigate a resource-constrained project scheduling problem with flexible resources. This is an \(\mathcal {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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

Notes

  1. The percentage gaps are computed as explained in Sect. 4.2, with the lower bound for each instance being equal to the length of the corresponding critical path.

References

  • Alcaraz J, Maroto C (2001) A robust genetic algorithm for resource allocation in project scheduling. Ann Oper Res 102(1):83–109

    Article  Google Scholar 

  • Alcaraz J, Maroto C (2006) A hybrid genetic algorithm based on intelligent encoding for project scheduling. In: Józefowska J, Węglarz J (eds) Perspectives in modern project scheduling, pp 249–274

  • Almeida BF, Correia I, Saldanha-da-Gama F (2015) An instance generator for the multi-skill resource-constrained project scheduling problem. Technical report, Faculdade de Ciências da Universidade de Lisboa—Centro de Matemática, Aplicações Fundamentais e Investigação Operacional. Available at https://ciencias.ulisboa.pt/sites/default/files/fcul/unidinvestig/cmaf-cio/SGama.pdf

  • Almeida BF, Correia I, Saldanha-da-Gama F (2016) Priority-based heuristics for the multi-skill resource constrained project scheduling problem. Expert Syst Appl 57:91–103

    Article  Google Scholar 

  • Brucker P, Drexl A, Möhring R, Neumann K, Pesch E (1999) Resource-constrained project scheduling: notation, classification, models, and methods. Eur J Oper Res 112(1):3–41

    Article  Google Scholar 

  • Correia I, Lourenço LL, Saldanha-da-Gama F (2012) Project scheduling with flexible resources: formulation and inequalities. OR Spectrum 34:635–663

    Article  Google Scholar 

  • Correia I, Saldanha-da-Gama F (2014) The impact of fixed and variable costs in a multi-skill project scheduling problem: an empirical study. Comput Ind Eng 72:230–238

    Article  Google Scholar 

  • Correia I, Saldanha-da-Gama F (2015) A modeling framework for project staffing and scheduling problems. In: Schwindt C, Zimmermann J (eds) Handbook on project management and scheduling, vol 1. Springer, Berlin, pp 547–564

    Google Scholar 

  • Demeulemeester EL, Herroelen W (2002) Project scheduling: a research handbook. Springer, Berlin

    Google Scholar 

  • Gonçalves JF, Mendes JJ, Resende MG (2008) A genetic algorithm for the resource constrained multi-project scheduling problem. Eur J Oper Res 189(3):1171–1190

    Article  Google Scholar 

  • Gonçalves JF, Resende MG (2011) Biased random-key genetic algorithms for combinatorial optimization. J Heuristics 17:487–525

    Article  Google Scholar 

  • Gonçalves JF, Resende MG (2013) A biased random key genetic algorithm for 2D and 3D bin packing problems. Int J Prod Econ 145(2):500–510

    Article  Google Scholar 

  • Gonçalves JF, Resende MG (2015) A biased random-key genetic algorithm for the unequal area facility layout problem. Eur J Oper Res 246(1):86–107

    Article  Google Scholar 

  • Gonçalves JF, Resende MG, Mendes JJ (2011) A biased random-key genetic algorithm with forward–backward improvement for the resource constrained project scheduling problem. J Heuristics 17(5):467–486

    Article  Google Scholar 

  • Gutjahr WJ, Katzensteiner S, Reiter P, Stummer C, Denk M (2008) Competence-driven project portfolio selection, scheduling and staff assignment. CEJOR 16:281–306

    Article  Google Scholar 

  • Hartmann S (2002) A self-adapting genetic algorithm for project scheduling under resource constraints. Naval Res Log (NRL) 49(5):433–448

    Article  Google Scholar 

  • Hartmann S, Briskorn D (2010) A survey of variants and extensions of the resource-constrained project scheduling problem. Eur J Oper Res 207(1):1–14

    Article  Google Scholar 

  • Hartmann S, Kolisch R (2000) Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem. Eur J Oper Res 127:394–407

    Article  Google Scholar 

  • Heimerl C, Kolisch R (2010) Scheduling and staffing multiple projects with a multi-skilled workforce. OR Spectrum 32:343–368

    Article  Google Scholar 

  • Herroelen WS, Demeulemeester EL (1998) Resource-constrained project scheduling: a survey of recent developments. Comput Oper Res 25:279–302

    Article  Google Scholar 

  • Klein R (2000) Bidirectional planning: improving priority rule-based heuristics for scheduling resource-constrained projects. Eur J Oper Res 127:619–638

    Article  Google Scholar 

  • Kolisch R (1996a) Efficient priority rules for the resource-constrained project scheduling problem. J Oper Manag 14:179–192

    Article  Google Scholar 

  • Kolisch R (1996b) Serial and parallel resource-constrained project scheduling methods revisited: theory and computation. Eur J Oper Res 90(2):320–333

    Article  Google Scholar 

  • Kolisch R, Hartmann S (1999) Heuristic algorithms for solving the resource-constrained project scheduling problem: classification and computational analysis. In: Weglarz J (ed) Project scheduling: recent models, algorithms and applications. Springer, Boston, pp 147–178

    Chapter  Google Scholar 

  • Kolisch R, Hartmann S (2006) Experimental evaluation of heuristics for the resource-constrained project scheduling problem: an update. Eur J Oper Res 174:23–37

    Article  Google Scholar 

  • Li H, Womer K (2009) Scheduling projects with multi-skilled personnel by a hybrid MILP/CP benders decomposition algorithm. J Sched 12:281–298

    Article  Google Scholar 

  • Li K, Willis R (1992) An alternative scheduling technique for resource constrained project scheduling. Eur J Oper Res 56:370–379

    Article  Google Scholar 

  • Mendes JJ, Gonçalves JF, Resende MG (2009) A random key based genetic algorithm for the resource constrained project scheduling problem. Comput Oper Res 36(1):92–109

    Article  Google Scholar 

  • Mingozzi A, Maniezzo V, Ricciardelli S, Bianco L (1998) An exact algorithm for the resource-constrained project scheduling problem based on a new mathematical formulation. Manag Sci 44(5):714–729

    Article  Google Scholar 

  • Özdamar L (1999) A genetic algorithm approach to a general category project scheduling problem. IEEE Trans Syst Man Cybern 29:44–69

    Article  Google Scholar 

  • Ruiz E, Albareda-Sambola M, Fernández E, Resende MG (2015) A biased random-key genetic algorithm for the capacitated minimum spanning tree problem. Comput Oper Res 57(C):95–108

    Article  Google Scholar 

  • Walter M, Zimmermann J (2016) Minimizing average project team size given multi-skilled workers with heterogeneous skill levels. Comput Oper Res 70(C):163–179

    Article  Google Scholar 

  • Węglarz J, Józefowska J, Mika M, Waligóra G (2011) Project scheduling with finite or infinite number of activity processing modes—a survey. Eur J Oper Res 208:177–205

    Article  Google Scholar 

Download references

Acknowledgements

This work was supported by National Funding from FCT—Fundação para a Ciência e a Tecnologia, under the projects Fundação para a Ciência e a Tecnologia, UID/MAT/04561/2013 (CMAF-CIO/FCUL) and UID/MAT/00297/2013 (CMA/FCT/UNL). The authors wish to thank the three anonymous referees for the valuable comments and suggestions provided which helped improving the manuscript.

Author information

Authors and Affiliations

  1. Departamento de Estatística e Investigação Operacional/Centro de Matemática, Aplicações Fundamentais e Investigação Operacional, Faculdade de Ciências, Universidade de Lisboa, 1749-016, Lisbon, Portugal

    Bernardo F. Almeida & Francisco Saldanha-da-Gama

  2. Departamento de Matemática/Centro de Matemática e Aplicações, Faculdade de Ciências e Tecnologia, Universidade Nova de Lisboa, 2829-516, Caparica, Portugal

    Isabel Correia

Authors
  1. Bernardo F. Almeida
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Isabel Correia
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Francisco Saldanha-da-Gama
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Bernardo F. Almeida.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Almeida, B.F., Correia, I. & Saldanha-da-Gama, F. A biased random-key genetic algorithm for the project scheduling problem with flexible resources. TOP 26, 283–308 (2018). https://doi.org/10.1007/s11750-018-0472-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11750-018-0472-9

Keywords

Mathematics Subject Classification

Search

Navigation