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

Autores/as

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

Palabras clave:

RCPSP, Project Scheduling, Resource Constraints Projects, Genetics Algorithms

Resumen

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.

Descargas

Los datos de descargas todavía no están disponibles.

Afiliación del autor/a

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

Referencias

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

Publicado

31-01-2008

Cómo citar

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). Recuperado a partir de https://www1.upb.edu/revista-investigacion-desarrollo/index.php/id/article/view/94

Número

Vol. 1 Núm. 7 (2007)

Sección

Economía, Empresa y Sociedad

Licencia

Reconocimiento-NoComercial-CompartirIgual
CC BY-NC-SA

Esta licencia permite a otros entremezclar, ajustar y construir a partir de su obra con fines no comerciales, siempre y cuando le reconozcan la autoría y sus nuevas creaciones estén bajo una licencia con los mismos términos.

Los autores pueden realizar acuerdos contractuales adicionales separados para la distribución no exclusiva de la versión publicada del artículo publicado en la revista (por ejemplo, publicarlo en un repositorio institucional o en un libro), sujeto a un reconocimiento de su publicación inicial en esta revista