On equilibrium threshold strategies when choosing between observable and unobservable queues

We consider threshold equilibrium strategies in a two-server memoryless queueing system where customers inspect one queue before deciding which queue to join. We show that such an equilibrium may not exist. A numerical study indicates that if threshold equilibria exist, the effective arrival rate to the unobserved queue is higher when the regime there is last-come first-served rather than first-come first-served.     

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

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.     

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.     

On the regulation of queues

It is proved that the variance of the delay in a queueing system as well as the expectation of any convex increasing function of the delay attain their minima when customers leave the system according to a FIFO departure discipline. The relationship to a corresponding property of the FCFS service discipline with respect to the waiting time in the queue before service, is examined and some interesting differences are pointed out.     

On bounds for bulk arrival queues

This paper gives a simple and effective approach pf deriving bounds for bulk arrival queues by making use of the bounds for single arrival queues. With this approach, upper bounds of mean actual/virtual waiting times and mean queue length at random epochs can be derived for the bulk arrival queues GI^X/G/1 and GI^X/G/c (lower bounds can be derived in a similar way). The merit of this approach is shown by comparing the bounds obtained with some existing results in the literature.     

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.      

On the order of tandem queues

We consider the optimal order of servers in a tandem queueing system withm stages, an unlimited supply of customers in front of the first stage, and a service buffer of size 1 but no intermediate storage buffers between the first and second stages. Service times depend on the servers but not the customers, and the blocking mechanism at the first two stages is manufacturing blocking. Using a new characterization of reversed hazard rate order, we show that if the service times for two servers are comparable in the reversed hazard rate sense, then the departure process is stochastically earlier if the slower server is first and the faster server is second than if the reverse is true. This strengthens earlier results that considered individual departure times marginally. We show similar results for the last two stages and for other blocking mechanisms. We also show that although individual departure times for a system with servers in a given order are stochastically identical to those when the order of servers is reversed, this reversibility property does not hold for the entire departure process.     

On pathwise behavior of multiserver queues

In this paper, by exploiting recent results on the pathwise behavior of the workload process in single server, work conserving queues of theG/G/1/ type, we show that the workload of multiserver, work conserving queues ofG/G/m/ (m<) (andG/G/) queues satisfies an o(t) growth condition, provided that the time average of the work brought into the system is less thanm form < (and finite form=).     

On the stability of retrial queues

We consider the following Type of problems. Calls arrive at a queue of capacity K (which is called the primary queue), and attempt to get served by a single server. If upon arrival, the queue is full and the server is busy, the new arriving call moves into an infinite capacity orbit, from which it makes new attempts to reach the primary queue, until it finds it non-full (or it finds the server idle). If the queue is not full upon arrival, then the call (customer) waits in line, and will be served according to the FIFO order. If λ is the arrival rate (average number per time unit) of calls and μ is one over the expected service time in the facility, it is well known that μ > λ is not always sufficient for stability. The aim of this paper is to provide general conditions under which it is a sufficient condition. In particular, (i) we derive conditions for Harris ergodicity and obtain bounds for the rate of convergence to the steady state and large deviations results, in the case that the inter-arrival times, retrial times and service times are independent i.i.d. sequences and the retrial times are exponentially distributed; (ii) we establish conditions for strong coupling convergence to a stationary regime when either service times are general stationary ergodic (no independence assumption), and inter-arrival and retrial times are i.i.d. exponentially distributed; or when inter-arrival times are general stationary ergodic, and service and retrial times are i.i.d. exponentially distributed; (iii) we obtain conditions for the existence of uniform exponential bounds of the queue length process under some rather broad conditions on the retrial process. We finally present conditions for boundedness in distribution for the case of nonpatient (or non persistent) customers. This revised version was published online in June 2006 with corrections to the Cover Date.     

On multiple priority multi-server queues with impatience

We consider Markovian multi-server queues with two types of impatient customers: high- and low-priority ones. The first type of customer has a non-preemptive priority over the other type. After entering the queue, a customer will wait a random length of time for service to begin. If service has not begun by this time he or she will abandon and be lost. We consider two cases where the discipline of service within each customer type is first-come first-served (FCFS) or last-come first-served (LCFS). For each type of customer, we focus on various performance measures related to queueing delays: unconditional waiting times, and conditional waiting times given service and given abandonment. The analysis we develop holds also for a priority queue with mixed policies, that is, FCFS for the first type and LCFS for the second one, and vice versa. We explicitly derive the Laplace–Stieltjes transforms of the defined random variables. In addition we show how to extend the analysis to more than two customer types. Finally we compare FCFS and LCFS and gain insights through numerical experiments.     

