Analysis of ticket queues with reneging customers

In this paper we analyse queues in which customer waiting positions are represented by ticket numbers. The customers at any time can observe the number being served and may leave the queue without obtaining the service (reneging). Assuming the customers’ tendency to renege depends dynamically on the difference between their ticket number and the number being served, we develop an approximation procedure in order to calculate the percentage of reneging customers. We give a detailed exposition of the analysis for the case of single-server system and provide a highlight of extension to multi-server systems. As an application of the approximating procedure, we also illustrate numerically that, under a hypothetical reneging behaviour, offering customers extra information on the actual queue length can reduce the customer reneging percentage by as much as 65%.     

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.     

Matching queues with reneging: a product form solution

Queueing Systems - Motivated by growing applications in two-sided markets, we study a parallel matching queue with reneging. Demand and supply units arrive to the system and are matched in an FCFS...     

Nonstationary Markovian queues

For a class of Markov queues, we estimate the decay function in different types of exponential convergence. Proceedings of the Seminar on Stability Problems for Stochastic Models, Vologda, Russia, 1998, Part II.     

Diffusion approximations for double-ended queues with reneging in heavy traffic

We study a double-ended queue consisting of two classes of customers. Whenever there is a pair of customers from both classes, they are matched and leave the system. The matching is instantaneous following the first-come–first-match principle. If a customer cannot be matched immediately, he/she will stay in a queue. We also assume customers are impatient with generally distributed patience times. Under suitable heavy traffic conditions, we establish simple linear asymptotic relationships between the diffusion-scaled queue length process and the diffusion-scaled offered waiting time processes and show that the diffusion-scaled queue length process converges weakly to a diffusion process that admits a unique stationary distribution.

     

Multiclass Markovian fluid queues

This paper considers a multiclass Markovian fluid queue with a buffer of infinite capacity. Input rates of fluid flows in respective classes and the drain rate from the buffer are modulated by a continuous-time Markov chain with finite states. We derive the joint Laplace-Stieltjes transform for the stationary buffer contents in respective classes, assuming the FIFO service discipline. Further we develop a numerically feasible procedure to compute the joint and marginal moments of the stationary buffer contents in respective classes. Some numerical examples are then provided.     

Exponential bounds for queues with Markovian arrivals

Exponential bounds [queueb]e ^b are found for queues whose increments are described by Markov Additive Processes. This is done by application of maximal inequalities to exponential martingales for such processes. Through a thermodynamic approach the constant is shown to be the decay rate for an asymptotic lower bound for the queue length distribution. The class of arrival processes considered includes a wide variety of Markovian multiplexer models, and a general treatment of these is given, along with that of Markov modulated arrivals. Particular attention is paid to the calculation of the prefactor .     

Bayesian inference in Markovian queues

This paper is concerned with the Bayesian analysis of general queues with Poisson input and exponential service times. Joint posterior distribution of the arrival rate and the individual service rate is obtained from a sample consisting inn observations of the interarrival process andm complete service times. Posterior distribution of traffic intensity inM/M/c is also obtained and the statistical analysis of the ergodic condition from a decision point of view is discussed.     

Approximations for Markovian multi-class queues with preemptive priorities

We discuss the approximation of performance measures in multi-class M/M/k queues with preemptive priorities for large problem instances (many classes and servers) using class aggregation and server reduction. We compared our approximations to exact and simulation results and found that our approach yields small-to-moderate approximation errors.     

Prediction in Markovian bulk arrival queues

This paper deals with the statistical analysis of bulk arrival queues from a Bayesian point of view. The focus is on prediction of the usual measures of performance of the system in equilibrium. Posterior predictive distribution of the number of customers in the system is obtained through its probability generating function. Posterior distribution of the waiting time, in the queue and in the system, of the first customer of an arriving group is expressed in terms of their Laplace and Laplace–Stieltjes transform. Discussion of numerical inversion of these transforms is addressed.     

Markovian bulk-arrival and bulk-service queues with general state-dependent control

We study a modified Markovian bulk-arrival and bulk-service queue incorporating general state-dependent control. The stopped bulk-arrival and bulk-service queue is first investigated, and the relationship between this stopped queue and the full queueing model is examined and exploited. Using this relationship, the equilibrium behaviour for the full queueing process is studied and the probability generating function of the equilibrium distribution is obtained. Queue length behaviour is also examined, and the Laplace transform of the queue length distribution is presented. The important questions regarding hitting times and busy period distributions are answered in detail, and the Laplace transforms of these distributions are presented. Further properties regarding the busy period distributions including expectation and conditional expectation of busy periods are also explored.

     

Equilibrium balking strategies in Markovian queues with working vacations

The equilibrium balking strategies are investigated in the paper for observable and unobservable single-server queues with working vacations. In such an M/M/1 queue with working vacations, the server undertakes the workload with a lower service rate rather than completely stops to work during the vacation period. Upon arrival, the customers decide whether to join or balk the queue based on observation of the queue length and the status of the server, along with the reward-cost structure of the system. Accordingly, four cases with respect to different levels of information are studied and the corresponding Nash equilibria are derived. Finally, the effect of the information levels as well as several parameters on the equilibrium threshold and equilibrium entrance probabilities is illustrated by numerical examples.     

Recursive calculation of moments in priority queues

We reconsider the discrete-time priority queue with two classes. The server serves high-priority customers as long as there are such customers, and only turns to the low-priority customers when there are no high-priority customers. Relying on a multivariate recursive extension of Faà di Bruno's formula, we find recursive equations to calculate the moments of the queue lengths. This allows for calculation of many more moments in much shorter time than conventionally possible.     

Decay properties of Markovian bulk-arrival and bulk-service queues with state-independent control

We consider decay properties regarding decay parameter and invariant measures of Markovian bulk-arrival and bulk-service queues with state-independent control. The exact value of the decay parameter, denoted by λz, is firstly revealed. A criterion regarding ）λz-recurrence and λz-positive is obtained. The corresponding λz-subinvariant/invariant measures and λz-subinvariant/invariant vectors are then presented.     

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.     

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.     

Perturbation bounds and truncations for a class of Markovian queues

We consider time-inhomogeneous Markovian queueing models with batch arrivals and group services. We study the mathematical expectation of the respective queue-length process and obtain the bounds on the rate of convergence and error of truncation of the process. Specific queueing models are shown as examples.     

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.     

Fluid models for many-server Markovian queues in a changing environment

Motivated by service systems with time-varying customer arrivals, we consider a fluid model as a macroscopic approximation for many-server Markovian queues alternating between underloaded and overloaded intervals. Our main result is a refinement of the piecewise stationary approximation (PSA) for the stationary distribution of the fluid model. The form of the refined approximation suggests simple metrics for assessing the accuracy of PSA for underloaded and overloaded intervals respectively.     

Customer equilibrium and optimal strategies in Markovian queues in series

We consider series of M/M/m queues with strategic customer behavior. Customers arrive to the first queue and decide whether to enter the system or balk and, if they enter, up to which queue to proceed before departing. Each customer makes an independent decision, with the objective of maximizing her total net benefit, which is equal to the value of service minus a cost due to expected delay. We formulate the customer decision as a game and identify the unique symmetric Nash equilibrium strategy, which is expressed in a backward recursive form. We also analyze the problem of maximizing the total customer welfare and establish the relationship between the equilibrium and the welfare maximizing strategies.