# A Data Aggregation Methodology to Assess the Global Production Capacity of Complex Supply Chains

Frederic Pereyrol, Jean-Christophe Deschamps, Julien François, Pascale Farthouat, Remy Dupas

## ► To cite this version:

Frederic Pereyrol, Jean-Christophe Deschamps, Julien François, Pascale Farthouat, Remy Dupas. A Data Aggregation Methodology to Assess the Global Production Capacity of Complex Supply Chains. International Conference on Advances in Production and Management Systems (APMS), Sep 2009, Paris, France. pp.251-258, 10.1007/978-3-642-16358-6_32. hal-01055846

HAL Id: hal-01055846

https://inria.hal.science/hal-01055846

Submitted on 13 Aug 2014

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published 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>

Distributed under a Creative Commons Attribution 4.0 International License
# A data aggregation methodology to assess the global production capacity of complex supply chains

Frederic Pereyrol¹, Jean-Christophe Deschamps¹, Julien François¹, Pascale Farthouat¹, Remy Dupas¹,

¹ University of Bordeaux, LAPS - IMS
351 Cours de la Liberation
33405 TALENCE cedex, France
{Frederic.Pereyrol, Jean-Christophe.Deschamps, Julien.François, Pascale.Farthouat, Remy.Dupas}@ims-bordeaux.fr

**Abstract.** Nowadays, no decisional tools allow to assess if an unforeseen customers demand variation should be accepted without creating material disruptions among a supply chain or not. The main difficulty consists in aggregating resources capacities, especially if resources perform different tasks with multiple items. This paper then proposes a data aggregation methodology based on graph analysis in order to assess the global production capacity of complex resources networks, like supply chains.

**Keywords:** aggregate capacity, networks flows, manufacturing processes

## 1 Introduction

In supply chains, decisions individually performed by each decision maker to elaborate its production plans guarantee a local optimal solution (i.e. the best compromise in terms of performances they intend to improve), but do not always ensure the most efficient coordination through the whole supply chain (SC). Many researchers have studied this problematic and have proposed different global solving approaches. Some studies proposed to develop a centralized middle-term planning process applied to the wide supply network. Others showed that performance is better when information (supply, production and delivery plans) is shared between industrial partners [2] [3] [5].

Since practical studies show that a centralized supply chain management represents today a non realistic approach for industrials, SC partners actually begin to share information to propose a common system of aggregated performance indicators. Assuming that this practice will be developed in the future, this paper proposes a data aggregation methodology starting from detailed technical data in order to assess the global production capacity of a supply chain. This study is motivated by the lack of tools allowing to evaluate if an unforeseen customers demand variation should be accepted without creating material disruptions among a SC or not.
In section 2, we will propose useful concepts and models in defining a new approach for assessing aggregated capacities in complex resources networks. Section 3 will describe the methodology used to reduce the complexity of graphs (and data) supporting the aggregate capacities calculation. A numerical example will be presented in section 4 to illustrate the considered approach before concluding.

## 2. Concepts and models

The originality of this paper consists in considering multi items performed on operating resources, their capacities being considered as dependant of the nature of the achieved products. The proposed approach consists in estimating an aggregated capacity to implement a global planning process in order to help managers to assess their own production loads in an aggregate way, according to customers' demands. A multi-level decomposition is applied to analyse the physical processes and graphs are used to model the supply chain structure. The proposed approach is defined, considering its application on a single time unit but should be generalized to a whole horizon time.

### 2.1 Modelling production processes by graphs

The proposed structured analysis framework is based on graph theory in order to assess the capacity of heterogeneous and interdependent production resources performing multiple items.

