Comparing Schedule Generation Schemes in Resource-Constrained Project Scheduling Using Elitist Genetic Algorithm
This article has been corrected.
VIEW CORRECTIONPublication: Journal of Construction Engineering and Management
Volume 136, Issue 2
Abstract
An issue has arisen with regard to which of the schedule generation schemes will perform better for an arbitrary instance of the resource-constrained project scheduling problem (RCPSP), which is one of the most challenging areas in construction engineering and management. No general answer has been given to this issue due to the different mechanisms between the serial scheme and the parallel scheme. In an effort to address this issue, this paper compares the two schemes using a permutation-based Elitist genetic algorithm for the RCPSP. Computational experiments are presented with multiple standard problems. From the results of a paired difference experiment, the algorithm using the serial scheme provides better solutions than the one using the parallel scheme. The results also show that the algorithm with the parallel scheme takes longer to solve each problem than the one using the serial scheme.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
The writers thank two anonymous reviewers for their critical and helpful comments and suggestions that improved the quality of this paper.
References
Baar, T., Brucker, P., and Knust, S. (1999). “Tabu-search algorithms and lower bounds for the resource-constrained project scheduling problem.” Meta-heuristics: Advances and trends in local search paradigms for optimization, S. Voss, S. Martello, I. Osman, and C. Roucairol, eds., Kluwer, Dordrecht, The Netherlands, 1–8.
Bedworth, D. D., and Bailey, J. E. (1982). Integrated production control systems-management, analysis, design, Wiley, New York.
Boctor, F. F. (1996). “Resource-constrained project scheduling by simulated annealing.” Int. J. Prod. Res., 34(8), 2335–2351.
Bouleimen, K., and Lecocq, H. (2003). “A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple modes version.” Eur. J. Oper. Res., 149, 268–281.
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.
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.
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, 733–750.
Hartmann, S. (1999). “Project scheduling under limited resources: Models, methods and applications.” Lec. Notes in Eco. and Math. Sys, Springer, New York.
Hartmann, S., and Kolisch, R. (2000). “Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem.” Eur. J. Oper. Res., 127, 394–407.
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.
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. (2006). “A multiheuristic approach to resource constrained project scheduling: An adaptive hybrid genetic algorithm.” Ph.D. dissertation, Univ. of Florida, Gainesville, Fla.
Kohlmorgen, U., Schmeck, H., and Haase, K. (1999). “Experiences with fine-grained parallel genetic algorithms.” Ann. Operat. Res., 90, 203–219.
Kolisch, R. (1996). “Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation.” Eur. J. Oper. Res., 90, 320–333.
Kolisch, R., and Sprecher, A. (1996). “PSPLIB—A project scheduling problem library.” Eur. J. Oper. Res., 96, 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., Chen, A., and Yang, C. (1999). “Fuzzy optimal model for resource-constrained construction scheduling.” J. Comput. Civ. Eng., 13(3), 207–216.
Leu, S., and Yang, C. (1999). “GA-based multicriteria optimal model for construction scheduling.” J. Constr. Eng. Manage., 125(6), 420–427.
Liu, Y., Zhao, S. -L., Du, X. -K., and Li, S. -Q. (2005). “Optimization of resource allocation in construction using genetic algorithms.” Proc., 2005 Int. Conf. on Machine Learning and Cybernetics, Vol. 6, IEEE Press, Guangzhou, China, 3428–3432.
Meyer, R., and Krueger, D. (1998). A minitab guide to statistics, Prentice-Hall, Upper Saddle River, N.J.
Pinson, E., Prins, C., and Rullier, F. (1994). “Using tabu search for solving the resource-constrained project scheduling problem.” Proc., 4th Int. Work. on Proj. Manage. and Sched., PMS ’94, Leuven, Belgium, 102–106.
Toklu, Y. C. (2002). “Application of genetic algorithms to construction scheduling with or without resource constraints.” Can. J. Civ. Eng., 29, 421–429.
Willis, R. J., and Hastings, N. A. J. (1976). “Project scheduling with resource constraints using branch and bound methods.” Oper. Res. Q., 27(2), 341–349.
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 Int. Design Eng. Tech. Conf. and Comp. and Info. in Eng. Conf., ASME, Salt Lake City, Utah, 1–11.
Information & Authors
Information
Published In
Journal of Construction Engineering and Management
Volume 136 • Issue 2 • February 2010
Pages: 160 - 169
Copyright
© 2010 ASCE.
History
Received: Jun 15, 2007
Accepted: Sep 15, 2009
Published online: Jan 15, 2010
Published in print: Feb 2010
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.