Rational Abandonment from Tele-Queues: Nonlinear Waiting Costs with Heterogeneous Preferences

We consider the modelling of abandonment from a queueing system by impatient customers. Within the proposed model, customers act rationally to maximise a utility function that weights service utility against expected waiting cost. Customers are heterogeneous, in the sense that their utility function parameters may vary across the customer population. The queue is assumed invisible to waiting customers, who do not obtain any information regarding their standing in the queue during their waiting period. Such circumstances apply, for example, in telephone centers or other remote service facilities, to which we refer as tele-queues. We analyse this decision model within a multi-server queue with impatient customers, and seek to characterise the Nash equilibria of this system. These equilibria may be viewed as stable operating points of the system, and determine the customer abandonment profile along with other system-wide performance measures. We provide conditions for the existence and uniqueness of the equilibrium, and suggest procedures for its computation. We also suggest a notion of an equilibrium based on sub-optimal decisions, the myopic equilibrium, which enjoys favourable analytical properties. Some concrete examples are provided to illustrate the modelling approach and analysis. The present paper supplements previous ones which were restricted to linear waiting costs or homogeneous customer population.     

Synchronized abandonments in a single server unreliable queue

We consider a single server unreliable queue represented by a 2-dimensional continuous-time Markov chain. At failure times, the present customers leave the system. Moreover, customers become impatient and perform synchronized abandonments, as long as the server is down. We analyze this model and derive the main performance measures using results from the basic q-hypergeometric series.     

A recursive method for the F-policy G/M/1/K queueing system with an exponential startup time

This paper deals with the optimal control of a finite capacity G/M/1 queueing system combined the F-policy and an exponential startup time before start allowing customers in the system. The F-policy queueing problem investigates the most common issue of controlling arrival to a queueing system. We provide a recursive method, using the supplementary variable technique and treating the supplementary variable as the remaining interarrival time, to develop the steady-state probability distribution of the number of customers in the system. We illustrate a recursive method by presenting three simple examples for exponential, 3-stage Erlang, and deterministic interarrival time distributions, respectively. A cost model is developed to determine the optimal management F-policy at minimum cost. We use an efficient Maple computer program to determine the optimal operating F-policy and some system performance measures. Sensitivity analysis is also studied.     

Analysis of an open tandem queueing network with population constraint and constant service times 1

We consider an open tandem queueing network with population constraint and constant service times. The total number of customers that may be present in the network can not exceed a given value K. Customers arriving at the queueing network when there are more than K customers are forced to wait in an external queue. The arrival process to the queueing network is assumed to be arbitrary. We show that this queueing network can be transformed into a simple network involving only two nodes. Using this simple network, we obtain an upper and lower bound on the mean waiting time. These bounds can be easily calculated. Validations against simulation data establish the tightness of these bounds.     

Tandem queueing system with infinite and finite intermediate buffers and generalized phase-type service time distribution

A tandem queueing system with infinite and finite intermediate buffers, heterogeneous customers and generalized phase-type service time distribution at the second stage is investigated. The first stage of the tandem has a finite number of servers without buffer. The second stage consists of an infinite and a finite buffers and a finite number of servers. The arrival flow of customers is described by a Marked Markovian arrival process. Type 1 customers arrive to the first stage while type 2 customers arrive to the second stage directly. The service time at the first stage has an exponential distribution. The service times of type 1 and type 2 customers at the second stage have a phase-type distribution with different parameters. During a waiting period in the intermediate buffer, type 1 customers can be impatient and leave the system. The ergodicity condition and the steady-state distribution of the system states are analyzed. Some key performance measures are calculated. The Laplace–Stieltjes transform of the sojourn time distribution of type 2 customers is derived. Numerical examples are presented.     

Maximum Entropy Condition in Queueing Theory

The main results in queueing theory are obtained when the queueing system is in a steady-state condition and if the requirements of a birth-and-death stochastic process are satisfied. The aim of this paper is to obtain a probabilistic model when the queueing system is in a maximum entropy condition. For applying the entropic approach, the only information required is represented by mean values (mean arrival rates, mean service rates, the mean number of customers in the system). For some one-server queueing systems, when the expected number of customers is given, the maximum entropy condition gives the same probability distribution of the possible states of the system as the birth-and-death process applied to an M/M/1 system in a steady-state condition. For other queueing systems, as M/G/1 for instance, the entropic approach gives a simple probability distribution of possible states, while no close expression for such a probability distribution is known in the general framework of a birth-and-death process.     

具有不耐烦顾客和PH分布休假的M/M/1排队系统

研究了具有不耐烦顾客的M/M/1休假排队系统,其中休假时间服从位相分布.当顾客在休假时间到达系统,顾客则会因为等待变得不耐烦.服务员休假结束后立刻开始工作.如果在顾客不耐烦时间段内,系统的休假还没有结束,顾客就会离开系统不再回来.建立的模型为水平相依QBD拟生灭过程,通过利用BrightTaylor算法得到系统的稳态概率解.同时还得到一些重要的性能指标.最后通过数据实例验证了我们的结论.     

On the Two-Class M/M/1 System under Preemptive Resume and Impatience of the Prioritized Customers

