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

Edgar Gutiérrez Franco, Fernando La Torre Zurita, Gonzalo Mejía Delgadillo

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.

Palabras clave


RCPSP, Project Scheduling, Resource Constraints Projects, Genetics Algorithms

Texto completo:

ABSTRACT RESUMEN FULL ARTICLE

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


Enlaces refback

  • No hay ningún enlace refback.


ESTADÍSTICAS DEL ARTICULO
Resumen : 346
ARCHIVO PDF ABSTRACT : 71
ARCHIVO PDF RESUMEN : 43
ARCHIVO PDF FULL ARTICLE : 116



Copyright (c) 2018 Revista Investigación & Desarrollo

Licencia de Creative Commons
Este obra está bajo una licencia de Creative Commons Reconocimiento-NoComercial-CompartirIgual 4.0 Internacional.