# A Decentralized Scheduling Policy for a Dynamically Reconfigurable Production System

Stefano Giordani, Marin Lujak, Francesco Martinelli

► To cite this version:

Stefano Giordani, Marin Lujak, Francesco Martinelli. A Decentralized Scheduling Policy for a Dynamically Reconfigurable Production System. The 4th International Conference on Industrial Applications of Holonic and Multi-Agent Systems, HoloMAS 2009, Springer, Aug 2009, Linz, Austria. pp.102-113, 10.1007/978-3-642-03668-2_10 . hal-05485726

HAL Id: hal-05485726

https://hal.science/hal-05485726v1

Submitted on 30 Jan 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# A Decentralized Scheduling Policy for a Dynamically Reconfigurable Production System

Stefano Giordani¹, Marin Lujak¹, and Francesco Martinelli²

¹ Dip. Ingegneria dell'Impresa - University of Rome "Tor Vergata", Italy

² Dip. Informatica Sistemi e Produzione - University of Rome "Tor Vergata", Italy

**Abstract.** In this paper, the static layout of a traditional multi-machine factory producing a set of distinct goods is integrated with a set of mobile production units - robots. The robots dynamically change their work position to increment the product rate of the different typologies of products in respect to the fluctuations of the demands and production costs during a given time horizon. Assuming that the planning time horizon is subdivided into a finite number of time periods, this particularly flexible layout requires the definition and the solution of a complex scheduling problem, involving for each period of the planning time horizon, the determination of the position of the robots, i.e., the assignment to the respective tasks in order to minimize production costs given the product demand rates during the planning time horizon.

We propose a decentralized multi-agent system (MAS) scheduling model with as many agents as there are the tasks in the system, plus a resource (robot) owner which assigns the robots to the tasks in each time period on the basis of the requests coming from the competing task agents. The MAS model is coupled with an iterative auction based negotiation protocol to coordinate the agents' decisions. The resource prices are updated using a strategy inspired by the subgradient technique used in the Lagrangian relaxation approach. To measure the effectiveness of the results, the same are evaluated in respect to that of the benchmark centralized model.

**Keywords:** Dynamic scheduling, multi-agent system, negotiation.

## 1 Introduction

Different solutions have been adopted through the years in the manufacturing domain in order to speed up the system's response to a fluctuating external demand. Some of the approaches to this problem include Flexible Manufacturing Systems (see, e.g., Huang and Chen, 1986), Group Technology (see, e.g., Selim et al., 1998), Holonic Manufacturing (see, e.g., Christensen, 1994), and Agile Productions Systems. Design and integration of robot assistance in manufacturing is a more recent research topic which also moves in this direction (see, e.g., Helms et al., 2002). Referring to the latter, we propose a scheduling solution to the problem where some production resources (machines) are assumed to be mobile units and can perform several different manufacturing tasks in the plant.
In more detail, we consider a manufacturing plant producing a set of distinct products where the tasks (i.e., assemblies of specific products) are executed on different fixed locations on the shop floor and require (additional) production resources represented by mobile manufacturing units, i.e., robots. The robots are assigned to the tasks where the production is executed, and dynamically change their location in respect to the tasks' local change in demand. A task can be seen as a non-preemptive set of manufacturing operations and all the tasks are assumed to be independent (or parallel). This for example occurs in the final stage of assembly process where the products, after the execution of the operations corresponding to a certain final assembly task on them, get distributed to the warehouses or clients, and, therefore, leave the system. The planning time horizon is assumed to be subdivided into a finite number of time periods. The problem we address consists in dynamically assigning the robots to the tasks, and minimizing production costs given the product demand rates during the planning time horizon.

