A unified algorithm for computing the stationary queue length distributions inM(k)/G/1/N and GI/M(k)/1/N queues

An iterative algorithm is developed for computing numerically the stationary queue length distributions in M/G/1/N queues with arbitrary state-dependent arrivals, or simply M(k)/G/1/N queues. The only input requirement is the Laplace-Stieltjes transform of the service time distribution.In addition, the algorithm can also be used to obtain the stationary queue length distributions in GI/M/1/N queues with state-dependent services, orGI/M(k)/1/N, after establishing a relationship between the stationary queue length distributions inGI/M(k)/1/N and M(k)/G/1/N+1 queues.Finally, we elaborate on some of the well studied special cases, such asM/G/1/N queues,M/G/1/N queues with distinct arrival rates (which includes the machine interference problems), andGI/M/C/N queues. The discussions lead to a simplified algorithm for each of the three cases.     

Two finite-difference methods for solving MAP(t)/PH(t)/1/K queueing models

In this paper two solution methods to the MAP(t)/PH(t)/1/K queueing model are introduced, one based on the Backwards Euler Method and the other on the Uniformization Method. Both methods use finite-differencing with a discretized, adaptive time-mesh to obtain time-dependent values for the entire state probability vector. From this vector, most performance parameters such as expected waiting time and expected number in the system can be computed. Also presented is a technique to compute the entire waiting (sojourn) time distribution as a function of transient time. With these two solution methods one can examine any transient associated with the MAP(t)/PH(t)/1/K model including time-varying arrival and/or service patterns. Four test cases are used to demonstrate the effectiveness of these methods. Results from these cases indicate that both methods provide fast and accurate solutions to a wide range of transient scenarios. This revised version was published online in June 2006 with corrections to the Cover Date.     

A Polynomial Factorization Approach for the Discrete Time GIX/>G/1/K Queue

This paper proposes a polynomial factorization approach for queue length distribution of discrete time GI ^X /G/1 and GI _X /G/1/K queues. They are analyzed by using a two-component state model at the arrival and departure instants of customers. The equilibrium state-transition equations of state probabilities are solved by a polynomial factorization method. Finally, the queue length distributions are then obtained as linear combinations of geometric series, whose parameters are evaluated from roots of a characteristic polynomial.     

First-passage-time and busy-period distributions of discrete-time Markovian queues:Geom(n)/Geom(n)/1/N

This paper gives simple explicit solutions of various first-passage-time distributions for a general class of discrete-time queueing models under arbitrary initial conditions, state-dependent transition probabilities and the finite waiting room. Explicit closed form expressions are obtained in terms of roots. These expressions are then used to get numerical as well as graphical results. Explicit closed-form expressions are also deduced for the continuous-time models including the busy-period distributions. The analysis is then extended to cover the case of two absorbing states.     

Probability analysis of the repairable queueing systemM/G(E k /H)/1

The repairable queueing system (RQS) in which the server has an exponential lifetime distribution has been studied in several articles [1–4]. Here, we deal with the new RQSM/G(E _k /H)/1 in which the lifetime distribution of the server is Erlangian. By forming a vector Markov process, i.e. by using the method of supplementary variables, we obtained some system characters, the reliability indices of the server, and the time distribution of a customer spent on the server. For this RQS, the generalized service time distribution of each customer will depend on the remainder life of the server. Based on this, a new kind of queues, for which the service time distributions are chosen by the customers in some stochastic manner, appears in queueing theory.Project supported by the National Natural Science Foundation of China.     

Markov renewal queues of M/M(a,d)/l/(b,n) system-part i

This paper discusses a general bulk service queue which falls into the Markov renewal class. Applying an analysis similar to the one by Hunter (1983) for M/M1/N type of feedback queues, certain properties of discrete and continuous time queue length processe are studied here. The results and formulas are then applied to a numerical illustration.     

Threshold policies for controlled retrial queues with heterogeneous servers

Retrial queues are an important stochastic model for many telecommunication systems. In order to construct competitive networks it is necessary to investigate ways for optimal control. This paper considers K -server retrial systems with arrivals governed by Neut' Markovian arrival process, and heterogeneous service time distributions of general phase-type. We show that the optimal policy which minimizes the number of customers in the system is of a threshold type with threshold levels depending on the states of the arrival and service processes. An algorithm for the numerical evaluation of an optimal control is proposed on the basis of Howar's iteration algorithm. Finally, some numerical results will be given in order to illustrate the system dynamics. AMS subject classification: 60K25 93E20     

The Periodic BMAP/PH/c Queue

In queueing theory, most models are based on time-homogeneous arrival processes and service time distributions. However, in communication networks arrival rates and/or the service capacity usually vary periodically in time. In order to reflect this property accurately, one needs to examine periodic rather than homogeneous queues. In the present paper, the periodic BMAP/PH/c queue is analyzed. This queue has a periodic BMAP arrival process, which is defined in this paper, and phase-type service time distributions. As a Markovian queue, it can be analysed like an (inhomogeneous) Markov jump process. The transient distribution is derived by solving the Kolmogorov forward equations. Furthermore, a stability condition in terms of arrival and service rates is proven and for the case of stability, the asymptotic distribution is given explicitly. This turns out to be a periodic family of probability distributions. It is sketched how to analyze the periodic BMAP/M _t /c queue with periodically varying service rates by the same method.     

Empirical Bayes estimation for queueing systems and networks

Empirical Bayes estimators are derived for standardM/M/1 queues,M/M/1 queues with state-dependent arrival and service rates, finite capacityM/M/1 queues with state-dependent rates and for open Jackson networks. The asymptotic properties of the empirical Bayes estimators are derived both with respect to the conditional distribution of the observations given the parameters, and with respect to the joint distribution of the observations and the parameters.     

