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.     

Expansions for Joint Laplace Transform of Stationary Waiting Times in (max,+)-linear Systems with Poisson Input

We give a Taylor series expansion for the joint Laplace transform of stationary waiting times in open (max,+)-linear stochastic systems with Poisson input. Probabilistic expressions are derived for coefficients of all orders. Even though the computation of these coefficients can be hard for certain systems, it is sufficient to compute only a few coefficients to obtain good approximations (especially under the assumption of light traffic). Combining this new result with the earlier expansion formula for the mean stationary waiting times, we also provide a Taylor series expansion for the covariance of stationary waiting times in such systems.It is well known that (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. The applicability of this expansion technique is discussed for several systems of this type.     

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.     

Error analysis for regenerative queueing estimators with special reference to gradient estimators via likelihood ratio

The performance of telecommunications systems is typically estimated (either analytically or by simulation) via queueing theoretic models. The gradient of the expected performance with respect to the various parameters (such as arrival rate or service rate) is very important as it not only measures the sensitivity to change, but is also needed for the solution of optimization problems. While the estimator for the expected performance is the sample mean of the simulation experiment, there are several possibilities for the estimator of the gradient. They include the obvious finite difference approximation, but also other recently advocated techniques, such as estimators derived from likelihood ratio transformations or from infinitesimal perturbations. A major problem in deciding upon which estimator to use and in planning the length of the simulation has been the scarcity of analytical error calculations for estimators of queueing models. It is this question that we answer in this paper for the waiting time moments (of arbitrary order) of theM / G / 1 queue by using the queueing analysis technique developed by Shalmon. We present formulas for the error variance of the estimators of expectation and of its gradient as a function of the simulation length; at arbitrary traffic intensity the formulas are recursive, while the heavy traffic approximations are explicit and of very simple form. For the gradient of the mean waiting time with respect to the arrival (or service) rate, and at 1 percent relative precision, the heavy traffic formulas show that the likelihood ratio estimator for the gradient reduces the length of the simulation required by the finite difference estimator by about one order of magnitude; further increasing the relative precision by a factor increases the reduction advantage by the same factor. At any relative precision, it exceeds the length of the simulation required for the estimation of the mean with the same relative precision by about one order of magnitude. While strictly true for theM / G / 1 queue, the formulas can also be used as guidelines in the planning of queueing simulations and of stochastic optimizations of complex queueing systems, particularly those with Poisson arivals.     

Diffusion Approximations for Queues with Markovian Bases

Consider a base family of state-dependent queues whose queue-length process can be formulated by a continuous-time Markov process. In this paper, we develop a piecewise-constant diffusion model for an enlarged family of queues, each of whose members has arrival and service distributions generalized from those of the associated queue in the base. The enlarged family covers many standard queueing systems with finite waiting spaces, finite sources and so on. We provide a unifying explicit expression for the steady-state distribution, which is consistent with the exact result when the arrival and service distributions are those of the base. The model is an extension as well as a refinement of the M/M/s-consistent diffusion model for the GI/G/s queue developed by Kimura [13] where the base was a birth-and-death process. As a typical base, we still focus on birth-and-death processes, but we also consider a class of continuous-time Markov processes with lower-triangular infinitesimal generators.     

On the Counting Process for a Class of Markovian Arrival Processes with an Application to a Queueing System

In this paper, we consider the counting process for a class of Markovian arrival processes (MAPs). We assume that the representing matrices in such MAPs are expanded in terms of matrix representations of the standard generators in the Lie algebra of the special linear group. The primary purpose of this paper is to construct an explicit solution of the time-dependent distribution and factorial moments of the number of arrival events in (0,t] of the counting process for this class of MAPs. Our construction relies on the Baker–Hausdorff lemma and the specific structure of the representing matrices. To investigate the efficiency of CPU usage with the explicit solution, we have conducted numerical experiments on computing the time-dependent distribution of the counting process through the explicit solution and uniformization-based method. We show that the CPU times required to compute the time-dependent distribution of the number of arrival events in (0,t] through the explicit solution have little sensitivity to t, while the consumption of CPU times with the uniformization-based method becomes greater as t increases. For illustrative purposes, we present a system performance analysis of a queueing system for possible use in automatic call distribution (ACD) systems. As an application of the explicit solution, we use it to express the waiting time distribution of the queueing system. Some numerical examples are also given with comparisons to computer simulations.AMS subject classification: 60K20, 60K25, 68M20This revised version was published online in June 2005 with corrected coverdate     

Finite-Buffer Queues with Workload-Dependent Service and Arrival Rates

We consider M/G/1 queues with workload-dependent arrival rate, service speed, and restricted accessibility. The admittance of customers typically depends on the amount of work found upon arrival in addition to its own service requirement. Typical examples are the finite dam, systems with customer impatience and queues regulated by the complete rejection discipline. Our study is motivated by queueing scenarios where the arrival rate and/or speed of the server depends on the amount of work present, like production systems and the Internet.First, we compare the steady-state distribution of the workload in two finite-buffer models, in which the ratio of arrival and service speed is equal. Second, we find an explicit expression for the cycle maximum in an M/G/1 queue with workload-dependent arrival and service rate. And third, we derive a formal solution for the steady-state workload density in case of restricted accessibility. The proportionality relation between some finite and infinite-buffer queues is extended. Level crossings and Volterra integral equations play a key role in our approach.AMS subject classification: 60K25, 90B22     

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.     

Analysis of an SPP/G/1 system with multiple vacations and E-limited service discipline

Many researchers have studied variants of queueing systems with vacations. Most of them have dealt with M/G/1 systems and have explicitly analyzed some of their performance measures, such as queue length, waiting time, and so on. Recently, studies on queueing systems whose arrival processes are not Poissonian have appeared. We consider a single server queueing system with multiple vacations and E-limited service discipline, where messages arrive to the system according to a switched Poisson process. First, we consider the joint probability density functions of the queue length and the elapsed service time or the elapsed vacation time. We derive the equations for these pdf's, which include a finite number of unknown values. Using Rouché's theorem, we determine the values from boundary conditions. Finally, we derive the transform of the stationary queue length distribution explicitly.     

Analysis of a finite buffer model with two servers and two nonpreemptive priority classes

In this paper, we analyze a finite buffer queueing model with two servers and two nonpreemptive priority service classes. The arrival streams are independent Poisson processes, and the service times of the two classes are exponentially distributed with different means. One of the two servers is reserved exclusively for one class with high priority and the other server serves the two classes according to a nonpreemptive priority service schedule. For the model, we describe its dynamic behavior by a four-dimensional continuous-time Markov process. Applying recursive approaches we present the explicit representation for the steady-state distribution of this Markov process. Then, we calculate the Laplace–Stieltjes Transform and the steady-state distribution of the actual waiting times of two classes of customers. We also give some numerical comparison results with other queueing models.     

Assembly-like queues with finite capacity: Bounds,asymptotics and approximations

In this paper we study a queueing model of assembly-like manufacturing operations. This study was motivated by an examination of a circuit pack testing procedure in an AT & T factory. However, the model may be representative of many manufacturing assembly operations. We assume that customers fromn classes arrive according to independent Poisson processes with the same arrival rate into a single-server queueing station where the service times are exponentially distributed. The service discipline requires that service be rendered simultaneously to a group of customers consisting of exactly one member from each class. The server is idle if there are not enough customers to form a group. There is a separate waiting area for customers belonging to the same class and the size of the waiting area is the same for all classes. Customers who arrive to find the waiting area for their class full, are lost. Performance measures of interest include blocking probability, throughput, mean queue length and mean sojourn time. Since the state space for this queueing system could be large, exact answers for even reasonable values of the parameters may not be easy to obtain. We have therefore focused on two approaches. First, we find upper and lower bounds for the mean sojourn time. From these bounds we obtain the asymptotic solutions as the arrival rate (waiting room, service rate) approaches zero (infinity). Second, for moderate values of these parameters we suggest an approximate solution method. We compare the results of our approximation against simulation results and report good correspondence.     

Convergence of a queueing system in heavy traffic with general patience-time distributions

We analyze a sequence of single-server queueing systems with impatient customers in heavy traffic. Our state process is the offered waiting time, and the customer arrival process has a state dependent intensity. Service times and customer patient-times are independent; i.i.d. with general distributions subject to mild constraints. We establish the heavy traffic approximation for the scaled offered waiting time process and obtain a diffusion process as the heavy traffic limit. The drift coefficient of this limiting diffusion is influenced by the sequence of patience-time distributions in a non-linear fashion. We also establish an asymptotic relationship between the scaled version of offered waiting time and queue-length. As a consequence, we obtain the heavy traffic limit of the scaled queue-length. We introduce an infinite-horizon discounted cost functional whose running cost depends on the offered waiting time and server idle time processes. Under mild assumptions, we show that the expected value of this cost functional for the n-th system converges to that of the limiting diffusion process as n tends to infinity.     

Optimal design of multi‐server Markovian queues with polynomial waiting and service costs

This paper is concerned with the optimal design of queueing systems. The main decisions in the design of such systems are the number of servers, the appropriate control to have on the arrival rates, and the appropriate service rate these servers should possess. In the formulation of the objective function to this problem, most publications use only linear cost rates. The linear rates, especially for the waiting cost, do not accurately reflect reality. Although there are papers involving nonlinear cost functions, no paper has ever considered using polynomial cost functions of degree higher than two. This is because simple formulas for computing the higher moments are not available in the literature. This paper is an attempt to fill this gap in the literature. Thus, the main contributions of our work are as follows: (i) the derivation of a very simple formula for the higher moments of the waiting time for the M/M/s queueing system, which requires only the knowledge of the expected waiting time; (ii) proving their convexity with respect to the design variables; and (iii) modeling and solving more realistic design problems involving general polynomial cost functions. We also focus on simultaneous optimization of the staffing level, arrival rate and service rate. Copyright © 2013 John Wiley & Sons, Ltd.     

Markov-modulatedPH/G/1 queueing systems

We study a PH/G/1 queue in which the arrival process and the service times depend on the state of an underlying Markov chain J(t) on a countable state spaceE. We derive the busy period process, waiting time and idle time of this queueing system. We also study the Markov modulated E_K/G/1 queueing system as a special case.     

Moments of first passage times in general birth–death processes

We consider ordinary and conditional first passage times in a general birth–death process. Under existence conditions, we derive closed-form expressions for the kth order moment of the defined random variables, k ≥ 1. We also give an explicit condition for a birth–death process to be ergodic degree 3. Based on the obtained results, we analyze some applications for Markovian queueing systems. In particular, we compute for some non-standard Markovian queues, the moments of the busy period duration, the busy cycle duration, and the state-dependent waiting time in queue.      

The MacLaurin expansion for a G/G/1 queue with Markov-modulated arrivals and services

Consider a Markov-modulated G/G/1 queueing system in which the arrival and the service mechanisms are controlled by an underlying Markov chain. The classical approaches to the waiting time of this type of queueing system have severe computational difficulties. In this paper, we develop a numerical algorithm to calculate the moments of the waiting time based on Gong and Hu's idea. Our numerical results show that the algorithm is powerful. A matrix recursive equation for the moments of the waiting time is also given under certain conditions.     

Equilibrium arrival times to a queue with order penalties

Suppose customers need to choose when to arrive to a congested queue with some desired service at the end, provided by a single server that operates only during a certain time interval. We study a model where the customers incur not only congestion (waiting) costs but also penalties for their index of arrival. Arriving before other customers is desirable when the value of service decreases with every admitted customer. This may be the case for example when arriving at a concert or a bus with unmarked seats or going to lunch in a busy cafeteria. We provide game theoretic analysis of such queueing systems with a given number of customers, specifically we characterize the arrival process which constitutes a symmetric Nash equilibrium.     

Analysis of customers’ impatience in queues with server vacations

Many models for customers impatience in queueing systems have been studied in the past; the source of impatience has always been taken to be either a long wait already experienced at a queue, or a long wait anticipated by a customer upon arrival. In this paper we consider systems with servers vacations where customers’ impatience is due to an absentee of servers upon arrival. Such a model, representing frequent behavior by waiting customers in service systems, has never been treated before in the literature. We present a comprehensive analysis of the single-server, M/M/1 and M/G/1 queues, as well as of the multi-server M/M/c queue, for both the multiple and the single-vacation cases, and obtain various closed-form results. In particular, we show that the proportion of customer abandonments under the single-vacation regime is smaller than that under the multiple-vacation discipline. This work was supported by the Euro-Ngi network of excellence.     

Convexity of single stage queueing systems with bulk arrival

In this paper we study the convexity of the waiting time, workload and the number of jobs in single stage queueing systems with respect to the bulk size of the arrival process. In particular we show that the number of jobs in a single server queueing systemG ^[x ]/GI/1 and in a multiple server queueing systemG ^[x]/M/c with bulk sizesx=(x ₁ ,x ₂ ,x ₃ ,...) is componentwise convex inx. This is in the sense of the sample path convexity introduced in Shaked and Shanthikumar [11]. These results have applications in the stochastic comparison of bulk arrival queueing systems.Research supported in part by NSF grant DDM-9113008.     

Working vacations queueing model with multiple types of server breakdowns

This paper deals with a single server working vacation queueing model with multiple types of server breakdowns. In a working vacations queueing model, the server works at a different rate instead of being completely idle during the vacation period; the arrival rate varies according to the server’s status. It is assumed that the server is subject to interruption due to multiple types of breakdowns and is sent immediately for repair. Each type of breakdown requires a finite random number of stages of repair. The life time of the server and the repair time of each phase are assumed to be exponentially distributed. We propose a matrix–geometric approach for computing the stationary queue length distribution. Various performance indices namely the expected length of busy period, the expected length of working vacation period, the mean waiting time and average delay, etc. are established. In order to validate the analytical approach, by taking illustration, we compute numerical results. The sensitivity analysis is also performed to explore the effect of different parameters.