Bayesian estimation for the M/G/1 queue using a phase-type approximation

This article deals with Bayesian inference and prediction for M/G/1 queueing systems. The general service time density is approximated with a class of Erlang mixtures which are phase-type distributions. Given this phase-type approximation, an explicit evaluation of measures such as the stationary queue size, waiting time and busy period distributions can be obtained. Given arrival and service data, a Bayesian procedure based on reversible jump Markov Chain Monte Carlo methods is proposed to estimate system parameters and predictive distributions.     

Relative efficiency of a parameter for a M/G/1 queueing system based on reduced and full likelihood functions

The present paper derives the relative efficiency of a parameter for the M/G/1 queueing system based on reduced and full likelihood functions. Monte Carlo simulations were carried out to study the finite sample properties for estimating the parameters of a M/G/1 queueing system. The simulation runs were conducted using various traftic intensities with increaseing sample sizes. The simulation results indicate that the loss in efficiency is quite small due to the use of a reduced likelihood function approach for estimating the parameter instead of the full likelihood, even for a moderate sample size of 50     

Bayesian analysis of Er/M/1 and Er/M/c queues

Bayesian inference and prediction tasks for Er/M/1 and Er/M/c queues are undertaken. Equilibrium probabilities of the queue size and waiting time distributions are estimated using conditional Monte-Carlo simulation methods. We illustrate that some standard queueing measures do not exist when independent priors are used for the arrival and service rates of a G/M/1 queue.     

Comparability of special distributions

In the note comparability criteria are stated for distributions belonging to the Weibull, Gamma and Lognormal class. This results complete the corresponding results from the monograph by Stoyan. As an example an upper bound is stated for the mean waiting time in a queueing system Gamma/Gamma/s.     

Estimation in M/Er /1 queueing systems

In this paper, the maximum likelihood estimates of the parameters for the M/E_r /1 queueing model are derived when the queue size at each departure point is observed. A numerical example is generated by simulating a finite Markov chain to illustrate the methodology for estimating the parameters with variable Erlang service time distribution. The problem of hypothesis testing and simultaneous Confidence regions of the parameter is also investigated.0     

Hypothesis Testing and Confidence Regions for the Mean Sojourn Time of an M/M/1 Queueing System

This article discusses testing hypotheses and confidence regions with correct levels for the mean sojourn time of an M/M/1 queueing system. The uniformly most powerful unbiased tests for three usual hypothesis testing problems are obtained and the corresponding p values are provided. Based on the duality between hypothesis tests and confidence sets, the uniformly most accurate confidence bounds are derived. A confidence interval with correct level is proposed.     

ANALYSIS OF A GI/G Y /1 SYSTEM IN DISCRETE-TIME

ABSTRACT

We consider a class of single server queueing systems in which customers arrive singly and service is provided in batches, depending on the number of customers waiting when the server becomes free. Service is independent of the batch size. This system could also be considered as a batch service queue in which a server visits the queue at arbitrary times and collects a batch of waiting customers for service, or waits for a customer to arrive if there are no waiting customers. A waiting server immediately collects and processes the first arriving customer. The system is considered in discrete time. The interarrival times of customers and the inter-visit times of the server, which we call the service time, have general distributions and are represented as remaining time Markov chains. We analyze this system using the matrix-geometric method and show that the resulting R matrix can be determined explicitly in some special cases and the stationary distributions are known semi-explicitly in some other special cases.     

Transient analysis of a finite source discrete-time queueing system using homogeneous Markov system with state size capacities (HMS/c)

Abstract

In this article, a finite source discrete-time queueing system is modeled as a discrete-time homogeneous Markov system with finite state size capacities (HMS/c) and transition priorities. This Markov system is comprised of three states. The first state of the HMS/c corresponds to the source and the second one to the state with the servers. The second state has a finite capacity which corresponds to the number of servers. The members of the system which can not enter the second state, due to its finite capacity, enter the third state which represents the system's queue. In order to examine the variability of the state sizes recursive formulae for their factorial and mixed factorial moments are derived in matrix form. As a consequence the probability mass function of each state size can be evaluated. Also the expected time in queue is computed by means of the interval transition probabilities. The theoretical results are illustrated by a numerical example.     

Confidence Intervals of Performance Measures for an M/G/1 Queueing System

In this article, we discuss constructing confidence intervals (CIs) of performance measures for an M/G/1 queueing system. Fiducial empirical distribution is applied to estimate the service time distribution. We construct fiducial empirical quantities (FEQs) for the performance measures. The relationship between generalized pivotal quantity and fiducial empirical quantity is illustrated. We also present numerical examples to show that the FEQs can yield new CIs dominate the bootstrap CIs in relative coverage (defined as the ratio of coverage probability to average length of CI) for performance measures of an M/G/1 queueing system in most of the cases.     

Estimation of the Parameters of a Two-phase Tandem Queue with a Second Optional Service

In this article, we consider a two-phase tandem queueing model with a second optional service. In this model, the service is done by two phases. The first phase of service is essential for all customers and after the completion of the first phase of service, any customer receives the second phase of service with probability α, or leaves the system with probability 1 ? α. Also, there are two heterogeneous servers which work independently, one of them providing the first phase of service and the other a second phase of service. In this model, our main purpose is to estimate the parameters of the model, traffic intensity, and mean system size, in the steady state, via maximum likelihood and Bayesian methods. Furthermore, we find asymptotic confidence intervals for mean system size. Finally, by a simulation study, we compute the confidence levels and mean length for asymptotic confidence intervals of mean system size with a nominal level 0.95.     

Workload Process,Waiting Times,and Sojourn Times in a Discrete Time MMAP[K]/SM[K]/1/FCFS Queue