The paper deals with the two-class priority M/M/1 system, where the prioritized class-1 customers are served under FCFS preemptive resume discipline and may become impatient during their waiting for service with generally distributed maximal waiting times. The class-2 customers have no impatience. The required mean service times may depend on the class of the customer. As the dynamics of class-1 customers are related to the well analyzed M/M/1+GI system, our aim is to derive characteristics for class-2 customers and for the whole system. The solution of the balance equations for the partial probability generating functions of the detailed system state process is given in terms of the weak solution of a family of boundary value problems for ordinary differential equations, where the latter can be solved explicitly only for particular distributions of the maximal waiting times. By means of this solution formulae for the joint occupancy distribution and for the sojourn and waiting times of class-2 customers are derived generalizing corresponding results recently obtained by Choi et al. in case of deterministic maximal waiting times. The latter case is dealt as an example in our paper.     

Dynamic admission and service rate control of a queue

This paper investigates a queueing system in which the controller can perform admission and service rate control. In particular, we examine a single-server queueing system with Poisson arrivals and exponentially distributed services with adjustable rates. At each decision epoch the controller may adjust the service rate. Also, the controller can reject incoming customers as they arrive. The objective is to minimize long-run average costs which include: a holding cost, which is a non-decreasing function of the number of jobs in the system; a service rate cost c(x), representing the cost per unit time for servicing jobs at rate x; and a rejection cost κ for rejecting a single job. From basic principles, we derive a simple, efficient algorithm for computing the optimal policy. Our algorithm also provides an easily computable bound on the optimality gap at every step. Finally, we demonstrate that, in the class of stationary policies, deterministic stationary policies are optimal for this problem.     

On priority queues with impatient customers

In this paper, we study three different problems where one class of customers is given priority over the other class. In the first problem, a single server receives two classes of customers with general service time requirements and follows a preemptive-resume policy between them. Both classes are impatient and abandon the system if their wait time is longer than their exponentially distributed patience limits. In the second model, the low-priority class is assumed to be patient and the single server chooses the next customer to serve according to a non-preemptive priority policy in favor of the impatient customers. The third problem involves a multi-server system that can be used to analyze a call center offering a call-back option to its impatient customers. Here, customers requesting to be called back are considered to be the low-priority class. We obtain the steady-state performance measures of each class in the first two problems and those of the high-priority class in the third problem by exploiting the level crossing method. We furthermore adapt an algorithm from the literature to obtain the factorial moments of the low-priority queue length of the multi-server system exactly.      

Delay Distribution of (Im)Patient Customers in a Discrete Time D-MAP/PH/1 Queue with Age-Dependent Service Times

This paper presents an algorithmic procedure to calculate the delay distribution of (im)patient customers in a discrete time D-MAP/PH/1 queue, where the service time distribution of a customer depends on his waiting time. We consider three different situations: impatient customers in the waiting room, impatient customers in the system, that is, if a customer has been in the waiting room, respectively, in the system for a time units it leaves the waiting room, respectively, the system. In the third situation, all customers are patient – that is, they only leave the system after completing service. In all three situations the service time of a customer depends upon the time he has spent in the waiting room. As opposed to the general approach in many queueing systems, we calculate the delay distribution, using matrix analytic methods, without obtaining the steady state probabilities of the queue length. The trick used in this paper, which was also applied by Van Houdt and Blondia [J. Appl. Probab., Vol. 39, No. 1 (2002) pp. 213–222], is to keep track of the age of the customer in service, while remembering the D-MAP state immediately after the customer in service arrived. Possible extentions of this method to more general queues and numerical examples that demonstrate the strength of the algorithm are also included.     

Convergence of a queueing system in heavy traffic with general patience-time distributions

We analyze a sequence of single-server queueing systems with impatient customers in heavy traffic. Our state process is the offered waiting time, and the customer arrival process has a state dependent intensity. Service times and customer patient-times are independent; i.i.d. with general distributions subject to mild constraints. We establish the heavy traffic approximation for the scaled offered waiting time process and obtain a diffusion process as the heavy traffic limit. The drift coefficient of this limiting diffusion is influenced by the sequence of patience-time distributions in a non-linear fashion. We also establish an asymptotic relationship between the scaled version of offered waiting time and queue-length. As a consequence, we obtain the heavy traffic limit of the scaled queue-length. We introduce an infinite-horizon discounted cost functional whose running cost depends on the offered waiting time and server idle time processes. Under mild assumptions, we show that the expected value of this cost functional for the n-th system converges to that of the limiting diffusion process as n tends to infinity.     

On the Diophantine Queueing System, <Emphasis Type="Italic">D/D</Emphasis><Superscript><Emphasis Type="Italic">a,b</Emphasis></Superscript><Emphasis Type="Italic">/</Emphasis>1

This paper considers the solution of a deterministic queueing system. In this system, the single server provides service in bulk with a threshold for the acceptance of customers into service. Analytic results are given for the steady-state probabilities of the number of customers in the system and in the queue for random and pre-arrival epochs. The solution of this system is a prerequisite to a four-point approximation to the model GI/G ^a,b /1. The paper demonstrates that the solution of such a system is not a trivial problem and can produce interesting results. The graphical solution discussed in the literature requires that the traffic intensity be a rational number. The results so generated may be misleading in practice when a control policy is imposed, even when the probability distributions for the interarrival and service times are both deterministic.     

