Covariance of weibull order statistics

Let X₁ < X₂ <… < X_n denote an ordered sample of size n from a Weibull population with cdf F(x) = 1 - exp (?x^p), x > 0. Formulae for computing Cov (X_i, X_j) are well known, but they are difficult to use in practice. A simple approximation to Cov(X_i, X_j) is presented here, and its accuracy is discussed.     

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.     

Characterizations of the exponential distribution by higher-order gap

Suppose X₁,X₂, ?,X_n is a random sample of size n from a continuous distribution function F(x) and let X_1,n, ≦ X_2,n ≦ ? ≦ X_n,n be the corresponding order statistics. We define the jth-order gap g_i,j as g_i,j = X_i+j,n ? X_i,n, 1 ≦ i < n, 1 ≦ j ≦ n ? i. In this article characterizations of the exponential distribution are given by considering the distributional properties of g_k,n-k, 1 ≦ k ≦ n.     

Scheduling deteriorating jobs to minimize makespan

We consider a single-machine problem of scheduling n independent jobs to minimize makespan, in which the processing time of job J_j grows by w_j with each time unit its start is delayed beyond a given common critical date d. This processing time is p_j if J_j starts by d. We show that this problem is NP-hard, give a pseudopolynomial algorithm that runs in time and O(nd) space, and develop a branch-and-bound algorithm that solves instances with up to 100 jobs in a reasonable amount of time. We also introduce the case of bounded deterioration, where the processing time of a job grows no further if the job starts after a common maximum deterioration date D > d. For this case, we give two pseudopolynomial time algorithms: one runs in O(n²d(D − d) time and O(nd(D − d)) space, the other runs in p_j)²) time and p_j) space. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 511–523, 1998     

Confidence intervals for ranked means

Suppose that observations from populations π₁, …, π_k (k ≥ 1) are normally distributed with unknown means μ₁., μ_k, respectively, and a common known variance σ². Let μ_[1] μ … ≤ μ_[k] denote the ranked means. We take n independent observations from each population, denote the sample mean of the n observation from π₁ by X _i (i = 1, …, k), and define the ranked sample means X _[1] ≤ … ≤ X _[k]. The problem of confidence interval estimation of μ₍₁₎, …,μ_[k] is stated and related to previous work (Section 1). The following results are obtained (Section 2). For i = 1, …, k and any γ(0 < γ < 1) an upper confidence interval for μ_[i] with minimal probability of coverage γ is (? ∞, X _[i]+ h) with h = (σ/n^1/2) Φ^?1(γ^1/k-i+1), where Φ(·) is the standard normal cdf. A lower confidence interval for μ_[i] with minimal probability of coverage γ is (X _i[i] – g, + ∞) with g = (σ/n^1/2) Φ^?1(γ^1/i). For the upper confidence interval on μ_[i] the maximal probability of coverage is 1– [1 – γ^1/k-i+1]ⁱ, while for the lower confidence interval on μ_[i] the maximal probability of coverage is 1–[1– γ^1/i] ^k-i+¹. Thus the maximal overprotection can always be calculated. The overprotection is tabled for k = 2, 3. These results extend to certain translation parameter families. It is proven that, under a bounded completeness condition, a monotone upper confidence interval h(X ₁, …, X _k) for μ_[i] with probability of coverage γ(0 < γ < 1) for all μ = (μ_[1], …,μ_[k]), does not exist.     

Readiness and the optimal redeployment of resources

This paper considers the problem of the optimal redeployment of a resource among different geographical locations. Initially, it is assumed that at each location i, i = 1,…, n, the level of availability of the resource is given by a₁ ≧ 0. At time t > 0, requirements R_f(t) ≧ 0 are imposed on each location which, in general, will differ from the a₁. The resource can be transported from any one location to any other in magnitudes which will depend on t and the distance between these locations. It is assumed that ΣR_j > Σa_t The objective function consideis, in addition to transportation costs incurred by reallocation, the degree to which the resource availabilities after redeployment differ from the requirements. We shall associate the unavailabilities at the locations with the unreadiness of the system and discuss the optimal redeployment in terms of the minimization of the following functional forms: \documentclass{article}\pagestyle{empty}\begin{document}$ \sum\limits_{j = 1}^n {kj(Rj - yj) + } $\end{document} transportation costs, Max \documentclass{article}\pagestyle{empty}\begin{document}$ \mathop {Max}\limits_j \,[kj(Rj - yj)] + $\end{document} transportation costs, and \documentclass{article}\pagestyle{empty}\begin{document}$ \sum\limits_{j = 1}^n {kj(Rj - yj)^2 + } $\end{document} transportation costs. The variables y_j represent the final amount of the resource available at location j. No benefits are assumed to accrue at any location if y_j > R_j. A numerical three location example is given and solved for the linear objective.     