From the organizational point of view, it is possible to identify two kinds of scenarios in an industrial factory: 1) the management of the plant is centralized, i.e., all the decisions are made by a single decision maker managing the whole system information; 2) the management of the plant is decentralized, i.e., the decisions are taken only using the local information by the set of local decision makers (agents) which are possibly in competition. The drawbacks of centralized systems are a lack of reliability since a critical point of failure in the network is a single central agent itself, and the elevated system's complexity as the system increases in size (see, e.g. Kurose and Simha, 1989, Sycara, 1998). In this paper, the latter, decentralized approach is adopted e.g. in the case when there is a significant number of production machines and the centralized system can not cope with the system's complexity in the real time. We analyze this scenario with a set of (task) agents representing the tasks which compete for the robots, and the resource (robot) owner, being in charge of managing the negotiation among task agents, and of assigning the robots to the tasks. This approach helps in building a highly scalable system since the decision-making process is distributed across all the fixed production machines and the resource owner, and therefore the decisions about the production lie in the hands of each one of them by locally maximizing their individual utility and profit through the process of multi-agent interaction and negotiation. Furthermore, market price mechanisms for resource allocation are by their nature distributed with each auction being held within certain limited dimensions. The most important advantages of this approach are modularity, regular interactions, incrementality, analyzability, and incentive engineering (see, e.g., Clearwater, 1996).

For this paper's scenario, a discrete time decentralized multi-agent system model coupled with an iterative auction based negotiation protocol (see, e.g., Kutanoglu and Wu, 2006, Schneider et al., 2005, and Robin, 1991) is proposed.

At the beginning of each iteration, the robot owner sets the robot hiring price to a given value for each time period. Each task agent, using this information together with its local information on demands and production costs of its specific product, performs its local optimization and makes a request to the robot
owner indicating the number of robots it wants to hire for each time period. The robot owner collects the task agent requests, finds a feasible robot assignment to tasks for each time period and, on the basis of the (positive or negative) deviation between the number of the total robot requests and the number of the available robots, changes the robot hiring prices for each time period so that the effective prices reach as much as possible the equilibrium between the number of the robots in the system and the number of the requested ones. In particular, an approach based on the subgradient technique used in Lagrangian relaxation is adopted (see, e.g., Chen et al., 1998, and Barahona and Anbil, 2000).

We experiment the proposed model considering highly variable demands in the planning time horizon: an ARMA model is used to model each task's demand fluctuations in the considered time horizon. To measure the effectiveness of the approach, a discrete time centralized model is used as a benchmark for the purpose of evaluating the fluctuation of the social welfare (see, e.g., Chevaleyre et al., 2006, Chevaleyre et al., 2004) of the task agents in the decentralized scenario.

The remainder of the paper is organized as follows. In Section 2 we review some of the economic models used in MAS negotiation in resource allocation. In Section 3 we describe the decentralized scheduling problem, and formulate the optimization problem addressed by each task agent. In Section 4 we describe the proposed negotiation process among agents. Furthermore, we give more details on the dynamic adjustment in subgradient optimization used in the auction algorithm, and on the evaluation of the quality of the robot assignment. Finally, in Section 5, we experiment the proposed decentralized model and compare its performance with that of the centralized scenario.

## 2 Negotiation Models in MAS Resource Allocation

For the multi-agent interaction and negotiation, there are several applicable economic models which might work well in this case (see, e.g., Kraus, 2001, Chevaleyre et al., 2006, Buyya et al., 2002). They are: Commodity Market model, where more resource owners specify their service price and charge users according to the amount of resource they consume; Posted price model, similar to the commodity market model, except that it publishes special offers to attract consumers to establish market share or motivate users to use cheaper offers. In this case there is no need for brokers to negotiate directly with clients for price, since the posted prices are generally cheaper than regular prices; Bargaining model where resource brokers bargain with clients for lower access price and higher usage duration; Tender/Contract-net model, which original version lacks a formal model for making bidding and awarding decisions. The Contract-net framework was extended to work among self-interested, computationally limited agents which decisions are based on marginal approximations of cost calculations. The advantage of this model is that if the selected contractor is unable to deliver a satisfactory service, the brokers can seek services of other contractors. This protocol has certain disadvantages. A task might be awarded to a less capable contractor if a more capable contractor is busy at award time.
In Auction Model, which is the approach chosen in this paper, one-to-many negotiation is supported, between a service provider (seller) who offers the goods or services for bids and then sells the item(s) to one winning out of many bidders (buyers) who give the bids to the seller. In the iterative version, the buyers can update the bids and the provider in respect to the offers updates the offered sale price. There are several variations on the basic auction form, including time limits, minimum or maximum limits on bid prices, and special rules for determining the winning bidder(s) and sale price(s). Auctions basically use market forces to negotiate a clearing price for the service and can be conducted as open or closed depending on whether they allow back-and-forth offers and counter offers (see, e.g., Vulkan and Jennings, 2000).