Let consider a detailed production process composed of a set $\mathbb{R}$ of operating resources $R_r$ (where r is the index of resource – $\mathbb{R}=\{R_r | r \in [1..R]\}$). These ones perform a set $\mathcal{T}$ of tasks $T_t$ - $\mathcal{T}=\{T_t | t \in [1..T]\}$. The relations between tasks and resources are expressed through the definition of a matrix $\Omega$: each resource $R_r$ fulfils one or several tasks, and its capacity is defined by a vector $\omega_r = [\omega_{r1} \dots \omega_{rr} \dots \omega_{rT}]^T$ ($t \in [1,...,T]$) wherein each component $\omega_{rt}$ represents "the maximum number of tasks t performed per time unit when the resource r only executes this type of task". When a resource $R_r$ has no technical competence to perform a task $T_t$, $\omega_{rt}=0$. The vectors set is synthesized through the matrix $\Omega=\{\omega_r / \forall r \in \mathbb{R}\}$ which represents the capacities set of all resources involved in production. The production process performs $P$ items (components, intermediate and finished products). Those required for performing the different tasks are defined in matrix $B=[\beta_{pq} | p,q \in [1..P]]$ where $\beta_{pq}$ is the number of component $P_p$ required to perform the product $P_q$, i.e matrix B characterizes the bill of materials (BoM) coefficients.

Digraphs (directed graphs) are used to depict two production representations: the resources dependencies and tasks sequencing. Let $\mathcal{V}$ and $\mathcal{E}$ be respectively the vertex and edge set of a acyclic graph $G=(\mathcal{V},\mathcal{E})$. Depicting the resources network by a graph $G$ allows us to have a flow-oriented representation. Each vertex (or node) $v \in \mathcal{V}$ is associated to an operating resource $R_r$ and a task $T_t$ (fig 1) according to matrices:

$$ - D=[d_{vr} | v \in \mathcal{V}, r \in \mathbb{R}] \text{ with } d_{vr}=1 \text{ if resource } R_r \text{ is related to node } v, 0 \text{ otherwise,} $$
$L=[l_{vt} | v \in V, t \in T]$ with $l_{vt}=1$ if task $T_t$ is related to node $v$, 0 otherwise,

Vr should be deduced from matrix D, expressing the vertices set associated to the same resource $R_r$. Directed edges $e \in E$ (also called arcs and noted $e=(u,v) \forall u,v \in V$) between nodes model the operating activities sequencing. Fig 1 proposes an example of graph G. Notice that, in this case, task $T_2$ is performed by resources $R_3$ or $R_4$, resource $R_2$ (respectively $R_4$) performs tasks $T_4$ (respectively $T_2$ and $T_5$).

<figure><img src="image_2.png" /><figcaption>Fig. 1 Production process modelling by graph</figcaption></figure>

In the following, we assume that, in graph G, a transportation activity always separates two production activities; divergence of materials flows is only due to transportation: a transportation task is represented by a node with one incoming arc and various outgoing arcs. Convergence of materials flow is only made in entrance of a production task $T_t$, which is then modelled by a vertex $v$ with various incoming edges and one outgoing edge (each operation performs one item (one outgoing product) resulting from the production/assembly of one or various components with different quantities).

We also make the hypothesis that a product $P_p$ and the task $T_t$ which accomplishes this one should be assimilated, so that $p=t$ (ex: task $T_2$ performs a product $P_2$). Based on this hypothesis, we define a matrix $A=[a_{uv} | u,v \in V]$ similar to a classical adjacency matrix except that the value $a_{uv}$ associated to each edge (when it exits) is determined as the coefficient $\beta_{pq}$ such as it is known at the customer's who orders the product $p$ (performed through the task $T_t$ associated to vertex $u$).

## 2.2 Calculation of network capacities based on classical solving approaches

The Max-Flow determination in the graph G representing flow interactions between operating resources is one way to assess the network capacity, when each resource $r$ is dedicated to one type of tasks (only one component of vector $\omega_r$ is not equal to zero).

In this case, the capacity matrix $C=[c_{uv} | u,v \in V]$ of the graph G can be easily deduced from the matrix $\Omega$. $C$ is derived from the adjacency matrix of the graph G in which $c_{uv}$ is a weight associated to an edge $e$ outgoing from vertex $u$ and incoming to vertex $v$. In order to simplify the graph analysis, we assume that all of materials (BoM) coefficients $\beta_{pq}$ are taken into account in the definition of capacities $c_{uv}$.
expressed on the graph G (through the use of matrix A), so that the unit of measure is
“the number of lots”:

