A branch and bound algorithm for computing optimal replacement policies in consecutive k‐out‐of‐n‐systems

This paper presents a branch and bound algorithm for computing optimal replacement policies in a discrete‐time, infinite‐horizon, dynamic programming model of a binary coherent system with n statistically independent components, and then specializes the algorithm to consecutive k‐out‐of‐n systems. The objective is to minimize the long‐run expected average undiscounted cost per period. (Costs arise when the system fails and when failed components are replaced.) An earlier paper established the optimality of following a critical component policy (CCP), i.e., a policy specified by a critical component set and the rule: Replace a component if and only if it is failed and in the critical component set. Computing an optimal CCP is a optimization problem with n binary variables and a nonlinear objective function. Our branch and bound algorithm for solving this problem has memory storage requirement O(n) for consecutive k‐out‐of‐n systems. Extensive computational experiments on such systems involving over 350,000 test problems with n ranging from 10 to 150 find this algorithm to be effective when n ≤ 40 or k is near n. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 288–302, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10017     

Consecutive k‐within‐m‐out‐of‐n:F system with exchangeable components

As a generalization of k‐out‐of‐n:F and consecutive k‐out‐of‐n:F systems, the consecutive k‐within‐m‐out‐of‐n:F system consists of n linearly ordered components such that the system fails iff there are m consecutive components which include among them at least k failed components. In this article, the reliability properties of consecutive k‐within‐m‐out‐of‐n:F systems with exchangeable components are studied. The bounds and approximations for the survival function are provided. A Monte Carlo estimator of system signature is obtained and used to approximate survival function. The results are illustrated and numerics are provided for an exchangeable multivariate Pareto distribution. © 2009 Wiley Periodicals, Inc. Naval Research Logistics 2009     

Evaluating methods for the reliability of a large 2‐dimensional rectangular k‐within‐consecutive‐(r,s)‐out‐of‐(m,n):F system

A 2‐dimensional rectangular k‐within‐consecutive‐(r, s)‐out‐of‐(m, n):F system consists of m × n components, and fails if and only if k or more components fail in an r × s submatrix. This system can be treated as a reliability model for TFT liquid crystal displays, wireless communication networks, etc. Although an effective method has been developed for evaluating the exact system reliability of small or medium‐sized systems, that method needs extremely high computing time and memory capacity when applied to larger systems. Therefore, developing upper and lower bounds and accurate approximations for system reliability is useful for large systems. In this paper, first, we propose new upper and lower bounds for the reliability of a 2‐dimensional rectangular k‐within‐consecutive‐(r, s)‐out‐of‐(m, n):F system. Secondly, we propose two limit theorems for that system. With these theorems we can obtain accurate approximations for system reliabilities when the system is large and component reliabilities are close to one. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

Modified discrete preventive maintenance policies

This article proposes a modified preventive maintenance (PM) policy which may be done only at scheduled times nT (n = 1,2, …): The PM is done at the next such time if and only if the total number of failures exceeds a specified number k. The optimal number k^* to minimize the expected cost rate is discussed. Further, four alternative similar PM models are considered, when the system fails due to a certain number of faults, uses, shocks, and unit failures.     

One-facility location with rectilinear tour distances

This article concerns the location of a facility among n points where the points are serviced by “tours” taken from the facility. Tours include m points at a time and each group of m points may become active (may need a tour) with some known probability. Distances are assumed to be rectilinear. For m ≤ 3, it is proved that the objective function is separable in each dimension and an exact solution method is given that involves finding the median of numbers appropriately generated from the problem data. It is shown that the objective function becomes multimodal when some tours pass through four or more points. A bounded heuristic procedure is suggested for this latter case. This heuristic involves solving an auxiliary three-point tour location problem.     

Stochastic comparisons for single-server queues

We consider single-server queueing systems with the queue discipline “first come, first served,” interarrival times {u_k, k ≥ l}, and service times {u_k, k ≥ l}, where the {u_k} and {u_k} are independent sequences of non-negative random variables that are independently but not necessarily identically distributed. Let X_k = u_k − u_k (k ≥ 1), S₀ 0, S_n = X₁ + X₂ … + X_n(n≥1). It is known that the (possibly nonhomogeneous) random walk {S_n} determines the behavior of the system. In this paper we make stochastic comparisons of two such systems σ₁,σ₂ whose basic random variables X and X are stochastically ordered. The corresponding random walks are also similarly ordered, and this leads to stochastic comparisons of idle times, duration of busy period and busy cycles, number of customers served during a busy period, and output from the system. In the classical case of identical distributions of {u_k} and {u_k} we obtain further comparisons. Our results are for the transient behavior of the systems, not merely for steady state.     

Reliability of a 2‐dimensional k‐within‐consecutive‐r × s‐out‐of‐m × n:F system

A 2‐dimensional rectangular (cylindrical) k‐within‐consecutive‐r × s‐out‐of‐m × n:F system is the rectangular (cylindrical) m × n‐system if the system fails whenever k components in a r × s‐submatrix fail. This paper proposes a recursive algorithm for the reliability of the 2‐dimensional k‐within‐consecutive‐r × s‐out‐m × n:F system, in the rectangular case and the cylindrical case. This algorithm requires min ( O (mk^r(n?s)), O (nk^s(m?r))), and O (mk^rn) computing time in the rectangular case and the cylindrical case, respectively. The proposed algorithm will be demonstrated and some numerical examples will be shown. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 625–637, 2001.     

