Laplace Transform and Moments of Waiting Times in Poisson Driven (max,+) Linear Systems

(Max,+) linear systems can be used to represent stochastic Petri nets belonging to the class of event graphs. This class contains various instances of queueing networks like acyclic or cyclic fork-and-join queueing networks, finite or infinite capacity tandem queueing networks with various types of blocking, synchronized queueing networks and so on. It also contains some basic manufacturing models such as kanban networks, assembly systems and so forth.In their 1997 paper, Baccelli, Hasenfuss and Schmidt provide explicit expressions for the expected value of the waiting time of the nth customer in a given subarea of a (max,+) linear system. Using similar analysis, we present explicit expressions for the moments and the Laplace transform of transient waiting times in Poisson driven (max,+) linear systems. Furthermore, starting with these closed form expressions, we also derive explicit expressions for the moments and the Laplace transform of stationary waiting times in a class of (max,+) linear systems with deterministic service times. Examples pertaining to queueing theory are given to illustrate the results.     

Transient and stationary waiting times in (max,+)-linear systems with Poisson input

We consider a certain class of vectorial evolution equations, which are linear in the (max,+) semi-field. They can be used to model several Types of discrete event systems, in particular queueing networks where we assume that the arrival process of customers (tokens, jobs, etc.) is Poisson. Under natural Cramér Type conditions on certain variables, we show that the expected waiting time which the nth customer has to spend in a given subarea of such a system can be expanded analytically in an infinite power series with respect to the arrival intensity λ. Furthermore, we state an algorithm for computing all coefficients of this series expansion and derive an explicit finite representation formula for the remainder term. We also give an explicit finite expansion for expected stationary waiting times in (max,+)-linear systems with deterministic queueing services. This revised version was published online in June 2006 with corrections to the Cover Date.     

A characterisation of (max,+)-linear queueing systems

The (max,+)-algebra has been successfully applied to many areas of queueing theory, like stability analysis and ergodic theory. These results are mainly based on two ingredients: (1) a (max,+)-linear model of the time dynamic of the system under consideration, and (2) the time-invariance of the structure of the (max,+)-model. Unfortunately, (max,+)-linearity is a purely algebraic concept and it is by no means immediate if a queueing network admits a (max,+)-linear representation satisfying (1) and (2). In this paper we derive the condition a queueing network must meet if it is to have a (max,+)-linear representation. In particular, we study (max,+)-linear systems with time-invariant transition structures. For this class of systems, we find a surprisingly simple necessary and sufficient condition for (max,+)-linearity, based on the flow of customers through the network. This revised version was published online in June 2006 with corrections to the Cover Date.     

Asymptotics of stochastic networks with subexponential service times

We analyse the tail behaviour of stationary response times in the class of open stochastic networks with renewal input admitting a representation as (max,+)-linear systems. For a K-station tandem network of single server queues with infinite buffer capacity, which is one of the simplest models in this class, we first show that if the tail of the service time distribution of one server, say server i ₀ ∈ {1,...,K}, is subexponential and heavier than those of the other servers, then the stationary distribution of the response time until the completion of service at server j ⩾ i ₀ asymptotically behaves like the stationary response time distribution in an isolated single-server queue with server i ₀. Similar asymptotics are given in the case when several service time distributions are subexponential and asymptotically tail-equivalent. This result is then extended to the asymptotics of general (max,+)-linear systems associated with i.i.d. driving matrices having one (or more) dominant diagonal entry in the subexponential class. In the irreducible case, the asymptotics are surprisingly simple, in comparison with results of the same kind in the Cramér case: the asymptotics only involve the excess distribution of the dominant diagonal entry, the mean value of this entry, the intensity of the arrival process, and the Lyapunov exponent of the sequence of driving matrices. In the reducible case, asymptotics of the same kind, though somewhat more complex, are also obtained. As a direct application, we give the asymptotics of stationary response times in a class of stochastic Petri nets called event graphs. This is based on the assumption that the firing times are independent and that the tail of the firing times of one of the transitions is subexponential and heavier than those of the others. An extension of these results to nonrenewal input processes is discussed. Asymptotics of queue size processes are also considered. This revised version was published online in June 2006 with corrections to the Cover Date.     

Tails for (max, plus) recursions under subexponentiality