A diffusion model for the control of a multipurpose reservoir system

This paper develops a methodology for optimizing operation of a multipurpose reservoir with a finite capacity V. The input of water into the reservoir is a Wiener process with positive drift. There are n purposes for which water is demanded. Water may be released from the reservoir at any rate, and the release rate can be increased or decreased instantaneously with zero cost. In addition to the reservoir, a supplementary source of water can supply an unlimited amount of water demanded during any period of time. There is a cost of C_i dollars per unit of demand supplied by the supplementary source to the i^th purpose (i = 1, 2, …, n). At any time, the demand rate R_i associated with the i^th purpose (i = 1, 2, …, n) must be supplied. A controller must continually decide the amount of water to be supplied by the reservoir for each purpose, while the remaining demand will be supplied through the supplementary source with the appropriate costs. We consider the problem of specifying an output policy which minimizes the long run average cost per unit time.     

Finite Markov chain models skip-free in one direction

Finite Markov processes are considered, with bidimensional state space, such that transitions from state (n, i) to state (m, j) are possible only if m ≤ n + 1. The analysis leads to efficient computational algorithms, to determine the stationary probability distribution, and moments of first passage times.     

Scheduling with earliest start and due date constraints on multiple machines

We consider the scheduling of n jobs on m identical machines when the jobs become available for processing at ready times a_i, a_i, ? 0, require d_i time units for processing and must be completed by times b_i for i = 1, 2, … n. The objective chosen is that of minimizing the total elapsed time to complete all jobs subject to the ready time and due date constraints, preemption is not allowed. We present a multi-stage solution algorithm for this problem that is based on an implicit enumeration procedure and also uses the labelling type algorithm which solves the problem when preemption is allowed.     

Decomposition algorithms for minimal cut problems

Consider a network G(N. A) with n nodes, where node 1 designates its source node and node n designates its sink node. The cuts (Z_i, =), i= 1…, n - 1 are called one-node cuts if 1 ? Z_i,. n q Z_i, Z₁-_? {1}, Z_i ? Z_i+1 and Z_i and Z_i+l differ by only one node. It is shown that these one-node cuts decompose G into 1 m n/2 subnetworks with known minimal cuts. Under certain circumstances, the proposed one-node decomposition can produce a minimal cut for G in 0(n² ) machine operations. It is also shown that, under certain conditions, one-node cuts produce no decomposition. An alternative procedure is also introduced to overcome this situation. It is shown that this alternative procedure has the computational complexity of 0(n³).     

An algorithm for separable piecewise convex programming problems

We present a branch and bound algorithm to solve mathematical programming problems of the form: Find x =|(x₁,…x_n) to minimize Σ?_i0(x₁) subject to x?G, l≦x≦L and Σ?_i0(x₁)≦0, j=1,…,m. With l=(l₁,…,l_n) and L=(L₁,…,L_n), each ?_ij is assumed to be lower aemicontinuous and piecewise convex on the finite interval [l_i.L_i]. G is assumed to be a closed convex set. The algorithm solves a finite sequence of convex programming problems; these correspond to successive partitions of the set C={x|l ≦ x ≦L} on the bahis of the piecewise convexity of the problem functions ?_ij. Computational considerations are discussed, and an illustrative example is presented.     

Distribution of sample correlation coefficients

Let (Y, X_l,…, X_K) be a random vector distributed according to a multivariate normal distribution where X_l,…, X_K are considered as predictor variables and y is the predictand. Let r_i, and R_i denote the population and sample correlation coefficients, respectively, between Y and X_i. The population correlation coefficient r_i is a measure of the predictive power of X_i. The author has derived the joint distribution of R_l,…, R_K and its asymptotic property. The given result is useful in the problem of selecting the most important predictor variable corresponding to the largest absolute value of r_i.     

IFR results for repairable systems

Consider a k-out-of-n system with independent repairable components. Assume that the repair and failure distributions are exponential with parameters {μ₁, ?,μ_n} and {λ₁, ?,λ_n}, respectively. In this article we show that if λ_i – μ_i = Δ for all i then the life distribution of the system is increasing failure rate (IFR).     

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.     

