Construction Resource Allocation and Leveling Using a Threshold Accepting–Based Hyperheuristic Algorithm
Publication: Journal of Construction Engineering and Management
Volume 138, Issue 7
Abstract
In this study we propose a threshold accepting based hyperheuristic for solving in a single run both the resource-constrained project scheduling problem or resource allocation, and the resource leveling problem. Having their roots in the field of artificial intelligence, hyperheuristics operate in the “low-level” heuristics domain rather than in the solutions domain. The hyperheuristic has been implemented within a commercial project management software package. Low-level heuristics operate on the solution domain defined by the priority values that the software uses for resource allocation. A case example from the literature and computational experiments on randomly generated projects demonstrate that the hyperheuristic achieves good performance in a timely manner, improving the results provided by the software.
Get full access to this article
View all available purchase options and get full access to this article.
References
Ahuja, H. N. (1976). Construction Performance Control by Networks, Wiley, NY.
Anagnostopoulos, K. P., and Koulinas, G. K. (2010). “A simulated annealing hyperheuristic for construction resource levelling.” Constr. Manage. Econ, 28(2), 163–175.
Anagnostopoulos, K., and Koulinas, G. (2011). “Resource-constrained critical path scheduling by a GRASP based hyperheuristic.” J. Comput. Civ. Eng., xxx(none), xxx–xxx. (Mar. 12, 2011).JCCEE5
Bandelloni, M., Tucci, M., and Rinaldi, R. (1994). “Optimal resource leveling using non-serial dynamic programming.” Eur. J. Oper. Res., 78(2), 162–177.EJORDT
Boctor, F. F. (1990). “Some efficient multi-heuristic procedures for resource-constrained project scheduling.” Eur. J. Oper. Res., 49(1), 3–13.EJORDT
Boctor, F. F. (1996). “Resource-constrained project scheduling by simulated annealing.” Int. J. Prod. Res., 34(8), 2335–2351.IJPRB8
Bouleimen, K., and Lecocq, H. (2003). “A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version.” Eur. J. Oper. Res., 149(2), 268–281.EJORDT
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.EJORDT
Burgess, A. R., and Killebrew, J. B. (1962). “Variation in activity level on a cyclic arrow diagram.” Ind. Eng.ILENDP, 13(2), 76–83.
Burke, E., Kendall, G., Newall, J., Hart, E., Ross, P., and Schulenburg, S. (2003a). “Hyperheuristics: An emerging direction in modern search technology.” Handbook of Metaheuristics, Glover, F. and Kochenberger, G. A., eds., Kluwer Academic Publishers, Dordrecht, 457–474.
Burke, E., Kendall, G., and Soubeiga, E. (2003b). “A tabu search hyperheuristic for timetabling and rostering.” J. Heuristics, 9(6), 451–470.
Burke, E. K., Kendall, G., Landa-Silva, D., O’Brien, R., and Soubeiga, E. (2005). “An ant algorithm hyperheuristic for the project presentation scheduling problem.” Proc., 2005 IEEE Congr. on Evol. Comput. (CEC 2005), IEEE Computer Society Press, Edinburgh, Scotland, 2263–2270.
Chakhlevitch, K., and Cowling, P. (2008). “Hyperheuristics: Recent developments.” Adaptive and Multilevel Metaheuristics, Studies in Computational Intelligence, Cotta, C., Sevaux, M. and Sorensen, K., eds., vol. 136, Springer, Berlin, 3–29.
Chan, W., Chua, D. K. H., and Kannan, G. (1996). “Construction resource scheduling with genetic algorithms.” J. Constr. Eng. Manage.JCEMD4, 122(2), 125–132.
Christodoulou, S. (2010). “Scheduling resource-constrained projects with ant colony optimization artificial agents.” J. Comput. Civ. Eng., 24(1), 45–55.JCCEE5
Cowling, P., Kendall, G., and Soubeiga, E. (2001). “A hyperheuristic approach to scheduling a sales summit.” Practice and Theory of Automated Timetabling III, Lecture Notes in Computer Science, Burke, E. and Erben, W., eds., vol. 2079, Springer, Heidelberg, 176–190.
Demeulemeester, E., and Herroelen, W. (1992). “A branch-and-bound procedure for the multiple resource-constrained project scheduling problem.” Manage. Sci., 38(12), 1803–1818.MSCIAM
Demeulemeester, E. L., and Herroelen, W. S. (2002). Project Scheduling—A Research Handbook, Kluwer Academic Publishers, Boston.
Dorndorf, U., and Pesch, E. (1995). “Evolution based learning in a job shop scheduling environment.” Comput. Oper. Res., 22(1), 25–40.CMORAP
Dowsland, K. A., Soubeiga, E., and Burke, E. (2007). “A simulated annealing based hyperheuristic for determining shipper sizes for storage and transportation.” Eur. J. Oper. Res., 179(3), 759–774.EJORDT
Dueck, G. (1990). “Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing.” J. Comput. Phys., 90(1), 161–175.JCTPAH
Easa, S. M. (1989). “Resource leveling in construction by optimization.” J. Constr. Eng. Manage.JCEMD4, 115(2), 302–316.
Fisher, H., and Thompson, G. L. (1963). “Probabilistic learning combinations of local job shop scheduling rules.” Industrial Scheduling, Muth, J. F. and Thompson, G. L., eds, Prentice Hall, Englewood Cliffs, 225–251.
Gavish, B., and Pirkul, H. (1991). “Algorithms for multi-resource generalized assignment problem.” Manage. Sci. J., 37(6), 695–713.
Han, L., and Kendall, G. (2003). “An investigation of a tabu assisted hyperheuristic genetic algorithm.” Proc., 2003 IEEE Congr. on Evol. Comput. (CEC 2003), IEEE Computer Society Press, Canberra, Australia, 2230–2237.
Harris, R. B. (1990). “Packing method for resource leveling (PACK).” J. Constr. Eng. Manage.JCEMD4, 116(2), 331–350.
Hartmann, S. (1998). “A competitive genetic algorithm for resource-constrained project scheduling.” Nav. Res. Logist. Q., 45(7), 733–750.NRLQAR
Hartmann, S., and Briskorn, D. (2010). “A survey of variants and extensions of the resource constrained project scheduling problem.” Eur. J. Oper. Res., 207(1), 1–14.EJORDT
Hegazy, T. (1999). “Optimization of resource allocation and leveling using genetic algorithms.” J. Constr. Eng. Manage.JCEMD4, 125(3), 167–175.
Hiyassat, M. A. S. (2000). “Modification of minimum moment approach in resource leveling.” J. Constr. Eng. Manage.JCEMD4, 126(4), 278–284.
Kolisch, R. (1996). “Efficient priority rules for the resource-constrained project scheduling problem.” J. Oper. Manage.JOTMES, 14(3), 179–192.
Leu, S. S., Yang, C. H., and Huang, J. C. (2000). “Resource leveling in construction by genetic algorithm-based optimization and its decision support system application.” Autom. Constr.AUCOES, 10(1), 27–41.
Lova, A., Tormos, P., Cervantes, M., and Barber, F. (2009). “An efficient hybrid genetic algorithm for scheduling projects with resource constraints and multiple execution modes.” Int. J. Prod. Econ., 117(2), 302–316.IJPCEY
Montgomery, D. C. (2001). Design and Analysis of Experiments, 5th Ed., Wiley, NY.
Neumann, K., and Zimmermann, J. (1999). “Resource leveling for projects with schedule-dependent time windows.” Eur. J. Oper. Res., 117(3), 591–605.EJORDT
Neumann, K., and Zimmermann, J. (2000). “Procedures for resource leveling and net present value problems in project scheduling with general temporal and resource constraints.” Eur. J. Oper. Res., 127(2), 425–443.EJORDT
Nonobe, K., and Ibaraki, T. (2001). “Formulation and tabu search algorithm for the resource constrained project scheduling problem.” Essays and Surveys in Metaheuristics, Ribeiro, C. C. and Hansen, P., eds., Kluwer Academic Publishers, Dordrecht, 557–588.
Ouelhadj, D., and Petrovic, S. (2010). “A cooperative hyperheuristic search framework.” J. Heuristics, 16(6), 835–857.
Pan, N. H., Hsaio, P. W., and Chen, K. Y. (2008). “A study of project scheduling optimization using Tabu Search algorithm.” Eng. Appl. Artif. Intell., 21(7), 1101–1112.EAAIE6
Qu, R., and Burke, E. K. (2009). “Hybridizations within a graph-based hyperheuristic framework for univ. timetabling problems.” J. Oper. Res. Soc., 60(9), 1273–1285.JORSDZ
Savin, D., Alkass, S., and Fazio, P. (1996). “Construction resource leveling using neural networks.” Can. J. Civ. Eng., 23(4), 917–925.CJCEB8
Senouci, A. B., and Eldin, N. N. (2004). “Use of genetic algorithms in resource scheduling of construction projects.” J. Constr. Eng. Manage.JCEMD4, 130(6), 869–877.
Storer, R. H., Wu, S. D., and Vaccari, R. (1995). “Problem and heuristic search space strategies for job shop scheduling.” ORSA J. Comput., 7(4), 453–467.OJCOE3
Weglarz, J., Jozefowska, J., Mika, M., and Waligora, G. (2011). “Project scheduling with finite or infinite number of activity processing modes—A survey.” Eur. J. Oper. Res., 208(3), 177–205.EJORDT
Winker, P., and Maringer, D. (2007). “The threshold accepting optimization algorithm in economics and statistics.” Optimization, Econometric and Financial Analysis, Kontoghiorghes, E. J. and Gatu, C., eds., Springer, Berlin, 107–125.
Zhang, H., Li, H., and Tam, C. M. (2006a). “Permutation-based particle swarm optimization for resource-constrained project scheduling.” J. Comput. Civ. Eng., 20(2), 141–149.JCCEE5
Zhang, H., Li, H., and Tam, C. M. (2006b). “Particle swarm optimization for preemptive scheduling under break and resource-constraints.” J. Constr. Eng. Manage.JCEMD4, 132(3), 259–267.
Information & Authors
Information
Published In
Journal of Construction Engineering and Management
Volume 138 • Issue 7 • July 2012
Pages: 854 - 863
Copyright
© 2012. American Society of Civil Engineers.
History
Received: Aug 1, 2010
Accepted: Sep 22, 2011
Published online: Sep 26, 2011
Published in print: Jul 1, 2012
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.