Large deviations without principle: join the shortest queue

We develop a methodology for studying “large deviations type” questions. Our approach does not require that the large deviations principle holds, and is thus applicable to a large class of systems. We study a system of queues with exponential servers, which share an arrival stream. Arrivals are routed to the (weighted) shortest queue. It is not known whether the large deviations principle holds for this system. Using the tools developed here we derive large deviations type estimates for the most likely behavior, the most likely path to overflow and the probability of overflow. The analysis applies to any finite number of queues. We show via a counterexample that this system may exhibit unexpected behavior Work of the first author was performed in part while visiting the Technion. Work of the second author was performed in part while visiting the Vrije Universiteit, Amsterdam, and was supported in part by Fund for the promotion of research at the Technion.     

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.     

On the Introduction of an Agile, Temporary Workforce into a Tandem Queueing System

We consider a two-station tandem queueing system where customers arrive according to a Poisson process and must receive service at both stations before leaving the system. Neither queue is equipped with dedicated servers. Instead, we consider three scenarios for the fluctuations of workforce level. In the first, a decision-maker can increase and decrease the capacity as is deemed appropriate; the unrestricted case. In the other two cases, workers arrive randomly and can be rejected or allocated to either station. In one case the number of workers can then be reduced (the controlled capacity reduction case). In the other they leave randomly (the uncontrolled capacity reduction case). All servers are capable of working collaboratively on a single job and can work at either station as long as they remain in the system. We show in each scenario that all workers should be allocated to one queue or the other (never split between queues) and that they should serve exhaustively at one of the queues depending on the direction of an inequality. This extends previous studies on flexible systems to the case where the capacity varies over time. We then show in the unrestricted case that the optimal number of workers to have in the system is non-decreasing in the number of customers in either queue. AMS subject classification: 90B22, 90B36     

Large Deviations of Queues Sharing a Randomly Time-Varying Server

We consider a discrete-time model where multiple queues, each with its own exogenous arrival process, are served by a server whose capacity varies randomly and asynchronously with respect to different queues. This model is primarily motivated by the problem of efficient scheduling of transmissions of multiple data flows sharing a wireless channel. We address the following problem of controlling large deviations of the queues: find a scheduling rule, which is optimal in the sense of maximizing

Approximation of throughput in tandem queues with multiple servers and blocking

In this paper, we develop an approximation method for throughput in tandem queues with multiple independent reliable servers at each stage and finite buffers between service stations. We consider the blocking after service (BAS) blocking protocol of each service stage. The service time distribution of each server is exponential. The approximation is based on the decomposition of the system into a set of coupled subsystems which are modeled by two-stage tandem queue with two buffers and are analyzed by using the level dependent quasi-birth-and-death (LDQBD) process.     

A scheduling problem for several parallel servers

In this paper, we study a scheduling problem of jobs from two different queues on several parallel servers. Jobs have exponentially distributed processing times, and incur costs per unit of time, until they leave the system, and there are no arrivals to the system at any time. The objective is to find the optimal strategy, i.e., to allocate the servers to the queues, such that the expected holding costs are minimized. We give a sufficient condition for which it is always optimal to allocate the servers only to jobs of a certain queue. Finally, the case of two servers is completely solved.     

Two Queues with Weighted One-Way Overflow

We consider an open queueing network consisting of two queues with Poisson arrivals and exponential service times and having some overflow capability from the first to the second queue. Each queue is equipped with a finite number of servers and a waiting room with finite or infinite capacity. Arriving customers may be blocked at one of the queues depending on whether all servers and/or waiting positions are occupied. Blocked customers from the first queue can overflow to the second queue according to specific overflow routines. Using a separation method for the balance equations of the two-dimensional server and waiting room demand process, we reduce the dimension of the problem of solving these balance equations substantially. We extend the existing results in the literature in three directions. Firstly, we allow different service rates at the two queues. Secondly, the overflow stream is weighted with a parameter p ∈ [0,1], i.e., an arriving customer who is blocked and overflows, joins the overflow queue with probability p and leaves the system with probability 1 − p. Thirdly, we consider several new blocking and overflow routines. An erratum to this article can be found at     

Stability criteria for controlled queueing systems

