The week's pick
Random Articles
Reseach Article
An Improved Genetic Algorithm for Resource Constrained Project Scheduling Problem
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 78 - Number 9 |
| Year of Publication: 2013 |
| Authors: S Diana, L Ganapathy, Ashok K Pundir |
10.5120/13520-1302
|
S Diana, L Ganapathy, Ashok K Pundir . An Improved Genetic Algorithm for Resource Constrained Project Scheduling Problem. International Journal of Computer Applications. 78, 9 ( September 2013), 34-39. DOI=10.5120/13520-1302
Abstract
Project scheduling with limited resources is a challenging management problem that is of immense importance to both practitioners and researchers. This problem is known to be NP-hard even under the simplifying assumptions of single renewable resource constraint, its constant availability over time and minimization of makespan as objective. This paper presents an improved Genetic Algorithm (GA) based approach for the single mode resource constrained project scheduling problem (RCPSP) with makespan minimization as objective. The proposed approach uses binary string based representations and operators for chromosomes. The approach was tested on some difficult instances with high optimality gap in the J120 data set of PSPLIB. It was found that the proposed approaches gave better results as compared to activity list based representations that are commonly used.
References
- Agarwal, A. , Colak, S. , Erenguc, S. "A neurogenetic approach for the resource-constrained project scheduling problem", Computers and Operations Research, 38, 2011, 44-50.
- Alcaraz, J. , Maroto, C. "A robust genetic algorithm for resource allocation in project scheduling", Annals of Operations Research, 102, 2001, 83–109.
- Alcaraz, J. , Maroto, C. , Ruiz, R. "Improving the performance of genetic algorithms for the RCPS problem", Proceedings of the Ninth International Workshop on Project Management and Scheduling, 2004, 40– 43.
- Coelho, J. , Tavares, L. "Comparative analysis of meta heuristics for the resource constrained project scheduling problem", Technical report, Instituto Superior Tecnico at Portugal, 2003.
- Debels, D. , Vanhoucke, M. "A Bi-population Based Genetic Algorithm for the Resource-Constrained Project Scheduling Problem", ICCSA, Vol. 4, 2005, 378-387.
- Debels D, Vanhoucke M: A Decomposition-Based Genetic Algorithm for the Resource-Constrained Project-Scheduling Problem. Operations Research 2007; 55: 457-469
- Franco, E. G. , Zurita, F. T. , and Delgadillo, G. M. "A Genetic Algorithm for the Resource Constrained Project Scheduling Problem (RSPSP)", Bolivia Research and Development, Vol. 7, 2007, 41–52.
- Goldberg, D. E. "Genetic algorithms in search, optimization, and machine learning", Addison-Wesley, 1989.
- Goncalves, J. , Mendes, J. , Resende, M. G. C. "A hybrid genetic algorithm for the job shop scheduling problem", European Journal of Operational Research, 167, 2005, 77-95.
- Goncalves, J. , Mendes, J. , Resende, M. G. C. "A random key based genetic algorithm for the resource-constrained project scheduling problem", Computers and Operations research, 36, 2009, 92-109.
- Goncalves, J. , Resende, M. G. C, Mendes, J. "A biased random key genetic algorithm with forward-backward improvement for resource-constrained project scheduling problem", Journal of Heuristics, 17, 2011, 467-486.
- Hartmann, S. "A competitive genetic algorithm for resource-constrained project scheduling", Naval Research Logistics, 45, 1998, 733–750.
- Hartmann, S. "Self-adapting genetic algorithm for project scheduling under resource constraint", Naval Research Logistics, 49, 2002, 433-448.
- Hindi, K. S. , Yang, H. , Fleszar, K. "An evolutionary algorithm for resource-constrained project scheduling", IEEE Transactions on Evolutionary Computation, Vol. 6, 2002, 512–518.
- Holland, J. H. "Adaptation in Natural and Artificial Systems", University of Michigan, Press, Ann Arbor, MI 1975.
- Jin lee Kim. "Hybrid genetic algorithm parameter effects for optimization of construction resource allocation problem", Construction research Congress ASCE, 2012.
- Kanchan, J. , Karuna, J. "A modified genetic algorithm for resource constrained project scheduling problem", International journal of Computer Applications, 57, 2012, 41-45
- Kohlmorgen, U. , Schmeck, H. , Haase, K. "Experiences with fine-grained parallel genetic algorithms", Annals of Operations Research, 90, 1999, 203–219.
- Kolisch, R. , Hartmann, S. "Experimental investigation of heuristics for resource-constrained project scheduling: An update", European Journal of Operational Research, 174, 2006, 23-37
- Lee, J. K. , Kim, Y. D. "Search heuristics for resource constrained project scheduling", Journal of the Operational Research Society, 47, 1996, 678–689.
- Mehdi, D. and Fariborz, J. "A new efficient Genetic algorithm for project scheduling under resource constraints", World Applied Sciences Journal, 7, 2009, 987-997.
- Spears, W. M. , and Dejong, K. A. "On the virtues of parameterized uniform crossover", Proceedings of the Fourth International Conference on Genetic Algorithms, 1991, 230-236.
- Toklu, Y. C. "Application of genetic algorithms to construction scheduling with or without resource constraints", Canadian Journal of Civil Engineering, 29, 2002, 421–429.
- Tormos, P. , Lova, A. "A competitive heuristic solution technique for resource-constrained project scheduling", Annals of Operations Research, 102, 2001, 65–81.
- Valls, V. , Ballestin, F. , Quintanilla, M. S. "A Resource Constrained Project Scheduling: A critical activity reordering heuristic", European Journal of Operational Research, 149, 2003, 282–301.
- Valls, V. , Ballestin, F. , Quintanilla, M. S. "Justification and RCPSP: A technique that pays", European Journal of Operational Research, 165, 2005, 375–86.
- Valls, V. , Ballestin, F. , Quintanilla, M. S. "A hybrid genetic algorithm for the RCPSP", European Journal of Oerational Research, 185, 2008, 496-508.
Index Terms
Keywords