Constructive Heuristics for Project Scheduling Resource Availability Cost Problem with Tardiness
Publication: Journal of Construction Engineering and Management
Volume 144, Issue 8
Abstract
This work proposes a deterministic and a probabilistic constructive heuristic for solving the project scheduling resource availability cost problem with tardiness (RACPT), as well as a new mixed integer mathematical formulation with disjunctive constraints and time modeled as a continuous variable. Despite its practical relevance, solution methods to solve this problem are scarce in the literature. The proposed algorithms combine the flexibility of an activity with the flexibility of a resource to select the next activity to be scheduled. Several priority rules from the literature were tested, and the best heuristic was selected. The proposed heuristics’ performances were compared with the mathematical formulation solved by an optimization software within a time limit, and the probabilistic constructive heuristic found optimal and near-optimal solutions for small instances. For medium and large instances, it obtained better results than the optimization model in about 20 times lower computational time. The heuristic was also compared with existing solution methods and was applied to a construction practical example, with good overall performance.
Get full access to this article
View all available purchase options and get full access to this article.
Data Availability Statement
Data generated or analyzed during the study are available from the corresponding author by request. Information about the Journal’s data sharing policy can be found here: http://ascelibrary.org/doi/10.1061/(ASCE)CO.1943-7862.0001263.
References
Afshar-Nadjafi, B. 2014a. “Multi-mode resource availability cost problem with recruitment and release dates for resources.” Appl. Math. Modell. 38 (21–22): 5347–5355. https://doi.org/10.1016/j.apm.2014.04.009.
Afshar-Nadjafi, B. 2014b. “Using GRASP for resource availability cost problem with time dependent resource cost.” Econ. Comput. Econ. Cybern. Stud. Res. 48 (1): 1–15.
Afshar-Nadjafi, B., and M. Arani. 2014. “Multimode preemptive resource investment problem subject to due dates for activities: Formulation and solution procedure.” In Advances in operations research. Cairo, Egypt: Hindawi.
Arcus, A. L. 1965. “COMSOAL: A computer method of sequencing operations for assembly lines.” Int. J. Prod. Res. 4 (4): 259–277. https://doi.org/10.1080/00207546508919982.
Chen, L., X. Li, and Z. Cai. 2012. “Heuristic methods for minimizing resource availability costs in multi-mode project scheduling.” In Proc., IEEE Int. Conf. on Systems, Man and Cybernetics, 809–813. New York, NY: IEEE.
Colak, E., and M. Azizoglu. 2014. “A resource investment problem with time/resource trade-offs.” J. Oper. Res. Soc. 65 (5): 777–790. https://doi.org/10.1057/jors.2013.46.
Coughlan, E. T., M. E. Lübbecke, and J. Schulz. 2010. “A branch-and-price algorithm for multi-mode resource leveling.” In Lecture Notes in Computer Science, edited by P. Festa, 226–238. Berlin, Germany: Springer.
Coughlan, E. T., M. E. Lübbecke, and J. Schulz. 2015. “A branch-price-and-cut algorithm for multi-mode resource leveling.” Eur. J. Oper. Res. 245 (1): 70–80. https://doi.org/10.1016/j.ejor.2015.02.043.
Demeulemeester, E. 1995. “Minimizing resource availability costs in time-limited project networks.” Manage. Sci. 41 (10): 1590–1598. https://doi.org/10.1287/mnsc.41.10.1590.
Drexl, A., and A. Kimms. 2001. “Optimization guided lower and upper bounds for the resource investment problem.” J. Oper. Res. Soc. 52 (3): 340–351. https://doi.org/10.1057/palgrave.jors.2601099.
Hartmann, S., and D. Briskorn. 2010. “A survey of variants and extensions of the resource-constrained project scheduling problem.” Eur. J. Oper. Res. 207 (1): 1–14. https://doi.org/10.1016/j.ejor.2009.11.005.
Hattab, A., and M. Haouari. 2016. “Robust resource investment problem with time-dependent resource cost and tardiness penalty.” In Proc., IEEE Int. Conf. on Industrial Engineering and Engineering Management, 1693–1698. New York, NY: IEEE.
Hsu, C.-C., and D. S. Kim. 2005. “A new heuristic for the multi-mode resource investment problem.” J. Oper. Res. Soc. 56 (4): 406–413. https://doi.org/10.1057/palgrave.jors.2601827.
Jaśkowski, P., and A. Sobotka. 2006. “Scheduling construction projects using evolutionary algorithm.” J. Constr. Eng. Manage. 132 (8): 861–870. https://doi.org/10.1061/(ASCE)0733-9364(2006)132:8(861).
Javanmard, S., B. Afshar-Nadjafi, and S. T. A. Niaki. 2017. “Preemptive multi-skilled resource investment project scheduling problem: Mathematical modelling and solution approaches.” Comput. Chem. Eng. 96 (Jan): 55–68. https://doi.org/10.1016/j.compchemeng.2016.11.001.
Jędrzejowicz, P., and E. Ratajczak-Ropel. 2012. “A-Team for solving the resource availability cost problem.” In Proc., Computational Collective Intelligence: Technologies and Applications: ICCCI 2012: Lecture Notes in Computer Science, edited by N. T. Nguyen, K. Hoang, and P. Jędrzejowicz, 443–452. Berlin, Germany: Springer.
Khoshjahan, Y., A. A. Najafi, and B. Afshar-Nadjafi. 2013. “Resource constrained project scheduling problem with discounted earliness-tardiness penalties: Mathematical modeling and solving procedure.” Comput. Ind. Eng. 66 (2): 293–300. https://doi.org/10.1016/j.cie.2013.06.017.
Klein, R. 2000. Scheduling of resource-constrained projects. New York, NY: Springer.
Kolisch, R., and S. Hartmann. 2006. “Experimental investigation of heuristics for resource-constrained project scheduling: An update.” Eur. J. Oper. Res. 174 (1): 23–37. https://doi.org/10.1016/j.ejor.2005.01.065.
Koulinas, G. K., and K. P. Anagnostopoulos. 2013. “A new tabu search-based hyper-heuristic algorithm for solving construction leveling problems with limited resource availabilities.” Autom. Constr. 31 (May): 169–175. https://doi.org/10.1016/j.autcon.2012.11.002.
Li, K. Y., and R. J. Willis. 1992. “An iterative scheduling technique for resource-constrained project scheduling.” Eur. J. Oper. Res. 56 (3): 370–379. https://doi.org/10.1016/0377-2217(92)90320-9.
Liberatore, M. J., B. Pollack-Johnson, and C. A. Smith. 2001. “Project management in construction: Software use and research directions.” J. Constr. Eng. Manage. 127 (2): 101–107. https://doi.org/10.1061/(ASCE)0733-9364(2001)127:2(101).
Liu, M., J. Liu, M. O. Wimmers, and M. Zhou. 2015. “A differential evolution algorithm for resource investiment problem with tardiness.” In Proc., 2015 IEEE Congress on Evolutionary Computation (CEC), 346–352. New York, NY: IEEE.
Meng, H., B. Wang, Y. Nie, X. Xia, and X. Zhang. 2016. “A scatter search hybrid algorithm for resource availability cost problem.” In Vol. 382 of Harmony search algorithm: Advances in intelligent systems and computing, edited by J. Kim and Z. Geem, 39–51. Berlin, Germany: Springer.
Möhring, R. H. 1984. “Minimizing costs of resource requirements in project networks subject to a fixed completion time.” Oper. Res. 32 (1): 89–120. https://doi.org/10.1287/opre.32.1.89.
Najafi, A. A., and F. Azimi. 2009. “A priority rule-based heuristic for resource investment project scheduling problem with discounted cash flows and tardiness penalties.” Math. Prob. Eng. 2009: 1–10. https://doi.org/10.1155/2009/106425.
Neumann, K., C. Schwindt, and J. Zimmermann. 2002. “Recent results on resource-constrained project scheduling with time windows: Models, solution methods, and applications.” Central Eur. J. Oper. Res. 10 (2): 113–148.
Neumann, K., and J. Zimmermann. 1999. “Resource levelling for projects with schedule-dependent time windows.” Eur. J. Oper. Res. 117 (3): 591–605. https://doi.org/10.1016/S0377-2217(98)00272-0.
Neumann, K., and J. Zimmermann. 2000. “Procedures for resource levelling and net present value problems in project scheduling with general temporal and resource constraints.” Eur. J. Oper. Res. 127 (2): 425–443. https://doi.org/10.1016/S0377-2217(99)00498-1.
Qi, J.-J., B. Guo, H.-T. Lei, and T. Zhang. 2014a. “Solving resource availability cost problem in project scheduling by pseudo particle swarm optimization.” J. Syst. Eng. Electron. 25 (1): 69–76. https://doi.org/10.1109/JSEE.2014.00008.
Qi, J.-J., Y.-J. Liu, P. Jiang, and B. Guo. 2015. “Schedule generation scheme for solving multi-mode resource availability cost problem by modified particle swarm optimization.” J. Scheduling 18 (3): 285–298. https://doi.org/10.1007/s10951-014-0374-0.
Qi, J.-J., Y.-J. Liu, H.-T. Lei, and B. Guo. 2014b. “Solving the multi-mode resource availability cost problem in project scheduling based on modified particle swarm optimization.” Arab. J. Sci. Eng. 39 (6): 5279–5288. https://doi.org/10.1007/s13369-014-1162-z.
Ranjbar, M., F. Kianfar, and S. Shadrokh. 2008. “Solving the resource availability cost problem in project scheduling by path relinking and genetic algorithm.” Appl. Math. Comput. 196 (2): 879–888. https://doi.org/10.1016/j.amc.2007.07.022.
Rodrigues, S. B., and D. S. Yamashita. 2010. “An exact algorithm for minimizing resource availability costs in project scheduling.” Eur. J. Oper. Res. 206 (3): 562–568. https://doi.org/10.1016/j.ejor.2010.03.008.
Sabzehparvar, M., S. M. Seyed-Hosseini, and S. Nouri. 2008. “A mathematical model for the multi-mode resource investment problem.” J. Ind. Eng. Int. 4 (7): 25–32.
Shadrokh, S., and F. Kianfar. 2007. “A genetic algorithm for resource investment project scheduling problem, tardiness permitted with penalty.” Eur. J. Oper. Res. 181 (1): 86–101. https://doi.org/10.1016/j.ejor.2006.03.056.
Sprecher, A., and A. Drexl. 1998. “Multi-mode resource-constrained project scheduling by a simple, general and powerful sequencing algorithm.” Eur. J. Oper. Res. 107 (2): 431–450. https://doi.org/10.1016/S0377-2217(97)00348-2.
Tormos, P., and A. Lova. 2003. “An efficient multi-pass heuristic for project scheduling with constrained resources.” Int. J. Prod. Res. 41 (5): 1071–1086. https://doi.org/10.1080/0020754021000033904.
Van Peteghem, V., and M. Vanhoucke. 2013. “An artificial immune system algorithm for the resource availability cost problem.” Flexible Serv. Manuf. J. 25 (1–2): 122–144. https://doi.org/10.1007/s10696-011-9117-0.
Van Peteghem, V., and M. Vanhoucke. 2015. “Heuristic methods for the resource availability cost problem.” In Vol. 1 of Handbook on project management and scheduling, edited by C. Schwindt and J. Zimmermann, 339–359. Cham, Switzerland: Springer.
Viana, A., and J. P. de Sousa. 2000. “Using metaheuristics in multiobjective resource constrained project scheduling.” Eur. J. Oper. Res. 120 (2): 359–374. https://doi.org/10.1016/S0377-2217(99)00163-0.
Yamashita, D. S., V. A. Armentano, and M. Laguna. 2006. “Scatter search for project scheduling with resource availability cost.” Eur. J. Oper. Res. 169 (2): 623–637. https://doi.org/10.1016/j.ejor.2004.08.019.
Yamashita, D. S., and R. Morabito. 2009. “A note on time/cost tradeoff curve generation for project scheduling with multi-mode resource availability costs.” Int. J. Oper. Res. 5 (4): 429–444. https://doi.org/10.1504/IJOR.2009.025702.
Yang, K.-K. 1998. “A comparison of dispatching rules for executing a resource-constrained project with estimated activity durations.” Omega 26 (6): 729–738. https://doi.org/10.1016/S0305-0483(98)00021-8.
Zhu, X., R. Ruiz, S. Li, and X. Li. 2017. “An effective heuristic for project scheduling with resource availability cost.” Eur. J. Oper. Res. 257 (3): 746–762. https://doi.org/10.1016/j.ejor.2016.08.049.
Information & Authors
Information
Published In
Journal of Construction Engineering and Management
Volume 144 • Issue 8 • August 2018
Copyright
©2018 American Society of Civil Engineers.
History
Received: Oct 17, 2017
Accepted: Feb 16, 2018
Published online: Jun 9, 2018
Published in print: Aug 1, 2018
Discussion open until: Nov 9, 2018
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.