Algoritmo Rushdi Optimizado Software RMES

Centro de Desarrollo de Gestión Empresarial. Poniente 1206 – Viña del Mar, Chile. Fono:(56) (32)688987 – Fax:(56) (32)2684079 empresa@mes.cl

Noviembre, 2009

1. Introducción

Este algoritmo es usado para el cálculo de confiabilidad de sistemas en redundancia o fraccionamiento. Estos sistemas se conocen como k-out-of-n:G, lo cual significa que el sistema funciona sí y sólo sí k de sus n componentes están operativos. La nomenclatura complementaria, k-out-of-n:F, se refiere a que el sistema falla sí y sólo sí k de los n componentes fallan. RMES utiliza la primera definición.

El presente trabajo utiliza las definiciones existentes en el documento ”Algoritmo Rushdi”, por lo cual, es necesario leer este documento antes de abordar el actual.

2. El algoritmo optimizado

Para implementar una optimización del algoritmo original, es necesario comprender a cabalidad el original.

Para ello se explicará el algoritmo de forma gráfica, de modo de entenderlo paso a paso. Por ejemplo, digamos que se tiene un subsistema 3-out-of-4:G. Supongamos que los valores de la confiabilidad de los 4 subsistemas se conocen y se almacenan en el vector ”P”:

P = [ p_{0} p_{1} p_{2} p_{3} ]

El algorimo original crearia la siguiente matriz A:

A = ( \begin{matrix}0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{matrix} )

2 EL ALGORITMO OPTIMIZADO  RMES

Y luego igualaria la primera fila a 1.

A = ( \begin{matrix}1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{matrix} )

Luego, se comenzaria por calcular la celda a_{1,1} usando los valores de las celdas a_{0,0} y a_{1,0} junto con el valor p_{0} del vector:

a_{1,1} = p_{0} · a_{0,0} + (1 − p_{0}) · a_{1,0}

Notar que a_{0,i} = 1 y a_{1,0} = 0, por lo tanto, para este caso particular a_{1,1} = p_{0}

A = ( \begin{matrix}a_{0,0} & 1 & 1 & 1 & 1 \\ a_{1,0} & a_{1,1} & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{matrix} )

Continuando con el algoritmo, se procede a calcular la siguiente celda, a_{1,2}, el cual se obtendra de las celdas a_{0,1} y a_{1,1} junto con el valor p_{1} del vector:

a_{1,2} = p_{1} · a_{0,1} + (1 − p_{1}) · a_{1,1}

A = ( \begin{matrix}a_{0,0} & a_{0,1} & 1 & 1 & 1 \\ a_{1,0} & a_{1,1} & a_{1,2} & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{matrix} )

Finalmente las ultimas celdas se calcularian de la siguiente manera:

a_{1,3} = p_{2} · a_{0,2} + (1 − p_{2}) · a_{1,2}
a_{1,4} = p_{3} · a_{0,3} + (1 − p_{3}) · a_{1,3}

A = ( \begin{matrix}a_{0,0} & a_{0,1} & a_{0,2} & a_{0,3} & 1 \\ a_{1,0} & a_{1,1} & a_{1,2} & a_{1,3} & a_{1,4} \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{matrix} )

En la siguiente iteración, el calculo comienza en la celda a_{2,2} y algoritmo es idéntico:

a_{2,2} = p_{1} · a_{1,1} + (1 − p_{1}) · a_{2,1}

A = ( \begin{matrix}a_{0,0} & a_{0,1} & a_{0,2} & a_{0,3} & 1 \\ a_{1,0} & a_{1,1} & a_{1,2} & a_{1,3} & a_{1,4} \\ 0 & a_{2,1} & a_{2,2} & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{matrix} )

a_{2,3} = p_{2} · a_{1,2} + (1 − p_{2}) · a_{2,2}

