Activity Uncrashing Heuristic with Noncritical Activity Rescheduling Method for the Discrete Time-Cost Trade-Off Problem
Publication: Journal of Construction Engineering and Management
Volume 146, Issue 8
Abstract
Despite intensive research efforts that have been devoted to discrete time-cost optimization of construction projects, the current methods have very limited capabilities for solving the problem for real-life–sized projects. This study presents a new activity uncrashing heuristic with noncritical activity rescheduling method to narrow the gap between the research and practice for time-cost optimization. The uncrashing heuristic searches for new solutions by uncrashing the critical activities with the highest cost-slope. This novel feature of the proposed heuristic enables identification and elimination of the dominated solutions during the search procedure. Hence, the heuristic can determine new high-quality solutions based on the nondominated solutions. Furthermore, the proposed noncritical activity rescheduling method of the heuristic decreases the amount of scheduling calculations, and high-quality solutions are achieved within a short CPU time. Results of the computational experiments reveal that the new heuristic outperforms state-of-the-art methods significantly for large-scale single-objective cost minimization and Pareto front optimization problems. Hence, the primary contribution of the paper is a new heuristic method that can successfully achieve high-quality solutions for large-scale discrete time-cost optimization problems.
Get full access to this article
View all available purchase options and get full access to this article.
Data Availability Statement
Data generated by the authors or analyzed during the study are available at https://blog.metu.edu.tr/rsonmez/research/dtctp, and http://etd.lib.metu.edu.tr/upload/12622120/index.pdf.
Acknowledgments
The authors gratefully acknowledge the financial support provided by the Scientific and Technological Research Council of Turkey (TÜBİTAK), under Grant No. 213M253.
References
Abuwarda, Z., and T. Hegazy. 2019. “Multi-dimensional optimization model for schedule fast-tracking without over-stressing construction workers.” Can. J. Civ. Eng. 46 (12): 1160–1173. https://doi.org/10.1139/cjce-2018-0544.
Afshar, A., A. Ziaraty, A. Kaveh, and F. Sharifi. 2009. “Nondominated archiving multicolony ant algorithm in time–cost trade-off optimization.” J. Constr. Eng. Manage. 135 (7): 668–674. https://doi.org/10.1061/(ASCE)0733-9364(2009)135:7(668).
Agdas, D., D. J. Warne, J. Osio-Norgaard, and F. J. Masters. 2018. “Utility of genetic algorithms for solving large-scale construction time-cost trade-off problems.” J. Comput. Civ. Eng. 32 (1): 04017072. https://doi.org/10.1061/(ASCE)CP.1943-5487.0000718.
Akkan, C., A. Drexl, and A. Kimms. 2005. “Network decomposition-based benchmark results for the discrete time–cost tradeoff problem.” Eur. J. Oper. Res. 165 (2): 339–358. https://doi.org/10.1016/j.ejor.2004.04.006.
Al Haj, R. A., and S. M. El-Sayegh. 2015. “Time–cost optimization model considering float-consumption impact.” J. Constr. Eng. Manage. 141 (5): 04015001. https://doi.org/10.1061/(ASCE)CO.1943-7862.0000966.
Aminbakhsh, S. 2018. “Heuristic and exact methods for the large-scale discrete time-cost trade-off problems.” Ph.D. thesis, Dept. of Civil Engineering, Middle East Technical Univ.
Aminbakhsh, S., and R. Sonmez. 2016. “Discrete particle swarm optimization method for the large-scale discrete time–cost trade-off problem.” Expert Syst. Appl. 51 (Jun): 177–185. https://doi.org/10.1016/j.eswa.2015.12.041.
Aminbakhsh, S., and R. Sonmez. 2017. “Pareto front particle swarm optimizer for discrete time-cost trade-off problem.” J. Comput. Civ. Eng. 31 (1): 04016040. https://doi.org/10.1061/(ASCE)CP.1943-5487.0000606.
Bader, J. M. 2010. Hypervolume-based search for multiobjective optimization: Theory and methods (No. 112). Zurich, Switzerland: Johannes Bader.
Beume, N., B. Naujoks, and M. Emmerich. 2007. “SMS-EMOA: Multiobjective selection based on dominated hypervolume.” Eur. J. Oper. Res. 181 (3): 1653–1669. https://doi.org/10.1016/j.ejor.2006.08.008.
De, P., E. James Dunne, J. B. Ghosh, and C. E. Wells. 1995. “The discrete time-cost tradeoff problem revisited.” Eur. J. Oper. Res. 81 (2): 225–238. https://doi.org/10.1016/0377-2217(94)00187-H.
Elbeltagi, E., T. Hegazy, and D. Grierson. 2005. “Comparison among five evolutionary-based optimization algorithms.” Adv. Eng. Inf. 19 (1): 43–53. https://doi.org/10.1016/j.aei.2005.01.004.
Elbeltagi, E., T. Hegazy, and D. Grierson. 2007. “A modified shuffled frog-leaping optimization algorithm: Applications to project management.” Struct. Infrastruct. Eng. 3 (1): 53–60. https://doi.org/10.1080/15732470500254535.
Feng, C. W., L. Liu, and S. A. Burns. 1997. “Using genetic algorithms to solve construction time-cost trade-off problems.” J. Comput. Civ. Eng. 11 (3): 184–189. https://doi.org/10.1061/(ASCE)0887-3801(1997)11:3(184).
Goyal, S. K. 1975. “A note on a simple CPM time-cost tradeoff algorithm.” Manage. Sci. 21 (6): 718–722. https://doi.org/10.1287/mnsc.21.6.718.
Hegazy, T. 1999. “Optimization of construction time-cost trade-off analysis using genetic algorithms.” Can. J. Civ. Eng. 26 (6): 685–697. https://doi.org/10.1139/l99-031.
Kandil, A. 2005. “Multi-objective optimization for large-scale highway construction projects.” Ph.D. thesis, Dept. of Civil Engineering, Univ. of Illinois at Urbana Champaign.
Kandil, A., and K. El-Rayes. 2006. “Parallel genetic algorithms for optimizing resource utilization in large-scale construction projects.” J. Constr. Eng. Manage. 132 (5): 491–498. https://doi.org/10.1061/(ASCE)0733-9364(2006)132:5(491).
Klanšek, U. 2015. “Mixed-integer nonlinear programming model for nonlinear discrete optimization of project schedules under restricted costs.” J. Constr. Eng. Manage. 142 (3): 04015088. https://doi.org/10.1061/(ASCE)CO.1943-7862.0001074.
Knowles, J. 2006. “ParEGO: A hybrid algorithm with on-line landscape approximation for expensive multiobjective optimization problems.” IEEE Trans. Evol. Comput. 10 (1): 50–66. https://doi.org/10.1109/TEVC.2005.851274.
Liberatore, M., B. Pollack-Johnson, and C. 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).
Ng, S., and Y. Zhang. 2008. “Optimizing construction time and cost using ant colony optimization approach.” J. Constr. Eng. Manage. 134 (9): 721–728. https://doi.org/10.1061/(ASCE)0733-9364(2008)134:9(721).
Siemens, N. 1971. “A simple CPM time-cost tradeoff algorithm.” Manage. Sci. 17 (6): B-354–B-363. https://doi.org/10.1287/mnsc.17.6.B354.
Sonmez, R., and Ö. H. Bettemir. 2012. “A hybrid genetic algorithm for the discrete time–cost trade-off problem.” Expert Syst. Appl. 39 (13): 11428–11434. https://doi.org/10.1016/j.eswa.2012.04.019.
Vanhoucke, M. 2005. “New computational results for the discrete time/cost trade-off problem with time-switch constraints.” Eur. J. Oper. Res. 165 (2): 359–374. https://doi.org/10.1016/j.ejor.2004.04.007.
Vanhoucke, M., J. Coelho, D. Debels, B. Maenhout, and L. V. Tavares. 2008. “An evaluation of the adequacy of project network generators with systematically sampled networks.” Eur. J. Oper. Res. 187 (2): 511–524. https://doi.org/10.1016/j.ejor.2007.03.032.
Vanhoucke, M., and D. Debels. 2007. “The discrete time/cost trade-off problem: Extensions and heuristic procedures.” J. Scheduling 10 (4–5): 311–326. https://doi.org/10.1007/s10951-007-0031-y.
Van Veldhuizen D. A. 1999. “Multiobjective evolutionary algorithms: Classifications, analyses, and new innovations.” Ph.D. thesis, Graduate School of Engineering, Air Force Institute of Technology, Air Univ.
Yang, I. 2007. “Using elitist particle swarm optimization to facilitate bicriterion time-cost trade-off analysis.” J. Constr. Eng. Manage. 133 (7): 498–505. https://doi.org/10.1061/(ASCE)0733-9364(2007)133:7(498).
Yang, I. T., Y. C. Lin, and H. Y. Lee. 2013. “Use of support vector regression to improve computational efficiency of stochastic time-cost trade-off.” J. Constr. Eng. Manage. 140 (1): 04013036. https://doi.org/10.1061/(ASCE)CO.1943-7862.0000784.
Zhang, H., and H. Li. 2010. “Multi-objective particle swarm optimization for construction time-cost tradeoff problems.” Constr. Manage. Econ. 28 (1): 75–88. https://doi.org/10.1080/01446190903406170.
Zheng, D., S. Ng, and M. Kumaraswamy. 2005. “Applying Pareto ranking and Niche formation to genetic algorithm-based multiobjective time–cost optimization.” J. Constr. Eng. Manage. 131 (1): 81–91. https://doi.org/10.1061/(ASCE)0733-9364(2005)131:1(81).
Zitzler, E., K. Deb, and L. Thiele. 2000. “Comparison of multiobjective evolutionary algorithms: Empirical results.” Evol. Comput. 8 (2): 173–195.
Zitzler, E., and L. Thiele. 1998. “Multiobjective optimization using evolutionary algorithms—A comparative case study.” In Proc., Int. Conf. on Parallel Problem Solving from Nature, 292–301. Berlin: Springer.
Information & Authors
Information
Published In
Journal of Construction Engineering and Management
Volume 146 • Issue 8 • August 2020
Copyright
©2020 American Society of Civil Engineers.
History
Received: Jul 19, 2019
Accepted: Feb 3, 2020
Published online: May 18, 2020
Published in print: Aug 1, 2020
Discussion open until: Oct 18, 2020
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.