$$
c_{uv} = \frac{(\sum_r \sum_l l_{ur} \cdot d_{ur} \cdot \omega_{tr})}{a_{uv}} \quad \forall u \in \mathcal{V}, v \in \text{Out}(u) \quad (1)
$$

The weight $c_{uv} \neq 0$ of every edge $e$ is completed by a flow $f_{uv}$ such as flows satisfy the classical constraints (2) and (3):

$$
f_{uv} \le c_{uv} \qquad \forall u, v \in \mathcal{V} \tag{2}
$$

$$
\sum_{u \in \text{In}(v)} f_{uv} = \sum_{w \in \text{Out}(v)} f_{vw} \qquad \forall v \in \mathcal{V} \tag{3}
$$

with In(v) set of vertices which are the origin of all edges incoming to vertex v
Out(v) set of vertices which are the destination of all edges outgoing from v

Expression (3) verifies the Kirchhoff law and is applied only if flows converging to a vertex v can be interpreted as the same product flow: the various incoming edges of vertex v represent the various possibilities for delivering the product to the resource associated to the vertex. In this context, the calculation of the maximum flow through the graph G (or maximum throughput) is obtained by applying the famous Ford-Fulkerson algorithm [1] [5] or others analytical approaches [6].

2.3 New fundaments for assessing the network capacity

Nevertheless, this calculus becomes hard when graphs represent more complex
phenomena as operating resources which assemble components in intermediate
products (i.e. several flows of components converge on the resources), or operating
resources which perform multiple items during the same time interval, i.e. the
resources capacity is dependent on the product.

The first quoted problem refers to production processes based on bill of materials
with tree structures representing that different components types are required to
perform assemblies and multiple material flows income to resources. Basing the
calculation of the maximum throughput on the respect of the Kirchhoff law, graphs do
not model these situations. In case of flows convergence representing different
components (fig. 2a), the considered sub graph can be simplified to one vertex with
one outgoing weighted arc (u,v). Expression (4) replaces expression (3):

$$
f_{vw} = \min_{u \in \text{In}(v)} (f_{uv}) \quad \forall v \in \mathcal{V}, w \in \text{Out}(v) \quad (4)
$$

Besides, complex production processes should contain resources that (not
simultaneously) perform multi items, represented by multiple vertices $v \in \mathcal{V}_f$ ($\mathcal{V}_f \subset \mathcal{V}$ is
defined as the vertices subset associated to resource $R_f$, i.e. $v \in \mathcal{V} | d_{vr}=1$). We assume
that a constant capacity expressed on the edge outgoing from each $v \in V_r$ is not representative of real phenomena when production load on resource $R_r$ relative to a task completion reduces the remaining capacity useful in others tasks accomplishment.

<figure><img src="image_3.png" /><figcaption>Fig. 2 Complex phenomena modeled in graphs</figcaption></figure>

Detailed information concerning the coupling of capacities associated to any edge modelling an output flow from a resource $R_r$ should be kept on graphs to assess in the best way the maximum throughput. Considering that capacities on graph G are not always constants, depending on partial loads due to the various tasks execution on a same resource $R_r$, these variable capacities are dynamically calculated in accordance with any flow on graph describing an output material flow of this resource (fig. 2b). Capacities are updated every time the flows vary, according to the following relation:

$$c_{uv} = \sum_{t} l_{ut} \cdot \omega_{rt} / a_{uv} - \sum_{ge \in V_r - \{u\}} \sum_{h \in Out(g)} \sum_{t} \frac{l_{ut} \cdot \omega_{rt} / a_{uv}}{l_{gt} \cdot \omega_{rt} / a_{gh}} f_{gh} \quad \begin{array}{l} \forall u \in V, v \in Out(u), \\ r \in \{R | d_{ur} = 1\} \end{array} \quad (6)$$

