Infinitesimal and finite perturbation analysis for queueing networks

The sample-path perturbation analysis technique is extended to include finite (and possibly large) perturbations typically introduced by changes in queue sizes or other parameters. It is shown that there is a natural hierarchy of perturbation analysis which takes care of increasingly large perturbations. Experiments with zero (infinitesimal) and first order (finite) perturbation analysis show that significant accuracy improvement can be obtained with small increase in computational effort.     

A new approach to the analysis of discrete event dynamic systems

We present a new, time domain approach to the study of discrete event dynamical systems (DEDS), typified by queueing networks and production systems. A general state-space representation is developed and perturbation analysis is carried out. Observation of a single sample realization of such a system can be used to predict behavior over other sample realizations, when some parameter is perturbed, without having to make additional observations. Conditions under which this is always possible are investigated and explicit results for some special cases are included.     

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.     

On derivative estimation of single-server queues via structural infinitesimal perturbation analysis

In Dai and Ho (1994) we developed a method, referred to asstructural infinitesimal perturbation analysis (SIPA), to address the need for derivative estimation with respect to a special type of parameter. However, it was not clear how much computational effort is required to implement this method. Derivative estimation via SIPA can be complicated in implementation. Such computational problems, also arise in several other derivative estimation methods. In this paper we take SIPA as a typical method and apply it to a special class of DEDS-several variations of single-server queues, focusing on the issue of implementation. We demonstrate that SIPA can be efficiently implemented. In some cases, it can be as simple as theinfinitesimal perturbation analysis (IPA), method which is considered to be the most efficient method available so far. The main approach we take is to combine SIPA with finite perturbation analysis and cut-and-paste techniques. Explicit formulae are given to various problems, some being impossible to solve using the traditional IPA method. Numerical examples are employed to illustrate the results.     

Strong consistency of infinitesimal perturbation analysis for tandem queueing networks

Strong consistency of infinitesimal perturbation analysis for the sojourn times in a class of tandem queueing networks is proved. Service times at the queues are correlated, and they are affine functions of the variable parameters. Differentiability of the average sojourn times is not assumed, but proved. The analysis is not based on assumptions of regenerative cycles of the networks but on stability and ergodicity of the queueing processes involved. The proof of strong consistency is based on a set of abstract conditions, described in terms of properties of the sample performance functions. These conditions are first shown to be sufficient for strong consistency, and then their validity for the networks in question is proved.Research supported in part by the NSF under grants Nos. ECS85-15449 and CDR-8803012, under ONR contract nos. N00014-90-K-1093 and N00014-89-J-1023, and under Army contract no. DAAL-03-83-K-0171. This author is now with the Department of Manufacturing Engineering, Boston University, Boston, MA 02215.     

一种计算性能指标对路径概率灵敏性的新方法

本文提出了应用全状态摄动分析直接计算对路径概率的灵敏性,推导了路径变化时摄动的产生规则,给出了两个数值例子.实验结果验证了这一方法的有效性和准确性,     

一种计算性能指标对路径概率灵敏性的新方法

本文提出了应用全状态摄动分析直接计算对路径概率的灵敏性,推导了路径变化时摄动的产生规则,给出了两个数值例子,实验结果验证了这一方法的有效性和准确性。     

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

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

离散事件动态系统的分析和优化：排队网络模型方法（下）

5近似分析法前面我们介绍了排队网络的三种分析方法,它们都可以求出准确解。这当然是最理想结果,遗憾的是这些方法并不适用于所有的排队网络模型。因此在这一节里我们接着介绍排队网络模型的近似分析。事实上上节已经介绍了一种近似方法:平均值近似分析法。之所以提出近似分析是因为一方面有许多排队网络用现在的理论还无法求出其准确解,因此不得不借助于近似分析;另     

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.     

Performance evaluation and perturbation analysis of discrete event dynamic systems

This is a conceptual and speculative paper concerning the future development of system and control theory in operational and discrete event systems with particular emphasis to the techniques of perturbation analysis.     

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.     

An event domain formalism for sample path perturbation analysis of discrete event dynamic systems

We present a state-space representation of a general discrete event dynamic system (DEDS) model on the basis of a natural event domain, which replaces time. Perturbation analysis of a sample path Of a DEDS is then formalized using some fundamental concepts introduced to establish conditions for its validity. A set of simple perturbation equations is then derived under these conditions, so that performance gradients with respect to parameters are estimated from observation of real or simulated data on a single sample path.     

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.     

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.     

Eigenvalues of dynamic max-min systems

Discrete event dynamic systems are studied in which the time evolution depends on the max-, min-, and the summation operation simultaneously. Specifically, necessary and sufficient conditions are given under which the operator which characterizes the evolution of such a system has an eigenvalue and eigenvector(s). Numerical algorithms to calculate these quantities are also provided.Most of the research described in this paper was done while at École des Mines de Paris in Fontainebleau, Centre d'Automatique et Informatique, France, during the summer of 1989.     

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.     

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.     

On-line control of partially observed discrete event systems

It is well known that the design of supervisors for partially observed discrete-event systems is an NP-complete problem and hence computationally impractical. Furthermore, optimal supervisors for partially observed systems do not generally exist. Hence, the best supervisors that can be designed directly for operation under partial observation are the ones that generate the supremal normal (and controllable) sublanguage. In the present paper we show that a standard procedure exists by which any supervisor that has been designed for operation under full observation, can be modified to operate under partial observation. When the procedure is used to modify the optimal full-observation supervisor (i.e., the one that generates the supremal controllable language), the resultant modified supervisor is at least as efficient as the best one that can be designed directly (that generates the supremal normal sublanguage). The supervisor modification algorithm can be carried out on-line with linear computational complexity and hence makes the control under partial observation a computationally feasible procedure.