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.     

Ergodicity and throughput bounds of Petri nets with uniqueconsistent firing count vector

Ergodicity and throughput bound characterization are addressed for a subclass of timed and stochastic Petri nets, interleaving qualitative and quantitative theories. The nets considered represent an extension of the well-known subclass of marked graphs, defined as having a unique consistent firing count vector, independently of the stochastic interpretation of the net model. In particular, persistent and mono-T-semiflow net subclasses are considered. Upper and lower throughput bounds are computed using linear programming problems defined on the incidence matrix of the underlying net. The bounds proposed depend on the initial marking and the mean values of the delays but not on the probability distributions (thus including both the deterministic and the stochastic cases). From a different perspective, the considered subclasses of synchronized queuing networks; thus, the proposed bounds can be applied to these networks     

Regenerative stochastic Petri nets

The stochastic Petri net (SPN) model is well suited to formal representation of concurrency, synchronization, and communication. We define the marking process of an SPN in terms of a general state space Markov chain which describes the net at successive transition firing times. Using structural properties of the SPN and recurrence theory for generalized semi-Markov processes, we establish conditions which ensure that the marking process of an SPN is a regenerative process and that the expected time between regeneration points is finite. This leads to a theory of regenerative simulation in the SPN setting.     

Properties and performance bounds for closed free choicesynchronized monoclass queueing networks

It is shown that many monoclass queuing networks (QN) with synchronizations can naturally be modeled with a subclass of Petri nets (PN) called free-choice nets (FC), for which a wide gamut of qualitative behavioral and structural results have been derived. Some of these net theoretic results are used to characterize the ergodicity, boundedness, and liveness of closed free-choice synchronized QNs. Upper and lower throughput bounds are defined based on the mean value of the service times, without any assumption on the probability distributions (thus including both the deterministic and the stochastic cases). It is shown that monotonicity properties exist between the throughput bounds and the parameters of the model in terms of population and service times. Proposed are (theoretically polynomial and practically linear complexity) algorithms for the computation of these bounds, based on linear programming problems defined on the incidence matrix of the underlying FC net. Using classical laws from queuing theory, bounds are provided for mean queue lengths and response time     

Superposition properties and performance bounds of stochastictimed-event graphs

This paper addresses the performance evaluation of stochastic timed-event graphs. The transition firing times are random variables with general distribution. We first consider a stochastic timed-event graph in which the firing times are generated by time superposition (or addition) of two sets of random variable sequences. Properties of this system are established. Chiefly, we prove that the average cycle time is subadditive, i.e., it is smaller than the sum of the average cycle times of the two stochastic timed-event graphs in which the firing times are generated by one of the two sets of random variable sequences, respectively. Based on these superposition properties, we derive various upper bounds of the average cycle time of a general stochastic timed-event graph. In particular, we obtain upper bounds which converge to the exact average cycle time as the standard deviations of the firing times decrease. Finally, we derive performance bounds for stochastic timed-event graphs with bounded firing times     

Cycle time of stochastic event graphs: evaluation and markingoptimization

Addresses the performance evaluation and optimization of a strongly connected event graph with random firing times. The authors proposed an upper bound and a lower bound for the average cycle time of event graphs knowing the initial marking. The authors then prove that, under some weak conditions on the firing time distributions, it is possible to reach, on average, a cycle time smaller than any given value C* with a finite marking, assuming that C* is greater than the greatest firing time. Finally, the authors propose an heuristic algorithm to reach such an average cycle time while minimizing a p-invariant criterion     

Optimal scheduling of parallel queues using stochastic flow models

We consider a classic scheduling problem for optimally allocating a resource to multiple competing users and place it in the framework of Stochastic Flow Models (SFMs). We derive Infinitesimal Perturbation Analysis (IPA) gradient estimators for the average holding cost with respect to resource allocation parameters. These estimators are easily obtained from a sample path of the system without any knowledge of the underlying stochastic process characteristics. Exploiting monotonicity properties of these IPA estimators, we prove the optimality of the well-known cμ-rule for an arbitrary finite number of queues and stochastic processes under non-idling policies and linear holding costs. Further, using the IPA derivative estimates obtained along with a gradient-based optimization algorithm, we find optimal solutions to similar problems with nonlinear holding costs extending current results in the literature.     

Evolution of the nth probability density and entropy function in stochastic systems