Estimation of ordered parameters from k stochastically increasing distributions

There are given k (? 2) univariate cumulative distribution functions (c.d.f.'s) G(x; θ_i) indexed by a real-valued parameter θ_i, i=1,…, k. Assume that G(x; θ_i) is stochastically increasing in θ_i. In this paper interval estimation on the i^th smallest of the θ's and related topics are studied. Applications are considered for location parameter, normal variance, binomial parameter, and Poisson parameter.     

A minmax search for the critical level of a system: The asymmetric case

We consider a system composed of k components, each of which is subject to failure if temperature is above a critical level. The failure of one component causes the failure of the system as a whole (a serially connected system). If z_i is the critical temperature of the ith component then z^* = min{z_i: i = 1,2,…, k} is the critical level of the system. The components may be tested individually at different temperature levels, if the temperature is below the critical level the cost is $1, otherwise the test is destructive and the cost is m > 1 dollars. The purpose of this article is to construct, under a budgetary constraint, an efficient (in a minmax sense) testing procedure which will locate the critical level of the system with maximal accuracy.     

The asymptotic joint distribution of the state occupancy times in an alternating renewal process

An alternating renewal process starts at time zero and visits states 1,2,…,r, 1,2, …,r 1,2, …,r, … in sucession. The time spent in state i during any cycle has cumulative distribution function F_i, and the sojourn times in each state are mutually independent, positive and nondegenerate random variables. In the fixed time interval [0,T], let U_i(T) denote the total amount of time spent in state i. In this note, a central limit theorem is proved for the random vector (U_i(T), 1 ≤ i ≤ r) (properly normed and centered) as T → ∞.     

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     

Selecting review periods for a coordinated multi‐item inventory model with staggered deliveries

Consider an N‐item, periodic review, infinite‐horizon, undiscounted, inventory model with stochastic demands, proportional holding and shortage costs, and full backlogging. For 1 ≤ j ≤ N, orders for item j can arrive in every period, and the cost of receiving them is negligible (as in a JIT setting). Every T_j periods, one reviews the current stock level of item j and decides on deliveries for each of the next T_j periods, thus incurring an item‐by‐item fixed cost k_j. There is also a joint fixed cost whenever any item is reviewed. The problem is to find review periods T₁, T₂, …, T_N and an ordering policy satisfying the average cost criterion. The current article builds on earlier results for the single‐item case. We prove an optimal policy exists, give conditions where it has a simple form, and develop a branch and bound algorithm for its computation. We also provide two heuristic policies with O(N) computational requirements. Computational experiments indicate that the branch and bound algorithm can handle normal demand problems with N ≤ 10 and that both heuristics do well for a wide variety of problems with N ranging from 2 to 200; moreover, the performance of our heuristics seems insensitive to N. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48:430–449, 2001     

Deterministic and stochastic scheduling with teamwork tasks

We study a class of new scheduling problems which involve types of teamwork tasks. Each teamwork task consists of several components, and requires a team of processors to complete, with each team member to process a particular component of the task. Once the processor completes its work on the task, it will be available immediately to work on the next task regardless of whether the other components of the last task have been completed or not. Thus, the processors in a team neither have to start, nor have to finish, at the same time as they process a task. A task is completed only when all of its components have been processed. The problem is to find an optimal schedule to process all tasks, under a given objective measure. We consider both deterministic and stochastic models. For the deterministic model, we find that the optimal schedule exhibits the pattern that all processors must adopt the same sequence to process the tasks, even under a general objective function GC = F(f₁(C₁), f₂(C₂), … , f_n(C_n)), where f_i(C_i) is a general, nondecreasing function of the completion time C_i of task i. We show that the optimal sequence to minimize the maximum cost MC = max f_i(C_i) can be derived by a simple rule if there exists an order f₁(t) ≤ … ≤ f_n(t) for all t between the functions {f_i(t)}. We further show that the optimal sequence to minimize the total cost TC = ∑ f_i(C_i) can be constructed by a dynamic programming algorithm. For the stochastic model, we study three optimization criteria: (A) almost sure minimization; (B) stochastic ordering; and (C) expected cost minimization. For criterion (A), we show that the results for the corresponding deterministic model can be easily generalized. However, stochastic problems with criteria (B) and (C) become quite difficult. Conditions under which the optimal solutions can be found for these two criteria are derived. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004