Tables for M/G/c queuing systems with phase-type service

Currently much research is done on the development of simple approximations for complex queuing systems. This practically important research is usually hampered by the fact that no exact results are available for a thorough testing of the approximations. In this paper we give for several M/G/c queuing systems with phase-type service the exact values for both the delay probability and the first two moments of the queuing time. These tables considerably extend the widely used Hillier-Lo tables which only consider Erlangian service and small values for the number of servers. The aim of the publication of our tables is to supply much needed test material to the research community and in this way to contribute to further progress in the research on queuing approximations. We present the result of the testing of several existing approximations. Also, the tables provide the practitioner with numerical results useful to design queuing systems.     

Analyticity of single-server queues in light traffic

Recently, several methods have been proposed to approximate performance measures of queueing systems based on their light traffic derivatives, e.g., the MacLaurin expansion, the Padé approximation, and interpolation with heavy traffic limits. The key condition required in all these approximations is that the performance measures be analytic when the arrival rates equal to zero. In this paper, we study theGI/G/1 queue. We show that if the c.d.f. of the interarrival time can be expressed as a MacLaurin series over [0, ), then the mean steady-state system time of a job is indeed analytic when the arrival rate to the queue equals to zero. This condition is satisfied by phase-type distributions but not c.d.f.'s without support [0, ), such as uniform and shifted exponential distributions. In fact, we show through two examples that the analyticity does not hold for most commonly used distribution functions which do not satisfy this condition.     

A graphical investigation of error bounds for moment-based queueing approximations

Many approximations of queueing performance measures are based on moment matching. Empirical and theoretical results show that although approximations based on two moments are often accurate, two-moment approximations can be arbitrarily bad and sometimes three-moment approximations are far better. In this paper, we investigate graphically error bounds for two- and three-moment approximations of three performance measures forGI/M/ · type models. Our graphical analysis provides insight into the adequacy of two- and three-moment approximations as a function of standardized moments of the interarrival-time distribution. We also discuss how the behavior of these approximations varies with other model parameters and with the performance measure being approximated.     

Probability masses fitting in the analysis of manufacturing flow lines

The analysis of manufacturing systems with finite capacity and with general service time distributions is made of two steps: the distributions have first to be transformed into tractable phase-type distributions, and then the modified system can be analytically modelled. In this paper, we propose a new alternative in order to build tractable phase-type distributions, and study its effects on the global modelling process. Called “probability masses fitting” (PMF), the approach is quite simple: the probability masses on regular intervals are computed and aggregated on a single value in the corresponding interval, leading to a discrete distribution. PMF shows some interesting properties: it is bounding, monotonic, refinable, it approximates distributions with finite support and it conserves the shape of the distribution. With the resulting discrete distributions, the evolution of the system is then exactly modelled by a Markov chain. Here, we focus on flow lines and show that the method allows us to compute upper and lower bounds on the throughput as well as good approximations of the cycle time distributions. Finally, the global modelling method is shown, by numerical experiments, to compute accurate estimations of the throughput and of various performance measures, reaching accuracy levels of a few tenths of a percent.     

Simulation of Student–Lévy processes using series representations

Lévy processes have become very popular in many applications in finance, physics and beyond. The Student–Lévy process is one interesting special case where increments are heavy-tailed and, for 1-increments, Student t distributed. Although theoretically available, there is a lack of path simulation techniques in the literature due to its complicated form. In this paper we address this issue using series representations with the inverse Lévy measure method and the rejection method and prove upper bounds for the mean squared approximation error. In the numerical section we discuss a numerical inversion scheme to find the inverse Lévy measure efficiently. We extend the existing numerical inverse Lévy measure method to incorporate explosive Lévy tail measures. Monte Carlo studies verify the error bounds and the effectiveness of the simulation routine. As a side result we obtain series representations of the so called inverse gamma subordinator which are used to generate paths in this model.     

Two issues in using mixtures of polynomials for inference in hybrid Bayesian networks

