IDEAS home Printed from https://ideas.repec.org/a/wly/navres/v45y1998i7p733-750.html
   My bibliography  Save this article

A competitive genetic algorithm for resource‐constrained project scheduling

Author

Listed:
  • Sönke Hartmann

Abstract

In this paper we consider the resource‐constrained project scheduling problem (RCPSP) with makespan minimization as objective. We propose a new genetic algorithm approach to solve this problem. Subsequently, we compare it to two genetic algorithm concepts from the literature. While our approach makes use of a permutation based genetic encoding that contains problem‐specific knowledge, the other two procedures employ a priority value based and a priority rule based representation, respectively. Then we present the results of our thorough computational study for which standard sets of project instances have been used. The outcome reveals that our procedure is the most promising genetic algorithm to solve the RCPSP. Finally, we show that our genetic algorithm yields better results than several heuristic procedures presented in the literature. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 733–750, 1998

Suggested Citation

  • Sönke Hartmann, 1998. "A competitive genetic algorithm for resource‐constrained project scheduling," Naval Research Logistics (NRL), John Wiley & Sons, vol. 45(7), pages 733-750, October.
    • Handle: RePEc:wly:navres:v:45:y:1998:i:7:p:733-750
    DOI: 10.1002/(SICI)1520-6750(199810)45:73.0.CO;2-C
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/(SICI)1520-6750(199810)45:73.0.CO;2-C
    Download Restriction: no
    File URL: https://libkey.io/10.1002/(SICI)1520-6750(199810)45:73.0.CO;2-C?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Erik Demeulemeester & Willy Herroelen, 1992. "A Branch-and-Bound Procedure for the Multiple Resource-Constrained Project Scheduling Problem," Management Science, INFORMS, vol. 38(12), pages 1803-1818, December.
    2. Brucker, Peter & Knust, Sigrid & Schoo, Arno & Thiele, Olaf, 1998. "A branch and bound algorithm for the resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 107(2), pages 272-288, June.
    3. Ozdamar, Linet & Ulusoy, Gunduz, 1994. "A local constraint based analysis approach to project scheduling under general resource constraints," European Journal of Operational Research, Elsevier, vol. 79(2), pages 287-298, December.
    4. Aristide Mingozzi & Vittorio Maniezzo & Salvatore Ricciardelli & Lucio Bianco, 1998. "An Exact Algorithm for the Resource-Constrained Project Scheduling Problem Based on a New Mathematical Formulation," Management Science, INFORMS, vol. 44(5), pages 714-729, May.
    5. Erik L. Demeulemeester & Willy S. Herroelen, 1997. "New Benchmark Results for the Resource-Constrained Project Scheduling Problem," Management Science, INFORMS, vol. 43(11), pages 1485-1492, November.
    6. Rainer Kolisch & Arno Sprecher & Andreas Drexl, 1995. "Characterization and Generation of a General Class of Resource-Constrained Project Scheduling Problems," Management Science, INFORMS, vol. 41(10), pages 1693-1703, October.
    7. Scott E. Sampson & Elliott N. Weiss, 1993. "Local search techniques for the generalized resource constrained project scheduling problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 40(5), pages 665-675, August.
    8. Kolisch, Rainer, 1996. "Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation," European Journal of Operational Research, Elsevier, vol. 90(2), pages 320-333, April.
    9. Rainer Kolisch & Andreas Drexl, 1996. "Adaptive search for solving hard project scheduling problems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 43(1), pages 23-40, February.
    10. Kolisch, Rainer & Sprecher, Arno, 1996. "PSPLIB - a project scheduling problem library," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 396, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    11. James H. Patterson, 1984. "A Comparison of Exact Approaches for Solving the Multiple Constrained Resource, Project Scheduling Problem," Management Science, INFORMS, vol. 30(7), pages 854-867, July.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. André Schnabel & Carolin Kellenbrink & Stefan Helber, 2018. "Profit-oriented scheduling of resource-constrained projects with flexible capacity constraints," Business Research, Springer;German Academic Association for Business Research, vol. 11(2), pages 329-356, September.
    2. Sepehr Proon & Mingzhou Jin, 2011. "A genetic algorithm with neighborhood search for the resource‐constrained project scheduling problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 58(2), pages 73-82, March.
    3. Feifei Li & Zhe Xu, 2018. "A multi-agent system for distributed multi-project scheduling with two-stage decomposition," PLOS ONE, Public Library of Science, vol. 13(10), pages 1-24, October.
    4. Haneen Algethami & Anna Martínez-Gavara & Dario Landa-Silva, 2019. "Adaptive multiple crossover genetic algorithm to solve workforce scheduling and routing problem," Journal of Heuristics, Springer, vol. 25(4), pages 753-792, October.
    5. Vega-Velázquez, Miguel Ángel & García-Nájera, Abel & Cervantes, Humberto, 2018. "A survey on the Software Project Scheduling Problem," International Journal of Production Economics, Elsevier, vol. 202(C), pages 145-161.
    6. Andreas Schirmer, 2000. "Case‐based reasoning and improved adaptive search for project scheduling," Naval Research Logistics (NRL), John Wiley & Sons, vol. 47(3), pages 201-222, April.
    7. Sönke Hartmann, 2002. "A self‐adapting genetic algorithm for project scheduling under resource constraints," Naval Research Logistics (NRL), John Wiley & Sons, vol. 49(5), pages 433-448, August.
    8. Abdollah Arasteh, 2020. "Considering Project Management Activities for Engineering Design Groups," SN Operations Research Forum, Springer, vol. 1(4), pages 1-29, December.
    9. Anıl Can & Gündüz Ulusoy, 2014. "Multi-project scheduling with two-stage decomposition," Annals of Operations Research, Springer, vol. 217(1), pages 95-116, June.
    10. Florian Mischek & Nysret Musliu, 2021. "A local search framework for industrial test laboratory scheduling," Annals of Operations Research, Springer, vol. 302(2), pages 533-562, July.
    11. Dieter Debels & Mario Vanhoucke, 2007. "A Decomposition-Based Genetic Algorithm for the Resource-Constrained Project-Scheduling Problem," Operations Research, INFORMS, vol. 55(3), pages 457-469, June.
    12. Luise-Sophie Hoffmann & Carolin Kellenbrink & Stefan Helber, 2020. "Simultaneous structuring and scheduling of multiple projects with flexible project structures," Journal of Business Economics, Springer, vol. 90(5), pages 679-711, June.
    13. Rob Eynde & Mario Vanhoucke, 2020. "Resource-constrained multi-project scheduling: benchmark datasets and decoupled scheduling," Journal of Scheduling, Springer, vol. 23(3), pages 301-325, June.
    14. José Romualdo Costa Filho & Renato Penha & Luciano Ferreira Silva & Flavio Santino Bizarrias, 2022. "Competencies for Managing Activities in Agile Projects," Global Journal of Flexible Systems Management, Springer;Global Institute of Flexible Systems Management, vol. 23(4), pages 431-452, December.
    15. Jürgen Kuster & Dietmar Jannach & Gerhard Friedrich, 2010. "Applying Local Rescheduling in response to schedule disruptions," Annals of Operations Research, Springer, vol. 180(1), pages 265-282, November.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Kolisch, R. & Padman, R., 2001. "An integrated survey of deterministic project scheduling," Omega, Elsevier, vol. 29(3), pages 249-272, June.
    2. Brucker, Peter & Drexl, Andreas & Mohring, Rolf & Neumann, Klaus & Pesch, Erwin, 1999. "Resource-constrained project scheduling: Notation, classification, models, and methods," European Journal of Operational Research, Elsevier, vol. 112(1), pages 3-41, January.
    3. Sönke Hartmann, 2002. "A self‐adapting genetic algorithm for project scheduling under resource constraints," Naval Research Logistics (NRL), John Wiley & Sons, vol. 49(5), pages 433-448, August.
    4. Dieter Debels & Mario Vanhoucke, 2007. "A Decomposition-Based Genetic Algorithm for the Resource-Constrained Project-Scheduling Problem," Operations Research, INFORMS, vol. 55(3), pages 457-469, June.
    5. Pfeifer, Jeremy & Barker, Kash & Ramirez-Marquez, Jose E. & Morshedlou, Nazanin, 2015. "Quantifying the risk of project delays with a genetic algorithm," International Journal of Production Economics, Elsevier, vol. 170(PA), pages 34-44.
    6. Chen, Jiaqiong & Askin, Ronald G., 2009. "Project selection, scheduling and resource allocation with time dependent returns," European Journal of Operational Research, Elsevier, vol. 193(1), pages 23-34, February.
    7. Klein, Robert & Scholl, Armin, 1999. "Computing lower bounds by destructive improvement: An application to resource-constrained project scheduling," European Journal of Operational Research, Elsevier, vol. 112(2), pages 322-346, January.
    8. Debels, Dieter & De Reyck, Bert & Leus, Roel & Vanhoucke, Mario, 2006. "A hybrid scatter search/electromagnetism meta-heuristic for project scheduling," European Journal of Operational Research, Elsevier, vol. 169(2), pages 638-653, March.
    9. Guo, Weikang & Vanhoucke, Mario & Coelho, José, 2023. "A prediction model for ranking branch-and-bound procedures for the resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 306(2), pages 579-595.
    10. Klein, Robert, 2000. "Bidirectional planning: improving priority rule-based heuristics for scheduling resource-constrained projects," European Journal of Operational Research, Elsevier, vol. 127(3), pages 619-638, December.
    11. Weglarz, Jan & Józefowska, Joanna & Mika, Marek & Waligóra, Grzegorz, 2011. "Project scheduling with finite or infinite number of activity processing modes - A survey," European Journal of Operational Research, Elsevier, vol. 208(3), pages 177-205, February.
    12. D. Debels & M. Vanhoucke, 2005. "A Decomposition-Based Heuristic For The Resource-Constrained Project Scheduling Problem," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/293, Ghent University, Faculty of Economics and Business Administration.
    13. Arno Sprecher, 2000. "Scheduling Resource-Constrained Projects Competitively at Modest Memory Requirements," Management Science, INFORMS, vol. 46(5), pages 710-723, May.
    14. Sprecher, Arno, 1999. "Network decomposition techniques for resource-constrained project scheduling," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 505, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    15. Hartmann, Sönke, 1999. "Self-adapting genetic algorithms with an application to project scheduling," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 506, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    16. Sophie Demassey & Christian Artigues & Philippe Michelon, 2005. "Constraint-Propagation-Based Cutting Planes: An Application to the Resource-Constrained Project Scheduling Problem," INFORMS Journal on Computing, INFORMS, vol. 17(1), pages 52-65, February.
    17. Schirmer, Andreas & Riesenberg, Sven, 1998. "Class-based control schemes for parameterized project scheduling heuristics," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 471, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    18. Jan Böttcher & Andreas Drexl & Rainer Kolisch & Frank Salewski, 1999. "Project Scheduling Under Partially Renewable Resource Constraints," Management Science, INFORMS, vol. 45(4), pages 543-559, April.
    19. Carlier, Jacques & Neron, Emmanuel, 2000. "A new LP-based lower bound for the cumulative scheduling problem," European Journal of Operational Research, Elsevier, vol. 127(2), pages 363-382, December.
    20. Schirmer, Armin, 1998. "Adaptive control schemes for parameterized heuristic scheduling," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 488, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:wly:navres:v:45:y:1998:i:7:p:733-750. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Wiley Content Delivery (email available below). General contact details of provider: https://doi.org/10.1002/(ISSN)1520-6750 .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.