Constraint-based construction project scheduling

This research explored the potential benefit of a more flexible and extensive representation of constraints in the construction project scheduling problem. The scheduling problem was formulated and solved as a Constraint Satisfaction Problem (CSP) and a subsequent Constraint Relaxation Problem (CRP). The research demonstrated a mechanism for considering an appropriate level of constraint representation to solve the practical construction project scheduling problem. In particular, the experiment demonstrated that this representation can be used as a synthesis tool for a decision support system to solve the problem. A backtracking scheme was used to solve the CSP problem. In this scheduling formulation, only the conventional constraints--resource capacity, activity precedence, activity duration, and project due date--were represented for testing and comparison purposes. Resource and temporal labeling were used to perform consistency checks, and a variable ordering heuristic was used to schedule with resource constraints represented by the equivalent disjunctive arc model. Experience based on scheduling 110 projects, showed the CSP formulation is a feasible but expensive method to solve the scheduling problem. The variable ordering heuristic performed relatively well compared to other heuristics. As discovered by many other researchers, the backtracking scheme based on chronological backtracking scheme performed poorly; it often failed to backtrack to the source of failure. A relaxation scheme based on the network flow algorithm was used to solve the CRP problem. The procedure uses the initial schedule generated by any conventional scheduling heuristic as a basis, including the CSP. A set of critical sequence activities constrained by capacity and precedence constraints is identified from the current schedule. Then, using an appropriate level of constraint representation, together with knowledge on their behavior and relationship, the constraints are relaxed relative to the activities on the critical sequence. The output of the procedure is a set of feasible values for the constraint for each value of project duration, while minimizing additional project cost due to direct cost. The procedure will also determine resource capacity adjustments that need to be made when the scheduling objective cannot be met with the existing resource capacity. The procedure was tested on six projects to determine the cost utility curve for the projects.