We study the stationary solution of a (max, plus)-linear recursion. Under subexponentiality assumptions on the input to the recursion, we obtain the tail asymptotics of certain (max, plus)-linear functionals of this solution. (Max, plus)-linear recursions arise from FIFO queueing networks; more specifically, from stochastic event graphs. In the event graph setting, two special cases of our results are of particular interest and have already been investigated in the literature. First, the functional may correspond to the end-to-end sojourn time of a customer. Second, for two queues in tandem, the functional may correspond to the sojourn time in the second queue. Our results allow for more general networks, which we illustrate by studying the tail asymptotics of the resequencing delay due to multi-path routing.     

Asymptotics of Subexponential Max Plus Networks: the Stochastic Event Graph Case

We calculate the exact tail asymptotics of stationary response times for open stochastic event graphs, in the irreducible and reducible cases. These networks admit a representation as (max,?plus)-linear systems in a random medium. We study the case of renewal input and i.i.d. service times with subexponential distributions. We show that the stationary response times have tail asymptotics of the same order as the integrated tail of service times. The mutiplicative constants only involve the intensity of the arrival process and the (max,?plus)-Lyapunov exponents of the sequence of (max,?plus)-matrices.     

The Discrete-Time GI/Geo/1 Queue with Multiple Vacations

We study a discrete-time GI/Geo/1 queue with server vacations. In this queueing system, the server takes vacations when the system does not have any waiting customers at a service completion instant or a vacation completion instant. This type of discrete-time queueing model has potential applications in computer or telecommunication network systems. Using matrix-geometric method, we obtain the explicit expressions for the stationary distributions of queue length and waiting time and demonstrate the conditional stochastic decomposition property of the queue length and waiting time in this system.     

On the burnside problem for semigroups of matrices in the (max,+) algebra

We show that the answer to the Burnside problem is positive for semigroups of matrices with entries in the (max,+)-algebra (that is, the semiring (ℝ∪{−∞},max,+)), and also for semigroups of (max,+)-linear projective maps with rational entries. An application to the estimation of the Lyapunov exponent of certain products of random matrices is also discussed.     

Stochastic Recursive Equations with Applications to Queues with Dependent Vacations

We focus on a special class of nonlinear multidimensional stochastic recursive equations in which the coefficients are stationary ergodic (not necessarily independent). Under appropriate conditions, an explicit ergodic stationary solution for these equations is obtained and the convergence to this stationary regime is established. We use these results to analyze several queueing models with vacations. We obtain explicit solutions for several performance measures for the case of general non-independent vacation processes. We finally extend some of these results to polling systems with general vacations.     

Effects of service disciplines inG/GI/s queueing systems

Transient extremal properties of some service disciplines are established in theG/GI/s queueing system for the minimization and maximization of the expectations of the Schur convex functions, convex symmetric functions and the sums of convex functions of the waiting times, response times, lag times and latenesses. When resequencing is required in the system, the FCFS and LCFS disciplines are shown to minimize and maximize, respectively, the expectations of any increasing functions of the end-to-end delays. All of these results are presented in terms of stochastic orderings. The paper concludes with extensions of the results to the stationary regime and to tandem as well as general queueing networks.This work was supported in part by the National Science Foundation under grant ASC 88-8802764.The work of this author was also partially supported by CEC DG-XIII under the ESPRIT-BRA grant QMIPS.     

First passage times for Markov renewal processes and applications

This paper proposes a uniformly convergent algorithm for the joint transform of the first passage time and the first passage number of steps for general Markov renewal processes with any initial state probability vector. The uniformly convergent algorithm with arbitrarily prescribed error can be efficiently applied to compute busy periods, busy cycles, waiting times, sojourn times, and relevant indices of various generic queueing systems and queueing networks. This paper also conducts a numerical experiment to implement the proposed algorithm.     

排队系统中的泰勒展开方法

综述了排队系统中的泰勒展开方法。它由Gong和Hu在1990s首次提出,并在最近几年里有了一些新的发展。首先,通过GI/GI/1队列的简单例子介绍其基本原理;其次,展示如何应用该方法分析相关性队列和离去过程;然后,阐述如何基于该方法发展排队网络近似的高阶矩方法;最后,讨论未来的几个可能研究方向。     

Approximation of the non-stationary M(t)/M(t)/c(t)-queue using stationary queueing models: The stationary backlog-carryover approach

This paper proposes a new approach for the time-dependent analysis of stochastic and non-stationary queueing systems. The analysis of a series of stationary queueing models leads to a new approximation of time-dependent performance measures.     

