Some limiting distributions associated with sequences of multinomial trials

A series of independent trials is considered in which one of k ≥ 2 mutually exclusive and exhaustive outcomes occurs at each trial. The series terminates when m outcomes of any one type have occurred. The limiting distribution (as m → ∞) of the number of trials performed until termination is found with particular attention to the situation where a Dirichlet distribution is assigned to the k vector of probabilities for each outcome. Applications to series of races involving k runners and to spares problems in reliability modeling are discussed. The problem of selecting a stopping rule so that the probability of the series terminating on outcome i is k^?1 (i.e., a “fair” competition) is also studied. Two generalizations of the original asymptotic problem are addressed.     

Solving quadratic assignment problems with rectangular distances and integer programming

The problem considered involves the assignment of n facilities to n specified locations. Each facility has a given nonnegative flow from each of the other facilities. The objective is to minimize the sum of transportation costs. Assume these n locations are given as points on a two-dimensional plane and transportation costs are proportional to weighted rectangular distances. Then the problem is formulated as a binary mixed integer program. The number of integer variables (all binary) involved equals the number of facilities squared. Without increasing the number of integer variables, the formulation is extended to include “site costs” Computational results of the formulation are presented.     

On the first time a separately maintained parallel system has been down for a fixed time

Consider a system consisting of n separately maintained independent components where the components alternate between intervals in which they are “up” and in which they are “down”. When the i^th component goes up [down] then, independent of the past, it remains up [down] for a random length of time, having distribution F_i[G_i], and then goes down [up]. We say that component i is failed at time t if it has been “down” at all time points s ?[t-A.t]: otherwise it is said to be working. Thus, a component is failed if it is down and has been down for the previous A time units. Assuming that all components initially start “up,” let T denote the first time they are all failed, at which point we say the system is failed. We obtain the moment-generating function of T when n = l, for general F and G, thus generalizing previous results which assumed that at least one of these distributions be exponential. In addition, we present a condition under which T is an NBU (new better than used) random variable. Finally we assume that all the up and down distributions F_i and G_i i = l,….n, are exponential, and we obtain an exact expression for E(T) for general n; in addition we obtain bounds for all higher moments of T by showing that T is NBU.     

Quadratic forms in spherical random variables: Generalized noncentral x2 distribution

Let X denote a random vector with a spherically symmetric distribution. The density of U = X'X, called a “generalized chi-square,” is derived for the noncentral case, when μ = E(X) ≠ 0. Explicit series representations are found in certain special cases including the “generalized spherical gamma,” the “generalized” Laplace and the Pearson type VII distributions. A simple geometrical representation of U is shown to be useful in generating random U variates. Expressions for moments and characteristic functions are also given. These densities occur in offset hitting probabilities.     

A note on a stochastic production-maximizing transportation problem

A stochastic production-maximizing problem with transportation constraints is considered where the production rates, R_ij, of man i — job j combinations are random variables rather than constants. It is shown that for the family of Weibull distributions (of which the Exponential is a special case) with scale parameters λ_ij and shape parameter β, the plan that maximizes the expected rate of the entire line is obtained by solving a deterministic fixed charge transportation problem with no linear costs and with “set-up” cost matrix ‖λ_ij‖.     

Asymptotic joint normality of an increasing number of multivariate order statistics and associated cell frequencies

Take n independent identically distributed (IID) observations from a continuous r-variate population, and choose some order statistics from each of the r variates. These order statistics are used to construct a grid in r-dimensional space. Under certain conditions, it is shown that as n increases we can choose an increasing number of order statistics in such a way that the asymptotic joint distribution of the chosen order statistics and of the frequencies of sample points falling in the cells of the grid can be assumed to be a normal distribution. An application to testing independence of random variables is given.     

Optimal replacement of parts having observable correlated stages of deterioration

A single component system is assumed to progress through a finite number of increasingly bad levels of deterioration. The system with level i (0 ≤ i ≤ n) starts in state 0 when new, and is definitely replaced upon reaching the worthless state n. It is assumed that the transition times are directly monitored and the admissible class of strategies allows substitution of a new component only at such transition times. The durations in various deterioration levels are dependent random variables with exponential marginal distributions and a particularly convenient joint distribution. Strategies are chosen to maximize the average rewards per unit time. For some reward functions (with the reward rate depending on the state and the duration in this state) the knowledge of previous state duration provides useful information about the rate of deterioration.     

Dynamic signatures and their use in comparing the reliability of new and used systems

