Conversation

The agents negotiate between themselves by using a variant of the contract Net Protocol [Davis e Smith, 1983] specially developed in this work. This variant is called "Contract Net Protocol with Constraint Propagation", and is described in the next image:

Figure 3 - Negotiation between agents: Contract Net Protocol with Constraint Propagation

Description

[Adapted from: Paulo Sousa, Carlos Ramos and José Neves (1999), Contracting Tasks Between Autonomous Resources – An application to dynamic scheduling of manufacturing orders. Proceedings of The Practical Application of Agents and Multi-Agents Technologies (PAAM’99), pp. 345-362. London, UK, 19-21 April 1999]

This section extends the protocol described in [Sousa and Ramos, 1998] by further explaining the scheduling procedure which has been adopted from a centralised method well described in [Ramos et al., 1995]. The protocol, based on the Contract Net Protocol [Davis e Smith, 1983], is divided in 4 phases:

1. task announcement;
2. forward influence;
3. backward influence and bidding; and
4. contracting.

For the scheduling of operations a Task Holon will negotiate with resources and establish a contract among them. The Resource Holons will then use constraint propagation in order to guarantee the relations among different operations for the same task.

During this section an example task will be used, consisting of three operations (op1, op2 and op3) that must be done sequentially. In the example scenario there are 4 resources that have some previous commitment to certain tasks, i.e. their agendas are not empty. Each resource is able of performing one operation and for operation op1 there are two possible resources A1 and A2.

Task Announcement

Figure 3 is a diagram of the exchanged messages in this phase. First, the Task Manager creates a new Task Holon and announces it what to do. Second, the recently created Task Holon will ask the Process Planning Holon for a basic plan – and some alternative plans too – for the manufacturing of the requested item. Third, the Process Planning Holon replies and the Task Holon selects a plan and builds up a list of necessary resources for the execution of that plan. (At this stage, Plans are generated by a system called TPMS - Task Planning for Manufacturing Systems [15] which acts as the Process Planning Holon in Figure 2). Fourth, the Task Holon sends the list of resources to the Task Manager, which will guarantee no conflict will arise during the negotiation process (as described on section 4.1). Fifth and last, when there is no chance that a conflict could arise, the Task Manager signals the Task Holon to start the negotiation.

Figure 3 – Task announcement

Forward Influence

During this phase constraint propagation will be done in order to determine the effective time-window of each operation. First of all the Task Holon contacts all the resources able to perform each operation, informing about resources contacted for predecessor and successor operations (Figure 4).

Figure 4 – Resource request

When a Request Announcement message arrives, the Holon looks at its agenda (denoted by ag' in Figure 5) and reserves time slots for that request. Later it will schedule the operation in some of those slots or simply delete the reservation if the task Holon don’t contract it.

After that, Resource Holons with no predecessors will pass a "influenced" list of time intervals to the successor Resource. This list is obtained by shifting the reserved intervals by the duration of the operation. For each List of Intervals message received, the Resource Holon will combine it with its agenda obtaining a new one (denoted by ag), i.e. intersect the time-intervals and remove the ones shorter then the operation’s duration.

Figure 5 – Forward influence

The new agenda will be the basis for the "influenced" list of intervals it will pass to successor Resource Holons (Figure 5). The forward influence phase stops when all resources with no successor receive the list of intervals from their predecessors.

Backward Influence and Bidding

The backward influence phase is similar to the forward influence but in the opposite direction. The backward influence phase ends when the Resource Holons for operations with no predecessor receive the list of intervals from the operations succeeding them.

When each Resource Holon has the final agenda, it responds to the Task Holon with a Resource Bid message (Figure 6), which includes information about the time intervals where the operation can be scheduled.

Figure 6 – Backward influence and bid

Contracting

After receiving all Resource Bid messages the Task Holon selects – based on heuristic rules (e.g. the resource having more free time till the deadline) – one Resource Holon that is able to handle each operation (Figure 7). If the co-ordination between resources is not possible, the Task Holon tries to change the selection of Resource Holons for the operations.

Figure 7 – Closing the negotiation

When receiving the Resource Request Acknowledge message, the resource Holon schedules the requested operation based on globally defined policies – e.g. ‘as late as possible’ – and locally defined ones – e.g. ‘for this resource, due to its low availability, schedule as soon as possible’. If, on the opposite, the resource receives a Resource Request Cancel message it erases the reservation made for that task and considers that time slots available for other tasks (in Figure 7 this is the case for resource A2).

References

(c) 1999-2000, Paulo Sousa
comments
Created: December 13th, 1999
Last updated: July 10th 2000