4.8 Reliability Design - Dynamic Programming

the problem has a reliability design in this video I'll explain you what the problem is then I'll take a example problem from the textbooks mostly found in the textbook then I'll explain how to solve that problem first of all let us understand what the problem is see the problem is we have to set up our system set up our system a system consists of some devices let us say d1 d2 d3 d4 I have some devices and have to take this dividers and set up a system for example I have to set up a studio for that I need a board and the camera and the batteries and lights and markers these things I need in the setup so let us call them as devices now each device is having some cost say there is some cost cost 1 cos 2 cos 3 and gospel and each device is having some reliability means what is the probability of working good like board that reliability is high lights the reliability is low they may go off and the marker the reliability is much lower it may dry up select that what is the chances that it works perfectly that is called as a reliability so each device is having some reliability now what the problem is see the reliability of devices may vary suppose the reliability of hdy was 0.9 each device is 0.9 then what is the reliability of an entire system that is product of all the reliability so it is 0.9 power 4 this is 0.65 6 1 see though the reliability of each device is 0.9 but the reliability of entire system is 0.65 means there are 35% chances of that system may fail so it means if I talk about the studio setup so I have to stop recording because of any of the reason that sargon or the camera is not working or marker is a tried so this could be the reasons I have to stop my recording so there are 35 person chances 65% chances it works perfectly so I have to improve my system and the problem is I want to set up a system such that the reliability is maximum so what I should do I should have more than one copies of markers or I should have more than one cameras I should have more than one lights see if one camera is off or gone damaged then I should use another camera in its place if the light is gone because of fluctuation then I should have another set of lights for continuing my recording so that's it so I should have the multiple copies of these devices we will call these that these devices are connected in series so now we should have the devices connected in parallel so same copies multiple copies of first device and multiple copies of second device so I should have multiple copies so we say that these are stages at each stage stage 1 and stage 2 stage 3 stage 4 at each stage we'll have the multiple copies where one of the copy may be working the rest of the copies will be acting as backup if this fails then this will continue working in its place so we say they are in parallel and the system is designed with taking parallel copies of devices so what is the meaning here so that is I should have the multiple copies of marker or I should have multiple copies of Lights that is the meaning then if I have multiple copies whether the reliability of each will increase now let us see how to know whether the reliability of this stage has improved or not so I am having three copies the reliability of each device is 0.9 if I have three copies what will be there Allah of the stage so let us learn how to calculate the reliability of a stage see for the first device the probability of working wood is 0.9 then 1 minus r1 that is the probability of not working wood as 0.1 then I have 3 copies of this one see I have 3 copies here so for 3 copies what is the probability that all three copies has failed so all three copies has fail means point power 3 then this will be point zero zero one this is the probability that all three copies have failed then 1 minus 1 minus r1 to the power of 3 gives me the probability that three copies are working perfectly so that is 0.999 see there is a much improvement in the reliability it was just 0.9 now the reliability of first stage is 0.99 9 now finally it means that if I have multiple copies of the same device then the reliability of the system entire system may increase and we want maximum reliability so for that I should have the extra amount with me the extra capital for buying multiple copies so now the actual problem is if I have some cost with me C is the cost the total amount in my hand and I have to set up a system by buying these devices and connecting them so these devices how many copies of each device I should buy if within that cost such that the total reliability of the system is maximized this is the problem now let us take an example problem and solve it now here is an example I have three devices and the cost of the devices is given let us say that is in dollars thirty dollars fifteen and twenty dollars and the reliability of the devices is also given that is point nine point eight and 0.5 then UI is the upper bound so let us understand what this upper bound is see we are trying to set up a sister by taking multiple copies so at least one copy I must take so for each device I must take C 1 plus C 2 plus C 3 that is sum of C I I should take one copy of each so that is 30 plus 15 plus 20 so this will become $65 so definitely I should take one copy of each device then the remaining amount I can spend for buying multiple copies of other devices so what is the remaining amount so actual cost is given as C so C minus sum of all CI is the remaining amount this is remaining so what is remaining one not five minus sixty five as forty so $40 sorry meaning and in that $40 how many copies of first device I can take how many I can take some second device for how many third like that I have to calculate so maximum how many copies I can take for each device so in this fifth 40 I can spend all 40 dollars on the first device only so how many copies I can take so 40 divided by 30 so I can take just one copy and this one so I can take one extra copy already one copy I said I must take it so how to know this now let me take it as a formula this is the remaining amount in that I have to divide it by CI the cost of that device and I should take the floor value plus one copy which I am already taking plus one so this result the remaining amount is $40 and this is $30 this is one then plus 1 so upper bound is 2 so I can take two copies of this device this is how we use the formula to find out in the remaining amount how many copies of each device I can take let us do it for the second device see $40 is remaining and the $15 is this one so I can take two copies and plus that is already there so three copies I can take and similarly this I can take for the third device I can take 40 by 20 so two copies and plus one copy that I am already having so three copies I can take so this means that this gives the upper bound of any device how many extra copies I can take this is the formula so I have upper bounds for all this means that after taking one one copy of each by spending sixty five dollars in the remaining $40 if I spend all $40 on first device I can take two copies the first actually one I am taking plus one copy if I spent everything on second device then total how many copies of second device the one already we are taking here then remaining two more copies then likewise total three copies in so we have the upper bond for each now we have to find out how many copies of each device we should take such that the reliability of a system is maximized that's all about the problem I have explained you about the problem now how to solve it is just like the set method of zero-one knapsack problem now I will show you how to solve this one for solving this problem we will take a set of order pair so each order pair will have a reliability and the cost now first order page first said set a 0 this will be having ordered pair 1 and cost is 0 see so far nothing I have spend I have not purchased anything there is no system at all so right now the reliability is 1 starting because reliability will multiply if I take 0 then the entire answer will be 0 so that's why we take reliability as fun now let us start consider d1 if I consider first device then how many copies I can take I can take 2 copies if I take only one copy of our device then what happens first device one copy device and the copy so reliability is 0.9 multiplied by this one 0.9 and the cost will be how much 30 $30 added so if I take just one copy of the first device then the reliability will be 0.9 that is multiplied and the cost is added I can take two copies there so I will prepare one more set two copies of first device if I take two copies of the device then what will be the reliability of a stage so you remember we have calculated this one for first stage two copies we are taking so this is 1 minus 1 minus 0.9 whole square so this is 1 minus 0.9 this is point 1 whole square 1 minus 0.01 and the reliability is 0.99 so this is 0.99 multiplied by 1 so we get the same thing and we are taking 2 copies so this will be 16 then combine these two and form set 1 so this set 1 is for first device so what are the possibilities we have 0.9 and $30 and 0.99 and $60 if I take one copy if I take two copies that's all this is the consideration of facet device now I will do the same thing for second device let us see consider d2 for second device so I have to prepare this sets now second device one copy if I take second device one copy what is the reliability 0.8 and the cost is 15 so that point 8 and cost 15 I should multiply with these to order pairs point 8 into 0.9 so this is 0.72 and the cost is 30 and this is 15 dollars so this will be 45 comma then with this also I should multiply that is point 8 into point 9 nine point seven nine two and the cost of this device is 15 so 15 added to this will be $75 this is one copy we have taken now actually we can take three copies let us take a second copy so if I take two copies of this one first of all let me calculate the reliability of this stage if there are two copies eientei it is the reliability if there is only one copy then if there are two copies I will calculate here one minus one minus reliability of second device two copies and this will be one minus one minus 0.8 whole square one minus this will be point two whole square so this will be 1 minus 0.04 this will be zero point nine six so I am taking two copies so the cost will be $30 so 0.96 and 30 I should multiply and add with these two order page so 0.9 into 0.96 will be point eight six food and the cost that is $30 and this is $30 so it will be $60 then next one is throw into nine six with this one this one so 0.96 into point nine nine point nine five zero four and the cost will be sixty plus 30 90 so two copies I have taken now one thing to observe here see when I have two copies the total cost is $90 I am having and one not $5 $95 gone remaining $15 now if I take this that is two copies of second device then coming purchased her device do I have that remaining amount or not five minus 90 15 $20 I need $20 in my hand so based on that this order Pierre will become infeasible so we can cut off this one I'll just strike off this one so installs calculating the reliability I could have done it directly just by checking the cost so from now onwards first we will find cost then we will multiply the reliability so that we can save some calculations now next three copies are possible so I should take the thread copy so second device third copy so let us see what is the reliability and what is the cost so this will be three copies and this is free copy so this is three so this is zero eight so this is nine nine two and if we have three copies of fifteen this is 45 so I should multiply 0.99 two and add fortify in both these order pair this is the result coming from first device so let me check by adding 45 plus 30 it will be 75 yes we'll be having remaining amount to buy this one so this is 75 and point two nine nine two into point nine eight nine - eight then one more this I should multiply an ad with this one 16 plus 45 it will be one not five so I cannot buy the third device so no need of this ordered pair so cut off this one so I am NOT calculating it also then I have set to this said to is how many order pairs it is having one two three four so I'll be reading four ordered pairs so the order page that we got from the second device are 0.72 for 50.7 nine seven five and 0.864 60 and 0.89 to 875 now I have to calculate for third device also but there is no space so what I will do is I will rewrite this one in smaller size so that we get some free space here so that is the last step remaining so let me rewrite this again with smaller size so I have changed the size here I am made a little small see this is set 0 this is for first device 1 copy 1 copy 2 copies and this is the combined form of this one merged of this one then second device first copy to copy and 3 copy 3 copies are there so then remaining whatever the other place we got we have taken now one thing we have to do here see reliability is 0.72 cost is 45 7 9 so from 7 to 2 7 9 it is increasing reliability increasing cost is also increasing 35 30 dollars are added to this one now 7 9 10 8 6 so the reliability is increasing reliability is increasing but the cost is from 75 to 60 how come the reliability increases only if you spend extra money but here you are editing the amount and the reliability is increasing this is wrong so reliability increases cost should also increase otherwise you have to cut off one order pair by applying dominance rule and the dominant rule says that the first one with higher costs you remove it remove this ordered pair based on the dominance rule this order paid is gone so now we are having just three ordered pairs now let us start working on third device and the third device b3 first copy one copy so s3 one copy so what is the reliability of this third device point 5 and the cost is 20 so multiply with all these three so the first one the reliability is point 5 is multiply so this is 0.36 and the COS 45 plus $20 is 65 and the second this is not there this is 0.864 into 0.5 as a point 4 3 2 and the cost is 60 plus 20 this is 80 then 0.89 2 8 into 0.5 s 4 4 6 4 and the cost is 20 plus 75 this is $95 this is when we are taking one copy off at her device now I should take two copies of the third device so for that I should calculate its reliability so the reliability of third device is 0.9 but if I have two copies how much it will be this is our 3 power 2 so this will be 1 minus 0.5 square so this is 1 minus 0.5 whole square this is 1 minus 0.25 this is 0.75 is the reliability of 2 copies and the cost will be $40 now these are the things multiplied with this and add 40 so one thing I told you that see the total cost notice we are on the third device lastly there is nothing remaining so the total cost should not exceed 1 not $5 0.75 into 0.72 this will be 5 4 and the cost is $45 plus 40 this will be $85 this is the time now next is 0.864 into 0.75 this is 6 for 8 and the cost is 60 plus 40 hundred dollars now the last one is $75 plus $40 this will be it will be 1 $15 so this one $15 will exceed the we have so no need to calculate the reliability and this will be gone like I told you it should be feasible within the given amount so that is gone now I have to take third set three copies so three copies means this will be Q this will be Q and this is Q so this is 0.125 and this will be eight seven five and this will be 40 plus forty three times this is $60 now $60 is their $60 in this one yes we can add some point seven two into 0.875 this will be six three and the cost is 45 plus sixty this is one not five and sixty plus sixty one twenty this is not possible so don't take this then 75 plus sixty this is not possible this is 135 don't take this so we are left with only sixty three point one not five only this ordered pair now set three that is formed is Marge all these and purge also so I will write on 0.366 five point zero three 280 point four four six four nine five see reliability is increasing cost is also increasing reliability increasing yes perfect then eight five so shall I take eight five point five four eight five see the reliability is increasing but the cost is decreasing so this will go away then 0.64 first comes what 6 3 then 6 4 so first is 0.6 a three and one not 5 then the last one is 0.64 so i have to take them in order point 6 4 8 comma hundred comma hundred see 63-64 this is increasing and the cost is one not five 200 decreasing so this is also gone so the order is that are remaining are this one two three and four now if you have the final order pay for three divisors at the third stage so what is the maximum reliability I am getting here that is 0.6 for 800 so the reliability of system that can be maximum is 0.64 8 and the cost will be 100 so this is the final answer now the question is how many copies of each device I should purchase now so for that I get done so like this this ordered pair 6 for 800 where we got it see we have merge these three and we got this one so that was here here so it means I should take two copies of device 2 3 so device 3 I should take 2 copies because I got dancer here and this we got it by multiplying with these ordered pairs first one was with one this one and the second one was with this one so this ordered pair see the reliability of two copies and the cost is multiplied and added we got this one so it was done from here this we got where here so this is here right so this is also for two copies of second device two copies then this regard by multiplying which one see we multiply these two and got these two answers right this was multiplied with this one so this is from coming from this and this we obtain where here so this is just one copy of first device so the answer is first device one copy second device two copies third device two copies and the cost of the system and the reliability will be this one this is the reliability and this is the cost of a system product of reliability and the summation of so the reliability is this one and the cost is hundred right total reliability of the system so we have improved the reliability of entire system if we don't take the multiple copies then the reliability will be less when we have taken multiple copies the reliability has improved that's all with the reliability design it is same as zero and knapsack problem I did not make this because there are a lot of calculations so just it is nothing but calculations only but this is little difficult for the students so I have prepared the video so if you face any difficulty let me know I will prepare another video for this one

Channel: Abdul Bari

Views: 168,420

Rating: 4.893959 out of 5

Keywords: reliability design, system design, dynamic programming, algorithms, algorithm, abdul bari, bari, gate

Id: uJOmqBwENB8

Length: 26min 31sec (1591 seconds)

Published: Wed Apr 11 2018