Abstract

In this paper, we study the total workload process and waiting times in a queueing system with multiple types of customers and a first-come-first-served service discipline. An M/G/1 type Markov chain, which is closely related to the total workload in the queueing system, is constructed. A method is developed for computing the steady state distribution of that Markov chain. Using that steady state distribution, the distributions of total workload, batch waiting times, and waiting times of individual types of customers are obtained. Compared to the GI/M/1 and QBD approaches for waiting times and sojourn times in discrete time queues, the dimension of the matrix blocks involved in the M/G/1 approach can be significantly smaller.     

ML and Bayes estimation in a two-phase tandem queue with a second optional service and random feedback

ABSTRACT

In this article, we consider a two-phase tandem queueing model with a second optional service and random feedback. The first phase of service is essential for all customers and after the completion of the first phase of service, any customer receives the second phase of service with probability α, feedback to the tail of the first queue with probability β if the service is not successful and leaves the system with probability 1 ? α ? β. In this model, our main purpose is to estimate the parameters of the model, traffic intensity, and mean system size, in the steady state, via maximum likelihood and Bayesian methods. Furthermore, we find asymptotic confidence intervals for mean system size. Finally, by a simulation study, we compute the confidence levels and mean length for asymptotic confidence intervals of mean system size with a nominal level 0.95.     

Matrix–geometric analysis of the discrete time Gi/G/1 system

In this paper, we show that the discrete GI/G/1 system can be analysed as a QBD process with infinite blocks. Most importantly, we show that Matrix–geometric method can be used for analyzing this general queue system including establishing its stability criterion and for obtaining the explicit stationary probability and the waiting time distributions. This also settles the unwritten myth that Matrix–geometric method is limited to cases with at least one Markov based characterizing parameter, i.e. either interarrival or service times, in the case of queueing systems.     

On Block Skip Free Transition Matrices and First Passage Times

Starting from an abstract setting which extends the property “skip free to the left” for transition matrices to a partition of the state space, we develop bounds for the mean hitting time of a Markov chain to an arbitrary subset from an arbitrary initial law. We apply our theory to the embedded Markov chains associated with the M/G/1 and the GI/M/1 queueing systems. We also illustrate its applicability with an asymptotic analysis of a non-reversible Markovian star queueing network with losses.     

NONPARAMETRIC STATISTICAL ANALYSIS OF DISCRETE-TIME QUEUES,WITH APPLICATIONS TO ATM TELETRAFFIC DATA

In this paper nonparametric statistical analysis of a discrete-time queueing system is considered. Estimation of performance measures of the system is studied. The attention is first focused on the estimation of the waiting time probability distribution, as well as of functionals of interest (mean waiting time, variance of the waiting time, etc.). The approach is based on the estimation of the corresponding generating function. Attention is paid to the estimation of the probability of a “long delay”, in view of its importance for applications. Results for possibly unstable models are also obtained. Finally, an application to ATM teletraffic data is provided.     

A transient analysis of M/G/1 queues with N-policy

We consider an M/G/1 queueing model with N-policy operating. This means, that the server will start up only if a queue of a prescribed length has built up. For this model the time dependent distribution of the queue length is given by simple renewal arguments without resorting to integral transform techniques.     

BMAP/G/1 Queue Under D-Policy: Queue Length Analysis

ABSTRACT

We study the queue length distribution of a queueing system with BMAP arrivals under D-policy. The idle server begins to serve the customers only when the sum of the service times of all waiting customers exceeds some fixed threshold D. We derive the vector generating functions of the queue lengths both at a departure and at an arbitrary point of time. Mean queue lengths are derived and a numerical example is presented.     

Approximated Transient Queue Length and Waiting Time Distributions via Steady State Analysis

Abstract

We propose a method to approximate the transient performance measures of a discrete time queueing system via a steady state analysis. The main idea is to approximate the system state at time slot t or on the n-th arrival–-depending on whether we are studying the transient queue length or waiting time distribution–-by the system state after a negative binomially distributed number of slots or arrivals. By increasing the number of phases k of the negative binomial distribution, an accurate approximation of the transient distribution of interest can be obtained.

In order to efficiently obtain the system state after a negative binomially distributed number of slots or arrivals, we introduce so-called reset Markov chains, by inserting reset events into the evolution of the queueing system under consideration. When computing the steady state vector of such a reset Markov chain, we exploit the block triangular block Toeplitz structure of the transition matrices involved and we directly obtain the approximation from its steady state vector. The concept of the reset Markov chains can be applied to a broad class of queueing systems and is demonstrated in full detail on a discrete-time queue with Markovian arrivals and phase-type services (i.e., the D-MAP/PH/1 queue). We focus on the queue length distribution at time t and the waiting time distribution of the n-th customer. Other distributions, e.g., the amount of work left behind by the n-th customer, that can be acquired in a similar way, are briefly touched upon.

Using various numerical examples, it is shown that the method provides good to excellent approximations at low computational costs–-as opposed to a recursive algorithm or a numerical inversion of the Laplace transform or generating function involved–-offering new perspectives to the transient analysis of practical queueing systems.     

Bayesian estimation of traffic intensity based on queue length in a multi-server M/M/s queue

In this article, we focus on multi-server queueing systems in which inter-arrival and service times are exponentially distributed (Markovian). We use a Bayesian technique, the sampling/importance resampling method (SIR), to estimate the parameters of these queueing systems, making possible the determination of performance measures that are essential to the evaluation of important practical applications such as computer and telecommunication networks, manufacturing and service systems, health care, and other similar real-life problems. Extensive numerical results are presented to demonstrate the accuracy and efficiency of the technique, as well as some of its limitations.