On spectral properties of finite population processor shared queues

We consider sojourn or response times in processor-shared queues that have a finite population of potential users. Computing the response time of a tagged customer involves solving a finite system of linear ODEs. Writing the system in matrix form, we study the eigenvectors and eigenvalues in the limit as the size of the matrix becomes large. This corresponds to finite population models where the total population is $N\gg 1$ . Using asymptotic methods we reduce the eigenvalue problem to that of a standard differential equation, such as the Hermite equation. The dominant eigenvalue leads to the tail of a customer’s sojourn time distribution.     

Order restoration in queues

We examine a class of problems in queueing networks which arise when customers enter a bank of parallel servers in a given order and lose their place in the sequence due to passing resulting from variations in service times. The original sequence is required before service can take place at the next station in the network. These problems arise naturally in flexible manufacturing systems. The result is that the next station beyond the parallel bank of servers can be approximated by a non-Markovian bulk arrival system. This station sees batch arrivals of customers that are eligible to receive service. The size of the arriving batches is shown to depend on the inter-arrival times. Several fundamental results are established for this class of problems including the distribution of batch inter-arrival times, batch sizes, and an approximate method for determining the distribution of the number of eligible and an exact method for determining the distribution of the number of ineligible customers in the system.     

Two queues in tandem

A system consisting of two queues in series, the output of one queue being the input of the other, is described. General distributions are discussed, but the exponential distribution is given particular consideration.     

On finite capacity queues with time dependent arrival rates

We consider the finite capacity M/M/1−K$M/M/1-K$ queue with a time dependent arrival rate λ(t)$\lambda \left(t\right)$. Assuming that the capacity K$K$ is large and that the arrival rate varies slowly with time (as t/K$t/K$), we construct asymptotic approximations to the probability of finding n$n$ customers in the system at time t$t$, as well as the mean number. We consider various time ranges, where the system is nearly empty, nearly full, or is filled to a fraction of its capacity. Extensive numerical studies are used to back up the asymptotic analysis.     

On the time-dependent moments of Markovian queues with reneging

We give an explicit representation for the time-dependent moments of a Markovian queueing system with reneging. Our expressions are comparable in form to the moment expressions for the M/M/1 queue found in Abate and Whitt (Queueing Syst. 2:41–65, 1987; Adv. Appl. Probab. 20:145–178, 1988). We also illustrate how to use these expressions to derive analogous moment expressions for a reflected Ornstein–Uhlenbeck process, with reflection at zero.     

Equilibrium threshold strategies in observable queueing systems under single vacation policy

This paper studies the equilibrium behavior of customers in continuous/discrete time queueing systems under single vacation policy. In the single vacation queueing system, the server can only take exactly one vacation when no customers exist in the system. This scheme is more practical under many specific circumstances. Based on the reward–cost structure, equilibrium behavior is considered in the fully observable and almost observable cases. The threshold strategies in equilibrium are obtained and the stationary system behavior is analyzed under the corresponding strategies. Finally, we illustrate the effect of the information level as well as several parameters on the equilibrium thresholds and social benefits via numerical experiments. The research results could instruct the customers to take optimal strategies and provide the managers with reference information on the pricing problem in the queueing system.     

On single-server closed queues with priorities and state dependent parameters

A wide class of closed single-channel queues is considered. The more general model involvesm +w + 1 “permanent” customers that occasionally require service. Them customers are of the first priority and the rest are of the second priority. The input rate and service of customers depend upon the total number of customers waiting for service. Such a system can also be described in terms of servicing machines processes with reserve replacement and multi-channel queues with finite waiting room. Two dual models, with and without idle periods, are treated. An explicit relation between the servicing processes of both models is derived. The semi-regenerative techniques originally developed in the author's earlier work [4] are extended and used to derive the probability distribution of the processes in equilibrium. Applications and examples are discussed. This paper is a part of work supported by the National Science Foundation under Grant No. DMS-8706186.