Consider a generalized queueing network model that is subject to two types of arrivals. The first type represents the regular customers; the second type represents signals. A signal induces a regular customer already present at a node to leave. Gelenbe [5] showed that such a network possesses a product form solution when each node consists of a single exponential server. In this paper we study a number of issues concerning this class of networks. First, we explain why such networks have a product form solution. Second, we generalize existing results to include different service disciplines, state-dependent service rates, multiple job classes, and batch servicing. Finally, we establish the relationship between these networks and networks of quasi-reversible queues. We show that the product form solution of the generalized networks is a consequence of a property of the individual nodes viewed in isolation. This property is similar to the quasi-reversibility property of the nodes of a Jackson network: if the arrivals of the regular customers and of the signals at a node in isolation are independent Poisson, the departure processes of the regular customers and the signals are also independent Poisson, and the current state of the system is independent of the past departure processes.

In several queueing systems the service rate of a server is affected by the work load present in the system. For example, a teller at a bank or a checker at a check-out counter in a supermarket may change the service rate depending on the number of customers present in the system. But the service rate as a function of the number in the system can rarely be measured. Consequently, in a typical model of such a system it is assumed that the service rate is constant. Hence, such systems with a single stage are often modeled by GI/GI/c queueing systems with mutually independent arrival and service processes. Then the observed service times are used to find a sample distribution that will represent the distribution of the assumed i.i.d. service times. The purpose of this paper is to explore the effect of this black box queue inference (BBQI) in its ability to predict the performance of the actual system. In this regard, we have shown that when the arrival process is Poisson, if the servers react favorably [unfavorably] to higher work loads (i.e., if the server increases [decreases] the service rate as the number of customers in the system increases) then the BBQI predictions will be pessimistic [optimistic]. This result can be used to identify the server's attitude toward higher work load.

Consider a large number of interacting queues with symmetric interactions. In the asymptotic limit, the interactions between any fixed finite subcollection become negligible, and the overall effect of interactions can be replaced by an empirical rate. The evolution of each queue is given by a time inhomogeneous Markov process. This may be considered a technique for writing dynamic Erlang fixed-point equations. We explore this as a tool to approximate sojourn time distributions.

The Rate Conservation Law (RCL) of Miyazawa [18] is generalized to what we call a General Rate Conservation Law (GRCL) to cover processes of unbounded variation such as Brownian motion and more general Levy processes. The general setup is that of a time-stationary semimartingale Y = [Yt: t ≥ 0], which is allowed to have jumps. From an elementary application of Ito's formula together with the Palm inversion formula, we obtain a law that includes Miya-zawa's RCL as a special case. A variety of applications and connections with the RCL are given. For example, we show that using the GRCL, one can immediately obtain the noted steady-state decomposition results for vacation queueing models, including those obtained by Kella and Whitt [13] for Jump-Levy processes. Other examples include state-dependent diffusion processes such as the Ornstein-Uhlenbeck process.

Known results in random graph theory lead easily to a quantitative result on the number of multiplications needed in a matrix factorization algorithm, under the assumption that non-zero entries are randomly distributed.

This paper deals with two related approximations that were recently proposed for the loss probability in finite-buffer queues. The purpose of the paper is twofold: first, to provide better insight and more theoretical support for both approximations, and second, to show by an experimental study how well both approximations perform. An interesting empirical finding is that in many cases of practical interest the two approximations provide upper and lower bounds on the exact value of the loss probability.

In this paper we describe an application of distributed-event parallel simulation to study the transient behavior of a large non-Markovian network of queues. In particular, we implemented the parallel-prefix-based algorithm of Greenberg, Lubachevsky, and Mitrani [13,14] on the 8,192-processor CM-2 Connection machine and the 16,384-processor MasPar computer to simulate the departure times D(k, n) of the kth customer from the nth queue in a long series of single-server queues. Each queue has unlimited waiting space and uses the first-in first-out discipline. The service times of all the customers at all the queues are i.i.d. with a general distribution, and the system starts out with k customers in the first queue and all other queues empty. Glynn and Whitt [11] established limit theorems for this model, but very little could be said about the limits themselves. The simulation results presented here describe the limits and the quality of the approximations resulting from using the limits for finite k and n. Indeed, the simulations suggest interesting conjectures. For this model speeding up a single long run is far superior to independent replications, because very long runs are required to obtain unbiased estimates of the desired quantities and the variance of the estimator at the end of the run is small. The achieved simulation rate was about 17 billion service completions per hour, which is a speedup by about a factor of 100 compared to simulation on a conventional single-processor machine. This speedup contributed greatly to performing the desired experiments.

We consider queueing networks containing customers and signals that were recently introduced in Gelenbe [4]. Both customers and signals can be exogenous or can be obtained by a Markovian transition of a customer after service. A signal entering a queue forces a customer to move on to another queue according to a Markovian routing rule or to leave the network in batch mode. This synchronized or triggered motion is useful in representing the effect of tokens in Petri-nets, for systems in which customers and work can be instantaneously moved from one queue to the other on the arrival of a signal as well as for other network behaviors that are encountered in parallel computer system modelling. We show that this network has product form stationary solution and establish the non-linear customer flow equations that govern it. Network stability is discussed in this new context.

A repair crew is responsible for the maintenance and operation of N installations. The crew has to perform a collection of preventive maintenance tasks at the various installations. The installations may break down from time to time, generating corrective maintenance requests which have priority over the preventive maintenance tasks. We formulate and analyze this real-world problem as a single-server multi-queue polling model with Globally Gated service discipline and with server interruptions. We derive closed-form expressions for the Laplace-Stieltjes Transform and the first moment of the waiting time distributions of the preventive and corrective maintenance requests at the various installations, and obtain simple and easily implementable static and dynamic rules for optimal operation of the system. We further show that, for the socalled elevator-type polling scheme, mean waiting times of preventive maintenance jobs at all installations are equal.

