PaperlayerView exact revision on arXiv

Source-linked AI summary

Per-State Signatures and Mean Time-to-Failure: An Algorithm for Systems With Simultaneous Failures

Guido Lagos, Simón Ávila

arXiv:2610.22181v1cs.DSmath.OCmath.PR

TL;DR

Maintenance decisions arise at partially failed states, where component identity can affect remaining life. The paper computes signatures and MTTFs for every state, then uses per-state MTTFs for threshold repair policies. In benchmarks, the best MTTF-threshold policy’s median excess cost over the optimal state-based policy is 0.36%.

  • Problem

    Reliability indices are usually reported for fully working systems, although maintenance decisions occur at partially failed states where component identity can affect remaining useful life.

    Source: §I · p. 1

  • Method

    The algorithm computes per-state signatures and MTTFs for monotone binary systems under exchangeable failure times whose survivor count is a continuous-time Markov chain.

    Source: §I · p. 1, §VIII · p. 13

  • Results

    The best MTTF-threshold policy has median excess cost of 0.36% over the optimal state-based policy.

    Source: §VIII · p. 14

  • Takeaways & Limitations

    Per-state signature is a strictly finer decision criterion than MTTF, and signature dominance at a common failure count implies MTTF dominance, but not conversely.

    Source: §VI · p. 7, §VIII · p. 13

    Enumerating 2^n states limits the algorithm to a few dozen components, and the single-pass threshold-policy calculation depends on MTTF monotonicity, which may fail for other models.

    Source: §VIII · p. 14

Abstract

from arXiv · show

We present an algorithm that computes the structural signature and the mean time-to-failure (MTTF) of a monotone binary system at every one of its states, rather than only at the state in which all components work. It makes no assumption on the structure function and evaluates it exactly once per state, as many times as needed for the signature of the complete system alone, so computing the MTTF everywhere costs only a factor polynomial in the number of components over computing it once. As a by-product, it identifies all minimal path sets. We assume exchangeable component failure times whose survivor count is a continuous-time Markov chain. This setting admits simultaneous failures, as in the L\'evy-frailty Marshall-Olkin, binomial failure rate and lethal-shock models, where the simplifications available for single failures do not apply. We use the per-state MTTF to define threshold repair policies. We show that the per-state signature is a strictly finer decision criterion than the MTTF: signature dominance at a common failure count implies MTTF dominance, but not conversely. Under the L\'evy-frailty Marshall-Olkin model the MTTF is monotone in the state, which yields the long-run cost rate of every threshold policy in a single pass. Experiments on 22 benchmark networks with up to 30 components and 31 failure models show that the best MTTF-threshold policy has a median excess cost of 0.36% over the optimal state-based policy, and that it is never worse than the best policy that repairs after a fixed number of failures.

I. INTRODUCTION

Reliability indices are usually reported for fully working systems, although maintenance decisions arise after partial failures and can depend on which components failed. Computing indices at every state is challenging because the state space grows exponentially with the number of components.

I. INTRODUCTION

  • Maintenance decisions occur at partially failed states, where states with the same failure count can have different remaining useful life depending on component identity.A decision rule that ignores those differences discards information available to the operator.Source: §I · p. 1

A. Setting and notation

  • The structural signature separates system structure from component failure-time behavior and summarizes the proportion of working states at each failure count.Its entries are differences of the tail signature, which is nonincreasing across failure counts.Source: A. Setting and notation · p. 1

B. Computational challenge due to the exponential number of states

  • Computing signatures is challenging because even one signature can require evaluating the system at all 2^n states, and per-state signatures appear to require repeated enumerations.For n = 40, the states with 20 failed components alone number 137,846,528,820.Source: B. Computational challenge due to the… · p. 2

C. Contributions

The paper develops an efficient way to compute per-state signatures and MTTFs, then uses them to analyze repair policies under exchangeable failure times with a Markov survivor count. Its experiments compare MTTF-threshold policies with state-based and fixed-failure-count alternatives.

C. Contributions

  • The algorithm computes signatures and MTTFs at every state with the same 2^n structure-function evaluations as a complete-system signature, plus polynomial overhead.It makes no assumption on the structure function and also identifies minimal path sets.Source: C. Contributions · p. 2

