We study stability properties of interconnected hybrid systems with application to large-scale logistics networks.
Hybrid systems are dynamical systems that combine two types of dynamics: continuous and discrete. Such behaviour occurs in wide range of applications. Logistics networks are one of such applications, where the continuous dynamics occurs in the production
and processing of material and the discrete one in the picking up and delivering of material. Stability of logistics networks characterizes their robustness to the changes occurring in the network. However, the hybrid dynamics and the large size of the network lead to complexity of the stability analysis.
In this thesis we show how the behaviour of a logistics networks can be described by interconnected hybrid systems. Then we recall the small gain conditions used in the stability analysis of continuous and discrete systems and extend them to establish input-to-
state stability (ISS) of interconnected hybrid systems. We give the mixed small gain condition in a matrix form, where one matrix describes the interconnection structure of the system and the second diagonal matrix takes into account whether ISS condition for a subsystem is formulated in the maximization or the summation sense. The small gain condition is sufficient for ISS of an interconnected hybrid system and can be applied to an interconnection of an arbitrary finite number of ISS subsystems. We also show an application of this condition to particular subclasses of hybrid systems: impulsive systems, comparison systems and the systems with stability of only a part of the state.
Furthermore, we introduce an approach for structure-preserving model reduction for large-scale logistics networks. This approach supposes to aggregate typical interconnection patterns (motifs) of the network graph. Such reduction allows to decrease the number of computations needed to verify the small gain condition.
Contents
Introduction
1 Mathematical models of logistics networks
1.1 Notation
1.1.1 Logistics network
1.1.2 Vectors and matrices
1.1.3 Graphs.
1.1.4 Notions from control theory
1.1.5 Dynamical systems and their stability
1.2 Review of the known modelling approaches
1.2.1 Discrete deterministic systems
1.2.2 Continuous deterministic systems
1.2.3 Hybrid deterministic systems
1.2.4 Stochastic models
1.3 Comparison of the modelling approaches
2 Stability of interconnected hybrid systems
2.1 Interconnected hybrid systems
2.2 Stability notions
2.2.1 Input-to-state stability (ISS)
2.2.2 ISS in terms of Lyapunov functions
2.3 Gains
2.3.1 Gain operator
2.3.2 Mixed small gain condition.
2.3.3 From summation to maximization
2.4 Stability conditions
2.4.1 Small gain theorems in terms of trajectories
2.4.2 Construction of ISS-Lyapunov functions for interconnected hybrid systems
2.4.3 Systems with stability of only a part of the state
2.4.4 Impulsive dynamical systems
2.4.5 Comparison systems
3 Model reduction approach for large-scale networks
3.1 Gain model
3.2 Aggregation rules
3.2.1 Aggregation of sequentially connected nodes
3.2.2 Aggregation of nodes connected in parallel
3.2.3 Aggregation of almost disconnected subgraphs
3.2.4 Notes on application of the aggregation rules
4 Conclusion and outlook
Acknowledgements
First, I would like to express my deep gratitude to my supervisor Priv. Doz. Dr. Sergey Dashkovskiy for his extensive support in academic and non-academic life, for the useful advices in proving and presentation of mathematical results, for his optimism and trust.
I also want to thank Prof. Dr. Fabian Wirth for valuable discussions and advices that led to interesting results and added rigidity in research.
I am grateful to my school teachers Bogdan Shpitalenko and Rostislav Smirnov that gave me inspiration in mathematics.
I am also thankful to my colleagues Lars Naujok and Andrii Mironchenko that have kindly agreed to read the earlier version of this thesis and for the insightful discussions and support. Besides that, it was a very nice time to be a colleague of them.
I would also like to thank the other colleagues from the work group "Mathematical Modelling of Complex Systems", from the Center for Industrial Mathematics at the University of Bremen and from the project "Stability, Robustness and Approximation of Dynamic Large-Scale Networks - Theory and Applications in Logistics Networks" for the useful discussions, support and nice work atmosphere, especially Prof. Dr. Hamid Reza Karimi, Thomas Makuschewitz, Michael Schönlein and Christoph Lahl.
And my deep gratitude to my parents Maria and Victor, brothers Alexander and Ivan, and my dear wife Tatiana for their great support, faith and encouragement.
I am also thankful to the Volkswagen Foundation for the financial support (Project Nr. I/82684).
Abstract
We study stability properties of interconnected hybrid systems with application to large-scale logistics networks.
Hybrid systems are dynamical systems that combine two types of dynamics: continuous and discrete. Such behaviour occurs in wide range of applications. Logistics networks are one of such applications, where the continuous dynamics occurs in the production and processing of material and the discrete one in the picking up and delivering of material. Stability of logistics networks characterizes their robustness to the changes occurring in the network. However, the hybrid dynamics and the large size of the network lead to complexity of the stability analysis.
In this thesis we show how the behaviour of a logistics networks can be described by interconnected hybrid systems. Then we recall the small gain conditions used in the stability analysis of continuous and discrete systems and extend them to establish input- to-state stability (ISS) of interconnected hybrid systems. We give the mixed small gain condition in a matrix form Γ ◦ D ≥ id, where the matrix Γ describes the interconnection structure of the system and the diagonal matrix D takes into account whether ISS con- dition for a subsystem is formulated in the maximization or the summation sense. The small gain condition is sufficient for ISS of an interconnected hybrid system and can be applied to an interconnection of an arbitrary finite number of ISS subsystems. We also show an application of this condition to particular subclasses of hybrid systems: impul- sive systems, comparison systems and the systems with stability of only a part of the state.
Furthermore, we introduce an approach for structure-preserving model reduction for large-scale logistics networks. This approach supposes to aggregate typical interconnection patterns (motifs) of the network graph. Such reduction allows to decrease the number of computations needed to verify the small gain condition.
Introduction
Hybrid dynamical systems occur in many modern applications due to their ability to deal with a combination of both continuous and discrete types of dynamics in one model. The continuous dynamics is usually given by an ordinary differential equation with an input:
Abbildung in dieser Leseprobe nicht enthalten
and the discrete dynamics is given by an instantaneous change in the state (jump):
Abbildung in dieser Leseprobe nicht enthalten
This system behaves continuously in the points [Abbildung in dieser Leseprobe nicht enthalten] and jumps in the points [Abbildung in dieser Leseprobe nicht enthalten]. Such behaviour occurs, for example, in control systems that combine digital and analog devices, e.g., robotics[5], network control systems[159],[110], reset systems[111] or engineering systems[62]. Logistics networks is another type of systems that possesses hybrid dynamics. These networks pro- duce and move goods from suppliers to customers. In the literature, there are known many approaches for the modelling of logistics networks. These models differ in their ability to describe different net- work characteristics, to apply various analysis methods and to achieve desirable performance goals. Networks, where only continuous flows occur, are described by continuous dynamical systems, see [69],[41] and[65]. A network with discrete changes is given by a discrete-time model[7],[116], [113]. A network with random (stochastic) events can be modelled as a stochastic model, see[94] and[145]. In more general types of logistics networks there are usually continuous changes in pro- duction, processing or transportation of goods and discrete (discontinuous) changes in picking up and delivering of goods to other locations. In this case it is natural to describe the dynamics by a hybrid dynamical system, see[137] and[146].
The analysis of logistics networks can be performed also in different directions: optimization[69],[113],[137], where the main point is optimal performance of the network; stability, where stable behaviour under perturbation is desirable[146],[41],[116],[69] ; control, where the tools for the control of the network are developed[113],[137].
However, the real-world logistics networks are large-scale and possess a complex structure. This im- plies large size and complex structure of their models. Analytical analysis of large-scale models is rather sophisticated and time-consuming. This motivates the question of reduction of the model size before its analysis. The best way of reduction is to approximate the model by a smaller one. It means that the reduced model has to possess similar characteristics as the original one. In mathematical systems theory there is a theory of model reduction that proposes different methods for reduction of large-scale systems[4],[123]. These methods are well-developed for linear systems. Their main ad- vantages are small approximation error, preservation of dynamical properties (stability, observability, controllability) and numerical efficiency. However, the weak point of their application to logistics networks is that they, in general, do not preserve the structure of the network. This property is cru- cial for the analysis of logistics networks, because logistics networks consist of real physical objects like production facilities, warehouses, retailers, transportation routes and thus information about them should not be lost. Furthermore, the dynamics of logistics networks is usually nonlinear. Compared to linear systems, the theory of model reduction of nonlinear systems is taking only the first steps in its development and is applied only to particular classes of nonlinear dynamics[10]. We start this thesis by surveying eleven known approaches for modelling of logistics networks in Chapter 1. These approaches cover four types of dynamics: discrete one in Section 1.2.1, continuous one in Section 1.2.2, hybrid one in Section 1.2.3 and stochastic one in Section 1.2.4. We present the main equations of each model that describe the network dynamics and recall the main results concerning their application to stability analysis and control. We support the survey by a comparison of main characteristics of the approaches in Table 1.1.
To study stability of a logistics network we consider one of the modelling approaches that proposes to model logistics networks as an interconnection of n hybrid subsystems. Then the dynamics of logistic location i is described by a hybrid system
Abbildung in dieser Leseprobe nicht enthalten
with state xi (e.g. queue of orders or stock level), external input ui (e.g. customer orders or flow of raw material), continuous changes described by the function fi, discontinuous changes described by the function gi. The sets Ci, Di define the type of the behaviour of the i th subsystem corresponding to the given states xi and inputs ui: continuous in case Ci or discontinuous in case Di. Thus, this modelling approach includes two types of dynamics in one model and allows description of more general types of logistics networks.
We are concerned with stability of logistics networks, because this property guarantees persistence of the network to perturbations that occur, for example, in demand, cooperation between logistic partners or transportation. In particular, we are interested in input-to-state stability (ISS) introduced for continuous systems in[152] and extended to hybrid systems in[27]. This type of stability assures boundedness of the overall state [Abbildung in dieser Leseprobe nicht enthalten] ofthesystemunderboundednessoftheoverall external input [Abbildung in dieser Leseprobe nicht enthalten] foralltimesandstatejumps:
Abbildung in dieser Leseprobe nicht enthalten
Here x 0 is the initial state, t is the time, k is the number of the interval between the jumps, [Abbildung in dieser Leseprobe nicht enthalten] is the norm of the hybrid input. The function [Abbildung in dieser Leseprobe nicht enthalten] increases in the first argument and tends to zero in the second and the third one. The function [Abbildung in dieser Leseprobe nicht enthalten] is strictly increasing and γ (0) = 0.
In the stability analysis of the interconnection of hybrid subsystems we restrict us to the case where all subsystems has the ISS property, i.e.
Abbildung in dieser Leseprobe nicht enthalten
Functions [Abbildung in dieser Leseprobe nicht enthalten] are strictly increasing, unbounded and [Abbildung in dieser Leseprobe nicht enthalten]. Furthermore, γ ij describes the influence of the j th subsystem on the i th subsystem and thus it is also called gain function. Our aim is to use information about the interconnection structure of the network for checking whether the network is ISS. For continuous and discrete systems a well-established approach is to use the so- called small gain conditions[82],[54],[126],[50] and[86]. As hybrid systems combine both types of dynamics, this motivates us to adapt these small gain conditions to hybrid subsystems. The first attempts were done for an interconnection of two hybrid systems in[96],[110]. In Chapter 2 we extend application of the small gain condition to an interconnection of more than two subsystems. Moreover, we extend this condition to the case where some subsystems has the ISS property with summations instead of maximizations in the definition of ISS. To this end, we consider the gain matrix [Abbildung in dieser Leseprobe nicht enthalten] that describes the interconnection structure of the network. To guarantee ISS of the network we impose a sufficient condition, the mixed small gain condition in a matrix form, see Theorem 2.4.5:
Abbildung in dieser Leseprobe nicht enthalten
where Γ : [Abbildung in dieser Leseprobe nicht enthalten] is a matrix operator corresponding to the gain matrixΓ,idistheidentity operator and ≥ is the logical neglecting of ≥. The diagonal matrix operator [Abbildung in dieser Leseprobe nicht enthalten] has id in the i th element of the diagonal in case the i th subsystem has the ISS property in terms of maximizations and id + α in case the i th subsystem has the ISS property in terms of summations with some [Abbildung in dieser Leseprobe nicht enthalten] such that α is strictly increasing, unbounded and α (0) = 0. Thus, the mixed small gain condition impose a condition on the cooperation between logistics locations, given by the matrix Γ, that guarantees stability of a logistics network.
In Theorem 2.4.13 we apply this small gain condition to construct an ISS-Lyapunov function for the interconnected hybrid system. This function provides a useful tool for establishing ISS of the hybrid system. As a corollary, we present the small gain conditions for particular classes of hybrid systems: for systems where only parts of the states are stable in Corollary 2.4.20, for impulsive systems in Theorem 2.4.26 and for comparison systems in Theorem 2.4.30.
In the case of a large size of a logistics network, the verification of the small gain condition needs large amount of computations due to the large size of the corresponding gain matrix Γ. With aim to reduce the size of Γ, in Chapter 3 we introduce an approach for structure preserving model reduction of logistics networks. In this approach we consider the matrix Γ as a model of logistics networks that describes the interconnection structure of the network. To reduce the size of the gain matrix, we introduce three rules based on certain types of interconnections in the networks, so-called motifs [103], that allow to pass from the matrix Γ of dimension n to the matrix Γ of dimension l with l < n. These rules suppose aggregation of the gains of the subsystems that belong to one of the following motifs: parallel connection, sequential connection and almost disconnected subgraph. In Theorems 3.2.1, 3.2.5 and 3.2.9 we derive that, if the small gain condition holds for Γ obtained by an application of one of three aggregation rules, then the small gain condition holds also for Γ. Thus, we can establish ISS of logistics network of the size n by checking the small gain condition corresponding to the matrix Γ of dimension l < n, see Corollaries 3.2.2, 3.2.6 and 3.2.10. As the matrix Γ consists in general of nonlinear gains this approach can be applied to networks with linear dynamics as well as with nonlinear one. Furthermore, these aggregation rules preserve the main structure of a logistics network.
Description of a model of a logistics network as an interconnected continuous system considered in Section 1.2.2 is published in[41],[43] and[44]. A survey on the known modelling approaches for logistics networks from Chapter 1 is partially published in[141],[146]. The result on the mixed small gain condition from Chapter 2 for interconnected continuous systems is published in[49],[50]. The small gain results for hybrid and impulsive systems are published in[45],[46],[47] and[48]. Application of the aggregation rules, considered in Chapter 3, to reduce the size of the model of a logistics network is published in[143],[144]. A result on an investigation of topological properties of logistics networks is published in[142].
Chapter 1 Mathematical models of logistics networks
Logistics network, called also production network or supply chain, is a system that moves products from suppliers to customers[36]. Modern logistics networks vary in their structural and dynami- cal properties. They may consist of locations geographically distributed all over the world as well of machines arranged inside one production facility[33]. The main performance indicators of such networks are stability, minimization of costs and ability to satisfy customer orders. Feature charac- teristics and dynamics of a logistics network can be modelled either by the simulation models[140] or by the mathematical models. We are interested in the mathematical models as they allow deep in- vestigation of network dynamics. In the literature there is a wide choice of modelling approaches that vary in their properties. To summarize these approaches, there were performed several reviews of the known models in the literature. In[17],[104] authors consider simulation, game-theoretic, determin- istic and stochastic models that are mostly static. Models describing the decision process in logistics networks were investigated in[100] and models that deal with information sharing were reviewed in [78]. However, the aforementioned papers do not consider the dynamical behaviour of the network. The dynamical properties of logistics networks were studied in[135]. The authors stress there on the review of the typical mathematical approaches for the analysis of dynamical effects in logistics net- works without providing a detailed overview of the known modelling approaches. In this chapter we are going to fill this gap. To this end, we go through the main modelling approaches known in the lit- erature and identify their modelling concepts, application areas and features. At the end of the chapter we provide a comparison table that highlights the main properties of each modelling approach.
1.1 Notation
First, we introduce the notation that will be used throughout the thesis.
1.1.1 Logistics network
The main activities of a logistics network include production, inventory control, storing and pro- cessing. Thus, the network consists of different objects: suppliers, production facilities, distributors, retailers, customers, machines at a production facility. We call such objects locations. We denote by n the number of locations and we number all the locations by i = 1 , . . . , n. The decision, a location takes, on handling the orders relies on a certain policy. By x we understand the state of a location. Usually, it is the stock level (inventory level) of a location or a work content to be performed. The variable q denotes a length of queue, e.g., the queue of customer orders at a location or products to be processed by a machine. The external input denoted by u, describes usually the flow of customer orders or the flow of raw material from the external suppliers. The output is denoted by y. A typical output is consumption. The customer demand is described by the variable d. An example of a logistics network that illustrates our notation is shown in Figure 1.1.
Abbildung in dieser Leseprobe nicht enthalten
Figure 1.1: General description of a logistics network.
The production rate of a production facility is given by a production function f and the maximal production rate is denoted by α. The number of a production step is denoted by [Abbildung in dieser Leseprobe nicht enthalten] and the product type is denoted by p = 1 , 2 , . We define by cij the consumption rate of products of location j by location i and we denote by dij the delivery rate of products of location i to location j. For usual time we write t. For the time needed to rearrange a location for production of another type of products we write τ and call this time adaptation time.
Note that this is only a general description of logistics networks and its parameters. Later in Section 1.2, where we present different approaches for mathematical modelling of dynamics of logistics networks, some of these parameters disappear or new ones appear depending on the features of a specific modelling approach.
Material, information and monetary flows connect locations of a logistics network and create the structure of the network. The structure of a flow is frequently characterized as linear, convergent, divergent, or nonlinear, see Figure 1.2. Here, linear denotes a simple chain of locations passed one after the other, convergent describes flows originating from a large number of locations and ending in a few end locations, divergent describes the opposite structure in which a few sources feed a larger number of end locations, while nonlinear in this context simply denotes a more intricate structure which does not fit into the other categories.
Lack of information between the locations, complexity of the network structure, nonlinearity of dy- namics and large size of the network can bring the network to instability, e.g.[154],[37],[107] and [39]. Instability of logistics network means, roughly speaking, unboundedness of the overall state.
[...]
-
-
-
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X.