Nothing Special   »   [go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

Project scheduling with flexible resources: formulation and inequalities

  • Regular Article
  • Published:
OR Spectrum Aims and scope Submit manuscript

Abstract

In this paper, we study a variant of the resource-constrained project scheduling problem in which resources are flexible, i.e., each resource has several skills. Each activity in the project may need several resources for each required skill. We present a mixed-integer linear programming formulation for this problem. Several sets of additional inequalities are also proposed. Due to the fact that some of the above-mentioned inequalities require a valid upper bound to the problem, a heuristic procedure is proposed. Computational experience is reported based on randomly generated data, showing that for instances of reasonable size the proposed model enlarged with the additional inequalities can be solved efficiently.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

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

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Alvarez-Valdés R, Tamarit JM (1993) The project scheduling polyhedron: dimension, facets and lifting theorems. Eur J Oper Res 67: 204–220

    Article  Google Scholar 

  • Alvarez-Valdes R, Crespo E, Tamarit JM, Villa F (2006) A scatter search algorithm for project scheduling under partially renewable resources. J Heuristics 12: 95–113

    Article  Google Scholar 

  • Alvarez-Valdes R, Crespo E, Tamarit JM, Villa F (2008) Grasp and path relinking for project scheduling under partially renewable resources. Eur J Oper Res 189: 1153–1170

    Article  Google Scholar 

  • Applegate D, Cook W (1991) A computational study of job-shop scheduling. ORSA J Comput 3: 149–156

    Article  Google Scholar 

  • Baptiste P, Demassey S (2004) Tight LP bounds for resource constrained project scheduling. OR Spectr 26: 251–262

    Article  Google Scholar 

  • Bellenguez O, Néron E (2005) Lower bounds for the multi-skill project scheduling problem with hierarchical levels of skills. In: Practice and theory of automated timetabling V: 5th international conference PATAT 2004, Pittsburgh, PA, USA, 18-20 Aug 2004, Revised selected papers, pp 229–243. Lecture Notes in Computer Science, vol 3616/2005. Springer, Berlin

  • Bellenguez-Morineau O (2008) Methods to solve multi-skill project scheduling problem. 4OR 6: 85–88

    Article  Google Scholar 

  • Bellenguez-Morineau O, Néron E (2006) Genetic algorithms for the multi-skill project scheduling problem. In: Extended abstracts of the 10th international workshop on project management and scheduling, Poland, 26–28 Apr 2006

  • Bellenguez-Morineau O, Néron E (2007) A branch-and-bound method for solving multi-skill project scheduling problem. RAIRO Oper Res 41: 155–170

    Article  Google Scholar 

  • Bellenguez-Morineau O, Néron E, Heurtebise M (2006) Decomposition method for solving multi-skill project scheduling problem. In: Extended abstracts of the 10th international workshop on project management and scheduling, Poland, 26–28 Apr 2006

  • Bertsegas D, Tseng P (1994) RELAX-IV: a faster version of the relax code for solving minimum cost flow problem. http://web.mit.edu/dimitrib/www/noc.htm

  • Blazewicz J, Lenstra JK, Rinnooy Kan A (1983) Scheduling subject to resource constraints: classification and complexity. Discrete Appl Math 5: 11–24

    Article  Google Scholar 

  • Böttcher J, Drexl A, Kolisch R, Salewski F (1999) Project scheduling under partially renewable resource constraints. Manage Sci 45: 543–559

    Article  Google Scholar 

  • Brucker P, Knust S, Schoo A, Thiele O (1998) A branch and bound algorithm for the resource-constrained project scheduling problem. Eur J Oper Res 107: 272–288

    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: 3–41

    Article  Google Scholar 

  • Carlier J, Néron E (2003) On linear lower bounds for the resource constrained project scheduling problem. Eur J Oper Res 149: 314–324

    Article  Google Scholar 

  • Carlier J, Pinson E (1989) An algorithm for solving the job-shop problem. Manage Sci 35: 164–176

    Article  Google Scholar 

  • Christofides N, Alvarez-Valdés R, Tamarit JM (1987) Project scheduling with resource constraints: a branch and bound approach. Eur J Oper Res 29: 262–273

    Article  Google Scholar 

  • Dauzère-Pérès S, Roux W, Lasserre JB (1998) Multi-resource shop scheduling with resource flexibility. Eur J Oper Res 107: 289–305

    Article  Google Scholar 

  • Demassey S (2008) Mathematical programming formulations and lower bounds. In: Artigues C, Demassey S, Néron E (eds) Resource-constrained project scheduling—models, algorithms, exptensions and applications, pp 49–62. ISTE, Willey

  • Dorndorf U, Pesch E, Phan-Huy T (2000) A branch-and-bound algorithm for the resource-constrained project scheduling problem. Math Methods Oper Res 52: 413–439

    Article  Google Scholar 

  • Hanne T, Nickel S (2005) A multiobjective evolutionary algorithm for scheduling and inspection planning in software development projects. Eur J Oper Res 167: 663–678

    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–14

    Article  Google Scholar 

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

    Article  Google Scholar 

  • Herroelen W, Leus R (2005) Project scheduling under uncertainty: survey and research potentials. Eur J Oper Res 165: 289–306

    Article  Google Scholar 

  • Herroelen W, De Reyck B, Demeulemeester E (1998) Resource-constrained project scheduling: a survey of recent developments. Comput Oper Res 25: 279–302

    Article  Google Scholar 

  • ILOG CPLEX user’s manual (2007) ILOG, Inc., Incline Village, Nevada. http://cplex.ilog.com

  • Klein R, Scholl A (1999) Computing lower bounds by destructive improvement: an application to resource-constrained project scheduling problem. Eur J Oper Res 112: 322–346

    Article  Google Scholar 

  • Kolisch R (1996) Serial and parallel resource-constrained project scheduling methods revisited: theory and computation. Eur J Oper Res 90: 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. Kluwer, Dordrecht, pp 147–178

    Google Scholar 

  • Kolisch R, Padman R (2001) An integrated survey of deterministic project scheduling. Omega 29: 249–272

    Article  Google Scholar 

  • Kolisch R, Sprecher A (1996) PSPLIB—a project scheduling problem library. Eur J Oper Res 96: 205–216

    Article  Google Scholar 

  • Kolisch R, Sprecher A, Drexl A (1995) Characterization and generation of a general class of resource- constrained project-scheduling problems. Manage Sci 41: 1693–1703

    Article  Google Scholar 

  • Koné O, Artigues C, Lopez P, Mongeau M (2011) Event-based MILP models for the resource-constrained project scheduling problem. Comput Oper Res 38: 3–13

    Article  Google Scholar 

  • Mellentien C, Schwindt C, Trautmann N (2004) Scheduling the factory pick-up of new cars. OR Spectr 26: 579–601

    Article  Google Scholar 

  • Mingozzi A, Maniezzo V, Ricciardelli S, Bianco L (1998) An exact algorithm for project scheduling with resource constraints based on a new mathematical formulation. Manage Sci 44: 714–729

    Article  Google Scholar 

  • Pessan C, Bellenguez-Morineau O, Néron E (2007) Multi-skill project scheduling problem and total productive maintenance. In: Proceedings of MISTA 2007, 3rd multidisciplinary international scheduling conference, Paris, France, 28–31 Aug 2007, pp 608–610

  • Schirmer A (1999) Project scheduling with scarce resources: models, methods, and applications. Verlag Dr. Kovac, Hamburg

    Google Scholar 

  • Zhu G, Bard JF, Yu G (2006) A branch-and-cut procedure for the multimode resource-constrained project-scheduling problem. INFORMS J Comput 18: 377–390

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Departamento de Matemática, Faculdade de Ciências e Tecnologia, Universidade Nova de Lisboa, 2829-516, Caparica, Portugal

    Isabel Correia & Lídia Lampreia Lourenço

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

    Isabel Correia

  3. Departamento de Estatística e Investigação Operacional, Faculdade de Ciências, Universidade de Lisboa, 1749-016, Lisboa, Portugal

    Francisco Saldanha-da-Gama

  4. Centro de Investigação Operacional, Faculdade de Ciências, Universidade de Lisboa, 1749-016, Lisboa, Portugal

    Lídia Lampreia Lourenço & Francisco Saldanha-da-Gama

Authors
  1. Isabel Correia
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Lídia Lampreia Lourenço
    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 Isabel Correia.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Correia, I., Lourenço, L.L. & Saldanha-da-Gama, F. Project scheduling with flexible resources: formulation and inequalities. OR Spectrum 34, 635–663 (2012). https://doi.org/10.1007/s00291-010-0233-0

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00291-010-0233-0

Keywords

Search

Navigation