Estimation for a class of simple queueing networks

Maximum likelihood estimators of the parameters of an open Jackson network are derived, and their joint asymptotic normality is established. The problem of estimation for tandem queues is discussed as a special case of the Jackson system. These results are valid when the system is not necessarily in equilibrium.     

On a class of approximations for closed queueing networks

This paper presents some analytical results concerning an approximation procedure for closed queueing networks. The procedure is well-known and has been found useful for product-form networks where large numbers of queues, jobs or job classes prohibit an exact analysis, as well as for networks which do not possess product-form. The procedure represents the mean sojourn time at a queue as a function of the throughput of the queue, and derives a set of fixed point equations for the throughputs of the various job classes. We begin by showing that under a mild regularity condition the fixed point equations have a unique solution. Then we show that derivatives of performance measures can be readily calculated, and that their simple form provides an interesting insight into capacity allocation in closed queueing networks.This work was supported in part by the Nuffield Foundation     

Performance evaluation of scheduling control of queueing networks: Fluid model heuristics

Motivated by dynamic scheduling control for queueing networks, Chen and Yao [8] developed a systematic method to generate dynamic scheduling control policies for a fluid network, a simple and highly aggregated model that approximates the queueing network. This study addresses the question of how good these fluid policies are as heuristic scheduling policies for queueing networks. Using simulation on some examples these heuristic policies are compared with traditional simple scheduling rules. The results show that the heuristic policies perform at least comparably to classical priority rules, regardless of the assumptions made about the traffic intensities and the arrival and service time distributions. However, they are certainly not always the best and, even when they are, the improvement is seldom dramatic. The comparative advantage of these policies may lie in their application to nonstationary situations such as might occur with unreliable machines or nonstationary demand patterns.     

Simple bounds for closed queueing networks

Consider a closed Jackson type network in which each queue has a single exponential server. Assume that N customers are moving among k queues. We establish simple closed form bounds on the network throughput (both lower and upper), which are sharper than those that are currently available. Numerical evaluation indicates that the improvements are significant.     

Empirical Bayes estimation for queueing systems and networks

Empirical Bayes estimators are derived for standardM/M/1 queues,M/M/1 queues with state-dependent arrival and service rates, finite capacityM/M/1 queues with state-dependent rates and for open Jackson networks. The asymptotic properties of the empirical Bayes estimators are derived both with respect to the conditional distribution of the observations given the parameters, and with respect to the joint distribution of the observations and the parameters.     

Higher order approximations for tandem queueing networks

In this paper a higher order approximation for single server queues and tandem queueing networks is proposed and studied. Different from the most popular two-moment based approximations in the literature, the higher order approximation uses the higher moments of the interarrival and service distributions in evaluating the performance measures for queueing networks. It is built upon the MacLaurin series analysis, a method that is recently developed to analyze single-node queues, along with the idea of decomposition using higher orders of the moments matched to a distribution. The approximation is computationally flexible in that it can use as many moments of the interarrival and service distributions as desired and produce the corresponding moments for the waiting and interdeparture times. Therefore it can also be used to study several interesting issues that arise in the study of queueing network approximations, such as the effects of higher moments and correlations. Numerical results for single server queues and tandem queueing networks show that this approximation is better than the two-moment based approximations in most cases.     

Large deviations for a simple closed queueing model

We consider a simple queueing model with one service station. The arrival and service processes have intensitiesa(N–Q _t) andNf(N ^–1 Q _t), where Q_t is the queue length,N is a large integer,a>0 andf(x) is a positive continuous function. We establish the large deviation principle for the sequence of the normalized queue length processq _N ^t =N ^–1Q_t,N1 for both light (a<f(0)) and heavy (af(0)) traffic and use this result for an investigation of ergodic properties ofq _N ^t ,N 1.     

A queueing model for crowdsourcing

