A Spectral Method for a Nonpreemptive Priority BMAP/G/1 QUEUE

Abstract

In this paper we consider a nonpreemptive priority queue with two priority classes of customers. Customers arrive according to a batch Markovian arrival process (BMAP). In order to calculate the boundary vectors we propose a spectral method based on zeros of the determinant of a matrix function and the corresponding eigenvectors. It is proved that there are M zeros in a set Ω, where M is the size of the state space of the underlying Markov process. The zeros are calculated by the Durand-Kerner method, and the stationary joint probability of the numbers of customers of classes 1 and 2 at departures is derived by the inversion of the two-dimensional Fourier transform. For a numerical example, the stationary probability is calculated.     

AN INFINITE-PHASE QUASI-BIRTH-AND-DEATH MODEL FOR THE NON-PREEMPTIVE PRIORITY M/PH/1 QUEUE

This paper considers a single server queue that handles arrivals from N classes of customers on a non-preemptive priority basis. Each of the N classes of customers features arrivals from a Poisson process at rate λ _i and class-dependent phase type service. To analyze the queue length and waiting time processes of this queue, we derive a matrix geometric solution for the stationary distribution of the underlying Markov chain. A defining characteristic of the paper is the fact that the number of distinct states represented within the sub-level is countably infinite, rather than finite as is usually assumed. Among the results we obtain in the two-priority case are tractable algorithms for the computation of both the joint distribution for the number of customers present and the marginal distribution of low-priority customers, and an explicit solution for the marginal distribution of the number of high-priority customers. This explicit solution can be expressed completely in terms of the arrival rates and parameters of the two service time distributions. These results are followed by algorithms for the stationary waiting time distributions for high- and low-priority customers. We then address the case of an arbitrary number of priority classes, which we solve by relating it to an equivalent three-priority queue. Numerical examples are also presented.     

Matrix Product-Form Solutions for LCFs Preemptive Service Single-Server Queues with Batch Markovian Arrival Streams

ABSTRACT

This paper considers three variants of last-come first-served (LCFS) preemptive service single-server queues, where customers are served under the LCFS preemptive resume (LCFS-PR), preemptive repeat-different (LCFS-PD), and preemptive repeat-identical (LCFS-PI) disciplines, respectively. These LCFS queues are fed by multiple batch Markovian arrival streams. Service times of customers from each arrival stream are generally distributed and their distributions may differ among different streams. For each of LCFS-PR, LCFS-PD, and LCFS-PI queues, we show that the stationary distribution of the queue string representing enough information to keep track of queueing dynamics has a matrix product-form solution. Further, this paper discusses the stability of LCFS-PD and LCFS-PI queues based on the busy cycle. Finally, by numerical experiment, we examine the impact of the variation of the service time distribution on the mean queue lengths for the three variants of LCFS queues.     

An Exact Analysis of the Multi‐class M/M/k Priority Queue with Partial Blocking

Abstract

We consider a multi‐server queuing model with two priority classes that consist of multiple customer types. The customers belonging to one priority class customers are lost if they cannot be served immediately upon arrival. Each customer type has its own Poisson arrival and exponential service rate. We derive an exact method to calculate the steady state probabilities for both preemptive and nonpreemptive priority disciplines. Based on these probabilities, we can derive exact expressions for a wide range of relevant performance characteristics for each customer type, such as the moments of the number of customers in the queue and in the system, the expected postponement time and the blocking probability. We illustrate our method with some numerical examples.     

Limit theorems for single server queues with mixed renewal and poisson inputs

The following queuing system is considered:Two independent recurrent input streams (streams 1 and 2) arrive at a server. It is assumed that stream 1 is of Poisson type. Three priority disciplines are studied in case that these customers have priority:head-of-the-line, preemptive-resume, and preemptive-repeat discipline. Formulas derived for the limiting distribution functions of the actual and the virtual waiting time of low priority customers and of the number of these customers in the system, by using of independences of certain random processes when the time tends to infinity.     

The existence of waiting time moments for single server queues with mixed renewal and poisson inputs

The following queuing system is considered: Two independent recurrent input streams (streams 1 and 2) arrive at a server. It is assumed that stream 1 is of Poisson type. Three priority disciplines are studied in case that customers of type 1 have priority: head-of-the-line, preemptive-resume, and preemptive-repeat discipline. For all three cases, the limiting distribution function of actual waiting times of low-priority customers is considered, and conditions are given for the existence of moments related to these limiting distributions.     

Tail Probability of Low-Priority Queue Length in a Discrete-Time Priority BMAP/PH/1 Queue

ABSTRACT

We investigate the tail probability of the queue length of low-priority class for a discrete-time priority BMAP/PH/1 queue that consists of two priority classes, with BMAP (Batch Markovian Arrival Process) arrivals of high-priority class and MAP (Markovian Arrival Process) arrivals of low-priority class. A sufficient condition under which this tail probability has the asymptotically geometric property is derived. A method is designed to compute the asymptotic decay rate if the asymptotically geometric property holds. For the case when the BMAP for high-priority class is the superposition of a number of MAP's, though the parameter matrices representing the BMAP is huge in dimension, the sufficient condition is numerically easy to verify and the asymptotic decay rate can be computed efficiently.     

Estimation of Traffic Intensity Based on Queue Length in a Single M/M/1 Queue

In this article, maximum likelihood estimator (MLE) as well as Bayes estimator of traffic intensity (ρ) in an M/M/1/∞ queueing model in equilibrium based on number of customers present in the queue at successive departure epochs have been worked out. Estimates of some functions of ρ which provide measures of effectiveness of the queue have also been derived. A comprehensive simulation study starting with the transition probability matrix has been carried out in the last section.     

A geometric process repair model for a cold standby repairable system with imperfect delay repair and priority in use

