Reliability Design–0/1 knapsack Application

What is 0/1 Knapsack in short 

you are given a

1)bag (knapsack)

2)weights (W i) of  ‘n’ items  e.g:-[10,20,30,40…]

3)values (V i) of above ‘n’ items e.g:-[50,60,70,80…]

4)capacity (C) (an integer) of knapsack

Now fill the bag with the given weights(either pick the whole item (1) or don’t pick any item (0) [i.e 0/1 knapsack] such that total weight of picked items is less than equal to the capacity of knapsack and maximizing total sum of values(i.e can be said as profits).

in short

Σ 1*(Vi)  is maximum

Σ 1*(Wi) <=C 

here 1*Vi and 1*Wi because this is for 0/1 knapsack [i.e no fractional parts are possible like we do in knapsack problem using greedy algo]

-this can be done using DP

In case of knapsack (greedy)

Σ (Vi)*(Xi) is maximum

Σ (Wi)*(Xi) <=C

where Xi is fraction of the given weight

the only difference in case of both knapsacks is in case of greedy we are provided by weights or stuff that can be divided into parts(like some chemicals like sugar etc…)where as in  0/1 we are given with elements or weights which cannot be splited(e.g:-devices like servers or some solid devices or solid stuff)

Reliability Design what is it ?

your given with number of devices to be connected in series and are asked to find out the reliability of the above system(i.e chain of devices)

if  Ri is the reliability of single device let it be ‘0.9’  (i.e out of 1)

then the reliability of system is  (πRi) i.e (0.9*0.9*0.9….n)

if n= 10 devices then above answer would be 0.94  which is very less when compared to individual device (in fact it is unexpecting because individual reliability is 0.99

So our task is to design a system to maximize the system reliability(i.e on whole) 

Now we shall instead of  connecting devices in series try for a new approach

From above discussion it is advisable to duplicate devices.Multiple copies of same device type are connected in parallel through the use of switching circuits.the switching circuits determine which devices in any given group are functioning properly.then they make use of such devices at each stage.


Layman Terms:-

consider you need to establish a data-center(just imagine :p) so you need to buy servers (storage systems) so you will do a survey of list of available company’s , their costs

let us assume you finalized three types of storage devices of 3 companies (A,B,C) and costs of each storage device is (5000$ ,5500$ , 6000$)  { mind that you have chosen three same in functioning devices but you may pose a question that why don’t you choose a low cost company product but some products may have some features which other doesn’t have like our smart phones even though all are just phones }

We require many storage devices (like may be 100  because u r planning data-center :p )


As shown above in stage 1 you will have all devices of A company and in stage 2 B ‘s devices and in stage 3 all C’s devices

If stage i contains Mi copies of Company (only A or only B or only C) then the probability that all Mi have malfunction is (1-Ri) ^ (Mi)  { where ^  means power}

                    Note:- here we may connect similar company devices in one stage using switching circuits 

then reliability of stage i becomes  1- ((1-Ri) ^ Mi)  [ careful 1-Ri means malfunction of a device]

thus now if Ri is 0.99 and Mi (i.e number of devices of a particular company ) is 2 then  stage reliability becomes 0.9999.

Now in our example there are 3 such stages therefore whole system reliabilty now becomes 0.9999 * 0.9999 * 0.9999 = 0.99970003  (if you remember previously when all devices were connected in series it was 0.904 only but now magic :p

but not always in this technique the reliability will be 0.99970003 because switching circuits they themselves may be some less reliable. but is much efficient than series connections.

Let  ∅i(Mi)  is a function which gives  the reliability of a stage which is dependent on number of devices in that stage(Mi) i.e instead of  1- ((1-Ri) ^ Mi)

therefore our aim is :-

 π (∅(Mi))  is to be maximized ,       and

Σ (Ci)* (Mi) <=C

where Ci is cost of i th device and C is your budget (i.e permissible cost)

This can be solved using Dynamic programming  0/1 Knapsack method


                                    In Knapsack —Here

knapsack capacity (C) –budget (permissible cost C)

sum of values must be maximized—system reliability is to be maximized

Mi is weights —Mi is devices


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s