A Branch-and-Bound Algorithm for Computing Optimal Replacement Policies in K -Out-of- N Systems

Chia-Shin Chung and James Flynn
Additional contact information
James Flynn: Cleveland State University, Cleveland, Ohio

Operations Research, 1995, vol. 43, issue 5, 826-837

Abstract: 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 component 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(n k ) . 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 20Mhz 386 microcomputer is 0.106 seconds.

Keywords: dynamic programming/optimal control: Markov decision model; programming branch and bound; reliability; replacement/renewal: multicomponent system (search for similar items in EconPapers)
Date: 1995
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.43.5.826 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:43:y:1995:i:5:p:826-837

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().