The time evolution of dynamical systems with random initial conditions is considered, by deriving the nth order probability density of the stochastic process which describes the response of the system, and the entropy function related to the said distibution. A constructive theorem is proved, which enables the explicit calculation of the nth order probability density in terms of the statistics of the initial conditions. Some monotonicity properties of the entropy are derived, and the results are applied in two examples. The same analysis can be applied to the study of the probabilistic response of dynamical systems with constant random parameters and deterministic initial conditions.     

On-line fault detection in discrete event systems by Petri nets and integer linear programming

The paper addresses the fault detection problem for discrete event systems in a Petri Net (PN) framework. Assuming that the structure of the PN model and the initial marking are known, faults are modelled by unobservable transitions. Moreover, we assume that there may be additional unobservable transitions associated with the system legal behaviour and that the marking reached after the firing of any transition is unknown. The proposed diagnoser works on-line: it waits for the firing of an observable transition and employs an algorithm based on the definition and solution of some integer linear programming problems to decide whether the system behaviour is normal or exhibits some possible faults. The results characterize the properties that the PN modelling the system fault behaviour has to fulfill in order to reduce the on-line computational effort.     

Determination of firing times for the stochastic Fitzhugh-Nagumo neuronal model

We present for the first time an analytical approach for determining the time of firing of multicomponent nonlinear stochastic neuronal models. We apply the theory of first exit times for Markov processes to the Fitzhugh-Nagumo system with a constant mean gaussian white noise input, representing stochastic excitation and inhibition. Partial differential equations are obtained for the moments of the time to first spike. The observation that the recovery variable barely changes in the prespike trajectory leads to an accurate one-dimensional approximation. For the moments of the time to reach threshold, this leads to ordinary differential equations that may be easily solved. Several analytical approaches are explored that involve perturbation expansions for large and small values of the noise parameter. For ranges of the parameters appropriate for these asymptotic methods, the perturbation solutions are used to establish the validity of the one-dimensional approximation for both small and large values of the noise parameter. Additional verification is obtained with the excellent agreement between the mean and variance of the firing time found by numerical solution of the differential equations for the one-dimensional approximation and those obtained by simulation of the solutions of the model stochastic differential equations. Such agreement extends to intermediate values of the noise parameter. For the mean time to threshold, we find maxima at small noise values that constitute a form of stochastic resonance. We also investigate the dependence of the mean firing time on the initial values of the voltage and recovery variables when the input current has zero mean.     

Blocking a transition in a free choice net and what it tells about its throughput

In a live and bounded free choice Petri net, pick a non-conflicting transition. Then there exists a unique reachable marking in which no transition is enabled except the selected one. For a routed live and bounded free choice net, this property is true for any transition of the net. Consider now a live and bounded stochastic routed free choice net, and assume that the routings and the firing times are independent and identically distributed. Using the above results, we prove the existence of asymptotic firing throughputs for all transitions in the net. Furthermore, the vector of the throughputs at the different transitions is explicitly computable up to a multiplicative constant.     

Estimation methods for nonregenerative stochastic Petri nets

When a computer, manufacturing, telecommunication, or transportation system is modeled as a stochastic Petri net (SPN), many long-run performance characteristics of interest can be expressed as time-average limits of the associated marking process. For nets with generally-distributed firing times, such limits often cannot be computed analytically or numerically, but must be estimated using simulation. Previous work on estimation methods for SPNs has focused on the case in which there exists a sequence of regeneration points for the marking process of the net, so that point estimates and confidence intervals for time-average limits can be obtained using the regenerative method for analysis of simulation output. This paper is concerned with SPNs for which the regenerative method is not applicable. We provide conditions on the clock-setting distributions and new-marking probabilities of an SPN under which time-average limits are well defined and the output process of the simulation obeys a multivariate functional central limit theorem. It then follows from results of Glynn and Iglehart (1990) that methods based on standardized time series can be used to obtain strongly consistent point estimates and asymptotic confidence intervals for time-average limits. In particular, the method of batch means is applicable. Moreover, the methods of Munoz and Glynn can be used to obtain point estimates and confidence intervals for ratios of time-average limits. We illustrate our results using an SPN model of an interactive video-on-demand system     

Firing and enabling sequences estimation for timed Petri nets