In this article, a two-dissimilar-component cold standby repairable system with one repairman is studied. Assume that the repair after failure for each component is delayed or undelayed. Component 2 after repair is “as good as new” while Component 1 after repair is not, but Component 1 has priority in use. Under these assumptions, using a geometric process, we consider a replacement policy N based on the failure number of Component 1. An optimal replacement policy N* is determined by minimizing the average cost rate C(N) of the system. Finally, a numerical example is given to illustrate some theoretical results and the model applicability.     

STABILITY IN QUEUES WITH IMPATIENT CUSTOMERS

This paper deals with GI/G/1 queueing systems with impatient customers that have individual deadlines until their beginning of service. The impatience law depends on the number of waiting customers and on the elapsed service time of the customer in service. An exhaustive analysis of the asymptotic behavior of the model, combining ideas of stochastic dominance of well–known processes and some properties of models with finite capacity, is provided. We prove that the model is ergodic, null recurrent or transient if the corresponding traffic parameter in a simple associated model is respectively lower than, equal to, or greater than one.     

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.     

Bernstein-von Mises theorem and Bayes estimation from single server queues

Abstract

In this paper, we prove the Bernstein-von Mises theorem for the GI∕G∕1 queueing system which is observed over a continuous time interval (0, T], where T is a suitable stopping time. And also the asymptotic properties of Bayes estimators of the parameters are investigated.     

Admission policies for a two class loss system

We consider the problem of dynamic admission control in a Markovian loss queueing system with two classes of customers with different service rates and revenues. We show that under certain conditions, customers of one class, which we call a preferred class, are always admitted to the system. Moreover, the optimal policy is of threshold type, and we establish that the thresholds are monotone under very restrictive conditions.     

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.     

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.     

A note on the robustness of PBIBD(2)s against breakdown in the event of observation loss

Robustness against design breakdown following observation loss is investigated for Partially Balanced Incomplete Block Designs with two associate classes (PBIBD(2)s). New results are obtained which add to the body of knowledge on PBIBD(2)s. In particular, using an approach based on the E‐value of a design, all PBIBD(2)s with triangular and Latin square association schemes are established as having optimal block breakdown number. Furthermore, for group divisible designs not covered by existing results in the literature, a sufficient condition for optimal block breakdown number establishes that all members of some design sub‐classes have this property.     

PIECEWISE POLYNOMIAL APPROXIMATIONS FOR HEAVY-TAILED DISTRIBUTIONS IN QUEUEING ANALYSIS

ABSTRACT

A basic difficulty in dealing with heavy-tailed distributions is that they may not have explicit Laplace transforms. This makes numerical methods that use the Laplace transform more challenging. This paper generalizes an existing method for approximating heavy-tailed distributions, for use in queueing analysis. The generalization involves fitting Chebyshev polynomials to a probability density function g(t) at specified points t ₁, t ₂, …, t _N . By choosing points t _i , which rapidly get far out in the tail, it is possible to capture the tail behavior with relatively few points, and to control the relative error in the approximation. We give numerical examples to evaluate the performance of the method in simple queueing problems.     

Maximum likelihood estimation for the generalized poisson distribution

The generalized Poisson distribution;containing two

parameters and studied by many researchers; describes the distribution of busy periods under a queueing system and has very interesting properties; The probabilities for successive classes depend upon the previous occurrences; The problem of admissible maximum likelihood estimators for for the parameters Is discussed and a necessary and sufficient condition is derived for which unique admissible maximum likelihood estimators exist; The first; order terms in the biases; variances and the covariance of these maximum likelihood estimators are obtained.     

Empirical likelihood confidence intervals under imputation for missing survey data from stratified simple random sampling

Missing observations due to non‐response are commonly encountered in data collected from sample surveys. The focus of this article is on item non‐response which is often handled by filling in (or imputing) missing values using the observed responses (donors). Random imputation (single or fractional) is used within homogeneous imputation classes that are formed on the basis of categorical auxiliary variables observed on all the sampled units. A uniform response rate within classes is assumed, but that rate is allowed to vary across classes. We construct confidence intervals (CIs) for a population parameter that is defined as the solution to a smooth estimating equation with data collected using stratified simple random sampling. The imputation classes are assumed to be formed across strata. Fractional imputation with a fixed number of random draws is used to obtain an imputed estimating function. An empirical likelihood inference method under the fractional imputation is proposed and its asymptotic properties are derived. Two asymptotically correct bootstrap methods are developed for constructing the desired CIs. In a simulation study, the proposed bootstrap methods are shown to outperform traditional bootstrap methods and some non‐bootstrap competitors under various simulation settings. The Canadian Journal of Statistics 47: 281–301; 2019 © 2019 Statistical Society of Canada     

On Uniformly Optimal Networks: A Reversal of Fortune?

In this article, the general problem of comparing the performance of two communication networks is examined. The standard approach, using stochastic ordering as a metric, is reviewed, as are the mixed results on the existence of uniformly optimal networks (UONs) which have emerged from this approach. While UONs have been shown to exist for certain classes of networks, it has also been shown that no UON network exists for other classes. Results to date beg the question: Is the problem of identifying a Uniformly Optimal Network (UON) of a given size dead or alive? We reframe the investigation into UONs in terms of network signatures and the alternative metric of stochastic precedence. While the endeavor has been dead, or at least dormant, for some 20 years, the findings in the present article suggest that the question above is by no means settled. Specifically, we examine a class of networks of a particular size for which it was shown that no individual network was uniformly optimal relative to the standard metric (the uniform ordering of reliability polynomials), and we show, using the aforementioned alternative metric, that this class is totally ordered and that a uniformly optimal network exists after all. Optimality with respect to “performance per unit cost” type metrics is also discussed.