Solving generalized grouping problems in cellular manufacturing systems using a network flow model Open Access

The manufacturing industry is experiencing rapid growth driven by increasing demand across diverse product categories. This growth is accompanied by transformative changes that are fundamentally reshaping manufacturing paradigms. Cellular manufacturing systems (CMS), based on the philosophy of group technology (GT), have been recognized as a technological innovation in job shop or batch-type production systems to gain economic advantages similar to those of mass production systems. CMS is capable of producing small-to medium-sized batches of a wide variety of parts in a flow-line manner. The concept of CMS involves dividing the entire production system into smaller autonomous subsystems to improve shop floor control, material handling, tooling and scheduling. This approach leads to decreased setup times, in-process inventories and throughput times. To achieve this decomposition, it is necessary to identify subsets of parts with similar processing or design requirements so that each subset of parts can be processed by a single subsystem. In the context of GT, each such subsystem is termed a machine cell and each subset of parts is referred to as a part family. The identification of machine cells and part families is known as machine-component grouping and is the first step in the design of a CMS. This partitioning of machines and parts in a factory is achieved through the application of GT. The application of GT does not depend on the degree of automation in a factory and hence, GT can be applied at any level of automation, from manual production to fully automated systems.

The grouping problem varies depending on factors like the availability of information and the level of decision-making. In a simple grouping problem, each part has only one process plan and each operation of the process plan can be performed on only one machine. As a result, each part has only one process route. Here, the terms “process plan” and “process route” have different meanings. A process plan lists the operations required to complete a part, while a process route lists the machines to which the various operations are assigned. On the other hand, in a generalized grouping problem, each part has more than one process route. The objective of the grouping problem, in this case, is to identify a single process route for each part and determine the process route families and machine cells. The goal is to ensure that each machine cell is capable of handling at least one process route family.

The generalized grouping problem is a significant area of research within the field of network flow models, where the primary objective is to optimally assign groups under certain constraints. Since the pioneering work on grouping based on graph theory by Rajagopalan and Batra (1975), numerous graph-theoretic methodologies have been developed by researchers over the past few decades. These approaches have been thoroughly studied in the most recent literature, including applications in social networks and computer science (Majeed and Rauf, 2020). This problem is particularly important in contexts such as telecommunications, transportation and logistics, where efficient resource allocation is critical. The graph-theory-based methodologies can be classified into two main categories: graph decomposition (or partition) and network flow.

The graph decomposition method constructs a graph from the given parts' process routes. The nodes in these graphs correspond to either machines, parts or both. The arcs represent the associations between nodes and carry a weight representing some kind of dissimilarity or interaction between the nodes. Depending on the node type, three types of graphs can be constructed: machine graph, part graph and machine-and-part graph (Werner, 2020). These are described in Table 1.

To obtain machine cells and part families, graphs are successively decomposed into sub-graphs, ensuring minimal interaction among them or resulting in disconnected sub-graphs. Numerous studies have shown that there is no single strategy that works most effectively for obtaining part families and machine cells. For example, some research (Uddin and Shanker, 2002; Prafulla and Kulkarni, 2021) discussed the use of genetic algorithm (GA) to solve generalized grouping problems in CMS, demonstrating improvements in optimizing these groupings without pre-specifying the number of groups. In the network flow method, a network is constructed by creating two nodes for each machine or part. The nodes are connected by directed arcs and the weight on the arcs represents some kind of cost, indicating dissimilarity between the parts or machines. These formulations solve the grouping problem optimally without pre-specifying the number of groups. A pioneering work by Lee and Garcia-Diaz (1993) formulated the machine grouping problem as a capacitated circulation network for a simple grouping case.

Network flow algorithms have been successfully applied to various production planning problems, including the simple grouping problem. However, no work has been reported on solving the generalized grouping problem using network flow algorithms. In this paper, a methodology is presented that employs a hierarchical approach to solve the generalized grouping problem when process routes are given for each part. In the first stage, process route families are formed using a unit capacity minimum cost network flow model. In the second stage, a heuristic procedure and a quadratic assignment model are presented for machine cell formation and the assignment of process route families to these cells.

The remainder of the paper is structured as follows. Section 2 reviews the relevant research on grouping problems and network flow models. The problem environment considered for the model creation is explained in Section 3. The solution strategy is described in Section 4. The proposed network model for the development of process route (or part) families is presented in Section 5. Section 6 describes the development of machine cells and the assignment of part families to these cells. The application of the proposed model to a few numerical issues is demonstrated in Section 7. Finally, Section 8 presents the conclusions and recommendations for future research.