# 3 Decentralized Scheduling Problem

A manufacturing system producing $P$ products is considered. The production is realized by the execution of different and independent (i.e. parallel) tasks, one for each product, requiring (additional) resources represented by a set of $N$ identical mobile robots, all at disposal of the tasks. Given a finite production time horizon of $T$ time periods, we consider the following decentralized discrete time production scheduling problem, where each task agent requests robots from the robot owner for each time period and schedules the production based on product demands and production costs, and the robot owner assigns the robots to the tasks for each unit time period on the basis of their requests.

The agent representing the task $i$ knows, for each time period $k$, product demand $d_i(k)$, robot maximum production rate $r_i(k)$ (production capacity), unitary manufacturing cost $c_i(k)$, unitary holding cost $h_i(k)$, unitary backlog cost $b_i(k)$, and unitary robot hiring cost $\rho_i(k)$, all nonnegative. For each time period, besides the robot hiring cost, a task has to pay also the cost of displacement of the additionally assigned robots in the time period with respect to the robots assigned to it in the previous time period. The same holds for the end of the planning time horizon, $T$, when the tasks with assigned robots pay the costs of the robot displacement to the robot depot. It is reasonable to assume that the robot's displacement time is negligible in respect to the length of the time period, $\Delta t$, and that the robot displacement cost does not depend on the locations of the tasks in the factory. This stands for the physical layout of the plant which is circular with radius $R$, as shown in Fig. 1. Therefore, let $\delta_i(k) = \delta$ be the cost of displacement of an additional robot to the location of task $i$ at the beginning of period $k$ (with $k = 1, \dots, T$), and let $\delta_i(T+1) = \delta$ be the cost of displacement of a robot to the robot depot at the end of the planning time horizon. For each time period $k$, the decision variables controlled by the agent of task $i$ are:

* $n_i(k) \ge 0$: required number of robots (robot request);

* $\Delta n_i(k) \ge 0$: number of additional robots in the present time period in respect to the one required in the period before;

* $u_i(k) \ge 0$: production rate.
<figure><img src="image_2.png" /><figcaption>Fig. 1. Circular shop-floor model</figcaption></figure>

Production can be anticipated or delayed in respect to the product demands resulting in holding and backlog costs, respectively. Each task *i* is associated with a buffer which content $x_i(k)$ at the end of time period *k* can be positive (if a stock of completed product items is present in the buffer) or negative (if a backlog of demands for the product realized with task *i* is in the queue). Using a standard notation, we denote $x_i^+(k) := \max\{x_i(k), 0\}$ as the stock level, and $x_i^-(k) := \max\{-x_i(k), 0\}$ as the backlog level at the end of time period *k*. Notice that, for each time period *k*, and task (product) *i*, only one of $x_i^+(k)$ and $x_i^-(k)$ can be different from 0 (i.e., $x_i^+(k) \cdot x_i^-(k) = 0$, $\forall k, \forall i$).

The local optimization problem addressed by every task agent *i* includes $x_i^+(k)$ and $x_i^-(k)$ as additional variables, for each time period *k*. Those variables, together with the production rates $u_i(k)$, are assumed to be continuous according to a fluid approximation. Given the above parameters and variables, the local optimization problem, $P_i$, addressed by each task agent *i* can be formulated as follows.

$$ (P_i): \quad \min z_i = \sum_{k=1}^{T} [h_i(k)x_i^+(k) + b_i(k)x_i^-(k) + c_i(k)u_i(k)] + \sum_{k=1}^{T} [\rho_i(k)n_i(k) + \delta_i(k)\Delta n_i(k)] + \delta_i(T+1)n_i(T), \quad (1) $$

subject to:

$$ x_i^+(k) - x_i^-(k) = x_i^+(k-1) - x_i^-(k-1) + \Delta t[u_i(k) - d_i(k)], \quad k = 1, \dots, T \quad (2) $$

