Two shock and wear systems under repair standing a finite number of shocks

A shock and wear system standing a finite number of shocks and subject to two types of repairs is considered. The failure of the system can be due to wear or to a fatal shock. Associated to these failures there are two repair types: normal and severe. Repairs are as good as new. The shocks arrive following a Markovian arrival process, and the lifetime of the system follows a continuous phase-type distribution. The repair times follow different continuous phase-type distributions, depending on the type of failure. Under these assumptions, two systems are studied, depending on the finite number of shocks that the system can stand before a fatal failure that can be random or fixed. In the first case, the number of shocks is governed by a discrete phase-type distribution. After a finite (random or fixed) number of non-fatal shocks the system is repaired (severe repair). The repair due to wear is a normal repair. For these systems, general Markov models are constructed and the following elements are studied: the stationary probability vector; the transient rate of occurrence of failures; the renewal process associated to the repairs, including the distribution of the period between replacements and the number of non-fatal shocks in this period. Special cases of the model with random number of shocks are presented. An application illustrating the numerical calculations is given. The systems are studied in such a way that several particular cases can be deduced from the general ones straightaway. We apply the matrix-analytic methods for studying these models showing their versatility.     

Shock models under a Markovian arrival process

A device submitted to shocks arriving randomly and causing damage is considered. Every shock can be fatal or not. The shocks follow a Markovian arrival process. When the shock is fatal, the device is instantaneously replaced. The Markov process governing the shocks is constructed, and the stationary probability vector calculated. The probability of the number of replacements during a time is determined. A particular case in which the fatal shock occurs after a fixed number of shocks is introduced, and a numerical application is performed. The expressions are in algorithmic form due to the use of matrix-analytic methods. Computational aspects are introduced. This model extends others previously considered in the literature.     

Optimal replacement policy based on maximum repair time for a random shock and wear model

We study a \(\delta \) shock and wear model in which the system can fail due to the frequency of the shocks caused by external conditions, or aging and accumulated wear caused by intrinsic factors. The external shocks occur according to a Bernoulli process, i.e., the inter-arrival times between two consecutive shocks follow a geometric distribution. Once the system fails, it can be repaired immediately. If the system is not repairable in a pre-specific time D, it can be replaced by a new one to avoid the unnecessary expanses on repair. On the other hand, the system can also be replaced whenever its number of repairs exceeds N. Given that infinite operating and repair times are not commonly encountered in practical situations, both of these two random variables are supposed to obey general discrete distribution with finite support. Replacing the finite support renewal distributions with appropriate phase-type (PH) distributions and using the closure property associated with PH distribution, we formulate the maximum repair time replacement policy and obtain analytically the long-run average cost rate. Meanwhile, the optimal replacement policy is also numerically determined by implementing a two-dimensional-search process.     

A reliability system under different types of shock governed by a Markovian arrival process and maintenance policy K

A reliability system subject to shocks producing damage and failure is considered. The source of shocks producing failures is governed by a Markovian arrival process. All the shocks produce deterioration and some of them failures, which can be repairable or non-repairable. Repair times are governed by a phase-type distribution. The number of deteriorating shocks that the system can stand is fixed. After a fatal failure the system is replaced by another identical one. For this model the availability, the reliability, and the rate of occurrence of the different types of failures are calculated. It is shown that this model extends other previously published in the literature.     

Consecutive k-out-of-n systems with maintenance

A consective k-out-of-n system consists of n linearly or cycliccally ordered components such that the system fails if and only if at least k consecutive components fail. In this paper we consider a maintained system where each component is repaired independently of the others according to an exponential distribution. Assuming general lifetime distributions for system's components we prove a limit theorem for the time to first failure of both linear and circular systems.     

Reliability analysis of two-unit cold standby repairable systems under Poisson shocks

