Skip to main content
SpringerLink
Log in

Simulated Annealing for Multi-Mode Resource-Constrained Project Scheduling

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

Abstract

In this paper the resource-constrained project scheduling problem with multiple execution modes for each activity and the makespan as the minimization criterion is considered. A simulated annealing approach to solve this problem is presented. The feasible solution representation is based on a precedence feasible list of activities and a mode assignment. A comprehensive computational experiment is described, performed on a set of standard test problems constructed by the ProGen project generator. The results are analyzed and discussed and some final remarks are included.

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. E.H.L. Aarts and J.H.M. Korst, Simulated Annealing and Boltzmann Machines: A Stochastic Approach to Combinatorial Optimization and Neural Computing (Wiley, Chichester, 1989).

    Google Scholar 

  2. E.H.L. Aarts, J.H.M. Korst and P.J.M. van Laarhoven, Simulated annealing, in: Local Search in Combinatorial Optimization, eds. E.H.L. Aarts and J.K. Lenstra (Wiley, Chichester, 1997) pp. 91–120.

    Google Scholar 

  3. T. Baar, P. Brucker and S. Knust, Tabu-search algorithms for the resource-constrained project scheduling problem, Technichal Report, University of Osnabrück, Germany (1997).

    Google Scholar 

  4. J. B?a?ewicz, J.K. Lenstra and A.H.G. Rinnooy Kan, Scheduling subject to resource constraints, Discrete Applied Mathematics 5 (1983) 11–24.

    Google Scholar 

  5. F.F. Boctor, Heuristics for scheduling projects with resource restrictions and several resource-duration modes, International Journal of Production Research 31 (1993) 2547–2558.

    Google Scholar 

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

    Google Scholar 

  7. F.F. Boctor, A new and efficient heuristic for scheduling projects with resource restrictions and multiple execution modes, European Journal of Operational Research 90 (1996) 349–361.

    Google Scholar 

  8. K. Bouleimen and H. Lecocq, A new efficient simulated annealing algorithm for the RCPSP and its multiple mode version, in: Proceedings of the 6th International Workshop on Project Management and Scheduling, Istanbul (July 7-9 1998).

  9. K. Bouleimen and H. Lecocq, A new efficient simulated annealing 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, Istanbul, 1998) pp. 19–22.

    Google Scholar 

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

    Google Scholar 

  11. V. Černy, Thermodynamical approach to the traveling salesman problem: an efficient simulation algorithm, Journal of Optimization Theory and Applications 45 (1985) 41–51.

    Google Scholar 

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

    Google Scholar 

  13. E. Demeulemeester and W. Herrolen, A branch-and-bound procedure for the multiple resourceconstrained project scheduling problem, Management Science 38(12) (1992) 1803–1818.

    Google Scholar 

  14. A. Drexl and J. Grünewald, Nonpreemptive multi-mode resource-constrained project scheduling, IIE Transactions 25 (1993) 74–81.

    Google Scholar 

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

    Google Scholar 

  16. S. Hartmann, Project scheduling with multiple modes: A genetic algorithm, Manuskripte aus den Instituten für Betriebswirtschaftslehre, No. 435, University of Kiel, Germany (1997).

    Google Scholar 

  17. S. Hartmann and A. Drexl, Project scheduling with multiple modes: A comparison of exact algorithms, Networks 32 (1998) 283–297.

    Google Scholar 

  18. S. Hartmann and R. Kolisch, Experimental evaluation of state-of-the-art heuristics for the resourceconstrained project scheduling problem, European Journal of Operational Research (1999) (to appear).

  19. S. Hartmann and A. Sprecher, A note on "Hierarchical models for multi-project planning and scheduling", European Journal of Operational Research 94 (1996) 377–383.

    Google Scholar 

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

    Google Scholar 

  21. U. Kohlmorgen, H. Schmeck and K. Haase, Experiences with fine-grained parallel genetic algorithms, Annals of Operations Research (1999) (to appear).

  22. R. Kolisch, Project scheduling under resource constraints-efficient heuristics for several problem classes, Physica (1995).

  23. 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 

  24. R. Kolisch and A. Drexl, Local search for nonpreemptive multi-mode resource-constrained project scheduling, IIE Transactions 29 (1997) 987–999.

    Google Scholar 

  25. R. Kolisch and S. Hartmann, Heuristic algorithms for solving the resource-constrained project scheduling problem: Classification and computational analysis, in: Project Scheduling: Recent Models, Algorithms and Applications, ed. J. Weglarz (Kluwer Academic, Dordrecht, 1999) pp. 147–178.

    Google Scholar 

  26. R. Kolisch and R. Padman, An Integrated survey of project scheduling, Manuskripte aus den Instituten für Betriebswirtschaftslehre, No. 463, University of Kiel, Germany (1997).

    Google Scholar 

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

    Google Scholar 

  28. 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 

  29. 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 

  30. V. Leon and B. Ramamoorthy, Strength and adaptability of problem-space based neighbourhoods for resource-constrained problem scheduling, OR Spectrum 17(2/3) (1995) 173–182.

    Google Scholar 

  31. V. Maniezzo and A. Mingozzi, A heuristic procedure for the multi-mode project scheduling problem based on Bender's decomposition, in: Project Scheduling: Recent Models, Algorithms and Applications, ed. J. Weglarz (Kluwer Academic, Dordrecht, 1999) pp. 179–196.

    Google Scholar 

  32. N. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Teller and E. Teller, Equation of state calculations by fast computing machines, Journal of Chemical Physics 21 (1953) 1087–1092.

    Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

  36. L. Özdamar and G. Ulusoy, A local constraint based analysis approach to project scheduling under general resource constraints, European Journal of Operational Research 79 (1994) 287–298.

    Google Scholar 

  37. J.H. Patterson, R. S?owi?ski, F.B. Talbot and J. Weglarz, An algorithm for a general class of precedence and resource-constrained scheduling problems, in: Advances in Project Scheduling, eds. R. S?owi?ski and J. Weglarz (Elsevier, Amsterdam, 1989) pp. 3–28.

    Google Scholar 

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

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

    Google Scholar 

  40. R. S?owi?ski, B. Soniewiecki and J. Weglarz, DSS for multiobjective project scheduling subject to multiple-category resource constraints, European Journal of Operational Research 79 (1994) 220–229.

    Google Scholar 

  41. M.G. Speranza and C. Vercellis, Hierarchical models for multi-project planning and scheduling, European Journal of Operational Research 64 (1993) 312–325.

    Google Scholar 

  42. A. Sprecher, Resource-Constrained Project Scheduling: Exact Methods for the Multi-Mode Case, Lecture Notes in Economics and Mathematical Systems 409 (Springer, Berlin, 1994).

    Google Scholar 

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

    Google Scholar 

  44. A. Sprecher, S. Hartmann and A. Drexl, An exact algorithm for project scheduling with multiple modes, OR Spektrum 19 (1997) 195–203.

    Google Scholar 

  45. 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 

  46. F.B. Talbot, Resource-constrained project scheduling with time-resource tradeoffs: The nonpreemptive case, Management Science 28 (1982) 1197–1210.

    Google Scholar 

  47. P.J.M. van Laarhoven and E.H.L. Aarts, Simulated Annealing: Theory and Applications (Reidel, Dordrecht, 1987).

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Computing Science, Poznań University of Technology, Piotrowo 3A, 60-965, Poznań, Poland

    Joanna Józefowska, Marek Mika, Rafał Różycki, Grzegorz Waligóra & Jan Węglarz

Authors
  1. Joanna Józefowska
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Marek Mika
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Rafał Różycki
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Grzegorz Waligóra
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Jan Węglarz
    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

Józefowska, J., Mika, M., Różycki, R. et al. Simulated Annealing for Multi-Mode Resource-Constrained Project Scheduling. Annals of Operations Research 102, 137–155 (2001). https://doi.org/10.1023/A:1010954031930

Download citation

  • Issue Date:

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

Search

Navigation