A sequential technique for the control of traffic intensity in Markovian queues

A sequential parameter control technique previously introduced by the author is modified in this paper so as to make it simple in practice. The detailed procedure involving two phases, a warning phase with control limits and a testing phase using an appropriate test is illustrated for a queueing system with an embedded Markov chain. Operating characteristics of the procedure are also examined.     

A Markovian single server with upstream job and downstream demand arrival stream

In this paper we consider a Markovian single server system which processes items arriving from an upstream region (as usual in queueing systems) and is controlled by a demand arrival stream for finished items from a downstream area. A finite storage is available at the server to store finished items not immediately needed in the downstream area. The system considered corresponds to an assembly-like queue with two input streams. The system is stable in a strict sense only if all queues are finite, i.e., both random processes are synchronized via blocking. This notion leads to a complementary system with a very similar state space which is a pair of Markovian single servers with synchronous arrivals. In the mathematical analysis the main focus is on the state probabilities and expectation of minimum and maximum of the two input queues. This revised version was published online in June 2006 with corrections to the Cover Date.     

Markovian queues with Poisson control

We investigate Markovian queues that are examined by a controller at random times determined by a Poisson process. Upon examination, the controller sets the service speed to be equal to the minimum of the current number of customers in the queue and a certain maximum service speed; this service speed prevails until the next examination time. We study the resulting two-dimensional Markov process of queue length and server speed, in particular two regimes with time scale separation, specifically for infinitely frequent and infinitely long examination times. In the intermediate regime the analysis proves to be extremely challenging. To gain further insight into the model dynamics we then analyse two variants of the model in which the controller is just an observer and does not change the speed of the server.     

A Markovian queueing model for ambulance offload delays

Ambulance offload delays are a growing concern for health care providers in many countries. Offload delays occur when ambulance paramedics arriving at a hospital Emergency Department (ED) cannot transfer patient care to staff in the ED immediately. This is typically caused by overcrowding in the ED. Using queueing theory, we model the interface between a regional Emergency Medical Services (EMS) provider and multiple EDs that serve both ambulance and walk-in patients. We introduce Markov chain models for the system and solve for the steady state probability distributions of queue lengths and waiting times using matrix-analytic methods. We develop several algorithms for computing performance measures for the system, particularly the offload delays for ambulance patients. Using these algorithms, we analyze several three-hospital systems and assess the impact of system resources on offload delays. In addition, simulation is used to validate model assumptions.     

A heuristic technique for the transient behavior of Markovian queueing systems

Through an examination of numerical solutions to Markovian queueing systems, it has been shown that the expected queue length eventually approaches its equilibrium value in an approximately exponential manner. Based on this observation a heuristic is proposed for approximating the transient expected queue length for Markovian systems by scaling the numerical solution of an M/M/1 system.     

Empirical Bayes estimation for queueing systems and networks

Empirical Bayes estimators are derived for standardM/M/1 queues,M/M/1 queues with state-dependent arrival and service rates, finite capacityM/M/1 queues with state-dependent rates and for open Jackson networks. The asymptotic properties of the empirical Bayes estimators are derived both with respect to the conditional distribution of the observations given the parameters, and with respect to the joint distribution of the observations and the parameters.     

Multigrid algorithm from cyclic reduction for Markovian queueing networks

A multigrid method based on cyclic reduction strategy is proposed to solve huge, nonsymmetric singular linear systems arising from Markovian queueing networks. A simple way to construct the matrix-dependent prolongation and restriction operators is presented in this paper. Numerical results for multiple queues are given to illustrate the efficiency and robustness of our methods.     

S-modular games,with queueing applications

The notion ofS-modularity was developed by Glasserman and Yao [9] in the context of optimal control of queueing networks.S-modularity allows the objective function to be supermodular in some variables and submodular in others. It models both compatible and conflicting incentives, and hence conveniently accommodates a wide variety of applications. In this paper, we introduceS-modularity into the context ofn-player noncooperative games. This generalizes the well-known supermodular games of Topkis [22], where each player maximizes a supermodular payoff function (or equivalently, minimizes a submodular payoff function). We illustrate the theory through a variety of applications in queueing systems.Supported in part by NSF Grant MSS-92-16490, and by Columbia's Center for Telecommunications Research.     

Shock models under a Markovian arrival process

A device submitted to shocks arriving randomly and causing damage is considered. Every shock can be fatal or not. The shocks follow a Markovian arrival process. When the shock is fatal, the device is instantaneously replaced. The Markov process governing the shocks is constructed, and the stationary probability vector calculated. The probability of the number of replacements during a time is determined. A particular case in which the fatal shock occurs after a fixed number of shocks is introduced, and a numerical application is performed. The expressions are in algorithmic form due to the use of matrix-analytic methods. Computational aspects are introduced. This model extends others previously considered in the literature.     

On the core of cooperative queueing games

We consider a class of cooperative games for managing several canonical queueing systems. When cooperating parties invest optimally in common capacity or choose the optimal amount of demand to serve, cooperation leads to “single-attribute” games whose characteristic function is embedded in a one-dimensional function. We show that when and only when the latter function is elastic will all embedded games have a non-empty core, and the core contains a population monotonic allocation. We present sufficient conditions for this property to be satisfied. Our analysis reveals that in most Erlang B and Erlang C queueing systems, the games under our consideration have a non-empty core, but there are exceptions, which we illustrate through a counterexample.     

Diffusion Approximations for Queues with Markovian Bases

