A Push–Pull Network with Infinite Supply of Work

We consider a two-node multiclass queueing network with two types of jobs moving through two servers in opposite directions, and there is infinite supply of work of both types. We assume exponential processing times and preemptive resume service. We identify a family of policies which keep both servers busy at all times and keep the queues between the servers positive recurrent. We analyze two specific policies in detail, obtaining steady state distributions. We perform extensive calculations of expected queue lengths under these policies. We compare this network with the Kumar–Seidman–Rybko–Stolyar network, in which there are two random streams of arriving jobs rather than infinite supply of work.     

Scheduling in Multiclass Networks with Deterministic Service Times

We consider general feed-forward networks of queues with deterministic service times and arbitrary arrival processes. There are holding costs at each queue, idling may or may not be permitted, and servers may fail. We partially characterize the optimal policy and give conditions under which lower priority should be given to jobs that would be delayed later in the network if they were processed now.     

Two Queues with Weighted One-Way Overflow

We consider an open queueing network consisting of two queues with Poisson arrivals and exponential service times and having some overflow capability from the first to the second queue. Each queue is equipped with a finite number of servers and a waiting room with finite or infinite capacity. Arriving customers may be blocked at one of the queues depending on whether all servers and/or waiting positions are occupied. Blocked customers from the first queue can overflow to the second queue according to specific overflow routines. Using a separation method for the balance equations of the two-dimensional server and waiting room demand process, we reduce the dimension of the problem of solving these balance equations substantially. We extend the existing results in the literature in three directions. Firstly, we allow different service rates at the two queues. Secondly, the overflow stream is weighted with a parameter p ∈ [0,1], i.e., an arriving customer who is blocked and overflows, joins the overflow queue with probability p and leaves the system with probability 1 − p. Thirdly, we consider several new blocking and overflow routines. An erratum to this article can be found at     

M/M/∞ Queues in series with non-homogeneous inputs

This paper studies the transient behaviour of tandem queueing system consisting of an arbitrary number r of queues in series with infinite server service facility at each queue. Poisson arrivals with time dependent parameter and exponential service times have been assumed. Infinite server queues realistically describe those queues in which sufficient service capacity exist to prevent virtually any waiting by the customer present. The model is suitable for both phase type service as well services in series. Very elegant solutions have been obtained and it has been shown that if the queue sizes are initially independent and Poisson then they remain independent and Poisson for all t.     

Server allocation for zero buffer tandem queues

In this paper we consider the problem of allocating servers to maximize throughput for tandem queues with no buffers. We propose an allocation method that assigns servers to stations based on the mean service times and the current number of servers assigned to each station. A number of simulations are run on different configurations to refine and verify the algorithm. The algorithm is proposed for stations with exponentially distributed service times, but where the service rate at each station may be different. We also provide some initial thoughts on the impact on the proposed allocation method of including service time distributions with different coefficients of variation.     

Analysis of Markov Multiserver Retrial Queues with Negative Arrivals

Negative arrivals are used as a control mechanism in many telecommunication and computer networks. In the paper we analyze multiserver retrial queues; i.e., any customer finding all servers busy upon arrival must leave the service area and re-apply for service after some random time. The control mechanism is such that, whenever the service facility is full occupied, an exponential timer is activated. If the timer expires and the service facility remains full, then a random batch of customers, which are stored at the retrial pool, are automatically removed. This model extends the existing literature, which only deals with a single server case and individual removals. Two different approaches are considered. For the stable case, the matrix–analytic formalism is used to study the joint distribution of the service facility and the retrial pool. The approximation by more simple infinite retrial model is also proved. In the overloading case we study the transient behaviour of the trajectory of the suitably normalized retrial queue and the long-run behaviour of the number of busy servers. The method of investigation in this case is based on the averaging principle for switching processes.     

Approximate analysis of non-stationary loss queues and networks of loss queues with general service time distributions