Petri nets (PNs) are useful tools for the modeling and analysis of discrete event systems. This work deals with the estimation of firing and enabling sequences for timed transition PNs with unknown time delays. The marking and reserved marking of the places are measured online. The estimation problem has exact and approximated solutions that are described. Sufficient conditions are given on the measurement accuracy of the marking and reserved marking vectors, so that the estimation of firing and enabling sequences is an exact one. If the estimation provides several solutions, the PN is extended in order to give a unique solution. Numerical aspects of the estimation are also investigated. As a consequence of this, the proposed method provides interesting tools for the modeling, performance analysis, and above all the monitoring of manufacturing systems and road traffic networks     

Free-choice Petri nets-an algebraic approach

In this paper, we give evolution equations for free-choice Petri nets which generalize the [max, +]-algebraic setting already known for event graphs. These evolution equations can be seen as a coupling of two linear systems, a (min, +)-linear system and a quasi-(+, x)-linear one. This leads to new methods and algorithms to: 1) in the untimed case, check liveness and several other basic logical properties; 2) in the timed case, establish various conservation and monotonicity properties; and 3) in the stochastic case, check stability, i.e., the fact that the marking remains bounded in probability, and constructs minimal stationary regimes. The main tools for proving these properties are graph theory, idempotent algebras, and ergodic theory     

Stochastic Petri net representation of discrete event simulations

In the context of discrete event simulation, the marking of a stochastic Petri net (SPN) corresponds to the state of the underlying stochastic process of the simulation and the firing of a transition corresponds to the occurrence of an event. A study is made of the modeling power of SPNs with timed and immediate transitions, showing that such Petri nets provide a general framework for simulation. The principle result is that for any (finite or) countable state GSMP (generalized semi-Markov process) there exists an SPN having a marking process that mimics the GSMP in the sense that the two processes (and their underlying general state-space Markov chains) have the same finite dimensional distributions     

Basic Server Semantics and Performance Monotonicity of Continuous Petri Nets

Continuous Petri nets were introduced as an approximation to deal with the state explosion problem which can appear in discrete event models. When time is introduced, the flow through a fluidified transition can be defined in many ways. The most used in literature are constant and variable speed (David and Alla, Discrete, continuous and hybrid Petri nets, Springer-Verlag, 2005), which can be seen as some kind of finite and infinite server interpretations of the transitions behavior, and derived from stochastic (discrete) Petri nets (Silva and Recalde, Annu Rev Control 28(2):253–266, 2004). In this paper we will compare the results obtained with both relaxations for the broad class of mono-T-semiflow reducible nets, and prove that, under some frequently true conditions, infinite server semantics offers a throughput which is closer to the throughput of the discrete system in steady state. In the second part, it will be proved that the throughput of mono-T-semiflow reducible net systems is monotone with respect to the speed of the transitions and the initial marking of the net.     

Balancing stocks and backlogs with stochastic lead times: A special case

The paper gives compact, finite horizon and asymptotic results concerning an inventory system, that allows backlogging, with constant demand and costs but stochastic lead times, not necessarily i.i.d., under two special conditions. The special conditions are: (1) no crossovers of orders; (2) there are both shortage and stock build-up between any two consecutive orders. It is shown that the minimal total expected cost, namely, of holding inventory, shortages and replenishments, as well as the optimal replenishment times depend, among other parameters, only on the lead time variances as representatives of the stochastic component of the model. The results are direct extensions of the deterministic EOQ model and lend themselves to tractable sensitivity analysis. Further possible developments are discussed.     

时间Petri网的随机模拟

模拟是Peri网进行系统分析的常用方法之一。由于时间Petri网采用时间区间来描述变迁实施的时间范围,因此变迁的实施时间点在区间内是不确定的。提出了时间Petri网的随机模拟方法。该方法在变迁开始使能时,根据某种随机分布确定实施区间内的实施时间点;然后基于模拟仿真的实验数据,运用统计分析方法及算法,构造时间Petri网状态类树,计算变迁实施区间及实施概率,为时间Petri网的系统模拟提供了一种新的探索途径。     

Reachability analysis in T-invariant-less Petri nets

An algorithm for reachability analysis in place/transition Petri nets having no transition invariants (T-invariants) is proposed. Given a Petri net with initial and target markings, a so-called complemented Petri net is created first that consists of the given Petri net and an additional complementary transition. Thereby, the reachability task is reduced to computation and investigation of those minimal-support and linearly combined T-invariants of the complemented Petri net, in which the complementary transition fires only once. Then, for each T-invariant with a single firing of the complementary transition, the algorithm will try to create a reachability path from the given initial marking to the target marking.