
Modeling and Control of Discrete Event Dynamic Systems 评分:
System and control theory deals with the problem of modeling and controlling systems. Natural systems, such as, for example, mechanical or thermodynamical systems, are characterized by continuous variables: the state of such a kind of systems is a vector whose entries are real numbers. Their evoluti
Contents 1 Introduction 3 2 Discrete Event Dynamic Systems: modelling and control 2.1 Discrete event Dynamic System models 2.1.1 State automata model 2.1.2 Petri net model 2. 1. 3 Dioid Alge rebra 2.1.4 Continuous how model 14 2.2 Control problem formulation and relaled issue 14 8 The state reconstruction algorithm 19 3. 1 Review of some Perturbation Analysis Techniques 20 3.2 The state reconstruction algorithm 26 3.2.1 Notation and queueing network dynamics 26 3.2.2 The state reconstruction problem 34 3.2.3 A concurrent implementation 40 3.3 Estimate analysis 43 4 Control of Discrete Event Systems based on the path reconstruc tion approach. 53 4.1 Review of some control approaches 58 4.2 STochastic Comparison Algorithm for NonSLalionary Discrete Event ystems 67 4.2.1 Optimization Problem Formulation 4.2.2 The stochastic comparison algorithm for non stationary DEDS 69 4.2.3 Analvtical results for the deterministic case 4.2.4 The general case 87 4.3 A modified version of the Stochastic Comparison algorithm for Non Stationary Discrete Event Systems 92 4.4 Some simulation results 94 4.5 Some implementation problems 103 Conclusions 107 Symbols and abbreviations ASA Augmented System analysis CSRA Concurrent sra CVDS ContinuousVariable Dynamic Systems DEDS Discrete Event Dynamic Systems FPA Finite pa GA Genetic Algorithm GSMP Generalized SemiMarkov process IPA Infinitesimal pa JⅠT Just in Time LR Likelyhood Ratio PA Perturbation Analys Standard clock g. Simulated Annealing SCA Stochastic Comparison Algorithm SCANS SCA for NonStationary DEDS SCANS SCANS improved SPA Smoothed pa SRA State Reconstruction Algorithm TWA Time Warping algorithm A particular resource allocation or paraineter vector value An optimal allocation The search space, i.e. the space of all possible 8 The set of optimal allocations (8, t) Performance function(or index) at time t for allocation A L(0, t, At) Estimate of (0, t)observing the system for At Optimize Minimize Chapter 1 Introduction System and control theory deals with the problem of modeling and controlling sys tems. Natural systems, such as, for example, mechanical or thermodynamical sys tems, are characterized by continuous variables: the state of such a kind of systems s a vector whose entries are real numbers. Their evolution is described by means of differential equations and is timedriven, that is, the current value of the state directly depends on the time, which can be thought of as an independent variable Once the equations of a model for this kind of systems have been derived it is pos sible in many cases, based on these equations, to find an analytical expression for a control law aimed at obtaining some desired results Very similar to these systems, there is a class of systems which are always char acterized by a real state vector, but their evolution, yet timedriven, is described by means of difference equations: in this case the state of the system changes only at discrete time ins tants. Many resulls available for timecontinuous syslems can be adapted to fit in this case All of these systems, discrete or continuous time dependent, are timedriven and their state can be given as a vector with real entries. They will be denoted with the term of ContinuousVariable Dynamic Systems(CVDS)(11) Many manmade systems can not be successfully described by models used for CVDS.It is the set of artificial systems usually characterized by some entities which can provide a particular desired service(and will be referred to as server s)and some other entities which compete one another and wait for this service(and will Introduction be called customers). This situation is really generaL: even if in this thesis the attention will be devoted to manufacturing systems(2D), the same concepts apply to communication and computer networks, or many general queueingsystems. If manufacturing systems are considered, a customer is typically a part which waits for an operalion on a queue while a server is a machine which performs a given set of operations on parts. In the communication system case the customer can be a piece of information which could require a particular channel or another device. which must be considered as a server There is a common feature in all these manmade systems: the state takes value on a discrete set. As an example, in the manufacturing case the state typically comprises the number of customers in the queues and the state of the machines (which, again, is a discrete if not boolean variable). Moreover the evolution is event driven rather than timedriven: the value of the state changes when something,that is an event, happens. The time an event is observed is usually a random variable and the state of the system as a function of the time is a stochastic process Discrete nature of the state and eventdependence make this kind of systems very different from CVDS. The term Discrete Event Dynamic Systems(dEds )comprises these najor characteristics Classical models like differential or difference equations are not useful to model DEDS. A mathematical model is a set of equations which can be used to reproduce the behavior of a system. In Chapter 2 a review of some mathematical models introduced to describe deds will be presented The main difference between these models and the ones used for CVds is that rarely they can be directly used to derive analytical expressions for metrics delined on the deds or for the control law which solves a particular control problem, how often is done in CVDs a different procedure is required for DEDS. A DEDS is usually a manmade system which has been realized for some specific purpose. The purpose of a DEDS and. in particular, of a manufacturing system, is that of providing some service achieving some objectives( 3, 2): at a high level these objectives can be those of making the most money, or guaranteeing high qualily products, or staying in Introduction business as long as possible. At a lower level, i.e. to achieve the previous results the objecti ves will be some performance measure like the number of part released by the system in the time unit(throughput), the time each customer has to wait for a service, the time a machine is in service, the cost and the gain corresponding to the dillerent operations, the percentage of imperfect products, and so on. Therelore, it appears natural to formulate a control problem for a manufacturing system as the optimization of a performance function defined to capture some interesting feature of the system. This performance function depends on the allocation of some resources and or on the definition of some policies or protocols: the dynamic choice of an allocation and / or the definition of a policy in order to optimize the considered performance function is then the objective of a control scheme From a more general point of view, the performance function can be seen as dependent on a vector of parameters, where each possible value for this vector can represent a particular resource allocation, a particular policy or a mix of them. In this perspective the objective of a control scheme is the dynamic choice of the value of the parameter vector to optimize a performance function. This is the problem addressed in this thesis, and it will be formally stated in Chapter 2, together with the main difficulties which arise to solve it In many cases a closed expression of the performance index as a function of the parameter vector is not directly available through mathematical models of the sys tem and many approaches, like Perturbation Analysis( 4, 5, 61, Rapid Learning (7), Sample Path Analysis(8) and State Reconstruction (19, 10) are aimed to compute an estimate of the performance function for a particular parameter set Ling. The estimate is computed using dala recorded during the observation of the system, which can evolve with a value of the parameter vector different from the one for which the estimate is sought. This will be the main subject of Chapter 3 which contains one of the contributions of this thesis. the state reconstruction al gorithm. This algorithm presents many advantages with respect to other well known techniques: it can be applied to any deds considering every possible value for the parameter vector; it provides an exact estimate of the performance function and Introduction 6 does not require any knowledge on future events of the dEds unlike many classical Perturbation Analysis techniques Chapter 4 deals with the control problem: how to use this kind of estimate approaches to design control algorithms. The basic idea is quite simple: once an estimate of the performance function for many and possibly all the values of the parameter vector is available, the objective is that of selecting the value of the parameter vector corresponding to the(supposed) best performance Such a con ceptually simple problem presents many complications. Among them: (i)the set of all possible values of the parameter vector. called the scarch space, can be very large and an estimate of the performance function for all possible values of the parameter vector could become computationally unfeasible;(ii) the performance function is known only through estimates; (ii ) the system can be timevarying, which means a good choice for the parameter vector can become quite bad in the future All of these as pects require a careful study for designing an accepta ble control scheme. A comparison between different proposals is offered in Chapter 4 Among them, a novel algorithm, the Stochastic Comparison Algorithm for Non Stationary DEDS(SCANS)(11, 12, 13), and a modified version of it are pre sented in Chapter 4 and c onstitute the more significant. c ontribution of t his thesis SCANS has been derived modifying one of the more recent stochastic optimiza tion approaches in this research area, the Stochastic Comparison Algorithm(SCa proposed by gong et al.( 14, 15) and described also in Chapter 4. The change has been performed trying to maintain the interesting characteristics of the original algorithm but with the objective of controlling non stationary DEDS. Analytical resulls as well as simulalion ex periments assess the elfectiveness of the proposed scheme, which can be applied to any DEDS and benefits from advantages of order statistics with respect to cardinal estimates(16, 17, 18) The thesis ends with a concluding chapter, Chapter 5, which summarizes on the results presented and reports some indications for future work Chapter 2 Discrete Event Dynamic Systems modelling and control This chapter focuses on two subjects: how to model a discrete Event Dynamic ystem and how a control problem can be formulated. In particular, the control problem considered in this thesis will be formally stated The first section is devoted to the description of the ma jor models which have been derived for studying DEDS [1, 19. It must be remarked that a mathematical model of a system (a general system, also a continuousVariable Dynamic system is a tool which allows to analvze and identify the behavior of the system. In that a model is not the real system but can be seen as another system, completely known alld sinple enough. which can be used to reproduce the behavior of the considered system with sufficient precision in terms of the objectives for which the model has been created. A model is created to analyze and identify a svstem but the identification process is usually nothing but the first step in the solution of a contro problem. As a matter of fact, for CVDs, the models can often be directly used to analytically compute a control law which solves the considered control problem As it will be more apparent in the following, the most part of models derived lo describe a discrete event Dynamic System is usually very complex and much more suitable for simulation purposes rather than analytical studies. This means that these models constitute a good tool to reproduce the behavior of a deds and its evolution, but they are not very useful to derive an analytical expression of the state Chapter 2Modeling and control as a function of the time. This is not only due to the stochastic nature of events characterizing a deds but it depends also on the particular structure of such a kind of systems The particular structure of a DEdS reflects also on the way a control problem for Chis kind of systems can be formulated. Section 2 deals with this problem. A Con trol problem, as said in the Introduction, can be often transformed in the dynamic optimization of a performance function defined on the system. In a manufacturing system, this objective function can depend on the particular policy adopted to pro cess arriving parts or on the allocation of some resources. These can be considered as two different problems but also as two steps in the design of a manufacturing system: a long term control is applied to allocate resources, then a policy must be defined given the allocation. But resource allocation can also be seen as a short term control problem especially when the resource allocation can be accomplished very quickly. In the Introduction, a parameter vector which can comprise both the resource allocation and the type of policy implemented has been mentioned, and the problem is the dynamic choice of the value of the parameter vector to optimize a performance function defined on the manufacturing system. TH ne discussion o problen is reported in Section 2.2 2.1 Discrete Event Dynamic system models The Discrete Event Dynamic Systems considered in this thesis are manufacturing systems, where some parts wait on queues to be serviced by some machines. The state of such a kind of systems comprises the number of parts waiting in all the queues contained in the system as well as the state of the machines, which can be idle, blocked, down or servicing a part. The state changes when an event happens For manulacturing systems an event can be a service completion, a part arrival, a machine failure or repair, and so on. a sequence of events drives the state of the system from a value to another value. If each event is associated with a symbol of a language, a sequence of events can be seen as a word in this language( 20, 2120180913 上传 大小：873KB

Robot Modeling and Control First Edition
《Robot Modeling and Control First Edition》 Mark W. Spong, Seth Hutchinson, and M. Vidyasagar
立即下载

Modeling and Control of Complex Physical Systems.pdf
Modeling and Control of Complex Physical Systems 键合图教材
立即下载

dynamic modeling and control of engineering systems
dynamic modeling and control of engineering systems
立即下载

Modeling and control of a Delta3 robot
Modeling and control of a Delta3 robot机械臂资料（转），速度，动力学分析，希望对大家有用
立即下载

Type2 Fuzzy Logic Uncertain Systems Modeling and Control.pdf
Type2 Fuzzy Logic Uncertain Systems Modeling and Control
立即下载

Modeling and Control of Complex Physical Systems The PortHamiltonian Approach
Modeling and Control of Complex Physical Systems The PortHamiltonian Approach
立即下载