Customers’ abandonment strategy in an <Emphasis Type="Italic">M</Emphasis> / <Emphasis Type="Italic">G</Emphasis> / 1 queue

We consider an M / G / 1 queue in which the customers, while waiting in line, may renege from it. We show the Nash equilibrium profile among customers and show that it is defined by two sequences of thresholds. For each customer, the decision is based on the observed past (which determines from what sequence the threshold is taken) and the observed queue length (which determines the appropriate element in the chosen sequence). We construct a set of equations that has the Nash equilibrium as its solution and discuss the relationships between the properties of the service time distribution and the properties of the Nash equilibrium, such as uniqueness and finiteness.     

Optimal balking strategies and pricing for the single server Markovian queue with compartmented waiting space

We consider the single server Markovian queue and we assume that arriving customers decide whether to enter the system or balk based on a natural reward-cost structure, which incorporates their desire for service as well as their unwillingness to wait. We suppose that the waiting space of the system is partitioned in compartments of fixed capacity for a customers. Before making his decision, a customer may or may not know the compartment in which he will enter and/or the position within the compartment in which he will enter. Thus, denoting by n the number of customers found by an arriving customer, he may or may not know ? n/a ?+1 and/or (n mod a)+1. We examine customers’ behavior under the various levels of information regarding the system state and we identify equilibrium threshold strategies. We also study the corresponding social and profit maximization problems.     

Strategic behavior in queues with the effect of the number of customers behind

In this paper, we investigate the strategic behavior in queues by considering the effect of the number of customers behind. The equilibrium joining strategy of customers is obtained and its implications for the service system are examined. We find that the complete queue transparency (i.e., disclosing the real-time system information) can have positive effect on customers, which might encourage more customers to join. Further, the follow-the-crowd (FTC) behavior can be observed, which results in multiple equilibria. By comparing the customer welfare under two different information levels, we demonstrate that, somewhat surprisingly, the queue transparency does not necessarily hurt the customer welfare, and a higher customer welfare can be obtained in the transparent case than that in opaque case when the demand volume is large.     

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.     

Equilibrium customer strategies in a single server Markovian queue with setup times

We consider a single server Markovian queue with setup times. Whenever this system becomes empty, the server is turned off. Whenever a customer arrives to an empty system, the server begins an exponential setup time to start service again. We assume that arriving customers decide whether to enter the system or balk based on a natural reward-cost structure, which incorporates their desire for service as well as their unwillingness to wait. We examine customer behavior under various levels of information regarding the system state. Specifically, before making the decision, a customer may or may not know the state of the server and/or the number of present customers. We derive equilibrium strategies for the customers under the various levels of information and analyze the stationary behavior of the system under these strategies. We also illustrate further effects of the information level on the equilibrium behavior via numerical experiments.      

Approximation of M/M/s/K retrial queue with nonpersistent customers

We consider the M/M/s/K retrial queues in which a customer who is blocked to enter the service facility may leave the system with a probability that depends on the number of attempts of the customer to enter the service facility. Approximation formulae for the distributions of the number of customers in service facility, waiting time in the system and the number of retrials made by a customer during its waiting time are derived. Approximation results are compared with the simulation.     

Tandem Queues with Impatient Customers for Blood Screening Procedures

We study a blood testing procedure for detecting viruses like HIV, HBV and HCV. In this procedure, blood samples go through two screening steps. The first test is ELISA (antibody Enzyme Linked Immuno-Sorbent Assay). The portions of blood which are found not contaminated in this first phase are tested in groups through PCR (Polymerase Chain Reaction). The ELISA test is less sensitive than the PCR test and the PCR tests are considerably more expensive. We model the two test phases of blood samples as services in two queues in series; service in the second queue is in batches, as PCR tests are done in groups. The fact that blood can only be used for transfusions until a certain expiration date leads, in the tandem queue, to the feature of customer impatience. Since the first queue basically is an infinite server queue, we mainly focus on the second queue, which in its most general form is an S-server M/G ^[k,?K]/S?+?G queue, with batches of sizes which are bounded by k and K. Our objective is to maximize the expected profit of the system, which is composed of the amount earned for items which pass the test (and before their patience runs out), minus costs. This is done by an appropriate choice of the decision variables, namely, the batch sizes and the number of servers at the second service station. As will be seen, even the simplest version of the batch queue, the M/M ^[k,?K]/1?+?M queue, already gives rise to serious analytical complications for any batch size larger than 1. These complications are discussed in detail, and handled for K?=?2. In view of the fact that we aim to solve realistic optimization problems for blood screening procedures, these analytical complications force us to take recourse to either a numerical approach or approximations. We present a numerical solution for the queue length distribution in the M/M ^[k,?K]/S?+?M queue and then formulate and solve several optimization problems. The power-series algorithm, which is a numerical-analytic method, is also discussed.     

