Optimization-based scheduling of construction projects with generalized precedence relationships: A real-life case study

Document Type : Article

Authors

1 Department of Civil Engineering, Atilim University, Ankara, 06830, Turkey

2 Graduate School of Natural and Applied Sciences, Atilim University, Ankara 06830, Turkey

Abstract

Concomitant reduction of cost and duration is recognized as one of the main aspects of construction planning. Expedition of project schedule naturally incurs extra costs due to implementation of more productive and/or high-price construction techniques. Meanwhile, a reduction in time is usually plausible only down to a certain limit, below which renders expeditions either technically or financially unviable. Thus, striking a reasonable balance between project cost and duration remains a desirable yet challenging task for which there has been a myriad of advancements and literature. Despite the many studies associated with this problem – referred to as time-cost trade-off problem (TCTP) – it is observed that only a few exercise TCTPs with generalized logical relationships. This observation holds despite the fact that generalized precedence relationships are imperative to introduce parallelism and to secure a realistic overlap among the activities. In this regard, a Simulated Annealing-based Genetic Algorithm as proposed herein, is specifically designed to provide the capability of exerting TCTPs with properly overlapped activities. Efficiency of this algorithm is tested over a wide range of problems and its performance is validated over a large-scale real-case construction project. Results of the hybridized GA indicate fast and robust convergence to high-quality solutions.

Keywords

Main Subjects

References

