A GENETIC ALGORITHM FOR THE RESOURCE CONSTRAINED PROJECT SCHEDULING PROBLEM (RCPSP)

Authors

  • Edgar Gutiérrez Franco Universidad de La Sabana
  • Fernando La Torre Zurita Universidad de los Andes
  • Gonzalo Mejía Delgadillo Universidad de los Andes

Keywords:

RCPSP, Project Scheduling, Resource Constraints Projects, Genetics Algorithms

Abstract

This paper proposes a Genetic Algorithm (GA) 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 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.

Downloads

Download data is not yet available.

Author Biographies

Edgar Gutiérrez Franco, Universidad de La Sabana

School of Industrial Engineering

Fernando La Torre Zurita, Universidad de los Andes

Department of Industrial Engineering

Gonzalo Mejía Delgadillo, Universidad de los Andes

Department of Industrial Engineering

References

F. Ballestin. Nuevos Métodos de Resolución del Problema de Secuenciación de Proyectos con Recursos Limitados, PhD Thesis; Universidad de Valencia, Spain. Internet: http://www.tdx.cesca.es/TDX-0218104-170322/, [2001].

M. Bartschi. A Genetic Algorithm for Resource-Constrained Scheduling, Master Thesis, Massachusetts Institute of Technology. 1996. Internet: http://lancet.mit.edu/~mwall/phd/thesis/thesis.pdf.

S. Colak. Resource Constrained Scheduling Problem: A Hybrid Neural Approach, s/f; Internet: http://www.cba.ufl.edu/dis/docs/papers/ResourceConstrainedProject

SchedulingAHybridNeuralApproach.pdf.

D. Debels and M. Vanhoucke. A Bi-Population Based Genetic Algorithm for the Resource- Constrained Project Scheduling Problem, February 2005.

D. Debels and M. Vanhoucke. A Decomposition-based Heuristic for the Resource-Constrained Project Scheduling Problem. Available: http://www.feb.ugent.be/fac/research/WP/Papers/wp_05_293.pdf. [February de 2005].

M. Dorigo. The Ant Colony optimization Metaheuristic, 1999, Internet: http://citeseer.ist.psu.edu/cache/papers/cs/29622/http:zSzzSziridia.ulb.ac.bezSz~gdicarozSzPaperszSzOptBook.pdf/dorigo99ant.pdf.

M. Dorigo and T. Stützle. Ant Colony Optimization, 2004, MIT Press; Massachussets, pp.2-39, pp.177-180.

J. Gonçalves et al. “A Genetic Algorithm for the Resource Constrained Multi-Project Scheduling Problem.” Internet: http://public.research.att.com/~mgcr/

/garcmpsp.pdf. January 2006.

S. Hartmann. Project Scheduling Under Limited Resources, Springer, Berlin, 1999.

S. Hartmann. “Self-Adapting Genetic algorithm with an Application to Project Scheduling.” Internet: http://citeseer.ifi.unizh.ch/cache/papers/cs/9819/http:zSzzSzwww.bwl.uni-kiel.dezSzbwlinstitutezSzProdzSzmabzSzsh_homezSzga_ext.pdf/hartmann99selfadapting.pdf. June 1999

S. Hartmann. “A Competitive Genetic Algorithm for Resource-Constrained Project Scheduling.” Internet: http://halfrunt.bwl.uni-kiel.de/bwlinstitute/Prod/mab/hartmann/

ga_sm4.pdf. 1998.

S. Hartmann and A. Drexl. “Project Scheduling with Multiple Modes: A Comparison of Exact Algorithms.” Internet: http://halfrunt.bwl.uni-kiel.de/bwlinstitute/Prod/mab/hartmann/

/exact2.pdf. 1998.

Q. Jiang. (2004).A Genetic Algorithm for Multiple Resource Constrained Project Scheduling, Master Thesis University of Wollongong. Internet: www.library.uow.edu.au/adt-NWU/uploads/approved/adt-NWU20050812.124618/public/02Whole.pdf.

R. Kolisch and A.(March 1996) Sprecher. PSPLIB – Aproject scheduling problem library. Available: http://citeseer.ist.psu.edu/cache/papers/cs/2982/ftp:zSzzSzftp.bwl.unikiel.dezSzpubzSzoperations-researchzSzwp396.pdf/kolisch96psplib.pdf.

D. Merkle et al. Ant Colony Optimization for Resource-Constrained Project Scheduling, pacosy.informatik.uni-leipzig.de/pv/Personen/ middendorf/Papers/RCPSP-GECCO.ps

A. Mingozzi and V. Maniezzo. “An Exact Algorithm for the Resource Constrained Project Scheduling Problem Based on a New Mathematical Formulation.” Internet: www.personal.dundee.ac.uk/~asjain/papers/csts.ps October 1995

M. Pinedo. Operations Scheduling and applications in Manufacturing, Algorithms and Systems, Prentice Hall, New York, Second Edition, 1999.

B. Ragaswany et al. “Tabu Search Candidate List Strategies in Scheduling.” Internet: www.personal.dundee.ac.uk/~asjain/papers/csts.ps. Enero de 1998

Published

2008-01-31

How to Cite

Gutiérrez Franco, E., La Torre Zurita, F., & Mejía Delgadillo, G. (2008). A GENETIC ALGORITHM FOR THE RESOURCE CONSTRAINED PROJECT SCHEDULING PROBLEM (RCPSP). Revista Investigación &Amp; Desarrollo, 1(7). Retrieved from https://www1.upb.edu/revista-investigacion-desarrollo/index.php/id/article/view/94

Issue

Vol. 1 No. 7 (2007)

Section

Economía, Empresa y Sociedad

License

Creative Commons Attribution-Noncommercial-Share Alike
CC BY-NC-SA

This license lets others remix, tweak, and build upon your work for non-commercial purposes, as long as they credit the author(s) and license their new creations under the identical terms.

The authors can enter additional separate contract agreements for non-exclusive distribution of the version of the article published in the magazine (for instance, they may publish it in an institutional repository or a book), subject to an acknowledgement of its initial publication in this magazine.