We give an almost complete classification of ergodicity and transience conditions for a general multi-queue system with the following features: arrivals form Poisson streams and there are various routing schemes for allocating arrivals to queues; the servers can be configured in a variety of ways; completed jobs can feed back into the system; the exponential service times and feedback probabilities depend upon the configuration of the servers (this model includes some types of multi-class queueing system); switching between service regimes is instantaneous. Several different levels of control of the service regimes are considered. Our results for the N-queue system require randomisation of service configurations but we have studied the two queue system in situations where there is less control. We use the semi-martingale methods described in Fayolle, Malyshev and Menshikov [3] and our results generalise Kurkova [8] and complement Foley and McDonald [4] and [5]. AMS 2000 subject classification: Primary: 90B22; Secondary: 60J10 90B15     

Asymptotically optimal control of parallel tandem queues with loss

We consider admission and routing controls for a system of N parallel tandem queues with finite buffers as N becomes large, with the aim of minimizing costs due to loss. We obtain the fluid limit as N→∞, and solve a related optimization problem. Asymptotically, for N large, the optimal cost and associated control take one of two forms, depending on the ratio between the cost of blocking an arrival at entry and discarding after service at the first queue.     

Diffusion approximation for an overloaded X model via a stochastic averaging principle

In previous papers we developed a deterministic fluid approximation for an overloaded Markovian queueing system having two customer classes and two service pools, known in the call-center literature as the X model. The system uses the fixed-queue-ratio-with-thresholds (FQR-T) control, which we proposed as a way for one service system to help another in face of an unexpected overload. Under FQR-T, customers are served by their own service pool until a threshold is exceeded. Then, one-way sharing is activated with customers from one class allowed to be served in both pools. The control aims to keep the two queues at a pre-specified fixed ratio. We supported the fluid approximation by establishing a functional weak law of large numbers involving a stochastic averaging principle. In this paper we develop a refined diffusion approximation for the same model based on a many-server heavy-traffic functional central limit theorem.     

Moderate deviations for time-varying dynamic systems driven by non-homogeneous Markov chains with Two-time Scales

Motivated by problems arising in time-dependent queues and dynamic systems with random environment, this work develops moderate deviations principles for dynamic systems driven by a fast-varying non-homogeneous Markov chain in continuous time. A distinct feature is that the Markov chain is time dependent or inhomogeneous, so are the dynamic systems. Under irreducibility of the non-homogeneous Markov chain, moderate deviations of a non-homogeneous functional are established first. With the help of a martingale problem formulation and a functional central limit theorem for the two timescale system, both upper and lower bounds of moderate deviations are obtained for the rapidly fluctuating Markovian systems. Then applications to queueing systems and dynamic systems modulated by a fast-varying Markov chain are examined.     

Optimal admission and pricing control problems in service industries with multiple servers and sideline profit

This paper deals with the problem of selecting profitable customer orders sequentially arriving at a company operating in service industries with multiple servers in which two classes of services are provided. The first class of service is designed to meet the particular needs of customers; and the company (1) makes a decision on whether to accept or to reject the order for this service (admission control) and (2) decides a price of the order and offers it to an arriving customer (pricing control). The second class of service is provided as a sideline, which prevents servers from being idle when the number of customer orders for the first class is less than the number of servers. This yields the sideline profit. A cost is paid to search for customer orders, which is called the search cost. In the context of search cost, the company has an option whether to conduct the search or not. In this paper, we discuss both admission control and pricing control problems within an identical framework as well as examine the structure of the optimal policies to maximize the total expected net profit gained over an infinite planning horizon. We show that when the sideline profit is large, the optimal policies may not be monotone in the number of customer orders in the system. Copyright © 2008 John Wiley & Sons, Ltd.     

Equilibrium customers’ choice between FCFS and random servers

Consider two servers of equal service capacity, one serving in a first-come first-served order (FCFS), and the other serving its queue in random order. Customers arrive as a Poisson process and each arriving customer observes the length of the two queues and then chooses to join the queue that minimizes its expected queueing time. Assuming exponentially distributed service times, we numerically compute a Nash equilibrium in this system, and investigate the question of which server attracts the greater share of customers. If customers who arrive to find both queues empty independently choose to join each queue with probability 0.5, then we show that the server with FCFS discipline obtains a slightly greater share of the market. However, if such customers always join the same queue (say of the server with FCFS discipline) then that server attracts the greater share of customers. This research was supported by the Israel Science Foundation grant No. 526/08.     

