A mission-critical production system has n stages that have to be performed sequ

Question

A mission-critical production system has n stages that have to be performed sequentially; stage i is performed by machine M_i. Each machine M_i has a probability r_i of performing reliably so a probability 1-r_i of failing (and the failures are independent). Therefore, if we implement each stage with a single machine, the probability that the whole system works is r_1 x r_2 x ... x r_n.
To improve this probability, we add redundancy, by having m_i copies of the machine M_i that performs stage i. The probability that all m_i copies of machine M_i fail simultaneously is only (1-r_i)^(m_i), so the probability that the whole system works is sigma(i=1 to n) (1-(1-r_i)^(m_i)). Each machine M_i costs c_i, and there is a total budget B to buy machines (where B and each c_i are positive integers.)

A) Design an algorithm whose input are the probabilities r_1, r_2, ... r_n, the costs c_1, c_2, ... c_n, and the budget B, and computes the redundancies m_1, ... m_n that are within the available budget and that maximize the probability that they system works correctly.

B) Suppose that you have a 5 stage production system with probabilities: r_1 = 0.75, r_2 = 0.85, r_3 = 0.95, r_4 = 0.80 r_5 = 0.77, costs c_1 = 100, c_2 = 225, c_3 = 350, c_4 = 175, c_5 = 150, and the budget B = 6000. Compute the redundancies m_1, ... , m_5 that are within the available budget and that maximize the probability that the system works correctly. What is this maximal probability?

Explanation / Answer

Answer :

Below are some of the choice which we can make as

Intially first , check to see if B is great enough to purchase one of each M_i. If not, then the system will not work and we are done and similarly, if any r_i is zero, then the system will not work and we are done.
Atleast one of each machine must be purchased, B_base = c_i, for i in {1, 2, 3, . . . , n} .Defining B_redundant = B - B_base. This is the remaining budget for we to spend on improving system reliability by adding redundancy.
For our redundancies m = (m_1, m_2, m_3, . . . , m_n), it's clear that each m_i 0. The maximum of each m_i is easy to find as the largest integer that is not more than B_redundant / c_i, often written as floor.
It is clear that we can solve for the optimal m by exhaustive enumeration.For exhaustive enumeration, we run through the feasible combinations of m .For example, if B_redundant is 6 and costs c = (1, 2, 3), then the flexible m are are given in the below table.

(0, 0, 1) dominated
(0, 0, 2)
(0, 1, 0) dominated,
(0, 1, 1)
(0, 2, 0) dominated,
(0, 3, 0)
(1, 0, 0) dominated
(1, 0, 1) dominated
(1, 1, 0) dominated
(1, 1, 1)
(1, 2, 0) dominated
(2, 0, 0) dominated
(2, 0, 1) dominated
(2, 1, 0) dominated
(2, 2, 0)
(3, 0, 0) dominated
(3, 0, 1)
(3, 1, 0)

When we can buy more of any M_i without decreasing the number of some other M_j, then that combination is dominated is as shown above, so we would not need to explore it further since it clearly is not optimal. And we also consider than if any r_i is 1, then that machine will never fail and there will be no benefit to purchasing a redundant or repeated machine for it. As such we can eliminate it from m to decrease the complexity of our evaluations so we don't waste time considering it more.

Also given that perfectly reliable machines do not benefit from redundancy, we might think that imperfect, but highly reliable machines will benefit less from redundancy than low-reliability machines. This principle may give we ideas to improve on finding the optimal m by prioritizing low-reliability machines first.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.