Analysis of a system with minimal repair and its application to replacement policy

The periodic replacement with minimal repair at failures is studied by many authors, however, there is not a clear definition for minimal repair. This paper defines a minimal repair in the term of the failure rate and devices some probability quantities and reliability properties. As an application of these results, the replacement model where a system is replaced at time T or at nth failure are considered and the optimum policies are discussed.     

A deteriorating cold standby repairable system with priority in use

In this paper, a cold standby repairable system consisting of two dissimilar components and one repairman is studied. In this system, it is assumed that the working time distributions and the repair time distributions of the two components are both exponential and component 1 is given priority in use. After repair, component 2 is “as good as new” while component 1 follows a geometric process repair. Under these assumptions, using the geometric process and a supplementary variable technique, some important reliability indices such as the system availability, reliability, mean time to first failure (MTTFF), rate of occurrence of failure (ROCOF) and the idle probability of the repairman are derived. A numerical example for the system reliability R(t) is given. And it is considered that a repair-replacement policy based on the working age T of component 1 under which the system is replaced when the working age of component 1 reaches T. Our problem is to determine an optimal policy T^∗ such that the long-run average cost per unit time of the system is minimized. The explicit expression for the long-run average cost per unit time of the system is evaluated, and the corresponding optimal replacement policy T^∗ can be found analytically or numerically. Another numerical example for replacement model is also given.     

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.     

Properties of random walks on discrete groups: Time regularity and off-diagonal estimates

In this paper we study some properties of the convolution powers K(n)=K∗K∗?∗K of a probability density K on a discrete group G, where K is not assumed to be symmetric. If K is centered, we show that the Markov operator T associated with K is analytic in Lp(G) for 1<p<∞, and prove Davies-Gaffney estimates in L² for the iterated operators Tn. This enables us to obtain Gaussian upper bounds for the convolution powers K(n). In case the group G is amenable, we discover that the analyticity and Davies-Gaffney estimates hold if and only if K is centered. We also estimate time and space differences, and use these to obtain a new proof of the Gaussian estimates with precise time decay in case G has polynomial volume growth.     

Irredundance, secure domination and maximum degree in trees

It is shown that the lower irredundance number and secure domination number of an n vertex tree T with maximum degree Δ?3, are bounded below by 2(n+1)/(2Δ+3)(T≠K_1,Δ) and (Δn+Δ-1)/(3Δ-1), respectively. The bounds are sharp and extremal trees are exhibited.     

A two-unit general parallel system with (n − 2) cold standbys—Analytic and simulation approach

A parallel (2, n − 2)-system is investigated here where two units start their operation simultaneously and any one of them is replaced instantaneously upon its failure by one of the (n − 2) cold standbys. We assume availability of n non-identical, non-repairable units for replacement or support. The system reliability is evaluated by recursive relations with unit-lifetimes T_i (i = 1, … , n) that have a general joint distribution function F(t). On the basis of the derived expression, simulation techniques have been developed for the evaluation of the system reliability and the mean time to failure, useful when dealing with large systems or correlated unit-lifetimes and less mathematically manageable distributions. Simulation results are presented for various lifetime distributions and comparisons are made with derived analytic results for some special distributions and moderate values of n.     

Linear maps that preserve singular and nonsingular matrices

Let M (n,K) be the algebra of n × n matrices over an algebraically closed field K and T:M (n,K)→M (n,K) a linear transformation with the property that T maps nonsingular (singular) matrices to nonsingular (singular) matrices. Using some elementary facts from commutative algebra we show that T is nonsingular and maps singular matrices to singular matrices (T is nonsingular or T maps all matrices to singular matrices). Using these results we obtain Marcus and Moyl's characterization [T(x) = UXVorU^tXV for fixed U and V] from a result of Dieudonné's. Examples are given to show the hypothesis of algebraic closure in necessary.     

Involutions in triangular groups

We describe involutions, i.e. elements of order 2, in the groups T _n (K) – of upper triangular matrices of dimension n (n?∈??), and T _∞(K) – of upper triangular infinite matrices, where K is a field of characteristic different from 2. Using the obtained result, we give a formula for the number of all involutions in T _n (K) in the case when K is a finite field.     

Generating 3-vertex connected spanning subgraphs

