Reliability Design Problem in Dynamic Programming

The reliability design problem is the designing of a system composed of several devices connected in series or parallel. Reliability means the probability to get the success of the device.

Let’s say, we have to set up a system consisting of D₁, D₂, D₃, …………, and D_n devices, each device has some costs C_1, C₂, C₃, …….., C_n. Each device has a reliability of 0.9 then the entire system has reliability which is equal to the product of the reliabilities of all devices i.e., πr_i = (0.9)⁴.  

Serial Combination of one copy of each device

It means that 35% of the system has a chance to fail, due to the failure of any one device. the problem is that we want to construct a system whose reliability is maximum. How it can be done so? we can think that we can take more than one copy of each device so that if one device fails we can use the copy of that device, which means we can connect the devices parallel.

When the same type of 3 devices is connected parallelly in stage 1 having a reliability 0.9 each then:

Reliability of device1, r₁= 0.9

The probability that device does not work well = 1 –  r₁ = 1 – 0.9 = 0.1 

The probability that all three copies failed = ( 1-r₁ )³ = (0.1)³ = 0.001

The Probability that all three copies work properly = 1 – (1- r₁)³ = 1- 0.001 = 0.999

We can see that the system with multiple copies of the same device parallel may increase the reliability of the system. 

Multiple copies of the same device type are connected in parallel through the use of a switching circuit

Given a cost C and we have to set up a system by buying the devices and we need to find number of copies of each device under the cost such that reliability of a system is maximized.

We have to design a three-stage system with device types D1, D2, and D3. The costs are $30, $15, and $20 respectively. The cost of the system is to be no more than $105. The reliability of each device type is 0.9, 0.8, and 0.5 respectively.

Explanation:

Given that we have total cost C = 105, 

sum of all C_i = 30 + 15 + 20 = 65, the remaining amount we can use to buy a copy of each device in such a way that the reliability of the system, may increase.

Remaining amount = C – sum of C_i = 105 – 65 = 40

Now, let us calculate how many copies of each device we can buy with $40, If consume all $40 in device1 then we can buy 40/30 = 1 and 1 copy we have already so overall 2 copies of device1. Now In general, we can have the formula to calculate the upper bond of each device:

U_i   =  floor( C – ∑C_i  / C_i ) + 1    (1 is added because we have one copy of each device before)

C1=30,  C2=15,  C3=20,   C=105
r1=0.9,  r2=0.8,  r3=0.5
u1 = floor ((105-(30+15+20))+1 = 2 
u2 = 3
u3 = 3

A tuple is just an ordered pair containing reliability and total cost up to a choice of m_i’s that has been made. we can make pair in of Reliability and Cost of each stage like _copyS^device

S⁰ = {(1,0)} 

Device 1:

Each Sⁱ from S^i-1 by trying out all possible values for r_i and combining the resulting tuples together.

• let us consider P₁ :
  • ₁S¹ = {(0.9, 30)}  where 0.9 is the reliability of stage1 with a copy of one device and 30 is the cost of P₁.
• Now, two copies of device1 so, we can take one more copy as:
  • ₂S¹ = { (0.99, 60) }  where 0.99 is the reliability of stage one with two copies of device, we can see that it will come as: 1 – ( 1 – r₁ )² = 1 – (1 – 0.9)² = 1 – 0.01 = 0.99 .
• After combining both conditions of Stage1 i.e., with copy one and copy of 2 devices respectively. 

S¹   = { ( 0.9, 30 ), ( 0.99, 60 ) }

Device 2:

S² will contain all reliability and cost pairs that we will get by taking all possible values for the stage2 in conjunction with possibilities calculated in S¹.

First of all we will check the reliability at stage2 when we have 1, 2, and 3 as a copy of device. let us assume that E_i is the reliability of the particular stage with n number of devices, so for S² we first calculate: 

• E₂ (with copy 1) = 1 – ( 1 – r₂ )¹  = 1 – ( 1 – 0.8 ) = 0.8
• E₂ (with copy 2) = 1 – (1 – r₂ )²  = 1 – (1 – 0.8 )² = 0.96
• E₂ (with copy 3) = 1 – (1 – r₂ )³ = 1 – ( 1 – 0.8 )³ = 0.992

If we use 1 copy of P₁ and 1 copy of P₂ reliability will be 0.9*0.8 and the cost will be 30+15

One Copy of Device two , ₁S² = { (0.8, 15) } Conjunction with S¹ (0.9, 30) =  { (0.72,45) }

Similarly, we can calculate other pairs as S²  = ( 0.72, 45 ), ( 0.792, 75), ( 0.864, 60), ( 0.98,90 ) }  

We get ordered pair (0.98,90) in S² when we take 2 copies of Device1and 2 copies of Device2 However, with the remaining cost of 15 (105 – 90), we cannot use device Device3 (we need a minimum of 1 copy of every device in any stage), therefore ( 0.792, 75) should be discarded and other ordered pairs like it. We get S² = { ( 0.72, 45 ), ( 0.864, 60 ), ( 0.98,90 ) }. There are other possible ordered pairs too, but all of them exceed cost limitations.

Up to this point we got ordered pairs:

S¹ = { ( 0.9, 30), ( 0.99, 60 ) }
S² = { ( 0.72, 45 ), ( 0.864, 60 ), ( 0.98,90 )}

Device 3:

First of all we will check the reliability at stage3 when we have 1, 2, and 3 as a copy of device. E_i is the reliability of the particular stage with n number of devices, so for S³ we first calculate: 

• E₃ (with copy 1) = 1 – ( 1 – r₃ )¹  = 1 – ( 1 – 0.5 ) = 0.5
• E₃ (with copy 2) = 1 – (1 – r₃ )²  = 1 – (1 – 0.5 )² = 0.75
• E₃ (with copy 3) = 1 – (1 – r₃ )³ = 1 – ( 1 – 0.5 )³ = 0.875

Now, possible ordered pairs of device three are as- S³ = { ( 0.36, 65), ( 0.396, 95), ( 0.432, 80), ( 0.54, 85), ( 0.648, 100 ), ( 0.63, 105 ) }

(0.648,100) is the solution pair, 0.648 is the maximum reliability we can get under the cost constraint of 105.