Crowdsourcing is getting popular after a number of industries such as food, consumer products, hotels, electronics, and other large retailers bought into this idea of serving customers. In this paper, we introduce a multi-server queueing model in the context of crowdsourcing. We assume that two types, say, Type 1 and Type 2, of customers arrive to a c-server queueing system. A Type 1 customer has to receive service by one of c servers while a Type 2 customer may be served by a Type 1 customer who is available to act as a server soon after getting a service or by one of c servers. We assume that a Type 1 customer will be available for serving a Type 2 customer (provided there is at least one Type 2 customer waiting in the queue at the time of the service completion of that Type 1 customer) with probability \(p, 0 \le p \le 1\). With probability \(q = 1 - p\), a Type 1 customer will opt out of serving a Type 2 customer provided there is at least one Type 2 customer waiting in the system. Upon completion of a service a free server will offer service to a Type 1 customer on an FCFS basis; however, if there are no Type 1 customers waiting in the system, the server will serve a Type 2 customer if there is one present in the queue. If a Type 1 customer decides to serve a Type 2 customer, for our analysis purposes that Type 2 customer will be removed from the system as Type 1 customer will leave the system with that Type 2 customer. Under the assumption of exponential services for both types of customers we study the model in steady state using matrix analytic methods and establish some results including explicit ones for the waiting time distributions. Some illustrative numerical examples are presented.     

A generalization of Norton's theorem for queueing networks

A general framework for aggregation and decomposition of product form queueing networks with state dependent routing and servicing is presented. By analogy with electrical circuit theory, the stations are grouped into clusters of subnetworks such that the process decomposes into a global process and a local process. Moreover, the local process factorizes into the subnetworks. The global process and the local processes can be analyzed separately as if they were independent. The global process describes the behaviour of the queuing network in which each cluster is aggregated into a single station, whereas the local process describes the behaviour of the subnetworks as if they are not part of the queueing network. The decomposition and aggregation method formalized in this paper allows us to first analyze the global behaviour of the queueing network and subsequently analyze the local behaviour of the subnetworks of interest or to aggregate clusters into single stations without affecting the behaviour of the rest of the queueing network. Conditions are provided such that:

- the global equilibrium distribution for aggregated clusters has a product form;

- this form can be obtained by merely monitoring the global behaviour;

- the computation of a detailed distribution, including its normalizing constant, can be decomposed into the computation of a global and a local distribution;

- the marginal distribution for the number of jobs at the stations of a cluster can be obtained by merely solving local behaviour.

As a special application, Norton's theorem for queueing networks is extended to queueing networks with state dependent routing such as due to capacity constraints at stations or at clusters of stations and state dependent servicing such as due to service delays for clusters of stations.     

Models for queue length in clocked queueing networks

We analyze a discrete-time network of queues. The unit element of the network is the 2 × 2 buffered switch, which we regard as a system of two queues working in parallel. We show how to transform transition probability information from the output of one switch, or network stage, to the input of the next one. This is used to carry out a Markov time series input model to predict mean queue length at every stage of the system. Another model considered is a renewal process time series model, which we use to find the mean queue length of the second stage of the network. Numerical simulations fall within the narrow band spanned by the two models.     

Fleet-sizing and service availability for a vehicle rental system via closed queueing networks

In this paper, we address the problem of determining the optimal fleet size for a vehicle rental company and derive analytical results for its relationship to vehicle availability at each rental station in the company’s network of locations. This work is motivated by the recent surge in interest for bicycle and electric car sharing systems, one example being the French program Vélib (2010). We first formulate a closed queueing network model of the system, obtained by viewing the system from the vehicle’s perspective. Using this framework, we are able to derive the asymptotic behavior of vehicle availability at an arbitrary rental station with respect to fleet size. These results allow us to analyze imbalances in the system and propose some basic principles for the design of system balancing methods. We then develop a profit-maximizing optimization problem for determining optimal fleet size. The large-scale nature of real-world systems results in computational difficulties in obtaining this exact solution, and so we provide an approximate formulation that is easier to solve and which becomes exact as the fleet size becomes large. To illustrate our findings and validate our solution methods, we provide numerical results on some sample networks.     

Branching/queueing networks: Their introduction and near-decomposability asymptotics

A new class of models, which combines closed queueing networks with branching processes, is introduced. The motivation comes from MIMD computers and other service systems in which the arrival of new work is always triggered by the completion of former work, and the amount of arriving work is variable. In the variant of branching/queueing networks studied here, a customer branches into a random and state-independent number of offspring upon completing its service. The process regenerates whenever the population becomes extinct. Implications for less rudimentary variants are discussed. The ergodicity of the network and several other aspects are related to the expected total number of progeny of an associated multitype Galton-Watson process. We give a formula for that expected number of progeny. The objects of main interest are the stationary state distribution and the throughputs. Closed-form solutions are available for the multi-server single-node model, and for homogeneous networks of infinite-servers. Generally, branching/queueing networks do not seem to have a product-form state distribution. We propose a conditional product-form approximation, and show that it is approached as a limit by branching/queueing networks with a slowly varying population size. The proof demonstrates an application of the nearly complete decomposability paradigm to an infinite state space. This revised version was published online in June 2006 with corrections to the Cover Date.     