A = ( \begin{matrix}a_{0,0} & a_{0,1} & a_{0,2} & a_{0,3} & 1 \\ a_{1,0} & a_{1,1} & a_{1,2} & a_{1,3} & a_{1,4} \\ 0 & a_{2,1} & a_{2,2} & a_{2,3} & 0 \\ 0 & 0 & 0 & 0 & 0 \end{matrix} )

Centro de Desarrollo de Gestión Empresarial. Poniente 1206 – Viña del Mar, Chile. Fono:(56) (32)688987 – Fax:(56) (32)2684079 2

a_{2,3} = p_{4} · a_{1,3} + (1 − p_{3}) · a_{2,3}

A = ( \begin{matrix}a_{0,0} & a_{0,1} & a_{0,2} & a_{0,3} & 1 \\ a_{1,0} & a_{1,1} & a_{1,2} & a_{1,3} & a_{1,4} \\ 0 & a_{2,1} & a_{2,2} & a_{2,3} & a_{2,4} \\ 0 & 0 & 0 & 0 & 0 \end{matrix} )

Y en la siguiente y última iteración el calculo comienza en la celda a_{3,3} hasta llegar a la celda a_{3,4}, valor que retorna el algoritmo.

a_{3,3} = p_{2} · a_{2,2} + (1 − p_{2}) · a_{3,2}

A = ( \begin{matrix}a_{0,0} & a_{0,1} & a_{0,2} & a_{0,3} & 1 \\ a_{1,0} & a_{1,1} & a_{1,2} & a_{1,3} & a_{1,4} \\ 0 & a_{2,1} & a_{2,2} & a_{2,3} & a_{2,4} \\ 0 & 0 & a_{3,2} & a_{3,3} & 0 \end{matrix} )

a_{3,4} = p_{3} · a_{2,3} + (1 − p_{3}) · a_{3,3}

A = ( \begin{matrix}a_{0,0} & a_{0,1} & a_{0,2} & a_{0,3} & 1 \\ a_{1,0} & a_{1,1} & a_{1,2} & a_{1,3} & a_{1,4} \\ 0 & a_{2,1} & a_{2,2} & a_{2,3} & a_{2,4} \\ 0 & 0 & a_{3,2} & a_{3,3} & a_{3,4} \end{matrix} )

De todo el proceso se pueden desprender que en cada paso unitario del algoritmo se necesita únicamente saber el valor de la celda superior izquierda y de la celda inmediatamente izquierda respecto de la actual. Mientras el algoritmo avanza, los valores que se calcularon para las primeras filas no se vuelven a utilizar. Esto lleva a pensar de que sólo es necesario utilizar un vector de tamaño n (la cantidad de subsistemas hijos) que almacene los valores por cada iteración.

Teniendo presente este esquema, es necesario aislar la primera iteración del resto, debido a que los valores iniciales de las celdas superiores deben ser igual a 1, lo que implica que la fórmula puede ser modificada para este caso particular.

Ubicaremos gráficamente un vector V dentro la matriz A para observar el comportamiento del algoritmo modificado. El vector V almacenará los valores del algoritmo.

V = [ v_{0} v_{1} v_{2} v_{2} ]

A = ( \begin{matrix}1 & 1 & 1 & 1 & 1 \\ 0 & v_{0} & v_{1} & v_{2} & v_{3} \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{matrix} )

Para la primera iteración se cumple que a_{0,i} = 1, por lo tanto la fórmula puede ser modificada de la siguiente manera:

a_{1,j} = p_{j−1} + (1 − p_{j−1}) · a_{1,j−1} ∀_{j=1...n}

Reemplazando para el vector V:

v_{j} = p_{j} + (1 − p_{j}) · a_{1,j} ∀_{j=0...n−1}

Centro de Desarrollo de Gestión Empresarial. Poniente 1206 – Viña del Mar, Chile. Fono:(56) (32)688987 – Fax:(56) (32)2684079 3

Para eliminar la dependencia con la matriz A, el valor de la celda a_{1,j} simplemente es el valor de la celda calculada en el paso anterior, la cual puede ser referenciada directamente. Para primer elemento v_{0}, v_{−1} no existe y se considera con valor 0, por ende, la fórmula puede ser aún más concisa.