In this paper we present an algorithm to generate all minimal 3-vertex connected spanning subgraphs of an undirected graph with n vertices and m edges in incremental polynomial time, i.e., for every K we can generate K (or all) minimal 3-vertex connected spanning subgraphs of a given graph in O(K²log(K)m²+K²m³) time, where n and m are the number of vertices and edges of the input graph, respectively. This is an improvement over what was previously available and is the same as the best known running time for generating 2-vertex connected spanning subgraphs. Our result is obtained by applying the decomposition theory of 2-vertex connected graphs to the graphs obtained from minimal 3-vertex connected graphs by removing a single edge.     

Carmichael numbers in number rings

We generalize Carmichael numbers to ideals in number rings and prove a generalization of Korselt's Criterion for these Carmichael ideals. We investigate when Carmichael numbers in the integers generate Carmichael ideals in the algebraic integers of abelian number fields. In particular, we show that given any composite integer n, there exist infinitely many quadratic number fields in which n is not Carmichael. Finally, we show that there are infinitely many abelian number fields K with discriminant relatively prime to n such that n is not Carmichael in K.     

Capacitated dynamic lot-sizing problem with delivery/production time windows

In this paper we generalize the classical dynamic lot-sizing problem by considering production capacity constraints as well as delivery and/or production time windows. Utilizing an untraditional decomposition principle, we develop a polynomial-time algorithm for computing an optimal solution for the problem under the assumption of non-speculative costs. The proposed solution methodology is based on a dynamic programming algorithm that runs in O(nT⁴) time, where n is the number of demands and T is the length of the planning horizon.     

An extended optimal replacement model of systems subject to shocks

A system is subject to shocks that arrive according to a non-homogeneous Poisson process. As shocks occur a system has two types of failures: type I failure (minor failure) is rectified by a minimal repair, whereas type II failure (catastrophic failure) is removed by replacement. The probability of a type II failure is permitted to depend on the number of shocks since the last replacement. This paper proposes a generalized replacement policy where a system is replaced at the nth type I failure or first type II failure or at age T, whichever occurs first. The cost of the minimal repair of the system at age t depends on the random part C(t) and deterministic paper c(t). The expected cost rate is obtained. The optimal n¹ and optimal T¹ which would minimize the cost rate are derived and discussed. Various special cases are considered and detailed.     

Gene tree correction for reconciliation and species tree inference: Complexity and algorithms

Reconciliation consists in mapping a gene tree T into a species tree S, and explaining the incongruence between the two as evidence for duplication, loss and other events shaping the gene family represented by the leaves of T. When S is unknown, the Species Tree Inference Problem is to infer, from a set of gene trees, a species tree leading to a minimum reconciliation cost. As reconciliation is very sensitive to errors in T, gene tree correction prior to reconciliation is a fundamental task. In this paper, we investigate the complexity of four different combinatorial approaches for deleting misplaced leaves from T. First, we consider two problems (Minimum Leaf Removal and Minimum Species Removal) related to the reconciliation of T with a known species tree S. In the former (latter respectively) we want to remove the minimum number of leaves (species respectively) so that T is “MD-consistent” with S. Second, we consider two problems (Minimum Leaf Removal Inference and Minimum Species Removal Inference) related to species tree inference. In the former (latter respectively) we want to remove the minimum number of leaves (species respectively) from T so that there exists a species tree S such that T is MD-consistent with S. We prove that Minimum Leaf Removal and Minimum Species Removal are APX-hard, even when each label has at most two occurrences in the input gene tree, and we present fixed-parameter algorithms for the two problems. We prove that Minimum Leaf Removal Inference is not only NP-hard, but also W[2]-hard and inapproximable within factor $c\ln n$, where n is the number of leaves in the gene tree. Finally, we show that Minimum Species Removal Inference is NP-hard and W[2]-hard, when parameterized by the size of the solution, that is the minimum number of species removals.     

A mixed integer linear programming formulation of the optimal mean/Value-at-Risk portfolio problem

In this paper, we consider an extension of the Markovitz model, in which the variance has been replaced with the Value-at-Risk. So a new portfolio optimization problem is formulated. We showed that the model leads to an NP-hard problem, but if the number of past observation T or the number of assets K are low, e.g. fixed to a constant, polynomial time algorithms exist. Furthermore, we showed that the problem can be formulated as an integer programming instance. When K and T are large and α^VaR is small—as common in financial practice—the computational results show that the problem can be solved in a reasonable amount of time.     