Assumptions:

  • The model allows simultaneous failures, but exchangeability and a Markov survivor count together force a pure-death chain and exclude several dependent-failure classes.The paper cites the L´evy-frailty Marshall-Olkin, binomial failure rate, and lethal-shock families as examples of the setting.Source: C. Contributions · p. 2, Assumptions · p. 3

C. Contributions

  • Signature dominance at a common failure count implies MTTF dominance, but the converse fails; under L´evy-frailty Marshall-Olkin, MTTF monotonicity enables a single-pass cost calculation for MTTF-threshold policies.The policies are compared using long-run expected cost, including a setup cost per repair intervention.Source: C. Contributions · p. 2
  • The best MTTF-threshold policy has median excess cost of 0.36% over the optimal state-based policy and median savings of 4.2% over the best r-out-of-n policy.The threshold cost curve is neither convex nor unimodal, so the threshold must be tuned over all breakpoints.Source: C. Contributions · p. 2

II. RELATED WORK

  • Existing signature methods target the complete system, while the paper reports no known method producing signatures for arbitrary states at comparable cost.Prior approaches include minimal path or cut set enumeration and symbolic representations such as binary decision diagrams.Source: §II · pp. 2–3

III. MTTF AT ALL STATES

  • The per-state subsystem signature motivates computing MTTF from any state, but the resulting equations can be difficult to simplify for simultaneous-failure models.The paper assumes exchangeable failure times and a continuous-time Markov chain for the survivor count.Source: §III · p. 3, Assumptions · p. 3

IV. EFFICIENT COMPUTATION THROUGH SIGNATURES

A recursive computation over states supplies the counting vectors used to derive each state’s signature and MTTF. The resulting sweep also identifies minimal path sets without extra evaluations of the structure function.

IV. EFFICIENT COMPUTATION THROUGH SIGNATURES

  • The recursion computes each state’s counting vector from its structure status and the vectors of its immediate sons, which are states formed by failing one working component.The sweep processes states by failure count and uses those vectors to obtain per-state signatures and MTTFs.Source: §IV · p. 4
  • For the three-component example with iid exponential failure times, repairing at the first failure is cheapest among the three distinct MTTF-threshold policies.The reported long-term costs are 1/10, 11/15, and 97/105 across the respective threshold intervals.Source: §IV · p. 4
  • Theorem 2’s algorithm evaluates the structure function exactly 2^n times, once per state, and computing MTTFs everywhere adds only polynomial overhead in memory and arithmetic.It requires O(n^2 2^n) integer additions and memory accesses, O(n 2^n) other basic operations, and O(√n 2^n) integers of memory for counting vectors.Source: §IV · pp. 4–5
  • The sweep identifies every minimal path set at no additional structure-function evaluations by flagging working states whose immediate sons are all failed.A minimal path set is a working component set for which every strict substate fails.Source: §IV · p. 5

V. APPLICATION: REPAIR POLICIES BASED ON THE MTTF

State-based repair policies choose whether to repair or continue when the system arrives at a state. Their long-term costs account for repair expenses and can be computed through renewal cycles.

V. APPLICATION: REPAIR POLICIES BASED ON THE MTTF

  • A state-based policy chooses to repair all failed components or continue operating as soon as the system reaches a state.Source: §V · p. 5
  • Repair costs include component replacement, system restoration after system failure, and a nonnegative fixed intervention setup cost.The setup cost can make grouping replacements advantageous; without it, repairing at the first failure is often close to optimal.Source: §V · p. 5
  • The long-term mean cost rate is obtained from expected cost and expected length of a renewal cycle, since repairs return the Markovian system to its brand-new state.The renewal epochs are the repairs.Source: §V · p. 5

A. MTTF-threshold policies

MTTF-threshold policies repair all failed components when the remaining expected working time falls below a fraction of the new-system MTTF. Under monotone MTTF, their long-run costs can be evaluated across all thresholds in one forward pass.