Extensive studies have been conducted based on the framework of network flow models, particularly in routing (Yan and Wong, 2009; Cova and Johnson, 2003), planning and scheduling (Rietz et al., 2016), production optimization (Lerlertpakdee et al., 2014), supply chain management and intelligent transportation (Hsu and Wallace, 2007; Rudi et al., 2016), inventory management and distribution (Hovav and Tsadikovich, 2015), social network analysis (Gomez et al., 2013), resilience assessment (Goldbeck et al., 2019; Yin et al., 2022), infrastructural interdependencies (Holden et al., 2013), water supply planning (Hsu and Cheng, 2002), strategic mine planning (Topal and Ramazan, 2012) and energy systems (Quelhas et al., 2007; Quelhas and McCalley, 2007). A number of graph theory-based studies on grouping problems have been published in the literature, where machines or parts are represented by the vertices of graphs and appropriately determined similarity coefficients are defined by the weights of the arcs. The grouping problem was first solved using graph theory by Rajagopalan and Batra (1975). Using the route cards of the parts, they developed a machine graph in which the vertices represented the machines and the edges represented Jaccard's similarity coefficients. Cells were identified as groups of vertices that were highly connected to one another.

For studying the optimization of cell formation, various algorithmic techniques have been used. Among these techniques, the hybrid genetic algorithm (GA) has been widely employed for machine-part grouping in CMS. The formation of machine groups and part families is a complex task in cellular manufacturing, which seeks to combine the fast production rate of flow lines with the flexibility of job shops. The integration of local search heuristics with GA, as proposed by Tariq et al. (2009), has demonstrated encouraging results in quickly obtaining optimal solutions, indicating the effectiveness of hybrid techniques in addressing real-world manufacturing challenges. Mak et al. (2000) proposed a GA to optimize cell development in manufacturing systems. Their approach provided practical insights into algorithmic techniques and strategies for optimization by dynamically adjusting parameters to maximize efficiency and reduce handling costs. Similarly, Salehi and Moghaddam, (2010) offered complex techniques and frameworks for performance evaluation, analyzing the implementation of GA to address cell formation problems. These methods have been further developed by hybrid GA proposed by James et al. (2007), demonstrating efficient optimization in practical situations.

The grouping problem was first solved by Lee and Garcia-Diaz (1993) as a circulation network flow problem. The idea is to group machines into cells so that each family of parts can be processed in a single machine cell. To achieve this, a directed graph for the machines is created and its network flow problem is solved. The solution to the network flow problem consists of one complete loop and several sub-loops, each loop corresponding to a machine cell. Compared to the p-median model, this approach is reported to have excellent potential for providing computationally efficient and optimal solutions for simple grouping problems. Cheng et al. (2019) developed generalized grouping strategies in coded caching and Garg and Arora (2018) developed fuzzy soft-set decision-making frameworks, demonstrating the flexibility of grouping techniques. These methods integrate expert preferences and efficiently manage uncertainty, offering powerful tools for decision-making. The use of grouping concepts in decision theory and computational problems is further illustrated by the grouping functions proposed by Bustince et al. (2012) and the generalized group testing procedures proposed by Malinovsky (2019). These approaches enhance efficiency and scalability across various fields. This thorough analysis highlights the usefulness and potential of network flow models in addressing a range of grouping problems.

Recent advances in graph-based and knowledge-driven methodologies have further enriched the landscape of manufacturing system design. Knowledge graphs, which represent entities and their relationships as structured semantic networks, have emerged as a powerful paradigm for integrating heterogeneous manufacturing data and enabling intelligent decision support. Lu et al. (2025) proposed a temporal knowledge graph reasoning method that fuses dynamic event embeddings with Hawkes process-based prediction for predictive maintenance of electromechanical equipment, demonstrating how graph-based representations can capture evolving relationships in complex industrial systems. Similarly, Su et al. (2025) developed a multi-layer knowledge graph architecture for digital twin systems in manufacturing processes, integrating a concept layer, a model layer and a decision layer to enhance predictive analysis and anomaly detection in aero-engine blade production. These works highlight the growing importance of graph-based formalisms beyond classical network flow in addressing modern manufacturing challenges. Digital twin frameworks integrate physical and virtual system representations to facilitate simulation, monitoring and optimization (Iliuţă et al., 2024; Liu et al., 2023). More recently, Cognitive Digital Twins have been proposed as an evolution of traditional digital twins, incorporating learning, reasoning and adaptive capabilities to support autonomous decision-making in complex industrial systems.

