Analysis of queues in a random environment with impatient customers

We study M/M/c queues (c = 1, 1 < c < ∞ and c = ∞) in a Markovian environment with impatient customers. The arrivals and service rates are modulated by the underlying continuous-time Markov chain. When the external environment operates in phase 2, customers become impatient. We focus our attention on the explicit expressions of the performance measures. For each case of c, the corresponding probability generating function and mean queue size are obtained. Several special cases are studied and numerical experiments are presented.     

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.      

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.     

On first-come,first-served queues with two classes of impatient customers

Queueing Systems - We study systems with two classes of impatient customers who differ across the classes in their distribution of service times and patience times. The customers are served on a...     

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%.     

Profit maximization in a multi-product firm with impatient customers

In this paper, the standard model of profit maximization is extended to include multi-product production in a market characterized by impatient customers. A formal model is presented that includes price, delivery frequency, production run length per set-up and product range as endogenous variables. The model facilitates the analysis of the complex interactions between these variables and highlights the inherent problems relating to profit maximization. For example, offering a broader range of products and/or more rapid delivery may seem to be a sensible response for a multi-product firm with impatient customers in a scenario of depressed demand. However, the analysis shows that such strategies could be counterproductive.     

Optimal buffer size and dynamic rate control for a queueing system with impatient customers in heavy traffic

We address a rate control problem associated with a single server Markovian queueing system with customer abandonment in heavy traffic. The controller can choose a buffer size for the queueing system and also can dynamically control the service rate (equivalently the arrival rate) depending on the current state of the system. An infinite horizon cost minimization problem is considered here. The cost function includes a penalty for each rejected customer, a control cost related to the adjustment of the service rate and a penalty for each abandoning customer. We obtain an explicit optimal strategy for the limiting diffusion control problem (the Brownian control problem or BCP) which consists of a threshold-type optimal rejection process and a feedback-type optimal drift control. This solution is then used to construct an asymptotically optimal control policy, i.e. an optimal buffer size and an optimal service rate for the queueing system in heavy traffic. The properties of generalized regulator maps and weak convergence techniques are employed to prove the asymptotic optimality of this policy. In addition, we identify the parameter regimes where the infinite buffer size is optimal.     

Analysis of $$\hbox {M}^{\mathrm {x}}/\hbox {G}/1$$ queues with impatient customers

This paper considers a batch arrival \(\hbox {M}^{\mathrm {x}}/\hbox {G}/1\) queue with impatient customers. We consider two different model variants. In the first variant, customers in the same batch are assumed to have the same patience time, and patience times associated with batches are i.i.d. according to a general distribution. In the second variant, patience times of customers in the same batch are independent, and they follow a general distribution. Both variants are related to an M/G/1 queue in which the service time of a customer depends on its waiting time. Our main focus is on the virtual and actual waiting times, and on the loss probability of customers.     

Analysis of customers’ impatience in queues with server vacations

Many models for customers impatience in queueing systems have been studied in the past; the source of impatience has always been taken to be either a long wait already experienced at a queue, or a long wait anticipated by a customer upon arrival. In this paper we consider systems with servers vacations where customers’ impatience is due to an absentee of servers upon arrival. Such a model, representing frequent behavior by waiting customers in service systems, has never been treated before in the literature. We present a comprehensive analysis of the single-server, M/M/1 and M/G/1 queues, as well as of the multi-server M/M/c queue, for both the multiple and the single-vacation cases, and obtain various closed-form results. In particular, we show that the proportion of customer abandonments under the single-vacation regime is smaller than that under the multiple-vacation discipline. This work was supported by the Euro-Ngi network of excellence.     

Approximate sojourn time distribution of a discriminatory processor sharing queue with impatient customers

We consider a two-class processor sharing queueing system scheduled by the discriminatory processor sharing discipline. Poisson arrivals of customers and exponential amounts of service requirements are assumed. At any moment of being served, a customer can leave the system without completion of its service. In the asymptotic regime, where the ratio of the time scales of the two-class customers is infinite, we obtain the conditional sojourn time distribution of each class customers. Numerical experiments show that the time scale decomposition approach developed in this paper gives a good approximation to the conditional sojourn time distribution as well as the expectation of it.     

Periodic routing to parallel queues and billiard sequences