Light tail asymptotics in multidimensional reflecting processes for queueing networks

We are concerned with the stationary distributions of reflecting processes on multidimensional nonnegative orthants and other related processes, provided they exist. Such stationary distributions arise in performance evaluation for various queueing systems and their networks. However, it is very hard to obtain them analytically, so our interest is directed to analytically tractable characteristics. For this, we consider tail asymptotics of the stationary distributions.     

Optimal Sequencing of Servers in the Two-Station Series Queueing System

This paper deals with determining an optimal sequence of service stations in a series queueing system. Optimality is defined in terms of the total time spent waiting for service. Sequences are compared on the basis of the moments of their steady-state total waiting time. In addition, the rules of stochastic dominance are applied which allow comparison of sequences on the basis of their waiting time distributions. Analytical results in the sequencing of service stations in series queues have been limited to stations with constant or exponential service times. This study extends the investigation to service distributions with varying degrees of statistical regularity given by the family of Erlang distributions.Relationships are developed for predicting optimal sequences. Validation is accomplished by simulating a number of systems and comparing the waiting time distribution functions for each sequence. The relationships are shown to be good predictors and useful in the study and design of systems of servers in series.     

A survey on retrial queues

Queueing systems in which arriving customers who find all servers and waiting positions (if any) occupied may retry for service after a period of time are called retrial queues or queues with repeated orders. Retrial queues have been widely used to model many problems in telephone switching systems, telecommunication networks, computer networks and computer systems. In this paper, we discuss some important retrial queueing models and present their major analytic results and the techniques used. Our concentration is mainly on single-server queueing models. Multi-server queueing models are briefly discussed, and interested readers are referred to the original papers for details. We also discuss the stochastic decomposition property which commonly holds in retrial queues and the relationship between the retrial queue and the queue with server vacations.     

Analysis of the M1,M2/G/1 G-queueing system with retrial customers

We consider a single server retrial queue with waiting places in service area and three classes of customers subject to the server breakdowns and repairs. When the server is unavailable, the arriving class-1 customer is queued in the priority queue with infinite capacity whereas class-2 customer enters the retrial group. The class-3 customers which are also called negative customers do not receive service. If the server is found serving a customer, the arriving class-3 customer breaks the server down and simultaneously deletes the customer under service. The failed server is sent to repair immediately and after repair it is assumed as good as new. We study the ergodicity of the embedded Markov chains and their stationary distributions. We obtain the steady-state solutions for both queueing measures and reliability quantities. Moreover, we investigate the stochastic decomposition law, the busy period of the system and the virtual waiting times. Finally, an application to cellular mobile networks is provided and the effects of various parameters on the system performance are analyzed numerically.     

State-dependent Coupling of Quasireversible Nodes

The seminal paper of Jackson began a chain of research on queueing networks with product-form stationary distributions which continues strongly to this day. Hard on the heels of the early results on queueing networks followed a series of papers which discussed the relationship between product-form stationary distributions and the quasireversibility of network nodes. More recently, the definition of quasireversibility and the coupling mechanism between nodes have been extended so that they apply to some of the later product-form queueing networks incorporating negative customers, signals, and batch movements.In parallel with this research, it has been shown that some special queueing networks can have arrival and service parameters which depend upon the network state, rather than just the node state, and still retain a generalised product-form stationary distribution.In this paper we begin by offering an alternative proof of a product-form result of Chao and Miyazawa and then build on this proof by postulating a state-dependent coupling mechanism for a quasireversible network. Our main theorem is that the resultant network has a generalised product form stationary distribution. We conclude the paper with some examples.     

Stationary waiting time derivatives

We investigate the stability of waiting-time derivatives when inputs to a queueing system-service times and interarrival times-depend on a parameter. We give conditions under which the sequence of waiting-time derivatives admits a stationary distribution, and under which the derivatives converge to the stationary regime from all initial conditions. Further hypotheses ensure that the expectation of a stationary waiting-time derivative is, in fact, the derivative of the expected stationary waiting time. This validates the use of simulation-based infinitesimal perturbation analysis estimates with a variety of queueing processes.We examine waiting-time sequences satisfying recursive equations. Our basic assumption is that the input and its derivatives are stationary and ergodic. Under monotonicity conditions, the method of Loynes establishes the convergence of the derivatives. Even without such conditions, the derivatives obey a linear difference equation with random coefficients, and we exploit this fact to find stability conditions.