Multilayer Network-Based Production Flow Analysis

Essential information about the products to be assembled, parts to be manufactured, materials to be used, methods and techniques to convert the material to the required finished components, and manpower to operate the plant is usually available to a company, but rarely in an appropriate form for ease of digestion by the manager. In this section, we propose a network-based model to study the relationship between these elements.

As can be seen in Figure 1, the proposed network consists of a set of bipartite graphs representing connections between the sets of products $\mathbf{p}=\left\{p_{1}, \ldots, p_{N_{p}}\right\}$, machines/workstations $\quad \mathbf{w}=\left\{w_{1}, \ldots, w_{N_{w}}\right\}$, parts/components $\mathbf{c}=\left\{C_{1}, \ldots, C_{N_{C}}\right\}$, activities (operations) $\mathbf{a}=\left\{a_{1}, \ldots, a_{N_{a}}\right\}$, and their categorical properties (referred as activity types) $\mathbf{t}=\left\{t_{1}, \ldots, t_{N_{t}}\right\}$ and skills of the operators needed to perform the given activity $\mathbf{s}=\left\{s_{1}, \ldots, s_{N_{s}}\right\}$.

Figure 1 Illustrative network representation of a production system. The definitions of the symbols are given in Table 1.

The relationships among these sets are defined by bipartite graphs $G_{i, j}=\left(O_{i}, O_{j}, E_{i, j}\right)$ represented by $\mathbf{A}\left[O_{i}, O_{j}\right]$ biadjacency matrices, where $O_{i}$ and $O_{j}$ are used as a general representation of a sets of objects, as $O_{i}, O_{j}, \in\{\mathbf{p}, \mathbf{w}, \mathbf{c}, \mathbf{a}, \mathbf{t}, \mathbf{s}\}$.

The edges of these bipartite networks can represent material, energy or information flows, structural relationships, assignments, attributes, and preferences, and the edge weights can be proportional to the number of shared components/resources or time/cost needed to produce a given product (see Table 1).

Table 1 Definition of the biadjacency matrices of the bipartite networks used to illustrate how a production system can be represented by a multidimensional network.

The proposed model can be considered as an interacting or interconnected network, where the family of bipartite networks defines crossed layers. Since different types of connections between the nodes can be defined, the model can also be handled as a multidimensional network. Both of these models are the special cases of multilayer networks, which representation is beneficial, since the layers represent the direct connections defined by the bipartite graphs, while the interlayer connections help in term of the visualization of the complex system by arranging the corresponding nodes at the same place within the layers (as it is illustrated in Figure 2).

Figure 2 Visualization of the illustrative network as a multilayer/multiplex network highlights how the complex production system can be grouped into modules based on the “viewpoints” of the layers.

Table 3 Node types of the proposed network.

Table 4 Node edge matchings in the proposed network.

Table 5 The ADACOR predicates can be directly applied to define layers of the network (please note that we use the term activity to refer to operations).

3.1. From Problems of Production Analysis to Tools of Network Science

The main benefit of the multidimensional network model is that it provides a transparent and easily interpretable integration of process- and product-relevant information and as well as facilitating the tools of network science for production flow analysis.

The aim of production flow analysis (PFA) is to identify bottlenecks and groups in products, components, and machines to highlight possible improvements by redesigning the layout, forming manufacturing cells, scheduling the activities, or identifying line families of products based on clustering the sequences of machine usage.

Modules/part families are sets of machines and parts that are highly likely to work together in one group or be processed in a similar order. Since this definition is similar to the concept of modules in networks, it is assumed that fining modules in (multidimensional) networks can be considered as a useful heuristical approach of PFA.

1. Calculation of the loads and usage frequencies – identification of the bottlenecks
   
   1. Calculation of unknown dependencies
      
   2. Analysis of node and edge centralities
      
2. Group formation – clustering nodes and identifying communities
   
   1. Rank-order-based clustering
      
   2. Similarity-based clustering
      
   1. Calculation of node similarities of (projected) networks
      
   2. Clustering nodes and edges based on the calculated similarities
      
   3. Joining of clusters of different objects to form modules
      
   1. Finding modules in the (multilayer) network
      
3. Line formation – ordering modules to minimize sequential transfers
   
   1. Ordering based on the ratio of in/out degrees – Hollier's method
      
   2. Application of graph layout techniques
      

