We wish to schedule heterogeneous jobs on a single machine to stochastically maximize the number of jobs that are correctly completed before a random due date. Jobs arrive according to an arbitrary arrival process. Job i has probability ci, that it will be correctly completed, and a processing time that has distribution Fi. Jobs that are incorrectly processed cannot be reprocessed, and jobs that are not completed by the due date are assumed to be incorrectly processed. The machine is subject to breakdowns and repairs. Both premptive and non-preemptive policies are considered. We give conditions under which simple index rules are optimal. This generalizes and extends the results of Derman et al. [3], Pinedo and Rammouz [9], and Buyukkoc et al. [2], who derive policies that maximize the expected number of jobs correctly completed by the due date. We also consider policies that stochastically minimize the number of correct job completions. For single class systems, we give conditions under which FCFS (first-come-first-served) or LAST (least-attained-service-time) service disciplines stochastically minimize or maximize the number in the system.

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.

Via order statistics we analyze the average length of all separators in random Prefix B-trees. From this result we draw some conclusions and conjectures concerning the average overall storage of random Prefix B-trees.

It is known that the lifetime of a k−out−of−n system has increasing failure rate (IFR) if all of its components have independent and identically distributed IFR lifetimes. Derman, Lieberman, and Ross raised the same question for consecutive−k−out−of−n systems. But the scarcity of results gives no clue as to whether most of such systems have IFR's. In this paper, we completely solve the k = 2 and k = 3 cases. We prove that these systems, with a handful of exceptions, do not have IFR's (contradicting the result of Derman, Lieberman, and Ross that a consecutive-2-out-of-n cycle has IFR for any n). Our result suggests the conjecture that for every fixed k there exists nk such that for every n ≧ nk a consecutive-k−out−of−n system does not have IFR. We also prove that for every fixed d there exists nd large enough such that for all n ≧ nd a consecuive.(n – d)−out−of−n system has IFR. In particular, if the system is a line, then nd = 3d +1 for d ≧ 1.

The following corrections for “A Globally Gated Polling System with Server Interruptions, and Applications to the Repairman Problem” by O.J. Boxma, J.A. Weststrate, and U. Yechiali, which appeared in Volume 7, Number 2, of Probability in the Engineering and Informational Sciences, missed the press date.

p. 192, (3.3): Xi should be Xi

p. 194, (3.12):should be

p. 195, (4.1): N should be n in the five summations over n (15x)

p. 195, (4.2): should be moved to the next line (after the multiplication sign)

p. 195, below (4.3): Add: so that EY1m = EXm = λmEC

p. 195, (4.4): Add: for m < n

p. 195, I. –3: Add: for m < n

p. 196, (4.5): Add: for m < n

p. 196, I. 5: Add: Again cov(Xm, Xn) = λm λn var(C), independent of the server interruption process.

p. 196, (4.8): m ≤ n should be m < n

