Inventory with service time and transfer of customers and/inventory

An inventory system with two parallel service facilities is considered. A certain number of customers are transferred from longer to shorter queue whenever their difference reaches a prescribed quantity. Along with this customer transfer, a certain quantity of inventory is also transferred, depending on availability. Further, if one of the queues has customers, but has no inventoried items whereas the other has at least one inventoried item to spare, then exactly one item is taken to the former and service begins thereby enhancing the efficiency of the system. Stability of the system is analysed. Several performance measures that helps in efficient design of such systems, are computed. Some numerical results are provided.     

Tail asymptotics for service systems with transfers of customers in an alternating environment

This study examines service systems with transfers of customers in an alternating environment. We model the service system as a two-server two-parallel queue (primary and auxiliary queues), that has various applications especially in manufacturing and healthcare systems. We establish a sufficient stability condition, and based on the censoring technique, we provide sufficient conditions under which the stationary distribution possesses an exactly geometric tail along the direction of the queue length in the primary queue.     

The effects of the availability of waiting-time information on a balking queue

We consider two balking queue models with different types of information about delays. Potential customers arrive according to a Poisson process, and they decide whether to stay or balk based on the available delay information. In the first model, an arriving customer learns a rough range of the current queue length. In the second model, each customer’s service time is the sum of a geometric number of i.i.d. exponential phases, and an arriving customer learns the total number of phases remaining in the system. For each information model, we compare two systems, identical except that one has more precise information. In many cases, better information increases throughput and thus benefits the service provider. But this is not always so. The effect depends on the shape of the distribution describing customers’ sensitivities to delays. We also study the effects of information on performance as seen by customers. Again, more information is often good for customers, but not always.     

A consistent diffusion approximation for finite-capacity multiserver queues

A diffusion approximation is developed for general multiserver queues with finite waiting spaces, which are typical models of manufacturing systems as well as computer and communication systems. The model is the standard GI/G/s/s + r queue with s identical servers in parallel, r extra waiting spaces, and the first-come, first-served discipline. The main focus is on the steady-state distribution of the number of customers in the system. The process of the number of customers is approximated by a time-homogeneous diffusion process on a closed interval in the nonnegative real line. A conservation law plus some heuristics standing on solid theoretical ground generate approximation formulas for the steady-state distribution and other congestion measures. These formulas are consistent with the exact results for the M/G/s/s and M/M/s/s + r queues. The accuracy of approximations for principal congestion measures are numerically examined for some particular cases.     

G-networks with multiple classes of signals and positive customers

G-networks are queueing models in which the types of customers one usually deals with in queues are enriched in several ways. In Gnetworks, positive customers are those that are ordinarily found in queueing systems; they queue up and wait for service, obtain service and then leave or go to some other queue. Negative customers have the specific function of destroying ordinary or positive customers. Finally triggers simply move an ordinary customer from one queue to the other. The term “signal” is used to cover negative customers and triggers. G-networks contain these three type of entities with certain restrictions; positive customers can move from one queue to another, and they can change into negative customers or into triggers when they leave a queue. On the other hand, signals (i.e. negative customers and triggers) do not queue up for service and simply disappear after having joined a queue and having destroyed or moved a negative customer. This paper considers this class of networks with multiple classes of positive customers and of signals. We show that with appropriate assumptions on service times, service disciplines, and triggering or destruction rules on the part of signals, these networks have a product form solution, extending earlier results.     

Dynamic load balancing in parallel queueing systems: Stability and optimal control

We consider a system of parallel queues with dedicated arrival streams. At each decision epoch a decision-maker can move customers from one queue to another. The cost for moving customers consists of a fixed cost and a linear, variable cost dependent on the number of customers moved. There are also linear holding costs that may depend on the queue in which customers are stored. Under very mild assumptions, we develop stability (and instability) conditions for this system via a fluid model. Under the assumption of stability, we consider minimizing the long-run average cost. In the case of two-servers the optimal control policy is shown to prefer to store customers in the lowest cost queue. When the inter-arrival and service times are assumed to be exponential, we use a Markov decision process formulation to show that for a fixed number of customers in the system, there exists a level S such that whenever customers are moved from the high cost queue to the low cost queue, the number of customers moved brings the number of customers in the low cost queue to S. These results lead to the development of a heuristic for the model with more than two servers.     

Strategic behavior and social optimization in Markovian vacation queues: The case of heterogeneous customers