3.2. Projections of the Multilayer Network and Calculation of Undefined Connections

As Figure 3 illustrates, when relationships among the $O_i$ and $O_j$ sets are not directly defined, it is possible to evaluate the relationship between its $0_{i,k}$ and $0_{j,l}$ elements as the number of possible paths or the length of the shortest path between these nodes.

Figure 3 Projection of a property connection.

In the case of connected unweighted multipartite graphs, the number of paths intersecting the $O_0$ set can be easily calculated based on the connected pairs of bipartite graphs as

Conditional connections could also provide useful information in terms of PFA. To demonstrate the problem, let us have a look at Figure 4 which shows the network defined in. In this example, although operators $o_{1}$ and $o_{3}$ do not share any machines, the fact that machines $m_{1}$ and $m_{2}$ produce identical products results in the $\mathbf{A}\left[\left.O_{2}\right|_{\mathrm{O}_{1}}\left(O_{0}, O_{0}\right)\right]$ projection operators defining a connection between these operators.

$\begin{aligned}&\mathbf{A}\left[O_{0}, O_{1}\right]=\left[\begin{array}{llll}1 & 1 & 0 & 0 \\1 & 1 & 1 & 0 \\0 & 0 & 0 & 1 \\0 & 0 & 0 & 1\end{array}\right] \\&\mathbf{A}\left[O_{0}, O_{2}\right]=\left[\begin{array}{lllll}1 & 1 & 0 & 0 & 0 \\0 & 1 & 1 & 0 & 0 \\0 & 0 & 1 & 1 & 0 \\0 & 0 & 0 & 1 & 1\end{array}\right] \\&\left.\left(O_{0}, O_{0}\right)\right]=\left[\begin{array}{lllll}2 & 4 & 2 & 0 & 0 \\4 & 9 & 5 & 0 & 0 \\2 & 5 & 4 & 2 & 1 \\0 & 0 & 2 & 4 & 2 \\0 & 0 & 1 & 2 & 1\end{array}\right]\end{aligned}$

Figure 4 The advantage of complex conditional analysis using inner network.

Formally, in some cases, the $\mathbf{A}\left[\left.O_{i}\right|_{O_{k}}\left(O_{j}, O_{j}\right)\right]$ conditional projections might be of interest defined by

$\begin{aligned}\mathbf{A}\left[\left.O_{i}\right|_{\mathrm{O}_{k}}\left(O_{j}, O_{j}\right)\right]=& \mathbf{A}\left[\left(O_{j}, O_{i}\right)\right]^{\mathrm{T}} \times\left(\mathbf{A}\left[\left(O_{j}, O_{k}\right)\right] \times \mathbf{A}\left[\left(O_{j}, O_{k}\right)\right]^{\mathrm{T}}\right) \\& \times \mathbf{A}\left[\left(O_{j}, O_{i}\right)\right]\end{aligned}$

where the resultant $\mathbf{A}\left[\left.O_{i}\right|_{\mathrm{O}_{k}}\left(O_{j}, O_{j}\right)\right]$ network states that the $i$ th property set is analyzed based on the $\mathbf{A}_{\mathrm{O}_{k}}\left[\left(O_{j}, O_{j}\right)\right]$ inner network defined by the inner projection of the objects to the $j$ th set.

The projections are not applicable for all types of edges (e.g., the projection with precedence constraints does not result in interpretable networks). Generally, the projections calculate the number of paths between the nodes which number is directly interpretable (e.g., it can reflect the number of assignable operators for a given workstation).

To support these calculations, it is beneficial to utilise the adjacency matrix of the whole multiplex network obtained by flattening or matricization:

$\mathbf{A}_{M}=\left[\begin{array}{cccc}0_{1} & \mathbf{A}_{1,2} & \cdots & \mathbf{A}_{1, N} \\\mathbf{A}_{2,1} & 0_{1} & \cdots & \mathbf{A}_{2, N} \\\vdots & \vdots & \cdots & \vdots \\\mathbf{A}_{N, 1} & \mathbf{A}_{N, 2} & \cdots & 0_{N}\end{array}\right]$

where $A_{i,j}$ is used to represent the $A[O_i,O_j]$ biadjacency matrices of the $G_{i,j}$ bipartite graphs.

