Algorithmic approximations for the busy period distribution of the M/M/c retrial queue

In this paper we deal with the main multiserver retrial queue of M/M/c type with exponential repeated attempts. This model is known to be analytically intractable due to the spatial heterogeneity of the underlying Markov chain, caused by the retrial feature. For this reason several models have been proposed for approximating its stationary distribution, that lead to satisfactory numerical implementations. This paper extends these studies by developing efficient algorithmic procedures for calculating the busy period distribution of the main approximation models of Wilkinson [Wilkinson, R.I., 1956. Theories for toll traffic engineering in the USA, The Bell System Technical Journal 35, 421–514], Falin [Falin, G.I., 1983. Calculations of probability characteristics of a multiline system with repeated calls, Moscow University Computational Mathematics and Cybernetics 1, 43–49] and Neuts and Rao [Neuts, M.F., Rao, B.M., 1990. Numerical investigation of a multiserver retrial model, Queueing Systems 7, 169–190]. Moreover, we develop stable recursive schemes for the computation of the busy period moments. The corresponding distributions for the total number of customers served during a busy period are also studied. Several numerical results illustrate the efficiency of the methods and reveal interesting facts concerning the behavior of the M/M/c retrial queue.     

Diffusion-equation model of slightly loaded M/M/1 queue

Another derivation of the diffusion approximation of the M/M/1 queue is presented, which results in a new boundary condition. The model proposed approximates the time-dependent behavior of the M/M/1 system for all values of channel utilization.     

Analysis of an M/G/∞ queue with batch arrivals and batch-dedicated servers

We analyze an M/G/∞ queue with batch arrivals, where jobs belonging to a batch have to be processed by the same server. The number of jobs in the system is characterized as a compound Poisson random variable through a scaling of the original arrival and batch size processes.     

The N threshold policy for the GI/M/1 queue

We study a GI/M/1 queue with an N threshold policy. In this system, the server stops attending the queue when the system becomes empty and resumes serving the queue when the number of customers reaches a threshold value N. Using the embeded Markov chain method, we obtain the stationary distributions of queue length and waiting time and prove the stochastic decomposition properties.     

Comparison conjectures about the M/G/s queue

We conjecture that the equilibrium waiting-time distribution in an M/G/s queue increases stochastically when the service-time distribution becomes more variable. We discuss evidence in support of this conjecture and others based partly on light-traffic and heavy-traffic limits. We also establish an insensitivity property for the case of many servers in light traffic.     

Further Results for the Queueing System <Emphasis Type="Italic">M</Emphasis><Superscript><Emphasis Type="Italic">x</Emphasis></Superscript>/<Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">c</Emphasis>

For the multi-channel bulk-arrival queue, M ^x /M/c, Abol'nikov and Kabak independently obtained steady state results. In this paper the results of these authors are extended, corrected and simplified. A number of measures of efficiency are calculated for three cases where the arrival group size has: (i) a constant value, (ii) a geometric distribution, or (iii) a positive Poisson distribution. The paper also shows how to calculate fractiles for both the queue length and the waiting time distribution. Examples of extensive numerical results for certain measures of efficiency are presented in tabular and chart form.     

An M/G/1 queue with two phases of service subject to the server breakdown and delayed repair

This paper deals with the steady-state behaviour of an M/G/1 queue with an additional second phase of optional service subject to breakdowns occurring randomly at any instant while serving the customers and delayed repair. This model generalizes both the classical M/G/1 queue subject to random breakdown and delayed repair as well as M/G/1 queue with second optional service and server breakdowns. For this model, we first derive the joint distributions of state of the server and queue size, which is one of chief objectives of the paper. Secondly, we derive the probability generating function of the stationary queue size distribution at a departure epoch as a classical generalization of Pollaczek–Khinchin formula. Next, we derive Laplace Stieltjes transform of busy period distribution and waiting time distribution. Finally, we obtain some important performance measures and reliability indices of this model.     

