# Analytic Hierarchy Process and Multilayer Network-Based Method for Assembly Line Balancing
## 2 Problem Formulation
### Multilayer Network-Based Representation of Production Lines  
The proposed network model of the production line consists of a set of bipartite graphs that represent connections between operators, \(\mathbf{o}=\{o_{1},\ldots,o_{N_{b}}\}\); skills of the operators needed to perform the given activity, \(\mathbf{s}=\{s_{1},\ldots,s_{N_{b}}\}\); equipment, \(\mathbf{e}=\{e_{1},\ldots,e_{N_{b}}\}\); activities (operations), \(\mathbf{a}=\{a_{1},\ldots,a_{N_{b}}\}\); and the precedence constraints between activities, \(\mathbf{a}^{{}^{\prime}}=\left\{a_{1}^{{}^{\prime}},\ldots,a_{N_{b}}^{{}^{ \prime}}\right\}\). The relationships between these sets are defined by bipartite graphs \(G_{i,j}=(O_{i},O_{j},E_{i,j})\) represented by \(\mathbf{A}[O_{i},O_{j}]\) biadjacency matrices, where \(O_{i}\) and \(O_{j}\) denote a general representation of the sets of objects, such that \(O_{i},O_{j}\in\left\{\mathbf{s},\mathbf{e},\mathbf{a}^{{}^{\prime}},\mathbf{ a},\mathbf{o}\right\}\). The edges of these bipartite networks represent structural relationships; e.g., the biadjacency matrix \(\mathbf{A}[\mathbf{a},\mathbf{a}^{\prime}]\) represents the precedence constraints or \(\mathbf{A}[\mathbf{a},\mathbf{o}]\) represents the assignments of activities to operators. Moreover, the edge weights can be proportional to the number of shared components/resources or time/cost (see Table 1) [10]. As can be seen in Figure 1, these bipartite networks are strongly connected. The proposed model can be considered as an interacting or interconnected network [8], where bipartite networks define the layers. Since different types of connections are defined, the model can also be handled as a multidimensional network. As illustrated in Figure 2, when relationships between the sets \(O_{i}\) and \(O_{j}\) are not directly defined, it is possible to evaluate the relationship between their elements \(o_{i,k}\) and \(o_{j,l}\) in terms of the number of possible paths or the length of the shortest path between these nodes [10]. \begin{table}
\begin{tabular}{l l l} \hline \hline  & **Nodes** & **Description** \\ \hline
**W** & Activity (**a**)–operator (**o**) & Operator assigned to the activity \\
**S** & Activity (**a**)–skill (**s**) & Skill/education required for a category of activities \\
**E** & Activity (**a**)–equipment (**e**) & Equipment which is in use in an activity \\
**A\({}^{\prime}\)** & Activity (**a**)–activity (**a**\({}^{\prime}\)) & Precedence constraint between activities \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Definition of the biadjacency matrices of the bipartite networks used to illustrate how a multidimensional network can represent a production line. Figure 1: Illustrative network representation of a production line. The definitions of the symbols are given in Table 1.  
In the case of connected unweighted multipartite graphs, the number of paths intersecting the set \(O_{0}\) can be easily calculated based on the connected pairs of bipartite graphs as follows:  
\[\mathbf{A}_{O_{0}}[O_{i},O_{j}]=\mathbf{A}[O_{0},O_{i}]^{T}\times\mathbf{A}[O_{0 },O_{j}]\,. \tag{1}\]  
In the proposed network model, the optimisation problem is defined by the allocation of tasks that require the allocation of different skills and tools to an operator that might necessitate extra training, labour and investment costs. The main benefit of the proposed network representation is that these costs can be directly evaluated based on the products of the biadjacency matrices \(\mathbf{S}\) and \(\mathbf{W}\):  
\[\mathbf{A}[\mathbf{s},\mathbf{o}]=\mathbf{A}[\mathbf{s},\mathbf{a}]\mathbf{ A}[\mathbf{a},\mathbf{o}]=\mathbf{SW}. \tag{2}\]  
The resultant network \(\mathbf{A}[\mathbf{s},\mathbf{o}]\) represents how many times a given skill should be utilised by an operator, while its unweighted version \(\mathbf{A}^{u}[\mathbf{s},\mathbf{o}]\) models which skills the operators should have.