Construction Scheduling Using the Constraint Satisfaction Problem Method
Publication: Journal of Construction Engineering and Management
Volume 139, Issue 4
Abstract
Construction projects are subject to numerous constraints of various types, including contractual due dates, resource limitations, and safety, financial, and managerial constraints. Most scheduling methods based on the critical path method (CPM) require that all project constraints be comprehensively defined and arranged into a single logical network for developing a project schedule. In real-life situations, however, there could be more than one option of execution, conditions, and/or precautions that may influence the logic of the project network and its outputs. CPM-based methods have been proven inadequate for scheduling in this kind of situation. This paper views construction scheduling as a constraint satisfaction problem (CSP), which is defined by a set of scheduling variables and a set of constraints. A CSP-based scheduling method has been developed to provide a framework for systematic constraint modeling and effective schedule generation. An illustrative real-life case example is presented to demonstrate the applicability of the proposed method. The results indicate that the present method is effective and efficient due to its expressive constraint representations and its ability to provide alternative schedules for multilogic project networks. This resembles more the nature of construction projects in which various types of constraints both conditional and unconditional are involved and many scheduling options can be derived. Comparing with the traditional CPM-based methods, the proposed method has the potential to transform the way construction schedules are generated and managed.
Get full access to this article
View all available purchase options and get full access to this article.
References
Allen, J. F. (1983). “Maintaining knowledge about temporal intervals.” Commun. ACM, 26(11), 832–843.
Barták, R. (2003). “Constraint-based scheduling: An introduction for newcomers.” Intelligent manufacturing systems, Kadar B., Monostori, L. M., and Morel, G., eds., IFAC Publications, Elsevier Science, 69–74.
Chan, W. T., and Hu, H. (2002). “Constraint programming approach to precast production scheduling.” J. Constr. Eng. Manage., 128(6), 513–521.
Choo, H. J., Tommelein, I. D., Ballard, G., and Zabelle, T. R. (1999). “WorkPlan: Constraint-based database for work package scheduling.” J. Constr. Eng. Manage., 125(3), 151–160.
Chua, D. K. H., and Yeoh, K. W. (2011). “PDM++: Planning framework from a construction requirements perspective.” J. Constr. Eng. Manage., 137(4), 266–274.
El-Bibany, H. (1997). “Parametric constraint management in planning and scheduling: Computational basis.” J. Constr. Eng. Manage., 123(3), 348–353.
Freuder, E. C. (1989). “Partial constraint satisfaction.” Proc., 11th Int. Joint Conf. on Artificial Intelligence, N. S., Sridharan, ed., Morgan Kaufmann Publishers, San Mateo, CA, 278–283.
Hegazy, T. (1999). “Optimization of resource allocation and leveling using genetic algorithms.” J. Constr. Eng. Manage., 125(3), 167–175.
Jaafari, A. (1984). “Criticism of CPM for project planning analysis.” J. Constr. Eng. Manage., 110(2), 222–233.
Johnston, M. D. (1990). “SPIKE: AI scheduling for NASA’s Hubble Space Telescope.” Proc., 6th Conf. on Artificial Intelligence Applications, The Association of Universities for Research in Astronomy for the National Aeronautics and Space Administration, Santa Barbara, CA, 184–190.
Kim, J. L. (2009). “Improved genetic algorithm for resource-constrained scheduling of large projects.” Can. J. Civ. Eng., 36(6), 1016–1027.
Kumar, V. (1992). “Algorithm for constraint satisfaction problems: A survey.” AI Mag., 13(1), 32–44.
Le Pape, C. (1994). “Implementation of resource constraints in ILOG SCHEDULE: A library for the development of constraint-based scheduling systems.” Intell. Syst. Eng., 3(2), 55–66.
Lorterapong, P., and Rattanadamrongagsorn, T. (2001). “Viewing construction scheduling as a constraint satisfaction problem.” Proc., 6th Int. Conf. on Application of Artificial Intelligence to Civil and Structural Engineering, Civil-Comp Press, Stirlingshire, U.K, 1–11.
Maheswari, J. U., Varghese, K., and Sridharan, T. (2006). “Application of dependency structure matrix for activity sequencing in concurrent engineering projects.” J. Constr. Eng. Manage., 132(5), 482–490.
Pultar, M. (1990). “Progress-based construction scheduling.” J. Constr. Eng. Manage., 116(4), 670–688.
Sacks, R., and Partouche, R. (2010). “Empire State building project: Archetype of ‘mass construction’.” J. Constr. Eng. Manage., 136(6), 702–710.
Sakka, Z. I., and El-Sayegh, S. M. (2007). “Float consumption impact on cost and schedule in the construction industry.” J. Constr. Eng. Manage., 133(2), 124–130.
Seppanen, O., Ballard, G., and Personen, S. (2010). “The combination of last-planner system and location-base management system.” Lean Constr. J., 43–54.
Sriprasert, E., and Dawood, N. (2002). “Requirements identification for 4D constraint-based construction planning and control system.” Proc., Int. Council for Research and Innovation in Building and Construction CIB W78 Conf. 2002, Aarhus School of Architecture, Denmark, 1–8.
Touahria, M., and Benmessahel, B. (2011). “An improved combinatorial particle swarm optimization algorithm to database vertical partition.” J. Emerg. Trends Comput. Inf. Sci., 2(3), 130–135.
Tsang, E. (1993). Foundations of constraint satisfaction, 1st Ed., Academic Press, London, U.K.
Ussavadilokrit, M., and Lorterapong, P. (2009). “The significance of constraints in high-rise building construction project planning.” Res. Dev. J., 20(1), 69–78.
Weng, H. J., and Chen, P. H. (2005). “Smart GA-based cost-scheduling model for resource-constrained projects.” Proc., 22nd Int. Symp. on Automation and Robotics in Construction, International Association for Automation and Robotics in Construction (IAARC), Ferrara, Italy, 1–9.
Zhao, Z. Y., Lv, Q. L., Zuo, J., and Zillante, G. (2010). “Prediction system for change management in construction project.” J. Constr. Eng. Manage., 136(6), 659–669.
Information & Authors
Information
Published In
Copyright
© 2013 American Society of Civil Engineers.
History
Received: Dec 13, 2011
Accepted: Jul 17, 2012
Published online: Jul 26, 2012
Published in print: Apr 1, 2013
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.