So I am working on this problem: A mission-critical production system has n stag

Question

So I am working on this problem:

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 functioning reliably and 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,r_2,...,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 fail simultaneously is only (1-r_i)^(m_i), so the probability that stage i is completed correctly is 1-(1-r_i)^(mi) and the probability that the whole system works is prod(i=1,n){1-(1-r_i)^(m_i)}. Each machine M_i has a cost c_i, and there is a total budget B to buy machines. (Assume that B and c_i are positive integers.) Write the algorithm in java code that given probabilities r_1,...,r_n, the costs c_1,...,c_n, and the budget B, finds the redundancies m_1,...,m_n that are within the available budget and that maximize the probability that the system works correctly (determine the maximum reliability achievable). Also, show how many machines of each type achieve that reliability bound within the budget.

So I read in a file that gives me the total budget allowed, followed by the number of machines, and then for each machine I read in the cost and the reliability. I store the cost and and reliability into two linked list (not sure if this is best).

try {
BufferedReader newFileBuffer = new BufferedReader(new FileReader(inputFile));
               budget = Integer.parseInt(newFileBuffer.readLine());
               numberOfMachines = Integer.parseInt(newFileBuffer.readLine());
               while ((fileLine = newFileBuffer.readLine()) != null)
               {      
                   line = fileLine.split(" ");
                  
               try
               {
                   cost.add(Integer.parseInt(line[0]));
                   totalCostOfOneEach += Integer.parseInt(line[0]);
                   reliability.add(Float.parseFloat(line[1]));
               } catch (NumberFormatException nfe) {};
                  
               }
               newFileBuffer.close();
           } catch (Exception e)
           {
               e.printStackTrace();
           }

From there I know that one of each machine must be used once so I subtract the budget by the total amount it cost for one of each machine (totalCostOfOneEach), this gives me left over budget or the redundancy budget if you will.

bRedundent = (budget - totalCostOfOneEach);
Now is where I am stuck, I am lost on what to loop over to find the solution. I have researched and found this http://cs.stackexchange.com/a/6734/46973 but I do not understand the line

Pr(b,j)=max{Pr(b-c_j*k, j-1)*(1-(1-r_j)^k}

So what I do know is I have created a double array and I initialize the arrays as so:

double[][] finalRel = new double[numberOfMachines][bRedundent];
   for (int j = 0; j < numberOfMachines; j++)
   {
       finalRel[0][j] = 0;
   }
      
   for (int b = 1; b < budget; b++)
   {
       finalRel[b][1] = reliability.get(0);
   }

Now is where I am stuck, I believe I should loop on the number of machine and then the cost but this is not working and I know I need incorporate the budget somehow. So this is what I currently have that does not work at all:

for (int i = 1; i < numberOfMachines; i++)
{
for (int c = cost.get(i); c < budget; c++)
       {
           finalRel[i][c] = Math.min(finalRel[i-1][c], finalRel[i-1][c - cost.get(numberOfMachines)]*(l));
       }  
   }

I know the subproblem is denoted finalRel[i, b], the most reliable configuration of machines 1, 2, . . . , i (at least one of each machine) available within budget b. The desired answer will be finalRel[n, B].

I realize this a lot of information but I have been stuck for a while now so any help is appreciated.

Explanation / Answer

I think you are proceeding in the right way and the reliability always to be maintained greater than zero

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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