This paper analyzes a scheduling system where a fixed number of nonpreemptive jobs is to be processed on multiple parallel processors with different processing speeds. Each processor has an exponential processing time distribution and the processors are ordered in ascending order of their mean processing times. Each job has its own deadline that is exponentially distributed with rate ß1, independent of the deadlines of other jobs and also independent of job processing times. A job departs the system as soon as either its processing completes or its deadline occurs. We show that there exists a simple threshold strategy that slochastically minimizes the total delay of all jobs. The policy depends on distributions of processing times and deadlines, but is independent of the rate of deadlines. When the rate of the deadline distribution is 0 (no deadlines), the total delay reduces to the flowtime (the sum of completion times of all jobs). If each job has its own probability of being correctly processed, then an extension of this policy stochastically maximizes the total number of correctly processed, nontardy jobs. We discuss possible generalizations and limitations of this result.

Since the introduction of the concept of coherent systems and the description of the reliability of such systems in terms of the reliabilities of the components, the concept of importance of a component has created a new and fruitful area of research. Two distinct concepts of importance can be found in the literature. We take the view that the importance of a component or a module that is part of a system can be derived directly from the role of the component or the module in the failure of the system. Here again, it is possible that there will be several definitions of role. In this paper we define the role of a module (or component) to be the probability that the module is among all the modules (or components) that failed at the time of system failure. The role of a module depends on the structure of the system in terms of the modules, the structure of the module in terms of its components and the distribution of lifetimes of the components. In this paper we study the role of a module under several structures and distributions for lifetimes. We establish various monotonicity properties and indicate applications of these properties to optimal allocation. Another quantity that describes the nature of the components in sustaining the system is the number of components that fail at the time of the failure of the system. We establish monotonicity properties for the expected number of failed components and also indicate applications to optimal allocation.

A set of stochastic jobs is to be processed on a single machine that is subject to breakdown. All jobs make progress as they are processed in the absence of machine breakdowns. However, breakdowns cause setbacks to (possibly) all jobs in the system, except those that have already been completed. With machines subject only to fairly mild restrictions on this “damage” process, we demonstrate the existence of a nonpreemptive policy that is optimal in the class of all preemptive ones.

Generalized semi-Markov processes and stochastic Petri nets provide building blocks for specification of discrete event system simulations on a finite or countable state space. The two formal systems differ, however, in the event scheduling (clock-setting) mechanism, the state transition mechanism, and the form of the state space. We have shown previously that stochastic Petri nets have at least the modeling power of generalized semi-Markov processes. In this paper we show that stochastic Petri nets and generalized semi-Markov processes, in fact, have the same modeling power. Combining this result with known results for generalized semi-Markov processes, we also obtain conditions for time-average convergence and convergence in distribution along with a central limit theorem for the marking process of a stochastic Petri net.

Suppose we have a single asset that we would like to sell. As time goes by, independent and identically distributed offers with a common known distribution F are given to us. At any given moment, we may either accept the current offer or reject it, thereby losing it forever. The rate at which offers arrive follows a nonhomogeneous Poisson process whose instantaneous intensity is under our control, using advertizing in a manner to be described. Our objective is, roughly, that of maximizing the total discounted expected reward composed of the offer we decide to accept, minus the total advertizing costs.

This paper considers scheduling n jobs on one machine to minimize the expected weighted flowtime and the number of late jobs. The processing times of the jobs are independent random variables. The machine is subject to failure and repair where the uptimes are exponentially distributed. We find the optimal policies for the preemptive repeat model.

Probabilistic influence diagrams are a useful stochastic modeling tool. To calculate probabilities of interest relative to a probabilistic influence diagram efficiently, it will be helpful for us to use an associated decomposable-directed graph. We first explore and discuss some graph-theoretic and conditional independence properties of decomposable probabilistic influence diagrams. These properties are helpful in providing an efficient algorithm for obtaining a posterior decomposable probabilistic influence diagram given the state of one or more observed nodes. The connection between Shachter's “sequential creation of conditionally barren nodes” concept and Lauritzen and Spiegeihalter's “moralization and triangulation” algorithm for calculating probabilities relative to a probabilistic influence diagram is made explicit. We also discuss how to use wisely the concepts of “sequential creation of conditionally barren nodes” and “merging nodes” together with the graph-theoretic properties of decomposable directed graphs to compute probabilities relative to probabilistic influence diagrams.

