A BRANCH-AND-BOUND ALGORITHM FOR COMPUTING OPTIMAL REPLACEMENT POLICIES IN K-OUT-OF-N SYSTEMS

• 成果类型: Article
• 署名作者: CHUNG, CS; FLYNN, J
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.43.5.826
• 发表日期: 1995
• 页码: 826-837

摘要

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 too 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.