We consider a single server queueing system in which service shuts down when no customers are present, and is resumed when the queue length reaches a given critical length. We assume customers are heterogeneous on delay sensitivity and analyze customers’ strategic response to this mechanism and compare it to the overall optimal behavior. We provide algorithms to compute the equilibrium arrival rates and also derive the monotonicity of equilibrium and optimal arrival rates. We show that there may exist multiple equilibria in such a system and the optimal arrival rate may be larger or smaller than the decentralized equilibrium one.     

Stochastic bounds for a polling system

In this note we consider two queueing systems: a symmetric polling system with gated service at allN queues and with switchover times, and a single-server single-queue model with one arrival stream of ordinary customers andN additional permanently present customers. It is assumed that the combined arrival process at the queues of the polling system coincides with the arrival process of the ordinary customers in the single-queue model, and that the service time and switchover time distributions of the polling model coincide with the service time distributions of the ordinary and permanent customers, respectively, in the single-queue model. A complete equivalence between both models is accomplished by the following queue insertion of arriving customers. In the single-queue model, an arriving ordinary customer occupies with probabilityp _i a position at the end of the queue section behind theith permanent customer,i = l, ...,N. In the cyclic polling model, an arriving customer with probabilityp _i joins the end of theith queue to be visited by the server, measured from its present position.For the single-queue model we prove that, if two queue insertion distributions {p _{i, i} = l, ...,N} and {q _{i, i} = l, ...,N} are stochastically ordered, then also the workload and queue length distributions in the corresponding two single-queue versions are stochastically ordered. This immediately leads to equivalent stochastic orderings in polling models.Finally, the single-queue model with Poisson arrivals andp ₁ = 1 is studied in detail.Part of the research of the first author has been supported by the Esprit BRA project QMIPS.     

Waiting time analysis of the multiple priority dual queue with a preemptive priority service discipline

The dual queue consists of two queues, called the primary queue and the secondary queue. There is a single server in the primary queue but the secondary queue has no service facility and only serves as a holding queue for the overloaded primary queue. The dual queue has the additional feature of a priority scheme to help reduce congestion. Two classes of customers, class 1 and 2, arrive to the dual queue as two independent Poisson processes and the single server in the primary queue dispenses an exponentially distributed service time at the rate which is dependent on the customer’s class. The service discipline is preemptive priority with priority given to class 1 over class 2 customers. In this paper, we use matrix-analytic method to construct the infinitesimal generator of the system and also to provide a detailed analysis of the expected waiting time of each class of customers in both queues.     

Waiting times in queueing networks with a single shared server

We study a queueing network with a single shared server that serves the queues in a cyclic order. External customers arrive at the queues according to independent Poisson processes. After completing service, a customer either leaves the system or is routed to another queue. This model is very generic and finds many applications in computer systems, communication networks, manufacturing systems, and robotics. Special cases of the introduced network include well-known polling models, tandem queues, systems with a waiting room, multi-stage models with parallel queues, and many others. A complicating factor of this model is that the internally rerouted customers do not arrive at the various queues according to a Poisson process, causing standard techniques to find waiting-time distributions to fail. In this paper, we develop a new method to obtain exact expressions for the Laplace–Stieltjes transforms of the steady-state waiting-time distributions. This method can be applied to a wide variety of models which lacked an analysis of the waiting-time distribution until now.     

Interacting queues in heavy traffic

We consider a system of parallel queues with Poisson arrivals and exponentially distributed service requirements. The various queues are coupled through their service rates, causing a complex dynamic interaction. Specifically, the system consists of one primary queue and several secondary queues whose service rates depend on whether the primary queue is empty or not. Conversely, the service rate of the primary queue depends on which of the secondary queues are empty.     

Ergodicity of the BMAP/PH/s/s+K retrial queue with PH-retrial times

Define the traffic intensity as the ratio of the arrival rate to the service rate. This paper shows that the BMAP/PH/s/s+K retrial queue with PH-retrial times is ergodic if and only if its traffic intensity is less than one. The result implies that the BMAP/PH/s/s+K retrial queue with PH-retrial times and the corresponding BMAP/PH/s queue have the same condition for ergodicity, a fact which has been believed for a long time without rigorous proof. This paper also shows that the same condition is necessary and sufficient for two modified retrial queueing systems to be ergodic. In addition, conditions for ergodicity of two BMAP/PH/s/s+K retrial queues with PH-retrial times and impatient customers are obtained. This revised version was published online in June 2006 with corrections to the Cover Date.     

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.     

A Law of the Iterated Logarithm for Extreme Queue Length in Multiphase Queues

