Computational & Technology Resources
an online resource for computational,
engineering & technology publications
Civil-Comp Proceedings
ISSN 1759-3433
CCP: 74
Edited by: B.H.V. Topping and B. Kumar
Paper 8

Viewing Construction Scheduling as a Constraint Satisfaction Problem

P. Lorterapong and T. Rattanadamrongagsorn

Construction Engineering and Management Program, Department of Civil Engineering, King Mongkut's University of Technology, Thonburi, Bangkok, Thailand

Full Bibliographic Reference for this paper
P. Lorterapong, T. Rattanadamrongagsorn, "Viewing Construction Scheduling as a Constraint Satisfaction Problem", in B.H.V. Topping, B. Kumar, (Editors), "Proceedings of the Sixth International Conference on the Application of Artificial Intelligence to Civil and Structural Engineering", Civil-Comp Press, Stirlingshire, UK, Paper 8, 2001. doi:10.4203/ccp.74.8
Keywords: scheduling, constraint satisfaction, resource allocation, temporal reasoning.

Problem Statement

Construction scheduling has been regarded as one of the most important and challenging tasks faced by project managers. This is due to the fact that most construction projects are normally performed out-door, exposing to a variety of unexpected events e.g. late material arrival times, adversarial weather, different site conditions, fluctuating labor productivity, etc.). These events can have an impact on activity execution time and cost. Like other domains, construction scheduling is also complex due to the number and variety of project objectives and constraints. Project objectives may include, for example, to maximize resource utilization, to avoid project delay, to minimize project overdraft, etc. These objectives are potentially conflicting each other, and, in many cases, cannot be precisely defined. These objectives are potentially conflicting each other, and in many cases, cannot be precisely defined. Project constraints can generally be classified into two groups (i.e. hard and soft)

In such a dynamic and complicated environment, any schedule must in practice be subject to frequent revision to ensure it is in line with changing project status. The problem of updating schedules in the most effective way when the constraints are changed or invalidated is one that is very challenging receiving increasing attention amongst both researchers and practitioners. In this study, construction scheduling is viewed as a decision making process under constraints of different importance, often using imprecise data, where compromises between project objectives are allowed.

Previous Scheduling Techniques

In the past, scheduling is classified into two types: deterministic and non- deterministic. Deterministic methods include such technique as the Critical Path Method (CPM). In CPM, the activity duration is predetermined and fixed throughout the scheduling process. CPM has continuously been criticized for its lack of ability to cope with uncertainty inherent in most construction projects. Non-deterministic methods such as Program Evaluation and Review Technique (PERT) and Monte Carlo simulation have therefore been introduced to overcome the limitation with the above–mentioned deterministic method. These techniques employ primarily the probability concept to model uncertainty associated with activity durations. There are, however, relatively few reports of the implementations of such techniques in construction practice. This is due, perhaps, to the demand for a well-established database system recommended for generating input data, as well as some statistical background required on the scheduler's part to maintain and process these data. A more recent scheduling method utilizing fuzzy sets based method attempts to model uncertainty that are inherent in their estimates such as "approximately 5 days", "between 3 and 4 days".

Proposed Constraint Satisfaction System

The about scheduling methods have provided partial solutions to the scheduling problem. As mentioned earlier, realistic solutions are those that adhere to the given project constraints while maximizing project goals. In this study, construction is therefore viewed as a constraint satisfaction problem. In general, it is the process of an incremental formation of a solution (i.e. schedule) that satisfies the constraints in a given project circumstances. A progressive assignment of start and finish times to project activities is iteratively performed until an acceptable schedule is obtained.

The purpose of this paper is to introduce a conceptual framework for constraint satisfaction problems and to describe the war in which construction scheduling problems can be modeled using the constraint satisfaction paradigm. The CSP features bear close resemblance to those of the scheduling problems found in most construction projects. According to computer science, the model, constraint representation and solution methods are briefly explained for idealizing the proposed scheduling system. A simplified numerical example is used to demonstrate practicality of the proposed framework. The CSP main thrusts are two folds: to enable expressive constraint representations and to provide effective, yet, flexible means to generate practical solutions taking into consideration the given constraints.

David, E.W., "Project Scheduling Under Resource Constraints- Historical Review and Categorization procedures", AIIE Transactions, 5(4), 297-312, 1973.
Fox, M.S. Smith, S.F. "ISIS A Knowledge-Based System for Factory Scheduling", Expert Systems, 1(1), 25-49, 1984. doi:10.1111/j.1468-0394.1984.tb00424.x
Smith, S.F. "A Constraint-Based Framework for Reactive Management of Factory Schedules", in Proceedings of the First International Conference on Expert Systems and the Leading Edge in Production Planning and Control, Charleston, South Carolina, 1987.
Kumar, V. "Algorithms for Constraint Satisfaction Problems: A Survey", AI Magazine, 13(1), 1992.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description