P 4k−1-factorization of bipartite multigraphs

Let λK _m,n be a bipartite multigraph with two partite sets having m and n vertices, respectively. A P _v-factorization of λK _m,n is a set of edge-disjoint P _v -factors of λK _m,n which partition the set of edges of λK _m,n. When v is an even number, Ushio, Wang and the second author of the paper gave a necessary and sufficient condition for the existence of a P _v -factorization of λK _m,n. When v is an odd number, we proposed a conjecture. However, up to now we only know that the conjecture is true for v = 3. In this paper we will show that the conjecture is true when v = 4k ? 1. That is, we shall prove that a necessary and sufficient condition for the existence of a P _4k?1-factorization of λK _m,n is (1) (2k ? 1)m ? 2kn, (2) (2k ? 1)n ? 2km, (3) m + n ≡ 0 (mod 4k ? 1), (4) λ(4k ? 1)mn/[2(2k ? 1)(m + n)] is an integer.     

A sequential method for preventive maintenance and replacement of a repairable single-unit system

This paper is concerned with when to implement preventive maintenance (PM) and replacement for a repairable ‘single-unit’ system in use. Under the main assumption that a ‘single-unit’ system gradually deteriorates with time, a sequential method is proposed to determine an optimal PM and replacement strategy for the system based on minimising expected loss rate. According to this method, PM epochs are determined one after the other, and consequently we can make use of all previous information on the operation process of the system. Also the replacement epoch depends on the effective age of the system. A numerical example shows that the sequential method can be used to solve the PM and replacement problem of a ‘single-unit’ system efficiently. Some properties of the loss functions W(L? _n ,b? _n ) and W? _r (N) with respect to PM and replacement respectively are discussed in the appendix.     

The decompositions of line graphs,middle graphs and total graphs of complete graphs into forests

We construct decompositions of L(K_n), M(K_n) and T(K_n) into the minimum number of line-disjoint spanning forests by applying the usual criterion for a graph to be eulerian. This gives a realization of the arboricity of each of these three graphs.     

Hajós' graph-coloring conjecture: Variations and counterexamples

For each integer n ≥ 7, we exhibit graphs of chromatic number n that contain no subdivided K_n as a subgraph. However, we show that a graph with chromatic number 4 contains as a subgraph a subdivided K₄ in which each triangle of the K₄ is subdivided to form an odd cycle.     

Reliability tests for Weibull distribution with variational shape parameter based on sudden death lifetime data

In the traditional design of reliability tests for assuring the mean time to failure (MTTF) in Weibull distribution with shape and scale parameters, it has been assumed that the shape parameter in the acceptable and rejectable populations is the same fixed number. For the purpose of expanding applicability of the reliability testing, Hisada and Arizono have developed a reliability sampling scheme for assuring MTTF in the Weibull distribution under the conditions that shape parameters in the both populations do not necessarily coincide, and are specified as interval values, respectively. Then, their reliability test is designed using the complete lifetime data. In general, the reliability testing based on the complete lifetime data requires the long testing time. As a consequence, the testing cost becomes sometimes expensive. In this paper, for the purpose of an economical plan of the reliability test, we consider the sudden death procedure for assuring MTTF in Weibull distribution with variational shape parameter.     

Preventive maintenance in a 1 out of n system: The uptime,downtime and costs

In repairable systems with redundancy, failed units can be replaced by spare units in order to reduce the system downtime. The failed units are sent to a repair shop or manufacturer for corrective maintenance and subsequently are returned for re-use. In this paper we consider a 1 out of n system with cold standby and we assume that repaired units are “as good as new”.When a unit has an increasing failure rate it can be advantageous to perform preventive maintenance in order to return it to its “as good as new” state, because preventive maintenance will take less time and tends to be cheaper. In the model we present we use age-replacement; a machine is taken out for preventive maintenance and replaced by a standby one if its age has reached a certain value, T_pm. In this paper we derive an approximation scheme to compute the expected uptime, the expected downtime and the expected costs per time unit of the system, given the total number of units and the age-replacement value, T_pm. Consequently the number of units and the value T_pm can be determined for maximum long-term economy.