The signature of a system with independent and identically distributed (i.i.d.) component lifetimes is a vector whose ith element is the probability that the ith component failure is fatal to the system. System signatures have been found to be quite useful tools in the study and comparison of engineered systems. In this article, the theory of system signatures is extended to versions of signatures applicable in dynamic reliability settings. It is shown that, when a working used system is inspected at time t and it is noted that precisely k failures have occurred, the vector s [0,1]^n‐k whose jth element is the probability that the (k + j)th component failure is fatal to the system, for j = 1,2,2026;,n ‐ k, is a distribution‐free measure of the design of the residual system. Next, known representation and preservation theorems for system signatures are generalized to dynamic versions. Two additional applications of dynamic signatures are studied in detail. The well‐known “new better than used” (NBU) property of aging systems is extended to a uniform (UNBU) version, which compares systems when new and when used, conditional on the known number of failures. Sufficient conditions are given for a system to have the UNBU property. The application of dynamic signatures to the engineering practice of “burn‐in” is also treated. Specifically, we consider the comparison of new systems with working used systems burned‐in to a given ordered component failure time. In a reliability economics framework, we illustrate how one might compare a new system to one successfully burned‐in to the kth component failure, and we identify circumstances in which burn‐in is inferior (or is superior) to the fielding of a new system. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

Assembly of systems having maximum reliability

The first problem considered in this paper is concerned with the assembly of independent components into parallel systems so as to maximize the expected number of systems that perform satisfactorily. Associated with each component is a probability of it performing successfully. It is shown that an optimal assembly is obtained if the reliability of each assembled system can be made equal. If such equality is not attainable, then bounds are given so that the maximum expected number of systems that perform satisfactorily will lie within these stated bounds; the bounds being a function of an arbitrarily chosen assembly. An improvement algorithm is also presented. A second problem treated is concerned with the optimal design of a system. Instead of assembling given units, there is an opportunity to “control” their quality, i.e., the manufacturer is able to fix the probability, p, of a unit performing successfully. However, his resources, are limited so that a constraint is imposed on these probabilities. For (1) series systems, (2) parallel systems, and (3) k out of n systems, results are obtained for finding the optimal p's which maximize the reliability of a single system, and which maximize the expected number of systems that perform satisfactorily out of a total assembly of J systems.     

On optimal aiming to hit a linear target

Typically weapon systems have an inherent systematic error and a random error for each round, centered around its mean point of impact. The systematic error is common to all aimings. Assume such a system for which there is a preassigned amount of ammunition of n rounds to engage a given target simultaneously, and which is capable of administering their fire with individual aiming points (allowing “offsets”). The objective is to determine the best aiming points for the system so as to maximize the probability of hitting the target by at least one of the n rounds. In this paper we focus on the special case where the target is linear (one‐dimensional) and there are no random errors. We prove that as long as the aiming error is symmetrically distributed and possesses one mode at zero, the optimal aiming is independent of the particular error distribution, and we specify the optimal aiming points. Possible extensions are further discussed, as well as civilian applications in manufacturing, radio‐electronics, and detection. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 323–333, 1999     

Optimal arrangement of systems

To location L_i we are to allocate a “generator” and n_i “machines” for i = 1, …,k, where n₁ … n₁ ≧ … ≧ n_k. Although the generators and machines function independently of one another, a machine is operable only if it and the generator at its location are functioning. The problem we consider is that of finding the arrangement or allocation optimizing the number of operable machines. We show that if the objective is to maximize the expected number of operable machines at some future time, then it is best to allocate the best generator and the n₁ best machines to location L₁, the second-best generator and the n₂-next-best machines to location L₂, etc. However, this arrangement is not always stochastically optimal. For the case of two generators we give a necessary and sufficient condition that this arrangement is stochastically best, and illustrate the result with several examples.     

Bolstering components for maximizing system lifetime

This article considers the problem of which component should be “bolstered” or “improved” in order to stochastically maximize the lifetime of a parallel system, series system, or in general, k-out-of-n system. Various ways of bolstering including active redundance, standby redundancy, and burn-in are studied. Also the method of reducing working temperature or stress level according to Arrhenius models is investigated. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 497–509, 1998     

The normal approximation to the multinomial with an increasing number of classes

For a fixed number of classes and the number of trials increasing, the approach of the multinomial cumulative distribution function to a normal cumulative distribution function is familiar. In this paper we allow the number of classes to increase as the number of trials increases, and show that under certain circumstances the probabilities assigned to arbitrary regions by the multinomial distribution are all close to the probabilities assigned by the distribution of “rounded off” normal random variables. As the number of trials increases, the amount rounded off approaches zero. The result can be used to study the asymptotic distribution of functions of multinomial random variables.     

Asymptotic distribution of some multivariate “success run” renewal processes,applied to a 2-i.i.d. unit repairable system

