Admission control in stochastic event graphs

We first show that the expectation of convex increasing functions of the workload (or waiting time) in (max, +) linear systems, under a single input sequence, is multi-modular. This is done using a coupling argument and a vectorial version of Lindley's equation. Next, we use this result and the optimization theory based on multi-modular costs to construct the optimal open-loop admission control in general (max, +) linear systems under admission rate constraints. This optimization result only requires stationarity assumptions on the arrival process and on the service times of the servers in the system     

Asymptotic properties of stochastic timed event graphs

This paper addresses the asymptotic properties of stochastic timed event graphs. The transition firing times are random variables with general distribution. Asymptotic properties with respect to the net structure, the transition firing times and the initial marking are established on the basis of some new performance bounds. Applications to manufacturing systems are presented. We prove in particular a conjecture which claims that the throughput rate of a transfer line decreases to a positive value when the number of machines increases.     

Marking optimization of stochastic timed event graphs using IPA

This paper addresses the marking optimization of stochastic timed event graphs, where the transition firing times are generated by random variables with general distributions. The marking optimization problem consists of obtaining a given cycle time while minimizing a p-invariant criterion. We propose two heuristic algorithms, both starting from the optimal solution to the associated deterministic problem and iteratively adding tokens to adequate places as long as the given cycle time is not obtained. Infinitesimal perturbation analysis of the average cycle time with respect to the transition firing times is used to identify the appropriate places in which new tokens are added at each iteration. Numerical results show that the heuristic algorithms provide solutions better than the ones obtained by the existing methods.     

Analytic evaluation of the cycle time on networked conflicting timed event graphs in the (Max,+) algebra

This work deals with performance evaluation of Conflicting Timed Event Graph (CTEG), a class of Petri net exhibiting phenomena such as synchronization, parallelism and resources sharing. It is well known that the dynamic of Timed Event Graphs (TEG) admits a linear state space representation in the (Max,+) algebra which makes the analysis and control of this class easier. There is also a possibility of associating conflicts with the TEGs by adding conflict places that are mostly considered as safe; this extended class is called CTEG. We first present an analytic evaluation of the cycle time of CTEG as a function of the cycle time of each TEG and of the timers of the conflict places. Finally, in a more general context, we look for a relaxation of the safety hypothesis on the conflict places in order to model and evaluate the cycle time on CTEGs with multiple shared resources.     

Cycle bases of graphs and sampled manifolds

Point samples of a surface in are the dominant output of a multitude of 3D scanning devices. The usefulness of these devices rests on being able to extract properties of the surface from the sample. We show that, under certain sampling conditions, the minimum cycle basis of a nearest neighbor graph of the sample encodes topological information about the surface and yields bases for the trivial and non-trivial loops of the surface. We validate our results by experiments.     

Optimisation of invariant criteria for event graphs

The problem of obtaining a cycle time that is smaller than a given value in a strongly connected event graph, while minimizing an invariant linear criterion, is addressed. This linear criterion is based on a p-invariant of the strongly connected event graph under consideration. Some properties of the optimal solution are proved, and a heuristic algorithm and an exact algorithm which make it possible to reach a solution to the problem are given. Applications of the results to the evaluation of job shops and Kanban systems are proposed     

Information-efficient control of discrete event stochastic systems

A state of a discrete event stochastic system (DESS) can be represented by a tuple of time-varying discrete parameters. The authors have extended the theory of controlled discrete event systems developed by Ramadge, Wonham and other researchers to stochastic modeling and performance measurement. This work presents some important characteristics of the DESS model. The problem of making the most efficient use of information-processing resources (sensors, computer capacity, etc.) in a special class of controlled systems is stated in a new, two-stage format. The format is used to develop a heuristic solution procedure of the problem. Finally, we perform a brief discussion of the model applicability to real-life design of automatic supervisors     

Disease management research using event graphs.

