Full-state perturbation analysis of discrete event dynamic systems

Discrete event dynamic systems are studied within the framework of perturbation analysis in this paper. Perturbation is extended from the event times only to both event times and queue lengths. An approximate technique, full-state perturbation analysis (PA), is developed as an extension of the PA approach. Full-state PA is able to deal with problems involving queue length perturbations which often defy existing PA methods, while it still retains all the advantages of existing PA. Full-state PA is used to calculate the throughput sensitivity to the number of customers in closed queueing networks and the throughput sensitivity to routing change. Numerical examples are given. Experimental results verify the validity and accuracy.This work is supported in part by the National High Technology Project and by Southeast University Research Funds for Young Teachers.     

极大代数方法在轧钢厂DEDS中的应用

本文用极大代数方法对某轧钢厂建立了离散事件动态系统(DEDS)模型,在周期分析与配置理论的基础上解决了最优调度与控制问题.     

极大代数意义下矩阵的特征值问题--一类离散事件动态系统运行周期的分析

在分析一类离散事件动态系统的运行周期及稳定性时,必须求解极大代数意义下矩阵的特征值及特征向量,这一直被认为是十分困难和繁复的工作.本文给出了求任一方阵特征值及特征向量的十分简单易行的方法以及有关的定理.     

极大代数意义下矩阵的特征值问题——一类离散事件动态系统运行周期的分析

在分析一类离散事件动态系统的运行周期及稳定性时,必须求解极大代数意义下矩阵的特征值及特征向量,这一直被认为是十分困难和繁复的工作.本文给出了求任一方阵特征值及特征向量的十分简单易行的方法以及有关的定理.     

极大代数意义下幂矩阵的周期性特征

在分析一类离散事件动态系统的运行周期性及稳定性时,必须求解极大代数意义下矩阵的特征值。这一直被认为是十分困难的工作。直至目前为止,尚无一种能确定任一方阵全部特征值及特征向量的简易方法。本文对极大代数意义下任一方阵的幂矩阵的周期性特征进行了深入分析。本文的结果为寻求计算特征值及特征向量的新算法提供了十分有效的途径。     

离散事件系统N步稳定性分析

讨论基于自动机/形式语言模型的离散事件系统(DES)稳定性问题,引入了确定性离散事件系统N步稳定性定义,并得到了稳定性的判据定理,推导了具体的算法实现。该算法具有多项式复杂度。     

Fault detection and isolation in manufacturing systems with an identified discrete event model

In this article a generic method for fault detection and isolation (FDI) in manufacturing systems considered as discrete event systems (DES) is presented. The method uses an identified model of the closed-loop of plant and controller built on the basis of observed fault-free system behaviour. An identification algorithm known from literature is used to determine the fault detection model in form of a non-deterministic automaton. New results of how to parameterise this algorithm are reported. To assess the fault detection capability of an identified automaton, probabilistic measures are proposed. For fault isolation, the concept of residuals adapted for DES is used by defining appropriate set operations representing generic fault symptoms. The method is applied to a case study system.     

一类柔性制造系统的运行特性

柔性制造系统是一类重要的离散事件动态系统,它的运行特性分析及系统优化已引起了广泛的注意．本文研究Cohen模型描述的一类柔性制造系统的运行特性,着重分析系统的加工时间矩阵与系统运行效率的关系．应用本文的结论,可以找到一大类具有相同运行效率的柔性制造系统,这对于系统的优化是有意义的,文中的例子不仅证实了各种结论,而且对于生产线上的排序问题有启发意义．     

Modular nonblocking state feedback control of discrete event systems and its application to dynamic oligopolistic markets

This article addresses a modular state feedback supervisory control problem where two local controllers should achieve a common control objective against another local controller. Each local controller has its own control objective described as a predicate. This article also addresses a nonblocking modular control problem in which a discrete event system controlled by three local controllers tends to reach the common marked states of two local controllers that are, however, prohibited by the third local controller. For a case study, we apply the proposed theory to an oligopolistic market composed of two firms and one government. Two oligopolistic firms have a common objective to maximise their total profit through collusion. However, the government prevents them from engaging in collusion. We show that the modular supervisory control theory presented in this article can be used to solve the problem of ‘how can the firms maximise their total profit against the intervention of government’?     

Diagnosability of discrete event systems subject to permanent sensor failures

This paper considers a failure diagnosis problem for discrete event systems subject to permanent sensor failures. A notion of diagnosability subject to permanent sensor failures is introduced with respect to a certain nondeterministic observation mask. For its verification, an aggregated Mealy automaton with a deterministic and state-dependent observation mask is defined. It is shown that the diagnosability of the aggregated Mealy automaton is equivalent to the diagnosability of the original system subject to permanent sensor failures. Then, a method for verifying the diagnosability of the aggregated Mealy automaton is presented. Moreover, the delay bound within which the occurrence of any failure string can be detected subject to permanent sensor failures is computed.     

Reduced ellipsoidal state observer of multidimensional discrete dynamic systems

The problem of synthesis of a reduced ellipsoidal state observer is considered for multidimensional linear stationary dynamic systems. The algorithms developed possess the robustness property, i.e., they are not sensitive to violation of a priori assumptions ah he system. Computer simulation of an adaptive spacecraft attitude control system confirms the cjjiciency of the algorithm developed. The study was carried out with the partial support of the Ukrainian Scientific and Technical Center. Project No. 548. Translated frorr Kibernetika i Sistemnyi Analiz, No. 2. pp. 99–105, March–April, 2000.     

Stabilization and blocking in state feedback control of discrete event systems