This paper models primary computer storage in the context of a general (GI/GI/l) queueing system. Queued items are described by sizes, or storage requirements, as well as by arrival and service times; the sum of the sizes of the items in the system is the occupied storage. Capacity constraints are represented by two different protocols for determining whether an arriving item is admitted to the system: (1) an item is accepted if and only if at its arrival time the currently occupied storage does not exceed a given constant C > 0, and (2) an item is accepted if and only if at its arrival time the occupied storage is at most C, and the occupied storage plus the item's size is at most C(l + ε) for some given ε > 0. We prove for both systems that in heavy traffic the occupied storage, suitably normalized, converges weakly to reflected Brownian motion with boundaries at 0 and at C. A distinctive feature of the proof is the characterization of reflected Brownian motion as a limit of unrestricted penalized processes.

These results make more plausible an earlier conjecture of the authors, i.e., that one obtains the same heavy traffic limit when the admission rule is: accept an item if and only if at its arrival time the occupied storage plus the item's size is no greater than C.

Suppose a discrete time Markov process is simulated so as to estimate p, the probability that it enters the set of states A before it enters the set of states B, for disjoint sets A and B. It is shown that the total hazard, which is an unbiased estimator of p, has a variance that is bounded above by p(2 – p).

An approximation scheme for evaluating Wiener integrals by simulating Brownian motion is studied. The rate of convergence and numerical results are given, including an application to the heat equation by using the Feynman-Kac formula.

Two multivariate aging classes described by Johnson and Kotz [7] and Zahedi [11] and known as vector multivariate increasing/decreasing hazard rate (VMIHR/VMDHR) class and decreasing/increasing multivariate mean remaining life of type 2 (DMMRL/IMMRL-2) class, respectively, as well as componentwise NBUE/NWUE class, are considered. The chain of implications between these classes and some characterizing properties of them with regard to the equilibrium distribution corresponding to a multivariate distribution function and concave (convex) transformation of the residual random vector have been established. The “closure under mixture’ property of the first two classes are also studied.

In this paper we consider stochastic flow-shop scheduling with reference to certain lateness-related performance measures. We show that for various assumptions on the distribution of job-processing times of a flow shop, certain scheduling policies following the stochastic analogy of the Earliest Due Date (EDD) rule yield optimal results.

A simple method of calculating Stieltjes integrals is proposed. The method is essentially the two-point (trapezoidal) rule from numerical analysis. Two theorems yielding error bounds are given. When error requirements are modest (two or three significant decimal places) the method is fast and inexpensive. Examples are given solving the Renewal equation from reliability theory. A program for an HP-41C hand calculator is given, which solves the renewal equation.

Efficiently computable bounds are developed for the time to first failure in a communications network with renewable links. The bounds approximate a network with bidirectional or unidirectional links by acyclic networks with unidirectional links.

Tijms H.C. and Van Ommeren J.C.W. (1989), Asymptotic Analysis for Buffer Behavior in Communication Systems, Probability in the Engineering and Informational Sciences, 3, 1–12.

This paper discusses an optimal dynamic policy for a queueing system with M servers, no waiting room, and two types of customers. Customer types differ with respect to the reward that is paid on commencement of service, but service times are exponentially distributed with the same mean for both types of customers. The arrival stream of one customer type is generated by a Poisson process, and the other customer type arrives according to the overflow process of an M/M/m/m queue. The objective is to determine a policy for admitting customers to maximize the expected long-run average reward.

By posing the problem in the framework of Markov decision processes and exploiting properties of submodular functions, the optimal policy is shown to be a “generalized trunk reservation policy”; in other words, the optimal policy accepts higher-paying customers whenever possible and accepts lower-paying customers only if fewer than c1 servers are busy, where i is the number of busy servers in the overflow queue. Computational issues are also discussed. More specifically, approximations of the overflow process by an interrupted Poisson process and a Poisson process are investigated.