Event Graphs, conditional representations of stochastic relationships between discrete events, simulate disease dynamics. In this paper, we demonstrate how Event Graphs, at an appropriate abstraction level, also extend and organize scientific knowledge about diseases. They can identify promising treatment strategies and directions for further research and provide enough detail for testing combinations of new medicines and interventions. Event Graphs can be enriched to incorporate and validate data and test new theories to reflect an expanding dynamic scientific knowledge base and establish performance criteria for the economic viability of new treatments. To illustrate, an Event Graph is developed for mastitis, a costly dairy cattle disease, for which extensive scientific literature exists. With only a modest amount of imagination, the methodology presented here can be seen to apply modeling to any disease, human, plant, or animal. The Event Graph simulation presented here is currently being used in research and in a new veterinary epidemiology course.     

Approximate throughput computation of stochastic marked graphs

A general iterative technique for approximate throughput computation of stochastic strongly connected marked graphs is presented. It generalizes a previous technique based on net decomposition through a single input-single output cut, allowing the split of the model through any cut. The approach has two basic foundations. First, a deep understanding of the qualitative behavior of marked graphs leads to a general decomposition technique. Second, after the decomposition phase, an iterative response time approximation method is applied for the computation of the throughput. Experimental results on several examples generally have an error of less than 3%. The state space is usually reduced by more than one order of magnitude; therefore, the analysis of otherwise intractable systems is possible     

Supervisory control of timed event graphs with partial specifications

This paper studies realizable firing time sequences under supervisory control in the max-algebra model of timed event graphs. A specification is assumed to be defined on firing times of a specified subset of transitions. Such a specification is called a partial specification. A necessary and sufficient condition for a partial specification to be realizable is presented under the assumption that all controllable transitions are in the specified subset. For a not realizable partial specification, the extremal realizable sequences are obtained as its approximations.     

Verification of discrete time stochastic hybrid systems: A stochastic reach-avoid decision problem

We present a dynamic programming based solution to a probabilistic reach-avoid problem for a controlled discrete time stochastic hybrid system. We address two distinct interpretations of the reach-avoid problem via stochastic optimal control. In the first case, a sum-multiplicative cost function is introduced along with a corresponding dynamic recursion which quantifies the probability of hitting a target set at some point during a finite time horizon, while avoiding an unsafe set during each time step preceding the target hitting time. In the second case, we introduce a multiplicative cost function and a dynamic recursion which quantifies the probability of hitting a target set at the terminal time, while avoiding an unsafe set during the preceding time steps. In each case, optimal reach while avoid control policies are derived as the solution to an optimal control problem via dynamic programming. Computational examples motivated by two practical problems in the management of fisheries and finance are provided.     

Control of stochastic discrete event systems modeled byprobabilistic languages

In Garg et al. (1999) and Garg (1992) the formalism of probabilistic languages for modeling the stochastic qualitative behavior of discrete event systems (DESs) was introduced. In this paper, we study their supervisory control where the control is exercised by dynamically disabling certain controllable events thereby nulling the occurrence probabilities of disabled events, and increasing the occurrence probabilities of enabled events proportionately. This is a special case of “probabilistic supervision” introduced in Lawford and Wonham (1993). The control objective is to design a supervisor such that the controlled system never executes any illegal traces (their occurrence probability is zero), and legal traces occur with minimum prespecified occurrence probabilities. In other words, the probabilistic language of the controlled system lies within a prespecified range, where the upper bound is a “nonprobabilistic language” representing a legality constraint. We provide a condition for the existence of a supervisor. We also present an algorithm to test this existence condition when the probabilistic languages are regular (so that they admit probabilistic automata representation with finitely many states). Next, we give a technique to compute a maximally permissive supervisor online     

Interval analysis and dioid: application to robust controller design for timed event graphs

This paper deals with feedback controller synthesis for timed event graphs, where the number of initial tokens and time delays are only known to belong to intervals. We discuss here the existence and the computation of a robust controller set for uncertain systems that can be described by parametric models, the unknown parameters of which are assumed to vary between known bounds. Each controller is computed in order to guarantee that the closed-loop system behavior is greater than the lower bound of a reference model set and is lower than the upper bound of this set. The synthesis presented here is mainly based on dioid, interval analysis and residuation theory.     

