Critical Sequence Crashing Heuristic for Resource-Constrained Discrete Time–Cost Trade-Off Problem
Publication: Journal of Construction Engineering and Management
Volume 142, Issue 3
Abstract
Despite the importance of project deadlines and resource constraints in construction scheduling, very little success has been achieved in solving the resource-constrained discrete time–cost trade-off problem (RCDTCTP), especially for large-scale projects. In this paper a new heuristic method is designed and developed to achieve fast and high-quality solutions for the large-scale RCDTCTP. The proposed method is based on the novel principles to enable effective exploration of the search space through adequate selection of the activities to be crashed for a resource constrained schedule, by only crashing the activities with zero float in a resource constrained-schedule, which form the critical sequence. The computational experiment results reveal that the new critical sequence crashing heuristic outperforms the state-of-the-art methods, both in terms of the solution quality concerning project cost and computation time. Solutions with a deviation of 0.25% from the best known solutions are achieved within seconds for the first time, for a large-scale project including up to 2,000 activities. The main contribution of the new heuristic to practitioners and researchers is that it provides a fast and effective method for optimal scheduling of real-life-size construction projects with project deadlines and resource constraints.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
The authors gratefully acknowledge the financial support provided by the Scientific and Technological Research Council of Turkey (TÜBİTAK) under Grant #213M253.
References
Afshar, A., Ziaraty, A., Kaveh, A., and Sharifi, F. (2009). “Nondominated archiving multicolony ant algorithm in time-cost trade-off optimization.” J. Constr. Eng. Manage., 668–674.
Ahn, T., and Erenguc, S. S. (1998). “The resource constrained project scheduling problem with multiple crashable modes: A heuristic procedure.” Eur. J. Oper. Res., 107(2), 250–259.
Bettemir, O., and Sonmez, R. (2014). “Hybrid genetic algorithm with simulated annealing for resource-constrained project scheduling.” J. Manage. Eng., 04014082.
Bettemir, Ö. H. (2009). “Optimization of time–cost–resource trade-off problems in project scheduling using meta-heuristic algorithms.” Ph.D. thesis, Middle East Technical Univ., Ankara, Turkey.
Blazewicz, J., Lenstra, J., and Rinnooy Kan, A. H. G. (1983). “Scheduling subject to resource constraints: classification and complexity.” Discrete Appl. Math., 5(1), 11–24.
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(2), 268–281.
Chan, W. T., Chua, D. K. H., and Kannan, G. (1996). “Construction resource scheduling with genetic algorithms.” J. Constr. Eng. Manage., 125–132.
Chen, P. H., and Shahandashti, S. M. (2009). “Hybrid of genetic algorithm and simulated annealing for multiple project scheduling with multiple resource constraints.” Autom. Constr., 18(4), 434–443.
Chen, P.-H., and Weng, H. (2009). “A two-phase GA model for resource-constrained project scheduling.” Autom. Constr., 18(4), 485–498.
Chen, R. M. (2011). “Particle swarm optimization with justification and designed mechanisms for resource-constrained project scheduling problem.” Exp. Syst. Appl., 38(6), 7102–7111.
Chua, D. K. H., Chan, W. T., and Govtndan, K. (1997). “A time-cost trade-off model with resource consideration using genetic algorithm.” Civ. Eng. Syst., 14(4), 291–311.
De, P., Dunne, E. J., Ghosh, J. B., and Wells, C. E. (1997). “Complexity of the discrete time-cost tradeoff problem for project networks.” Oper. Res., 45(2), 302–306.
Deblaere, F., Demeulemeester, E., and Herroelen, W. (2011). “RESCON: Educational project scheduling software.” Comput. Appl. Eng. Educ., 19(2), 327–336.
Elbeltagi, E., Hegazy, T., and Grierson, D. (2007). “A modified shuffled frog-leaping optimization algorithm: applications to project management.” Struct. Infrastruct. Eng., 3(1), 53–60.
Fallah-Mehdipour, E., Bozorg Haddad, O., Rezapour Tabari, M. M., and Mariño, M. A. (2012). “Extraction of decision alternatives in construction management projects: Application and adaptation of NSGA-II and MOPSO.” Exp. Syst. Appl., 39(3), 2794–2803.
Feng, C. W., Liu, L., and Burns, S. A. (1997). “Using genetic algorithms to solve construction time-cost trade-off problems.” J. Comput. Civ. Eng., 184–189.
Goldratt, E. (1997). Critical chain, North River Press, Great Barrington, MA.
Hartmann, S. (1998). “A competitive genetic algorithm for resource constrained project scheduling.” Naval Res. Logist., 45(7), 733–750.
Hegazy, T. (1999). “Optimization of resource allocation and leveling using genetic algorithms.” J. Constr. Eng. Manage., 167–175.
Hegazy, T., and Menesi, W. (2012). “Heuristic method for satisfying both deadlines and resource constraints.” J. Constr. Eng. Manage., 688–696.
Hegazy, T., Shabeeb, A., El-Beltagi, E., and Cheema, T. (2000). “Algorithm for scheduling with multi-skilled constrained resources.” J. Constr. Eng. Manage., 414–421.
Hekimoglu, O. (2007). “Comparison of the resource allocation capabilities of project management software packages in resource constrained project scheduling problems.” M.S. thesis, Middle East Technical Univ., Ankara, Turkey.
Herroelen, W., and Leus, R. (2005). “Identification and illumination of popular misconception about project scheduling and time buffering in a resource-constrained environment.” J. Oper. Res. Soc., 56(1), 102–109.
Kandil, A., and El-Rayes, K. (2006). “Parallel genetic algorithms for optimizing resource utilization in large-scale construction projects.” J. Constr. Eng. Manage., 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, NJ, 347–365.
Kim, J. L., and Ellis, R. D. (2008). “Permutation-based elitist genetic algorithm for optimization of large-sized resource-constrained project scheduling.” J. Constr. Eng. Manage., 904–913.
Kim, J. L., and Ellis, R. D. (2010). “Comparing schedule generation schemes in resource-constrained project scheduling using elitist genetic algorithm.” J. Constr. Eng. Manage., 160–169.
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. S., and Yang, C. H. (1999). “A genetic-algorithm-based resource-constrained construction scheduling system.” Constr. Manage. Econ., 17(6), 767–776.
Li, K., and Willis, R. (1992). “An iterative scheduling technique for resource-constrained project Scheduling.” Eur. J. Oper. Res., 56(3), 370–379.
Liberatore, M., Pollack-Johnson, B., and Smith, C. (2001). “Project management in construction: Software use and research directions.” J. Constr. Eng. Manage., 101–107.
Lova, A., and Tormos, P. (2002). “Combining random sampling and backward–forward heuristics for resource-constrained multi-project scheduling.” Proc., 8th Int. Workshop on Project Management and Scheduling, EURO Working Group, 244–248.
Lu, M., and Lam, H-C. (2009). “Transform schemes applied on nonfinish-to-start logical relationships in project network diagrams.” J. Constr. Eng. Manage., 863–873.
Lu, M., Lam, H-C., and Dai, F. (2008). “Resource-constrained critical path analysis based on discrete event simulation and particle swarm optimization.” Autom. Constr., 17(6), 670–681.
Lu, M., and Li, H. (2003). “Resource-activity critical-path method for construction planning.” J. Constr. Eng. Manage., 412–420.
Mellentien, C., and Trautmann, N. (2001). “Resource allocation with project management software.” OR Spektrum, 23(3), 383–394.
Menesi, W., Golzarpoor, B., and Hegazy, T. (2013). “Fast and near-optimum schedule optimization for large-scale projects.” J. Constr. Eng. Manage., 1117–1124.
Ng, S., and Zhang, Y. (2008). “Optimizing construction time and cost using ant colony optimization approach.” J. Constr. Eng. Manage., 721–728.
Özdamar, L., and Ulusoy, G. (1994). “A local constraint based analysis approach to project scheduling under general resource constraints.” Eur. J. Oper. Res., 79(2), 287–298.
Siemens, N. (1971). “A simple CPM time-cost tradeoff algorithm.” Manage. Sci., 17(6), B–354–B–363.
Sonmez, R., and Bettemir, Ö. H. (2012). “A hybrid genetic algorithm for the discrete time-cost trade-off problem.” Exp. Syst. Appl., 39(13), 11428–11434.
Sonmez, R., and Uysal, F. (2014). “Backward-forward hybrid genetic algorithm for resource-constrained multiproject scheduling problem.” J. Comput. Civ. Eng., 04014072.
Tormos, P., and Lova, A. (2001). “A competitive heuristic solution tech-nique for resource-constrained project scheduling.” Ann. Oper. Res., 102(1/4), 65–81.
Valls, V., Ballestin, F., and Quintanilla, M. S. (2005). “Justification and RCPSP: A technique that pays.” Eur. J. Oper. Res., 165(2), 375–386.
Vanhoucke, M., and Debels, D. (2007). “The discrete time/cost trade-off problem: Extensions and heuristic procedures.” J. Scheduling, 10(4–5), 311–326.
Wang, Q., and Qi, J. (2009). “Improved particle swarm optimization for RCP scheduling problem.” 6th Int. Symp. on Neural Networks, Springer, Berlin, 49–57.
Wiest, J. D. (1964). “Some properties of schedules for large projects with limited resources.” Oper. Res., 12(3), 395–418.
Wuliang, P., and Chengen, W. (2009). “A multi-mode resource-constrained discrete time-cost tradeoff problem and its genetic algorithm based solution” Int. J. Project Manage., 27(6), 600–609.
Xiong, Y., and Kuang, Y. (2008). “Applying an ant colony optimization algorithm-based multiobjective approach for time-cost trade-off.” J. Constr. Eng. Manage., 153–156.
Yang, I. (2007). “Using elitist particle swarm optimization to facilitate bicriterion time-cost trade-off analysis.” J. Constr. Eng. Manage., 498–505.
Zheng, D., Ng, S., and Kumaraswamy, M. (2005). “Applying Pareto ranking and niche formation to genetic algorithm-based multiobjective time-cost optimization.” J. Constr. Eng. Manage., 81–91.
Information & Authors
Information
Published In
Journal of Construction Engineering and Management
Volume 142 • Issue 3 • March 2016
Copyright
© 2015 American Society of Civil Engineers.
History
Received: Mar 11, 2015
Accepted: Aug 26, 2015
Published online: Oct 23, 2015
Published in print: Mar 1, 2016
Discussion open until: Mar 23, 2016
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.