A heuristic algorithm for determining replacement policies in k‐out‐of‐n systems

The authors study a discrete‐time, infinite‐horizon, dynamic programming model for the replacement of components in a binary k‐out‐of‐n failure system. (The system fails when k or more of its n components fail.) Costs are incurred when the system fails and when failed components are replaced. The objective is to minimize the long‐run expected average undiscounted cost per period. A companion article develops a branch‐and‐bound algorithm for computing optimal policies. Extensive computational experiments find it effective for k to be small or near n; however, difficulties are encountered when n ≥ 30 and 10 ≤ k ≤ n − 4. This article presents a simple, intuitive heuristic rule for determining a replacement policy whose memory storage and computation time requirements are O(n − k) and O(n(n − k) + k), respectively. This heuristic is based on a plausible formula for ranking components in order of their usefulness. The authors provide sufficient conditions for it to be optimal and undertake computational experiments that suggest that it handles parallel systems (k = n) effectively and, further, that its effectiveness increases as k moves away from n. In our test problems, the mean relative errors are under 5% when n ≤ 100 and under 2% when k ≤ n − 3 and n ≤ 50. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44, 273–286, 1997.