Review of a fast simulation method for the analysis of queueing networks

This paper presents a review of and refinements to a class of discrete-event models for the analysis of unreliable queueing systems. In contrast to conventional piece-by-piece simulators, these models observe a number of rare events that affect the inflow and outflow rates at each queue. Between events, the evolution of the system is approximated by a linear function. Several experiments confirm the accuracy of this approximation and its computational efficiency over conventional simulation. © 1997 by John Wiley & Sons, Ltd.     

Perturbation analysis and optimization of queueing networks

A new time-domain-based approach is developed in this paper for the perturbation analysis of queueing networks. We show that, by observing a single sample path realization of the network trajectory, we can derive sensitivity information of the throughput of the system with respect to various parameters. This information can then be used for the optimization of queueing networks. Numerous experiments as well as analytical results demonstrating the validity of this new approach are given and discussed.     

A logistics problem: a non-markovian queueing network model and algorithm

In this paper, a stochastic version of the classical deterministic balanced single commodity capacitated transportation network problem is presented. In this model, each arc of the network connects a supply node to a demand node and the flow of units forming along each arc of the network forms a stochastic process (i.e.G/M/1 queueing system with generally distributed interarrival time, a Markovian server, a single server, infinite capacity, and the first come first served queueing discipline). In this model, the total transportation cost is minimized such that the total supply rate is equal to the total demand rate, and the resulting probability of finding excessive congestion along each arc (i.e., the resulting probability of finding congestion inside the queueing system formed along each arc in excess of a fixed number) is equal to a desirable value     

Diffusion approximations for open queueing networks with service interruptions

This paper establishes functional central limit theorems describing the heavy-traffic behavior of open single-class queueing networks with service interruptions. In particular, each station has a single server which is alternatively up and down. There are two treatments of the up and down times. The first treatment corresponds to fixed up and down times and leads to a reflected Brownian motion, just as when there are no service interruptions, but with different parameters. To represent long rare interruptions, the second treatment has growing up and down times with the up and down times being of ordern andn ^1/2, respectively, when the traffic intensities are of order 1-n^–1/2. In this case we establish convergence in the SkorohodM ₁ topology to a multidimensional reflection of multidimensional Brownian motion plus a multidimensional jump process.     

Towards better multi-class parametric-decomposition approximations for open queueing networks

Methods are developed for approximately characterizing the departure process of each customer class from a multi-class single-server queue with unlimited waiting space and the first-in-first-out service discipline. The model is (GT _i /GI _i )/1 with a non-Poisson renewal arrival process and a non-exponential service-time distribution for each class. The methods provide a basis for improving parametric-decomposition approximations for analyzing non-Markov open queueing networks with multiple classes. For example, parametric-decomposition approximations are used in the Queueing Network Analyzer (QNA). The specific approximations here extend ones developed by Bitran and Tirupati [5]. For example, the effect of class-dependent service times is considered here. With all procedures proposed here, the approximate variability parameter of the departure process of each class is a linear function of the variability parameters of the arrival processes of all the classes served at that queue, thus ensuring that the final arrival variability parameters in a general open network can be calculated by solving a system of linear equations.     

Asymptotic analysis for closed multichain queueing networks with bottlenecks

We consider a two-chain exponential queueing network with a large number of customers that consists of one infinite-server (IS) station and two processor-sharing (PS) or FCFS single-server stations. The asymptotic behavior of the partition function is studied for such a network when one or both PS (FCFS) nodes are heavily loaded. The results are derived using methods of multidimensional complex analysis (the theory of homologies and residues) and the saddle-point method.     

Nonexistence of Brownian models for certain multiclass queueing networks

We present two multiclass queueing networks where the Brownian models proposed by Harrison and Nguyen [3,4] do not exist. If self-feedback is allowed, we can construct such an example with a two-station network. For a three-station network, we can construct such an example without self-feedback.Research supported in part by Texas Instruments Corporation Grant 90456-034.     

Multigrid algorithm from cyclic reduction for Markovian queueing networks

A multigrid method based on cyclic reduction strategy is proposed to solve huge, nonsymmetric singular linear systems arising from Markovian queueing networks. A simple way to construct the matrix-dependent prolongation and restriction operators is presented in this paper. Numerical results for multiple queues are given to illustrate the efficiency and robustness of our methods.