This paper analyses the reliability of a cold standby system consisting of two repairable units, a switch and a repairman. At any time, one of the two units is operating while the other is on cold standby. The repairman may not always at the job site, or take vacation. We assume that shocks can attack the operating unit. The arrival times of the shocks follow a homogeneous Poisson process and their magnitude is a random variable following a known distribution. Time on repairing a failed unit and the length of repairman’s vacation follow general continuous probability distributions, respectively. The paper derives a number of reliability indices: system reliability, mean time to first failure, steady-state availability, and steady-state failure frequency.     

A reliability semi‐Markov model involving geometric processes

We consider a semi‐Markov process that models the repair and maintenance of a repairable system in steady state. The operating and repair times are independent random variables with general distributions. Failures can be caused by an external source or by an internal source. Some failures are repairable and others are not. After a repairable failure, the system is not as good as new and our model reflects that. At a non‐repairable failure, the system is replaced by a new one. We assume that external failures occur according to a Poisson process. Moreover, there is an upper limit N of repairs, it is replaced by a new system at the next failure, regardless of its type. Operational and repair times are affected by multiplicative rates, so they follow geometric processes. For this system, the stationary distribution and performance measures as well as the availability and the rate of occurrence of different types of failures in stationary state are calculated. Copyright © 2002 John Wiley & Sons, Ltd.     

Aging properties of the residual life length of k‐out‐of‐n systems with independent but non‐identical components

The k‐out‐of‐n structure is a very popular type of redundancy in fault‐tolerant systems, it has founded wide applications in industrial and military systems during the past several decades. This paper will investigate the residual life length of a k‐out‐of‐n system with independent (not necessarily identical) components, given that the (n?k)th failure has occurred at time t?0. Behaviour of PF₂, IFR, DRHR, DMRL, NBU(2) and NBUC classes of life distributions are derived in terms of the monotonicity of the residual life given the time of the (n?k)th failure. Copyright © 2004 John Wiley & Sons, Ltd.     

Optimal replacement and allocation of multi‐state elements in k‐within‐m‐from‐r/n sliding window systems

This paper proposes a new model that generalizes the linear sliding window system to the case of multiple failures. The considered k ‐within‐ m ‐from‐ r / n sliding window system consists of n linearly ordered multi‐state elements and fails if at least k groups out of m consecutive groups of r consecutive multi‐state elements have cumulative performance lower than the demand W . A reliability evaluation algorithm is suggested for the proposed system. In order to increase the system availability, maintenance actions can be performed, and the elements can be optimally allocated. A joint element allocation and maintenance optimization model is formulated with the objective of minimizing the total maintenance cost subjected to the pre‐specified system availability requirement. Basic procedures of genetic algorithms are adapted to solve the optimization problem. Numerical experiments are presented to illustrate the applications. Copyright © 2015 John Wiley & Sons, Ltd.     

On the use of phase‐type distributions for inventory management with supply disruptions

Maintaining the continuity of operations becomes increasingly important for systems that are subject to disruptions due to various reasons. In this paper, we study an inventory system operating under a (q, r) policy, where the supply can become inaccessible for random durations. The availability of the supply is modeled by assuming a single supplier that goes through ON and OFF periods of stochastic duration, both of which are modeled by phase‐type distributions (PTD). We provide two alternative representations of the state transition probabilities of the system, one with integral and the other employing Kolmogorov differential equations. We then use an efficient formulation for the analytical model that gives the optimal policy parameters and the long‐run average cost. An extensive numerical study is conducted, which shows that OFF time characteristics have a bigger impact on optimal policy parameters. The ON time characteristics are also important for critical goods if disasters can happen. Copyright © 2011 John Wiley & Sons, Ltd.     

The k‐piece packing problem