We consider controlled discrete event systems modeled by the Ramadge-Wonham model, with a control specification given in terms of both admissible and target states. We define blocking in state feedback control using the notion of stability of discrete event systems. Intuitively, a system is said to be blocking if some trajectories of admissible states cannot reach target states. For control-invariant predicates we define two performance measures called a prestabilizing measure and a blocking measure. First, we present an algorithm to compute the minimally restrictive nonblocking solution. But the nonblocking solution may be restrictive. Then we present design methods to improve the two performance measures. And we show that the task of logical optimization of a blocking feedback can be done by two steps.     

Supervisory control using augmented languages in discrete event systems

This paper introduces the concept of an augmented (super) language of a specified language and studies its application to finite state supervisory control. First, we investigate several properties of an augmented language, especially related to controllability of the specified language. We propose an algorithm for the computation of a controllable sublanguage for which a finite state supervisor exists, using an augmented language, and show a sufficient condition for the controllable sublanguage to be supremal. It is shown, however, that such a finite state supervisor is sometimes blocking. Moreover, we discuss the relationship between the Wonham-Ramadge algorithm and our proposed one.     

Diagnosability of fuzzy discrete event systems

In this paper, discrete event systems (DESs) are reformulated as fuzzy discrete event systems (FDESs) and fuzzy discrete event dynamical systems (FDEDSs). These frameworks include fuzzy states, events and IF-THEN rules. In these frameworks, all events occur at the same time with different membership degrees. Fuzzy states and events have been introduced to describe uncertainties that occur often in practical problems, such as fault diagnosis applications. To measure a diagnoser’s fault discrimination ability, a fuzzy diagnosability degree is proposed. If the diagnosability of the degree of the system yields one a diagnoser can be implemented to identify all possible fault types related to a system. For any degree less than one, researchers should not devote their time to distinguish all possible fault types correctly. Thus, two different diagnosability definitions FDEDS and FDES are introduced. Due to the specialized fuzzy rule-base embedded in the FDEDS, it is capable of representing a class of non-linear dynamic system. Computationally speaking, the framework of diagnosability of the FDEDS is structurally similar to the framework of diagnosability of a non-linear system. The crisp DES diagnosability has been turned into the term fuzzy diagnosability for the FDES. The newly proposed diagnosability definition allows us to define a degree of diagnosability in a class of non-linear systems. In addition, a simple fuzzy diagnosability checking method is introduced and some numerical examples are provided to illustrate this theoretical development. Finally, the potential applications of the proposed method are discussed.     

Optimizing discrete event dynamic systems via the gradient surface method

In this paper we propose a gradient surface method (GSM) for the optimization of discrete event dynamic systems. GSM combines the advantages of response surface methodology (RSM) and efficient derivative estimation techniques like perturbation analysis (PA) or likelihood ratio method (LR). In GSM, the gradient estimation is obtained by PA (or LR), and the performance gradient surface is obtained from observations at various points in a fashion similar to the RSM. Zero points of the successive approximating gradient surface are then taken as the estimates of the optimal solution. GSM is characterized by several attractive features: it is a single-run method and more efficient than RSM; it uses at each iteration step the information from all data points rather than just the local gradient; it tries to capture the global features of the gradient surface and thereby quickly arrives at the vicinity of the optimal solution. A number of examples are exhibited to illustrate this method.This work was supported by the Office of Naval Research Grants Nos. N00014-90-K-1093 and N00014-89-J-1023, by National Science Foundation Grant No. ECS-85-15449 and by Army Grant No. DAAL-03-86-K-0171.     

Diagnosability of discrete event systems and its applications

As man-made systems become more and more complex, diagnostics of component failures is no longer an easy task that can be performed based on experience and intuition. Therefore, it is important to develop a systematic approach to diagnostic problems. Diagnostics can be done either on-line or off-line. By on-line diagnostics, we mean diagnostics performed while the system to be diagnosed is in normal operation. On the other hand, in off-line diagnostics, the system is not in normal operation. We will study both on-line and off-line diagnostics in this paper and identify main features and differences of these two types of diagnostics. We will also introduce the concept of diagnosability and study its properties, all in the framework of discrete event systems. This study is motivated by diagnostic problems in the automotive industry and we will emphasize its applications.     

Modal control of linear time invariant systems

A procedure is presented for the determination of a linear control law (for a system with one input) such that the resultant closed–loop System has specified eigenvalues. The design procedure is simpler than existing techniques.     

Min-max functions

A variety of problems in operations research, control theory, computer science, etc., can be modeled as discrete event systems with maximum and minimum constraints. When these systems require only maximum constraints (or, dually, only minimum constraints) they can be studied by linear methods based on max-plus algebra. Systems with mixed constraints, however, are nonlinar from this perspective and relatively little is known about their behaviour. The paper lays the foundations of the theory of discrete event systems with mixed constraints. We introduce min-max functions,F:R ⁿ R ⁿ , which are constructed using finitely many operations of min, max and +, and study them as dynamical systems. Among other results, we give a complete account of the periodic behavior of functions of dimension 2; we introduce and characterize the concept of balance which generalizes irreducibility in the linear theory; and we give a formula for the cycle time (eigenvalue) of a min-max function which generalizes the maximum cycle mean formula.     

按树的最大特征值排序

设Tn为n个顶点的树的集合.人们研究了Tn中树的最大特征值及其序,给出了第1至第13位的序以及对应的树.用另一种方法给出了第10至第13位的序以及对应的树,并在此基础上将Tn中树的最大特征值的序扩展到第14位.