Consider a base family of state-dependent queues whose queue-length process can be formulated by a continuous-time Markov process. In this paper, we develop a piecewise-constant diffusion model for an enlarged family of queues, each of whose members has arrival and service distributions generalized from those of the associated queue in the base. The enlarged family covers many standard queueing systems with finite waiting spaces, finite sources and so on. We provide a unifying explicit expression for the steady-state distribution, which is consistent with the exact result when the arrival and service distributions are those of the base. The model is an extension as well as a refinement of the M/M/s-consistent diffusion model for the GI/G/s queue developed by Kimura [13] where the base was a birth-and-death process. As a typical base, we still focus on birth-and-death processes, but we also consider a class of continuous-time Markov processes with lower-triangular infinitesimal generators.     

Strong approximations for Markovian service networks

Inspired by service systems such as telephone call centers, we develop limit theorems for a large class of stochastic service network models. They are a special family of nonstationary Markov processes where parameters like arrival and service rates, routing topologies for the network, and the number of servers at a given node are all functions of time as well as the current state of the system. Included in our modeling framework are networks of M _t /M _t /n _t queues with abandonment and retrials. The asymptotic limiting regime that we explore for these networks has a natural interpretation of scaling up the number of servers in response to a similar scaling up of the arrival rate for the customers. The individual service rates, however, are not scaled. We employ the theory of strong approximations to obtain functional strong laws of large numbers and functional central limit theorems for these networks. This gives us a tractable set of network fluid and diffusion approximations. A common theme for service network models with features like many servers, priorities, or abandonment is “non-smooth” state dependence that has not been covered systematically by previous work. We prove our central limit theorems in the presence of this non-smoothness by using a new notion of derivative. This revised version was published online in June 2006 with corrections to the Cover Date.     

Monotone control of queueing networks

This paper uses submodularity to obtain monotonicity results for a class of Markovian queueing network service rate control problems. Nonlinear costs of queueing and service are allowed. In contrast to Weber and Stidham [14], our monotonicity theorem considers arbitrary directions in the state space (not just control directions), arrival routing problems, and certain uncontrolled service rates. We also show that, without service costs, transition-monotone controls can be described by simple control regions and switching functions. The theory is applied to queueing networks that arise in a manufacturing system that produces to a forecast of customer demand, and also to assembly and disassembly networks.     

The heavy traffic limit of a class of Markovian queueing models

Reflected Brownian motion is obtained as the heavy traffic limit of the level component (Q_n) of a class of bivariate Markov chains {(J_n, Q_n)} incorporating those having a matrix-geometric stationary distribution. Approximations for both transient and ergodic behaviour are obtained as a corollary and illustrated for the Markov-modulated M/M/1 queue.     

Estimation of time-varying ARMA models with Markovian changes in regime

In this paper, we consider the estimation of time-varying ARMA models subject to Markovian changes in regime. We give explicit conditions ensuring consistency and asymptotic normality, as well as the limiting covariance matrix, of least squares and quasi-generalized least-squares estimators.     

Traffic processes in a class of finite Markovian queues

This paper exposes the stochastic structure of traffic processes in a class of finite state queueing systems which are modeled in continuous time as Markov processes. The theory is presented for theM/E _k /φ/L class under a wide range of queue disciplines. Particular traffic processes of interest include the arrival, input, output, departure and overflow processes. Several examples are given which demonstrate that the theory unifies many earlier works, as well as providing some new results. Several extensions to the model are discussed.     

Waiting time analysis of a two-stage queueing system with priorities

A two-stage queueing system with two types of customers and non-preemptive priorities is analyzed. There is no waiting space between stages and so the blocking phenomenon is observed. The arrivals follow a Poisson distribution for the high priority customers and a gamma distribution for the low priority customers, while all service times are arbitrarily distributed. We derive expressions for the Laplace transform of the waiting time density of a low priority customer both in the transient and the steady state.     

Cost allocation in a bank ATM network

We consider a situation in which a group of banks consider connecting their Automated Teller Machines (ATMs) in a network, so that the banks customers may use ATMs of any bank in the network. The problem studied is that of allocating the total transaction costs arising in the network, among the participating banks. The situation is modeled as a cooperative game with transferable utility. We propose two allocations, and discuss their relation to the core and other well-known solution concepts, as well as to population monotonicity.Endre Bjørndal has enjoyed the hospitality of Tilburg University, and has also received financial support from Telenor AS and the Norwegian School of Economics and Business Administration.     

A Diffusion Approximation for a Markovian Queue with Reneging

Consider a single-server queue with a Poisson arrival process and exponential processing times in which each customer independently reneges after an exponentially distributed amount of time. We establish that this system can be approximated by either a reflected Ornstein–Uhlenbeck process or a reflected affine diffusion when the arrival rate exceeds or is close to the processing rate and the reneging rate is close to 0. We further compare the quality of the steady-state distribution approximations suggested by each diffusion.     

An explicit solution to a tandem queueing model

We consider two queues in tandem, each with an exponential server, and with deterministic arrivals to the first queue. We obtain an explicit solution for the steady state distribution of the process (N₁(t), N₂(t), Y(t)), where N_j(t) is the queue length in the jth queue and Y(t) measures the time elapsed since the last arrival. Then we obtain the marginal distributions of (N₁(t), N₂(t)) and of N₂(t). We also evaluate the solution in various limiting cases, such as heavy traffic. This revised version was published online in June 2006 with corrections to the Cover Date.