No CrossRef data available.
Distributed coordination of project schedule changes using agent-based compensatory negotiation methodology
Published online by Cambridge University Press: 07 November 2003
Abstract
In the construction industry, projects are becoming increasingly large and complex, necessitating multiple subcontractors. Traditional centralized coordination techniques used by general contractors become insufficient as subcontractors perform most work and provide their own resources. When subcontractors cannot provide enough resources, they hinder their own performance, that of other subcontractors, and ultimately the entire project. Thus, projects need a new distributed coordination approach wherein all of the concerned subcontractors can respond to changes and reschedule a project dynamically. This paper presents a new distributed coordination framework for project schedule changes (DCPSC) that is based on an agent-based negotiation approach wherein software agents evaluate the impact of changes, simulate decisions, and give advice on behalf of the human subcontractors. A case example demonstrates the significance of the DCPSC. It compares two centralized coordination methodologies used in current practice to the DCPSC framework. We demonstrate that our DCPSC framework always finds a solution that is better than or equal to any of two centralized coordination methodologies.
Information
- Type
- Research Article
- Information
- Copyright
- 2003 Cambridge University Press
1. INTRODUCTION
Despite the ubiquity of change in large, complex construction projects, current approaches to change coordination are mostly reactive and therefore lead to less than optimal solutions. However, if changes in a given schedule were coordinated prior to execution, then better solutions could be found. Previous researchers have explored the various causes of schedule changes in construction projects. Discrepancies between the needed resources for activities and the resources available to subcontractors are one major cause of change (O'Brien et al., 1995). The resource discrepancies occur when the timing of the activities is not well matched with the available resources, that is, when subcontractors have different perspectives of scheduling. The resource focus in our work is the local resource that subcontractors provide, not the global resources that general contractors (GCs) provide.
Soon after the GC awards subcontracts according to the master project schedule, subcontractors often want to change the master schedule because resource discrepancies cause additional costs through either overutilizing currently available resources or importing new resources (O'Brien & Fischer, 2000). Therefore, the subcontractors may try to change the project schedule in order to accommodate their wishes. Changes are likely to cause schedule conflicts among subcontractors because any move affects the activities of other subcontractors in tightly coupled construction project schedules. A schedule conflict occurs when one subcontractor tries to reschedule his activity to the same time interval that another subcontractor has already scheduled the succeeding activity. Because all activities have precedence relationships, related activities cannot be overlapped.
In most cases, these schedule conflicts cannot be easily resolved by simply delaying the succeeding activities because such delays would affect the resource profiles of succeeding subcontractors, which would cause additional costs for them. Delays could also extend the project completion beyond the deadline. Therefore, there is a need for a methodology to handle subcontractors' resource-driven schedule changes.
In current practice, the coordination of subcontractors' resource-driven schedule changes in complex projects is difficult for GCs, because they generally do not know the details of each subcontractor's resource constraints. Furthermore, GCs have little incentive to accommodate the subcontractors' wishes. This dilemma in current project schedule coordination stems from a mismatch between traditional centralized coordination techniques in the industry and current construction practices employing more and more subcontracting. Subcontractors are competitive by nature and cannot be coordinated simply by orders from GCs, a method that was traditionally used by the latter, when they performed most of the work themselves.
1.1. Assumptions of the distributed coordination framework for product schedule changes (DCPSC)
Before going further, we would like to state three assumptions made for DCPSC. First, our research addressed the coordination of subcontractors' resource constraints after the GC has made the master schedule. Therefore, we assume that project schedules have fixed work logic and precedence relations among activities.
Second, we also assume that subcontractors keep their resource information private and want to enhance their resource utilization by rescheduling their activities without violating the work logic. Because their activities are interdependent with other subcontractors' activities, subcontractors have to consult with other subcontractors when rescheduling their activities. In most construction projects schedule conflicts are common and must be negotiated among subcontractors.
Third, subcontractors work collaboratively to achieve a common project goal, but they are different organizations. Therefore, they cannot be regarded as “benevolent” in accommodating changes, that is, they are unlikely to help without compensation. Rather, they are “competitive,” which means they will not let a subcontractor affect their work without compensation. If reasonable monetary compensation is provided, then they are likely to help.
1.2. Case example
We introduce a case example that we will use throughout this work to illustrate our research. Consider the example network in Figure 1. The results of the conventional critical path method (CPM) calculations and the resource requirement for each activity appear in Figure 1. Activities A, E, and G are assigned to Sub-α, activities B and D are assigned to Sub-β, and activities C and F are assigned to Sub-δ. For simplicity, assume each subcontractor uses the same resource for its activities.
An example network schedule.
Assume that the subcontractors predicted at the time of bidding that they would have sufficient resources available for the activity to support the initial schedule. The resource histogram in Figure 2 indicates the initial resource requirements, based on the above schedule, for completion of the activities. The resource requirements for noncritical activities, which are not as constrained as the critical activities, are set at their latest start–finish schedules. Therefore, the schedule will be feasible.
A resource requirement histogram.
However, as the actual execution dates approach, the resource availability has become tighter under changing market conditions. Two reasons could explain why the resource availability would change: the subcontractors experience a shortage of workers, breakdowns of major equipment, shortage of major materials, and so forth (Clough & Sears, 1991); and the subcontractors might want to move the committed resources from the project to more lucrative projects (O'Brien & Fischer, 2000). For whatever reasons, assume that each subcontractor now has revised available resource profiles for each activity, as shown in Figure 3. Bold resource histograms A, B, and D differ from the required resource diagrams. Note that the resource availability is shown for explanation purposes only, even though such private information is usually kept within subcontractors and not made available to the GC.
An available resource histogram.
This resource histogram implies that some subcontractors' schedules differ from their original ones. For instance, Sub-α wants to finish Activity A on day 4 because Sub-α does not have enough resources to finish on day 3. Sub-β wants to finish Activity B on day 8 because Sub-β does not have enough resources to finish on day 7.
Note that the mere collection of subcontractors' preferred schedules is not guaranteed to produce a feasible schedule because the subcontractors' resource availability is independent, unlike their schedules. Therefore, some activities might violate the network logic in the schedule. For instance, on day 4, Activity B starts before Activity A has finished.
1.3. Two current centralized coordination methodologies
As a basis for evaluating the effectiveness of DCPSC, we introduce two centralized coordination methodologies used in current practice. Under the centralized coordination methodologies below, the GC is obligated to coordinate the subcontractors. It is reasonable to assume that the information needed for coordination, such as the subcontractors' preferred schedules and resource information, is not available to the GC but is kept within subcontractors (Choo & Tommelein, 2000). Assume that communication and coordination are kept among subcontractors and the GC under the current contractual GC-subcontractor relationships, not between subcontractors. We examine two methodologies of centralized coordination (tight and loose) that we regard as the representation of existing practice.
1.3.1. Tight “iron-fist” centralized coordination (TCC)
Under TCC, the objective is to finish the project on time and the subcontractors are instructed to finish their activities before the latest finish date of each activity. Under TCC, the GC can coordinate the subcontractors to finish the project on time. However, some subcontractors might experience cost overruns when their available resources differ from their resource requirements. For the GC, the cost overruns could be regarded as the subcontractors' fault for poor management of their resources.
Under TCC, Sub-α has to expedite Activity A to finish on time in spite of its different resource availability. Assume that Sub-α will choose overtime to accelerate Activity A while paying extra costs. Other activities will have the same initial schedule. Sub-β also has to expedite Activity B to finish on time. Assume that Sub-β will choose overtime to accelerate Activity B while paying extra costs. Activity D will keep the same initial schedule. Note that Activity D will have a fluctuating resource profile of 8, 10, and 2 resources in 3 consecutive days in order to match with the available resources of Sub-β (see Fig. 3). Sub-δ can keep its preferred schedule because Sub-δ can finish its activities before the deadlines. The revised resource histogram following TCC is in Figure 4. The diagonal hatching indicates overtime.
The revised resource histogram after TCC.
In summary, TCC costs more for some subcontractors if they have different resource availability than their initial resource requirements. This also lowers the resource utilization, even though TCC would guarantee that they finish on time. Note that the GC has no consideration of subcontractors' resource utilization in TCC.
1.3.2. Loose “laissez-faire” centralized coordination (LCC)
Under LCC, the objective is to match the resources available to produce a workable schedule. The role of the centralized coordinator is minimal in keeping the original schedule (Tommelein & Ballard, 1997). Under LCC, activities are finished when enough resources are provided, as in resource-driven scheduling (El-Rayes & Moselhi, 1996; Choo et al., 1999). Without knowing subcontractors' resource availability, the GC instructs them to start their activities when the preceding activities have been finished and when enough resources are available; that is, the job is ready for the subcontractor and the work can proceed unimpeded (Clough & Sears, 1991). LCC usually delays the project, and some subcontractors might experience cost overruns due to delays of preceding activities, as well as their resource deviations. The GC also incurs liquidated damages due to the project delay. Disputes among subcontractors would follow if the causes of delays are not clearly established and the cost overruns are not reimbursed properly.
Under LCC, Sub-α can delay the finish of Activity A, but Activity B will be delayed by Activity A because Activity B is also allowed to delay its finish. Sub-δ can keep the schedule of Activity C. Then, Sub-α, Sub-β, and Sub-δ must delay the start dates of Activities D, E, F, and G while paying extra costs for importing resources. Next, Sub-α is forced to delay the start date of Activity G. As a result, the project is delayed by 2 days and the GC needs to pay liquidated damages for this delay. Figure 5 shows the revised resource histogram after LCC. The diagonal hatching indicates required overtime.
The revised resource histogram after LCC.
In summary, LCC costs more for some subcontractors when they have to import new resources because of delays in preceding activities, as well as their resource deviations. The project has missed its completion date, and the GC has to pay liquidated damages. Options to expedite the activities instead of paying liquidated damages, like time-cost trade-off analysis (Fondahl, 1961, 1991; Antill & Woodhead, 1990), are limited because these require information, such as the cost slope for each activity, that usually is not available to the GC.
1.4. Challenges for DCPSC
From the shortcomings of two current coordination methodologies, we set practical challenges for DCPSC to set up the criteria against which we will measure the goodness of a new methodology for DCPSC.
In the example, TCC is equitable in that subcontractors have to pay for their errors in planning, but LCC forces subcontractors into a worse situation by simply delaying affected activities. Some subcontractors benefit and others do not, regardless of fault. The first criterion is whether a new distributed coordination methodology can enable subcontractors to compensate the affected subcontractors for disadvantageous agreements.
In the example, neither TCC nor LCC considered alternatives because of the tightly coupled network of related activities. The second criterion is whether a new methodology can allow subcontractors to identify schedule conflicts, consider alternatives, and resolve schedule conflicts in a tightly coupled network of related activities.
In the example, neither TCC nor LCC had schedule conflicts because the GC maintained work logic during coordination. However, if subcontractors know only their schedules and relationships to other subcontractors' activities, maintaining work logic becomes a big task. The third criterion is whether a new methodology maintains work logic and ensures convergence of distributed coordination.
These challenges have been ignored in past research on the coordination of project planning and scheduling because of its dominant orientation to centralized approaches and the lack of a formal distributed coordination methodology, as we discuss in the next section.
2. POINTS OF DEPARTURE
This section reviews previous work on coordination of project planning and scheduling and on distributed coordination in the field of cooperative distributed problem solving and multiagent systems research.
2.1. Previous coordination of project planning and scheduling
Numerous research papers have recognized a major problem in the CPM network approach, which assumes unlimited resource supplies, and have provided frameworks to address various limited-resource issues in construction planning and scheduling. However, few current frameworks address the difficulties of gathering information in the coordination of subcontractors' resource-driven schedule changes. The existing centralized frameworks are insufficient because the information needed for centralized resource-based scheduling, such as the resource constraints, is usually kept private by subcontractors (Choo & Tommelein, 2000) and is usually not available for the centralized frameworks, as stated in one of the assumptions of DCPSC.
When only some subcontractors benefit from the coordination of their resource-driven schedule changes and when GCs are not willing to coordinate the work of subcontractors (Tommelein & Ballard, 1997), subcontractors need to work together with minimal information sharing. Subcontractors need a new distributed coordination methodology that allows the evaluation of the impact of their changes and the making of appropriate decisions.
Current distributed frameworks in construction and in the broader project management and artificial intelligence research literature have inadequately addressed challenges for DCPSC. They have not provided a monetary conflict-resolution mechanism, which is their main shortcoming, even though some of them have provided various conflict-resolution mechanisms for interactions between participants (Koo, 1987; Jin & Levitt, 1993; Khedro et al., 1993; Gomes et al., 1994). ProcessLink (Petrie et al., 1998) identifies dependencies among activities and participants but does not specify a conflict-resolution mechanism.
As this review of previous literature demonstrates, the distributed coordination with monetary conflict-resolution mechanism is a new problem domain that current research does not explore. The problem we are trying to solve is rescheduling activities through distributed coordination when subcontractors have available resources that differ from the needed resources. They need a distributed coordination framework that includes a monetary conflict-resolution methodology, wherein a project can be rescheduled dynamically by all of the concerned subcontractors while maintaining schedule logic and keeping their information private.
2.2. Previous distributed agent-based coordination
Many cooperative distributed problem solving (CDPS) and multiagent systems (MAS) papers have proposed various distributed coordination methodologies, but we found that the research has shortcomings in applications for DCPSC.
First, we found that none of the papers mentioned an explicit method for the transfer of utility units (“money”) to compensate for disadvantageous agreements. Allowing the transfer of utility is very important for DCPSC. By allowing the transfer of utility units to compensate for the external costs, the group of subcontractors prefers the changed project schedule to the initial schedule. Consequently, a new project schedule is “Pareto superior” (Feldman, 1980, p. 140) to the initial schedule.
Our monetary conflict-resolution methodology is more efficient than using the incentives or reward mechanisms found in some market-based systems (Malone et al., 1988; Wellman, 1993; Shoham & Tanaka, 1997). The Clarke tax-voting mechanism (Ephrati & Rosenschein, 1996) collects taxes centrally but provides no way to distribute the collected taxes. The unified negotiation protocol (Rosenschein & Zlotkin, 1998) does not provide an explicit monetary conflict-resolution mechanism, so it uses an implicit method of working together after flipping a coin.
Our compensatory negotiation methodology differs from payment via contracts used in other MAS research (Sandholm, 1993; Sen & Durfee, 1996), in which any profit-seeking bid from agents might prevent a system from reaching a better solution. Compromise via negotiation (Sycara, 1989) provides a way of transferring utilities between agents through a central mediator, but it is implicit and not for compensation of disadvantageous agreements. Distributed constraint satisfaction (Yokoo et al., 1992, 1998) and distributed search (Durfee & Montgomery, 1991; Sycara et al., 1991; Decker & Lesser, 1992) find a satisfactory solution that requires no disadvantageous agreements for any agent.
Another finding is that most CDPS and MAS applications employ pairwise negotiation or multilateral (auction) protocols, which are based on the Contract Net Protocol (Smith, 1980) and would be unsuitable for coordinating the tightly coupled project schedules. Pairwise negotiation or multilateral (auction) protocols cannot capture external effects of their agreements on other agents because agents do not know the consequences of their decision until getting the responses from the succeeding agents. Rather, they implicitly assume that there are no externalities.
The third finding is that most CDPS and MAS applications do not guarantee the convergence of distributed computation because protocols that cannot ensure consistency among agents' knowledge cannot ensure convergence. Some distributed search frameworks use unique ID (Yokoo et al., 1992), pecking order (Durfee & Montgomery, 1991), or heuristic order (Sycara et al., 1991); but none of them use the CPM (Fondahl, 1961) for coordination of message passing.
3. DCPSC DESCRIPTION
The DCPSC consists of three components that are similar to Oberlender's (1993) project definition: project schedule, resource constraints, and extra costs. Project schedule refers to the schedule that represents the logical sequencing and timing of the work to be performed. Usually, a GC prepares the project schedule and assigns parts of the schedule to specialty contractors, that is, subcontractors. Nonetheless, the separately assigned project schedules interrelate with each other because they are a part of the whole project schedule. Resource constraints represent the differences between the needed resources and subcontractors' available resources. Therefore, the subcontractors want to change the project schedule in their favor in a way that enhances their resource utilization. Resolving resource constraints without violating the work logic is the task of subcontractors. Extra cost refers to the subcontractors' worst extra costs determined by their resource constraints.
When there are resource constraints that conflict with the project schedule, the resource constraints generate schedule changes and determine the extra cost information. Subcontractors will try to lower the extra costs through distributed coordination among subcontractors and accept the schedule changes that lower the extra costs associated with the schedule changes, which will enhance the project schedule.
In order for subcontractors to consider their own activities and enhance global outcomes, we developed the distributed coordination framework for project schedule changes, based on the social welfare function (Varian, 1978). The social welfare function is “some sort of function that aggregates individual utility functions to come up with some sort of social utility” (Varian, 1978, p. 153). Varian also states, “The social welfare function is increasing in each of its arguments—if you increase an agent's utility without decreasing anybody else's utility then society is made better off” (Varian, 1978, p. 153).
These explanations of the social welfare function exactly match with the current problem of DCPSC among self-interested subcontractors. In the context of this paper, the social welfare function is a function that aggregates individual utility functions of subcontractors to come up with the social utility of the project; and if you increase a subcontractor's utility without decreasing anybody else's utility, then the project is made better off.
3.1. Formalization of DCPSC
We formalize the distributed coordination framework of project schedule changes as follows. A set of subcontractors A = {A1,…, An} must produce a collective decision over a set of activities {a1,…, am}. Each subcontractor needs to know a utility for its alternatives of its own activity, by taking into consideration the extra costs to others of its course of action and weighing it against its own extra costs. We define a social choice function, E, such that E represents the group choice, as follows:
where E and Cost(i, j) is the sum of the subcontractors' extra costs for all m activities of n subcontractors and the jth activity, which belongs to the ith subcontractor.
Unlike the ideals of social choice function, which is the summation of individual utility, our social choice function is the summation of individual subcontractor's extra costs, which is indeed the negative utility for subcontractors and social welfare. In our social choice function, the utility for subcontractors and social welfare increases when the extra costs decrease.
To increase individual utility and social welfare together, therefore, we set the objective of distributed coordination of project schedule changes so as to lower E, that is, the sum of subcontractors' costs associated with their resource constraints, subject to the precedence relationship among project activities:
subject to
where Finishx is the finish date of activity x, Starty is the start date of activity y, and Sx is the set of activities that must succeed activity x.
One distinguishing feature of the problem definition is that the problem will be solved through collaboration of all the concerned subcontractors in a distributed manner. Another notable feature is that every subcontractor only considers its own activities, but it will also enhance global outcomes. The third feature is that distributed coordination maintains the logical sequencing of the work to be performed, even though it might change the timing of the work. These features of the DCPSC overcome shortcomings of the current centralized coordination approaches.
3.2. Agent-based negotiation approach
The previous section reveals three important issues of distributed coordination for project schedule changes: distributed coordination by competitive subcontractors, socially rational decision making, and maintaining the logical sequence of the work. In this section, we discuss the adoption of the agent-based negotiation approach, which is needed to overcome the difficulties stemming from these issues.
3.2.1. Agent
Because of the huge number of interactions among subcontractors throughout the distributed coordination for project schedule change, each subcontractor should have a software agent, which is a program capable of communicating with other software agents using an Agent Communication Language (Khedro et al., 1993). The agent exchanges messages with other agents to evaluate changes and advises its human subcontractor to make a decision.
For this research, we adopted the so-called typed-message agent (TMA, Petrie, 1996). Agent communities define TMA as those agents that must exchange messages to accomplish a task. For agent characteristics, TMA stresses peer–peer communications and message passing based on shared, typed protocols and semantics to which the agent communities have committed, along with other important features for DCPSC (Jeon, 2000):
- performing a task that would normally be performed by a person;
- using peer–peer communication, which differs from the traditional client/server model;
- communicating with a common agent language, such as Knowledge Query and Manipulation Language (Finin et al., 1994);
- obeying agent negotiation protocols, the semantics of which the agent community shares; and
- maintaining state information, and acting on it, which distinguishes agents from other object-oriented software programs.
3.2.2. Agent-based negotiation
There are many definitions of agent-based negotiation in the CDPS and MAS research communities. In the context of this paper, we define agent-based negotiation as the process of resolving conflicts among affected agents by increasing knowledge about others' intentions through the structured exchange of relevant information. The objective of agent-based negotiation is to improve mutual agreements for conflicting agents so that the results of negotiations do not make any conflicting agent worse off than before the negotiations.
3.2.3. Advantages of agent-based negotiation approach
TMAs provide several advantages over recent object-oriented approaches and other agent systems. The key idea of TMAs is their ability to model distributed coordination among subcontractors throughout the conflict-resolution negotiation processes. TMAs can model the subcontractors as software agents performing a task on behalf of human subcontractors, while modeling the interactions among subcontractors as agent negotiation protocols based on agent communication language.
With the ability to model distributed coordination, the agent-based negotiation approach based on TMA is a powerful tool to overcome the difficulties by the distributed approach. Software agents can communicate rapidly with each other over the Internet, which allows subcontractors to coordinate project schedule changes in a distributed manner by using the agent-based compensatory negotiation methodology to be summarized in the next section.
4. AGENT-BASED COMPENSATORY NEGOTIATION (ABCN) METHODOLOGY
The ABCN methodology consists of three main aspects: the compensatory negotiation strategy, based on utility to the agents; the multilinked negotiation protocols by which agents interact with other agents; and message-handling mechanisms for agents to evaluate alternatives and simulate the decision making. Kim and Paulson (2003) show details of the ABCN methodology.
4.1. Compensatory negotiation strategy based on utility
Each agent calculates utility of timing to evaluate the impacts of its schedule changes and to compensate other agents for disadvantageous agreements through a utility transfer scheme.
4.1.1. Utility of timing
In our research, we adopted the definition of utility by Rosenschein and Zlotkin (1998, p. 361) to quantify utility of timing:
The utility of a deal for an agent is defined as the cost of its original work minus the cost of its new work given the deal. The difference is how much it has gained from the deal.
In the context of this paper, we represent utility of timing of as a real-valued number (money), which describes the difference between the cost of the initial schedule and the costs of alternatives for the activity as units of money based on resource utilization. A reasonable assumption about resource utilization is that any discrepancy between the resource requirements and the available resources causes a subcontractor to incur extra costs of either overutilizing current resources, for example, paying overtime or importing new resources. These extra costs motivate the search for a better solution. The utility units are common for all agents, and agents can transfer their utility units to other agents for compensation.
Each agent calculates the utility for each activity k using the following function:
where ACk is the extra acceleration cost for accelerating the kth activity and DCx is the extra delay cost for delaying the succeeding activity x. Note that the agent, which has activity k, knows ACk but does not know the summation of DCx until getting DCs from the succeeding activities.
Agents can calculate the ACs and DCs by using given rates, such as overtime rates, extra rates, or import rates. However, the assumptions vary by the parameters for characteristics of resources, such as units, fixed/variable, timing, and upper limits. Therefore, instead of calculating AC- and DC-based the parameters, which cannot cover all the different situations that should be considered, the “clients” (subcontractors) provide their agents with schedule-change options. Agents can calculate the utility of timing for their activities from the given schedule-change options. We represent a schedule-change option as a tuple of the form:
The startDate is the possible start date of the activity. The endDate is the possible finish date of the activity. The extraCost is the extra cost associated with the timing of the activity. An activity has one or more schedule-change options.
4.1.2. Utility transfer for compensatory negotiation
The key concept of the compensatory negotiation strategy is to transfer utility (money) to compensate agents for “playing along” in a situation that, to them, is otherwise locally suboptimal. After getting DC through negotiation, if AC is more than DC, that is, there is positive utility, the agent decides to make an extension, and transfers the DC portion of the utility to other agents for compensation of disadvantageous agreements.
4.2. Multilinked negotiation protocols
Negotiation protocols govern the interaction among agents by constraining the way the agents interact. In this research, agents need negotiation protocols to get DCs from succeeding agents and transfer utility to other agents for compensation of disadvantages agreements. Compensatory negotiation starts with a nominal project schedule and has an agent propose to compensate other agents for costs imposed on the latter for the former's change of the plan. This is simple when agents can reschedule their activities without affecting others or the counterpart agent is one, which is the case of pairwise negotiation. In a more complicated case, an agent needs to negotiate with another agent, which in turn needs to negotiate with a third, and so on, until the last agent. We call this “multilinked” negotiations.
The negotiation protocols provide the performatives, which are shared primitive message types for agents to use in negotiation (Finin et al., 1994), and the conversation sequence, which decides whom to talk with and how to initiate and maintain the communication. The next two sections summarize the performatives and conversation sequence for the multilinked negotiation protocols.
4.2.1. Multilinked negotiation performatives
Our multilinked negotiation performatives fall into three classes: human interaction, negotiation control, and negotiation. The human interaction performatives allow a human subcontractor to provide necessary data to its agent and an agent to inform its subcontractor of the current status of negotiation. The negotiation performatives facilitate the actual compensatory negotiation processes. The negotiation control performatives manage the states of negotiation processes. The human interaction performatives include input, ready, inform, and final. The negotiation performatives include ask-cost, reply-cost, accept, reject, confirm, renege, accept-all, reject-all, confirm-all, and renege-all. The negotiation control performatives include ready, hand-over, and done.
4.2.2. Conversation sequence of multilinked negotiation
The conversation sequence decides with whom to talk and how to initiate and maintain the communication. It is important to note that the project activity precedence relationships govern the agent message exchange. Since we developed the multilinked negotiation protocols for DCPSC, agents should exchange messages according to the project schedule. We can guarantee that our protocols will converge, which means they will not enter infinite loops of refinement, because agents use static activity precedence relationships in the project schedule for message passing among agents.
4.3. Message-handling mechanisms
The agent reacts according to the message it gets. Therefore, it should have the functionality of handling messages for each type of multilinked message protocol. When the agent handles a message, it should also make a decision accordingly. Message-handling mechanisms use the CPM schedule for coordination of message passing among agents so that agents exploit the sequence logic in the project schedule for coordinating message passing and to ensure successful completion of distributed computation.
4.4. Summary of ABCN methodology
To summarize, agents can accomplish four crucial procedures: calculating utility with a utility function from the predefined schedule-change options; exploring feasible alternatives by collaboration with other agents using multilinked negotiation protocols; evaluating the impact of their alternatives; and making appropriate decisions based on the evaluation. When the decisions affect other agents' activities, agents transfer utility to compensate other agents that are forced to make disadvantageous agreements; as a result, agents cooperatively enhance the overall project schedule in a distributed manner.
5. EVALUATION
This section demonstrates the effectiveness of the ABCN methodology for DCPSC through comparison tests. It compares two centralized coordination methodologies used in current practice to the DCPSC-based ABCN methodology in terms of extra costs and project duration.
5.1. Schedule change options
From the available resource histograms in the case example, assume that schedule change options are predefined in the format of (startDate(day) endDate(day) extraCost($)), as shown in Table 1. Note that option 1 includes initially available options, which are feasible because the start date of an activity is later than the end dates of the preceding activities. There is also an option that includes liquidated damages ($4,000) for a 2-day project delay, which the GC needs to pay. Keep in mind that the predefined schedule-change options are prepared by each subcontractor and are initially kept private.
Predefined schedule-change options before coordination
5.2. ABCN methodology
Under the ABCN, Sub-α evaluates the AC ($480) for Activity A, which is the difference between the option of A1 (1 3 480) and the option of A2 (1 4 0), and the DC ($5,760), which is the cost response from the succeeding activities of Activity A (Kim & Paulson, 2003, shows detailed steps). Then Sub-α decides to expedite Activity A to finish on time as the option of A1 (1 3 480) because DC is much more than AC. Note that the cost overrun will not be reimbursed because Sub-α has to decide first according to its position in the network schedule. However, if AC was more than DC, Sub-α could keep its new preferred schedule while reimbursing the costs for succeeding activities.
Then Sub-β and Sub-δ, which have activities succeeding Activity A, evaluate the options of their activities, Activity B and Activity C. Sub-β can use its new preferred schedule as the option of B2 (4 8 0) because the AC ($1,920) for expediting Activity B is more than the DC ($1,024) for expediting Activity E and delaying Activity F. Sub-β will compensate the costs to Sub-α and Sub-δ, which are $640 for Activity E and $384 for Activity F, respectively. Note that the initial options are changed due to the compensation. That is, B2′ (4 8 1024) from B2 (4 8 0), E2′ (9 10 0) from E2 (9 10 680), and F2′ (9 10 0) from F2 (9 10 384). Sub-δ will keep Activity C the same as the initial schedule as the option of C1 (5 7 0) because its schedule is good.
Next, Sub-α, Sub-β, and Sub-δ evaluate the options of their Activities E, D, and F. Due to changed options of Activity E and Activity F, all subcontractors will keep the changed schedule as E2′ (9 10 0), D2′ (9 10 0), and F2′ (9 10 0) because their schedules are good. Finally, Sub-α evaluates the options of Activity G and decides to keep the schedule as F1 (11 12 0). The chosen schedule-change options after ABCN are marked with checkmarks in Table 2.
Selected schedule-change options after ABCN
Figure 6 shows a revised resource histogram after ABCN. The diagonal hatching indicates the overtime.
The revised resource histogram after ABCN.
In the ABCN above, subcontractors make agreements only if the agreements can lower the sum of subcontractors' costs while compensating others for disadvantageous agreements. In summary, ABCN enhances the project network schedule that has schedule conflicts, while lowering the sum of subcontractors' costs associated with their resource constraints by rescheduling the project subject to the precedence relationship among project activities in cases of changes in subcontractors' resource availabilities. Next, we evaluate the effectiveness of the ABCN by showing whether it can find a solution that is better than or equal to results from current practice.
5.3. TCC methodology
Under TCC, Sub-α has to choose the option of A1 (1 3 480). Other activities remain the same as the options of E1 (8 10 0) and G1 (11 12 0). Sub-β also has to choose the option of B1 (4 7 1920). Activity D will remain the same as option D1 (8 9 0). Sub-δ can keep its preferred schedule with the options of C1 (5 7 0) and F1 (8 9 0). Chosen schedule change options after TCC are marked with checkmarks in Table 3.
Selected schedule-change options after TCC
In summary, TCC costs more ($480 and $1,920) for some subcontractors (Sub-α and Sub-β, respectively) when they have different resource availability than their initial resource requirements (Activity A and Activity B). TCC lowers the resource utilization for Sub-α and Sub-β, even though TCC would guarantee to finish on time (12 days).
5.4. LCC methodology
Under LCC, Sub-α can choose the option of A2 (1 4 0), but Activity B has to choose the option of B5 (5 9 0) because of the option A2. Sub-δ can keep the option of C1 (5 7 0). Then, Sub-α, Sub-β, and Sub-δ must select their options for their other activities: E3 (10 12 0) for Activity E, D3 (10 11 960) for Activity D, and F3 (10 11 768) for Activity F. Next, Sub-α is forced to select the option of G2 (13 14 4512). Note the option includes liquidated damages for a 2-day project delay, which the GC needs to pay. The chosen schedule change options after LCC are marked with checkmarks in Table 4.
Selected schedule-change options after LCC
In summary, LCC costs more ($512, $960, and $768) for all subcontractors (Sub-α, Sub-β, and Sub-δ, respectively) when they have to employ new resources (Activity D, Activity F, and Activity G) because of delays of the preceding activities (Activity A and Activity B). The project missed its completion date (2-day delay) and the central coordinator has to pay liquidated damages of $4,000 in this case.
5.5. Comparison of the three coordination methodologies
Table 5 summarizes the comparison among three different coordination methodologies in terms of cost and duration.
Summary of resuls
ABCN can find a solution that is better than or equal to any of the results from the centralized coordination methodologies. In these examples, it is better. However, it does not eliminate all extra costs for some subcontractors in cases where some subcontractors have to expedite their activities by working overtime to avoid large costs for delaying or expediting succeeding activities. Note that, under ABCN, the project can be flexible on finish time if any subcontractor is willing to pay the project delay penalty in return for a delay.
Appendix A shows the generalization of these evaluation results with mathematical proofs. A few limitations of DCPSC also became more evident in this phase of evaluation. For example:
- DCPSC is only applicable to “balanced” schedules. A balanced schedule is a schedule in which paths between two nodes have the same number of nodes if there are multiple paths. Otherwise, DCPSC falls into the state of “deadlocks.” We can modify “unbalanced” schedules by adding zero-duration dummy nodes.
- Every schedule should have one start node and one finish node. Otherwise, DCPSC falls into the state of deadlocks. We can easily modify schedules without these by adding zero-duration start and end nodes.
Inserting dummy activities can minimize these limitations, but identifying these situations before DCPSC involves additional overhead. We need to check every node and relationship to identify unbalanced paths in the schedule. Like forward propagation, the first node is zero and adds one (+1) to its relationships to the succeeding activities. When two or more relationships come to one node, the node checks if the numbers are the same. If the numbers are the same, the schedule is balanced.
6. CONCLUSION
We have shown a DCPSC based on an ABCN methodology. The new framework emphasizes the distributed nature of coordinating project schedule changes and the autonomy of subcontractors while providing new effective methods for coordinated exchange of information and negotiation protocols and a novel negotiation methodology for resolving schedule conflicts. This in itself is a significant departure from prior and recent research, particularly in the area of construction project planning and scheduling, which has traditionally attempted to centralize the coordination process to enhance a project schedule.
We conclude that the DCPSC framework enhances the project network schedule (in terms of lowering the sum of subcontractors' costs associated with their resource constraints) by rescheduling the project subject to the precedence relationship among project activities in cases of changes in subcontractors' resource availabilities. Thus, this research would help construction subcontractors to increase efficiency in their resource use in a distributed manner, which leads to successful completion of whole projects.
Our DCPSC framework has some present limitations, some of which are shared with centralized coordination methodologies. One of the limitations is that, because of the limited capability of its agents, DCPSC does not allow changes of work logic in a project schedule; instead, it only finds a better schedule with the fixed work logic. Another is that DCPSC does not provide direct relationships between resource constraints and schedule-change options, which is attributable to too many parameters to consider.
Future research must seek to overcome the limitations of this research. A first research area is to investigate direct relationships between resource constraints and schedule-change options. Direct relationships between resource constraints and schedule-change options would take into account the investigation and parameterization of many factors that would relate resource constraints to schedule-change options, such as units, fixed/variable, timing, and upper limits of resources.
A second research area is to develop a more general distributed coordination methodology for allowing changes in work logic in project schedules. Such a methodology would take into account a different representation of activities, such as input and output requirements for each activity. The input/output requirements that allow it to be dynamic is an advance over the traditional CPM model that only includes fixed precedence relationships between activities.
A third research area is to extend the framework to allow distributed coordination/negotiation for variables other than time. Researchers can extend this work to help subcontractors resolve conflicts among competitive actors in other areas, such as mechanical, electrical, and plumbing coordination and workspace management. These involve spatial and temporal constraints between the activities performed by different subcontractors and would require conceptual extensions to time constraints in this research.
This research can improve the competitive performance of construction projects to improve schedules, enhance resource utilization, and support cooperative relationships among subcontractors. GCs as well as subcontractors get benefits from employing the research results. Industry can apply this research to many important areas of project management, such as Internet-based project management, distributed control of large-scale engineering systems, and management of complex distributed systems.
ACKNOWLEDGMENTS
The Center for Integrated Facility Engineering of Stanford University supported the research. We would like to thank Professor Victor R. Lesser of the University of Massachusetts, Computer and Information Science Department, Professor Yan Jin of the University of Southern California, Aerospace and Mechanical Engineering Department, and Professor Weng Tat Chan of the National University of Singapore, Civil Engineering Department, for their input into this research.
APPENDIX A: GENERALIZATION OF EVALUATION RESULTS
A.1. Definitions of total cost overruns of TCC, LCC, and DCPSC
This section shows the definitions of total cost overruns of TCC (CTCC), LCC (CLCC), and DCPSC (CDCPSC).
A.1.1. Definition of total cost overruns of TCC
A naive formulation of the total cost overruns (CTCC) after TCC is as follows:
where ACi is the cost for expediting the ith activity, over and above the original cost.
However, examining the actual process of getting ACi on any project plan produces a more complex formulation as below:
where k is the order of Wave, which is a set of activities to be considered at the same time, that is, Wave1 is the first (only one) activity and Wavei is {succeeding activities of Wave(i−1)} for i ≥ 2; and ACik is the cost for expediting the ith activity, over and above the original cost within the kth Wave.
Considering ∀k, ACik = ACi, because there is only one AC for each activity, the following formula generalize the total cost overruns (CTCC) after TCC:
A.1.2. Definition of total cost overruns of LCC
A naive formulation of the total cost overruns (CLCC) after LCC is as follows:
where LCCi = CBi is the cost for delaying the ith activity, over and above the original cost. This includes the cost of unscheduled resources and liquidated damages.
However, examining the actual process of getting CBi on any project plan produces a more complex formulation as below:
where LCCk is the cost for delaying all the activities with the kth wave; LCCik is the cost for delaying the ith activity with the the kth wave; CBik is the cost for delaying the ith activity, over and above the original cost within the kth wave; CDik is the cost for delaying succeeding activities of the ith activity, over and above the original cost within the kth Wave.
Because CBi is the cost for delaying the ith activity, which accumulates all the CBik, [sum ]kWave = CBik. Therefore, the following formula generalizes CLCC:
A.1.3. Definition of total cost overruns of DCPSC
The following formula generalizes the total cost overruns (CDCPSC) after DCPSC:
where DCPSCk is the minimum cost between the cost for expediting and the costs for delaying activities with the kth wave; DCPSCik is the minimum cost between the cost for expediting and the costs for delaying activities from the ith activity with the kth wave; and DCik is the minimum cost between the cost for expediting and the costs for delaying succeeding activities of the ith activity, over and above the original cost within the kth Wave.
A.2. Comparisons of total cost overruns of TCC, LCC, and DCPSC
Theorem 1. CDCPSC ≤ CTCC. Because min(ACik, (CBik + DCik)) ≤ ACik by the definition of min,
Theorem 2. CDCPSC ≤ CLCC.█
Lemma 1. CDCPSC ≤ CLCC when the activities follow a linear sequence, which means the nth activity follows the (n − 1)th activity and so on, as shown in Figure A1. Because Wavek is the kth activity, then i = k. Thus, we can simplify CLCC as follows:
The activity precedence network.
With the same procedure, we can simplify CDCPSC as follows:
Now we compare CDCPSC with CLCC. Basis: k = n: because ∀k, DCPSCn+1k = 0 and because there is no succeeding activity, DCPSCn+1n = 0.
When k = n − 1: because DCPSCn+1n−1 = 0,
When k = k: given ∀i, l ≤ i ≤ n,
we prove that DCPSCl−1k ≤ LCCl−1k by induction on the activity number within the same wave k.
The conclusion we draw is that DCPSCk is less than or equal to LCCk for any activity number for k ≤ i ≤ n. Therefore, DCPSCk = DCPSCkk ≤ LCCkk = LCCk.
Then,
Therefore, CDCPSC ≤ CLCC when the activities follow a linear sequence.
Lemma 2. If CDCPSC ≤ CLCC for each string of linear activities, then this is so for the xth activity where they fork also.
Because CDCPSC ≤ CLCC for each string of linear activities, then this is so for the activity where they also fork because the summation of CDCPSC is less than or equal to the summation of CLCC for the xth activity where they fork.█
Lemmas 1 and 2 show that CDCPSC ≤ CLCC within any project plan where the activities follow a linear sequence and the activity where they also fork.
Theorems 1 and 2 show that DCPSC always finds a solution that is better than or equal to that of any of two centralized coordination methodologies (TCC and LCC) because DCPSC selects the minimum value among the cost of expediting the activity (AC) and the cost for delaying the activity (CB).
References
REFERENCES
Antill, J.M. &
Woodhead, R.W.
(1990).
Critical Path Methods in Construction Practice.
New York:
Wiley.
Choo, H.J. &
Tommelein, I.D.
(2000).
Interactive coordination of distributed work plan.
Proc. Sixth Construction Congress, pp.
11–20.
Orlando, FL:
ASCE.
Choo, H.J.,
Tommelein, I.D.,
Ballard, G., &
Zabelle, T.D.
(1999).
WorkPlan: Constraint-based database for work package scheduling.
Journal of Construction Engineering and Management, ASCE,
125(3),
151–160.Google Scholar
Clough, R.H. &
Sears, G.A.
(1991).
Construction Project Management.
New York:
Wiley.
Decker, K.S. &
Lesser, V.
(1992).
Generalizing the partial global planning algorithm.
International Journal on Intelligent Cooperative Information
Systems,
1(2),
319–346.Google Scholar
Durfee, E.H. &
Montgomery, T.A.
(1991).
Coordination as distributed search in a hierarchical behavior space.
IEEE Transactions on Systems, Man, and Cybernetics,
21(6),
1363–1378.Google Scholar
El-Rayes, K. &
Moselhi, O.
(1996).
Resource-driven scheduling of repetitive activities on
construction projects.
Construction Management and Economics,
16,
433–446.Google Scholar
Ephrati, E. &
Rosenschein, J.S.
(1996).
Deriving consensus in multi-agent systems.
Artificial Intelligence,
87(1–2),
21–74.Google Scholar
Feldman, A.M.
(1980).
Welfare Economics and Social Choice Theory,
Boston:
Martinus Nijhoff.
Finin, T.,
Fritzson, R.,
McKay, D., &
McEntire, R.
(1994).
KQML as an agent communication language.
Proc. Third International Conf. Information and Knowledge
Management, pp.
456–463,
New York:
ACM.
Fondahl, J.M.
(1961).
A Non-computer Approach to the Critical Path Method for the
Construction Industry.
Technical Report No. 9.
Stanford, CA:
Stanford University.
Fondahl, J.W.
(1991).
The development of the construction engineer: Past progress and
future problems.
Journal of Construction Engineering and Management,
117(3),
380–392.Google Scholar
Gomes, C.P.,
Tate, A., &
Thomas, L.
(1994).
Distributed scheduling framework.
Proc. Int. Conf. Tools With Artificial Intelligence, pp.
49–55.
Piscataway, NJ:
IEEE.
Jeon, H.
(2000).
Dynamic constraint management in collaborative design.
PhD Thesis.
Stanford, CA:
Stanford University.
Jin, Y. &
Levitt, R.E.
(1993).
i-AGENTS: Modeling organizational problem solving in multi-agent
teams.
Intelligent Systems in Accounting, Finance and Management,
2,
247–270.Google Scholar
Khedro, T.,
Genesereth, M.R., &
Teicholz, P.M.
(1993).
Agent-based framework for integrated facility engineering.
Engineering with Computers,
9(2),
94–107.Google Scholar
Kim, K. &
Paulson, B.C.
(2003).
An agent-based compensatory negotiation methodology to facilitate
distributed coordination of project schedule changes.
Journal of Computing in Civil Engineering,
17(1),
10–18.Google Scholar
Koo, C.C.
(1987).
A distributed model for performance systems.
PhD Thesis.
Stanford, CA:
Stanford University.
Malone, T.W.,
Fikes, R.E., &
Howard, M.T.
(1988).
Enterprise: A market like task scheduler for distributed computing
environment. In
The Ecology of Computation,
(Huberman, B.A., Ed.), pp.
177–205.
Amsterdam:
Elsevier Science BV.
Oberlender, G.D.
(1993).
Project Management for Engineering and Construction.
New York:
McGraw–Hill.
O'Brien, W. &
Fischer, M.A.
(2000).
Importance of capacity constraints to construction cost and
schedule.
Journal of Construction Engineering and Management,
126(5),
366–373.Google Scholar
O'Brien, W.,
Fischer, M.A., &
Jucker, J.V.
(1995).
An economic view of project coordination.
Construction Management and Economics,
13(5),
393–400.Google Scholar
Petrie, C.
(1996).
Agent-based engineering, the Web, and intelligence.
IEEE Expert,
11(6),
24–29.CrossRefGoogle Scholar
Petrie, C.,
Goldmann, S., &
Raquet, A.
(1998).
Agent-based Project Management.
Technical Report No. 19981118,
Stanford, CA:
Stanford University.
Rosenschein, J.S.
(1994).
Rules of Encounter: Designing Conventions for Automated Negotiation
Among Computers.
Cambridge, MA:
MIT Press.
Rosenschein, J.S. &
Zlotkin, G.
(1998).
Designing conventions for automated negotiation. In
Readings in Agents
(Huhn, M.N. &
Singh, M.P., Eds.).
San Francisco, CA:
Morgan Kaufmann.
Sandholm, T.
(1993).
An implementation of the contract net protocol based on marginal
cost calculations.
Proc. Eleventh National Conf. Artificial Intelligence, pp.
256–262.
Menlo Park, CA:
AAAI.
Sen, S. &
Durfee, E.H.
(1996).
A contracting model for flexible distributed scheduling.
Annals of Operations Research,
65,
195–222.Google Scholar
Shoham, Y. &
Tanaka, K.
(1997).
A dynamic theory of incentives in multi-agent systems.
Proc. Fifteenth Int. Joint Conf. Artificial Intelligence, pp.
626–631.
Menlo Park, CA:
AAAI.
Smith, R.G.
(1980).
The contract net protocol: High level communication and control in
a distributed problem solver.
IEEE Transactions on Computers,
C-29,
1104–1113.Google Scholar
Sycara, K.
(1989).
Multi-agent compromise via negotiation. In
Distributed Artificial Intelligence
(Gasser, L. &
Huhns, M., Eds.),
Vol. 2, pp.
119–137.
San Francisco, CA:
Morgan Kaufmann.
Sycara, K.,
Roth, S.,
Sadeh, N., &
Fox, M.
(1991).
Distributed constrained heuristic search.
IEEE Transactions on Systems, Man, and Cybernetics,
21(6),
1446–1461.Google Scholar
Tommelein, I.D. &
Ballard, G.
(1997).
Coordinating specialists.
Technical Report, No. 97-8.
Berkeley, CA:
University of California.
Varian, H.R.
(1978).
Microeconomic Analysis.
New York:
W.W. Norton.
Wellman, M.P.
(1993).
A market-oriented programming environment and its application to
distributed multicommodity flow problems.
Journal of Artificial Intelligence Research,
1,
1–23.Google Scholar
Yokoo, M.,
Durfee, E.H.,
Ishida, T., &
Kuwabara, K.
(1992).
Distributed constraint satisfaction for formalizing distributed
problem solving.
Proc. Twelfth IEEE Int. Conf. Distributed Computing Systems, pp.
614–621.
Piscataway, NJ:
IEEE.
Yokoo, M.,
Durfee, E.H.,
Ishida, T., &
Kuwabara, K.
(1998).
Distributed constraint satisfaction problem: Formalization and
algorithms.
IEEE Transactions on Knowledge and Data Engineering,
10(5),
673–685.Google Scholar
An example network schedule.
A resource requirement histogram.
An available resource histogram.
The revised resource histogram after TCC.
The revised resource histogram after LCC.
Predefined schedule-change options before coordination
Selected schedule-change options after ABCN
The revised resource histogram after ABCN.
Selected schedule-change options after TCC
Selected schedule-change options after LCC
Summary of resuls
The activity precedence network.
You have
Access
- 7
- Cited by