3.3. Calculation of Node Similarities

Node similarities can reveal useful information with regard to PFA, for example, if the similarities of the machines need to be defined based on how many common parts they are processing. When the machines are denoted as $k$ and $j$, and $S_{k}$ and $S_{j}$ as the sets of parts that are connected to these machines, the similarities of the machines can be evaluated according to the Jaccard similarity index:

$\operatorname{sim}(k, j)=\frac{\left|S_{k} \cap S_{j}\right|}{\left|S_{k}\right|+\left|S_{j}\right|-\left|S_{k} \cap S_{j}\right|}.$

The proposed network-based representation is also beneficial in similarity analysis. When $O_{0}=\mathbf{w}$ represents the set of machines/workstations and $O_{i}=\mathbf{c}$ represents the set of components, the $\mathbf{a}_{j, i}=1$ edge weight stored at the intersection of the $j$ th row and $i$ th column of the $\mathbf{A}\left[O_{0}, O_{i}\right]$ biadjacency matrix represents that the $i$ th type of component is built in at the $j$ th workstation and the degree of the $j$ th node, $k_{j}=\sum_{i} \mathbf{a}_{j, i}$ is identical to the cardinality of the $\left|S_{j}\right|$ set, which means how numbers of component types are built in at the $j$ th workstation.

We can generate two projections for each bipartite network. The first projection connects two $O_{o}$ nodes (in our case, two workstations) by a link if they are linked to the same $O_{i}$ node (same components). As Figure 5 illustrates, the $\left|S_{k} \cap S_{j}\right|$ cardinality is identical to the $j-k$ edge weight of the projected network which represents how many identical components are built in at the $k$ th and $j$ th workstation:

$\mathbf{A}_{\mathrm{O}_{0}}\left[O_{0}, O_{i}\right]=\mathbf{A}\left[O_{0}, O_{i}\right]^{\mathrm{T}} \times \mathbf{A}\left[O_{0}, O_{i}\right]$

Figure 5 Two different projections can measure how the neighboring node set generates connections among the objects.

The second projection connects the $O_{i}$ nodes (in our case, two components/parts) by a link if they connect to the same $O_{o}$ node (workstations), which projection represents how parts are connected by the machines:

$\mathbf{A}_{\mathrm{O}_{0}}\left[\mathrm{O}_{0}, \mathrm{O}_{i}\right]=\mathbf{A}\left[\mathrm{O}_{0}, \mathrm{O}_{i}\right] \times \mathbf{A}\left[\mathrm{O}_{0}, \mathrm{O}_{i}\right]^{\mathrm{T}}$

When the similarities of more layers are taken into account, multiple projections on the same machines can be defined by the weighted sum of their projections:

$\mathbf{A}\left[O_{0}, O_{0}\right]=\sum_{i} w_{i} \mathbf{A}\left[O_{0}, O_{i}\right] \times \mathbf{A}\left[O_{0}, O_{i}\right]^{\mathrm{T}}$

3.4. Identifying Modules for Group Formation

Communities are locally dense connected subgraphs in a network, so nodes that belong to a community have a higher probability to link to the other members of that community than to nodes that do not belong to the same community. Our key idea is that finding communities in (multilayer) networks of the proposed models can be used to solve group/cell formation problems of PFA. To formalize the cell formation problem, we utilized the modularity measure introduced by Newman and improved for bipartite graphs by Barber.

A module of the network consists of a subgraph whose vertices are more likely to be connected to one another than to the vertices outside the subgraph. Modularity reflects the extent, relative to a random configuration network, to which edges are formed within modules instead of between modules. The modularity can be determined for each community of a network (in PFA, this means the modularity of each production cell can be calculated). For a network with $n_{c}$ communities, the following modularity value is used to determine the modularity value of community $Q_{c}$ in terms of each $C_{c}$ community with $N_{c}$ nodes connected by $L_{c}$ links, $c=1, \ldots, n_{c}$ :

$Q_{c}=\frac{1}{L} \sum_{(i, j) \in C_{c}}\left(\mathbf{a}_{i, j}-\frac{k_{i} k_{j}}{L}\right)=\frac{L_{c}}{L}-\frac{k_{i} k_{j}}{L^{2}}.$