References:
1. Kaveh, A., Rajabi, F., and Mirvalad, S. "Manyobjective optimization for construction project scheduling using non-dominated sorting differential evolution algorithm based on reference points", Scientia Iranica, 28(6), pp. 3112-3128 (2021). https://doi.org/10.24200/sci.2021.58952.5988.
2. Kelley, J.E. and Walker, M.R. "Critical-path planning and scheduling", Proceedings of Eastern Joint Computer Conference, Association for Computing Machinery, New York, NY, USA, pp. 160-173 (1959). https://doi.org/10.1145/1460299.1460318.
3. Fulkerson, D.R. "A network  flow computation for project cost curves", Management Science, INFORMS, 7(2), pp. 167-178 (1961). https://doi.org/10.1287/mnsc.7.2.167.
4. Siemens, N. "A simple CPM time-cost tradeoff algorithm", Management Science, INFORMS, 17(6), pp. B354-B363 (1971). https://doi.org/10.1287/mnsc.17.6.B354.
5. Goyal, S.K. "A note on a simple CPM time-cost trade-off algorithm", Management Science, INFORMS, 21(6), pp. 718-722 (1975). https://doi.org/10.1287/mnsc.21.6.718.
6. Falk, J.E. and Horowitz, J.L. "Critical path problems with concave cost-time curves", Management Science, INFORMS, 19(4), pp. 446-455 (1972). https://doi.org/10.1287/mnsc.19.4.446.
7. Foldes, S. and Soumis, F. "PERT and crashing revisited - mathematical generalizations", European Journal of Operational Research, 64(2), pp. 286-294 (1993). https://doi.org/10.1016/0377-2217(93)90183-N.
8. Skutella, M. "Approximation algorithms for the discrete time-cost tradeoff problem", Mathematics of Operations Research, 23(4), pp. 909-929 (1998). https://doi.org/10.1287/moor.23.4.909.
9. Zheng, D.X.M., Ng, S.T., and Kumaraswamy, M.M. "Applying a genetic algorithm-based multiobjective approach for time-cost optimization", Journal of Construction Engineering and Management, 130(2), pp. 168-176 (2004). https://doi.org/10.1061/(ASCE)0733-9364(2004) 130:2(168).
10. Feng, C.W., Liu, L., and Burns, S.A. "Using genetic algorithms to solve construction time-cost trade-off problems", Journal of Computing in Civil Engineering, 11(3), pp. 184-189 (1997). https://doi.org/10.1061/ (ASCE)0887-3801 (1997)11:3(184).
11. Sonmez, R. and Bettemir, O.H. "A hybrid genetic algorithm for the discrete time- cost trade-off problem", Expert Systems with Applications, 39(13), pp. 11428-11434 (2012). https://doi.org/10.1016/j.eswa.2012.04.019.
12. Aminbakhsh, S. and Sonmez, R. "Pareto front particle swarm optimizer for discrete timecost trade-off problem", Journal of Computing in Civil Engineering, 31(1), 04016040 (2017). https://doi.org/10.1061/(ASCE)CP.1943- 5487.0000606.
13. Agdas, D., Warne, D.J., Osio-Norgaard, J., and Masters, F.J. "Utility of genetic algorithms for solving large-scale construction time-cost trade-off problems", Journal of Computing in Civil Engineering, 32(1), 04017072 (2018). https://doi.org/10.1061/(ASCE)CP.1943- 5487.0000718.
14. Chen, L., Zhang, J., and Peng, W. "Research on the hierarchical discrete time-cost trade-off problem for program", Journal of Construction Engineering and Management, 148(7), 04022039 (2022). https://doi.org/10.1061/(ASCE)CO.1943-
7862.0002293.
15. Kelley, J.E. "Critical-path planning and scheduling - mathematical basis", Operations Research, 9(3), pp. 296-320 (1961). https://doi.org/10.1287/opre.9.3.296.
16. Butcher, W.S. "Dynamic programming for project cost-time curves", Journal of the Construction Division, ASCE, 93, pp. 59-74 (1967). https://doi.org/10.1061/JCCEAZ.0000191.
17. Liu, L., Burns, S. A., and Feng, C. W. "Construction time-cost trade-off analysis using LP/IP hybrid method", Journal of Construction Engineering and Management, 121(4), pp. 446-454 (1995). https://doi.org/10.1061/(ASCE)0733-9364(1995) 121:4(446).
18. Demeulemeester, E. L., De Reyck, B., Foubert, B., Herroelen, W. S., and Vanhoucke, M. "New computational results on the discrete time/cost trade-off problem in project networks", Journal of the Operational Research Society, 49(11), pp. 1153-1163 (1998). https://doi.org/10.1057/palgrave.jors.2600634.
19. Nasiri, S., and Lu, M. "Streamlined project timecost tradeoff optimization methodology: algorithm, automation, and application", Automation in Construction, 133, 104002 (2022). https://doi.org/10.1016/j.autcon.2021.104002.
20. Son, J., Hong, T., and Lee, S. "A mixed (continuous + discrete) time-cost trade-off model considering four different relationships with lag time", KSCE Journal of Civil Engineering, 17(2), pp. 281-291 (2013). https://doi.org/10.1007/s12205-013-1506-3.
21. Klansek, U., and Psunder, M. "MINLP optimization model for the nonlinear discrete time-cost trade-off problem", Advances in Engineering Software, 48, pp. 6-16 (2012). https://doi.org/10.1016/j.advengsoft.2012.01.006.
22. Van Eynde, R. and Vanhoucke, M. "A reduction tree approach for the discrete time/cost trade-off problem", Computers and Operations Research, 143, 105750 (2022). https://doi.org/10.1016/j.cor.2022.105750.
23. Fondahl, J.M. "A non-computer approach to the critical path method for the construction industry", Technical Report, 9, Construction Institute, Department of Civil Engineering, Stanford University, California (1961). https://hdl.handle.net/2027/mdp.39015000453970.
24. Moselhi, O. "Schedule compression using the direct stiffness method", Canadian Journal of Civil Engineering, 20(1), pp. 65-72 (1993). https://doi.org/10.1139/l93-007.
25. Bettemir, O.H. and Birgonul, M.T. "Network analysis algorithm for the solution of discrete time-cost trade-off problem", KSCE Journal of Civil Engineering, 21(2), pp. 1047-1058 (2017). https://doi.org/10.1007/s12205-016-1615-x.
26. Sonmez, R., Aminbakhsh, S., and Atan, T. "Activity uncrashing heuristic with noncritical activity rescheduling method for the discrete timecost trade-off problem", Journal of Construction Engineering and Management, 146(8), 04020084 (2020). https://doi.org/10.1061/(ASCE)CO.1943- 7862.0001870.
27. Xiong, Y. and Kuang, Y.P. "Applying an ant colony optimization algorithm-based multiobjective approach for time-cost trade-off", Journal of Construction Engineering and Management, 134(2), pp. 153-156 (2008). https://doi.org/10.1061/(ASCE)0733- 9364(2008)134:2(153).
28. Yang, I.T. "Performing complex project crashing analysis with aid of particle swarm optimizationalgorithm", International Journal of Project Management, 25(6), pp. 637-646 (2007). https://doi.org/10.1016/j.ijproman.2006.11.001.
29. Liu, D., Li, H., Wang, H., et al. "Discrete symbiotic organisms search method for solving large-scale timecost trade-off problem in construction scheduling", Expert Systems With Applications, 148, 113230 (2020). https://doi.org/10.1016/j.eswa.2020.113230.
30. Klansek, U. and Psunder, M. "Cost optimal project scheduling", Organizacija, 41(4), pp. 153-158 (2008). https://doi.org/10.2478/v10051-008-0017-3.
31. Sakellaropoulos, S. and Chassiakos, A.P. "Project time-cost analysis under generalised precedence relations", Advances in Engineering Software, 35(10), pp. 715-724 (2004). https://doi.org/10.1016/j.advengsoft.2004.03.017.
32. Cajzek, R. and Klansek, U. "Cost optimization of project schedules under constrained resources and alternative production processes by mixed-integer nonlinear programming", Engineering, Construction and Architectural Management, 26(10), pp. 2474-2508 (2019). https://doi.org/10.1108/ECAM-01-2019-0013.
33. Tavana, M., Abtahi, A.R., and Khalili-damghani, K. "A new multi-objective multi-mode model for solving preemptive time-cost-quality trade-off project scheduling problems", Expert Systems with Applications, 41(4), pp. 1830-1846 (2013). https://doi.org/10.1016/j.eswa.2013.08.081.
34. Holland, J.H., Adaptation in Natural and Artiffcial Systems: An Introductory Analysis with Applications to Biology, Control, and Artiffcial Intelligence, Cambridge, MA, USA: University of Michigan Press (1975). https://doi.org/10.7551/mitpress/1090.001.0001.
35. Namazian, A., Haji Yakhchali, S., and Rabbani, M. "Integrated bi-objective project selection and scheduling using bayesian networks: a risk- based approach", Scientia Iranica, 26(6), pp. 3695-3711 (2019). https://doi.org/10.24200/sci.2019.21387.
36. Akhbari, M. "Integration of multi-mode resourceconstrained project scheduling under bonus-penalty policies with material ordering under quantity discount scheme for minimizing project cost", Scientia Iranica, 29(1), pp. 427-446 (2022). https://doi.org/10.24200/sci.2020.54286.3680.
37. Erden, C., Demir, H.I., and Canpolat, O. "A modiffed integer and categorical pso algorithm for solving integrated process planning, dynamic scheduling and due date assignment problem", Scientia Iranica, 30(2), pp. 738-756 (2023). https://doi.org/10.24200/sci.2021.55250.4130.
38. Esmailnezhad, B. and Saidi-Mehrabad, M. "A twostage stochastic supply chain scheduling problem with production in cellular manufacturing environment: a case study", Scientia Iranica, 30(4), pp. 1399-1422 (2023). https://doi.org/10.24200/sci.2021.53506.3277.
39. Albayrak, G. and Ozdemir, I. "A state of art review on metaheuristic methods in time-cost trade-off problems", International Journal of Structural and Civil Engineering Research, 6(1), pp. 30-34 (2017). https://doi.org/10.18178/ijscer.6.1.30-34.
40. El-Rayes, K. and Kandil, A. "Time-cost-quality trade-off analysis for highway construction", Journal of Construction Engineering and Management, 131(4), pp. 477-486 (2005). https://doi.org/10.1061/(ASCE)0733- 9364(2005)131:4(477).
41. Azaron, A., Perkgoz, C., and Sakawa, M. "A genetic algorithm approach for the time-cost trade-off in PERT networks", Applied Mathematics and Computation, 168(2), pp. 1317-1339 (2005). https://doi.org/10.1016/j.amc.2004.10.021.
42. Srinivas, M. and Patnaik, L.M. "Adaptive probabilities of crossover and mutation in genetic algorithms", IEEE Transactions on Systems, Man, and Cybernetics, 24(4), pp. 656-667 (1994). https://doi.org/10.1109/21.286385.
43. Bettemir, O.H. "Optimization of time-cost-resource trade-off problems in project scheduling using metaheuristic algorithms", Ph.D. Thesis, Middle East Technical University, Ankara, Turkey (2009). https://hdl.handle.net/11511/18989.
44. Adler, D. "Genetic algorithms and simulated annealing: a marriage proposal", International Conference on Neural Networks, IEEE, San Francisco, CA, USA https://doi.org/10.1109/ICNN.1993.298712.
45. Reeves, C.R. "A genetic algorithm for  flowshop sequencing", Computers and Operations Research, 22(1), pp. 5-13 (1995). https://doi.org/10.1016/0305-0548(93)E0014-K.
46. Tumuluru, J.S. and McCulloch, R.C. "A new hybrid genetic algorithm for optimizing the single and multivariate objective functions", ASABE Annual International Meeting, ASABE, New Orleans Marriott, New Orleans, LA, USA, 152188606 (2015). https://doi.org/10.13031/aim.20152188606.
47. Wang, L. and Zheng, D.Z. "An effective hybrid optimization strategy for job-shop scheduling problems", Computers and Operations Research, 28(6), pp. 585- 596 (2001). https://doi.org/10.1016/S0305-0548(99)00137-9.
48. Hegazy, T. "Optimization of construction time-cost trade-off analysis using genetic algorithms", Canadian Journal of Civil Engineering, 26(6), pp. 685-697 (1999). https://doi.org/10.1139/l99-031.
49. Goncalves, J.F., Mendes, J.J.M., and Resende, M.G.C. "A genetic algorithm for the resource constrained multi-project scheduling problem", European Journal of Operational Research, 189(3), pp. 1171-1190 (2008). https://doi.org/10.1016/j.ejor.2006.06.074.
50. Elbeltagi, E., Hegazy, T., and Grierson, D. "Comparison among ffve evolutionary-based optimization algorithms", Advanced Engineering Informatics, 19(1), pp. 43-53 (2005). https://doi.org/10.1016/j.aei.2005.01.004.
51. Chassiakos, A.P. and Sakellaropoulos, S.P. "Timecost optimization of construction projects with generalized activity constraints", Journal of Construction Engineering and Management, 131(10), pp. 1115-1124 (2005). https://doi.org/10.1061/(ASCE) 0733-9364(2005)131:10(1115).
52. Ahmed, A. "Genetic-algorithm-based optimization approach for time-cost trade-off problem with generalized precedence relationships", M.Sc. Thesis, Atilim University, Ankara, Turkey (2020). https://hdl.handle.net/20.500.14411/4708.
53. Hegazy, T., and Abuwarda, Z. "Schedule  flexibility and compression horizon: new key parameters for effective corrective actions", Canadian Society for Civil Engineering Annual Conference, CSCE2019 (2019). https://legacy.csce.ca/elf/apps/CONFERENCE VIEWER/conferences/2019/pdfs/PaperPDF version 145 0301042149.pdf.
Scientia Iranica
Volume 31, Issue 19
Transactions on Civil Engineering (A)
November and December 2024
Pages 1809-1824

Files

History

  • Receive Date: 01 December 2021
  • Revise Date: 13 January 2023
  • Accept Date: 29 August 2023

Share

How to cite

Statistics