This paper presents a branch and bound algorithm for computing optimal replacement policies in a discrete-time, infinite-horizon, dynamic programming model of a binary coherent system with n statistically indpendent components, and then specializes the algorithm to consecutive k-out-of-n systems. The objective is to minimize the long-run expected average undiscounted cost per period. (Costs arise when the system fails and when failed components are replaced.) An earlier paper established the optimality of following a critical component policy (CCP), i.e., a policy specified by a critical component set and the rule: Replace a component if and only if it is failed and in the critical component set. Computing an optimal CCP is a optimization problem with n binary variables and a nonlinear objective function. Our branch and bound algorithm for solving this problem has memory storage requirement O(n) for consecutive k-out-of-n systems. Extensive computational experiments on such systems involving over 350,000 test problems with n ranging from 10 to 150 find this algorithm to be effective when n ≤ 40 or k is near R.
