We study a discrete time, infinite-horizon, dynamic programming model for the replacement of components in a binary coherent system with n components. Costs are incurred when the system fails and when failed components are replaced. The objective is to minimize the expected discounted infinite-horizon cost or the long-run expected average undiscounted cost per period. An earlier paper found general conditions under which it is optimal to follow a critical component policy (CCP), i.e. a policy specified by a critical component set and the rule: Replace a componnet if and only if it is failed and in the critical component set. Computing an optimal CCP is a binary nonlinear programming problem in n variables. This paper specializes to k-out-of-n systems and develops a branch-and-bound algorithm for finding an optimal decision. Its memory storage requirement is O((n + 1)(n – k + 1)), and the number of nodes examined is under O(nk). Extensive computational experiments with n ranging from 10 to 100 find it to be effective when k is small or near n. In our 120,000 test problems with k = n (parallel systems), the average computation time on a 20 MHz 386 microcomputer is 0.106 seconds.