SpringerLink
Log in

Solving the MRCPSP/max with the objective of minimizing tardiness/earliness cost of activities with double genetic algorithms

  • ORIGINAL ARTICLE
  • Published:
The International Journal of Advanced Manufacturing Technology Aims and scope Submit manuscript

Abstract

This paper presents a meta-heuristic method for a resource-constrained project scheduling problem. In this problem, the activities are given with multiple executive modes and there are minimum as well as maximum time lags between different activities. The objective here is to determine a mode and a start (or finish) time, for each activity such that total tardiness/earliness cost of activities could be minimized. The meta-heuristic approach was developed, as a two-phased genetic algorithm. The process of solving the proposed problem includes two stages (phases). In the first stage, through applying a genetic algorithm, the main problem is simplified so that each activity has only one executive mode. In the second phase, through develo** another genetic algorithm, the best answer to the problem is achieved. Finally, the computational results obtained from the solution algorithms of this research were compared with the results existing in the Project Scheduling Problem Library (PSPLIB). These algorithms were provided in the MATLAB programming language. The findings show that our algorithm improved some of the best recorded solutions in the PSPLIB.

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
EUR 32.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

  1. Mika M, Waligora G, Weglarz J (2008) Tabu search for multi-mode resource-constrained project scheduling with schedule-dependent setup times. Eur J Oper Res 187:1238–1250

    Article  MATH  Google Scholar 

  2. Neumann K, Schwindt C (1997) Activity-on-node networks with minimal and maximal time lags and their application to make-to-order production. OR-Spektrum 19:205–217

    Article  MATH  MathSciNet  Google Scholar 

  3. Bartusch M, Möhring RH, Radermacher FJ (1988) Scheduling project networks with resource constraints and time windows. Ann Oper Res 16:199–240

    Article  Google Scholar 

  4. De Reyck B, Herroelen W (1998) A branch-and-bound procedure for the resource-constrained project scheduling problem with generalized precedence constraints. Oper Res 111:152–174

    MATH  Google Scholar 

  5. Fest A, Möhring RH, Stork F, Uetz M (1998) Resource constrained project scheduling with time windows: a branching scheme based on dynamic release dates. Technical report 596, TU Berlin, Germany

  6. Dorndorf U, Pesch E, Phan-Huy T (2000) A time-oriented branch and bound algorithm for resource constrained project scheduling with generalized precedence constraints. Manag Sci 46:1365–1384

    Article  MATH  Google Scholar 

  7. Franck B, Selle T (1998) Metaheuristics for the resource-constrained project scheduling problem with schedule-dependent time windows. Technical report WIOR-546, Universitat Karlsruhe, Germany

  8. Franck B, Neumann K, Schwindt C (2001) Truncated branch-and-bound, schedule-construction, and schedule-improvement procedures for resource-constrained project scheduling. OR-Specktrum 23:297–324

    Article  MATH  MathSciNet  Google Scholar 

  9. Cesta A, Oddi A, Smith SF (2002) A constraint-based method for project scheduling with time windows. J Heuristics 8(1):109–136

    Article  MATH  Google Scholar 

  10. Smith TB, Pyle JM (2004) An effective algorithm for project scheduling with arbitrary temporal constraints. In: Proceedings of the 19th national conference on artificial intelligence (AAAI'04), AAAI, San Jose, pp 544–549

  11. Ballestín F, Barrios A, Valls V (2011) An evolutionary algorithm for the resource-constrained project scheduling problem with minimum and maximum time lags. J Sched 14:391–406

    Article  MATH  MathSciNet  Google Scholar 

  12. De Reyck B (1998) Scheduling projects with generalized precedence relations: exact and heuristic procedures. PhD thesis, Katholieke Universiteit Leuven, Belgium

  13. Nonobe K, Ibaraki T (2003) A tabu search algorithm for a generalized resource constrained project scheduling problem. In: MIC2003: the fifth metaheuristics international conference, pp 551–556

  14. Heilmann R (2001) Resource-constrained project scheduling: a heuristic for the multi-mode case. OR-Spektrum 23:335–357

    Article  MATH  MathSciNet  Google Scholar 

  15. Heilmann R (2003) A branch-and-bound procedure for the multi-mode resource-constrained project scheduling problem with minimum and maximum time lags. Eur J Oper Res 144:348–365

    Article  MATH  MathSciNet  Google Scholar 

  16. Barrios A, Ballestín F, Valls V (2011) A double genetic algorithm for the MRCPSP/max. Comput Oper Res 38:33–43

    Article  MATH  MathSciNet  Google Scholar 

  17. Haupt RL, Haupt SE (2004) Practical genetic algorithm, 2nd edn. Wiley, Hoboken

    Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  19. Hartmann S (2001) Project scheduling with multiple modes: a genetic algorithm. Ann Oper Res 102:111–135

    Article  MATH  MathSciNet  Google Scholar 

  20. De Reyck B, Herroelen W (1999) The multi-mode resource-constrained project scheduling problem with generalized precedence relations. Eur J Oper Res 119:538–556

    Article  MATH  Google Scholar 

  21. Tarjan R (1972) Depth-first search and linear graph algorithms. SIAM J Comput 1:146–160

    Article  MATH  MathSciNet  Google Scholar 

  22. Alcaraz J, Maroto C, Ruiz R (2003) Solving the multi-mode resource-constrained project scheduling problem with genetic algorithms. J Oper Res Soc 54:614–626

    Article  MATH  Google Scholar 

  23. Van Peteghem V, Vanhoucke M (2010) A genetic algorithm for the preemptive and non-preemptive multi-mode resource-constrained project scheduling problem. Eur J Oper Res 201:409–418

    Article  MATH  Google Scholar 

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

    Article  MATH  Google Scholar 

  25. Agarwal A, Colak S, Erenguc S (2011) A neuro-genetic approach for the resource-constrained project scheduling problem. Comput Oper Res 38(1):44–50

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  27. Hartmann S (1998) A competitive genetic algorithm for resource-constrained project scheduling. Nav Res Logist 45:733–750

    Article  MATH  Google Scholar 

  28. Valls V, Ballestín F, Quintanilla S (2008) A hybrid genetic algorithm for the resource-constrained project scheduling problem. Eur J Oper Res 185(2):495–508

    Article  MATH  Google Scholar 

  29. Chen W, Shi Y, Teng H, Lan X, Hu L (2010) An efficient hybrid algorithm for resource-constrained project scheduling. Inf Sci 180(6):1031–1039

    Article  Google Scholar 

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

    Article  MATH  Google Scholar 

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

    Article  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Industrial Engineering, Faculty of Engineering and Technology, University of Alzahra, Tehran, Iran

    Jafar Bagherinejad & Zahra Rafie Majd

Authors
  1. Jafar Bagherinejad
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Zahra Rafie Majd
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jafar Bagherinejad.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bagherinejad, J., Majd, Z.R. Solving the MRCPSP/max with the objective of minimizing tardiness/earliness cost of activities with double genetic algorithms. Int J Adv Manuf Technol 70, 573–582 (2014). https://doi.org/10.1007/s00170-013-5303-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00170-013-5303-4

Keywords

Search

Navigation