The behaviour of (k,…,kn,n−ik)ci/i! is asymptotically normal

Let N(n,i) = (k,…,kⁿ,n?ik)c^i/i, i = O.…,[n/k]. We prove that the random variable X_n such that $\text{P(X}{}_{\mathrm{<mtext>n</mtext>}}\text{= i) =}\text{N(n, i)}\text{Σ}{}_{\mathrm{<mtext>j</mtext>}}\text{N(n, j)}$ has asymptotically (n → ∞) a normal distribution and we give some combinatorial applications of this result.We also improve a result of Godsil [3] dealing with matchings in graph.     

Zeros of the functions f(n) = Σi=0(−1)i(in−2i)

The main result of this paper is the following: the only zeros of the title function are at n = 3 and n = 12. This is achieved by means of the recursion function for f(n), viz. F(x) = x³ ? x ? 1 which has only one real root w. This turns out to be the fundamental unit of Q(w). From the norm equation of the units, N(w) = x³ + y³ + z³ ? 3xyz + 2x²z + xz² ? xy² ? yz² = 1, and the negative powers of w which are of binary form, the result follows. The paper concludes with two remarkable combinatorial identities.     

Comparisons between observable and unobservable M/M/1 queues with respect to optimal customer behavior

We consider an M/M/1 queueing system in which the queue length may or may not be observable by a customer upon entering the system. The “observable” and “unobservable” models are compared with respect to system properties and performance measures under two different types of optimal customer behavior, which we refer to as “selfishly optimal” and “socially optimal”. We consider average customer throughput rates and show that, under both types of optimal customer behavior, the equality of effective queue-joining rates between the observable and unobservable systems results in differences with respect to other performance measures such as mean busy periods and waiting times. We also show that the equality of selfishly optimal queue-joining rates between the two types of system precludes the equality of socially optimal joining rates, and vice versa.     

Steady state analysis of an M/G/1 queue with linear retrial policy and two phase service under Bernoulli vacation schedule

We consider a single server queueing system with two phases of heterogeneous service and Bernoulli vacation schedule which operate under the so called linear retrial policy. This model extends both the classical M/G/1 retrial queue with linear retrial policy as well as the M/G/1 queue with two phases of service and Bernoulli vacation model. We carry out an extensive analysis of the model.     

The Factorization of Queueing Equations and Their Interpretation

There are many queueing systems, including the M ^x /M ^y /c queue, the GI ^x /M/c queue and the M/D/c queue, in which the distribution of the queue length at certain epochs is determined by a Markov chain with the following structure. Except for a number of boundary states, all columns of the transition matrix are identical except for a shift which assures that there is always the same element occupying the main diagonal. This paper describes how one can find the equilibrium distribution for such Markov chains. Typically, this problem is solved by factorizing of a certain expression characterizing the repeated columns. In this paper, we show that this factorization has a probabilistic significance and we use this result to develop new approaches for finding the equilibrium distribution in question.     

The inverse M-matrix problem

One aspect of the inverse M-matrix problem can be posed as follows. Given a positive n × n matrix A=(a_ij) which has been scaled to have unit diagonal elements and off-diagonal elements which satisfy 0 < y ? a_ij ? x < 1, what additional element conditions will guarantee that the inverse of A exists and is an M-matrix? That is, if A^?1=B=(b_ij), then b_ii> 0 and b_ij ? 0 for i≠_j. If n=2 or x=y no further conditions are needed, but if n ? 3 and y < x, then the following is a tight sufficient condition. Define an interpolation parameter s via x²=sy+(1?s)y²; then B is an M-matrix if s^?1 ? n?2. Moreover, if all off-diagonal elements of A have the value y except for a_ij=a_jj=x when i=n?1, n and 1 ? _j ? n?2, then the condition on both necessary and sufficient for B to be an M-matrix.     

On p−q=c and related three term exponential Diophantine equations with prime bases