We discuss two issues in using mixtures of polynomials (MOPs) for inference in hybrid Bayesian networks. MOPs were proposed by Shenoy and West for mitigating the problem of integration in inference in hybrid Bayesian networks. First, in defining MOP for multi-dimensional functions, one requirement is that the pieces where the polynomials are defined are hypercubes. In this paper, we discuss relaxing this condition so that each piece is defined on regions called hyper-rhombuses. This relaxation means that MOPs are closed under transformations required for multi-dimensional linear deterministic conditionals, such as Z = X + Y, etc. Also, this relaxation allows us to construct MOP approximations of the probability density functions (PDFs) of the multi-dimensional conditional linear Gaussian distributions using a MOP approximation of the PDF of the univariate standard normal distribution. Second, Shenoy and West suggest using the Taylor series expansion of differentiable functions for finding MOP approximations of PDFs. In this paper, we describe a new method for finding MOP approximations based on Lagrange interpolating polynomials (LIP) with Chebyshev points. We describe how the LIP method can be used to find efficient MOP approximations of PDFs. We illustrate our methods using conditional linear Gaussian PDFs in one, two, and three dimensions, and conditional log-normal PDFs in one and two dimensions. We compare the efficiencies of the hyper-rhombus condition with the hypercube condition. Also, we compare the LIP method with the Taylor series method.     

Efficient simulation and conditional functional limit theorems for ruinous heavy-tailed random walks

The contribution of this paper is to introduce change of measure based techniques for the rare-event analysis of heavy-tailed random walks. Our changes of measures are parameterized by a family of distributions admitting a mixture form. We exploit our methodology to achieve two types of results. First, we construct Monte Carlo estimators that are strongly efficient (i.e. have bounded relative mean squared error as the event of interest becomes rare). These estimators are used to estimate both rare-event probabilities of interest and associated conditional expectations. We emphasize that our techniques allow us to control the expected termination time of the Monte Carlo algorithm even if the conditional expected stopping time (under the original distribution) given the event of interest is infinity–a situation that sometimes occurs in heavy-tailed settings. Second, the mixture family serves as a good Markovian approximation (in total variation) of the conditional distribution of the whole process given the rare event of interest. The convenient form of the mixture family allows us to obtain functional conditional central limit theorems that extend classical results in the literature.     

Analytic approximations of queues with lightly- and heavily-correlated autoregressive service times

We consider a single-server queueing system. The arrival process is modelled as a Poisson process while the service times of the consecutive customers constitute a sequence of autoregressive random variables. Our interest into autoregressive service times comes from the need to capture temporal correlation of the channel conditions on wireless network links. If these fluctuations are slow in comparison with the transmission times of the packets, transmission times of consecutive packets are correlated. Such correlation needs to be taken into account for an accurate performance assessment. By means of a transform approach, we obtain a functional equation for the joint transform of the queue content and the current service time at departure epochs in steady state. To the best of our knowledge, this functional equation cannot be solved by exact mathematical techniques, despite its simplicity. However, by means of a Taylor series expansion in the parameter of the autoregressive process, a “light-correlation” approximation is obtained for performance measures such as moments of the queue content and packet delay. We illustrate our approach by some numerical examples, thereby assessing the accuracy of our approximations by simulation. For the heavy correlation case, we give differential equation approximations based on the time-scale separation technique, and present numerical examples in support of this approximation.     

An investigation of phase-distribution moment-matching algorithms for use in queueing models

Algorithms for matching moments to phase-type distributions are evaluated on the basis of their performance in their intended application, queueing models. The moment-matching algorithms under consideration match two moments to a hyperexponential distribution with balanced means and three moments to a mixture of two Erlang distributions of common order. These algorithms are used to approximate an interarrival-time distribution for a queueing model, and the accuracy of associated performance-measure approximations is then used to evaluate the moment-matching algorithms. Three performance measures are considered, and attention is focussed on the steady-state mean queue length (number in system) of theGI/M/1 queue. Performance-measure approximations are compared to three-moment bounds and performance-measure values arising from hypothetical approximated distributions.     

Ruin probability and time of ruin with a proportional reinsurance threshold strategy

In this paper, we present a threshold proportional reinsurance strategy and we analyze the effect on some solvency measures: ruin probability and time of ruin. This dynamic reinsurance strategy assumes a retention level that is not constant and depends on the level of the surplus. In a model with inter-occurrence times being generalized Erlang(n)-distributed, we obtain the integro-differential equation for the Gerber?CShiu function. Then, we present the solution for inter-occurrence times exponentially distributed and claim amount phase-type(N). Some examples for exponential and phase-type(2) claim amount are presented. Finally, we show some comparisons between threshold reinsurance and proportional reinsurance.