MAP/(PH/PH)/c Queue with Self-Generation of Priorities and Non-Preemptive Service

Abstract

Customers arriving according to a Markovian arrival process are served at a c server facility. Waiting customers generate into priority while waiting in the system (self-generation of priorities), at a constant rate γ; such a customer is immediately taken for service, if at least one of the servers is free. Else it waits at a waiting space of capacity c exclusively for priority generated customers, provided there is vacancy. A customer in service is not preempted to accommodate a priority generated customer. The service times of ordinary and priority generated customers follow distinct PH-distributions. It is proved that the system is always stable. We provide a numerical procedure to compute the optimal number of servers to be employed to minimize the loss to the system. Several performance measures are evaluated.     

A single server queue with service interruptions

In this paper we characterize the queue-length distribution as well as the waiting time distribution of a single-server queue which is subject to service interruptions. Such queues arise naturally in computer and communication problems in which customers belong to different classes and share a common server under some complicated service discipline. In such queues, the viewpoint of a given class of customers is that the server is not available for providing service some of the time, because it is busy serving customers from a different class. A natural special case of these queues is the class of preemptive priority queues. In this paper, we consider arrivals according the Markovian Arrival Process (MAP) and the server is not available for service at certain times. The service times are assumed to have a general distribution. We provide numerical examples to show that our methods are computationally feasible. This revised version was published online in June 2006 with corrections to the Cover Date.     

Matrix analytic methods for a multi-server retrial queue with buffer

We present numerical methods for obtaining the stationary distribution of states for multi-server retrial queues with Markovian arrival process, phase type service time distribution with two states and finite buffer; and moments of the waiting time. The methods are direct extensions of the ones for the single server retrial queues earlier developed by the authors. The queue is modelled as a level dependent Markov process and the generator for the process is approximated with one which is spacially homogeneous above some levelN. The levelN is chosen such that the probability associated with the homogeneous part of the approximated system is bounded by a small tolerance and the generator is eventually truncated above that level. Solutions are obtained by efficient application of block Gaussian elimination.     

Factorization and Stochastic Decomposition Properties in Bulk Queues with Generalized Vacations

This paper considers a class of stationary batch-arrival, bulk-service queues with generalized vacations. The system consists of a single server and a waiting room of infinite capacity. Arrivals of customers follow a batch Markovian arrival process. The server is unavailable for occasional intervals of time called vacations, and when it is available, customers are served in groups of fixed size B. For this class of queues, we show that the vector probability generating function of the stationary queue length distribution is factored into two terms, one of which is the vector probability generating function of the conditional queue length distribution given that the server is on vacation. The special case of batch Poisson arrivals is carefully examined, and a new stochastic decomposition formula is derived for the stationary queue length distribution.AMS subject classification: 60K25, 90B22, 60K37     

Equilibrium and optimal behavior of customers in Markovian queues with multiple working vacations

This paper studies the customers’ equilibrium and socially optimal joining–balking behavior in single-server Markovian queues with multiple working vacations. Different from the classical vacation policies, the server does not completely stop service but maintains a low service rate in vacation state in case there are customer arrivals. Based on different precision levels of the system information, we discuss the observable queues, the partially observable queues, and the unobservable queues, respectively. For each type of queues, we get both the customers’ equilibrium and socially optimal joining–balking strategies and make numerical comparisons between them. We numerically observe that their equilibrium strategy is unique, and especially, the customers’ equilibrium joining probability in vacation state is not necessarily smaller than that in busy state in the partially observable queues. Moreover, we also find that the customers’ individual behavior always deviates from the social expectation and makes the system more congested.     

A stability criterion via fluid limits and its application to a polling system

We introduce a generalized criterion for the stability of Markovian queueing systems in terms of stochastic fluid limits. We consider an example in which this criterion may be applied: a polling system with two stations and two heterogeneous servers. This revised version was published online in June 2006 with corrections to the Cover Date.