BUS606: Operations and Supply Chain Management

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.