A. MTTF-threshold policies

  • A threshold γ repairs all failed components when a working state’s remaining expected lifetime is below γ times the new-system MTTF; otherwise operation continues.The policy is defined for γ in (0, 1].Source: A. MTTF-threshold policies · p. 5
  • One forward pass evaluates the long-run mean cost of every MTTF-threshold policy when the MTTF is monotone and known at every state.The threshold policies can number from five to more than a million, making separate linear-system solutions expensive.Source: A. MTTF-threshold policies · pp. 5–6
  • The cycle length, failed-component count at repair, and corrective-repair probability are computed from the states where the policy continues.The continuation set consists of working states with MTTF at least γ times the new-system MTTF.Source: A. MTTF-threshold policies · p. 6
  • Grouping states with the same working-component count and counting vector reduces storage, and sorting those classes by MTTF permits exact evaluation at every threshold breakpoint.In experiments, class counts were 0.005%–0.4% of states for systems with at least 24 components; the cost curve need not be unimodal, so all breakpoints must be evaluated.Source: A. MTTF-threshold policies · p. 6
  • For the Lévy-frailty Marshall–Olkin model, MTTF is monotone, but it need not be monotone in other models.For sequential order statistics with νw = c w^q and q > 1, the MTTF is not monotone; the n = 3 example gives 1 < 1/c ≈ 1.64 for two states.Source: A. MTTF-threshold policies · p. 6

B. Optimal state-based policy

The optimal state-based policy minimizes long-term mean cost among policies that repair at failed states and continue at the fully working state. An iterative policy-improvement procedure computes it and terminates after finitely many iterations.

B. Optimal state-based policy

  • The optimal state-based policy minimizes long-term mean cost among policies that repair at every failed state and continue at the fully working state.Its cost is denoted v* state in the passage.Source: B. Optimal state-based policy · p. 6
  • The method uses policy iteration for average-cost semi-Markov decision processes, equivalently Dinkelbach’s method for fractional programs.Each iteration constructs a policy from statewise choices, then updates the cost-rate estimate using that policy’s cycle cost and length.Source: B. Optimal state-based policy · p. 7
  • The algorithm terminates after finitely many iterations because its cost-rate estimates decrease to the unique root of a strictly decreasing, piecewise-linear function.The function is the minimum of finitely many affine functions, one per policy.Source: B. Optimal state-based policy · p. 7
  • Each pass takes O(n^2 2^n) operations and retains only two consecutive state levels in memory.The sums over substates need not be enumerated individually.Source: B. Optimal state-based policy · p. 7

VI. SIGNATURE DOMINANCE AND THE EXPRESSIVENESS OF SIGNATURE-BASED POLICIES

The per-state tail signature contains decision information beyond the MTTF. At a common failure count, signature dominance implies MTTF dominance, while signature-threshold policies can distinguish states that MTTF thresholds treat alike.

VI. SIGNATURE DOMINANCE AND THE EXPRESSIVENESS OF SIGNATURE-BASED POLICIES

  • At a common working-component count, signature dominance implies MTTF dominance, and strict MTTF dominance follows when the signatures differ and all weights are positive.The positivity condition holds when the working-component count, started at w, can visit every value with positive probability.Source: §VI · p. 7
  • Signature comparisons across states with different numbers of failed components remain unresolved, and signature dominance does not follow from MTTF dominance.Tail signatures can cross, so the converse of the dominance theorem fails.Source: §VI · p. 7
  • MTTF-threshold policies respect signature dominance: if a policy repairs at a dominating state, it also repairs at the dominated state.This follows from the implication from signature dominance to MTTF dominance.Source: §VI · p. 7
  • The per-state tail signature is a strictly finer repair-decision criterion than MTTF because different signatures can yield the same MTTF.MTTF is a single linear projection of the signature; other signature weights can separate states that share an MTTF.Source: §VI · p. 7
  • The expressiveness result does not establish a cost advantage; the gap between the best MTTF-threshold policy and the optimal state-based policy bounds possible savings from signature-threshold policies.Signature-threshold policies are state-based policies that repair at failed states and continue at the fully working state.Source: §VI · p. 7

VII. COMPUTATIONAL EXPERIMENTS

The experiments consider exchangeable failure models whose survivor count is a pure-death continuous-time Markov chain. The iid exponential case is a single-failure model calibrated to unit mean component lifetimes.

VII. COMPUTATIONAL EXPERIMENTS

  • The experiments report computational effort, MTTF-threshold policy behavior, and comparisons with r-out-of-n and optimal state-based policies.The paper’s experimental scope includes failure models, test systems, and costs.Source: §VII · p. 7

A. Failure models satisfying Assumptions (A)–(C)

  • Under Assumptions (A)–(B), the survivor count is a pure-death continuous-time Markov chain specified by exit rates and transition probabilities.Models are calibrated so each component has unit mean lifetime.Source: A. Failure models satisfying… · p. 8

