This article presents a heuristic algorithm for determining replacement policies in a discrete-time, infinite-horizon, dynamic programming model of a binary coherent system with n statistically independent components, and then specializes the algorithm to consecutive k-out-of-n systems. Costs arise 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 on consecutive k-out-of-n systems find it effective when n ⩽ 40 or k is near n; however, the computations can be intractable when n > 40 and 2 ⩽ k < n – 15, suggesting the need for a good heuristic. Computational experiments on consecutive k-out-of-n systems involving over 300,000 test problems find the heuristic of this article highly effective. For each n and k tested, its percentage error was under 2.53%, and its mean computation time on a 1700 MHz Pentium IV was under 0.24 s (the largest n in our experiments was 200).