Approximate mean value analysis for stochastic marked graphs

An iterative technique for the computation of approximate performance indices of a class of stochastic Petri net models is presented. The proposed technique is derived from the mean value analysis algorithm for product-form solution stochastic Petri nets. In this paper, we apply the approximation technique to stochastic marked graphs. In principle, the proposed technique can be used for other stochastic Petri net subclasses. In this paper, some of these possible applications are presented. Several examples are presented in order to validate the approximate results     

On just-in-time control of timed event graphs with input constraints: a semimodule approach

Timed event graph (TEG) is a subclass of timed Petri nets that can be used to model discrete event systems subject to synchronization and time delay phenomena. Just-in-Time control in TEG can be defined as the determination of latest admission date of resources in order to respect a given demand profile. In this paper this kind of control problem is studied in situations in which the input dynamics are constrained to a given semimodule (a kind of linear vector space in a semiring context). We give necessary and sufficient conditions to solve the problem and present two computational methods to solve it. Application examples are presented to illustrate the applicability of the results.     

Cycle time assignment of min-max systems

A variety of problems in computer networks, digital circuits, communication networks, manufacturing plants, etc., can be modelled as discrete event systems with maximum and minimum constraints. Systems with mixed constraints are non-linear and are called min-max systems. The cycle time vector of such a system arises as a performance measure for discrete event systems and provides the appropriate non-linear generalization of the spectral radius. This paper gives a complete account of the cycle time assignment by the state feedback for min-max systems. We describe some new definitions and results about such assignment which generalize the initial earlier works and shed new light on aspects of linear control theory. For an arbitrary min-max system, by introducing the concept of colouring graph and constructing the total condensation and its matrix representation, we give the canonical structure form. In order to design the state feedback system in which the internal structure property is unchanged and the cycle time can be assigned, we introduce and characterize the assignability, uniform state feedback and unmerged assignment for min-max systems. We present an algorithm for the unmerged assignment and illustrate our algorithm by means of an example.     

A necessary and sufficient condition for diagnosability of stochastic discrete event systems

Stochastic discrete event systems (SDES) are systems whose evolution is described by the occurrence of a sequence of events, where each event has a defined probability of occurring from each state. The diagnosability problem for SDES is the problem of determining the conditions under which occurrences of a fault can be detected in finite time with arbitrarily high probability. (IEEE Trans Autom Control 50(4):476–492 2005) proposed a class of SDES and proposed two definitions of stochastic diagnosability for SDES called A- and A A-diagnosability and reported a necessary and sufficient condition for A-diagnosability, but only a sufficient condition for A A-diagnosability. In this paper, we provide a condition that is both necessary and sufficient for determining whether or not an SDES is A A-diagnosable. We also show that verification of A A-diagnosability is equivalent to verification of the termination of the cumulative sum (CUSUM) procedure for hidden Markov models, and that, for a specific class of SDES called fault-immediate systems, the sequential probability ratio test (SPRT) minimizes the expected number of observable events required to distinguish between the normal and faulty modes.     

Firing rate optimization of cyclic timed event graphs by token allocations

In this paper, we deal with the problem of allocating a given number of tokens in a cyclic timed event graph (CTEG) so as to maximize the firing rate of the net. We propose three different approaches. The first one is a “greedy” incremental procedure that is computationally very efficient. The only drawback is that the convergence to the optimum is guaranteed only when the set of places where tokens can be allocated satisfies given constraints. The other two procedures involve the solution of a mixed integer linear programming problem. The first one needs the knowledge of the elementary circuits, thus it is convenient only for those classes of CTEG whose number of elementary circuits is roughly equal to the number of places, such as some kanban-systems. On the contrary, the second one enables one to overcome this difficulty, thus providing an efficient tool for the solution of allocation problems in complex manufacturing systems like job-shop systems.