In this companion paper of [10] we introduce the combinatorial notion of unbalance for a routing pattern. Using this unbalance we derive an upper bound for the total average expected waiting time of jobs which are routed to parallel queues according to a periodic routing rule. A billiard sequence is obtained with unbalance smaller than or equal to –1, where N is the number of different symbols in the sequence which corresponds to the number of parallel queues in the routing problem.     

Computational algorithm and parameter optimization for a multi-server system with unreliable servers and impatient customers

We consider an infinite capacity M/M/c queueing system with c unreliable servers, in which the customers may balk (do not enter) and renege (leave the queue after entering). The system is analyzed as a quasi-birth-and-death (QBD) process and the necessary and sufficient condition of system equilibrium is obtained. System performance measures are explicitly derived in terms of computable forms. The useful formulae for computing the rate matrix and stationary probabilities are derived by means of a matrix analytical approach. A cost model is derived to determine the optimal values of the number of servers, service rate and repair rate simultaneously at the minimal total expected cost per unit time. The parameter optimization is illustrated numerically by the Quasi-Newton method.     

Analysis of two queues in parallel with jockeying and restricted capacities

In this paper, we present two parallel queues with jockeying and restricted capacities. Each exponential server has its own queue, and jockeying among the queues is permitted. The capacity of each queue is restricted to L   including the one being served. Customers arrive according to a Poisson process and on arrival; they join the shortest feasible queue. Moreover, if one queue is empty and in the other queue, more than one customer is waiting, then the customer who has to receive after the customer being served in that queue is transferred to the empty queue. This will prevent one server from being idle while the customers are waiting in the other queue. Using the matrix-analytical technique, we derive formulas in matrix form for the steady-state probabilities and formulas for other performance measures. Finally, we compare our new model with some of Markovian queueing systems such as Conolly’s model [B.W. Conolly, The autostrada queueing problems, J. Appl. Prob. 21 (1984) 394–403], M/M/2$M/M/2$ queue and two of independent M/M/1$M/M/1$ queues for the steady state solution.     

Optimal assignment policy of a single server attended by two queues

A single server attends to two separate queues. Each queue has Poisson arrivals and exponential service. There is a switching cost whenever the server switches from one queue to another. The objective is to minimize the discounted or average holding and switching costs over a finite or an infinite horizon. We show numerically that the optimal assignment policy is characterized by a switching curve. We also show that the optimal policy is monotonic in the following senses: If it is optimal to switch from queue one to queue two, then it is optimal to continue serve queue two whenever the number of customers in queue one or in queue two decreases or increases, respectively.     

Optimal control for parallel queues with a single batch server

We consider a queueing system with multiple Poisson arrival queues and a single batch server that has infinite capacity and a fixed service time. The problem is to allocate the server at each moment to minimize the long-run average waiting cost. We propose a Cost-Arrival Weighted (CAW) policy for this problem based on the structure of the optimal policy of a corresponding fluid model. We show that this simple policy enjoys a superior performance by numerical experiments.     

Stochastic scheduling of parallel queues with set-up costs

We consider the problem of allocating a single server to a system of queues with Poisson arrivals. Each queue represents a class of jobs and possesses a holding cost rate, general service distribution, and a set-up cost. The objective is to minimize the expected cost due to the waiting of jobs and the switching of the server. A set-up cost is required to effect an instantaneous switch from one queue to another. We partially characterize an optimal policy and provide a simple heuristic scheduling policy. The heuristic's performance is evaluated in the cases of two and three queues by comparison with a numerically obtained optimal policy. Simulation results are provided to demonstrate the effectiveness of our heuristic over a wide range of problem instances with four queues.     

Waiting time based routing policies to parallel queues with percentiles objectives

We develop a method to obtain near-optimal routing policies to parallel queues with decisions based on customers’ wait and performance objectives which include percentiles of the waiting time. We formulate and explicitly derive a value function where the waiting time is used as a decision variable. This allows us to apply a one-step policy improvement method to obtain an efficient routing solution. Numerical illustrations reveal that classical monotone policies are not always optimal.     

On computing average cost optimal policies with application to routing to parallel queues

The Approximating Sequence Method for computation of average cost optimal stationary policies in denumerahle state Markov decision chains, introduced in Sennott (1994), is reviewed. New methods for verifying the assumptions are given. These are useful for models with multidimensional state spaces that satisfy certain mild structural properties. The results are applied to four problems in the optimal routing of packets to parallel queues. Numerical results are given for one of the models.