A Fixed Point Approximation (FPA) method has recently been suggested for non-stationary analysis of loss queues and networks of loss queues with Exponential service times. Deriving exact equations relating time-dependent mean numbers of busy servers to blocking probabilities, we generalize the FPA method to loss systems with general service time distributions. These equations are combined with associated formulae for stationary analysis of loss systems in steady state through a carried load to offered load transformation. The accuracy and speed of the generalized methods are illustrated through a wide set of examples.     

Large deviations of Markovian polling models with applications to admission control

In this paper we consider large deviations and admission control problems for a discrete-time Markovian polling system. The system consists of two-parallel queues and multiple heterogeneous servers. The arrival process of each queue is a superposition of mutually independent Markovian on/off processes, and the multiple servers serve independently the two queues according to the so called Bernoulli service schedule. Using the large deviations techniques, we derive upper and lower bounds of the overflow probabilities, and then we present an admission control criterion by which different Quality of Service (QoS) requirements for the two queues are guaranteed.     

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.     

Interoutput times in processor sharing queues with feedback

While properties of the flows in isolated processor sharing queues are well understood, little is known about the flows in networks with processor sharing nodes. This paper analyzes the internal traffic processes in processor sharing queues with instantaneous Bernoulli feedback. The internal traffic does not inherit the insensitivity to the shape of the service requirement distribution from the external traffic. The interoutput time distribution is studied in the single server and infinite server processor sharing queues. For the systems we study, we show that when service requirement distributions with the same means are convexly ordered, so are interoutput time distributions.This work was partially supported by the National Science Foundation under Grant ECS-8501217 and by the Graduate School of the University of Massachusetts under Faculty Research Grant 1-03205.     

Fluid models of many-server queues with abandonment

We study many-server queues with abandonment in which customers have general service and patience time distributions. The dynamics of the system are modeled using measure-valued processes, to keep track of the residual service and patience times of each customer. Deterministic fluid models are established to provide a first-order approximation for this model. The fluid model solution, which is proved to uniquely exist, serves as the fluid limit of the many-server queue, as the number of servers becomes large. Based on the fluid model solution, first-order approximations for various performance quantities are proposed.     

Modeling traffic flow interrupted by incidents

A steady-state M/M/c queueing system under batch service interruptions is introduced to model the traffic flow on a roadway link subject to incidents. When a traffic incident happens, either all lanes or part of a lane is closed to the traffic. As such, we model these interruptions either as complete service disruptions where none of the servers work or partial failures where servers work at a reduced service rate. We analyze this system in steady-state and present a scheme to obtain the stationary number of vehicles on a link. For those links with large c values, the closed-form solution of M/M/∞ queues under batch service interruptions can be used as an approximation. We present simulation results that show the validity of the queueing models in the computation of average travel times.     

TheGr X n/G n/∞ system: System size

An important property of most infinite server systems is that customers are independent of each other once they enter the system. Though this non-interacting property (NIP) has been instrumental in facilitating excellent results for infinite server systems in the past, the utility of this property has not been fully exploited or even fully recognized. This paper exploits theNIP by investigating a general infinite server system with batch arrivals following a Markov renewal input process. The batch sizes and service times depend on the customer types which are regulated by the Markov renewal process. By conditional approaches, analytical results are obtained for the generating functions and binomial moments of both the continuous time system size and pre-arrival system size. These results extend the previous results on infinite server queues significantly.     

Erlang arrivals joining the shorter queue

We consider a system in which customers join upon arrival the shortest of two single-server queues. The interarrival times between customers are Erlang distributed and the service times of both servers are exponentially distributed. Under these assumptions, this system gives rise to a Markov chain on a multi-layered quarter plane. For this Markov chain we derive the equilibrium distribution using the compensation approach. The expression for the equilibrium distribution matches and refines tail asymptotics obtained earlier in the literature.     

A model for rational abandonments from invisible queues