v_{0} = p_{j}
v_{j} = p_{j} + (1 − p_{j}) · v_{j−1} ∀_{j=1...n−1}

Gráficamente, el algoritmo seria el siguiente:

v_{0} = p_{0}

A = ( \begin{matrix}1 & 1 & 1 & 1 & 1 \\ 0 & v_{0} & − & − & − \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{matrix} )

v_{1} = p_{1} + (1 − p_{1}) · v_{0}

A = ( \begin{matrix}1 & 1 & 1 & 1 & 1 \\ 0 & v_{0} & v_{1} & − & − \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{matrix} )

v_{2} = p_{2} + (1 − p_{2}) · v_{1}

A = ( \begin{matrix}1 & 1 & 1 & 1 & 1 \\ 0 & v_{0} & v_{1} & v_{2} & − \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{matrix} )

v_{3} = p_{3} + (1 − p_{3}) · v_{2}

A = ( \begin{matrix}1 & 1 & 1 & 1 & 1 \\ 0 & v_{0} & v_{1} & v_{2} & v_{3} \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{matrix} )

Para la siguiente iteración, es necesario modificar el criterio anterior. El valor de la celda v_{1} es el que debe ser calculado, entonces, siguiendo la fórmula:

v_{1} = p_{1} · v̂_{0} + (1 − p_{1}) · v_{0}

A = ( \begin{matrix}1 & 1 & 1 & 1 & 1 \\ 0 & v̂_{0} & − & v_{2} & v_{3} \\ 0 & v_{0} & v_{1} & − & − \\ 0 & 0 & 0 & 0 & 0 \end{matrix} )

En donde v̂_{i} se refiere al valor antiguo de la celda i del vector V antes de ser calculada. Particularmente, para el primer paso de la iteración, no se realiza cálculo sobre v_{0}, además, su valor es v_{0} = 0, y se debe de recordar que v̂_{i} tiene un valor calculado en la iteración anterior, por lo tanto, sólo es necesario modificar la fórmula:

Centro de Desarrollo de Gestión Empresarial. Poniente 1206 – Viña del Mar, Chile. Fono:(56) (32)688987 – Fax:(56) (32)2684079 4

v_{1} = p_{1} · v̂_{0}

A = ( \begin{matrix}1 & 1 & 1 & 1 & 1 \\ 0 & v̂_{0} & − & v_{2} & v_{3} \\ 0 & 0 & v_{1} & − & − \\ 0 & 0 & 0 & 0 & 0 \end{matrix} )

El problema de esto es que se pierde el valor original de v_{1}, el cual se utiliza en el paso siguiente de la iteración. Por lo tanto, el valor de v_{1} debe ser almacenado en una variable auxiliar antes de realizar el calculo. Esta variable se llamará ”actualOldValue”, o AOV

AOV = v_{1}
v_{1} = p_{1} · v̂_{0}

A = ( \begin{matrix}1 & 1 & 1 & 1 & 1 \\ 0 & v̂_{0} & AOV & v_{2} & v_{3} \\ 0 & 0 & v_{1} & − & − \\ 0 & 0 & 0 & 0 & 0 \end{matrix} )

Para la siguiente iteración, es necesario utilizar el valor AOV y v_{1} para calcular el nuevo valor de la celda v_{2}, pero también es necesario almacenar el valor de la celda v_{2} anterior al cálculo, dado que se necesita el valor antiguo para el cálculo de la siguiente celda en la iteraciíon. Se utilizará la variable AOV para almacenar el valor de v_{2} previo al calculo, pero ademas, se debe almacenar el valor que AOV tenía almacenado. Para ello, se utilizará la variable ”upperOldValue”, o UOV. Esta se utilizará para realizar el cálculo de la celda actual v_{2}. Entonces:

UOV = AOV
AOV = v_{2}
v_{2} = p_{2} · UOV + (1 − p_{2}) · v_{1}