If the $Q_{c}$ modularity value of a cluster is a positive value, then the subgraph $C_{c}$ tends to be a community. The modularity of the full network can be evaluated by summing $Q_{c}$ over all $n_{c}$ communities, $Q=\sum_{c} Q_{c}$.

As can be seen, the definition of modularity perfectly fits the problem of manufacturing cell formation. Therefore, we propose a graph modularity maximization-based approach for this purpose. In this study, we adapt the Newman, LP-BRIM, and adaptive BRIM algorithms available in the BiMAT MATLAB toolbox.

To illustrate the applicability of this approach, Figure 6 visualizes a cell formation problem and how the extracted modules can be assigned as manufacturing cells.

(a) The rows and columns of the biadjacency matrix of the bipartite graph can be reordered to visualize the similarities of the modular graph layout

(b) After reordering/serialization of the biadjacency matrix, the modular structure of the problem is revealed

Figure 6 Modularity analysis of the $30 × 41$ machine-part benchmark example.

The efficiency of the formation of the cell can be evaluated based on $e$, the total number of activities; $e_{0}$, the number of exceptional elements that are excluded from the cells; and $e_{v}$, the number of zeros in the cells:

$\Gamma=\frac{e-e_{0}}{e+e_{v}}$

Table 6 compares the efficiencies of cell formation achieved by the proposed clustering and the modularity-based algorithms of cell formation with recently developed advanced goal-oriented optimization results in several benchmark problems of. As can be seen, modularity-based algorithms perform surprisingly well, the $\Gamma$ values (given as rounded parentages) are near to the optimized performances, and most importantly, the number of machine-part matchings outside of the modules ( $e_{0}$ values) and the number of modules are much smaller in almost all cases than the optimized reference solutions.

Table 6 Cell formation efficiency of bipartite modularity optimization algorithms. The $\Gamma$ values are given as rounded percentages.

Based on this success, several modularity optimization algorithms were applied. As will be demonstrated in the following section, the approach is also applicable when searching for modules in multiple layers by the multilayer InfoMap algorithm.

To provide a detailed and reproducible case study for production flow analysis, an open-source benchmark model of modular wire-harness production was developed. The details of the model are given in the Appendix. The multilayer network model of the production flow analysis problem is formed and analyzed in the MuxViz framework developed for the interactive visualization and exploration of multilayer networks [49]. The established network is depicted in Figure 2.

4.1. Similarity and Modularity Analysis

Figure 7 Multilayer network representing the details of the work of the operators (built-in components, $C$; zones of the activities, $Z$; skills, $S$; assignment of the operators to the workstations, $O$; and activity types, $T$) (see Table 1 for the detailed definition of the layers).

Although our network defines part families indirectly in layer $M$ and also groups of these activities (in layer $T$), it is interesting to observe how the multilayer network is structured and how the analysis of the modularity of the network can form part and activity groups. For this purpose, a multilayer InfoMap algorithm was applied.

The analysis yielded useful and informative results. 26 modules were identified. Although layer $\mathbf{M}$ which represents how the activities are grouped according to different products, this analysis was able to detect the modules of the products $\left(m_{1}, \ldots, m_{7}\right)$ in terms of the types of the activities $\left(t_{1}, \ldots, t_{16}\right)$. This result confirms that the analysis of the modularity of the proposed multilayer network model is useful in fine-tuning the existing part families based on multiple aspects representing the layers of the model.

To demonstrate how such information is useful in the early process-design phase to define technical modules, layer T of the C-Z-S-O-T multilayer network is shown in Figure 9. As can be seen, the most significant module is separated into six smaller groups by following the structure of layer $Z$ that defines in which zone the activities occur. The central role of the most frequent and widely distributed $t_{10}$ type of activity (wire-terminal attachment) is also highlighted.

Figure 9 Layer T of the network defines the types of activities. The six clusters formed in this layer reflect the effects of how the activities are distributed among the zones (defined by layer Z), which illustrates the benefit of the multidimensional network-based visual exploration of the production data.

4.2. Workload Analysis

