Optimal server allocation in general,finite, multi‐server queueing networks

Queueing networks with finite buffers, multiple servers, arbitrary acyclic, series‐parallel topologies, and general service time distributions are considered in this paper. An approach to optimally allocate servers to series, merge, and split topologies and their combinations is demonstrated. The methodology builds on two‐moment approximations to the service time distribution embedded in the generalized expansion method for computing the performance measures in complex finite queueing networks and Powell's algorithm for optimally allocating servers to the network topology. Convexity of the objective function along with results from computational experiments is presented for showing the efficacy of the methodology. Copyright © 2009 John Wiley & Sons, Ltd.     

A single server queue with service interruptions

In this paper we characterize the queue-length distribution as well as the waiting time distribution of a single-server queue which is subject to service interruptions. Such queues arise naturally in computer and communication problems in which customers belong to different classes and share a common server under some complicated service discipline. In such queues, the viewpoint of a given class of customers is that the server is not available for providing service some of the time, because it is busy serving customers from a different class. A natural special case of these queues is the class of preemptive priority queues. In this paper, we consider arrivals according the Markovian Arrival Process (MAP) and the server is not available for service at certain times. The service times are assumed to have a general distribution. We provide numerical examples to show that our methods are computationally feasible. This revised version was published online in June 2006 with corrections to the Cover Date.     

Reduction of a polling network to a single node

We consider a discrete-time tree network of polling servers where all packets are routed to the same node (called node 0), from which they leave the network. All packets have unit size and arrive from the exterior according to independent batch Bernoulli arrival processes. The service discipline of each node is work-conserving and the service discipline of node 0 has to be HoL-based, which is an additional assumption that is satisfied by, a.o., m _i -limited service, exhaustive service, and priority disciplines. Let a type i packet be a packet that visits queue i of node 0. We establish a distributional relation between the number of type i packets in the network and in a single station system, and we show equality of the mean end-to-end delay of type i packets in the two systems. Essentially this reduces an arbitrary tree network to a much simpler system of one node, while preserving the mean end-to-end delay of type i packets.      

Stability and instability of routings through a queueing network

We consider a network of N nodes with given distances in which customers arrive at one of the nodes and request transportation to one of the other nodes. There is a finite number of servers (or transporters) with possibly different capacities and speed available. We show that there exists a critical arrival rate κ_c, such that if the arrival rate is larger than κ_c then the number of customers in the system increases to ∞ with linear speed no matter which routing strategy for the transporters is chosen (even if we allow the strategy to depend on the future arrival process). If, on the other hand, κ < _c then there exists even a fixed periodic routing strategy which keeps the system stable (in a sense to be made precise). We prefer to start with a deterministic set-up which allows very general arrival processes and look at the stochastic case only in the final section where we get more refined results by assuming that the arrival process has integrable stationary ergodic increments (which still allows batch arrivals and long-range dependence). Potential applications include the control of elevators in highrise buildings. This revised version was published online in June 2006 with corrections to the Cover Date.     

Optimal server scheduling in nonpreemptive finite-population queueing systems

We consider a finite-population queueing system with heterogeneous classes of customers and a single server. For the case of nonpreemptive service, we fully characterize the structure of the server's optimal service policy that minimizes the total average customer waiting costs. We show that the optimal service policy may never serve some classes of customers. For those classes that are served, we show that the optimal service policy is a simple static priority policy. We also derive sufficient conditions that determine the optimal priority sequence.     

Single server with linear state-dependent mean rate

A birth-death queueing system with asingle server, first-come first-served discipline, Poisson arrivals and mean service rate which depends linearly on the number of customers in the system, is considered. Explicit expressions are derived for the equilibrium densities of the sojourn and waiting times. Simple approximations to the densities, including the first order correction terms, are obtained in a heavy-traffic situation.     

Analysis of a single server queue with semi-Markovian service interruption

In this paper we analyze a discrete-time single server queue where the service time equals one slot. The numbers of arrivals in each slot are assumed to be independent and identically distributed random variables. The service process is interrupted by a semi-Markov process, namely in certain states the server is available for service while the server is not available in other states. We analyze both the transient and steady-state models. We study the generating function of the joint probability of queue length, the state and the residual sojourn time of the semi-Markov process. We derive a system of Hilbert boundary value problems for the generating functions. The system of Hilbert boundary value problems is converted to a system of Fredholm integral equations. We show that the system of Fredholm integral equations has a unique solution. This revised version was published online in June 2006 with corrections to the Cover Date.     

Optimal control of a single server in a finite-population queueing network

We study the optimal dynamic assignment of a single server to multiple stations in a finite-population queueing network. The objective is to maximize the long-run average reward/throughput. We use sample-path comparisons to identify conditions on the network structure and service time distributions under which the optimal policy is an index policy. This index policy assigns the server to the non-empty station where it takes the shortest amount of time (in some stochastic sense) to complete a job. For example, in a network of multiple parallel stations, the optimal policy assigns the highest priority to the fastest station if service times can be ordered in likelihood ratios. Finally, by means of a numerical study, we test the shortest-expected-remaining-service-time policy on parallel-series networks with three stations and find that this index policy either coincides with the optimal policy or provides a near-optimal performance.     