A = ( \begin{matrix}1 & 1 & 1 & 1 & 1 \\ 0 & v̂_{0} & UOV & AOV & v_{3} \\ 0 & 0 & v_{1} & v_{2} & − \\ 0 & 0 & 0 & 0 & 0 \end{matrix} )

Para la siguiente iteración, no es necesario agregar más variables, sólo actualizar las existentes:

UOV = AOV
AOV = v_{3}
v_{3} = p_{3} · UOV + (1 − p_{3}) · v_{2}

A = ( \begin{matrix}1 & 1 & 1 & 1 & 1 \\ 0 & v̂_{0} & − & UOV & AOV \\ 0 & 0 & v_{1} & v_{2} & v_{3} \\ 0 & 0 & 0 & 0 & 0 \end{matrix} )

Centro de Desarrollo de Gestión Empresarial. Poniente 1206 – Viña del Mar, Chile. Fono:(56) (32)688987 – Fax:(56) (32)2684079 5

Para la última iteración, se ocupa el mismo criterio anterior. Sabemos que v_{1} = 0, entonces el primer paso de la iteración sería:

AOV = v_{2}
v_{2} = p_{2} · v̂_{1}

A = ( \begin{matrix}1 & 1 & 1 & 1 & 1 \\ 0 & − & − & − & − \\ 0 & − & v̂_{1} & AOV & v_{3} \\ 0 & − & 0 & v_{2} & 0 \end{matrix} )

El ultimo paso de la iteración sería:

UOV = AOV
AOV = v_{3}

v_{3} = p_{3} · UOV + (1 − p_{3}) · v_{2}

A = ( \begin{matrix}1 & 1 & 1 & 1 & 1 \\ 0 & − & − & − & − \\ 0 & − & v̂_{1} & UOV & AOV \\ 0 & 0 & 0 & v_{2} & v_{3} \end{matrix} )

El codigo de este algoritmo es el siguiente:

private static double rushdiGeneral(double[] ssR, int k) {
int n = ssR.length;
double upperOldValue;
double actualOldValue;
double array[] = new double[n];
int i, j;
array[0] = ssR[0];
for (j = 1; j < n; j++) {
  array[j] = ssR[j] + (1 - ssR[j]) * array[j - 1];
}
for (i = 1; i < k; i++) {
  actualOldValue = array[i];
  array[i] = ssR[i] * array[i - 1];
  for (j = i + 1; j < n; j++) {
    upperOldValue = actualOldValue;
    actualOldValue = array[j];
    array[j] = ssR[j] * upperOldValue + (1 - ssR[j]) * array[j - 1];
  }
}
return array[n - 1];
}

Centro de Desarrollo de Gestión Empresarial. Poniente 1206 – Viña del Mar, Chile. Fono:(56) (32)688987 – Fax:(56) (32)2684079 6

En donde ssR es el vector de contiene la confiabilidad de los hijos de la maquina y k es la mñima cantidad de equipos en operación. El valor de k puede ir entre 1 y n, donde n es la cantidad de elementos del vector ssR.

Para el caso particular k = 1 se implementó un algoritmo recursivo que tiene mejor performance que el presente algoritmo, pero únicamente para un valor de k = 1, para cualquier otro valor, su performance es pobre y de hasta menor calidad que el algoritmo rushdi original.

El codigo se basa en la siguiente fórmula:

R(i, j) = p_{j}R(i − 1, j − 1) + q_{j}R(i, j − 1)

Y esta es su implementación:

private static double rushdiOneMinToWork(double[] ssR, int n)
  if (n == 0) {
    return 0;
  }
  return ssR[n - 1] + (1 - ssR[n - 1]) * rushdiOneMinToWork(ssR, n - 1);
}

En donde ssR es el vector de contiene la confiabilidad de los hijos de la maquina y n un parámetro que varía con la recursión, inicialmente es la cantidad de elementos del vector ssR.

Centro de Desarrollo de Gestión Empresarial. Poniente 1206 – Viña del Mar, Chile. Fono:(56) (32)688987 – Fax:(56) (32)2684079 7