The methodology to model systems as graphs or networks already exists for a long time. The availability of information technology and computational power has led to a renaissance of the network modeling approach. Scientists have collected data and started to create huge models of complex networks from various domains. Manufacturing and logistics benefits from this development, because material flow systems are predetermined to be modeled as networks. This chapter revisits selected advances in network modeling and analysis in manufacturing and logistics that have been achieved in the last decade. It presents the basic modeling concept, the transition from static to dynamic and stochastic models, and a collection of examples how network models can be applied to contribute to solving problems in planning and control of logistic systems.
Hinweise
Till Becker was affiliated to LogDynamics until 2018 as Head of the Research Group Production Systems and Logistics Systems at the University Bremen, Germany
1 Introduction
Since the beginning of the division of labor, manufacturing processes have been split up in different tasks. These individual tasks have their own tools, materials, and places. To exploit the advantages of this type of organization of a manufacturing process, a proper planning and control of all involved aspects is vital. This chapter focuses on a manufacturing system’s underlying structure, i.e., the pattern of the material flow. Such a pattern can be found on various levels of detail. In all cases, it is a network of entities connected by material flow. This can be, e.g., a network of machines on a shop floor or a network of suppliers, manufacturers, and retailers in a supply chain.
We present a retrospect on the development of a deeper understanding of complex networks in manufacturing and logistics throughout the last decade around the work of the Production Systems and Logistic Systems group within the Research Cluster for Dynamics in Logistics at the University of Bremen, Germany.
Anzeige
2 Complex Networks in Manufacturing and Logistics
2.1 Modeling of Complex Networks
Systems of interacting or connected entities can be modeled as a graph (G), which consists of a set of vertices (V ) connected by a set of edges (E), such that G = (V, E). Another widely used nomenclature calls these system networks, composed of nodes connected by links. In general, there is no difference in the meaning of the two variants and they can be used synonymously. Although the concept of graphs is known in mathematics since centuries, the modeling of large-scale systems as graphs has not been feasible for a long time due to the required effort to manually gather data, draw the graph, and perform any type of calculation for graph-based algorithms.
The pioneering research in complex networks has covered network models from various domains, such as social networks, biological networks, and computer networks (see, e.g., Albert and Barabási 2002; Boccaletti et al. 2006). The researchers have investigated the structure of complex networks, their properties, and their formation. A main finding throughout the years was the fact that network models, although coming from different domains, share common properties with regard to their structure.
The transfer and application of complex network theory to the manufacturing and logistics domain began a decade ago with the works of Vrabič et al. (2013) and Becker et al. (2014). The early contributions demonstrate how the material flow in a manufacturing system can be converted into a network model. Network modeling is based on material flow data, which can be collected as a byproduct from shop floor control systems. Such data consists of a list of all available machines on the shop floor and a collection of records documenting the individual material flow events. Each record contains at least the manufacturing order ID, the machine that processed a certain operation, as well as a timestamp. An algorithm can be used to build the network model by creating the sets V and E (Becker et al. 2014). The network nodes are represented by the machines on the shop floor. The set of edges is filled by linking each record with its consecutive record from the same manufacturing order: if an item from the same manufacturing order is first being processed on machine A, and the next timestamp is an operation on machine B, then a link A → B is added to E.
Figure 1 displays two network models created by Becker et al. (2014). Both were created in the exactly same fashion using the algorithm presented above. However, due to the differences in the handling of the material flow in the two systems, two very distinct network models were obtained. Figure 1a shows the material movements on a shop floor during the manufacturing of machine parts, whereas Fig. 1b illustrates the flow of items in process industry with distinct groups of machines in clusters.
Fig. 1
Two network representations of the material for two different manufacturing scenarios created with data from manufacturing execution systems. (a) Network model of a shop floor production of machine parts. (b) Network model from process industry
×
Anzeige
2.2 The Structure of Manufacturing Networks and Its Impact on Material Flow
2.2.1 Comparison of Manufacturing Networks to Other Flow-Oriented Networks
A large part of the research work dealing with complex networks in manufacturing either discovers structural characteristics of those networks or investigates the relation between structural network characteristics and the performance of the material flow. Network models from other domains have already been described in detail, such as engineered networks from communication (Braha and Bar-Yam 2006), urban traffic (Lämmer et al. 2006), or supply chains (Meepetchdee and Shah 2007), but also evolved network structures like river networks (De Menezes and Barabási 2004) or predator–prey relations in ecosystems (Williams et al. 2002).
Therefore, a first approach was to compare the properties of manufacturing networks and other flow-oriented networks. The comparisons covered traffic networks (Becker et al. 2011) as well as metabolic networks (Becker et al. xxxx, 2011). These network types were chosen for comparison, because they also represent a structure in which a flow of items needs to be managed in order to fulfill the system’s objectives. Networks of metabolic reactions in cells in particular can be seen as “factories,” which transform incoming items into final products via enzyme reactions. The main findings were that, on the one hand, all these network types exhibit strong structural similarities when observing the distribution of network characteristics, such as degree of connectivity. On the other hand, flow simulations on these networks showed a distinct behavior. Metabolic networks tend to have a more evenly distributed flow, whereas manufacturing networks tend to go toward a hub-and-spoke architecture with a small number of highly frequented nodes.
2.2.2 The Relation Between Structure and Performance
As a consequence of the investigation of different networks from various domains, researchers have hypothesized that there is a relation between the static structure of a network and its performance regarding the material flow. The rationale behind this is the idea that networks are designed (or in the case of biological or ecological networks have evolved) in a way to support the material flow processes. In order to quantify structural properties of networks, a variety of network figures has been developed (see, e.g., Boccaletti et al. 2006). Most researchers focus on centrality measures, which indicate how strong the nodes in a network are connected with each other. The most frequently used centrality measures are Degree-Centrality, Betweenness-Centrality, Closeness-Centrality, and Eigenvector-Centrality (Becker and Wagner 2016). Centrality measures can be determined for individual nodes or as an average over all nodes in the network (Becker et al. 2012; Omar et al. 2018). A key observation by Becker et al. (2012) is the fact that there is a nonlinear relation between the degree of connectivity in a material flow network and its performance. Figure 2 shows the results from a simulation study. A material flow simulation was carried out in a selection of networks. These networks were constructed from real-world data following the procedure described in Sect. 2.1. The work in process (WIP) served as key performance figure. It indicates how much work content is present in the system, e.g., waiting in queues or being currently processed, and should be kept on a low level. The obtained results show that there is an ideal degree of connectivity in the network structure which allows to keep the WIP low. Lower connectivity and increased connectivity lead to an increase in WIP.
Fig. 2
The graph shows the relation between the average degree of a network and the work in process obtained from a series of material flow simulations. The results indicate that a specific degree of connectivity in a material flow network is best suited to prevent the buildup of queues (Becker et al. 2012)
×
Beber and Becker (2014) extended the scope beyond individual nodes and investigate patterns in the shape of three-node subgraphs, also known as network motifs. Their findings indicate that the motif signature can serve as a “fingerprint” to distinguish different manufacturing networks from each other.
Other approaches make use of network centrality metrics to identify bottleneck work stations in a manufacturing system (Blunck et al. 2014). Although the assessment of the actual material flow in a network sill provides more reliable information whether a work station is a bottleneck or not, the centrality of a node in a network can also be used to identify those bottlenecks. The advantage of the network measures is their availability. Even in early planning stages, when material flow data is either not yet available or can only be acquired with the help of computer simulations, the bottleneck situation in a manufacturing system can already be assessed using network measures.
Another application-oriented approach using centrality measures is able to identify key machines in a manufacturing system based on network measures (Becker and Wagner 2016). A selection of centrality measures were used to identify the machines that have the highest impact on material flow performance. The results emphasized the applicability of certain network centrality measures for this purpose. Moreover, it could be shown that not all centrality measures are suited to identify important nodes in manufacturing systems, due to the specific mechanics of flow in these systems in comparison to other networks.
2.3 Dynamic Processes on Material Flow Networks
The previous modeling approach of networks basically considers the static description of material flow and information flow structures, which effectively means that network elements do not change over time. Applied to material flow systems, it would mean there is no change in material flow level at any time. However, recent studies suggest that the structure of a material flow network changes as a result of events or changing circumstances (e.g., passing a job to the next work station or failure of work stations) over a specific period of time (see, e.g., Beber and Becker 2014; Vrabič et al. 2013). Consequently, it might be useful to consider such dynamic processes for specific applications.
Figure 3 shows potential structural changes in networks. As indicated earlier, all these changes are, among other things, triggered by additional work systems, machine breakdowns, changes in product mix, etc. In real material flow systems, a combination of all these events leads to a variety structural changes during a certain observation period. For analytical purposes, the entire observation period can be divided into a number of time windows. If there are any active nodes and edges within a defined time window, a network instance is created. This way, structural changes can be observed and linked to various events. Although the length of each time window can be selected freely, it has a significant impact on the structural changes. For example, for shorter time windows, the average values of different key network figures display stronger variation from one time window to another, whereas for longer time windows the deviations between time windows are lower (Wagner and Becker 2016).
Fig. 3
The structural changes affect in particular both network elements (i.e., nodes and edges). It is therefore possible that nodes and edges disappear or join the network over time. Moreover, the intensity of the edge weights may vary over time (Wagner and Becker 2016)
Network modeling in manufacturing and logistics has seen a number of advances in the recent decade. The first simple, yet effective modeling approach based on material flow data has been presented in Sect. 2.1. The consideration of the development of networks over time was discussed in Sect. 2.3. A further development in network modeling in manufacturing was the introduction of stochastic models. In particular, the Stochastic Block Model (SBM) allows for a prediction of future states in a manufacturing system (Funke and Becker 2020). The motivation behind the application of SBMs as a tool in manufacturing systems modeling is the fact that many material ïňĆow systems consist of elements that can be grouped into clusters of similar objects in terms of their role in the material flow, e.g., manufacturing cells. In a nutshell, an SBM is a network model in which groups of similar nodes (like clusters) are seen as structural equivalent. Instead of explicitly modeling the links between nodes, the general probability of two nodes from two groups being connected is given (see Fig. 4).
Fig. 4
Minimal model of an SBM: (1) the network model is transformed into an adjacency matrix, (2) the nodes are grouped into blocks with similar connections, and (3) the result is a block matrix with probabilities indicating the likelihood of two nodes from corresponding blocks being connected
×
Creating an SBM is not as straightforward as creating a simple network model as presented in Sect. 2.1. The modeling requires the selection of the desired type of SBM and an appropriate inference method to derive the actual model from the material flow data. Funke and Becker (2019) have investigated, compared, and evaluated a variety of SBM variants and inference methods to facilitate the selection process.
Funke and Becker (2020) were then able to demonstrate how an SBM can be applied to perform link prediction. Due to the stochastic nature of the model, it is possible to retrieve a probability of two nodes being connected (or not being connected) in the future. Consequently, managers and planners will be enabled to make design decision regarding the planning and control of material flow in their manufacturing systems.
4 Identification of Autonomous Clusters Considering the Topological Setting
Nowadays, companies are faced with constantly increasing complexity due, for example, to shorter product life cycles, increasing customer requirements, and high fluctuations in demand. This requires novel control solutions. The massive technological improvements over the past years additionally support the transformation toward autonomous control approaches. Previous research activities in the context of autonomous control are primarily limited to control algorithms and technologies. However, most companies are facing the challenge not only to select appropriate control algorithms and to adapt the new technologies but also to decide how the structure of a system, i.e., the network topology, can support their transformation toward decentralized autonomous control. From a topological perspective, modularization, which subdivides a system into small units with autonomous decision-making, seems to be a promising approach (Gronau and Theuer 2011; Mourtzis and Doukas 2013). The resulting question is which work systems should form a unit and act autonomously?
A first attempt to identify highly interacting work systems, in order to be able to subsequently merge them into autonomous units—here called clusters, was made by Vrabič et al. (2012). Their approach is based on the assumption that edges in networks represent the intensity of material flow between the corresponding nodes. Consequently, nodes inside a cluster should be strongly connected, but only loosely connected to other nodes outside the cluster. In recent years, a number of clustering methods have been developed. Some methods have been tested to determine their suitability for the identification of autonomous clusters. Subsequently, the proposed approach was extended to include the dynamic development of the manufacturing system over time (Becker and Wagner 2015; Becker and Weimer 2014). To this end, they evaluated the consistency of clusters over time (for an example, see Fig. 5). Tracking the evolution of each cluster can help identify robust clusters, which are therefore particularly suited to serve as autonomous clusters. Furthermore, in accordance with the results of Lancichinetti et al. (2010) that real-world networks of the same category are identical with respect to their cluster structure, Wagner and Becker (2016) were able to show that this is also true for material flow networks for relatively shorter time windows (see Fig. 6).
Fig. 5
Resulting network representations for three different time windows in order to reveal similar cluster pattern. Within the first time window, two clusters have been identified and only one cluster in the following time windows. The nodes 6, 29, 30, and 31 are represented in all time windows (Becker and Wagner 2015)
Fig. 6
Increasing the length of time windows results in an increasing number of nodes and edges. As a result, this leads to a lower number of clusters, which are in turn larger in size. The results for shorter time windows are mostly similar for both datasets (a and b)
×
×
5 Synthetic Material Flow Networks with a Built-In Cluster Structure: A Random Walk-Based Approach
In order to be able to test the proposed clustering approach for the identification of autonomous structures in networks of different typologies, appropriate data is needed. However, due to a lack of reliable data with different cluster structures, the necessity arises to generate well-characterized synthetic material flow networks that allow extensive testing in simulation studies. Synthetic networks are characterized by the fact that they are generated randomly, but within a framework of rules. To generate graphs with a certain built-in cluster structure, a random walk-based approach can be applied, as presented in Wagner and Becker (2017, 2018). With this approach, different job routing patterns are modeled as random walks.
A random walk is considered as a stochastic process which results in a sequence of randomly visited nodes (Lovász 1993). Consequently, random walks do not require any global network information. Moreover, they can help to understand the underlying routing mechanics of systems and are therefore able to reveal specific characteristics like cluster structures in networks (Schaeffer 2007). This is explained by the fact that random walks tend to get trapped in clusters. Hence, it is not the random walks themselves that create networks with certain characteristics, but they need a network as a basis for their movements. Such networks are also referred to as underlying networks (Rosvall and Bergstrom 2008). The topological characteristics of such a network have been used to guide a random walk. To be able to create networks with various built-in cluster structures, not only the parameters of the random walks have to be defined but also those of the underlying network.
After applying this approach, it can be observed how random walks change the number of clusters, the cluster sizes, and the degree of connectivity of clusters given in the underlying network. The main result shows that the random walk-based routing is well suited to map the cluster structures of a number of tested underlying networks (Wagner and Becker 2018). This gives the underlying network a leading function. In future, this approach can be extended to create networks with other topological patterns.
6 Summary and Outlook
Research on complex networks has become visible across many different disciplines throughout the recent years. With regard to the flow of material, goods, and information in supply chains, traffic, and on shop floors, network models are a powerful tool in manufacturing and logistics research. This chapter has shown the foundations of network modeling in this domain and presented a selection of more detailed research activities and application-oriented approaches. It became apparent that, on the one hand, many network-related insights from physics, biology, or social sciences can be transferred to manufacturing and engineering. On the other hand, material flow in manufacturing has also specific properties, which are distinct from the flow of traffic on roads or the flow of messages in social networks. This is why it is essential to continue the research on complex networks in manufacturing and logistics.
The direction for future research should be aligned with the application opportunities in industry. More and more companies will collect massive amounts of system data in the context of Industry 4.0 and thus will be able to make use of network modeling. The inclusion of Artificial Intelligence (AI) methods in the processing of network data can further increase the quality of network models. Therefore, the so far developed methodologies should be transferred into practical applications for decision-making in planning, operation, and control of logistic systems. Figure 7 summarizes the development of network research in manufacturing and logistics.
Fig. 7
Network modeling in manufacturing and logistics has emerged from the application of graph theory in the information age. Initially, researchers have concentrated on modeling and description of logistic networks. Over the years, the research has evolved into a multitude of methods for description, design, and prediction of networks. Future research should be focused on creating industrial applications and on the inclusion of additional data sources and AI methods
×
Acknowledgements
The authors and the presented work were partially funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation), grant numbers BE 5538/2-1 and BE 5538/3-1, as well as by the Institutional Strategy of the University of Bremen, and funded by the German Excellence Initiative.
Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.
The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