It is worth noting that various graph-based models exist for representing and solving manufacturing system problems, including Bayesian networks (BNs), Petri nets and knowledge graphs. Bayesian networks are particularly suited for modeling probabilistic dependencies and reasoning under uncertainty, making them valuable for fault diagnosis and quality prediction in manufacturing. However, BNs are fundamentally designed for probabilistic inference and do not naturally accommodate the assignment and flow-conservation constraints inherent in grouping problems. Similarly, while Petri nets excel at modeling concurrent and sequential processes, they are primarily oriented towards process flow analysis rather than combinatorial grouping optimization. The network flow model adopted in this study is specifically designed to solve the minimum-cost assignment problem, where the objective is to minimize total dissimilarity among process routes within families. With clearly specified supply and demand nodes, capacity limitations, and cost functions, network flow models' mathematical structure immediately translates to the generalized grouping problem's combinatorial structure, allowing for optimal or nearly optimal solutions using well-known algorithms. This structural alignment makes the network flow formulation inherently more suitable for the grouping problem than alternative graph-based models.

Furthermore, the concept of cognitive digital twins (CDTs) has garnered significant attention in the context of Industry 5.0, where integrating human expertise with machine intelligence is paramount. Su et al. (2024) proposed a three-layer cognitive digital twin model that leverages knowledge graphs to incorporate workers’ knowledge and experience into intelligent manufacturing processes, comprising an ontology layer, a knowledge layer and a cognitive layer for advanced analysis and model evolution. CDTs employ ontological representations and simulation models that share conceptual similarities with the graph-based formulations used in this study. Specifically, the network flow model developed here could serve as a foundational decision-support component within a CDT framework, where the process route family formation and machine cell assignment outputs could be integrated into a digital twin’s virtual model for real-time simulation, what-if analysis and dynamic reconfiguration of manufacturing cells. Such integration would enhance the CDT’s reasoning capabilities by providing optimal grouping solutions that can be re-evaluated as manufacturing conditions evolve, thereby supporting adaptive and human-centric manufacturing decision-making.

It is evident that network flow models have been successfully applied across various domains, including social networks, decision-making, industry and infrastructure, to ensure computational efficiency and practical application. These models provide robust frameworks for enhancing resilience, improving decision-making and optimizing complex systems. Consequently, they offer valuable insights for the development of a network flow model for the generalized grouping problem.

For the proposed network flow model, a generalized grouping problem is considered where each part has more than one process route. The input to the problem is a two-dimensional (0–1) matrix showing the requirement of machines for various operations of each process route. The entry value in the matrix is 1 if an operation of a process route requires a particular machine and 0 otherwise. The grouping problem involves selecting one process route for each part from the given alternatives and grouping them into process route families, each of which can be processed by a single machine cell. Several process route families can be processed by a machine cell. The objective is to minimize the distance (dissimilarity) among the process routes within a family. The proposed model is expected to result in machine cells with the minimum possible inter-cell movements.

We consider a problem situation where there are K parts and each part has a set of distinct process routes. Different process routes for a part generally require different sets of machines to complete the operations. In total, combining all the parts, there are N process routes. There are M machines of different types and a maximum of C cells are to be created. The objective is to minimize the inter-cell movements of parts and to maximize machine utilization.

It is important to note that the problem formulation assumes deterministic process routes, where each part’s set of feasible process routes and machine requirements are known with certainty. This assumption is adopted to establish the mathematical foundations of the network flow model and to demonstrate its optimality properties. The implications of relaxing this assumption to accommodate stochastic manufacturing environments are discussed in Section 8.

The proposed model solves the problem in a hierarchical manner. First, process route families are formed based on minimum dissimilarity among the members of each family using a network flow model. In the second stage, machine cells are formed and process route families are assigned to these cells simultaneously, with the objective of maximizing machine utilization. For machine cell formation and process route family assignment, a heuristic and a QAP formulation are proposed.

The mechanism of process route family formation is as follows. First of all, for each part, there is a source or supply node (k_s) and a sink or demand node (k_d). For each process route, there are two nodes, a and b and a directed arc (a, b). From each part source node, arcs go to the corresponding process route node a. All arcs coming to a part sink node come from the corresponding process route node b. It is obvious that only one process route must be selected for each part. Let part k have TPR(k) process routes. So, TPR(k)−1 routes are eliminated from consideration by including the corresponding arcs in directed paths from source to sink (k_s → i_a → i_b →k_d). The flow value on all process route arcs is constrained to 1. The supply at the source and demand at the sink are fixed at TPR(k)−1 for all parts. This results in exactly one process route, with no supply from the source for each part. However, since all process routes are constrained to have flow value 1, even the process route arcs getting no supply from the source node have to have the flow conditions satisfied. This is possible only if such unsatisfied arcs form cycles within themselves, which are nothing but process route families. Further, to encourage better formation of process route cycles, the arc costs from one process route to another are taken as the corresponding dissimilarity values between them, the total of which is to be minimized over the whole network. In this way, the network flow model tries to group similar process routes together. The calculations of dissimilarity values are described in Sub-section 5.1.

