A branch-and-bound algorithm for computing optimal replacement policies in K-out-of-N systems

A branch-and-bound algorithm for computing optimal replacement policies in K-out-of-N systems

0.00 Avg rating0 Votes
Article ID: iaor19982109
Country: United States
Volume: 43
Issue: 5
Start Page Number: 826
End Page Number: 837
Publication Date: Sep 1995
Journal: Operations Research
Authors: ,
Keywords: programming: dynamic, programming: markov decision, programming: branch and bound
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 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)(nk + 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.

Reviews

Required fields are marked *. Your email address will not be published.