The balancing of modular production is challenging due to the great diversity of products. Besides group formation, the analysis of the workloads is also an important task in production flow analysis. The proposed bipartite network-based model can be directly applied for this purpose as the biadjacency matrices of the layers result in simple calculations. To illustrate this applicability, let us consider the analysis of how well the production line is balanced. The equation $\mathbf{L}_{a}=\mathbf{M P}_{p}^{\prime}$ represents the activities of the production of the $p$th product (where $\mathbf{P}_{p}$ represents the $p$ th column of the $\mathbf{P}$ productmodule matrix). As these activities are assigned to the workstations as $\mathbf{L}_{w}=\operatorname{diag}\left(\mathbf{L}_{a}\right) \mathbf{W}$ and $\mathbf{T}^{\prime} \mathbf{L}_{w}$ represents the number of activities grouped by activity types and $\mathbf{T}^{\prime} \mathbf{C C}^{\prime} \mathbf{L}_{w}$ is the number of built-in components at the workstations, the total activity time at the workstations can be calculated by the following equation, where $\theta_{t}$ represents the elementary activity times given in the appendix:

$\mathbf{I}_{\mathrm{time}}=\left[\mathbf{T}^{\prime} \mathbf{L}_{w}, \mathbf{T}^{\prime} \mathbf{C} \mathbf{C}^{\prime} \mathbf{L}_{w}\right] \theta_{t}.$

As Figure 10 illustrates, the calculations above can be used to check how the process is balanced and how the complexity of the product influences the workloads of the workstations.

(a) Number of built-in components at a given workstation. The figure shows how the workload differs during the production of the base module $p_1$and the most complex product $p_{64}$

(b) Total station times during the production of the 16th product

Figure 10 The workloads (number of activities, built-in components, and total activity times) can be easily calculated based on the biadjacency matrices of the proposed model, which supports the balancing of the conveyor belt.

4.3. Analysis of the Flexibility of Operator Assignment

In the early $80 \mathrm{~s}$, suggested that organisational research should incorporate network perspective. In the early $90 \mathrm{~s}$, six themes (turnover/absenteeism, power, work attitudes, job design, leadership, and motivation) dominated the research of microorganisational behaviour. Recently, multilayer networks are becoming widely used in the analysis of social networks where people interact with each other in multiple ways like via mobile phone and emails. In this paper, we make the first attempt to integrate such analysis to the modelling and optimisation of production process.

For successful line balancing of wire-harness production, the skills of the operators influencing the speed of the conveyor belt should also be studied and handled. Dynamic job rotation requires efficient allocation of the assembly tasks while taking into account the constraints related to the available skills of the operators. Figure 11 shows the distribution of the required skills as a function of different product modules, $\mathbf{M}^{\prime} \mathbf{T S}$. As can be seen, the most in demand is the $s_{3}$ terminal-attaching skill, while $s_{6}$ is the visual testing skill which is required only once during production. The abilities of the operators can also be calculated, for example, $\mathbf{W}^{\prime} \mathbf{T S O}^{\prime}$ yields how many activities can be performed at a given operator-workstation assignment (see Figure 11(a)).

(a) Distribution of the required skills as a function of the modules of the product

(b) The number of activities that can be performed during a given operator-workstation assignment. The skills of the operators constrain the flexibility of line balancing

Figure 11 Analysis of the demand of skills and the flexibility of the operator-workstation assignment.

The presented analysis can be useful in designing the sessions of the operators by determining the components of critical skills and knowledge. Figure 12 shows the layers $S$ and $O$ of the network. Five groups of activity, skill, and operator nodes were identified with the help of multilayer modularity analysis. The smallest module contains the $t_{15}$ clip installation activity type which requires specialist skills.

Figure 12 Skill (S) and operator (O) layers define the network that can be used to determine elements of critical knowledge which is useful in terms of the design of training programs for the operators.

As can be seen, the skill $s_4$ can be considered a key piece of knowledge, because it is related to five types of activities. Operators $o_9$ and $o_{10}$ possess specialist knowledge, while $s_3$ consists of group-wise knowledge because it is the most related to the operators.

The presented analysis demonstrated that the analysis of the node degrees can identify the critically essential skills and resources. Skills that have small degrees in the $O$ layer can be considered as the knowledge of specialist, while skills with large degrees are quantified as group-wise knowledge. Skills that have no links at the $S$ layer are useless, while skills that have a small degree at the $O$ layer and high degree at the $S$ layer are critical, as this reflects that a small number of operators can be assigned to a large number of tasks which requires this knowledge.