### 3. A data aggregation methodology to assess a global production capacity

The proposed methodology based on graphs analysis should be applied recursively at an abstraction level n-1 in order to obtain an aggregate representation at level n. We introduce the notations $R_r^n$ (respectively $T_p^n$) which reference any resource r (respectively any task t) at the level n. The methodology uses graphs properties and solving algorithms previously mentioned to simplify the graph structure, when it is required to aggregate at the level n (graph G^n), any detailed network defined by a graph G^{n-1} at the level n-1. The aggregation process is decomposed in several steps:

- Step 1: any arc e=(u,v) is deleted if $\sum_{w \in In(u)} c_{wu} < c_{uv}$ or $\sum_{w \in Out(v)} c_{vw} < c_{uv}$.

- Step 2: based on the detailed graph G^{n-1} describing the resource and task network at the lower abstraction level, a vertices subset $V_r$ is defined,
considering that the subset $V_r$ represents one tasks subsequence (i.e a unique tree/road exists and connects the various nodes $v \in V_r$).

- Step 3: we define a resource $R_r^n$ (respectively $T_r^n$) which is the encapsulation of resources $R_r^{n-1}$ (respectively tasks $T_r^{n-1}$) associated to vertices $v \in V_r$. $V_r$ is then modelled by one vertex u in graph $G^n$ with one weighted outgoing arc $e=(u,v)$ such as its capacity is :

$$c_{uv} = \min_{x,y \in V_r} (c_{xy}) \qquad (6)$$

Notice that expression (6) is deduced from expression (4). $V_r$ can define graph structures representing parts of a production process with operating resources which assemble different components. Go to step 2 until no new set $V_r$ can be identified (any task subsequence is aggregated).

- Step 5: on the graph $G^{n-1}$, we search a vertices subset $V_r'$ such as this one represents alternative tasks subsequence (i.e $V_r'$ defines a acyclic sub graph $G_s$ in which multiple roads connect the source to the sink).

- Step 6: resources and tasks are aggregated as defined in step 2 and $G^n$ is partially completed. The capacity $c_{uv}$ is deduced from the application of the Ford-Fulkerson algorithm to the sub graph $G_s$. Go to step 5 until all sets $V_r'$ are treated.

Graph $G^n$ results from the reduction and simplification of the graph $G^{n-1}$, according to the calculation of aggregate capacities. The remaining structure of the graph is then mainly composed of vertices associated to resources performing multi items and should undergo a last reduction in order to keep one vertex associated to each performed product type. The global capacity of the network is then deduced from the graph $G^n$ by calculating the maximum throughputs according to capacities associated to the edges set. The aggregation process should be applied recursively.

# 4. Illustrative example

In this section, a SC example is defined to concretely apply the data aggregation methodology.

## 4.1 Description / modeling

The studied SC instance is composed of a two coupled multi-stage supply chains structure. Three products are performed: tables (product 1), small-sized shelves (product 2) and large-sized shelves (product 3). For reducing the complexity, transport capacities are supposed infinite, so that only production activities impact the global capacity assessment. Some details concerning the case study from which this
numerical example is extracted should be found in [3] [4]. The following graph G⁰ models the SC at the detailed level (Fig. 3a).

<figure><img src="image_4.png" /><figcaption>Fig. 3 SC modeling by graphs</figcaption></figure>

Arc capacities c<sub>uv</sub> mentioned on the graph G<sup>0</sup> result from equation (6) such as:

$$
\begin{align*}
c_{3,7} &= 15 - 1,5f_{4,8}; & c_{4,8} &= 10 - 0,67f_{3,7} \\
c_{9,12} &= 20 - f_{10,13} - 1,67f_{11,14}; & c_{10,13} &= 20 - f_{9,12} - 1,67f_{11,14}; & c_{11,14} &= 12 - 0,6f_{9,12} - 0,6f_{10,13}
\end{align*}
$$