p. 197, 1st formula: [λi should be

p. 199, I. 6: 5.2 The should be The

p. 199, I. 14: 5.3 The should be The

p. 200, I. 10: [E should be E(

p. 204: The last line of subsection 6.2 should be changed to: Moreover, when sj → 0, the index rules (6.2) and (6.4) approach the well-known cμ rule in both the static and dynamic optimization.

p. 207, I. –1: (to appear) should be: 85–90

p. 208, I. 1: 92 should be 93 (2×)

p. 208, I. 5: (to appear) should be 35: 187–208

We consider the following problem. For a given population of m items, we have to make a decision whether or not the population includes a relatively large cluster of identical items. This decision affects the effectiveness of a subsequent computational process, depending on the actual existence of the cluster and its size. To make a good decision, we use a statistical sample which should indicate the existence of a cluster and find a representative thereof. This paper describes the optimal sampling technique to be used in such a case, given the cost of the sampling and the potential gain in speed of the subsequent process. The optimal fixed sample size is specified, as well as the optimal sequential sampling, along with characterizing the dependence of the cost function on the truncation point.

For the case that the a priori distribution of the cluster proportion is known, we present formulae by which the optimal sampling procedures can be easily calculated. For the common situation in which the a priori distribution is not known, we present, in the case of a fixed sample size, a tight upper bound for the sample size, which is independent of the a priori distribution, and for the case of the sequential sampling, we present an approximately optimal truncation point, which is also independent of the a priori distribution.

The situation described arose in connection with choosing the best sorting method, an application that will be described in full detail. The most interesting practical result is that for our application truncating the sequential procedure at 35 observations, out of a population of 25,000–30,000 items, guarantees that in our sorting application we are always within 2.1% of the optimal cost independently of the a priori distribution.

Simple and insensitive lower and upper bounds are proposed for the call congestion of M/GI/c/n queues. To prove them we establish the general monotonicity property that increasing the waiting room and/or the number of servers in a /GI/c/n queue increases the throughput. An asymptotic result on the number of busy servers is obtained as a consequence of the bounds. Numerical evidence as well as an application to optimal design illustrates the potential usefulness for engineering purposes. The proof is based on a sample path argument.

Frequency measurements by means of zero-crossing-counting device can be disturbed by noise in many different ways, such as fluctuating zero level or extra zero crossings. This paper presents a mathematical theory for analysis of the effect of noise on a zero-crossing counter. Comparisons are made with experiments made on the production of clicks in a zero-crossing-detecting FM receiver.

Al-Osh and Alzaid (1988, Statistical Papers 29: 281–300) introduced a class of Poisson moving-average processes. In this paper, we analyze certain properties of such models. In particular, we show that the model has the property of time reversibility. Regression properties of the model are also given. Furthermore, we determine the asymptotic limit distribution for the sample autocovariance function and establish the asymptotic validity of a bootstrap approximation.

In this paper we consider the problem of finding the optimal order for two servers in series when there is no queue capacity. We show that it is better for the faster server to be first. The strength of this conclusion will depend on the strength of the assumption made about the service distribution. We also find the optimal order for some systems where both servers have the same average service time and different service distributions.

Discretization is a simple, yet powerful tool in obtaining time-dependent probability distribution of continuous-time Markov chains. One of the most commonly used approaches is uniformization. A recent addition to such approaches is an external uniformization technique. In this paper, we briefly review these different approaches, propose some new approaches, and discuss their performances based on theoretical bounds and empirical computational results. A simple method to get lower and upper bounds for first passage time distribution is also proposed.

Let X1, X2,… be i.i.d. random points in R2 with distribution v, and let Ln be the length of the shortest path through X1,…, Xn. The exact almost sure rate of growth of Ln, is obtained under the assumption that v is self-similar in an appropriate sense. This extends a well-known theorem of Beardwood, Halton, and Hammersley.

This paper shows that the equilibrium distribution of a queueing network with batch routing continues to be of product form if a batch that cannot enter its destination — for example, as a consequence of capacity constraints — immediately triggers a new transition that takes up the whole batch.

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.

A two–time scale stochastic approximation algorithm is proposed for simulation-based parametric optimization of hidden Markov models, as an alternative to the traditional approaches to “infinitesimal perturbation analysis.” Its convergence is analyzed, and a queueing example is presented.

This paper is concerned with how coupling can be used to enhance the efficiency of a certain class of terminating simulations, in Markov process settings in which the stationary distribution is known. We are able to theoretically establish that our coupling-based estimator is often more efficient than the naive estimator. In addition, we discuss extensions of our methodology to Markov process settings in which conventional coupling fails and show (for Doeblin chains) that knowledge of the stationary distribution is sometimes unnecessary.

Recent developments in stochastic modeling show that enormous analytical advantages can be gained if a general cumulative distribution function (c.d.f.) can be approximated by generalized hyperexponential distributions. In this paper, we introduce a procedure to explicitly construct such approximations of an arbitrary c.d.f. Although our approach can be used in different types of stochastic models, the main motivation comes from queueing theory in obtaining approximations of the idle-period distribution and other performance measures in GI/G/1 queues.