ON THE INFINITE SERVER SHORTEST QUEUE PROBLEM: SYMMETRIC CASE

Abstract

We consider two identical parallel M/M/∞ queues. A new arrival is routed to the queue with the smaller number of customers. If both systems have equal occupancy, the arrival joins either with probability 1/2. These types of models have been used to describe CDMA (Code Division Multiple Access) cellular systems. We analyze this model both numerically and asymptotically. For the latter, we consider the limit ρ = λ/μ → ∞, where λ (resp., μ) is the arrival (resp., service) rate. An efficient numerical method is developed for computing the joint steady-state distribution of the number of customers in the two queues. We give several asymptotic formulas, valid for different ranges of the state variables, which show the qualitative structure of the joint distribution. The numerical accuracy of the asymptotic results is tested.     

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.     

Two-queue polling systems with switching policy based on the queue that is not being served

We study a system of two non-identical and separate M/M/1/? queues with capacities (buffers) C₁ < ∞ and C₂ = ∞, respectively, served by a single server that alternates between the queues. The server’s switching policy is threshold-based, and, in contrast to other threshold models, is determined by the state of the queue that is not being served. That is, when neither queue is empty while the server attends Q_i (i = 1, 2), the server switches to the other queue as soon as the latter reaches its threshold. When a served queue becomes empty we consider two switching scenarios: (i) Work-Conserving, and (ii) Non-Work-Conserving. We analyze the two scenarios using Matrix Geometric methods and obtain explicitly the rate matrix R, where its entries are given in terms of the roots of the determinants of two underlying matrices. Numerical examples are presented and extreme cases are investigated.     

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.     

A Subset Selection Procedure for Selecting the Exponential Population Having the Longest Mean Lifetime When the Guarantee Times are the Same

ABSTRACT

Consider k(≥ 2) independent exponential populations Π₁, Π₂, …, Π _k , having the common unknown location parameter μ ∈ (?∞, ∞) (also called the guarantee time) and unknown scale parameters σ₁, σ₂, …σ _k , respectively (also called the remaining mean lifetimes after the completion of guarantee times), σ _i  > 0, i = 1, 2, …, k. Assume that the correct ordering between σ₁, σ₂, …, σ _k is not known apriori and let σ_[i], i = 1, 2, …, k, denote the ith smallest of σ _j s, so that σ_[1] ≤ σ_[2] ··· ≤ σ_[k]. Then Θ _i  = μ + σ _i is the mean lifetime of Π _i , i = 1, 2, …, k. Let Θ_[1] ≤ Θ_[2] ··· ≤ Θ_[k] denote the ranked values of the Θ _j s, so that Θ_[i] = μ + σ_[i], i = 1, 2, …, k, and let Π_(i) denote the unknown population associated with the ith smallest mean lifetime Θ_[i] = μ + σ_[i], i = 1, 2, …, k. Based on independent random samples from the k populations, we propose a selection procedure for the goal of selecting the population having the longest mean lifetime Θ_[k] (called the “best” population), under the subset selection formulation. Tables for the implementation of the proposed selection procedure are provided. It is established that the proposed subset selection procedure is monotone for a general k (≥ 2). For k = 2, we consider the loss measured by the size of the selected subset and establish that the proposed subset selection procedure is minimax among selection procedures that satisfy a certain probability requirement (called the P*-condition) for the inclusion of the best population in the selected subset.     

Constants on a Uniform Berry-Esseen Bound on Some Borel Sets in ℝ k via Stein's Method

For each n, k ∈ ?, let Y _i  = (Y _i1, Y _i2,…, Y _ik ), 1 ≤ i ≤ n be independent random vectors in ? ^k with finite third moments and Y _ij are independent for all j = 1, 2,…, k. In this article, we use the Stein's technique to find constants in uniform bounds for multidimensional Berry-Esseen inequality on a closed sphere, a half plane and a rectangular set.     

A One Sided Test Based on Sample Quasi Ranges

Abstract