A batch arrival retrial queue with two phases of service and Bernoulli vacation schedule

We consider an M X /G/1 queueing system with two phases of heterogeneous service and Bernoulli vacation schedule which operate under a linear retrial policy. In addition, each individual customer is subject to a control admission policy upon the arrival. This model generalizes both the classical M/G/1 retrial queue with arrivals in batches and a two phase batch arrival queue with a single vacation under Bernoulli vacation schedule. We will carry out an extensive stationary analysis of the system , including existence of the stationary regime, embedded Markov chain, steady state distribution of the server state and number of customer in the retrial group, stochastic decomposition and calculation of the first moment.     

Sojourn times in a processor sharing queue with multiple vacations

We study an M/G/1 processor sharing queue with multiple vacations. The server only takes a vacation when the system has become empty. If he finds the system still empty upon return, he takes another vacation, and so on. Successive vacations are identically distributed, with a general distribution. When the service requirements are exponentially distributed we determine the sojourn time distribution of an arbitrary customer. We also show how the same approach can be used to determine the sojourn time distribution in an M/M/1-PS queue of a polling model, under the following constraints: the service discipline at that queue is exhaustive service, the service discipline at each of the other queues satisfies a so-called branching property, and the arrival processes at the various queues are independent Poisson processes. For a general service requirement distribution we investigate both the vacation queue and the polling model, restricting ourselves to the mean sojourn time.     

Some results for the queues Mx/M/c and GIx/ G/c

We develop for the queue M^x/M/c an upper bound for the mean queue length and lower bounds for the delay probabilities (that of an arrival group and that of an arbitrary customer in the arrival group). An approximate formula is also developed for the general bulk-arrival queue GI^x/G/c. Preliminary numerical studies have indicated excellent performance of the results.     

Comparisons between observable and unobservable M/M/1 queues with respect to optimal customer behavior

We consider an M/M/1 queueing system in which the queue length may or may not be observable by a customer upon entering the system. The “observable” and “unobservable” models are compared with respect to system properties and performance measures under two different types of optimal customer behavior, which we refer to as “selfishly optimal” and “socially optimal”. We consider average customer throughput rates and show that, under both types of optimal customer behavior, the equality of effective queue-joining rates between the observable and unobservable systems results in differences with respect to other performance measures such as mean busy periods and waiting times. We also show that the equality of selfishly optimal queue-joining rates between the two types of system precludes the equality of socially optimal joining rates, and vice versa.     

Analysis of the M/M/1 Queue with Processor Sharing via Spectral Theory

We show in this paper that the computation of the distribution of the sojourn time of an arbitrary customer in a M/M/1 with the processor sharing discipline (abbreviated to M/M/1 PS queue) can be formulated as a spectral problem for a self-adjoint operator. This approach allows us to improve the existing results for this queue in two directions. First, the orthogonal structure underlying the M/M/1 PS queue is revealed. Second, an integral representation of the distribution of the sojourn time of a customer entering the system while there are n customers in service is obtained.     

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.     

On a processor sharing queue that models balking

We consider the processor sharing M/M/1-PS queue which also models balking. A customer that arrives and sees n others in the system “balks” (i.e., decides not to enter) with probability 1−b _n . If b _n is inversely proportional to n + 1, we obtain explicit expressions for a tagged customer’s sojourn time distribution. We consider both the conditional distribution, conditioned on the number of other customers present when the tagged customer arrives, as well as the unconditional distribution. We then evaluate the results in various asymptotic limits. These include large time (tail behavior) and/or large n, lightly loaded systems where the arrival rate λ → 0, and heavily loaded systems where λ → ∞. We find that the asymptotic structure for the problem with balking is much different from the standard M/M/1-PS queue. We also discuss a perturbation method for deriving the asymptotics, which should apply to more general balking functions.     

