Skip to main content
SpringerLink
Log in

Project Scheduling with Multiple Modes: A Genetic Algorithm

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

Abstract

In this paper we consider the resource-constrained project scheduling problem with multiple execution modes for each activity and makespan minimization as objective. We present a new genetic algorithm approach to solve this problem. The genetic encoding is based on a precedence feasible list of activities and a mode assignment. After defining the related crossover, mutation, and selection operators, we describe a local search extension which is employed to improve the schedules found by the basic genetic algorithm. Finally, we present the results of our thorough computational study. We determine the best among several different variants of our genetic algorithm and compare it to four other heuristics that have recently been proposed in the literature. The results that have been obtained using a standard set of instances show that the new genetic algorithm outperforms the other heuristic procedures with regard to a lower average deviation from the optimal makespan.

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. K. Backhaus, B. Erichson, W. Plinke and R. Weiber, Multivariate Analysemethoden: Eine anwendungsorientierte Einführung (Springer, Berlin, Germany, 1996).

    Google Scholar 

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

  3. F.F. Boctor, An adaptation of the simulated annealing algorithm for solving resource-constrained project scheduling problems, International Journal of Production Research 34 (1996) 2335–2351.

    Google Scholar 

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

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

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

    Google Scholar 

  7. A.E. Eiben, E.H.L. Aarts and K.M. van Hee, Global convergence of genetic algorithms: A Markov chain analysis, in: Lecture Notes in Comput. Sci. 496 (1990) pp. 4–12.

    Google Scholar 

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

    Google Scholar 

  9. D.E. Goldberg, Genetic Algorithms in Search, Optimization, andMachine Learning (Addison-Wesley, Reading, MA, 1989).

    Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

  12. S. Hartmann and R. Kolisch, Experimental investigation of state-of-the-art heuristics for the resource-constrained project scheduling problem, European Journal of Operational Research 127 (2000) 399–407.

    Google Scholar 

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

    Google Scholar 

  14. U. Kohlmorgen, H. Schmeck and K. Haase, Experiences with fine-grained parallel genetic algorithms, Annals of Operations Research, forthcoming.

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

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

    Google Scholar 

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

    Google Scholar 

  18. 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. W?glarz (Kluwer, Amsterdam, the Netherlands, 1999) pp. 147–178.

    Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

  21. Z. Michalewicz, Heuristic methods for evolutionary computation techniques, Journal of Heuristics 1 (1995) 177–206.

    Google Scholar 

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

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

  24. R. Slowinski, Two approaches to problems of resource allocation among project activities: A comparative study, Journal of the Operational Research Society 31 (1980) 711–723.

    Google Scholar 

  25. R. Slowinski, B. Soniewicki and J. W?glarz, DSS for multiobjective project scheduling subject to multiple-category resource constraints, European Journal of Operational Research 79 (1994) 220–229.

    Google Scholar 

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

    Google Scholar 

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

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

    Google Scholar 

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

    Google Scholar 

  30. D. Whitley, V.S. Gordon and K. Mathias, Lamarckian evolution, the Baldwin effect and function optimization, in: Proceedings of the Parallel Problem Solving from Nature (Springer, Berlin, Germany, 1994) pp. 6–15.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut für Betriebswirtschaftslehre Lehrstuhl für Produktion und Logistik, Christian-Albrechts-Universität zu Kiel, Olshausenstraße 40, 24118, Kiel, Germany

    Sönke Hartmann

  2. LOGAS Gesellschaft für logistische Anwendungssysteme mbH, Gutenberg-Haus, Steckelhörn 5, 20457, Hamburg, Germany

    Sönke Hartmann

Authors
  1. Sönke Hartmann
    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

Hartmann, S. Project Scheduling with Multiple Modes: A Genetic Algorithm. Annals of Operations Research 102, 111–135 (2001). https://doi.org/10.1023/A:1010902015091

Download citation

  • Issue Date:

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

Search

Navigation