At the stage of machine cell formation and route family assignment, the machine requirements for the various process route families are evaluated. Machine cells are created based on these requirements. Some process route families may be assigned to a cell if their machine requirements are fully met by that cell. If the requirements do not match completely, the family will be assigned to a cell where most of its requirements are satisfied, which may result in inter-cell movements.

The following notations are used for the development of the network flow model for process route family formation and machine cell formation model.

i, j

= process route

k

= part

m

= machine

c

= machine cell

r

= process route family

K

= total number of parts

PR(k)

= set of process routes for part k

TPR(k)

= total number of process routes for part k =|PR(k)|

A

= set of process routes over all parts

N

= total number of process routes over all parts =|A| =$∑k=1KΤPR(k)$

M

= total number of machines

C

= maximum number of machine cells that can be formed

R

= total number of process route families

max_c

= maximum number of machines that can be assigned to a cell c

$ω(i,j)$

= cost of unit flow on arc (i, j)

$aim$

= ${1if process route i requires machine m for processing 0(irrespective of thenumber of times itis requiredotherwise$

u_mr

= usage factor for machine m in process route family r indicating the number of processes routes in a process route family r using machine m=$∑i∈raim$

$Zmc$

= ${1if machine m is assigned to cell c0otherwise$

$Yrc$

= ${1if process route family r is assigned to machine cell c0otherwise$

$f$ (x, y)

= flow from node x to node y

The proposed network flow model consists of three steps. The first step involves computing the pairwise dissimilarity between process routes, as described in subsection 5.1. The second step constructs the unit capacity minimum cost flow network, detailed in subsection 5.2. The third step identifies the process route families by solving the unit capacity minimum cost network flow problem, as described in subsection 5.3.

The pairwise dissimilarities between process routes are computed as follows:

The dissimilarity value between a pair of process routes is measured as the number of machines that are not common to them. Let d_ij be the dissimilarity between process routes i and j. The value of d_ij (dissimilarity) is an indicator showing the degree of dissimilarity between process routes i and j. The value gets smaller as the two process routes require more and more common machines for processing. The process route-machine matrix A = [a_im] (i = 1, …, N; m = 1, …, M) is used to calculate the elements d_ij; of the dissimilarity matrix D = [d_ij]. The Hamming metric, to calculate the distance between a pair of binary row vectors, is used to calculate the dissimilarity between two process routes of different parts as shown below:

For example, consider process routes 1 and 3, where the number of machines in route 1 is 7 and the number of machines for route 3 is 5, out of which 3 machines are common. Then the dissimilarity between the pair (1, 3) is taken as (total number of machines $−$ total number of common machines) = (5 + 7) $−$ (2 × 3) = 6. To illustrate the calculation of the total dissimilarity value for a process route family, let us consider a process route family having process routes 1, 2, 3 and 4. Now, one cyclic order for this family could be (1, 2), (2, 3), (3, 4) and (4, 1). The dissimilarity value for this cyclic order will be d₁₂ + d₂₃+ d₃₄ + d₄₁, where d_ij is the dissimilarity value between processes routes i and j. There will be 4! such cyclic orders (n! cyclic orders for n process routes) and some of them will have the same dissimilarity value because of the symmetric nature of the dissimilarity coefficients, d_ij = d_ji. The dissimilarity value for a process route family is taken as the minimum of total dissimilarity values amongst all cyclic orders.

The construction of the unit capacity minimum cost flow network is based on the work of Lee and Garcia-Diaz (1993), who proposed the network flow formulation for a simple grouping problem. The network is constructed using the N $×$ N dissimilarity matrix D obtained in subsection 5.1. The creation of nodes and arcs connecting the nodes and the assignment of weightage on arcs are carried out as follows:

Create K supply nodes designated as 1_s, 2_s, …, K_s and one node corresponding to each part (the subscript s denotes that it is a supply node). The supply capacity of the node k_s is taken as TPR(k)−1 units, i.e. one less than the total number of process routes of part k; k = 1, …, Κ.

Create K demand nodes designated as l_d, 2_d, …,K_d, again one node corresponding to each part (the subscript d denotes that it is a demand node). The demand requirement of node k_d is again taken as TPR(k)−1 units; k = 1,...,K.

Corresponding to each process route i, create a pair of nodes i_a and i_b. The two sets of nodes are designated as 1_a, 2_a, …, N_a and 1_b, 2_b, …, N_b; i = 1, …, N. These 2 N nodes are used as transshipment nodes, i.e. these nodes do not possess any supply capacity, nor do they have any demand.

Create arcs and assign a capacity-cost triplet [U, L, C] to each arc to indicate an upper bound on its flow (U), a lower bound on its flow (L) and the per unit cost of flow (C) respectively, according to the following rules.

• Rule I:

For each supply node k_s, k = 1, …, K and the corresponding transshipment node i_a, i $∈$ PR(k); create supply arcs directed from k_s to i_a, signifying that part k uses process route i. For example, arc (1_s, 1_a) indicates that part 1 uses process route 1 for its processing. Assign capacity-cost triplet [U, L, C] = [1, 0, 0] to all arcs (k_s, i_a).

• Rule II:

For each node pair i_a and i_b, i = 1, …, N; create transshipment arcs directed from i_a to i_b. The two nodes i_a and i_b, connected by a directed arc, represent a process route. For example, arc (1_a, 1_b) represents process route 1, arc (2_a, 2_b) represents process route 2 and so on. Assign capacity-cost triplet [U, L, C] = [1, 1, 0] to all arcs (i_a, i_b).

• Rule III:

For each node i_b, i $∈$ PR(k), k = 1, …, K and the corresponding node k_d, create demand arcs directed from i_b to k_d. The directed arc (i_b, k_d) signifies that part k uses process route i; for example, the directed arc (1_b, 1_day) indicates that part 1 uses process route 1 for its processing. Assign capacity-cost triplet [U, L, C] = [1, 0, 0] to all arcs (i_b, k_d).

• Rule IV:

For each node i_b and j_a, i $∈$ PR(k), j $∉$ PR(k), k = 1, …, K; create relational arcs directed from i_b to j_a and assign capacity-cost triplet [U, L, C] = [1, 0, d_ij). The cost of shipping one unit of flow from node i_b to node j_a is taken as the dissimilarity value between process routes i and j.

The network constructed for the problem environment described in section 4, according to the steps described above, is shown in Figure 1.

1. The upper and the lower bound on flow on transshipment arcs (i_a, i_b), i = 1, …, N is 1 unit. Thus, in accordance with the flow conservation, a node i_b can supply 1 unit of flow to either destination node j_a or to demand node k_d, i $∈$ PR(k), j $∉$ PR(k), k = 1, …, Κ.

2. If a part k has TPR(k) = n process routes, n units of flow are needed to satisfy the flow condition on the n transshipment arcs, say, (i_a, i_b), ((i $+$ 1)_a, (i $+$ 1)_b), … ((i $+$ n$−$ 1)_a, (i $+$ n$−$ 1)_b). However, according to the network construction, the supply node k_s can supply only TPR(k) $−$ 1 = n $−$ 1 units of flow, that is, to only n $−$ 1 of the transshipment arcs. The remaining 1 unit of flow required on the unsatisfied arc can be satisfied by including it either in a path with satisfied process route arcs of some other parts or in a cycle with unsatisfied process route arcs of some other parts. In general, such a cycle or path may involve more than one part and its process routes. The relational arcs (i_b, j_a) (i and j must not belong to the same part) are used to create these cycles or paths and the weightage assigned to each such arc (i_b, j_a) is the dissimilarity value between process routes i and j, namely, d_ij. In the framework of the proposed minimum cost network flow problem, the relational arc that has the minimum dissimilarity (i.e. cost of flow) will be chosen for creating the cycle or path and this is true for all other parts. Therefore, any optimal (or feasible) solution of the proposed minimum cost network flow problem will contain paths (from supply nodes to demand nodes) with flow value 1 or both paths and cycles with flow value 1. Two types of paths could be there. The first kind, direct path (k_s → i_a → i_b →k_d), includes only one process route, whereas the second kind, indirect path, includes more than one process route. The direct path does not contain any relational arcs, but the indirect path does.

3. The cost of flow on all arcs is zero except on relational arcs (i_b, j_a), i $∈$ PR(k), j $∉$ PR(k), k = 1, …, K; whose cost of flow is the dissimilarity value between process routes i and j, i.e. d_ij. Therefore, minimizing the total cost of flow in the network is equivalent to minimizing the total cost of flow on the relational arcs (i_b, j_a) with flow value 1, which, in turn, is equivalent to minimizing the total dissimilarity values among the process routes involved in creating the paths and cycles.

The objective function is to minimize the total cost of flow in the network and consists of four components: cost of flow on supply arcs, cost of flow on transshipment arcs, cost of flow on relational arcs and cost of flow on demand arcs. Assuming the linearity, these costs are computed as the product of flow rate $f$ (.,.) and cost of unit flow $ω$ (.,.). The four cost components can be written as follows:

The cost of flow on supply arcs, transshipment arcs and demand arcs will always be zero because their cost of flow is zero according to Rule I, Rule II and Rule IV, respectively. The cost of flow for the relational arcs, $ω$ (i_b, j_a), is taken as d_ij, the dissimilarity value between the two process routes i and j according to Rule III. Therefore, the objective function is reduced to:

1. Flow conservation at source nodes k_s

Flow emanating from these nodes must be equal to their supply capacities:

1. Flow conservation at nodes i_a

Since these are transshipment nodes, therefore, the incoming flow must be equal to the outgoing flow:

1. Flow conservation at nodes i_b

These nodes are also transshipment nodes. Therefore, the incoming flow must be equal to the outgoing flow:

1. Flow conservation at sink nodes k_d

These are the sink nodes. Therefore, the flow incoming to these nodes must be equal to their requirement:

1. Side constraints - only one process route arc on any path from supply to demand node

This constraint is used to ensure that the path from a supply node to a demand node with flow value 1 must include only one process route and thus will eliminate from the network any indirect paths, i.e. the paths from supply nodes to demand nodes with flow value 1 which include more than one process routes. It can be written as:

1. The integrality constraints for flow variables

The model formulated in Equations 2–8 is a 0–1 integer linear programming problem, which can be solved using any procedure designed for 0–1 integer linear programming problems. Except for constraint 7, all other constraints and the objective function conform to the standard network structure and can be solved using any minimum-cost network flow algorithm. However, due to constraint 7, a specialized network flow algorithm is required to solve this problem. In this work, CPLEX, a general mixed integer optimization package (version 22.1.0.0), is used to solve the problem. The output consists of binary (0–1) flow values for all arcs.

As stated in subsection 5.2 (observation 2), the network solution will contain cycles and paths (indirect paths) to satisfy the flow conditions on unsatisfied arcs. However, due to side constraint 7, the solution cannot contain any indirect paths, i.e. paths that include more than one process route and contain relational arcs. Therefore, the only way to satisfy the flow conditions on unsatisfied arcs is by creating cycles. The cost of flow on these arcs is the dissimilarity value between the two process routes connected by a relational arc. Since the objective function minimizes the cost of flow on relational arcs and only cycles can contain relational arcs, minimizing the total cost of flow on relational arcs is equivalent to minimizing the cost of flow on cycles. In other words, this means minimizing the dissimilarity values (which are the costs of flow for relational arcs) between the process routes included in the cycles. Generally, a cycle contains at least two process routes (each from a different part). These cycles will represent process route families in the context of GT and can be identified from the solution of the mathematical model described in subsection 5.2 by isolating the relational arcs with a flow value of 1. This identification of cycles is illustrated in Figure 2. The network shown in this figure represents a grouping problem with 4 machines and 4 parts (with a total of 8 process routes). To illustrate the identification of cycles, let the solution of the model have flow value 1 on relational arcs (2_b, 3_a), (3_b, 2_a), (6_b, 7_a) and (7_b, 6_a). From these, two cycles can be identified. The first cycle consists of the following four arcs:

The second cycle also consists of four arcs:

From these two cycles, two process route families can be identified:

1. Process route family 1 consists of process routes 1 and 4, corresponding to parts 1 and 2, respectively.

2. Process route family 2 consists of process routes 6 and 7, corresponding to parts 3 and 4, respectively.

The computational complexity of the proposed network flow model is governed by the dimensions of the resulting 0–1 integer linear programming (ILP) problem. For a problem instance with K parts, N total process routes across all parts and M machines, we characterize the model dimensions as follows. The network consists of 2K + 2N nodes: K supply nodes (k_s), K demand nodes (k_d) and 2N transshipment nodes (i_a and i_b for each process route). The number of arcs comprises four categories: N supply arcs (k_s → i_a), N transshipment arcs (i_a → i_b), N demand arcs (i_b → k_d) and relational arcs (i_b → j_a) where i ∈ PR(k) and j ∉ PR(k). The number of

Where, $n¯=NK$ is the mean number of process routes per part. Each arc corresponds to a binary decision variable. Note that the N transshipment arc variables are fixed at 1 (since the lower and upper bounds are both 1 by Rule II), leaving

The total number of constraints comprises five groups: K supply-flow conservation constraints (Eq. 3), N flow conservation constraints at nodes i_a (Eq. 4), N flow conservation constraints at nodes i_b (Eq. 5), K demand-flow conservation constraints (Eq. 6) and N side constraints (Eq. 7), yielding a total of 3N + 2K explicit constraints (excluding integrality constraints, which are handled implicitly by the solver).

Table 2 provides the exact model dimensions and computational performance for the two example problems. All experiments were conducted using IBM ILOG CPLEX 22.1.0.0 on a desktop computer with an Intel Core i7 processor and 16 GB RAM, running under Windows 10.

From a theoretical perspective, the standard minimum-cost network flow problem (without side constraints) can be solved in strongly polynomial time. Well-known algorithms include the successive shortest path algorithm with complexity O(n²m), the minimum mean cycle-canceling algorithm with complexity O(n²m³ log n) and the network simplex method, where n and m denote the number of nodes and arcs, respectively (Ahuja et al., 1993). Our formulation conforms to this standard structure in all respects except for side constraint (7), which couples the supply-side and demand-side flow variables for each process route, i.e. f(ks, ia) = f(ib, kd). This side constraint introduces a structure analogous to the “network flow with side constraints” class of problems. While such problems are NP-hard in general, the integrality of our formulation (with unit capacities) and the specific structure of constraint (7) often allow CPLEX to solve them efficiently via LP relaxation with branch-and-bound, as the LP relaxation of network flow problems naturally yields integer solutions for the network-structured portion of the constraints.

Regarding scalability, the number of relational arcs (and thus binary variables) grows quadratically with N in the worst case. For a problem with K = 100 parts and an average of 5 process routes per part (N = 500), the number of relational arcs would be approximately 500 × 495 = 247,500, yielding a model with roughly 248,500 binary variables and 1,700 constraints. While modern commercial ILP solvers such as CPLEX and Gurobi routinely solve problems of this scale (and significantly larger), we acknowledge that instances with thousands of process routes may require computational times that are non-negligible. To address such cases, three mitigation strategies are available:

1. LP relaxation exploitation: Since the constraint matrix is nearly totally unimodular (all constraints except Eq. (7) form a network matrix), the LP relaxation is expected to produce integer or near-integer solutions in most cases, significantly reducing the branch-and-bound search tree.

2. Decomposition: The problem can be decomposed by partitioning parts into clusters based on shared machine requirements before solving smaller sub-problems independently. This approach trades global optimality for computational tractability while preserving solution quality in practice.

3. Heuristic alternative: The heuristic procedure proposed in Section 6.2 does not require an ILP solver and operates with time complexity dominated by O(R² × M) for the merging steps, where R is the number of process route families and M is the number of machines. This is substantially less than the ILP formulation. In our experiments, the heuristic yielded solutions identical to the exact ILP formulation for both example problems, suggesting it is a reliable alternative for large-scale instances.

It is also instructive to compare the computational requirements of the proposed model with those of alternative methods for the generalized grouping problem. Genetic algorithm-based approaches (Uddin and Shanker, 2002; Tariq et al., 2009) typically require specifying population sizes, crossover/mutation rates and termination criteria and their convergence is not guaranteed to produce optimal solutions. The p-median model, used as a benchmark in Example II, requires pre-specification of the number of groups and solves a different optimization formulation. By contrast, the proposed network flow model provides provably optimal solutions to the process route family formation problem without pre-specifying the number of families and its solution time was negligible for both example problems tested.

For machine cell formation, we propose a QAP formulation and a heuristic procedure. The descriptions are given in the following subsections.

The QAP formulation assigns part families and machines to cells simultaneously. The inputs to the model are the maximum number of cells that can be formed, the maximum number of machines that can be assigned to a cell and the machine usage factors (i.e. the number of process routes in a particular family using a particular machine) for all process route (part) families. The objective of the formulation is to maximize machine utilization. The output of the model is the assignment of part families and machines to cells.

The objective of the model is to maximize machine utilization and can be written as:

1. Each machine is assigned to only one cell

1. Each process route family is assigned to only one cell

1. Maximum number of machines that can be assigned to a cell

The objective of the heuristic procedure is also to maximize machine utilization. It follows a hierarchical approach and consists of three steps. The first step combines process route families wherever possible. The second step assigns machines to the process route families. The third step merges process route families and machine cells wherever feasible within the system constraints. The inputs to the procedure are the maximum number of machines that can be assigned to a cell, the process route families and the machines they require. The details of the heuristic are as follows:

• Step-1. Combining the process route families

  • (1)

    Take a process route family r

  • (2)

    Check if the machines used by this process route family r are a subset or superset of the machines used by any other process route family. If the answer is yes, merge the two process route families; otherwise, go to 3.

  • (3)

    Repeat 1 and 2 for all route families till no merging is possible.

• Step-2. Assigning the machines to process route families

  • (1)

    Compute for each machine m the usage factor u_mr for each process route family r

  • (2)

    Assign machine m to a process route family r where u_mr is maximum, the ties being broken arbitrarily.

  • (3)

    Repeat 2 for all machines.

• Step-3. Merging the process route families and machine cells

Merge two process route families and the corresponding machine cells if there is some inter-cell movement between them, but only if the merging does not violate the cell size limit. Stop when no more merging is possible.

To evaluate the effectiveness of the proposed formulation, two benchmark datasets are selected from the literature on generalized grouping problems: one without exceptional elements (i.e. where disjoint groups exist) and the other with exceptional elements (i.e. where disjoint groups do not exist). The number of exceptional elements serves as a critical performance metric for cell formation effectiveness The nusmber of exceptional elements is used as a critical criterion for measuring the effectiveness of cell formation, it is widely used by researchers in generalized grouping theory.

The first problem shown in Table 3 is the incidence matrix. There are 5 parts with a total of 11 process routes and 4 machines. In the process route family formation stage, two cycles are identified.

The two cycles are shown in Figures 3 and 4, respectively. From the two cycles, two process route families can be identified.

1. Process route family 1 consists of process routes 2 and 7, corresponding to parts 1 and 3, respectively.

2. Process route family 2 consists of process routes 5, 9 and 11, corresponding to parts 2, 4 and 5, respectively.

In the machine cell formation stage, the machine utilizations u_mr for each process route family r are calculated and shown in Table 4.

From Tables 4 and it is obvious that none of the machines are utilized by more than one process route family and hence, two machine cells are easily identified as:

1. Machine cell 1 consisting of machines 2 and 4

2. Machine cell 2 consisting of machines 1 and 3

After rearranging the matrix according to the results obtained from the process route family formation and the machine cell formation stage, the resultant matrix is shown in Table 5.

The second problem is given in Table 6. This problem has 20 parts having a total of 51 process routes and 20 machines. In the process route family formation stage, seven cycles are identified as:

The seven cycles are shown in Figures 5–11.

From the seven cycles shown in Figures 5–11, seven process route families can be identified as:

1. Process route family 1 consisting of process routes 2, 6 and 11 corresponding to parts 1, 3 and 5 respectively.

2. Process route family 2 consisting of process routes 30, 33 and 36 corresponding to parts 11, 12 and 13 respectively.

3. Process route family 3 consisting of process routes 49, 50 and 51 corresponding to parts 18, 19 and 20 respectively.

4. Process route family 4 consisting of process routes 4 and 8 corresponding to parts 2 and 4 respectively.

5. Process route family 5 consisting of process routes 41 and 47 corresponding to parts 14 and 16 respectively.

6. Process route family 6 consisting of process routes 44 and 48 corresponding to parts 15 and 17 respectively.

7. Process route family 7 consisting of process routes 12, 17, 21, 23 and 28 corresponding to parts 6, 7, 8, 9 and 10 respectively.

In the machine cell formation stage, applying machine cell formation heuristic, five machine cells are obtained with only one exceptional element. These results are same as those obtained by solving the QAP formulation for machine cell formation:

1. Machine cell 1 consisting of machines [1, 7, 9, 12]. Process route families as-signed to it are 1 and 4 which contain process routes [2, 4, 6, 8, 11].

2. Machine cell 2 consisting of machines [2, 5, 6, 16, 19). Process route family assigned to it is 7 which contains process routes [12, 17, 21, 23, 28].

3. Machine cell 3 consisting of machines [3, 8, 11, 18]. Process route family assigned to it is 2 which contains process routes [30, 33, 36].

4. Machine cell 4 consisting of machines [10, 14, 17, 20]. Process route families assigned to it are 5 and 6 which contain process routes [41, 44, 47, 48].

5. Machine cell 5 consisting of machines [4, 13, 15]. Process route family assigned to it is 3 which contains process routes [49, 50, 51].

After rearranging the process route-machine incidence matrix, the resultant matrix is shown in Table 7. The present model yields one exceptional element, whereas the p-median formulation yields three exceptional elements. For comparison, the results obtained from the p-median model are shown in matrix form in Table 8.