Permutation-Based Elitist Genetic Algorithm for Optimization of Large-Sized Resource-Constrained Project Scheduling
This article has a reply.
VIEW THE REPLYThis article has a reply.
VIEW THE REPLYPublication: Journal of Construction Engineering and Management
Volume 134, Issue 11
Abstract
The resource-constrained project scheduling problem (RCPSP) has received the attention of many researchers because its general model can be used in a wide variety of construction planning and scheduling applications. The exact procedures and priority-rule-based heuristics fail to search for the optimum solution to the RCPSP of large-sized project networks in a reasonable amount of time for successful application in practice. This paper presents a permutation-based elitist genetic algorithm for solving the problem in order to fulfill the lack of an efficient optimal solution algorithm for project networks with 60 activities or more as well as to overcome the drawback of the exact solution approaches for large-sized project networks. The proposed algorithm employs the elitist strategy to preserve the best individual solution for the next generation so the improved solution can be obtained. A random number generator that provides and examines precedence feasible individuals is developed. A serial schedule generation scheme for the permutation-based decoding is applied to generate a feasible solution to the problem. Computational experiments using a set of standard test problems are presented to demonstrate the performance and accuracy of the proposed algorithm.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
The writers wish to thank Dr. Anurag Agarwal at the Dept. of Information Systems and Operations Management, University of Florida for providing the optimal and lower bound solutions and three anonymous reviewers for their helpful suggestions that improved the quality of this paper.
References
Ahn, C. W., Kim, K. P., and Ramakrishna, R. S. (2004). “A memory-efficient elitist genetic algorithm.” Lect. Notes Comput. Sci., 3019 (PPAM’03), 552–559.
Brucker, P., Knust, S., Schoo, A., and Thiele, O. (1998). “A branch and bound algorithm for the resource-constrained project scheduling problem.” Eur. J. Oper. Res., 107(2), 272–288.
Chan, W., Chua, D. K. H., and Kannan, G. (1996). “Construction resource scheduling with genetic algorithms.” J. Constr. Eng. Manage., 122(2), 125–132.
Costa, L., and Oliveira, P. (2004). “An elitist genetic algorithm for multiobjective optimization.” Metaheuristics: Computer decision-making (applied optimization), M. G. Resende and J. Pinho de Sousa, eds., Kluwer Academic, Norwell, Mass., 217–236.
Demeulemeester, E. L., and Herroelen, W. S. (1997). “New benchmark results for the resource-constrained project scheduling problem.” Manage. Sci., 43(11), 1485–1492.
Elazouni, A. M., and Metwally, F. G. (2005). “Finance-based scheduling: Tool to maximize project profit using improved genetic algorithms.” J. Constr. Eng. Manage., 131(4), 400–412.
Geroa, M. B. P., García, A. B., and del Coz Díaz, J. J. (2005). “A modified elitist genetic algorithm applied to the design optimization of complex steel structures.” J. Constr. Steel Res., 61(2), 265–280.
Goldberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning, Addison-Wesley, Reading, Mass.
Hartmann, S. (1998). “A competitive genetic algorithm for resource-constrained project scheduling.” Naval Res. Logistics Quart., 45(7), 733–750.
Hegazy, T. (1999). “Optimization of resource allocation and leveling using genetic algorithms.” J. Constr. Eng. Manage., 125(3), 167–175.
Hegazy, T., and Kassab, M. (2003). “Resource optimization using combined simulation and genetic algorithms.” J. Constr. Eng. Manage., 129(6), 698–705.
Holland, J. K. (1975). Adaptation in neural and artificial systems, University of Michigan Press, Ann Arbor, Mich.
Jaśkowski, P., and Sobotka, A. (2006). “Scheduling construction projects using evolutionary algorithm.” J. Constr. Eng. Manage., 132(8), 861–870.
Kandil, A., and El-Rayes, K. (2006). “Parallel genetic algorithms for optimizing resource utilization in large-scale construction projects.” J. Constr. Eng. Manage., 132(5), 491–498.
Kelley, J. E., Jr. (1963). “The critical-path method: Resources planning and scheduling.” Industrial scheduling, J. F. Muth and G. L. Thompson, eds., Prentice-Hall, Englewood Cliffs, N.J., 347–365.
Kim, J.-L., and Ellis, R. D. (2005). “A framework for integration model of resource-constrained scheduling using genetic algorithms.” Proc., 37th Conf. on Winter Simulation, M. E. Kuhl, N. M. Steiger, F. B. Armstrong, and J. A. Joines, eds., Winter Simulation Conference, 2119–2126.
Kolisch, R., and Sprecher, A. (1996). “PSPLIB—A project scheduling problem library.” Eur. J. Oper. Res., 96(1), 205–216.
Lee, J.-K., and Kim, Y.-D. (1996). “Search heuristics for resource-constrained project scheduling.” J. Oper. Res. Soc., 47(5), 678–689.
Leu, S., and Yang, C. (1999). “GA-based multicriteria optimal model for construction scheduling.” J. Constr. Eng. Manage., 125(6), 420–427.
Majumdar, J., and Bhunia, A. K. (2007). “Elitist genetic algorithm for assignment problem with imprecise goal.” Eur. J. Oper. Res., 177(2), 684–692.
Mingozzi, A., Maniezzo, V., Ricciardelli, S., and Bianco, L. (1998). “An exact algorithm for the resource-constrained project scheduling problem based on a new mathematical formulation.” Manage. Sci., 44(5), 714–729.
Reeves, C. R. (1995). “Genetic algorithms and combinatorial optimization.” Applications of modern heuristic methods, V. J. Rayward-Smith, ed., Alfred Waller, Henley-on-Thames, U.K., 111–125.
Senouci, A. B., and Eldin, N. N. (2004). “Use of genetic algorithms in resource scheduling of construction projects.” J. Constr. Eng. Manage., 130(6), 869–877.
Taranenko, A., and Vesel, A. (2001). “An elitist genetic algorithm for the maximum independent set problem.” Proc., 23rd Int. Conf. on Information Technology Interfaces, ITI 2001, SRCE University Computing Centre, Univ. of Zagreb, Croatia, 373–378.
Toklu, Y. C. (2002). “Application of genetic algorithms to construction scheduling with or without resource constraints.” Can. J. Civ. Eng., 29(3), 421–429.
Zhang, H., Li, H., and Tam, C. M. (2006). “Permutation-based particle swarm optimization for resource-constrained project scheduling.” J. Comput. Civ. Eng., 20(2), 141–149.
Zhuang, M., and Yassine, A. A. (2004). “Task scheduling of parallel development projects using genetic algorithm.” Proc., ASME 2004 Design Engineering Technical Conf. and Computer, and Information in Engineering Conf., ASME, New York, 1–11.
Information & Authors
Information
Published In
Journal of Construction Engineering and Management
Volume 134 • Issue 11 • November 2008
Pages: 904 - 913
Copyright
© 2008 ASCE.
History
Received: Aug 15, 2006
Accepted: May 16, 2008
Published online: Nov 1, 2008
Published in print: Nov 2008
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.