A k‐piece of a graph G is a connected subgraph of G all of whose nodes have degree at most k and at least one node has degree equal to k. We consider the problem of covering the maximum number of nodes of a graph by node disjoint k‐pieces. When k = 1 this is the maximum matching problem, and when k = 2 this is the problem, recently studied by Kaneko [ 19 [, of covering the maximum number of nodes by disjoint paths of length greater than 1. We present a polynomial time algorithm for the problem as well as a Tutte‐type existence theorem and a Berge‐type min‐max formula. We also solve the problem in the more general situation where the “pieces” are defined in terms of lower and upper bounds on the degrees. © 2006 Wiley Periodicals, Inc. J Graph Theory     

Reliability analysis of a stand-by system with repair and intermediate stocks for failed and repaired units

In this paper we give a reliability analysis of a stand-by system with repair, consisting of N working and N^R stand-by units. Failed and repaired units are collected in intermediate stocks. Concerning the delivery from the intermediate stocks we consider two rules: (i) the collected units are delivered in fixed time intervals; (ii) the units will be delivered when there are k units accumulated. The system fails if a unit that has failed cannot be replaced by a stand-by unit. Using a point process approach we derive approximations for the stationary availability and mean time between failures of the system. Numerical results show that the proposed approximations, which can be handled easily, work well.     

Optimization issues in k-out-of-n systems

The k-out-of-n system is a system consisting of n independent components such that the system works if and only if at least k of these n components are successfully running. Each component of the system is subject to shocks which arrive according to a nonhomogeneous Poisson process. When a shock takes place, the component is either minimally repaired (type 1 failure) or lying idle (type 2 failure). Assume that the probability of type 1 failure or type 2 failure depends on age. First, we investigate a general age replacement policy for a k-out-of-n system that incorporates minimal repair, shortage and excess costs. Under such a policy, the system is replaced at age T or at the occurrence of the (n-k + 1)th idle component, whichever occurs first. Moreover, we consider another model; we assume that the system operates some successive projects without interruptions. The replacement could not be performed at age T. In this case, the system is replaced at the completion of the Nth project or at the occurrence of the (n-k + 1)th idle component, whichever occurs first. For each model, we develop the long term expected cost per unit time and theoretically present the corresponding optimum replacement schedule. Finally, we give a numerical example illustrating the models we proposed. The proposed models include more realistic factors and extend many existing models.     

Estimation with Sequential Order Statistics from Exponential Distributions

The lifetime of an ordinary k-out-of-n system is described by the (n–k+1)-st order statistic from an iid sample. This set-up is based on the assumption that the failure of any component does not affect the remaining ones. Since this is possibly not fulfilled in technical systems, sequential order statistics have been proposed to model a change of the residual lifetime distribution after the breakdown of some component. We investigate such sequential k-out-of-n systems where the corresponding sequential order statistics, which describe the lifetimes of these systems, are based on one- and two-parameter exponential distributions. Given differently structured systems, we focus on three estimation concepts for the distribution parameters. MLEs, UMVUEs and BLUEs of the location and scale parameters are presented. Several properties of these estimators, such as distributions and consistency, are established. Moreover, we illustrate how two sequential k-out-of-n systems based on exponential distributions can be compared by means of the probability P(X < Y). Since other models of ordered random variables, such as ordinary order statistics, record values and progressive type II censored order statistics can be viewed as sequential order statistics, all the results can be applied to these situations as well.     

An imperfect maintenance model with block replacements

We consider a model in which when a device fails it is either repaired to its condition prior to failure or replaced. Moreover, the device is replaced at times kT, k = 1, 2, … The decision to repair or replace the device at failure depends on the age of the device at failure. We find the optimal block time, T₀, that minimizes the long-run average cost of maintenance per unit time. Our results are shown to extend many of the well known results for block replacement policies.     

Multidimensional viscous shocks II: The small viscosity limit

In this paper we prove the existence of curved, multidimensional viscous shocks and also justify the small‐viscosity limit. Starting with a curved, multidimensional (inviscid) shock solution to a system of hyperbolic conservation laws, we show that the shock can be obtained as a small‐viscosity limit of solutions to an associated parabolic problem (viscous shocks). The two main hypotheses are a natural Evans function assumption on the viscous profile, together with a restriction on how much the shock can deviate from flatness. The main tools are a conjugation lemma that removes x_N/? dependence from the linearization of the parabolic problem about the viscous profile, new degenerate Kreiss‐type symmetrizers used to prove an L² estimate for the linearized problem, and a finite‐regularity calculus of semiclassical and mixed type (classical‐semiclassical) pseudodifferential operators. © 2003 Wiley Periodicals, Inc.     

Average‐case analyses of first fit and random fit bin packing

We prove that the First Fit bin packing algorithm is stable under the input distribution U{k−2, k} for all k≥3, settling an open question from the recent survey by Coffman, Garey, and Johnson [“Approximation algorithms for bin backing: A survey,” Approximation algorithms for NP‐hard problems, D. Hochbaum (Editor), PWS, Boston, 1996]. Our proof generalizes the multidimensional Markov chain analysis used by Kenyon, Sinclair, and Rabani to prove that Best Fit is also stable under these distributions [Proc Seventh Annual ACM‐SIAM Symposium on Discrete Algorithms, 1995, pp. 351–358]. Our proof is motivated by an analysis of Random Fit, a new simple packing algorithm related to First Fit, that is interesting in its own right. We show that Random Fit is stable under the input distributions U{k−2, k}, as well as present worst case bounds and some results on distributions U{k−1, k} and U{k, k} for Random Fit. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 16: 240–259, 2000     

Algorithms for coloring semi-random graphs

The graph coloring problem is to color a given graph with the minimum number of colors. This problem is known to be NP-hard even if we are only aiming at approximate solutions. On the other hand, the best known approximation algorithms require n^δ (δ>0) colors even for bounded chromatic (k-colorable for fixed k) n-vertex graphs. The situation changes dramatically if we look at the average performance of an algorithm rather than its worst case performance. A k-colorable graph drawn from certain classes of distributions can be k-colored almost surely in polynomial time. It is also possible to k-color such random graphs in polynomial average time. In this paper, we present polynomial time algorithms for k-coloring graphs drawn from the semirandom model. In this model, the graph is supplied by an adversary each of whose decisions regarding inclusion of edges is reversed with some probability p. In terms of randomness, this model lies between the worst case model and the usual random model where each edge is chosen with equal probability. We present polynomial time algorithms of two different types. The first type of algorithms always run in polynomial time and succeed almost surely. Blum and Spencer [J. Algorithms, 19 , 204–234 (1995)] have also obtained independently such algorithms, but our results are based on different proof techniques which are interesting in their own right. The second type of algorithms always succeed and have polynomial running time on the average. Such algorithms are more useful and more difficult to obtain than the first type of algorithms. Our algorithms work for semirandom graphs drawn from a wide range of distributions and work as long as p≥n^−α(k)+ϵ where α(k)=(2k)/((k−1)(k+2)) and ϵ is a positive constant. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 13, 125–158 (1998)     

The number of k‐SAT functions

We study the number SAT(k; n) of Boolean functions of n variables that can be expressed by a k‐SAT formula. Equivalently, we study the number of subsets of the n‐cube 2ⁿ that can be represented as the union of (n ? k)‐subcubes. In The number of 2‐SAT functions (Isr J Math, 133 (2003), 45–60) the authors and Imre Leader studied SAT(k; n) for k ≤ n/2, with emphasis on the case k = 2. Here, we prove bounds on SAT(k; n) for k ≥ n/2; we see a variety of different types of behavior. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 22: 227–247, 2003     

On the interaction between maintenance,spare part inventories and repair capacity for a k-out-of-N system with wear-out

In this paper we consider a k-out-of-N system with identical, repairable components under a condition-based maintenance policy. Maintenance consists of replacing all failed and/or aged components. Next, the replaced components have to be repaired. The system availability can be controlled by the maintenance policy, the spare part inventory level, the repair capacity and repair job priority setting. We present two approximate methods to analyse the relation between these control variables and the system availability. Comparison with simulation results shows that we can generate accurate approximations using one of these models, depending on the system size.