Equilibrium and optimal strategies to join a queue with partial information on service times

In this paper, we study customer equilibrium as well as socially optimal strategies to join a queue with only partial information on the service time distribution such as moments and the range. Based on such partial information, customers adopt the entropy-maximization principle to obtain the expectation of their waiting cost and decide to join or balk. We find that more information encourages customers to join the queue. And it is beneficial for decision makers to convey partial information to customers in welfare maximization but reveal full information in profit maximization.     

TheM/G/1 queue with processor sharing and its relation to a feedback queue

The central model of this paper is anM/M/1 queue with a general probabilistic feedback mechanism. When a customer completes his ith service, he departs from the system with probability 1–p(i) and he cycles back with probabilityp(i). The mean service time of each customer is the same for each cycle. We determine the joint distribution of the successive sojourn times of a tagged customer at his loops through the system. Subsequently we let the mean service time at each loop shrink to zero and the feedback probabilities approach one in such a way that the mean total required service time remains constant. The behaviour of the feedback queue then approaches that of anM/G/1 processor sharing queue, different choices of the feedback probabilities leading to different service time distributions in the processor sharing model. This is exploited to analyse the sojourn time distribution in theM/G/1 queue with processor sharing.Some variants are also considered, viz., anM/M/1 feedback queue with additional customers who are always present, and anM/G/1 processor sharing queue with feedback.     

<Emphasis Type="Italic">M</Emphasis><Superscript><Emphasis Type="Italic">X</Emphasis></Superscript>/<Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">c</Emphasis> Queue with catastrophes and state-dependent control at idle time

We consider an M ^X /M/c queue with catastrophes and state-dependent control at idle time. Properties of the queues which terminate when the servers become idle are first studied. Recurrence, equilibrium distribution, and equilibrium queue-size structure are studied for the case of resurrection and no catastrophes. All of these properties and the first effective catastrophe occurrence time are then investigated for the case of resurrection and catastrophes. In particular, we obtain the Laplace transform of the transition probability for the absorbing M ^X /M/c queue.     

The Maximum Queue Length for Heavy-Tailed Service Times in the M/G/1 FB Queue

This paper treats the maximum queue length M, in terms of the number of customers present, in a busy cycle in the M/G/1 queue. The distribution of M depends both on the service time distribution and on the service discipline. Assume that the service times have a logconvex density and the discipline is Foreground Background (FB). The FB service discipline gives service to the customer(s) that have received the least amount of service so far. It is shown that under these assumptions the tail of M is bounded by an exponential tail. This bound is used to calculate the time to overflow of a buffer, both in stable and unstable queues.     

A G/M/1 retrial queue with constant retrial rate

In this paper, we are concerned with the analytical treatment of an GI/M/1 retrial queue with constant retrial rate. Constant retrial rate is typical for some real world systems where the intensity of individual retrials is inversely proportional to the number of customers in the orbit or only one customer from the orbit is allowed to make the retrials. In our model, a customer who finds the server busy joins the queue in the orbit in accordance with the FCFS (first-come-first-out) discipline and only the oldest customer in the queue is allowed to make the repeated attempts to reach the server. A distinguishing feature of the considered system is an arbitrary distribution of inter-arrival times, while the overwhelming majority of the papers is devoted to the retrial systems with the stationary Poisson arrival process. We carry out an extensive analytical analysis of the queue in steady state using the well-known matrix analytic technique. The ergodicity condition and simple expressions for the stationary distributions of the system states at pre-arrival, post-arrival and arbitrary times are derived. The important and difficult problem of finding the stationary distribution of the sojourn time is solved in terms of the Laplace–Stieltjes transform. Little’s formula is proved. Numerical illustrations are presented.     

Heavy-traffic extreme value limits for Erlang delay models

We consider the maximum queue length and the maximum number of idle servers in the classical Erlang delay model and the generalization allowing customer abandonment—the M/M/n+M queue. We use strong approximations to show, under regularity conditions, that properly scaled versions of the maximum queue length and maximum number of idle servers over subintervals [0,t] in the delay models converge jointly to independent random variables with the Gumbel extreme value distribution in the quality-and-efficiency-driven (QED) and ED many-server heavy-traffic limiting regimes as n and t increase to infinity together appropriately; we require that t _n →∞ and t _n =o(n ^1/2?ε ) as n→∞ for some ε>0.