An approximation analysis for an assembly-like queueing system with time-constraint items

We study an assembly-like queueing system one of whose queues has items with generally distributed time-constraints, where this system has a single server providing services using each item individually. It is well-known that analysis of a queueing system which has items with time-constraint (i.e., impatient items) is difficult since the analytical model must involve all the departure times of these impatient items. We therefore propose to employ the techniques of Whitt’s approximation and show the method for obtaining the stationary distribution of the model. Through some simulation experiments, we discuss the validation of our approximation model, and show that the approximation is accurate in various kinds of situations (e.g., service time distribution and the number of queues).     

Optimization and sensitivity analysis of controlling arrivals in the queueing system with single working vacation

This paper analyzes the F-policy M/M/1/K queueing system with working vacation and an exponential startup time. The F-policy deals with the issue of controlling arrivals to a queueing system, and the server requires a startup time before allowing customers to enter the system. For the queueing systems with working vacation, the server can still provide service to customers rather than completely stop the service during a vacation period. The matrix-analytic method is applied to develop the steady-state probabilities, and then obtain several system characteristics. We construct the expected cost function and formulate an optimization problem to find the minimum cost. The direct search method and Quasi-Newton method are implemented to determine the optimal system capacity K, the optimal threshold F and the optimal service rates (μ_B,μ_V) at the minimum cost. A sensitivity analysis is conducted to investigate the effect of changes in the system parameters on the expected cost function. Finally, numerical examples are provided for illustration purpose.     

Analysis of a two-phase queueing system with a fixed-size batch policy

We consider a single-server, two-phase queueing system with a fixed-size batch policy. Customers arrive at the system according to a Poisson process and receive batch service in the first-phase followed by individual services in the second-phase. The batch service in the first-phase is applied for a fixed number (k) of customers. If the number of customers waiting for the first-phase service is less than k when the server completes individual services, the system stays idle until the queue length reaches k. We derive the steady state distribution for the system’s queue length. We also show that the stochastic decomposition property can be applied to our model. Finally, we illustrate the process of finding the optimal batch size that minimizes the long-run average cost under a linear cost structure.     

On M/G/1 system under NT policies with breakdowns,startup and closedown

This paper studies the vacation policies of an M/G/1 queueing system with server breakdowns, startup and closedown times, in which the length of the vacation period is controlled either by the number of arrivals during the vacation period, or by a timer. After all the customers are served in the queue exhaustively, the server is shutdown (deactivates) by a closedown time. At the end of the shutdown time, the server immediately takes a vacation and operates two different policies: (i) The server reactivates as soon as the number of arrivals in the queue reaches to a predetermined threshold N or the waiting time of the leading customer reaches T units; and (ii) The server reactivates as soon as the number of arrivals in the queue reaches to a predetermined threshold N or T time units have elapsed since the end of the closedown time. If the timer expires or the number of arrivals exceeds the threshold N, then the server reactivates and requires a startup time before providing the service until the system is empty. If some customers arrive during this closedown time, the service is immediately started without leaving for a vacation and without a startup time. We analyze the system characteristics for each scheme.     

Queues with system disasters and impatient customers when system is down

Consider a system operating as an M/M/c queue, where c=1, 1<c<∞, or c=∞. The system as a whole suffers occasionally a disastrous breakdown, upon which all present customers (waiting and served) are cleared from the system and lost. A repair process then starts immediately. When the system is down, inoperative, and undergoing a repair process, new arrivals become impatient: each individual customer, upon arrival, activates a random-duration timer. If the timer expires before the system is repaired, the customer abandons the queue never to return. We analyze this model and derive various quality of service measures: mean sojourn time of a served customer; proportion of customers served; rate of lost customers due to disasters; and rate of abandonments due to impatience.      

A note on the distributional Little’s law for discrete-time queues with D-MAP arrivals and its application

For a class of discrete-time FIFO queueing systems with D-MAP (discrete-time Markovian arrival process), we present a distributional Little’s law that relates the distribution of the stationary number of customers in system (queue) with that of the stationary number of slots a customer spends in system (queue). Taking the multi-server D-MAP/D/c queue as an example, we demonstrate how this relation can be utilized to get the desired distribution of the number of customers. Sample numerical results are presented at the end.     

Locating and staffing service centers under service level constraints

Many firms experience demand from geographically dispersed customers. This demand is satisfied by mobile servers that travel to the site of the customer. To achieve this in a cost-effective manner, the firm needs to decide where to locate its service centers, which customer regions to assign to the centers and the staffing level   at each center so that customers experience a defined level of service at minimum cost. To determine adequate staffing levels, we approximate a service center and the customer regions assigned to it as an M/G/s$M/G/s$ queueing system. Based on this queueing model, we explore properties of two different staffing level functions. The queueing model is embedded in a large-scale integer program. Using the concept of column generation, we develop an algorithm that can efficiently solve moderate-sized problems.