We consider a single-server retrial queueing system where retrial time is inversely proportional to the number of customers in the system. A necessary and sufficient condition for the stability of the system is found. We obtain the Laplace transform of virtual waiting time and busy period. The transient distribution of the number of customers in the system is also obtained.

In this paper we analyze an asymmetric 2 × 2 buffered switch, fed by two independent Bernoulli input streams. We derive the joint equilibrium distribution of the numbers of messages waiting in the two output buffers. This joint distribution is presented explicitly, without the use of generating functions, in the form of a sum of two alternating series of product-form geometric distributions. The method used is the so-called compensation approach, developed by Adan, Wessels, and Zijm.

We define a notion of regularity ordering among stochastic processes called directionally convex (dcx) ordering and give examples of doubly stochastic Poisson and Markov renewal processes where such ordering is prevalent. Further-more, we show that the class of segmented processes introduced by Chang, Chao, and Pinedo [3] provides a rich set of stochastic processes where the dcx ordering can be commonly encountered. When the input processes to a large class of queueing systems (single stage as well as networks) are dcx ordered, so are the processes associated with these queueing systems. For example, if the input processes to two tandem /M/c1→/M/c2→…→/M/cm queueing systems are dcx ordered, so are the numbers of customers in the systems. The concept of directionally convex functions (Shaked and Shanthikumar [15]) and the notion of multivariate stochastic convexity (Chang, Chao, Pinedo, and Shanthikumar [4]) are employed in our analysis.

In this paper we describe a class of discrete time processes that can be used to model packet arrival streams in packetized communication. Mathematically, (K(t)) can be seen as a discrete time self-exciting point process, as a multitype branching process, or as an epidemic with immigration of infected people. The purpose of this paper is to show that this class of models simultaneously is quite useful and analytically more tractable than is obvious at first glance. It is shown that certain probabilities can reliably be computed using generating function methods, and expressions are given for the second order properties and for the asymptotic index of dispersion.

Past research on polling systems has been quite restricted in the form of the paths followed by the server. This paper formulates a general, continuous model of such paths that includes closed walks on graphs. Customers arrive by a Poisson process and have general service times. The distribution of arrivals over the path is governed by an absolutely continuous, but otherwise arbitrary, distribution. The main results include a characterization of the stationary state distribution and explicit formulas for expected waiting times. The formulas reveal an interesting decomposition of the system into two components: a fluid limit and an M/G/1 queue.

We consider a Markov decision chain with countable state space, finite action sets, and nonnegative costs. Conditions for the average cost optimality inequality to be an equality are derived. This extends work of Cavazos-Cadena [8]. It is shown that an optimal stationary policy must satisfy the optimality equation at all positive recurrent states. Structural results on the chain induced by an optimal stationary policy are derived. The results are employed in two examples to prove that any optimal stationary policy must be of critical number form.

Knockout tournaments are often used in sports (or experiments where preferences are registered by comparisons instead of measurements) to determine the champion of an event. A knockout tournament plan (KTP) for n players is a rooted binary tree with n leaves to be labeled by the n players. Each subtree of two leaves represents a match between the two players labeling the two leaves; the winner of the match then moves on to label the root of the subtree. While there are many KTPs to choose from for a given number of players, in the real world an almost balanced KTP is usually chosen. One reason could be the perception that a balanced KTP is “fair” to the players, in the sense that, given a random labeling of leaves by players, a stronger player has a better chance to win the tournament. Surprisingly, it has been shown that not all KTPs have this property, and it is difficult to prove this property for any general class of KTPs. So far the property has been shown to hold only for balanced KTPs. In this paper we extend it to some classes of almost balanced KTPs.

A Markov decision chain with denumerable state space incurs two types of costs — for example, an operating cost and a holding cost. The objective is to minimize the expected average operating cost, subject to a constraint on the expected average holding cost. We prove the existence of an optimal constrained randomized stationary policy, for which the two stationary policies differ on at most one state. The examples treated are a packet communication system with reject option and a single-server queue with service rate control.

We consider N sites (N ≤ ∞), each of which may be either occupied or unoccupied. Time is discrete, and at each time unit a set of occupied sites may attempt to capture a previously unoccupied site. The attempt will be successful with a probability that depends on the number of sites making the attempt, in which case the new site will also be occupied. A benefit is gained when new sites are occupied, but capture attempts are costly. The problem of optimal occupation is formulated as a Markov decision process in which the admissible actions are occupation strategies and the cost is a function of the strategy and the number of occupied sites. A partial order on the state-action pairs is used to obtain a comparison result for stationary policies and qualitative results concerning monotonicity of the value function for the n-stage problem (n ≤ ∞). The optimal policies are partially characterized when the cost depends on the action only through the total number of occupation attempts made.

Suppose each permutation (πl,…,πn) of ( 1, …, n) has probability 1/n!. The oscillation of (πl; …, πn) is defined as Tn = | πk − πk+1|, where πn+1 = π1. It is proved that (Tn − ETn)/(var Tn)1/2 converges in distribution to N(0,1). The connection between the oscillation and the presortedness measure is also discussed.

In a previous paper, we defined and studied a branching process input stream that can be used to model the organization of packets (in packetized communication) in messages. In this paper we derive a central result on the effect that such streams have on a packet switch (or queue) and further study one particular model (the case of so-called short-range dependence), where the distribution of the number of packets in a buffer can explicitly be found (albeit in the form of a transform). The solution to this particular model suggests an approximation for the average buffer content in the general case.