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.     

Convexity properties of the overflow in an ordered-entry system with heterogeneous servers

The overflow probability in an Erlang loss system is known to be decreasing convex in the number of servers. Here we consider the GI/M/m loss system with ordered entry and heterogeneous servers. We show that adding a sequence of servers with non-increasing (non-decreasing) service rates will yield a decreasing convex (log-concave) sequence of overflow probabilities. An optimal server allocation problem is solved as a direct application of these results.     

Threshold policies for controlled retrial queues with heterogeneous servers

Retrial queues are an important stochastic model for many telecommunication systems. In order to construct competitive networks it is necessary to investigate ways for optimal control. This paper considers K -server retrial systems with arrivals governed by Neut' Markovian arrival process, and heterogeneous service time distributions of general phase-type. We show that the optimal policy which minimizes the number of customers in the system is of a threshold type with threshold levels depending on the states of the arrival and service processes. An algorithm for the numerical evaluation of an optimal control is proposed on the basis of Howar's iteration algorithm. Finally, some numerical results will be given in order to illustrate the system dynamics. AMS subject classification: 60K25 93E20     

Convex comparison of service disciplines in real time queues

We present a comparison of the service disciplines in real time queueing systems (the customers have a deadline before which they should enter the service booth). We state that giving priority to customers having an early deadline minimizes the average stationary lateness. We show this result by comparing adequate random vectors with the Schur convex majorization ordering.     

Expulsion and scheduling control for multiclass queues with heterogeneous servers

We consider an M/M/2 system with nonidentical servers and multiple classes of customers. Each customer class has its own reward rate and holding cost. We may assign priorities so that high priority customers may preempt lower priority customers on the servers. We give two models for which the optimal admission and scheduling policy for maximizing expected discounted profit is determined by a threshold structure on the number of customers of each type in the system. Surprisingly, the optimal thresholds do not depend on the specific numerical values of the reward rates and holding costs, making them relatively easy to determine in practice. Our results also hold when there is a finite buffer and when customers have independent random deadlines for service completion.     

Analysis of job transfer policies in systems with unreliable servers

We consider a system where incoming jobs may be executed at different servers, each of which goes through alternating periods of being available and unavailable. Neither the states of the servers nor the relevant queue sizes are known at moments of arrival. Hence, a load balancing mechanism that relies on random time-out intervals and job transfers from one queue to another is adopted. The object is to minimize a cost function which may include holding costs and transfer costs. A model of a single queue with an unreliable server and timeouts is analyzed first. The results are then used to obtain an approximate solution for arbitrary number of queues. Several transfer policies are evaluated and compared.     

Two fluid approximations for multi-server queues with abandonments

Insight is provided into a previously developed M/M/s/r+M(n) approximation for the M/GI/s/r+GI queueing model by establishing fluid and diffusion limits for the approximating model. Fluid approximations for the two models are compared in the many-server efficiency-driven (overloaded) regime. The two fluid approximations do not coincide, but they are close.     

Transient analysis of queues with heterogeneous arrivals

In this paper we consider a discrete time queueing model where the time axis is divided into time slots of unit length. The model satisfies the following assumptions: (i) an event is either an arrival of typei of batch sizeb _i, i=1,...,r with probability _i or is a depature of a single customer with probability or zero depending on whether the queue is busy or empty; (ii) no more than one event can occur in a slot, therefore the probability that neither an arrival nor a departure occurs in a slot is 1––_{i i} or 1–_{i i} according as the queue is busy or empty; (iii) events in different slots are independent. Using a lattice path representation in higher dimensional space we will derive the time dependent joint distribution of the number of arrivals of various types and the number of completed services. The distribution for the corresponding continuous time model is found by using weak convergence.     

Stationary queues with one autonomous server

Given a stationary stochastic continuous demand of service σ(θ_tω) dt with ∫ σ(ω)P(dω) < 1, we construct real stationary point processes $\text{(T}{}_{\mathrm{n}}\text{, n ∈}\text{Z}\text{)[T}{}_{\mathrm{n}}\text{< T}{}_{\mathrm{n}}\text{+1, lim}{}_{\mathrm{\pm \infty }}\text{T}{}_{\mathrm{n}}\text{= ±∞]}$ such that