Mean-value analysis for a class of Petri nets and batch-movement queueing networks with product-form equilibrium distributions

A number of recent papers have shown that there are classes of queueing networks, with batches of customers served and routed through the network, which have generalized product form equilibrium distributions. This extends to some Petri nets. In this paper, we indicate how a class of these is amenable to a mean-value analysis similar to that used for single-movement networks. To bring out the simplicity of the underlying ideas, we do this by working a simple example rather than presenting the development in its generality.     

Control and scheduling in a two-station queueing network: Optimal policies and heuristics

Consider a two-station queueing network with two types of jobs: type 1 jobs visit station 1 only, while type 2 jobs visit both stations in sequence. Each station has a single server. Arrival and service processes are modeled as counting processes with controllable stochastic intensities. The problem is to control the arrival and service processes, and in particular to schedule the server in station 1 among the two job types, in order to minimize a discounted cost function over an infinite time horizon. Using a stochastic intensity control approach, we establish the optimality of a specific stationary policy, and show that its value function satisfies certain properties, which lead to a switching-curve structure. We further classify the problem into six parametric cases. Based on the structural properties of the stationary policy, we establish the optimality of some simple priority rules for three of the six cases, and develop heuristic policies for the other three cases.     

On the optimal control of a single-server queueing system: Further remarks

This comment is in response to a reply by Scott and Jefferson (Ref. 3) concerning the application of control theory to a queueing problem.     

A single server queue with cyclically indexed arrival and service rates

In this paper we consider a queueing model that results from at least two apparently unrelated areas. One motivation to study a system of this type results from a test case of a computer simulation factor screening technique calledfrequency domain methodology. A second motivation comes from manufacturing, where due to cyclic scheduling of upstream machines, the arrival process to downstream machines is periodic. The model is a single server queue with FIFO service discipline and exponential interarrival and service times where the arrival and/or service rates are deterministic cyclic functions of the customer sequence number. We provide steady state results for the mean number in the system for the model with cyclic arrival and fixed service rates and for the model with fixed arrival and cyclic service rates. For the model with both cyclic arrival and service rates, upper and lower bounds are developed for the steady state mean waiting time in the system. Throughout the paper various implications and/or insights derived from the results of this study are discussed for frequency domain methodology.The authors acknowledge the financial support of the CBA/GSB Faculty Research Committee of the College of Business Administration, The University of Texas at Austin.     

On the optimal control of a single-server queueing system: Reply

This comment replies to a criticism due to Klein and Gruver (Ref. 1) of our earlier paper (Ref. 2) on the application of control theory to a queueing system. The criticism concerns the state-space diagram and the table which we inadvertently gave for the terminal-reward problem, albeit incorrectly labeled, rather than for the free-endpoint problem considered in our paper. We show that the solution given by Klein and Gruver is itself incorrect and nonoptimal.     

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.     

Estimating the sojourn time sensitivity in queueing networks using perturbation analysis

The sample path perturbation analysis technique developed earlier for the analysis of throughput sensitivities (Refs. 1–3) is extended to the performance measures involving mean sojourn times of customers. The major features of the sojourn time sensitivity problem are twofold. Firstly, it is a performance associated with servers, and not with customers. Secondly, the average sojourn time in any finite observation period can be a discontinuous function of mean service times when blocking is involved in a system. This discontinuity causes errors which must be accounted for in the estimation of sensitivities. Numerical experiments and analysis validate this method of computation of the sensitivities.This work was supported by the US Office of Naval Research, Contracts N00014-84-K-0465 and N00014-79-C-0776, and by the National Science Foundation, Grant No. ENG-78-15231.     

A two-stage queueing network with MAP inputs and buffer sharing

In this paper, we study a two-stage tandem queueing network with MAP inputs and buffer sharing. The two stages share the same buffer. By using Markov process, we give an exact analysis of the queueing network. Since the customer arrival is not a Poisson process, the PASTA (Poisson Arrivals See Time Averages) property does not hold. A matrix filtration technique is proposed to derive the probability distribution of queue length at arrivals. Our objective is to investigate how the buffer sharing policy is mitigate the tradeoff between the probability that an arriving customer is lost and the probability that the first-stage server is blocked. The numerical results show that buffer sharing policy is more flexible, especially when the inputs have large variant and are correlated.     

A Simple proof for the stability of global FIFO queueing networks

We study the stability of multiclass queueing networks under the global FIFO （first in first out） service discipline, which was established by Bramson in 2001. For these networks, the service priority of a customer is determined by his entrance time. Using fluid models, we describe the entrance time of the most senior customer in the networks at time t, which is the key to simplify the proof for the stability of the global FIFO queueing networks.     

Closed queueing networks with batch services

In this paper we study queueing networks which allow multiple changes at a given time. The model has a natural application to discrete-time queueing networks but describes also queueing networks in continuous time. It is shown that product-form results which are known to hold when there are single changes at a given instant remain valid when multiple changes are allowed.