A HEURISTIC ALGORITHM FOR DETERMINING REPLACEMENT POLICIES IN K-OUT-OF-N SYSTEMS

The authors study a discrete-time, infinite-horizon, dynamic programmi ng model for the replacement of components in a binary k-out-of-n fail ure 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 avera ge undiscounted cost per period. A companion article develops a branch -and-bound algorithm for computing optimal policies. Extensive computa tional experiments find it effective for k to be small or near n; howe ver, difficulties are encountered when n greater than or equal to 30 a nd 10 less than or equal to k less than or equal to n - 4. This articl e presents a simple, intuitive heuristic rule for determining a replac ement policy whose memory storage and computation time requirements ar e 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 usefulne ss. The authors provide sufficient conditions for it to be optimal and undertake computational experiments that suggest that it handles para llel systems (k = n) effectively and, further, that its effectiveness increases as k moves away from n. In our test problems, the mean relat ive errors are under 5% when n less than or equal to 100 and under 2% when k less than or equal to n - 3 and n less than or equal to 50. (C) 1997 John Wiley & Sons, Inc.