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.

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.

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.

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.

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.

The asymptotic probability of buffer overflow for a queueing system with a Markov fluid input and deterministic service rate is derived by way of large deviation theory. The equations characterizing the deviant behavior are presented and examples are given for which closed-form solutions may be obtained. An independence result extends the analysis to cases where the input is an aggregate of independent Markov fluids.

We consider an inventory system with compound Poisson demands replenished by discrete production of units on a single-server facility. This facility may start a vacation at any production completion epoch; at the completion of a vacation the inventory level is inspected to decide whether or not to resume production. Unit production and vacation times are independent and identically distributed with general distributions. Under an (s, S) policy, production is terminated when the inventory level reaches a critical level S, and production is resumed when the inventory level, upon completion of a vacation, is at or below a prespecified value s. In this paper we prove that an (s, S) policy is optimal among all possible policies. We also derive a highly efficient algorithm for the determination and evaluation of an optimal (s, S) policy.

Tasks belonging to N priority classes arrive for processing in a single or multiserver facility. If the processing does not begin by a certain time (deterministic or random), the task is lost and a cost is incurred. We determine properties of dynamic, nonidling, nonpreemptive strategies that minimize an infinite horizon expected cost.

In this paper the objective is to find a job sequence that minimizes, stochastically or in expectation, the sum of the total weighted job earliness and the total weighted job tardiness on one machine, when the job processing times are independent and identically distributed random variables. We first derive results for the case in which the jobs share a common, random due date. We then obtain results when the job due dates are distinct, independent random variables.