Let the data from the ith treatment/population follow a distribution with cumulative distribution function (cdf) F _i (x) = F[(x ? μ _i )/θ _i ], i = 1,…, k (k ≥ 2). Here μ _i (?∞ < μ _i  < ∞) is the location parameter, θ _i (θ _i  > 0) is the scale parameter and F(?) is any absolutely continuous cdf, i.e., F _i (?) is a member of location-scale family, i = 1,…, k. In this paper, we propose a class of tests to test the null hypothesis H ₀ ? θ₁ = · = θ _k against the simple ordered alternative H _A  ? θ₁ ≤ · ≤ θ _k with at least one strict inequality. In literature, use of sample quasi range as a measure of dispersion has been advocated for small sample size or sample contaminated by outliers [see David, H. A. (1981). Order Statistics. 2nd ed. New York: John Wiley, Sec. 7.4]. Let X _i1,…, X _in be a random sample of size n from the population π _i and R _ir  = X _i:n?r  ? X _i:r+1, r = 0, 1,…, [n/2] ? 1 be the sample quasi range corresponding to this random sample, where X _i:j represents the jth order statistic in the ith sample, j = 1,…, n; i = 1,…, k and [x] is the greatest integer less than or equal to x. The proposed class of tests, for the general location scale setup, is based on the statistic W _r  = max_1≤i<j≤k (R _jr /R _ir ). The test is reject H ₀ for large values of W _r . The construction of a three-decision procedure and simultaneous one-sided lower confidence bounds for the ratios, θ _j /θ _i , 1 ≤ i < j ≤ k, have also been discussed with the help of the critical constants of the test statistic W _r . Applications of the proposed class of tests to two parameter exponential and uniform probability models have been discussed separately with necessary tables. Comparisons of some members of our class with the tests of Gill and Dhawan [Gill A. N., Dhawan A. K. (1999). A One-sided test for testing homogeneity of scale parameters against ordered alternative. Commun. Stat. – Theory and Methods 28(10):2417–2439] and Kochar and Gupta [Kochar, S. C., Gupta, R. P. (1985). A class of distribution-free tests for testing homogeneity of variances against ordered alternatives. In: Dykstra, R. et al., ed. Proceedings of the Conference on Advances in Order Restricted Statistical Inference at Iowa city. Springer Verlag, pp. 169–183], in terms of simulated power, are also presented.     

Commuting Matrices in the Queue Length and Sojourn Time Analysis of MAP/MAP/1 Queues

Queues with Markovian arrival and service processes, i.e., MAP/MAP/1 queues, have been useful in the analysis of computer and communication systems and different representations for their stationary sojourn time and queue length distribution have been derived. More specifically, the class of MAP/MAP/1 queues lies at the intersection of the class of QBD queues and the class of semi-Markovian queues. While QBD queues have a matrix exponential representation for their queue length and sojourn time distribution of order N and N², respectively, where N is the size of the background continuous time Markov chain, the reverse is true for a semi-Markovian queue. As the class of MAP/MAP/1 queues lies at the intersection, both the queue length and sojourn time distribution of a MAP/MAP/1 queue has an order N matrix exponential representation. The aim of this article is to understand why the order N² distributions of the sojourn time of a QBD queue and the queue length of a semi-Markovian queue can be reduced to an order N distribution in the specific case of a MAP/MAP/1 queue. We show that the key observation exists in establishing the commutativity of some fundamental matrices involved in the analysis of the MAP/MAP/1 queue.     

A Tandem Queue with Server Slow-Down and Blocking

Abstract

We consider two variants of a two-station tandem network with blocking. In both variants the first server ceases to work when the queue length at the second station hits a ‘blocking threshold.’ In addition, in variant 2 the first server decreases its service rate when the second queue exceeds a ‘slow-down threshold, ’ which is smaller than the blocking level. In both variants the arrival process is Poisson and the service times at both stations are exponentially distributed. Note, however, that in case of slow-downs, server 1 works at a high rate, a slow rate, or not at all, depending on whether the second queue is below or above the slow-down threshold or at the blocking threshold, respectively. For variant 1, i.e., only blocking, we concentrate on the geometric decay rate of the number of jobs in the first buffer and prove that for increasing blocking thresholds the sequence of decay rates decreases monotonically and at least geometrically fast to max{ρ₁, ρ₂}, where ρ _i is the load at server i. The methods used in the proof also allow us to clarify the asymptotic queue length distribution at the second station. Then we generalize the analysis to variant 2, i.e., slow-down and blocking, and establish analogous results.     

