Circuit Reliability Design as a dynamic programming problem by Tony C. Smith -------------------------------------------------------------------- The simplest form of a multi-stage circuit (i.e. a circuit where all stages are connected in series) is where each stage has one device. If d_i is the i-th device, and the reliability of d_i is r_i and the cost of one d_i is c_i, then an n-stage circuit must have (minimum cost) C_min = SUM_(1<=i<=n) c_i and its reliability is equal to the probability that any one device fails, which is (circuit reliability) RR_n = PROD_(1<=i<=n) r_i Each stage can be made more reliable by adding copies of the device in parallel, such that if any one device in that stage fails there is another to fulfill the function. Now the reliability of that stage (sr_i) is equal to the probability that all copies of the device fail simultaneously, which is (stage reliability) sr_i = 1 - (1-r_i)^m_i where m_i is the number of devices in the stage. Obviously the circuit reliability computed as R_n = PROD_(1<=i<=n) sr_i The goal now is to maximize R_n subject to the constraint of some budget C (that is, the maximum allowed cost). The number of additional devices that can be added to any one stage is at most equal to u_i = 1 + (int)[(C - C_min)/c_i] That is, u_i is an upperbound for m_i. The goal in solving the circuit reliability problem is to find the set {m_1, m_2, ... m_n} that maximizes R_n given C. A dynamic programming solution is possible because the principle of optimality holds. As in the knapsack problem, when the decision is being made about which last device to add for the finished circuit, the solution is comprised of the best solution found so far for either 1) the same budget with one-fewer device types to consider, or 2) a budget with enough money left over to buy one more of the currently available device types. If there are i device types available, then S_i,j is the set of decisions available to us when we can have m_i = j. That set only includes decisions that are still viable (i.e. haven't been ruled out because of available options) after considering i types of devices. Thus the solution for S_i,j is going to be either the best one found for S_(i-1), or S_i,j-1 plus one more device of type d_i if we can afford it. Put another way, we start considering all 1<=j<=u_1, m_1=j for {m_1,m_2=1,....,m_n=1} before considering options for m_2.