Strong Stability of Queues with Multiple Vacation of the Server

Abstract

The main purpose of this article is to use the strong stability method to approximate the characteristics of the M/G/1//N queue with server vacation by those of the classical M/G/1//N queue, when the rate of the vacations is sufficiently small. This last queue is simpler and more exploitable in practice. For this, we proof the stability conditions and next obtain quantitative stability estimates with an exact computation of constants. From these theoretical results, we can develop an algorithm in order to check the conditions of approximation. These results of approximation have a great practical and economic interest in reliability systems and maintenance optimization policy, when we consider elements with constant failure rate.     

Right order spectral gap estimates for generating sets of ℤ4

Using coupling arguments, a distance method and Zeifman's method we give sharp estimates on the spectral gap for a special case of the class of Markov chains on generating n‐tuples of Abelian groups. In our case the group is ?₄. © 2002 Wiley Periodicals, Inc. Random Struct. Alg. 20: 220–238, 2002     

L estimates on functions of Markov operators

We prove L estimates for functions of Markov operators on a discrete measure space of superpolynomial volume growth.

     

Exact formula for sensitivity analysis of Markov chains

Given a family of Markov chains whose transition matrices depend on a parameter vector, we given an exact formula for the gradient of the equilibrium distribution with respect to that parameter even in the case of multiple ergodic classes and transient states. This formula generalizes previous results in the ergodic case.     

Double-sided matching queues: Priority and impatient customers

We analyze a double-sided queue with priority that serves patient customers and customers with zero patience (i.e., impatient customers). In a two-sided market, high and low priority customers arrive to one side and match with queued customers on the opposite side. Impatient customers match with queued patient customers; when there is no queue, they leave the system unmatched. All arrivals follow independent Poisson processes. We derive exact formulae for the stationary queue length distribution and several steady-state performance measures.     

Time-discrete higher order ALE formulations: a priori error analysis

We derive optimal a priori error estimates for discontinuous Galerkin (dG) time discrete schemes of any order applied to an advection–diffusion model defined on moving domains and written in the Arbitrary Lagrangian Eulerian (ALE) framework. Our estimates hold without any restrictions on the time steps for dG with exact integration or Reynolds’ quadrature. They involve a mild restriction on the time steps for the practical Runge–Kutta–Radau methods of any order. The key ingredients are the stability results shown earlier in Bonito et al. (Time-discrete higher order ALE formulations: stability, 2013) along with a novel ALE projection. Numerical experiments illustrate and complement our theoretical results.     

Estimating mean time to absorption for a markov chain with limited information

In many applications of absorbing Markov chains, solution of the problem at hand involves finding the mean time to absorption. Moreover, in almost all real world applications of Markov chains, accurate estimation of the elements of the probability matrix is a major concern. This paper develops a technique that provides close estimates of the mean number of stages before absorption with only the row sums of the transition matrix of transient states.     

Approximate uniformization for continuous-time Markov chains with an application to performability analysis

An approximate version of the standard uniformization technique is introduced for application to continuous-time Markov chains with unbounded jump rates. This technique is shown to be asymptotically exact and an error bound for the order of its accuracy is provided. An illustrative queueing application is included.     

Simultaneous Occurrences of Runs in Independent Markov Chains

We observe m independent and identically distributed binary Markov chains and look for simultaneous occurrences of runs in several of them. We are interested in the distribution of the maximum number of simultaneous runs on finite time intervals. First we introduce a natural exact approach and also explain why it fails to calculate the required probabilities. Then we find exact upper and lower bounds for the probability of interest. We apply these results to detect genomic deletions in cancer patients.      

Optimal-order convergence rates for Eulerian-Lagrangian localized adjoint methods for reactive transport and contamination in groundwater

Eulerian–Langrangian localized adjoint methods (ELLAM) were developed to solve convection–diffusion–reaction equations governing contaminant transport in groundwater flowing through a porous medium, subject to various combinations of boundary conditions. In this article, we prove optimal-order error estimates and some superconvergence results for the ELLAM schemes. In contrast to many existing estimates for a variety of numerical methods, which often contain the temporal derivatives of the exact solution, our error estimates contain the total derivatives of the exact solution but do not involve any temporal derivatives of the exact solution. © 1995 John Wiley & Sons, Inc.     

Retrial queues with server subject to breakdowns and repairs