If the probability of “failure” in a multivariate renewal process of the “success run” type is very small, then if certain conditions are imposed on the components of the renewals, the joint distribution of their total durations is approximately exponential with all mass along one line. This result is applied to a 2-i.i.d. unit repairable system of the “1 out of 2:G, Cold Standby” type.     

A note on a paper by W. Szwarc

In this note the authors call for a change of the optimality criteria given by Theorem 3 in section 5 of the paper of W. Szwarc “On Some Sequencing Problems” in NRLQ Vol. 15, No. 2 [2]. Further, two cases of the three machine problem, namely, (i) ≦ and (ii) ≦ are considered, and procedures for obtaining optimal sequences in these cases are given. In these cases the three-machine problem is solved by solving n (the number of jobs) two-machine problems.     

Confidence bounds and propagation of uncertainties in system availability and reliability computations

This paper develops bounds on the uncertainties in system availabilities or reliabilities which have been computed from structural (series, parallel, etc.) relations among uncertain subsystem availabilities or reliabilities. It is assumed that the highly available (reliable) subsystems have been tested or simulated to determine their unavailabilities (unreliabilities) to within some small percentages of uncertainty. It is shown that series, parallel and r out of n structures which are nominally highly available will have unavailability uncertainties whose percentages errors are of the same order as the subsystem uncertainties. Thus overall system analysis errors, even for large systems, are of the same order of magnitude as the uncertainties in the component probabilities. Both systematic (bias type) uncertainties and independent random uncertainties are considered.     

Flowshop/no-idle or no-wait scheduling to minimize the sum of completion times

This paper deals with flowshop/sum of completion times scheduling problems, working under a “no-idle” or a “no-wait” constraint, the former prescribes for the machines to work continuously without idle intervals and the latter for the jobs to be processed continuously without waiting times between consecutive machines. Under either of the constraints the problem is unary NP-Complete for two machines. We prove some properties of the optimal schedule for n/2/F, no-idle/σC_i. For n/m/P, no-idle/σC_i, and n/m/P, no-wait/σC_i, with an increasing or decreasing series of dominating machines, we prove theorems that are the basis for polynomial bounded algorithms. All theorems are demonstrated numerically.     

Testing fit with nuisance location and scale parameters

For each n, X₁(n),…, X_n(n) are independent and identically distributed random variables, each with cumulative distribution function F(x) which is known to be absolutely continuous but is otherwise unknown. The problem is to test the hypothesis that \documentclass{article}\pagestyle{empty}\begin{document}$ F(x) = G\left( {{\textstyle{{x - \theta _1 } \over {\theta _2 }}}} \right) $\end{document}, where the cumulative distribution function G_x is completely specified and satisfies certain regularity conditions, and the parameters θ₁, θ₂ are unknown and unspecified, except that the scale parameter θ₂, is positive. Y₁ (n) ≦ Y₂ (n) ≦ … ≦ Y_n (n)are the ordered values of X₁(n),…, X_n(n). A test based on a certain subset of {Y_i(n)} is proposed, is shown to have asymptotically a normal distribution when the hypothesis is true, and is shown to be consistent against all alternatives satisfying a mild regularity condition.     

An approximate dynamic programing approach to the development of heuristics for the scheduling of impatient jobs in a clearing system

A single server is faced with a collection of jobs of varying duration and urgency. Each job has a random lifetime during which it is available for nonpreemptive service. Should a job's lifetime expire before its service begins then it is lost from the system unserved. The goal is to schedule the jobs for service to maximize the expected number served to completion. Two heuristics have been proposed in the literature. One (labeled π^S) operates a static priority among the job classes and works well in a “no premature job loss” limit, whereas the second (π^M) is a myopic heuristic which works well when lifetimes are short. Both can exhibit poor performance for problems at some distance from the regimes for which they were designed. We develop a robustly good heuristic by an approximative approach to the application of a policy improvement step to the asymptotically optimal heuristic π^S, in which we use a fluid model to obtain an approximation for the value function of π^S. The performance of the proposed heuristic is investigated in an extensive numerical study. © 2010 Wiley Periodicals, Inc. Naval Research Logistics 2010     

On the uncapacitated K‐commodity network design problem with zero flow‐costs

Extending Sastry's result on the uncapacitated two‐commodity network design problem, we completely characterize the optimal solution of the uncapacitated K‐commodity network design problem with zero flow costs for the case when K = 3. By solving a set of shortest‐path problems on related graphs, we show that the optimal solutions can be found in O(n³) time when K = 3, where n is the number of nodes in the network. The algorithm depends on identifying a list of “basic patterns”; the number of basic patterns grows exponentially with K. We also show that the uncapacitated K‐commodity network design problem can be solved in O(n³) time for general K if K is fixed; otherwise, the time for solving the problem is exponential. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004