Exact and approximate numerical solutions of steady-state distributions arising in the queueGI/G/1

In this paper we first obtain, in a unified way, closed-form analytic expressions in terms of roots of the so-called characteristic equation (c.e.), and then discuss the exact numerical solutions of steady-state distributions of (i) actual queueing time, (ii) virtual queueing time, (iii) actual idle time, and (iv) interdeparture time for the queueGI/R/1, whereR denotes the class of distributions whose Laplace-Stieltjes transforms (LSTs) are rational functions (ratios of a polynomial of degree at mostn to a polynomial of degreen). For the purpose of numerical discussions of idle- and interdeparture-time distributions, the interarrival-time distribution is also taken to belong to the classR. It is also shown that numerical computations of the idle-time distribution ofR/G/1 queues can be done even ifG is not taken asR. Throughout the discussions it is assumed that the queue discipline is first-come-first-served (FCFS). For the tail of the actual queueing-time distribution ofGI/R/1, approximations in terms of one or more roots of the c.e. are also discussed. If more than one root is used, they are taken in ascending order of magnitude. Numerical aspects have been tested for a variety of complex interarrival- and service-time distributions. The analysis is not restricted to generalized distributions with phases such as Coxian-n (C _n ), but also covers nonphase type distributions such as uniform (U) and deterministic (D). Some numerical results are also presented in the form of tables and figures. It is expected that the results obtained from the present study should prove to be useful not only to practitioners, but also to queueing theorists who would like to test the accuracies of inequalities, bounds or approximations.     

Queue-length and waiting-time distributions of discrete-time GI X/Geom/ 1 queueing systems with early and late arrivals

In this paper, we give a unified approach to solving discrete-time GI ^X/Geom/ 1 queues with batch arrivals. The analysis has been carried out for early- and late-arrival systems using the supplementary variable technique. The distributions of numbers in systems at prearrival epochs have been expressed in terms of roots of associated characteristic equations. Furthermore, distributions at arbitrary as well as outside observer's observation epochs have been obtained using the relation derived in this paper. We also present delay analyses for both the systems. Numerical results are presented for various interarrival-time and batch-size distributions. This revised version was published online in June 2006 with corrections to the Cover Date.     

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.     

A numerically efficient method for the MAP/D/1/K queue via rational approximations

The Markovian Arrival Process (MAP), which contains the Markov Modulated Poisson Process (MMPP) and the Phase-Type (PH) renewal processes as special cases, is a convenient traffic model for use in the performance analysis of Asynchronous Transfer Mode (ATM) networks. In ATM networks, packets are of fixed length and the buffering memory in switching nodes is limited to a finite numberK of cells. These motivate us to study the MAP/D/1/K queue. We present an algorithm to compute the stationary virtual waiting time distribution for the MAP/D/1/K queue via rational approximations for the deterministic service time distribution in transform domain. These approximations include the well-known Erlang distributions and the Padé approximations that we propose. Using these approximations, the solution for the queueing system is shown to reduce to the solution of a linear differential equation with suitable boundary conditions. The proposed algorithm has a computational complexity independent of the queue storage capacityK. We show through numerical examples that, the idea of using Padé approximations for the MAP/D/1/K queue can yield very high accuracy with tractable computational load even in the case of large queue capacities.This work was done when the author was with the Bilkent University, Ankara, Turkey and the research was supported by TÜBITAK under Grant No. EEEAG-93.     

服务台休假的GI/Geom/1离散时间排队

本文研究了具有位相型休假、位相型启动和单重几何休假的离散时间排队,假定 顾客到达间隔服从一般分布,服务时间服从几何分布,运用矩阵解析方法我们得到了这 些排队系统中顾客在到达时刻稳态队长分布及其随机分解.     

Approximating nonstationaryPh(t)/M(t)/s/c queueing systems

Nonstationary phase processes are defined and a surrogate distribution approximation (SDA) method for analyzing transient and nonstationary queueing systems with nonstationary phase arrival processes is presented. Regardless of system capacityc, the SDA method requires the numerical solution of only 6K differential equations, whereK is the number of phases in the arrival process, compared to theK(c+1) Kolmogorov forward equations required for the classical method of solution. Time-dependent approximations of mean and variance of the number of entities in the system and the number of busy servers are obtained. Empirical test results over a wide range of systems indicate the SDA is quite accurate.This research was partially funded by National Science Foundation grant ECS-8404409.     

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.      

M/G/1/K queues withN-policy and setup times

A steady-state analysis is given for M/G/1/K queues with combinedN-policy and setup times before service periods. The queue length distributions and the mean waiting times are obtained for the exhaustive service system, the gated service system, the E-limited service system, and the G-limited service system. Numerical examples are also provided.     

The Weight Distribution of C 5(1, n)

In [2] the codes C _q (r,n) over were introduced. These linear codes have parameters , can be viewed as analogues of the binary Reed-Muller codes and share several features in common with them. In [2], the weight distribution of C ₃(1,n) is completely determined.In this paper we compute the weight distribution of C ₅(1,n). To this end we transform a sum of a product of two binomial coefficients into an expression involving only exponentials an Lucas numbers. We prove an effective result on the set of Lucas numbers which are powers of two to arrive to the complete determination of the weight distribution of C ₅(1,n). The final result is stated as Theorem 2.     

Empirical Bayesian analysis for traffic intensity:M/M/1 queues with covariates

In this paper, we consider a set of individualM/M/1 queues in which variations in both arrival rates and service rates are partly explained by some covariates representing associated characteristics of individual queues. The random error that takes into account the remaining variation is assumed to follow a gamma distribution. Bayes and empirical Bayes procedures are suggested to make inferences concerning individual traffic intensity parameters that can be applied to several industrial queueing problems.