Using a theorem on linear forms in logarithms, we show that the equation p^x−2^y=p^u−2^v has no solutions (p,x,y,u,v) with x≠u, where p is a positive prime and x,y,u, and v are positive integers, except for four specific cases, or unless p is a Wieferich prime greater than 10¹⁵. More generally, we obtain a similar result for p^x−q^y=p^u−q^v>0 where q is a positive prime, . We solve a question of Edgar showing there is at most one solution (x,y) to p^x−q^y=2^h for positive primes p and q and positive integer h. Finally, we use elementary methods to show that, with a few explicitly listed exceptions, there are at most two solutions (x,y) to |p^x±q^y|=c and at most two solutions (x,y,z) to p^x±q^y±2^z=0, for given positive primes p and q and integer c.     

On x3 + y3 = D

The simplest case of Fermat's last theorem, the impossibility of solving x³ + y³ = z³ in nonzero integers, has been proved. In other words, 1 is not expressible as a sum of two cubes of rational numbers. However, the slightly extended problem, in which integers D are expressible as a sum of two cubes of rational numbers, is unsolved. There is the conjecture (based on work of Birch, Swinnerton-Dyer, and Stephens) that x³ + y³ = D is solvable in the rational numbers for all square-free positive integers D ≡ 4 (mod 9). The condition that D should be square-free is necessary. As an example, it is shown near the end of this paper that x³ + y³ = 4 has no solutions in the rational numbers. The remainder of this paper is concerned with the proof published by the first author (Proc. Nat. Acad. Sci. USA., 1963) entitled “Remarks on a conjecture of C. L. Siegel.” This pointed out an error in a statement of Siegel that the diophantine equation ax³ + bx²y + cxy² + dy³ = n has a bounded number of integer solutions for fixed a, b, c, d, and, further, that the bound is independent of a, b, c, d, and n. However, x³ + y³ = n already has an unbounded number of solutions. The paper of S. Chowla itself contains an error or at least an omission. This can be rectified by quoting a theorem of E. Lutz.     

On the diophantine equation y2 − D = 2k

The equation of the title is studied for 1 ≤ D ≤ 100. It is shown that for such values of D the above equation is really interesting only if D = 17, 41, 73, 89, 97. Then, for these values of D, (i) necessary conditions are given for the solvability of the diophantine equations y² = 2x⁴ + D and y² = 8x⁴ + D, and (ii) y² ? D = 2^k is solved.     

Algorithmic analysis of the Geo/Geo/c retrial queue

In this paper, we consider a discrete-time queue of Geo/Geo/c type with geometric repeated attempts. It is known that its continuous counterpart, namely the M/M/c queue with exponential retrials, is analytically intractable due to the spatial heterogeneity of the underlying Markov chain, caused from the retrial feature. In discrete-time, the occurrence of multiple events at each slot increases the complexity of the model and raises further computational difficulties. We propose several algorithmic procedures for the efficient computation of the main performance measures of this system. More specifically, we investigate the stationary distribution of the system state, the busy period and the waiting time. Several numerical examples illustrate the analysis.     

A noncommutative analogue of |D(Xk|=|kXk−1|

The paper concerns alternating powers of a Hilbert space. Let ∧^k be defined by ∧^k(A)(x₁∧?∧x_k)=Ax₁∧?∧Ax_k. It is proved that the norm of the linear map D∧^k(A) depends only upon |A| and is assumed at the identity.     

The diophantine equation x3 + 3y3 = 2n

It is proved that the equation of the title has a finite number of integral solutions (x, y, n) and necessary conditions are given for (x, y, n) in order that it can be a solution (Theorem 2). It is also proved that for a given odd x₀ there is at most one integral solution (y, n), n ≥ 3, to x₀³ + 3y³ = 2ⁿ and for a given odd y₀ there is at most one integral solution (x, n), n ≥ 3, to x³ + 3y₀³ = 2ⁿ.