Stochastic Comparisons and Dependence of Spacings from Two Samples of Exponential Random Variables

Let X ₁,X ₂,…,X _n be independent exponential random variables such that X _i has hazard rate λ for i = 1,…,p and X _j has hazard rate λ* for j = p + 1,…,n, where 1 ≤ p < n. Denote by D _i:n (λ, λ*) = X _i:n  ? X _i?1:n the ith spacing of the order statistics X _1:n  ≤ X _2:n  ≤ ··· ≤ X _n:n , i = 1,…,n, where X _0:n ≡ 0. It is shown that the spacings (D _1,n ,D _2,n ,…,D _n:n ) are MTP₂, strengthening one result of Khaledi and Kochar (2000), and that (D _1:n (λ₂, λ*),…,D _n:n (λ₂, λ*)) ≤ _lr (D _1:n (λ₁, λ*),…,D _n:n (λ₁, λ*)) for λ₁ ≤ λ* ≤ λ₂, where ≤ _lr denotes the multivariate likelihood ratio order. A counterexample is also given to show that this comparison result is in general not true for λ* < λ₁ < λ₂.     

Some New Results on Likelihood Ratio Orderings for Spacings of Heterogeneous Exponential Random Variables

Let X ₁, X ₂,…, X _n be independent exponential random variables with X _i having failure rate λ _i for i = 1,…, n. Denote by D _i:n  = X _i:n  ? X _i?1:n the ith spacing of the order statistics X _1:n  ≤ X _2:n  ≤ ··· ≤ X _n:n , i = 1,…, n, where X _0:n ≡ 0. It is shown that if λ _n+1 ≤ [≥] λ _k for k = 1,…, n then D _n:n  ≤ _lr D _n+1:n+1 and D _1:n  ≤ _lr D _2:n+1 [D _2:n+1 ≤ _lr D _2:n ], and that if λ _i  + λ _j  ≥ λ _k for all distinct i,j, and k then D _n?1:n  ≤ _lr D _n:n and D _n:n+1 ≤ _lr D _n:n , where ≤ _lr denotes the likelihood ratio order. We also prove that D _1:n  ≤ _lr D _2:n for n ≥ 2 and D _2:3 ≤ _lr D _3:3 for all λ _i 's.     

A MAP/G/1 Queue with an Underlying Birth–Death Process

Abstract

In this paper, we define a birth–death‐modulated Markovian arrival process (BDMMAP) as a Markovian arrival process (MAP) with an underlying birth–death process. It is proved that the zeros of det(zI ? A(z)) in the unit disk are real and simple. In order to analyze a BDMMAP/G/1 queue, two spectral methods are proposed. The first one is a bisection method for calculation of the zeros from which the boundary vector is derived. The second one is the Fourier inversion transform of the probability generating function for the calculation of the stationary probability distribution of the queue length. Eigenvalues required in this calculation are obtained by the Duran–Kerner–Aberth (DKA) method. For numerical examples, the stationary probability distribution of the queue length is calculated by using the spectral methods. Comparisons of the spectral methods with the currently best methods available are discussed.     

Estimating Average Worth of the Selected Subset from Two-Parameter Exponential Populations

ABSTRACT