We propose a model for abandonments from a queue, due to excessive wait, assuming that waiting customers act rationally but without being able to observe the queue length. Customers are allowed to be heterogeneous in their preferences and consequent behavior. Our goal is to characterize customers' patience via more basic primitives, specifically waiting costs and service benefits: these two are optimally balanced by waiting customers, based on their individual cost parameters and anticipated waiting time. The waiting time distribution and patience profile then emerge as an equilibrium point of the system. The problem formulation is motivated by teleservices, prevalently telephone- and Internet-based. In such services, customers and servers are remote and queues are typically associated with the servers, hence queues are invisible to waiting customers. Our base model is the M/M/m queue, where it is shown that a unique equilibrium exists, in which rational abandonments can occur only upon arrival (zero or infinite patience for each customer). As such a behavior fails to capture the essence of abandonments, the base model is modified to account for unusual congestion or failure conditions. This indeed facilitates abandonments in finite time, leading to a nontrivial, customer dependent patience profile. Our analysis shows, quite surprisingly, that the equilibrium is unique in this case as well, and amenable to explicit calculation. This revised version was published online in June 2006 with corrections to the Cover Date.     

Out-patient Queues at the Ibn-Rochd Health Centre

An arbitrary policy of fixing the number of outpatient appointments specifying the dates (and not the exact times) of appointments created long queues and large waiting times in some departments of the Ibn-Rochd health centre, but considerable idle time for the consulting doctors in others. After narrating in detail these circumstances and examining a number of possible options, this paper describes the scientific approaches made to determine the number of appointments, the corresponding parameters of the queue and the system and the service per cent occupation.Finite source size, a random number of initial patients, group arrivals, non-exponential service time distribution, late start-up of the servicing unit and many other factors combined to render available theoretical results difficult to apply and results obtained by applying approximately equivalent theoretical models unreliable as compared with those observed in real life. It is shown that simulation could be more profitably applied in such situations.     

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.     

Features of some discrete-time cyclic queueing networks

A class of discrete-time closed cyclic networks is analyzed, where queues at each node have ample waiting room and have independent geometric service times with possibly unequal means. If each node has a single server or if there are sufficiently many parallel servers at each node to accommodate all jobs, equilibrium vectors of product form are obtained. For some other cases, equilibrium vectors of product form need not exist. For the single-server model, a normalization constant is computed and used to determine the queue-length distribution at a node.     

A scheduling problem for several parallel servers

In this paper, we study a scheduling problem of jobs from two different queues on several parallel servers. Jobs have exponentially distributed processing times, and incur costs per unit of time, until they leave the system, and there are no arrivals to the system at any time. The objective is to find the optimal strategy, i.e., to allocate the servers to the queues, such that the expected holding costs are minimized. We give a sufficient condition for which it is always optimal to allocate the servers only to jobs of a certain queue. Finally, the case of two servers is completely solved.     

Models and Approximations for Call Center Design

A call center is a facility for delivering telephone service, both incoming and outgoing. This paper addresses optimal staffing of call centers, modeled as M/G/n queues whose offered traffic consists of multiple customer streams, each with an individual priority, arrival rate, service distribution and grade of service (GoS) stated in terms of equilibrium tail waiting time probabilities or mean waiting times. The paper proposes a methodology for deriving the approximate minimal number of servers that suffices to guarantee the prescribed GoS of all customer streams. The methodology is based on an analytic approximation, called the Scaling-Erlang (SE) approximation, which maps the M/G/n queue to an approximating, suitably scaled M/G/1 queue, for which waiting time statistics are available via the Pollaczek-Khintchine formula in terms of Laplace transforms. The SE approximation is then generalized to M/G/n queues with multiple types of customers and non-preemptive priorities, yielding the Priority Scaling-Erlang (PSE) approximation. A simple goal-seeking search, utilizing SE/PSE approximations, is presented for the optimal staffing level, subject to GoS constraints. The efficacy of the methodology is demonstrated by comparing the number of servers estimated via the PSE approximation to their counterparts obtained by simulation. A number of case studies confirm that the SE/PSE approximations yield optimal staffing results in excellent agreement with simulation, but at a fraction of simulation time and space.