1) iid exponentially distributed failures: 

2) L´evy-frailty Marshall-Olkin (LFMO) model:

The LFMO model represents component failures through a shared degradation process whose jumps can fail several components simultaneously. Experiments calibrate LFMO and related common-cause models to the same pairwise beta factor, while allowing their failure-batch behavior to differ.

2) L´evy-frailty Marshall-Olkin (LFMO) model:

  • The common degradation process L causes simultaneous failures when its jumps exceed components’ independent exponential stress tolerances.Its Laplace exponent Ψ characterizes the model; only Ψ(1), ..., Ψ(n) are needed, including for subordinators that cannot be simulated without bias.Source: 2) L´evy-frailty Marshall-Olkin (LFMO)… · p. 8

3) Binomial failure rate and lethal-shock models:

  • [BFR] models shocks that independently fail each working component with probability p, while [LSh] models shocks that fail all working components at once.Both are LFMO-type models; [BFR] combines drift with compound Poisson jumps, and [LSh] combines drift with killing.Source: 3) Binomial failure rate and… · p. 8

B. Failure models used in the experiments

  • The experiments normalize models to Ψ(1) = 1 and compare β values from 1% to 50%, producing 31 failure models including [Exp].[LFMO-IG] cannot attain pairwise beta factors above approximately 0.586.Source: B. Failure models used in the… · pp. 8–9
  • The pairwise beta factor is the fraction of a component’s failure rate due to events that also fail a given other component.Matching β makes the models agree on every pair of components, while their simultaneity can grow differently for larger groups.Source: B. Failure models used in the… · p. 9
  • At n = 30, mean components failing at the first epoch range from 1.05 to 1.91 in the realistic scenario, 1.24 to 6.0 in the poorly separated scenario, and 1.94 to 15.0 in the stressed scenario.Despite matched pairwise dependence, the models produce different batch sizes as system size grows.Source: B. Failure models used in the… · p. 9

C. Systems used in the experiments

The experiments use 22 two-terminal network systems and a grid of failure models and maintenance costs. They compare MTTF-threshold policies with fixed-failure-count and optimal state-based policies, using one state-space sweep per system.

C. Systems used in the experiments

  • The 22 benchmarks are two-terminal networks with 5 to 30 edges as components, and the system works when working edges connect s to t.Their state spaces range from 32 to about 1.07 × 10^9 configurations.Source: C. Systems used in the experiments · p. 9

D. Cost structure

  • The cost grid contains 45 pairs of ρ, the relative cost of replacing all components, and σ, the intervention setup cost.ρ ranges from 1/10 to 10, and σ from 0 to 0.5.Source: D. Cost structure · pp. 9–10

E. Benchmark policies

  • The best MTTF-threshold policy is compared with repair after a fixed number of failures and with the optimal state-based policy.The gap between the best MTTF-threshold and optimal state-based costs upper-bounds the savings any signature-threshold policy can achieve over the best MTTF-threshold policy.Source: E. Benchmark policies · p. 10

F. Experimental design and computational setup

  • The design covers 682 system–failure-model configurations and 30,690 configuration–cost combinations; Algorithm 1 runs once per system, then state MTTFs and policy curves are computed from stored state classes.The optimal state-based policy is computed for 19 systems with n ≤ 27, covering 26,505 combinations.Source: F. Experimental design and… · p. 10

G. Results: the MTTF at all states

Grouping states by counting vector makes it practical to compute MTTFs and policy curves without repeating the full state sweep for each failure model. MTTF-threshold policies outperform fixed-failure-count policies in the reported comparisons, though threshold costs can be irregular across the search range.

G. Results: the MTTF at all states

  • Algorithm 1 takes 1.2 to 5.6 times as long as complete-state enumeration for systems with n ≥ 21, and at most about eight minutes for n = 30.Its peak memory reaches 12.4 GB for systems 13 and 21, dominated by the two largest consecutive counting-vector levels, consistent with the O(√n 2^n) bound.Source: G. Results: the MTTF at all states · p. 11, Table II · p. 12
  • For systems with n ≥ 24, counting-vector classes comprise 0.005% to 0.4% of states, letting each failure model’s state MTTFs and policy curve be computed from classes in at most 2.8 seconds.The ungrouped sweep with MTTFs is 1.6 to 6.3 times slower for n ≥ 21 and can take up to 51 minutes for n = 30.Source: G. Results: the MTTF at all states · p. 11, Table II · p. 12

