Skip to main content
SpringerLink
Log in

A Robust Genetic Algorithm for Resource Allocation in Project Scheduling

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

Genetic algorithms have been applied to many different optimization problems and they are one of the most promising metaheuristics. However, there are few published studies concerning the design of efficient genetic algorithms for resource allocation in project scheduling. In this work we present a robust genetic algorithm for the single-mode resource constrained project scheduling problem. We propose a new representation for the solutions, based on the standard activity list representation and develop new crossover techniques with good performance in a wide sample of projects. Through an extensive computational experiment, using standard sets of project instances, we evaluate our genetic algorithm and demonstrate that our approach outperforms the best algorithms appearing in the literature.

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

Similar content being viewed by others

References

  1. J. Alcaraz and C. Maroto, A genetic algorithm for the resource-constrained project scheduling problem, in: Proceedings of the Sixth International Workshop on Project Management and Scheduling, eds. G. Barbaroso?lu, S. Karabat?, L. Özdamar and G. Ulusoy (Bo?aziçi University Printing Office, 1998) pp. 7-10.

  2. R. Álvarez-Valdés and J.M. Tamarit, Heuristic algorithms for resource-constrained project scheduling: A review and an empirical analysis, in: Advances in Project Scheduling, eds. R. Slowinski and J. W?glarz (Elsevier, 1989) pp. 114-134.

  3. R. Álvarez-Valdés and J.M. Tamarit, Algoritmos heurísticos deterministas y aleatorios en secuenciación de proyectos con recursos limitados, Qüestiiò 13 (1989) 173–191.

    Google Scholar 

  4. T. Baar, P. Brucker and S. Knust, Tabu-search algorithms and lower bounds for the resourceconstrained project scheduling problem, in: Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, eds. S. Voss, S. Martello, I. Osman and C. Roucairol (Kluwer Academic, 1998) pp. 1-18.

  5. E. Balas, Project scheduling with resource constraints, in: Applications of Mathematical Programming Techniques, ed. E.M.L. Beale (English University Press, 1971) pp. 187-200.

  6. C.E. Bell and J. Han. A new heuristic solution method in resource-constrained project scheduling, Naval Research Logistics 38 (1991) 315–331.

    Google Scholar 

  7. C.E. Bell and K. Park, Solving resource-constrained project scheduling problems by A*-search, Naval Research Logistics 37 (1990) 61–84.

    Google Scholar 

  8. F.F. Boctor, Some efficient multi-heuristic procedures for resource-constrained project scheduling, European Journal of Operational Research 49 (1990) 3–13.

    Google Scholar 

  9. F.F. Boctor, Resource-constrained project scheduling by simulated annealing, International Journal in Production Research 34 (1996) 2335–2351.

    Google Scholar 

  10. K. Bouleimen and H. Lecocq, A new efficient simulated annealing algorithm for the resourceconstrained project scheduling problem, in: Proceedings of the Sixth International Workshop on Project Management and Scheduling, eds. G. Barbaroso?lu, S. Karabat?, L. Özdamar and G. Ulusoy (Bo?aziçi University Printing Office, Istanbul, 1998) pp. 19–22.

    Google Scholar 

  11. P. Brucker, A. Drexl, R. Möhring, K. Neumann and E. Pesch, Resource-constrained project scheduling: Notation, classification, models, and methods, European Journal of Operational Research 112 (1998) 3–41.

    Google Scholar 

  12. P. Brucker, S. Knust, A. Schoo and O. Thiele, A branch and bound algorithm for the resourceconstrained project scheduling problem, European Journal of Operational Research 107 (1998) 272–288.

    Google Scholar 

  13. J.A. Carruthers and A. Battersby, Advances in critical path methods, Operational Research Quarterly 17 (1966) 359–380.

    Google Scholar 

  14. L.D. Chambers, Practical Handbook of Genetic Algorithms: Applications, Vol. I (CRC Press, 1995).

  15. J.-H. Cho and Y.-D. Kim, A simulated annealing algorithm for resource constrained project scheduling problems, Journal of the Operational Research Society 48 (1997) 735–744.

    Google Scholar 

  16. N. Christofides, R. Álvarez-Valdés and J.M. Tamarit, Project scheduling with resource constraints: A branch and bound approach, European Journal of Operational Research 29 (1987) 262–273.

    Google Scholar 

  17. D.F. Cooper, Heuristics for scheduling resource-constrained projects: An experimental investigation, Management Science 22 (1976) 1186–1194.

    Google Scholar 

  18. D.F. Cooper, A note on serial and parallel heuristics for resource-constrained project scheduling, Foundations of Control Engineering 2 (1977) 131–133.

    Google Scholar 

  19. E.M. Davies, An experimental investigation of resource allocation in multiactivity projects, Operational Research Quarterly 24 (1973) 587–591.

    Google Scholar 

  20. E.W. Davis and G.E. Heidorn, An algorithm for optimal project scheduling under multiple resource constraints, Management Science 17 (1971) 803–816.

    Google Scholar 

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

    Google Scholar 

  22. B. De Reyck and W. Herroelen, A branch-and-bound procedure for the resource-constrained project scheduling problem with generalized precedence relations, European Journal of Operational Research 111 (1998) 152–174

    Google Scholar 

  23. E. Demeulemeester and W. Herroelen, A branch-and-bound procedure for the multiple resource-constrained project scheduling problem, Management Science 38 (1992) 1803–1818.

    Google Scholar 

  24. E. Demeulemeester and W. Herroelen, New benchmark results for the resource-constrained project scheduling problem, Management Science 43 (1997) 1485–1492.

    Google Scholar 

  25. E. Demeulemeester and W. Herroelen, A branch-and-bound procedure for the generalized resourceconstrained project scheduling problem, Operations Research 45 (1997) 201–212.

    Google Scholar 

  26. A. Drexl, Scheduling of project networks by job assignment, Management Science 37 (1991) 1590–1602.

    Google Scholar 

  27. S.E. Elmaghraby, Activity Networks: Project Planning and Control by Network Models (Wiley, 1977).

  28. E.A. Elsayed, Algorithms for project scheduling with resource constraints, International Journal of Production Research 20 (1982) 95–103.

    Google Scholar 

  29. E. Falkenauer, Genetic Algorithms and Grouping Problems (Wiley, 1998).

  30. F. Glover, Tabu search-Part I, ORSA Journal on Computing 1 (1989) 190–206.

    Google Scholar 

  31. F. Glover, Tabu search-Part II, ORSA Journal on Computing 2 (1989) 4–32.

    Google Scholar 

  32. D.E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning (Addison-Wesley, 1989).

  33. S. Hartmann, A competitive genetic algorithm for resource-constrained project scheduling, Naval Research Logistics 45 (1998) 733–750.

    Google Scholar 

  34. N.A.J. Hastings, On resource allocation in project networks, Operational Research Quarterly 23 (1972) 217–221.

    Google Scholar 

  35. W. Herroelen, E. Demeulemeester, B. De Reyck, A classification scheme for project scheduling, in: Project Scheduling: Recent Models, Algorithms and Applications, ed. J. W?glarz (Kluwer Academic, 1998) pp. 1-26.

  36. H.J. Holland, Adaptation in Natural and Artificial Systems (University of Michigan Press, 1975).

  37. T. Jones, Crossover, macromutation, and population-based search, in: Proceedings of the Sixth International Conference on Genetic Algorithms, ed. L.J. Eshelman (Morgan Kaufmann, 1995).

  38. J.E. Kelley, The critical-path method: Resources planning and scheduling, in: Industrial Scheduling, eds. J.F. Muth and G.L. Thompson (Prentice-Hall, 1963) pp. 347-365.

  39. S. Kirkpatrick, C.D. Gelatt Jr. and M.P. Vecchi, Optimization by simulated annealing, Science 220 (1983) 671–680.

    Google Scholar 

  40. U. Kohlmorgen, H. Schmeck and K. Haase, Experiences with fine-grained parallel genetic algorithms, Working paper, Institut für Angewandte Informatik und Formale Beschreibungsverfahren, Universität Karlsruhe, Karlsruhe, Germany (1996).

    Google Scholar 

  41. R. Kolisch, Efficient priority rules for the resource-constrained project scheduling problem, Journal of Operations Management 14 (1996) 179–192.

    Google Scholar 

  42. R. Kolisch, Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation, European Journal of Operational Research 90 (1996) 320–333.

    Google Scholar 

  43. R. Kolisch and A. Drexl, Adaptive search for solving hard project scheduling problems, Naval Research Logistics 43 (1996) 23–40.

    Google Scholar 

  44. R. Kolisch and S. Hartmann, Heuristic algorithms for the resource-constrained project scheduling problem: classification and computational analysis, in: Project Scheduling: Recent Models, Algorithms and Applications, ed. J. W?glarz (Kluwer Academic, 1998) pp. 147-178.

  45. R. Kolisch and A. Sprecher, PSPLIB-a project scheduling problem library, European Journal of Operational Research 96 (1996) 205–216.

    Google Scholar 

  46. R. Kolisch, A. Sprecher and A. Drexl, Characterization and generation of a general class of resourceconstrained project scheduling problems, Management Science 41 (1995) 1693–1703.

    Google Scholar 

  47. S.R. Lawrence, Resource constrained project scheduling-A computational comparison of heuristic scheduling techniques, Working paper, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, USA (1985).

    Google Scholar 

  48. J.-K. Lee, and Y.-D. Kim, Search heuristics for resource constrained project scheduling, Journal of the Operational Research Society 47 (1996) 678–689.

    Google Scholar 

  49. V.J. Leon and R. Balakrishnan, Strength and adaptability of problem-space based neighborhoods for resource-constrained scheduling, OR Spektrum 17 (1995) 173–182.

    Google Scholar 

  50. R.K.-Y. Li and J. Willis, An iterative scheduling technique for resource-constrained project scheduling, European Journal of Operational Research 56 (1992) 370–379.

    Google Scholar 

  51. A. Lova, Programación de multiproyectos con recursos limitados: Un enfoque multicriterio, Unpublished Ph.D., Department of Statistics and Operations Research, Universidad Politécnica de Valencia, Valencia, Spain (1997).

    Google Scholar 

  52. A. Mingozzi, V. Maniezzo, S. Ricciardelli and L. Bianco, An exact algorithm for the resource-constrained project scheduling based on a new mathematical formulation, Management Science 44 (1998) 714–729.

    Google Scholar 

  53. M. Mori and C.C. Tseng, A genetic algorithm for multi-mode resource constrained project scheduling problem, European Journal of Operational Research 100 (1997) 134–141.

    Google Scholar 

  54. K.S. Naphade, S.D. Wu and R.H. Storer, Problem space search algorithms for resource-constrained project scheduling, Annals of Operations Research 70 (1997) 307–326.

    Google Scholar 

  55. T. Nazareth, S. Verma, S. Bhattacharya and A. Bagchi, The multiple resource-constrained project scheduling problem: A breadth-first approach, Working Paper, Indian Institute of Management, Calcutta, India (1996).

    Google Scholar 

  56. K. Nonobe and T. Ibaraki, Formulation and tabu search algorithm for the resource constrained project scheduling problem (RCPSP), Working paper, Department of Applied Mathematics and Physics, Kyoto University, Kyoto, Japan (1999).

    Google Scholar 

  57. M.J. Norusis, SPSS Advanced Statistics 6.1 (SPSS, 1994).

  58. L. Özdamar, A genetic algorithm approach to a general category project scheduling problem, IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews 29 (1999) 44–59.

    Google Scholar 

  59. L. Özdamar and G. Ulusoy, An iterative local constraint based analysis for solving the resource constrained project scheduling problem, Journal of Operations Management 14 (1996) 193–208.

    Google Scholar 

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

    Google Scholar 

  61. J.H. Patterson, Alternate methods of project scheduling with limited resources, Naval Research Logistics Quarterly 20 (1973) 767–784.

    Google Scholar 

  62. J.H. Patterson, Project scheduling: The effect of problem structure on heuristic performance, Naval Research Logistics Quarterly 23 (1976) 95–124.

    Google Scholar 

  63. J.H. Patterson, A comparison of exact approaches for solving the multiple constrained resource project scheduling problem, Management Science 30 (1984) 854–867.

    Google Scholar 

  64. J.H. Patterson and W.D. Huber, A horizon-varying, zero-one approach to project scheduling, Management Science 20 (1974) 990–998.

    Google Scholar 

  65. J.H. Patterson and G.W. Roth, Scheduling a project under multiple resource constraints: a zero-one programming approach, AIIE Transactions 8 (1976) 449–455.

    Google Scholar 

  66. J.H. Patterson, R. Slowinski, F.B. Talbot and J. W?glarz, An algorithm for a general class of precedence and resource constrained scheduling problems, in: Advances in Project Scheduling, eds. R. Slowinski and J. W?glarz (Elsevier, 1989) pp. 3-28.

  67. E. Pinson, C. Prins, and F. Rullier, Using tabu search for solving the resource-constrained project scheduling problem, in: Proceedings of the Fourth International Workshop on Project Management and Scheduling (Katholieke Universiteit Leuven, 1994) pp. 102-106.

  68. B. Pollack-Johnson, Hybrid structures and improving forecasting and scheduling in project management, Journal of Operations Management 12 (1995) 101–117.

    Google Scholar 

  69. A.A.B. Pritsker, L.J.Watters and P.M. Wolfe, Multiproject scheduling with limited resources: a zero-one programming approach, Management Science 16 (1969) 93–107.

    Google Scholar 

  70. F.J. Radermacher, Scheduling of project networks, Annals of Operations Research 4 (1985/86) 227–252.

    Google Scholar 

  71. S.E. Sampson and E.N. Weiss, Local search techniques for the generalized resource constrained project scheduling problem, Naval Research Logistics 40 (1993) 665–675.

    Google Scholar 

  72. A. Schirmer and S. Riesenberg, Parameterized heuristics for project scheduling-Biased random sampling methods, Working paper, Instituten für Betriebswirtschaftslehre, Universität Kiel, Kiel, Germany (1997).

    Google Scholar 

  73. A. Schirmer and S. Riesenberg, Class-based control schemes for parameterized project scheduling heuristics, Working paper, Instituten für Betriebswirtschaftslehre, Universität Kiel, Kiel, Germany (1998).

    Google Scholar 

  74. L.R. Shaffer, J.B. Ritter and W.L. Meyer, The Critical-Path Method (McGraw-Hill, 1965).

  75. W.P. Simpson and J.H. Patterson, A multiple-tree search procedure for the resource-constrained project scheduling problem, European Journal of Operational Research 89 (1996) 525–542.

    Google Scholar 

  76. A. Sprecher, Resource Constrained Project Scheduling-Exact Methods for the Multi-Mode Case (Springer, 1994).

  77. A. Sprecher, Solving the RCPSP efficiently at modest memory requirements, Instituten für Betriebswirtschaftslehre, Universität Kiel, Kiel, Germany (1996).

    Google Scholar 

  78. A. Sprecher and A. Drexl, Solving multi-mode resource-constrained project scheduling problems by a simple, general and powerful sequencing algorithm, European Journal of Operational Research 107 (1998) 431–450.

    Google Scholar 

  79. A. Sprecher, R. Kolisch and A. Drexl, Semi-active, active, and non-delay schedules for the resource-constrained project scheduling problem, European Journal of Operational Research 80 (1995) 94–102.

    Google Scholar 

  80. J.P. Stinson, E.W. Davis and B.M. Khumawala, Multiple resource-constrained scheduling using branch and bound, AIIE Transactions 10 (1978) 252–259.

    Google Scholar 

  81. F.B. Talbot and J.H. Patterson, An efficient integer programming algorithm with network cuts for solving resource-constrained scheduling problems, Management Science 24 (1978) 1163–1174.

    Google Scholar 

  82. A. Thesen, Heuristic scheduling of activities under resource and precedence restrictions, Management Science 23 (1976) 412–422.

    Google Scholar 

  83. P.R. Thomas and S. Salhi, An investigation into the relationship of heuristic performance with network-resource characteristics, Journal of the Operational Research Society 48 (1997) 34–43.

    Google Scholar 

  84. P. Tormos, Programación de proyectos con recursos limitados: Técnicas heurísticas basadas en reglas de prioridad, Unpublished Ph.D., Department of Statistics and Operations Research, Universidad Politécnica de Valencia, Valencia, Spain (1996).

    Google Scholar 

  85. G. Ulusoy and L. Özdamar, Heuristic performance and network/resource characteristics in resourceconstrained project scheduling, Journal of the Operational Research Society 40 (1989) 1145–1152.

    Google Scholar 

  86. G. Ulusoy and L. Özdamar, A constraint-based perspective in resource constrained project scheduling, International Journal of Production Research 32 (1994) 693–705.

    Google Scholar 

  87. V. Valls, M.A. Pérez and M.S. Quintanilla, Heuristic performance in large resource-constrained projects, Working paper, Departament of Statistics and Operations Research, Universitat de València, Valencia, Spain (1992).

    Google Scholar 

  88. G.E. Whitehouse and J.R. Brown, GENRES: An extension of Brooks algorithm for project scheduling with resource constraints, Computers and Industrial Engineering 3 (1979) 261–268.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Statistics and Operations Research, Universidad Politécnica de Valencia, Camino de Vera s/n., 46022, Valencia, Spain

    J. Alcaraz & C. Maroto

Authors
  1. J. Alcaraz
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. C. Maroto
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Alcaraz, J., Maroto, C. A Robust Genetic Algorithm for Resource Allocation in Project Scheduling. Annals of Operations Research 102, 83–109 (2001). https://doi.org/10.1023/A:1010949931021

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1010949931021

Search

Navigation