for a given constant D \2>0. These point processes correspond to a service discipline for which a single server services during the time intervals [T_n, T_n+1[ the demand of service accumulated during the proceding intervals [T_n?1, T_n[ and take a rest of fixed duration D.     

Smoothed perturbation analysis for queues with finite buffers

Applying the technique of smoothed perturbation analysis (SPA) to theGI/G/1/K queue, we derive gradient estimators for two performance measures: the mean steady-state system time of a served customer and the probability that an arriving customer is rejected. Unbiasedness of the estimators follows from results of a previous general framework on SPA estimators. However, in that framework, the estimators often require the simulation of numerous additional sample subpaths, possibly making the technique practically infeasible in applications. We exploit some of the special structure of theGI/G/1/K queue to come up with an estimator which requires at most the simulation of a single additional sample subpath. By establishing certain regenerative properties, we provide a strong consistency proof for the estimator.     

Sample path methods in the control of queues

Sample path methods are now among the most used techniques in the control of queueing systems. However, due to the lack of mathematical formalism, they may appear to be non-rigorous and even sometimes mysterious. The goal of this paper is threefold: to provide a general mathematical setting, to survey the most popular sample path methods including forward induction, backward induction and interchange arguments, and to illustrate our approach through the study of a number of classical scheduling and routing optimization problems arising in queueing theory.Z. Liu was supported in part by the CEC DG XIII under the ESPRIT BRA grants QMIPS.P. Nain was supported in part by NSF under grant NCR-9116183 and by the CEC DG XIII under the ESPRIT BRA grants QMIPS.D. Towsley was supported in part by NSF under grant NCR-9116183.     

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=).     

The combinatorics of birth-death processes and applications to queues

In this paper we present a combinatorial technique which allows the derivation of the transition functions of general birth-death processes. This method provides a flexible tool for the transient analysis of Markovian queueing systems with state dependent transition rates, like M/M/c models or systems with balking and reneging. This revised version was published online in June 2006 with corrections to the Cover Date.     

Large deviations ordering of point processes in some queueing networks

Given a stochastic ordering between point processes, say that a p.p. N is smooth if it is less than the Poisson process with the same average intensity for this ordering. In this article we investigate whether initially smooth processes retain their smoothness as they cross a network of FIFO ·/D/1 queues along fixed routes. For the so-called strong variability ordering we show that point processes remain smooth as they proceed through a tandem of quasi-saturated (i.e., loaded to 1) M+·/D/1 queues. We then introduce the Large Deviations ordering, which involves comparison of the rate functions associated with Large Deviations Principles satisfied by the point processes. For this ordering, we show that smoothness is retained when the processes cross a feed-forward network of unsaturated ·/D/1 queues. We also examine the LD characteristics of a deterministic p.p. at the output of an M+·/D/1 queue. This revised version was published online in June 2006 with corrections to the Cover Date.     

A tollbooth tandem queue with heterogeneous servers

We study a tandem queueing system with K servers and no waiting space in between. A customer needs service from one server but can leave the system only if all down-stream servers are unoccupied. Such a system is often observed in toll collection during rush hours in transportation networks, and we call it a tollbooth tandem queue. We apply matrix-analytic methods to study this queueing system, and obtain explicit results for various performance measures. Using these results, we can efficiently compute the mean and variance of the queue lengths, waiting time, sojourn time, and departure delays. Numerical examples are presented to gain insights into the performance and design of the tollbooth tandem queue. In particular, it reveals that the intuitive result of arranging servers in decreasing order of service speed (i.e., arrange faster servers at downstream stations) is not always optimal for minimizing the mean queue length or mean waiting time.     

A stochastic recirculation system with random access

A model for a stochastic recirculation system with randomly accessed multiple heterogeneous servers, no waiting rooms, and exponentially-distributed service times is provided. In this system the units are assigned to one of the servers upon arrival by random mechanism. Units which find all servers busy recirculate and combine with the incoming arrivals and join those already in the system to initiate the next cycle. The equilibrium behavior of the internal and external stochastic processes of the system is analyzed using a two parameter approximation. A simulation model is also developed and its behavior is compared against the analytical model at the steady state. The model with randomly-accessed servers is compared to a single server model already established in the literature. The performance of the model is then examined for a wide range of parameter values to obtain conclusions about its optimal performances.     

Multiclass batch arrival retrial queues analyzed as branching processes with immigration

TheM/G/1 batch arrival retrial queue is studied by means of branching processes with immigration. We shall investigate this queue when traffic intensity is less than one, tends to one or is greater than one.     

Nonstationary queues with Interrrupted Poisson arrivals and unreliable/repairable servers

A queueing model having a nonstationary Interrupted Poisson arrival process (IPP(t)),s time-dependent exponential unreliable/repairable servers and finite capacityc is introduced, and an approximation method for analysis of it is developed and tested. Approximations are developed for the time-dependent queue length moments and the system viewpoint waiting time distributions and moments. The approximation involves state-space partitioning and numerically integrating partial-moment differential equations (PMDEs). Surrogate distribution approximations (SDA's) are used to close the system of PMDEs. The approximations allow for analysis using only (s + 1)(s + 6) differential equations for the queue length moments rather than the 2(c + 1)(s +1) equations required by the classic method of numerically integrating the full set of Kolmogorov-forward equations. Effectively hours of cpu time are reduced to minutes for even modest capacity systems. Approximations for waiting time distributions and moments are developed.This research was partially funded by National Science Foundation grant ECS-8404409.     

Approximation of throughput in tandem queues with multiple servers and blocking

In this paper, we develop an approximation method for throughput in tandem queues with multiple independent reliable servers at each stage and finite buffers between service stations. We consider the blocking after service (BAS) blocking protocol of each service stage. The service time distribution of each server is exponential. The approximation is based on the decomposition of the system into a set of coupled subsystems which are modeled by two-stage tandem queue with two buffers and are analyzed by using the level dependent quasi-birth-and-death (LDQBD) process.