H. Results: the MTTF-threshold policies

  • Threshold cost is not generally convex or unimodal: among 20,925 combinations with at most 10,000 breakpoints, 74% had a breakpoint cost exceeding both neighbors.A decreasing-γ search from 1 lost more than 1% against the best threshold in 23% of these combinations, so evaluating all breakpoints was used to guarantee the best threshold.Source: H. Results: the MTTF-threshold policies · p. 11
  • A median 20% cost saving over corrective maintenance and 4.2% over the best r-out-of-n policy were achieved by the best MTTF-threshold policy.It was never worse than the best r-out-of-n policy; the reported median best threshold was γ = 0.69.Source: H. Results: the MTTF-threshold policies · p. 11

I. Results: comparison with the optimal policies

The best MTTF-threshold policy is near-optimal across the evaluated combinations, while the optimal state-based policy often uses which components have failed. Threshold-policy costs can be costly to optimize and are far cheaper to evaluate than the state-based optimum; the conclusions also delimit the algorithm’s scope.

I. Results: comparison with the optimal policies

  • The best MTTF-threshold policy is optimal within 10^-9 in 17% of combinations, with median excess cost 0.36%, 90th percentile 3.4%, and 99th percentile 13%.Across 26,505 combinations, the optimal state-based policy repairs at some but not all states at a given failure count in 95% of combinations; the median number of such levels is 6.Source: §I · p. 12, Table III · p. 13, Figure 5 · p. 13
  • The excess-cost gap generally shrinks as failures become more strongly batched, but grows with system size and can reach 35% in a large, nearly independent-failure case.The 35% example is system 17 under [Exp]; its best r-out-of-n policy costs at least 80% more than the optimal state-based policy.Source: §I · p. 12

J. Computational effort of the policies

  • Once state classes are stored, a failure-model cost curve takes at most 2.8 seconds and serves new cost pairs, while the state-based optimum requires repeated passes over all states.For n = 27, one pass takes 52 seconds; the optimal policy takes a median 197 seconds per cost pair for system 17, and the largest systems were not computed because of runtime and memory demands.Source: J. Computational effort of the policies · pp. 12–13
  • For two configurations, threshold-policy cost curves are piecewise constant and not unimodal, with 54 and 731 breakpoints; in (a), the best threshold policy is within 0.24% of the optimal state-based policy, versus 6.2% for the best r-out-of-n policy.Source: Figure 4 · p. 13

VIII. CONCLUSIONS AND DISCUSSION

  • The algorithm computes per-state signatures and MTTFs with 2^n structure-function evaluations, and its enumeration limits it to a few dozen components.Under the L´evy-frailty Marshall-Olkin model, MTTF monotonicity enables single-pass threshold-policy costing; the study identifies extension to larger systems and other settings as further work.Source: §VIII · pp. 13–14

APPENDIX A PROOFS

The proofs derive state counting information recursively and use it to establish the algorithm’s evaluation cost. They also justify threshold-policy cost calculations and MTTF monotonicity under the L´evy-frailty Marshall-Olkin model.

APPENDIX A PROOFS

  • Each lower sub-state is counted once among the immediate sub-states by choosing which of the shut-off components remains failed.This correspondence underlies the recursion for obtaining a state's counting vectors from those of its immediate sub-states.Source: Appendix A · p. 14
  • The structure function is evaluated once per state, and the all-state computation adds only polynomial work and memory beyond computing the complete-system signature.The proof reduces signature computation to level counts and processes levels in turn, retaining MTTFs and counting vectors for consecutive levels.Source: Appendix A · p. 14
  • For an MTTF-threshold policy, expected time in each eligible state determines cycle duration and failure counts, while the terminal state determines repair cost.The argument also derives corrective-repair probability from transitions out of eligible states.Source: Appendix A · p. 14
  • Coupling residual lifetimes under the L´evy-frailty Marshall-Olkin model shows that a state with fewer working components has no greater MTTF.The proof uses the same residual lifetimes for components shared by the two states and then applies structure-function monotonicity.Source: Appendix A · p. 14

Related papers

Loading 2610.22181v1…