Measures of component importance for markov chain imbeddable reliability structures

In this article we study the reliability importance of the components for the wide class of Markov chain imbeddable systems (MIS). Methods for the evaluation of Birnbaum importance are developed for a general MIS, and some generating function techniques are demonstrated for the special case of homogeneous MISs. As an application, the reliability ordering for the components of a k‐out‐of‐n and consecutive‐k‐out‐of‐n structure is examined in some detail. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 613–639, 1999     

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.     

Confidence intervals in discrete event simulation: A comparison of replication and batch means

Suppose that we have enough computer time to make n observations of a stochastic process by means of simulation and would like to construct a confidence interval for the steady-state mean. We can make k independent runs of m observations each (n=k.m) or, alternatively, one run of n observations which we then divide into k batches of length m. These methods are known as replication and batch means, respectively. In this paper, using the probability of coverage and the half length of a confidence interval as criteria for comparison, we empirically show that batch means is superior to replication, but that neither method works well if n is too small. We also show that if m is chosen too small for replication, then the coverage may decrease dramatically as the total sample size n is increased.     

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.     

Component importance for linear consecutive‐ k ‐Out‐of‐ n and m ‐Consecutive‐ k ‐Out‐of‐ n systems with exchangeable components

Measuring the relative importance of components in a mechanical system is useful for various purposes. In this article, we study Birnbaum and Barlow‐Proschan importance measures for two frequently studied system designs: linear consecutive k ‐out‐of‐ n and m ‐consecutive‐ k ‐out‐of‐ n systems. We obtain explicit expressions for the component importance measures for systems consisting of exchangeable components. We illustrate the results for a system whose components have a Lomax type lifetime distribution. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

A problem of restricted partitions

This paper presents a simple algorithm for finding the number of restricted k-partitions of a natural number n. The unrestricted k-partitions of n are expressed as the sum of these restricted k-partitions, called inadmissible, and the admissible k-partitions. The simplicity of the algorithm is striking, though all the implications are unclear.     

On a ruckle problem in discrete games of ambush

The following zero-sum game is considered. Red chooses in integer interval [1, n] two integer intervals consisting of k and m points where k + m < n, and Blue chooses an integer point in [1, n]. The payoff to Red equals 1 if the point chosen by Blue is at least in one of the intervals chosen by Red, and 0 otherwise. This work complements the results obtained by Ruckle, Baston and Bostock, and Lee. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44: 353–364, 1997     

On scheduling with earliest starts and due dates on a group of identical machines

This paper examines the (n, m) scheduling problem with n operations distributed among m machines. An algorithm for solving this problem is presented and, gives a good heuristic solution on a wide class of problems. Computational results are reported which demonstrate the efficiency of this approach.     

Optimal replacement policies with two or more loaded sliding standbys

This article defines optimal replacement policies for identical components performing different functions in a given system, when more than one spare part is available. The problem is first formulated for two components and any number of spare parts and the optimal replacement time y(x) at time x is found to have a certain form. Sufficient conditions are then provided for y(x) to be a constant y* for x > y*, and y(x) = x for x > y* (single-critical-number policy). Under the assumption that the optimal policies are of the single-critical-number type, the results are extended to the n-component case, and a theorem is provided that reduces the required number of critical numbers. Finally, the theory is applied to the case of the exponential and uniform failure laws, in which single-critical-number policies are optimal, and to another failure law in which they are not.     

Optimal inspection and repair of renewable coherent systems with independent components and constant failure rates

Suppose that a multicomponent reliability system earns revenue while it is working and that it has a finite number of possible failure states (defined as states in which it ceases to work), each with a known prior probability. When the system stops working its components can be inspected one at a time, and, if necessary, replaced or repaired, until the system is restored to its original (operating) state. Inspections (as well as replacements or repairs) are time consuming and expensive. An optimal adaptive inspection strategy for examining and fixing the components of a failed system restores it as efficiently as possible, taking into account the opportunity costs due to lost revenue while the system remains failed as well as the costs and times required for inspections. This article presents exact and heuristic procedures for constructing optimal adaptive strategies for k-out-of-n and general coherent systems. Average revenue per unit time is taken as the maximand for most of the article, but characterizations of optimality are also obtained for series systems in the case of discounted return over an infinite planning horizon. © 1994 John Wiley & Sons, Inc.     

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.     

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     

A note on combined job selection and sequencing problems

We investigate the solvability of two single‐machine scheduling problems when the objective is to identify among all job subsets with cardinality k,1≤k≤n, the one that has the minimum objective function value. For the single‐machine minimum maximum lateness problem, we conclude that the problem is solvable in O(n²) time using the proposed REMOVE algorithm. This algorithm can also be used as an alternative to Moore's algorithm to solve the minimum number of tardy jobs problem by actually solving the hierarchical problem in which the objective is to minimize the maximum lateness subject to the minimum number of tardy jobs. We then show that the REMOVE algorithm cannot be used to solve the general case of the single‐machine total‐weighted completion time problem; we derive sufficient conditions among the job parameters so that the total weighted completion time problem becomes solvable in O(n²) time. © 2013 Wiley Periodicals, Inc. Naval Research Logistics 60: 449–453, 2013