IDEAS home Printed from https://ideas.repec.org/a/iad/wpaper/0307.html
   My bibliography  Save this article

A genetic algorithm for the resource constrained project scheduling problem (RCPSP)

Author

Listed:
  • Edgar Gutiérrez Franco

    (School of Industrial Engeneering, Universidad de La Sabana)

  • Fernando La Torre Zurita

    (Department of Industrial Engeneering, Universidad de los Andes)

  • Gonzalo Mejía Delgadillo

    (Department of Industrial Engeneering, Universidad de los Andes)

Abstract

This paper proposes a Genetic Algorithm for the Resource Constrained Project Scheduling Problem (RCPSP). Resources are renewable and there is a unique way to perform the activities. This work employs Genetics Algorithms to schedule project activities to minimize makespan subject to precedence constraints and resources availability. A serial generation scheme is used to obtain the schedule. The algorithm was programmed using Object Oriented programming that allows generating individuals with their own attributes such as activity sequence and makespan. A Genetic Algorithm (GA) is proposed which uses a novel chromosome representation. The issues of the GA parameter tuning are also discussed in this paper. A computer tool that allows the user to define activities, precedence constraints and resource capacity was developed.

Suggested Citation

  • Edgar Gutiérrez Franco & Fernando La Torre Zurita & Gonzalo Mejía Delgadillo, 2007. "A genetic algorithm for the resource constrained project scheduling problem (RCPSP)," Investigación & Desarrollo, Universidad Privada Boliviana, vol. 1(1), pages 41-52.
    • Handle: RePEc:iad:wpaper:0307
    as

    Download full text from publisher

    File URL: http://www1.upb.edu/RePEc/iad/wpaper/0307.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Debels, Dieter & Vanhoucke, Mario, 2005. "A Bi-Population Based Genetic Algorithm for the Resource-Constrained Project Scheduling Problem," Vlerick Leuven Gent Management School Working Paper Series 2005-8, Vlerick Leuven Gent Management School.
    2. 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.
    3. 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.
    Full references (including those not matched with items on IDEAS)

    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. V. Van Peteghem & M. Vanhoucke, 2008. "A Genetic Algorithm for the Multi-Mode Resource-Constrained Project Scheduling Problem," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 08/494, Ghent University, Faculty of Economics and Business Administration.
    2. Peteghem, Vincent Van & Vanhoucke, Mario, 2010. "A genetic algorithm for the preemptive and non-preemptive multi-mode resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 201(2), pages 409-418, March.
    3. 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.
    4. Deblaere, Filip & Demeulemeester, Erik & Herroelen, Willy, 2011. "Proactive policies for the stochastic resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 214(2), pages 308-316, October.
    5. Xichao Su & Wei Han & Yu Wu & Yong Zhang & Jie Liu, 2018. "A Proactive Robust Scheduling Method for Aircraft Carrier Flight Deck Operations with Stochastic Durations," Complexity, Hindawi, vol. 2018, pages 1-38, November.
    6. Gonzalo Muñoz & Daniel Espinoza & Marcos Goycoolea & Eduardo Moreno & Maurice Queyranne & Orlando Rivera Letelier, 2018. "A study of the Bienstock–Zuckerberg algorithm: applications in mining and resource constrained project scheduling," Computational Optimization and Applications, Springer, vol. 69(2), pages 501-534, March.
    7. Horbach, Andrei, 2009. "A boolean satisfiability approach to the resource-constrained project scheduling problem," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 644, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    8. Nadia Chaudry & Ingunn Vermedal & Kjetil Fagerholt & Maria Fleischer Fauske & Magnus Stålhane, 2020. "A decomposition solution approach to the troops-to-tasks assignment in military peacekeeping operations," The Journal of Defense Modeling and Simulation, , vol. 17(4), pages 357-371, October.
    9. Vanhoucke, Mario & Coelho, José, 2016. "An approach using SAT solvers for the RCPSP with logical constraints," European Journal of Operational Research, Elsevier, vol. 249(2), pages 577-591.
    10. Lei Lei & Michael Pinedo & Lian Qi & Shengbin Wang & Jian Yang, 2015. "Personnel scheduling and supplies provisioning in emergency relief operations," Annals of Operations Research, Springer, vol. 235(1), pages 487-515, December.
    11. Jiang, Yuanchun & Liu, Yezheng & Shang, Jennifer & Yildirim, Pinar & Zhang, Qingfu, 2018. "Optimizing online recurring promotions for dual-channel retailers: Segmented markets with multiple objectives," European Journal of Operational Research, Elsevier, vol. 267(2), pages 612-627.
    12. Debels, D. & Vanhoucke, M., 2006. "Meta-Heuristic resource constrained project scheduling: solution space restrictions and neighbourhood extensions," Vlerick Leuven Gent Management School Working Paper Series 2006-18, Vlerick Leuven Gent Management School.
    13. Hongbo Li & Erik Demeulemeester, 2016. "A genetic algorithm for the robust resource leveling problem," Journal of Scheduling, Springer, vol. 19(1), pages 43-60, February.
    14. Kolisch, R. & Padman, R., 2001. "An integrated survey of deterministic project scheduling," Omega, Elsevier, vol. 29(3), pages 249-272, June.
    15. Coelho, José & Vanhoucke, Mario, 2011. "Multi-mode resource-constrained project scheduling using RCPSP and SAT solvers," European Journal of Operational Research, Elsevier, vol. 213(1), pages 73-82, August.
    16. M. Vanhoucke, 2007. "A genetic algorithm to investigate the trade-off between project lead time and net present value," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 07/456, Ghent University, Faculty of Economics and Business Administration.
    17. Zamani, Reza, 2013. "A competitive magnet-based genetic algorithm for solving the resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 229(2), pages 552-559.
    18. V. Van Peteghem & M. Vanhoucke, 2009. "An Artificial Immune System for the Multi-Mode Resource-Constrained Project Scheduling Problem," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 09/555, Ghent University, Faculty of Economics and Business Administration.

    More about this item

    Keywords

    Calidad de Vida; Análisis de Componentes Principales; PRINQUAL;
    All these keywords.

    JEL classification:

    • C00 - Mathematical and Quantitative Methods - - General - - - General

    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:iad:wpaper:0307. 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: Ricardo Nogales C. (email available below). General contact details of provider: https://edirc.repec.org/data/ciupbbo.html .

    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.