According to the proposed methodology, graph G⁰ is aggregated leading to the elaboration of graph G¹ (fig. 3b) from which we can deduce the matrix C¹ defining the various capacities of arcs, assimilated to those of the supply chain (represented by a single resource) in relation with the different aggregate tasks (one task for one performed product). Considering a workload vector W=(w₁ w₂ w₃)ᵀ in which wₚ is the number of products Pₚ to be performed in the supply chain, we assume that (f₁,₄ f₂,₅)ᵀ = (w₂ w₃)ᵀ represents the order book for the resource R₁, and (f₃,₆ f₄,₇ f₅,₈)ᵀ = (w₁ w₂ w₃)ᵀ represents the order book for the resource R₂. The capacity of the aggregate resource (supply chain R) is then a vector, so that:

$$
\text{CAP}(R) = \begin{bmatrix} 20-w_2-1,67w_3 \\ \min(15-1,5w_3, 20-w_1-1,67w_3) \\ \min(10-0,67w_2, 12-0,6w_1-0,6w_2) \end{bmatrix} \quad (10)
$$

4.2 Exploitation of the aggregate capacity

Each component of CAP(R) is interpreted as the maximum number of each product the supply chain performs, if loads induced by others productions is known. The comparison of CAP(R) with values defined in W allows to verify if orders book W should be performed or not, during the considered time unit. Suppose that the workload vector is W=(4 4 2)ᵀ. Expression (10) leads to assess the supply chain capacity as CAP(R)=(12.67 12.00 7.20)ᵀ. We notice that W<CAP(R) (i.e. the value of every element of W is lower than the value of the corresponding element in
CAP(R)), showing that the supply chain may perform the orders book. If we now consider a vector $W=(10 \ 5 \ 4)^T$, the vector CAP(R) becomes $CAP(R)=(8.33 \ 3.33 \ 3)^T$. We can observe that 10 products $P_1$ are required to be performed and only 8 can be completed during the considered time interval (one time unit). If necessary, overloaded resources should then be defined by analysing the capacities on resources $R_1$ and $R_2$: $CAP(R_1)=(9 \ 6.67)^T$ and $CAP(R_2)=(8.33 \ 3.33 \ 3)^T$ shows that overload is only due to the second resource.

**5. Conclusion**

The assessment of aggregate capacities in complex resources networks is today a great challenge in developing rapid computational approaches able to show if new orders to perform in a supply chain may cause disruption or not. In this context, we propose first fundamentals of a data aggregation methodology, referring to graph theory. Nevertheless, the numerical example being simple, the approach feasibility must be proved through its application to more complex networks. Experiments must also be performed to determinate the inaccuracy of production loads calculations based on aggregated capacities knowledge, relative to results issue from a detailed complex planning process.

**References**

1. Bertin R., Bourrieres J.P., - A multi-level and parametric approach to Max-Flow analysis for networked manufacturing and logistics, Studies in Informatics and Control, Vol. 13, N.2, pp 119-134, 2004

2. Dominguez H., Lashkari R. S., Model for integrating the supply chain of an appliance company: a value of information approach. International Journal of Production Research, 01 June 2004, Vol. 42, No 11, pp 2113-2140

3. François J., Deschamps J.-C., Fontan G., and Bourrieres J.P., Assessing the impact of control architectures on Supply Chains performances, 4th IFIP International Workshop on Performance Measurement, Bordeaux, 27-28 june 2005.

4. François J., J.-C. Deschamps, G. Fontan, and J.P. Bourrieres, Collaborative planning for entreprises involved in different supply chains, IEEE SSSM'06 (International Conference on Service Systems and Service Management), Troyes (France), 25-27 october 2006

5. Ford L. R., Fulkerson D. R., Flows in networks, Princeton University Press, 1962.

6. Huang G. Q., Lau J. S. K, Mak K. L., The impacts of sharing production information on supply chain dynamics : a review of the literature. International Journal of Production Research, 2003, Vol. 41, No 7, pp 1483-1517