In this paper we consider a single server retrial queue where the server is subject to breakdowns and repairs. New customers arrive at the service station according to a Poisson process and demand i.i.d. service times. If the server is idle, the incoming customer starts getting served immediately. If the server is busy, the incoming customer conducts a retrial after an exponential amount of time. The retrial customers behave independently of each other. The server stays up for an exponential time and then fails. Repair times have a general distribution. The failure/repair behavior when the server is idle is different from when it is busy. Two different models are considered. In model I, the failed server cannot be occupied and the customer whose service is interrupted has to either leave the system or rejoin the retrial group. In model II, the customer whose service is interrupted by a failure stays at the server and restarts the service when repair is completed. Model II can be handled as a special case of model I. For model I, we derive the stability condition and study the limiting behavior of the system by using the tools of Markov regenerative processes.Visiting from Department of Applied Mathematics, Korea Advanced Institute of Science and Technology, Cheongryang, Seoul, Korea.     

Stability and monotonicity for interactive Markov chains

In a Markov chain model of a social process, interest often centers on the distribution of the population by state. One question, the stability question, is whether this distribution converges to an equilibrium value. For an ordinary Markov chain (a chain with constant transition probabilities), complete answers are available. For an interactive Markov chain (a chain which allows the transition probabilities governing each individual to depend on the locations by state of the rest of the population), few stability results are available. This paper presents new results. Roughly, the main result is that an interactive Markov chain with unique equilibrium will be stable if the chain satisfies a certain monotonicity property. The property is a generalization to interactive Markov chains of the standard definition of monotonicity for ordinary Markov chains.     

Random walks and the effective resistance of networks

In this article we present an interpretation ofeffective resistance in electrical networks in terms of random walks on underlying graphs. Using this characterization we provide simple and elegant proofs for some known results in random walks and electrical networks. We also interpret the Reciprocity theorem of electrical networks in terms of traversals in random walks. The byproducts are (a) precise version of thetriangle inequality for effective resistances, and (b) an exact formula for the expectedone-way transit time between vertices.     

Slow recurrent regimes for a class of one-dimensional stochastic growth models

We classify the possible behaviors of a class of one-dimensional stochastic recurrent growth models. In our main result, we obtain nearly optimal bounds for the tail of hitting times of some compact sets. If the process is an aperiodic irreducible Markov chain, we determine whether it is null recurrent or positive recurrent and in the latter case, we obtain a subgeometric convergence of its transition kernel to its invariant measure. We apply our results in particular to state-dependent Galton–Watson processes and we give precise estimates of the tail of the extinction time.     

On Markovian Multi-Class,Multi-Server Queueing

Multi-class multi-server queueing problems are a generalisation of the well-known M/M/k queue to arrival processes with clients of N types that require exponentially distributed service with different average service times. In this paper, we give a procedure to construct exact solutions of the stationary state equations using the special structure of these equations. Essential in this procedure is the reduction of a part of the problem to a backward second order difference equation with constant coefficients. It follows that the exact solution can be found by eigenmode decomposition. In general eigenmodes do not have a simple product structure as one might expect intuitively. Further, using the exact solution, all kinds of interesting performance measures can be computed and compared with heuristic approximations (insofar available in the literature). We provide some new approximations based on special multiplicative eigenmodes, including the dominant mode in the heavy traffic limit. We illustrate our methods with numerical results. It turns out that our approximation method is better for higher moments than some other approximations known in the literature. Moreover, we demonstrate that our theory is useful to applications where correlation between items plays a role, such as spare parts management.     

马氏环境中马氏链的Poisson极限律

本文研究了马氏环境中马氏链,证明了该过程于小柱集上的回返次数是渐近地服从Poisson分布的,同时还给出了该过程是(?)-混合的一个充分条件以及过程回返于小柱集之概率的一个指数估计式.     

Extremal indices, geometric ergodicity of Markov chains, and MCMC

We investigate the connections between extremal indices on the one hand and stability of Markov chains on the other hand. Both theories relate to the tail behaviour of stochastic processes, and we find a close link between the extremal index and geometric ergodicity. Our results are illustrated throughout with examples from simple MCMC chains.      

On multiple Markov chains

The aim of this paper is to examine multiple Markov dependence for the discrete as well as for the continuous parameter case. In both cases the Markov property with arbitrary parameter values is investigated and it is shown that it leads to the degeneration of the multiple Markov dependence to the simple one.     

三叉树上分支马氏链的等价性质

在二叉树上分支马氏链的等价性质研究的基础上,给出了三叉树上分支马氏链定义的离散形式,除了把二叉树上分支马氏链的两个等价性质平移到三叉树上分支马氏链以外,又给出了三叉树上分支马氏链的两个等价性质及两个性质.得出结论的关键方法是在概率乘积公式及条件概率公式的计算中正确处理其中所涉及到的许多繁杂的必然事件.     

二叉树上分支马氏链的等价性质

本文给出了二叉树上分支马氏链定义的离散形式,然后研究了它的两个等价性质.最后,我们指出在二叉树情况下,树指标马氏链就是一类特殊的分支马氏链.