Approximation of M/M/s/K retrial queue with nonpersistent customers

We consider the M/M/s/K retrial queues in which a customer who is blocked to enter the service facility may leave the system with a probability that depends on the number of attempts of the customer to enter the service facility. Approximation formulae for the distributions of the number of customers in service facility, waiting time in the system and the number of retrials made by a customer during its waiting time are derived. Approximation results are compared with the simulation.     

Containment of socially optimal policies in multiple-facility Markovian queueing systems

We consider a Markovian queueing system with N heterogeneous service facilities, each of which has multiple servers available, linear holding costs, a fixed value of service and a first-come-first-serve queue discipline. Customers arriving in the system can be either rejected or sent to one of the N facilities. Two different types of control policies are considered, which we refer to as ‘selfishly optimal’ and ‘socially optimal’. We prove the equivalence of two different Markov Decision Process formulations, and then show that classical M/M/1 queue results from the early literature on behavioural queueing theory can be generalized to multiple dimensions in an elegant way. In particular, the state space of the continuous-time Markov process induced by a socially optimal policy is contained within that of the selfishly optimal policy. We also show that this result holds when customers are divided into an arbitrary number of heterogeneous classes, provided that the service rates remain non-discriminatory.     

Strategic joining in M/M/1 retrial queues

The equilibrium and socially optimal balking strategies are investigated for unobservable and observable single-server classical retrial queues. There is no waiting space in front of the server. If an arriving customer finds the server idle, he occupies the server immediately and leaves the system after service. Otherwise, if the server is found busy, the customer decides whether or not to enter a retrial pool with infinite capacity and becomes a repeated customer, based on observation of the system and the reward–cost structure imposed on the system. Accordingly, two cases with respect to different levels of information are studied and the corresponding Nash equilibrium and social optimization balking strategies for all customers are derived. Finally, we compare the equilibrium and optimal behavior regarding these two information levels through numerical examples.     

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.     

Some results for the queues Mx/M/c and GIx/ G/c

We develop for the queue M^x/M/c an upper bound for the mean queue length and lower bounds for the delay probabilities (that of an arrival group and that of an arbitrary customer in the arrival group). An approximate formula is also developed for the general bulk-arrival queue GI^x/G/c. Preliminary numerical studies have indicated excellent performance of the results.     

On the GI/M/1/N queue with multiple working vacations—analytic analysis and computation

We consider finite buffer single server GI/M/1 queue with exhaustive service discipline and multiple working vacations. Service times during a service period, service times during a vacation period and vacation times are exponentially distributed random variables. System size distributions at pre-arrival and arbitrary epoch with some important performance measures such as, probability of blocking, mean waiting time in the system etc. have been obtained. The model has potential application in the area of communication network, computer systems etc. where a single channel is allotted for more than one source.     

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.     

Applications of bulk queues to group testing models with incomplete identification

A population of items is said to be “group-testable”, (i) if the items can be classified as “good” and “bad”, and (ii) if it is possible to carry out a simultaneous test on a batch of items with two possible outcomes: “Success” (indicating that all items in the batch are good) or “failure” (indicating a contaminated batch). In this paper, we assume that the items to be tested arrive at the group-testing centre according to a Poisson process and are served (i.e., group-tested) in batches by one server. The service time distribution is general but it depends on the batch size being tested. These assumptions give rise to the bulk queueing model M/G^(m,M)/1, where m and M(>m) are the decision variables where each batch size can be between m and M. We develop the generating function for the steady-state probabilities of the embedded Markov chain. We then consider a more realistic finite state version of the problem where the testing centre has a finite capacity and present an expected profit objective function. We compute the optimal values of the decision variables (m, M) that maximize the expected profit. For a special case of the problem, we determine the optimal decision explicitly in terms of the Lambert function.     

Some remarks on the meaning of equality in Diophantos’s Arithmetica

Diophantos in Arithmetica, without having defined previously any concept of “equality” or “equation,” employs a concept of the unknown number as a tool for solving problems and finds its value from an equality ad hoc created. In this paper we analyze Diophantos’s practices in the creation and simplification of such equalities, aiming to adduce more evidence on certain issues arising in recent historical research on the meaning of the “equation” in Diophantos’s work.     

On M-structures

We introduce the notion of M-structures and consider the class $\text{M}$ of stratifiable spaces with M-structures. Especially we study the relation between the class $\text{M}$ and that of M₁-spaces.     

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.     

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.     

Splitting manifolds as M × R where M has a k-fold end structure

Let X be a locally finite simplicial complex of dimension n, n? 5, equipped with a k-fold end structure [4] and consider a piecewise linear (n + 1)-dimensional manifold M that is proper homotopy equivalent to X × R by F:M → X × R, where R is the set of real numbers. The question arises as to whether or not the manifold M can be split, i.e., written as M = N × R where N is a n-manifold and where there is a proper homotopy between F and (p₁ ° F₀) × id:N × R → X × R, preserving the natural (k+1)-fold end structure, where F₀ is F|_N and p₁ is the projection X × R → X. Of particular significance is the fact that X is noncompact. When the construction of such splittings is attempted, algebraic obstructions arise, which vanish if and only if the construction can be completed. This paper develops such an obstruction theory by utilizing methods of L.C. Siebenmann and the k-fold end structures of F. Waldhausen.     

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.     

Stable invariant manifolds for parabolic dynamics

We consider nonautonomous equations v^′=A(t)v in a Banach space that exhibit stable and unstable behaviors with respect to arbitrary growth rates ecρ(t) for some function ρ(t). This corresponds to the existence of a “generalized” exponential dichotomy, which is known to be robust. When ρ(t)≠t this behavior can be described as a type of parabolic dynamics. We consider the general case of nonuniform exponential dichotomies, for which the Lyapunov stability is not uniform. We show that for any sufficiently small perturbation f of a “generalized” exponential dichotomy there is a stable invariant manifold for the perturbed equation v^′=A(t)v+f(t,v). We also consider the case of exponential contractions, which allow a simpler treatment, and we show that they persist under sufficiently small nonlinear perturbations.     

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.     

M-matrix asymptotics for Sturm–Liouville problems on graphs

We consider a system formulation for Sturm–Liouville operators with formally self-adjoint boundary conditions on a graph. An M-matrix associated with the boundary value problem is defined and related to the matrix Prüfer angle associated with the system boundary value problem, and consequently with the boundary value problem on the graph. Asymptotics for the M-matrix are obtained as the eigenparameter tends to negative infinity. We show that the boundary conditions may be recovered, up to a unitary equivalence, from the M-matrix and that the M-matrix is a Herglotz function. This is the first in a series of papers devoted to the reconstruction of the Sturm–Liouville problem on a graph from its M-matrix.     

Lindelöf spaces which are Menger, Hurewicz, Alster, productive, or D

We discuss relationships in Lindelöf spaces among the properties “Menger”, “Hurewicz”, “Alster”, “productive”, and “D”.     

Lindelöf spaces which are indestructible, productive, or D

We discuss relationships in Lindelöf spaces among the properties “indestructible”, “productive”, “D”, and related properties.     

On algebraic Riccati equations associated with M-matrices

We consider the algebraic Riccati equation for which the four coefficient matrices form an M-matrix K. When K is a nonsingular M-matrix or an irreducible singular M-matrix, the Riccati equation is known to have a minimal nonnegative solution and several efficient methods are available to find this solution. In this paper we are mainly interested in the case where K is a reducible singular M-matrix. Under a regularity assumption on the M-matrix K, we show that the Riccati equation still has a minimal nonnegative solution. We also study the properties of this particular solution and explain how the solution can be found by existing methods.