A double-loop network G(h1, h2) has n nodes represented by the n residues modulo n and 2n links given by i ↦i + h1, i ↦ i + h2, i = 0,1,…,n – 1.We consider the reliability model where each link fails independently with probability p, the nodes always work, and the network fails if it is not strongly connected. There exists no known polynomial time algorithm to compute the reliabilities of general double-loop networks. When p is small, the reliability is dominated by the link connectivity. As all strongly connected double.loop networks have link connectivity exactly 2, a finer measure of reliability is needed. In this paper we give such a measure and show how to use it to obtain the most reliable double-loop networks.

Employing a failure rate approach, we propose a test statistic, , for the classic goodness-of-fit problem. It is then shown that a variation of , obtained by replacing observed variances by expected variances (an unwise change in our point of view), leads to the classical test statistic, x2. We argue that should be better approximated by a chi-square distribution, and thus employing , the true p−values should be closer to the nominal p−values than under x2 Various other comparisons of the two tests are made.

This paper presents a simple and practical approach to solving the equilibrium equations for a class of Markov chains with an infinite number of states. Markov chains arising in queueing and inventory applications often have the property that the state probabilities exhibit a geometric tail behavior. The basic idea of the approach is to reduce the infinite system of linear equations to a finite system using the geometric tail behavior of the equilibrium probabilities. The reduction typically leads to a remarkably small system of linear equations that can be routinely solved by a Gaussian elimination method. An application is given to the single-server queue with scheduled arrivals.

In this paper we present a general framework for stochastic one-machine scheduling problems with zero release times and no partial ordering and review and extend some of the results for nonpreemptive permutation schedules recently obtained for these models.

In this paper we consider one-machine scheduling problems with or without a perfect machine and random processing times and derive among other results elimination criteria for different classes of cost functions.

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.

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.

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).

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.

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.