$$ u_i(k) \le r_i(k) n_i(k), \quad k = 1, \dots, T; \quad (3) $$

$$ n_i(k) - n_i(k-1) \le \Delta n_i(k), \quad k = 1, \dots, T; \quad (4) $$
$$u_i(k), x_i^+(k), x_i^-(k), \Delta n_i(k) \ge 0, \quad k = 1, \dots, T; \qquad (5)$$

$$0 \le n_i(k) \le N \quad \text{and integer, } k = 1, \dots, T. \qquad (6)$$

The values of $x_i^+(0)$, $x_i^-(0)$, and $n_i(0)$ represent the initial conditions, i.e. the stock level, the backlog level, and the number of preassigned robots to task $i$ respectively, at the beginning of the planning time horizon. These values are assumed to be equal to zero. Constraints (2) are the mass balance constraints among product demand $\Delta t \cdot d_i(k)$, stock level $x_i^+(k)$, backlog level $x_i^-(k)$, and production level $\Delta t \cdot u_i(k)$, for each time period $k$. W.l.o.g., assuming that, for each time period $k$ and for each task $i$, the values of $h_i(k)$ and $b_i(k)$ are positive, the constraint $x_i^+(k) \cdot x_i^-(k) = 0$, is implicitly satisfied by the optimal solution, and, hence, omitted in the formulation. Constraints (3) limit the production rate $u_i(k)$ to be not greater than the production capacity $r_i \cdot n_i(k)$. Constraints (4) together with the (non-negative) robot displacement cost allow to find the value $\Delta n_i(k)$ of additionally assigned robots: note that there is no need to define this variable as an integer in the formulation.

For each task agent $i$, let $n_i^*(k)$ be the number of required robots at time period $k$, in the optimal solution of problem $P_i$, and let $z_i^*$ be the optimal solution of $P_i$. Each task agent (decision maker) finds such a solution taking into account only its local objective and constraints, but shares with the other task agents limited amount of available robots (resources). Therefore, these local decisions can be implemented only if the following global constraints are satisfied.

$$\sum_{i=1}^{P} n_i^*(k) \le N, \quad k = 1, \dots, T. \qquad (7)$$

In general, this is not the case, and, hence, a negotiation process must be implemented among the task agents to come up with a set of local solutions that together satisfy also Constraints (7). We assume that this process is supervised by another decision maker, i.e. the robot owner, that assigns the robots to the tasks for each time period on the basis of their requests, guaranteeing the fulfilment of the constraint on the limited robot amount. In the next section, we provide a model for such a negotiation.

# 4 Negotiation Process

The negotiation among the tasks is modeled by an iterative auction process controlled by the robot owner which is in charge of coordination of the negotiation. At each iteration:

Step 1. The robot owner (auctioneer) communicates to the task agents (bidders) current prices of the robots in the $T$ time periods;
Step 2. Each task agent based on the local utility function of its local objective, the constraints, and the current robot prices, determines the robot requests (a bid) for the T time periods maximizing its utility function, and communicates its robot requests to the robot owner;

Step 3. Based on the bids received from the task agents, the robot owner allocates the robots to the tasks, for each time period, maximizing its own utility function;

Step 4. In order to reduce the possible conflicts among tasks generated by their bids (i.e., the violation of Constraints (7)), or to stimulate the usage of the robots, the robot owner updates the robot prices.