The object of this research in queueing theory is the Law of the Iterated Logarithm (LIL) under the conditions of heavy traffic in Multiphase Queueing Systems (MQS). In this paper, the LIL is proved for extreme values of important probabilistic characteristics of the MQS investigated as well as maxima and minima of the summary queue length of customers and maxima and minima of the queue length of customers. Also, the paper presents a survey on the works for extreme values in queues and the queues in heavy traffic.      

Revenue-maximizing pricing and scheduling strategies in service systems with flexible customers

We propose a model of service operations systems in which customers are heterogeneous both in terms of their private delay sensitivity and flexibility. A service provider maximizes revenue through jointly optimal pricing and steady-state scheduling strategies. We provide a complete analysis for this generally intractable problem. Interestingly, when one queue accommodates a large population of impatient customers, it may be desirable to strategically idle the server in the other queue, which is a phenomenon new to the literature.     

Waiting time distributions in the accumulating priority queue

We are interested in queues in which customers of different classes arrive to a service facility, and where performance targets are specified for each class. The manager of such a queue has the task of implementing a queueing discipline that results in the performance targets for all classes being met simultaneously. For the case where the performance targets are specified in terms of ratios of mean waiting times, as long ago as the 1960s, Kleinrock suggested a queueing discipline to ensure that the targets are achieved. He proposed that customers accumulate priority as a linear function of their time in the queue: the higher the urgency of the customer’s class, the greater the rate at which that customer accumulates priority. When the server becomes free, the customer (if any) with the highest accumulated priority at that time point is the one that is selected for service. Kleinrock called such a queue a time-dependent priority queue, but we shall refer to it as the accumulating priority queue. Recognising that the performance of many queues, particularly in the healthcare and human services sectors, is specified in terms of tails of waiting time distributions for customers of different classes, we revisit the accumulating priority queue to derive its waiting time distributions, rather than just the mean waiting times. We believe that some elements of our analysis, particularly the process that we call the maximum priority process, are of mathematical interest in their own right.     

Equilibrium customers’ choice between FCFS and random servers

Consider two servers of equal service capacity, one serving in a first-come first-served order (FCFS), and the other serving its queue in random order. Customers arrive as a Poisson process and each arriving customer observes the length of the two queues and then chooses to join the queue that minimizes its expected queueing time. Assuming exponentially distributed service times, we numerically compute a Nash equilibrium in this system, and investigate the question of which server attracts the greater share of customers. If customers who arrive to find both queues empty independently choose to join each queue with probability 0.5, then we show that the server with FCFS discipline obtains a slightly greater share of the market. However, if such customers always join the same queue (say of the server with FCFS discipline) then that server attracts the greater share of customers. This research was supported by the Israel Science Foundation grant No. 526/08.     

Exact Analysis of the State-Dependent Polling Model

We consider a polling model in which a number of queues are served, in cyclic order, by a single server. Each queue has its own distinct Poisson arrival stream, service time, and switchover time (the server's travel time from that queue to the next) distribution. A setup time is incurred if the polled queue has one or more customers present. This is the polling model with State-Dependent service (the SD model). The SD model is inherently complex; hence, it has often been approximated by the much simpler model with State-Independent service (the SI model) in which the server always sets up for a service at the polled queue, regardless of whether it has customers or not. We provide an exact analysis of the SD model and obtain the probability generating function of the joint queue length distribution at a polling epoch, from which the moments of the waiting times at the various queues are obtained. A number of numerical examples are presented, to reveal conditions under which the SD model could perform worse than the corresponding SI model or, alternately, conditions under which the SD model performs better than a corresponding model in which all setup times are zero. We also present expressions for a variant of the SD model, namely, the SD model with a patient server.     

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.     

The MM CPP/GE/c G-Queue: Sojourn Time Distribution

We obtain the sojourn time probability distribution function at equilibrium for a Markov modulated, multi-server, single queue with generalised exponential (GE) service time distribution and compound Poisson arrivals of both positive and negative customers. Such arrival processes can model both burstiness and correlated traffic and are well suited to models of ATM and other telecommunication networks. Negative customers remove (ordinary) customers in the queue and are similarly correlated and bursty. We consider both the cases where negative customers remove positive customers from the front and the end of the queue and, in the latter case, where a customer currently being served can and cannot be killed by a negative customer. These cases can model an unreliable server or load balancing respectively. The results are obtained as Laplace transforms and can be inverted numerically. The MM CPP/GE/c G-Queue therefore holds the promise of being a viable building block for the analysis of queues and queueing networks with bursty, correlated traffic, incorporating load balancing and node-failures, since the equilibrium behaviour of both queue lengths and response times can be determined in a tractable way.