Question

A mission-critical production system has n stages that have to be performed sequentially; stage i is performed by machine ${\mathbf{M}}_{\mathbf{i}}$. Each machine M_i has a probability ${\mathbf{r}}_{\mathbf{i}}$of functioning reliably and a probability $\mathbf{1}\mathbf{-}{\mathbf{r}}_{\mathbf{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 ${\mathit{r}}_{\mathbf{1}}\mathbf{·}{\mathit{r}}_{\mathbf{2}}\mathbf{·}\mathbf{·}\mathbf{·}{\mathit{r}}_{\mathbf{n}}$. To improve this probability we add redundancy, by having mi copies of the machine M_i that performs stage i. The probability that all mi copies fail simultaneously is only ${\left(1-r_i\right)}^{\mathbf{m}\mathbf{i}}\mathbf{,}$so the probability that stage i is completed correctly is 1 − ${\left(1-r_i\right)}^{\mathbf{m}\mathbf{i}}\mathbf{,}$ and the probability that the whole system works $\mathit{i}\mathit{s}\mathbf{}{{\mathit{\Pi }}^{\mathbf{n}}}_{\mathbf{i}\mathbf{=}\mathbf{1}}\left(1-{\left(1-ri\right)}^{mi}\right)\mathbf{.}$Each machine has a cost ${\mathit{c}}_{\mathbf{i}}$, and there is a total budget to buy machines. (Assume that B and ${\mathbf{c}}_{\mathbf{i}}$are positive integers.) Given the probabilities ${\mathit{r}}_{\mathbf{1}}\mathbf{·}{\mathit{r}}_{\mathbf{2}}\mathbf{·}\mathbf{·}\mathbf{·}{\mathit{r}}_{\mathbf{n}}$, the costs${\mathit{c}}_{\mathbf{1}}\mathbf{,}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{,}{\mathit{c}}_{\mathbf{n}}\mathbf{,}$ and the budget find the redundancies${\mathit{m}}_{\mathbf{1}}\mathbf{,}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{,}{\mathit{m}}_{\mathbf{n}}$ that are within the available budget and that maximize the probability that the system works correctly.

Short answer

Let us first understand the problem clearly:

• We have mission-critical production system in which there are n stages of work. The work of each stage is performed in sequential manner where machine_{${\mathrm{M}}_{\mathrm{i}}$} will do stage i work.
• Each machine_{${\mathrm{M}}_{\mathrm{i}}$} has probability reliability of $r_i$, and${\left(1-r_i\right)}^{mi},$ is the probability of failure.
• If all work is implemented on a single system, then will be the probability of complete system.
• Each machine has the cost c_i and total budget.
• We need to find the redundancy${\mathrm{M}}_{\mathrm{i}}$ so that we do work within the budget Band maximum reliability.

The probability that the whole system works$is{{\Pi }^n}_{i=1}\left(1-{\left(1-ri\right)}^{mi}\right).$

Step-by-step solution

Approach

First, we will compute left over budge${\mathrm{B}}_{\min }=\left\{{\mathrm{c}}_1+{\mathrm{c}}_2+\dots .+{\mathrm{c}}_{\mathrm{n}}\right\}.$ This can be distributed over N stages with its cost. we implement each stage with a single machine, the probability that the whole system work${\mathrm{r}}_1·{\mathrm{r}}_2···{\mathrm{r}}_{\mathrm{n}}$.

For this we will use Knapsack Algorithm with repetition so we can computer remaining budget by simply subtracting B-B_min. many of each machines copy do we need. For this we have to count the number of copies of each machine that we need.

Algorithm

In this we take array $\mathrm{counts}\left[{\mathrm{m}}_1{\mathrm{m}}_2\dots .{\mathrm{m}}_{\mathrm{n}}\right]$

So, size of $arraycounts=n$and initially, all value is$1incounts\left[\right]$

$\begin{array}{l}for\left(w=1to\left(B-B_{min}\right)\right)\\ \begin{array}{l}\\ value\left(w\right)=0\end{array}\\ \begin{array}{l}\\ for\left(i=1ton\right)\end{array}\\ \begin{array}{l}\\ if\left(c_i<w\right)\end{array}\end{array}$

$\begin{array}{l}c=counts\left(w\right)\circledR counts\left(w-c_i\right)\&i=i+1\\ \begin{array}{l}\\ v=value\left(c\right)\end{array}\\ \begin{array}{l}\\ if\left(v>value\left(w\right)\right)\end{array}\\ \begin{array}{l}\\ value\left(w\right)=v\end{array}\end{array}$

$\begin{array}{l}\begin{array}{l}counts\left(w\right)=c\\ \end{array}\\ returncounts\left(B-B_{min}\right)\end{array}$

Thus, we compute and store it. Each machine_{$M_i$} has probability reliability of $r_i$, and${\left(1-r_i\right)}^{mi},$ is the probability of failure. If all work is implemented on a single system, then$r_1·r_2···r_n$ will be the probability of complete system. Each machine has the cost c_i and total budget. We need to find the redundancy so that we do work within the budget Band maximum reliability. And the probability that the whole system works$is{{\Pi }^n}_{i=1}\left(1-{\left(1-ri\right)}^{mi}\right).$