The iteration process repeats until a certain (halting) condition is reached (e.g., a maximum number of iterations have been performed, or the best robot allocation found is sufficiently good from the agents' point of view). At the end, the best robot allocation is retrieved.

Let $B_i = \{n_i(k) : k = 1, \dots, T\}$ be a bid of task agent $i$, and let $\Lambda = \{\lambda(k) : k = 1, \dots, T\}$ be the (current) set of the robot prices fixed by the robot owner (each one for each time period). The utility function $U_i(B_i, \Lambda)$ of agent $i$ is the opposite of the total production cost during the planning time horizon:

$$U_i(B_i, \Lambda) = -z_i^*(B_i) - p(B_i, \Lambda). \qquad (8)$$

In this expression, $z_i^*(B_i)$ is the (minimum) production cost for task $i$ with fixed numbers of assigned robots $n_i(k)$, with $k = 1, \dots, T$, according to bid $B_i$, and $p(B_i, \Lambda) = \sum_{k=1}^T \lambda(k)n_i(k)$ is the (additional) robot cost to be payed to the robot owner. Note that, $z_i^*(B_i)$ is the optimal solution of the local optimization problem $P_i$ with fixed values of $n_i(k)$.

In Step 2, agent $i$ finds the best bid $B_i^*$, i.e., the bid that maximizes its utility function $U_i(B_i, \Lambda)$. Let $U_i^*(\Lambda)$ be its maximum value for a given set $\Lambda$ of robot prices. Finding $B_i^*$, and hence determining $U_i^*(\Lambda)$, corresponds to solving the problem $P_i$ with $\lambda(k)$ added to the robot hiring cost $\rho_i(k)$ in the objective function (1).

In Step 3, the resource owner receives bid $B_i^*$ from each task $i$, and assigns robots to tasks maximizing its utility function taking into account the received bids. Denoting with $\nu_i(k)$ the number of robots assigned to task $i$ in time period $k$, the utility function $R(\nu, \Lambda)$ of the resource owner is the total profit obtained from the robot assignment, and, hence, it is

$$R(\nu, \Lambda) = \sum_{k=1}^{T} \lambda(k) \sum_{i=1}^{P} \nu_i(k). \qquad (9)$$

Since $\nu_i(k)$ cannot be greater than robot request (bid) $n_i^*(k)$ of task agent $i$ and $\sum_{i=1}^P \nu_i(k)$ cannot be greater than $N$, for each $k = 1, \dots, T$, the maximization of $R(\nu, \Lambda)$ can be easily obtained by assigning robots to tasks as follows.

For each time period $k$, order the tasks according to the non-increasing robot requests $n_i^*(k)$, and, following this task order, assign $\nu_i(k) = \min\{n_i^*(k), N'(k)\}$
robots to task $i$, where $N'(k)$ (with $0 \le N'(k) \le N$) is the number of non-assigned (yet available) robots in time period $k$.

The quality of the robot assignment is evaluated from the agents' point of view, measuring the social welfare $w(\nu)$ of the tasks related to a given robot assignment $\nu = \{\nu_i(k) | i = 1, \dots, P, k = 1, \dots, T\}$ as the (minimum) total production cost of the tasks with that robot assignment, that is,

$$w(\nu) = \sum_{i=1}^{P} z_{i}^{*}(\nu_{i}), \qquad (10)$$

where $z_i^*(\nu_i)$ is the optimal solution of $P_i$ with a given number of robots $n_i(k) = \nu_i(k)$ assigned to task $i$, for each time period $k$. Let $w^*$ be the best (minimum) value of the social welfare found so far during the iterative auction process. It can be proved that the expression

$$w_L(\Lambda) = - \sum_{i=1}^{P} U_i^*(\Lambda) - N \sum_{k=1}^{T} \lambda(k), \qquad (11)$$

is a valid lower bound on the best value of the agents' social welfare, for any vector $\Lambda$ of non-negative robot prices $\lambda(k)$.

In Step 4 the resource owner updates the robot prices $\lambda(k)$, with $k = 1, \dots, T$. This is done, considering the total requests' deviation $dev(k) = \sum_{i=1}^{P} n_i^*(k) - N$ of the total number of requested robots from the number $N$ of available robots, and by increasing the current value of $\lambda(k)$ if $dev(k)$ is positive (i.e., $dev(k)$ is the excess of robot requirements), or decreasing it (at most to 0) if $dev(k)$ is negative (in this latter case $-dev(k)$ is the deficit of robot requirements). The value of the increase (decrease) of $\lambda(k)$ should be a non-decreasing function of the excess (deficit); moreover, it is a good practice that the auctioneer is more aggressive in the early iterations to get very quickly a good robot assignment, while smaller adjustments can be made in later iterations to refine the quality of the same. A possible choice for the price updating that goes in this direction is that of using an algorithm inspired by the subgradient technique used in Lagrangean relaxation, that experimentally guarantees the convergence of the Lagrangean dual (see, e.g., Held et al., 1974).

At iteration $h$ of the auction process, let $dev^h(k)$ be the deviation of the robot requirements, and $\Lambda^h$ be the vector of the robot prices $\lambda^h(k)$, with $k = 1, \dots, T$. The new value of the robot price in time period $k$ at iteration $h+1$ is:

$$\lambda^{h+1}(k) = \max \left\{ 0, \lambda^h(k) + \alpha^h \frac{w^* - w_L(\Lambda^h)}{\sum_{k=1}^{T} (dev^h(k))^2} dev^h(k) \right\}, \qquad (12)$$

where $\alpha^h$ is a scalar controlling the aggressiveness of the auctioneer. Following analog practice in Lagrangean relaxation (see, e.g., Held et al., 1974) we start with value $\alpha_0 = 2$, and halve its value if the best task social welfare value found so far is not improved within a certain number of iterations.
In Step 1, the amount of information going from the robots' owner to the task agents is $O(P \cdot T \cdot \log(\lambda_{max}))$ bits, where $\lambda_{max}$ is the maximum robot price. In Step 2 the amount of information sent by the task agents to the robot owner is $O(P \cdot T \cdot \log(N))$ bits. Step 3 is done in $O((P \log P) \cdot T)$ time. Finally, in Step 4, the price update is done in $O(P \cdot T)$ time.

# 5 Performance Analysis

The performance of the proposed decentralized multi-agent system model is compared with that of the optimization model for the production scheduling problem in the centralized scenario where the management of the plant is done by a single decision maker that controls all the information of the whole system.

## 5.1 Centralized Scheduling Model

The centralized production scheduling problem consists in minimizing the total cost of the tasks under the set of local task constraints and the constraint on the limited number of robots. Following analog reasoning used in modeling the local production scheduling problem addressed by each task in the decentralized scenario, we model the centralized problem as follows. The objective function to be minimized is the total cost of the tasks, that is, the social welfare $w = \sum_{i=1}^{P} z_i$, where $z_i$ is the objective function (1) of problem $P_i$. The constraints to be fulfilled are the set of local constraints of each task $i$, that is, the set of constraints (2)–(6) of problem $P_i$, for each $i = 1, ..., P$, with the addition of the constraints on the limited number of robots, that is,

$$ \sum_{i=1}^{P} n_i(k) \le N, \quad k = 1, ..., T. \qquad (13) $$

## 5.2 Simulation Results

The Multi-Agent System is simulated. The simulator and the negotiation algorithm are implemented in the C language using the CPLEX 8.0 callable library for the solution of problem $P_i$ and are run on a PC with a 1.5 GHz dual-core duo CPU and 1 GB of RAM.

The production system is simulated with $P = 10$ tasks. The number of time periods of the planning horizon is $T = 100$, with the duration of each period $\Delta t = 1$. The external demand of task $i$ is modeled as $d_i(k) = \bar{d}_i \cdot [1 + \delta d_i(k)]$, for $k = 1, ..., T$, where $\bar{d}_i$ is the average demand rate of the product produced by task $i$ in the planning horizon and $\delta d_i(k)$ are values generated by the ARMA process with parameters $p_i = 2$ and $q_i = 2$ taken from the Example (2) of Gaalman (2006). In our numerical example, the average demand is $\bar{d}_i = 5$, for each product $i$.

We simulate the production system with different number of robots, $N$. In order to cover a wide range of cases (from very highly congested to very low-congested cases), we consider the values of $N$ in the range $[\bar{N}(1-0.4), \bar{N}(1+0.4)]$,
where $\bar{N}$ is the number of robots for which the average production rate of the system $\bar{N} \frac{1}{P \cdot T} \sum_{i=1}^{P} \sum_{k=1}^{T} r_i(k)$ (approximately) equals the total average demand rate $\sum_{i=1}^{P} \bar{d}_i$.

The values of the unitary production costs are fixed, noticing that if the unitary backlog cost $b_i(k)$ is not large enough in respect to the unitary manufacturing cost $c_i(k)$, and the robot cost $\rho_i(k)$, it may happen that, even if the system has enough capacity to clear all the demand, a positive backlog is found at the end of the planning horizon. For this reason, in the numerical case considered here, we assumed for each task $i$ the following relation among the parameters of the cost function:

$$h_i(k) < c_i(k) + \frac{\rho_i(k)}{r_i(k)} < b_i(k) \qquad (14)$$

The first inequality in (14) constrains the unitary holding cost $h_i(k)$ to be lower than the sum of the unitary manufacturing cost $c_i(k)$ and the robot cost per unit of allocated production capacity ($\frac{\rho_i(k)}{r_i(k)}$). The second inequality prohibits starvation as mentioned above. If these relations on the cost parameters hold, the backlog of the system at the end of the planning horizon can be used as a measurement of the congestion. For simplicity, we assume that the unitary costs of backlog, $b_i(k)$, inventory, $h_i(k)$, manufacturing, $c_i(k)$, and robot rental, $\rho_i(k)$, are constant and equal for all the tasks in all the time periods. In our case the costs are: $h_i(k) = 4$, $\rho_i(k) = 10$, $c_i(k) = 5$, $b_i(k) = 20$, $\forall i, \forall k$. Finally, the robot production capacity $r_i(k)$ is also assumed to be constant and equal for all the tasks and time periods. In particular, we assume $r_i(k) = 1$ for each task $i$ and time period $k$. In this way, all the considered mixed integer problems are solved within a fraction of one second by CPLEX, and, hence, we are able to execute each simulation in less than two minutes; notice, however, that providing a CPU

<figure><img src="image_3.png" /><figcaption>Fig. 2. Decentralized vs. centralized performance, number of tasks: $P = 10$</figcaption></figure>
time efficient approach for the considered scheduling problem is out of the scope of this paper.

Let $w_D$ be the best solution value of the total production cost (social welfare) obtained for the decentralized scenario by applying the proposed approach, and let $w_C$ be the optimal solution value of the model for the centralized scenario. Performance of the decentralized model in respect to the centralized one is evaluated measuring the gap (in percentage) $g = [(w_D - w_C)/w_C] \cdot 100$, that provides an estimation of the relative extra-cost incurred in the decentralized scenario in respect to the centralized one for not having at disposal all the system information to optimally reconfigure and distribute the available robots.

Fig. 2, for $P = 10$, shows the trends of the social welfare $w_D$ and $w_C$ for the decentralized and centralized scenarios, respectively, and gap $g$, for increasing number $N$ of robots in the range $[\bar{N}(1-0.4), \bar{N}(1+0.4)]$, with $\bar{N} = 50$ (since $\sum_{i=1}^P \bar{d}_i = 50$ and $\bar{N} \frac{1}{P} \sum_{i=1}^P \sum_{k=1}^T r_i(k) = 50$). In particular, for $N \le \bar{N}(1-0.15)$ or $N \ge \bar{N}(1+0.15)$, $g$ is less than 5% and it decreases as $N$ reaches the extremes of the considered range of values of $N$, for which $g$ is less than 0.1%. In fact, when the total number of robots in the system is significantly lower than $\bar{N}$, the system is highly constrained, and both the decentralized and the centralized approaches are characterized by very high and comparable backlog costs. The total costs of the two approaches differ in practice in the values of the other cost components, that are indeed negligible in respect to the backlog cost. Oppositely, when the total number of robots in the system is significantly larger than $\bar{N}$, the local optimal solutions of the task agents’ subproblems are likely to satisfy (resource) Constraints (7), and then the set of local solutions of the decentralized approach is equivalent to the centralized solution. Moreover, in this case, there is no backlog cost and then the total cost of both approaches is small. In the intermediate case, i.e., when $N$ approaches $\bar{N}$, the gap $g$ among the total costs of the decentralized and the centralized approach increases. This is due to the fact that the latter approach can take full advantage of having at disposal all the information, which allows it to satisfy the resource constraint with a smaller backlog cost in respect to that payed by the decentralized case.

# 6 Conclusions

A flexible manufacturing shop floor layout consisting of a set of mobile machines (robots) is considered in this paper. A multi-agent system coupled with an iterative auction based negotiation protocol is proposed to solve the problem of dynamic allocation of the robots to the tasks of the system in response to demand and/or cost fluctuations. For simplicity, the tasks are assumed independent, but the solution approach can also be applied to the case of tasks with precedence relations (see, e.g., Kutanoglu, 2006). The performance of the proposed decentralized solution is then compared with the same (optimal) obtained by using a centralized planner: the intuitive result that the two approaches provide a different cost only when the production capacity of the system is approximately equal to the average demand is noticed. This is the case in fact, when the conflict
in the resource allocation is often violated and its proper management (possible
only if the decision maker has all the system's information) makes the difference.

References

Barahona, F., Anbil, R.: The volume algorithm: producing primal solutions with a subgradient method. Math. Prog. 87, 385–399 (2000)

Buyya, R., Abramson, D., Giddy, J., Stockinger, H.: Economic models for resource management and scheduling in grid computing. Concurrency and Computation: Practice and Experience 14, 1507–1542 (2002)

Chen, H., Chu, C., Proth, J.M.: An improvement of the Lagrangean relaxation approach for job shop scheduling: A dynamic programming method. IEEE Trans. on Rob. and Autom. 14, 786–795 (1998)

Chevaleyre, Y., Endriss, U., Estivie, S., Maudet, N.: Multiagent resource allocation with k-additive utility functions. In: Proc. DIMACS-LAMSADE Workshop on Comp. Science and Decision Theory, Annales du LAMSADE, pp. 83–100 (2004)

Chevaleyre, Y., Dunne, P.E., Endriss, U., Lang, J., Lemaitre, M., Maudet, N., Padget, J., Phelps, S.: Issues in multiagent resource allocation. Informatica 30, 3–31 (2006)

Christensen, J.H.: Holonic manufacturing systems: Initial architecture and standards directions. In: Proc. 1st Euro Workshop on Holonic Manufacturing Systems, HMS Consortium, Hannover, Germany, December 1 (1994)

Clearwater, S.H.: Market-based control: a paradigm for distributed resource allocation. World Scientific Publishing Co., Inc, River Edge (1996)

Gaalman, G.: Bullwhip reduction for ARMA demand: The proportional order-up-to policy versus the full-state-feedback policy. Automatica 42, 1283–1290 (2006)

Held, M., Wolfe, P., Crowder, H.D.: Validation of subgradient optimization. Math. Prog. 6, 62–88 (1974)

Helms, E., Schraft, R.D., Haegele, M.: Robwork: Robot assistant in industrial environments. In: Proc. 11th IEEE workshop ROMAN 2002, pp. 399–404 (2002)

Huang, P.Y., Chen, C.S.: Flexible manufacturing systems: An overview and bibliography. Prod. and Inv. Mng. 27, 80–90 (1986)

Kraus, D.S.: Strategic negotiation in multiagent environments. MIT Press, Cambridge (2001)

Kurose, J.F., Simha, R.: A microeconomic approach to opt. resource allocation in distributed comp. systems. IEEE Transactions on Computers 38, 705–717 (1989)

Kutanoglu, E., Wu, S.D.: Incentive compatible, collaborative production scheduling with simple communication among distributed agents. Int. J. of Prod. Res. 44, 421–446 (2006)

Roundy, R.O., Maxwell, W.L., Herer, Y.T., Tayur, S.R., Getzler, A.W.: A price-directed approach to real-time scheduling of production operations. IIE Transactions 23, 149–160 (1991)

Schneider, J., Apfelbaum, D., Bagnell, D., Simmons, R.: Learning opportunity costs in multi-robot market based planners. In: Proc. 2005 IEEE International Conference on Robotics and Automation, pp. 1151–1156 (2005)

Selim, H.M., Askin, R.G., Vakharia, A.J.: Cell formation in group technology: review, evaluation and directions for future research. Comp. and Ind. Eng. 34, 3–20 (1998)

Sycara, K.P.: Multiagent Systems. AI Magazine 19(2), 79–92 (1998)

Vulkan, N., Jennings, N.R.: Efficient mechanisms for the supply of services in multi-agent environments. Decision Support Systems 28(1-2), 5–19 (2000)