Skip to main content

Advertisement

Springer Nature Link
Log in

Efficient genetic algorithm for resource-constrained project scheduling problem

  • Published:
Transactions of Tianjin University Aims and scope Submit manuscript

Abstract

This paper presents a new genetic algorithm for the resource-constrained project scheduling problem (RCPSP). The algorithm employs a standardized random key (SRK) vector representation with an additional gene that determines whether the serial or parallel schedule generation scheme (SGS) is to be used as the decoding procedure. The iterative forward-backward improvement as the local search procedure is applied upon all generated solutions to schedule the project three times and obtain an SRK vector, which is reserved into population. Several evolutionary strategies are implemented including the elitist selection (the high quality solution set), and the selection of parents used in crossover operator. The computational experiments on 1 560 standard instances show that the proposed algorithm outperforms the current state-of-the-art heuristic algorithms for J30 and J60, and ranks the third for J120 with 50 000 schedules; it ranks the second for J30 and J60, and ranks the fifth for J120 with 5 000 schedules; it ranks the third, second, and fifth for J30, J60 and J120 with 1 000 schedules, respectively. It is demonstrated that the proposed algorithm is competitive for RCPSP, especially for larger number of schedules.

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

  1. Hartmann S, Kolisch R. Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem[J]. European Journal of Operational Research, 2000, 127(2): 394–407.

    Article  MATH  Google Scholar 

  2. Kolisch R, Hartmann S. Experimental investigation of heuristics for resource-constrained project scheduling: An update[J]. European Journal of Operational Research, 2006, 174(1): 23–37.

    Article  MATH  Google Scholar 

  3. Brucker P, Drexl A, Möhring R et al. Resource-constrained project scheduling: Notation, classification, models, and methods[J]. European Journal of Operational Research, 1999,112(1): 3–41.

    Article  MATH  Google Scholar 

  4. Blazewicz J, Lenstra J, Rinnooy Kan A. Scheduling subject to resource constraints: Classification and complexity[ J]. Discrete Applied Mathematics, 1983, 5(1): 11–24.

    Article  MATH  MathSciNet  Google Scholar 

  5. Davis E W, Patterson J H. A comparison of heuristic and optimum solutions in resource-constrained project scheduling[J]. Management Science, 1975, 21(8): 944–955.

    Article  Google Scholar 

  6. Kolisch R. Efficient priority rules for the resource-constrained project scheduling problem[J]. Journal of Operations Management, 1996, 14(3): 179–192.

    Article  Google Scholar 

  7. Boctor F F. Some efficient multi-heuristic procedures for resource-constrained project scheduling[J]. European Journal of Operational Research, 1990, 49(1): 3–13.

    Article  Google Scholar 

  8. Özdamar L, Ulusoy G. A note on an iterative forward/backward scheduling technique with reference to a procedure by Li and Wills[J]. European Journal of Operational Research, 1996, 89(2): 400–407.

    Article  MATH  Google Scholar 

  9. Kolisch R, Drexl A. Adaptive search for solving hard project scheduling problem[J]. Naval Research Logistics, 1996, 43(1): 23–40.

    Article  MATH  Google Scholar 

  10. Lee J K, Kim Y D. Search heuristics for resource constrained project scheduling[J]. Journal of Operational Research Society, 1996, 47(5): 678–689.

    MATH  Google Scholar 

  11. Alcaraz J, Maroto C, Ruiz R. Improving the performance of genetic algorithm for the RCPS problem[C]. In: Proceedings of the Ninth International Workshop on Project Management and Scheduling. Nancy, France, 2004. 40–43.

  12. Hartmann S. A competitive genetic algorithm for resource-constrained project scheduling[J]. Naval Research Logistics, 1998, 45(7): 733–750.

    Article  MATH  MathSciNet  Google Scholar 

  13. Hartmann S. A self-adapting genetic algorithm for resource-constrained under project scheduling[J]. Naval Research Logistics, 2002, 49(5): 433–448.

    Article  MATH  MathSciNet  Google Scholar 

  14. Valls V, Ballestin F, Quintanilla S. A hybrid genetic algorithm for the resource-constrained project scheduling problem[ J]. European Journal of Operational Research, 2008, 185(2): 495–508.

    Article  MATH  MathSciNet  Google Scholar 

  15. Mendes J J, Goncalves J F, Resende M G C. A random key based genetic algorithm for the resource constrained project scheduling problem[J]. Computers & Operations Research, 2009, 36(1): 92–109.

    Article  MATH  MathSciNet  Google Scholar 

  16. Debels D, Vanhoucke M. A decomposition-based genetic algorithm for the resource-constrained project scheduling problem[J]. Operations Research, 2007, 55(3): 457–469.

    Article  MATH  Google Scholar 

  17. Bouleimen K, Lecocq H. A new efficient simulated annealing algorithm for solving resource constrained project scheduling problem and its multiple modes version[J]. European Journal of Operational Research, 2003, 149(2): 268–281.

    Article  MATH  MathSciNet  Google Scholar 

  18. Nonobe K, Ibaraki T. Formulation and tabu search algorithm for the resource constrained project scheduling problem[C]. In: Essays and Surveys in Metaheuristics. Kluwer Academic Publishers, 2002. 557–588.

  19. Merkle D, Middendorf M, Schemeck H. Ant colony optimization for resource-constrained project scheduling[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(4): 333–346.

    Article  Google Scholar 

  20. Debels D, de Reyck B, Leus R et al. A hybrid scatter search/electromagnetism meta-heuristic for project scheduling[ J]. European Journal of Operational Research, 2006, 169(2): 638–653.

    Article  MATH  MathSciNet  Google Scholar 

  21. Ranjbar M. Solving the resource-constrained project scheduling problem using filter-and-fan approach[J]. Applied Mathematics and Computation, 2008, 201(1/2): 313–318.

    Article  MATH  Google Scholar 

  22. Tormos P, Lova A. A competitive heuristic solution technique for resource-constrained project scheduling[J]. Annals of Operations Research, 2001, 102(1–4): 65–81.

    Article  MATH  MathSciNet  Google Scholar 

  23. Kochetov Y, Stolyar A. Evolutionary local search with variable neighborhood for the resource constrained project scheduling problem[C]. In: Proceedings of the 3rd International Workshop of Computer Science and Information Technologies. Russia, 2003.

  24. Palpant M, Artigues C, Michelon P. LSSPER: Solving the resource-constrained project scheduling problem with large neighborhood search[J]. Annals of Operations Research, 2004, 131(1–4): 237–257.

    Article  MATH  MathSciNet  Google Scholar 

  25. Chambers L D. Practical Handbook of Genetic Algorithms: Applications[M]. CRC Press, Floride, 1995.

    Google Scholar 

  26. Kolisch R, Sprecher A. PSPLIB—A project scheduling problem library[J]. European Journal of Operational Research, 1996, 96(1): 205–216.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Sciences, Tianjin University, Tianjin, 300072, China

    Hong Wang  (王 宏), Tongling Li  (李同玲) & Dan Lin  (林 丹)

Authors
  1. Hong Wang  (王 宏)
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Tongling Li  (李同玲)
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Dan Lin  (林 丹)
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Hong Wang  (王 宏).

Additional information

WANG Hong, born in 1973, female, Dr, associate Prof.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Wang, H., Li, T. & Lin, D. Efficient genetic algorithm for resource-constrained project scheduling problem. Trans. Tianjin Univ. 16, 376–382 (2010). https://doi.org/10.1007/s12209-010-1495-y

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12209-010-1495-y

Keywords

Search

Navigation