Suppose independent random samples are available from k(k ≥ 2) exponential populations ∏₁,…,∏ _k with a common location θ and scale parameters σ₁,…,σ _k , respectively. Let X _i and Y _i denote the minimum and the mean, respectively, of the ith sample, and further let X = min{X ₁,…, X _k } and T _i  = Y _i  ? X; i = 1,…, k. For selecting a nonempty subset of {∏₁,…,∏ _k } containing the best population (the one associated with max{σ₁,…,σ _k }), we use the decision rule which selects ∏ _i if T _i  ≥ c max{T ₁,…,T _k }, i = 1,…, k. Here 0 < c ≤ 1 is chosen so that the probability of including the best population in the selected subset is at least P* (1/k ≤ P* < 1), a pre-assigned level. The problem is to estimate the average worth W of the selected subset, the arithmetic average of means of selected populations. In this article, we derive the uniformly minimum variance unbiased estimator (UMVUE) of W. The bias and risk function of the UMVUE are compared numerically with those of analogs of the best affine equivariant estimator (BAEE) and the maximum likelihood estimator (MLE).     

The Recursive Kernel Distribution Function Estimator Based on Negatively and Positively Associated Sequences

Let {X _j , j ≥ 1} be a strictly stationary negatively or positively associated sequence of real valued random variables with unknown distribution function F(x). On the basis of the random variables {X _j , j ≥ 1}, we propose a smooth recursive kernel-type estimate of F(x), and study asymptotic bias, quadratic-mean consistency and asymptotic normality of the recursive kernel-type estimator under suitable conditions.     

A Fast Wavelet Algorithm for Analyzing One-Dimensional Signal Processing and Asymptotic Distribution of Wavelet Coefficients With Numerical Example and Simulation

In this article, we consider a sample point (t _j , s _j ) including a value s _j  = f(t _j ) at height s _j and abscissa (time or location) t _j . We apply wavelet decomposition by using shifts and dilations of the basic Häar transform and obtain an algorithm to analyze a signal or function f. We use this algorithm in practical to approximating function by numerical example. Some relationships between wavelets coefficients and asymptotic distribution of wavelet coefficients are investigated. At the end, we illustrate the results on simulated data by using MATLAB and R software.     

Nonparametric Prediction Intervals for Future Order Statistics in a Proportional Hazard Model

Consider k independent random samples with different sample sizes such that the ith sample comes from the cumulative distribution function (cdf) F _i  = 1 ? (1 ? F)^{α _i} , where α _i is a known positive constant and F is an absolutely continuous cdf. Also, suppose that we have observed the maximum and minimum of the first k samples. This article shows how one can construct the nonparametric prediction intervals for the order statistics of the future samples on the basis of these information. Three schemes are studied and in each case exact expressions for the prediction coefficients of prediction intervals are derived. Numerical computations are given for illustrating the results. Also, a comparison study is done while the complete samples are available.     

Reliabilities for (n,f, k (i,j)) and ⟨n,f, k (i,j)⟩ Systems

The (n,f,k(i,j)):F(? n,f,k(i,j)?:F) system consists of n components ordered in a line or circle, while the system fails if, and only if, there exist at least f failed components OR (AND) at least k consecutive failed components among components i,i + 1,…,j ? 1,j. In this article, we present the system reliability formulae for these systems with product of matrices by means of a two-stage finite Markov chain imbedding approach, a technique first used by Cui et al. (2002 Cui , L. R. , Kuo , W. , Xie , M. ( 2002 ). On (f,g)-out-of-((i,j),n) systems and its reliability . In: Third International Conference on Mathematical Methods in Reliability Methodology and Practice , June 17–20 , Norway , Trondheim , pp. 173 – 176 . [Google Scholar]). In addition, their dual systems, denoted by (n,f,k(i,j)):G and ? n,f,k(i,j)?:G, are also introduced. Two numerical examples are given to illustrate the results.     

Testing independence with additional information

Let X = (X^j : j = 1,…, n) be n row vectors of dimension p independently and identically distributed multinomial. For each j, X^j is partitioned as X^j = (X^j₁, X^j₂, X^j₃), where p_i is the dimension of X^j_i with p₁ = 1,p₁+p₂+p₃ = p. In addition, consider vectors Y^j_i, i = 1,2j = 1,…,n_i that are independent and distributed as X¹_i. We treat here the problem of testing independence between X¹₁ and X¹₃ knowing that X¹₁ and X¹₂ are uncorrected. A locally best invariant test is proposed for this problem.