Contribuciones al reemplazamiento óptimo de sistemas reparables y al dimensionamiento óptimo de sistemas de colas
Full text
Universidad de Las Palmas de Gran Canaria Departamento de Matemáticas Tesis Doctoral Contribuciones al reemplazamiento óptimo de sistemas reparables y al dimensionamiento óptimo de sistemas de colas Juan José Giónzález Henríquez Las Palmas de Gran Canaria, Marzo de 2003
Universidad de Las Palmas de Gran Canaria Departamento de Matemáticas Tesis Doctoral Contribuciones al reemplazamiento óptimo de sistemas reparables y al dimensionamiento óptimo de sistemas de colas Autor: Juan José González Henríquez Directores: Pedro Saavedra Santana y Angelo Santana del Pino
DON PEDRO SAAVEDRA SANTANA, Catedrático de Universidad del Área de Conocimiento de Estadística e Investigación Operativa del Departamento de Matemáticas de la Universidad de Las Palmas de Gran Canaria y DON ANGELO SANTANA DEL PINO, Titular de Universidad del Área de Conocimiento de Estadística e Investigación Operativa del Departamento de Matemáticas de la Universidad de Las Palmas de Gran Canaria, CERTIFICAN que la presente memoria titulada, CONTRIBUCIONES AL REEMPLAZAMIENTO ÓPTIMO DE SISTEMAS REPARABLES Y AL DIMENSIONAMIENTO ÓPTIMO DE SISTEMAS DE COLAS, ha sido realizada bajo la dirección de ambos por el Licenciado en Matemáticas D. JUAN JOSÉ GONZÁLEZ HENRÍQUEZ, y constituye su Tesis para optar al grado de Doctor en Matemáticas. Y para que así conste, en cumplimiento de la legislación vigente y a los efectos oportunos a,-epie~iiaya lugar, firmamos la presente en Las Palmas de Gran Canaria, p: 25 de mafeo de dos mil tres. fdo.: D. Pedro ;elo Santana del Pino
índice General Lista de Símbolos v Agradecimientos vii Prefacio ix 1 GenercJidades sobre procesos puntuales 11 1.1 Introducción 11 1.2 Parámetros principales de un proceso puntual en IR"*" 16 1.3 Estacionariedad 19 1.4 La función de intensidad condicional 21 1.5 Modelos Básicos 24 1.5.1 Proceso de Poisson 24 1.5.2 Proceso de renovación 27 1.6 Superposición de procesos de renovación 30 1.7 El problema general de regla de parada 32 1.7.1 Caso monótono 34 1.8 El problema de parada y el reemplazamiento de sistemas reparables . 35 2 Modelos de sistemas reparables 39 2.1 Introducción 39 2.2 Reparaciones mínimas y perfectas 41
2 ÍNDICE GENERAL 2.3 Reparaciones imperfectas 43 2.4 Otros modelos de reparaciones imperfectas 44 2.4.1 Modelos lineales generalizados y modelos loglineales 45 2.4.2 Proceso de renovación modulados 45 2.4.3 Procesos de renovación con tendencia 46 2.4.4 Proceso gamma no homogéneo 47 2.5 Modelos de sistemas reparables con costes 47 2.5.1 Políticas básicas de reemplazamiento 49 3 Un modelo de repciraciones mínimas psira un sistema reparable compuesto. 53 3.1 Introducción 53 3.2 Determinación de la Estrategia Óptima 57 3.3 Análisis de un caso particular 60 4 Teoría de paradas óptimas y flabilidad 63 4.1 Introducción 63 4.2 Modelo de Boland-Proschan y procesos de decisión semi-Markovianos 65 4.3 Modelo de Boland-Proschan y teoría de paradas óptimas 66 5 Dimensionamiento óptimo de un sistema de colas 69 5.1 Motivación y presentación del modelo 69 5.2 Descripción del estado del sistema 76 5.3 Cálculo de las probabilidades estacionarias del sistema 79 5.4 Probabilidades de pérdida 84 5.5 Tiempos de espera 85 5.6 Optimización del rendimiento del sistema 90 5.7 Análisis de los resultados 91 5.7.1 Caso 1: \R » Ajv, p = 0.95 92 5.7.2 Caso 2: XR « XN, P = 0.95 99
ÍNDICE GENERAL üi 5.7.3 Caso 3: A^ ^ Ajv, p = 0.95 102 5.7.4 Caso 4: p « 0.95 108 5.8 Conclusión 109 B ibliografía 111
Lista de símbolos Concepto N M E+ B o{x) r{t) HtlHt) [x\ Definición Conjunto de los números naturales incluido el O Conjunto de los números reales Conjunto de los números reales positivos a-álgebra de Borel sobre M Una función que dividida entre x se aproxima a cero a media que X tiende a cero Función de razón de fallos. Función de intensidad condicional. Función indicatriz del conjunto E. Parte entera de x.
Agradecimientos En primer lugar, quiero expresar mi agradecimiento a los profesores Dr. D. Pedro Saavedra Santana y Dr. D. Angelo Santana del Pino por su orientación, estímulo y eficaz ayuda en la dirección de este trabajo. También quiero expresar mi gratitud a muchos compañeros del departamento de Matemáticas, en especial a aquellos que se siente atraídos por la Estadística. Todos ellos, en en algún momento, me escucharon y me aconsejaron tanto profesionalmente como anímicamente. También agradezco a D. Eduardo Rodríguez Barrera, a D". Nancy Sanín y al Dr. D. Gustavo Montero sus sugerencias y aportaciones M^rpC en la redacción de este documento. Por último agradezco a mis amigos y familiares su apoyo y entusiasmo a lo largo de esta empresa. Todavía recuerdo emotivamente aquellas simpáticas palabras de mi madre: "anímate y ponte a trabajar con tu gemelo". Un especial agradecimeinto a mi mujer por su santa paciencia (aunque no siempre; y con razón) en mis horas delante del ordenador.
Prefacio En esta memoria analizamos tres problemas de optimización, dos en el campo de la fiabilidad de sistemas y uno en el campo de la teoría de colas. Los tres problemas comparten, desde un punto de vista teórico, la misma función objetivo. Se trata de la función del beneficio o coste por unidad de tiempo a largo plazo (lo que proceda) que aparece en la teoría de la renovación con recompensa. En los problemas de fiabilidad, el concepto de renovación adquiere un significado particular: reemplazamiento de un sistema. El acelerado ritmo económico, junto con el gran desarrollo tecnológico, que se experimenta en nuestro tiempo hace que todo usuario de un sistema deba en algún momento estudiar la conveniencia de continuar con el sistema disponible o reemplazarlo. Con el tiempo y debido al desgate, la propensión al fallo de un sistema aumenta. De esta manera, el coste de reemplazamiento del sistema puede compensar económicamente el coste de las reparaciones que un sistema de edad considerada generaría en un futuro. Por tanto el objetivo en un problema de éstas características es determinar el instante óptimo para reemplazar un sistema por otro (de características similares) de tal manera que el beneficio por unidad de tiempo a largo plazo para la empresa sea el mejor posible. El problema relacionado con la teoría de colas es un problema que surge en el campo de la comunicación de sistemas informáticos. En concreto, se trata de un problema de modelo de elecciones (polling model), es decir, un problema donde es necesario planificar la manera (cíclica o aleatoria) en que un único servidor atiende a múltiples colas. El caso que nos ocupa se trata de un sistema formada por dos colas con buffers finitos de tamaño N y R, respectivamente, que son atendidas por un
16 Generalidades sobre procesos puntuales Teorema 1 Cualquiera de las siguientes condiciones determina la distribución de probabilidad de un proceso puntual sobre M; (i) Las distribuciones finito-dimensionales P{N{Ai) = n¿ ;^ = 1, 2,... ,n} siendo Ai conjutos Borel acotados*. (ii) Las distribuciones finito-dimensionales de la sucesión de puntos {Tí}^_^ . (iii) Las distribuciones finito-dimensionales de la sucesión de intervalos {To,X, :¿-0,±l,...}. (iv) Las distribuciones finito-dimensionales del proceso {N{t) : t E IR}. 1.2 Parámetros principcJes de un proceso puntual en IR+ Una forma natural de medir el número de ocurrencias en un intervalo determinado en un proceso puntual es a través de la función M(t) = E[N{t)]. A lo largo de esta sección estudiaremos la importancia de esta función y su relación con aspectos interesantes de los procesos puntuales en M.~^. Se puede comprobar que M(t) es una función no decreciente continua a la derecha y tal que el límite por la izquierda M(í—) = linisit M{t) existe para todo t. Respecto a M(t) podemos decir lo siguiente: • A partir de la equivalencia (1.5) se deduce que P{N{t) > i) = P{Ti < t). Si denotamos por G¿ (í) a la función de distribución de la variable T¿ tenemos que, oo oo M{t) = E[N{t)] = J2^(^W ^ ^) = E^^W- (l-8b) 1=1 Í=l Por lo tanto si las funciones de distribución G¿(í) son absolutamente continuas, M{t) es absolutamente continua y su derivada m{t) (salvo en un conjunto de *Un teorema sobre medidas aleatorias afirma que la distribución de probabilidad de una medida aleatoria queda determinada al conocer las distribuciones finito-dimensionales de toda familia Al,... ,Ak de conjuntos disjuntos de un semianillo de conjuntos acotados que genera la cr-álgebra de Borel correspondiente. Por tanto los conjuntos Ai puede ser intervalos disjuntos de la forma (a, b].
Parámetros principales de un proceso puntual en E"*" 17 medida de Lebesgue nula) es de la forma, oo m{t) = J2gi{t) (1.8c) í=i siendo gi{t) una densidad de Gi(t). Denominaremos a r?7,(í) función de razón de ocurrencias de puntos del proceso; representa la razón instantánea de variación del número esperado de puntos con respecto al tiempo. La integral de m{t) en un intervalo nos da el número medio de puntos en ese intervalo. • Si M{t) existe en un entorno de ¿o Y M{to—) ^ M{to) entonces, hay una probabilidad positiva de que el suceso de interés ocurra al menos un vez en ÍQEl recíproco también es cierto. Además de la función razón de ocurrencia de puntos, en la teoría de procesos puntuales es de interés la llamada función de intensidad definida por. Si A(í) existe, A(í)Aí es aproximadamente la probabilidad de que haya al menos un punto en el intervalo (í,í + Ai]. Se puede probar que si M(í) < oo para todo t entonces la función A(í) existe. En la primera sección de este capítulo hablábamos del interés especial que tienen para nosostros los procesos puntuales simples, aquellos procesos sin múltiples ocurrencias. En términos probabilísticos, aquellos procesos puntuales para los que P{N{\x\ = O o 1; Va; e M } = 1. También decíamos que cuando se define un proceso puntual a través de las distribuciones finito-dimensionales con las correspondientes condiciones de consistencias de las que habla el teorema de extensión de Kolmogorov, no queda, claro como son las trayectorias del proceso (continuas, derivables , etc). En el caso que nos ocupa sabemos que las trayectorias A'^(í) (í > 0) son funciones con recorrido en N, no decrecientes, continuas a la derecha y con A'^(O) = 0. Nos falta saber si estas funciones en escalera son o no de saltos unitarios. Desde luego.
18 Generalidades sobre procesos puntuales si los saltos son unitarios el proceso puntual es simple. A continuación daremos dos condiciones suficientes para garantizar que el proceso puntual es simple. Definición 1 n A{t) = sup j:P{N{ti^,,ti\ > 1}, (1.8e) 1=1 cuando el supremo recorre todas las particiones O = ÍQ < ti... < tn = t del intervalo (O, t]. A (í) es la integral superior de la función intervalo P [N{a, b] > 1] ,a> b. Teorema 2 Si M{t) < oo para cada í > O, M (í) = A (í) <í=4> N es simple. Por lo tanto, una condición suficiente para que un proceso puntual integrable (M(í) < oo) sea simple es que M (t) = A (í) . También son de interés los siguientes teoremas. Teorema 3 Si M{t) < oo para cada í > O, entonces: a)E [^ (í)] = A (í), siendo ^ (t) el número de discontinuidades de N (•) sobre el intervalo {0,t] . b)X (¿) existe en casi todo punto y A{t) = J^X (x) dx. Corolario 1 Si un proceso puntual integrable es simple entonces t M (t) = A{t) = J X (x) dx y m{t) = X (t) en casi todo punto. o Del corolario anterior se deduce que, para un proceso puntual con esperanza finita y sin ocorrencias simultáneas, puede hablarse sin ambigüedad de la función de razón de ocurrencia de puntos m(t), la cual coincide con la función A(í). En términos de fiabilidad de sistemas, la igualdad m{t) = X (í) indica que la razón de ocurrencia de fallos es igual a la razón con la que se producen los instantes de fallo, dado que sólo se produce un fallo en cada instante de fallo. Esta igualdad no se da cuando
Estacioneariedad 19 el sistema está sujeto a circunstancias que pueden causar muchos fallos simultáneos. Así ocurre, por ejemplo, con ciertos fenómenos (una tormenta de granizo, una lluvia de meteoritos) que pueden causar varias averías simultáneas en un sistema. En este caso, el conocimiento de la función m(í) es para la empresa de mayor utilidad que el conocimiento de A (í) pues, a partir de ella podrá decidir el número de operarios de mantenimiento necesarios para hacer frente a las múltiples averías que se producirán en un instante incierto t. Hemos dicho que si M(í) < oo y M(t) = A(í) para todo t entonces el proceso puntual es simple. Aparte de esta condición, existen otras condiciones, que tratan aspectos infinitesimales del proceso, para garantizar que un proceso puntual es simple. En [1], (capítulo 7) se habla con rigor de todas estas condiciones infinitesimales. De todas ellas nos merece especial atención la siguiente: un proceso puntual en la recta real es orderly si, lim^W'-';^i>"=0. {1.8f) Puede probarse que, un proceso puntual que verifica (1.8f) es simple. Para finalizar diremos que en un proceso puntual simple se verifican las siguientes aproximaciones, M{x^b)-M{x) = E\]^{x,x + d\^ ~P{A^(x,a; + (5] = 1} ~ P{iV(a;,a; + ¿j > 1} (l-8g) 1.3 Estacionariedad En esta sección vamos a exponer algunos conceptos sobre procesos puntuales estacionarios que emplearemos en esta memoria. Definición 2 Un •proceso puntual sobre E es estacionario si para todo r = 1,2,..., y para todo subconjunto Borel acotado Ai,... ,Ar deM. la distribución conjunta del vector, {N{Ai+t),...N{Ar + t)}
20 Generalidades sobre procesos puntuales no depende de t con -oo < í < oo. En el caso de que el proceso puntual se defina sobre la semirrecta real positiva, los conjuntos Ai serán subconjuntos Borel de (O, oo) y t tomará valores reales positivos. Esta forma de estacionariedad puede debilitarse de diversas maneras; por ejemplo restringiendo los conjuntos Ai,... ,Ar a ser intervalos y/o acotando por un valor b los valores de r. Entre estos casos se encuentra la denominada estacionariedad simple. Un proceso puntual es estacionario simple o simplemente estacionario si la distribución del número de puntos en un intervalo depende de su longitud pero no de su localización^; esto es, si Pk{x) = P{N(t,t + x] = k} (x>0,k = 0,l,...), (1.8h) depende de la longitud de x pero no de la localización de t. Se puede comprobar ([l], pág 43) que para un proceso puntual con esta propiedad M(t) = m • t. De acuerdo con (1.8c) m nos da la razón de ocurrencia de puntos del proceso. ¿Cuándo existirá la función de intensidad (l.Sd) de un proceso simplemente estacionario? Si existe, ¿Será constante e igual a m? Y, ¿Cuándo es simple un proceso simplemente estacionario? El siguiente teorema da respuesta a estas preguntas. Teorema 4 (a) (Khintchine) La función de intensidad de un proceso simplemente estacionario existe y es una constante A con O < A < oo (b) (Korolyuk) Si un proceso puntual es simple y simplemente estacionario entonces \ = m. (c) (Dobrushin) Si un proceso puntual es simplemente estacionario y m < oo entonces el proceso es simple ( y ordely (l.Sfjj Definición 3 Un proceso puntual tiene intervalos estacionarios cuando para todo r = 1,2,..., y para todo los enteros ii,... ,ir la distribución conjunta de {Xi^^k, • •• , Xi^+k} no depende de k {k = Q,±l,...). ^A esta propiedad también se le conoce como propiedad de incrementos estacionarios.
La función de intensidad condicional 21 De acuerdo con, (1.8a) para que las trayectorias de un proceso con esta propiedad esté bien definido es preciso elegir un punto arbitrario ¿o a partir del cual se ubican los puntos del proceso. Una posibilidad, quizá la más natural, es tomar ío = 0. Por lo general, el proceso de la definición anterior no será estacionario en el sentido de la definición 2. Uno de los resultados más interesantes de esta sección es la correspondencia biyectiva que existe entre las distribuciones de probabilidad V de procesos estacionarios simples sobre M con razón de ocurrencias m finita y las distribuciones de probabilidad Vo de las dobles sucesiones estacionarias de variables aleatorias positivas con media ?TT.~^([1], pág 475). Sin ánimo de extendernos en cuestiones que pertenecen a la llamada teoría de Palm, únicamente decir que de esta correspondencia se deduce una de las relaciones más conocidas en teoría de colas, las famosas ecuaciones de Palm-Kinchin: Pk{x) = -m {7Tk{u) - •Kk-i{u)}du (A; = 1,2,...), (1.8i) Jo Po{x) = 1 — m I TTo{u)du Jo siendo TTk{x) = lim P{A^(0,a;] = k \ N{-6,0] > 0} con íc fijo y A: = 0,1, 2,... Es claro que para cada x las TTk{x) constituyen una distribución discreta de probabilidad, llamada distribución de Palm. Las ecuaciones (1.8i) adquieren relevancia práctica cuando observamos un proceso estacionario simple en un punto (un evento) arbitrario del proceso (muestreo síncrono). 1.4 La función de intensidad condicional A partir de las observaciones reales de tiempos de vida, tanto en fiabilidad como en el análisis de supervivencia, es difícil elegir un modelo entre las diversas funciones no simétricas de probabilidad. Por ejemplo, las diferencias entre la función de distribución gamma, WeibuU y lognormal son significativas tan sólo en la cola de la distribución. Por otra parte, y debido a la limitación del tamaño muestral, los tiempos
22 Generalidades sobre procesos puntuales de vida suelen estar diseminados en la cola de la distribución por lo que resulta difícil discriminar entre estas funciones de distribución. Es necesario, por tanto, definir un concepto que nos permita distiguir entre dos posibles funciones de distribución. Tal concepto es la función de razón de riesgo o función de razón de fallos definida como: , , ,. P(t<T <t + A\t>T) ,, ^., r(t) = lim^ L^^_J!.. (1.8j) Si la distribución de fallos F tiene función de densidad /, la función de razón de fallos r{t), para aquellos valores de t tales que F{t) < 1, adquiere la forma: r{t) = ¿fií- (1.8k) ^ ^ F{t) ^ ' donde F{t) = 1 — F{t). Esta función tiene una interpretación probabilística muy útil; r(í)A representa la probabilidad de que un objeto de edad t falle en el intervalo [í,í + A). Atendiendo a la siguiente igualdad, F(í) = exp{- I r{s)ds} (1.81) Jo es claro que F queda determinada unívocamente por su función de riesgo. Es por esta razón y por su interpretación probabilística por lo que en fiabilidad y en supervivencia se suele utilizar la función de riesgo como guía para elegir el modelo que mejor se ajusta a los tiempos de vida observados. Precisamente algo parecido ocurre cuando se observan datos de un fenómeno que se puede modelar a través de un proceso puntual simple. En este caso la función recibe el nombre de función de intensidad condicional y se define como: donder l-ít denota la historia del proceso de fallos hasta el instante t e incluyendo t. Por lo general, se entenderá que Tít está generada por {N{s) : O < s < í} y que P{N{t + A) — N{t) > 1) = o(A). Esto último es una condición necesaria para que el proceso sea simple. En fiabilidad, por ejemplo, A(Í|7ÍÍ)A es aproximadamente
La función de intensidad condicional 23 la probabilidad de un fallo en el intervalo [t,t + Ai), condicionado a la historia del proceso de fallos hasta el instante de tiempo t. Desde el punto de vista teórico la función de intensidad condicional es sumamente importante, pues a partir de ella queda completamente determinada la estructura probabilística de un proceso puntual simple en la recta real positiva. Para una demostración rigurosa de este enunciado puede consultarse [1] (cap. 13) o [2]. Desde el punto de vista práctico, la eleccióji de un modelo para unas observaciones reales se realiza más fácilmente a través de la función de intensidad condicional que a través de otras formas equivalentes que sirven para definir un proceso puntual simple. De hecho, en la modelización de fallos de sistemas reparables (sistemas que pueden ser puestos en funcionamiento tras un fallo) es costumbre desde hace algún tiempo dar la función de intensidad condicional, cuando se quiere especificar un modelo de fallos para un sistema reparable. Haremos una revisión de estos modelos en el siguiente capítulo de esta memoria. A continuación trataremos una situación interesante donde la función de intensidad condicional adquiere una expresión concreta. Paxa ello, sea {Ti} la sucesión de puntos de un proceso puntual simple con O = TQ < Ti < T2 < ... y sea Fn{x\TQ,Ti,... ,T„_i) la función de distribución condicional de la variable ^n — Tn — Tn-i condicionada a "HT™-! = cr(To,... ,r„_i). Supongamos además que para todo n > 1, Fn{x\To,Ti,... ,T„_i) admite una función de densidad fn{x), es decir, Fnix\nT„_,)= r fniu)du. (l.8n) Jo Bajo esta suposiciones se puede demostrar que la función de intensidad condicional adquiere la forma concreta, ^(^1^*) = 1 Jf ~/lÍ T ^°^^^ {Tn<t< r„+i} . (1.8o) Una demostración heurística de este resultado puede encontrarse en la páginas 59 — 61 de [2]. Si por ejemplo, la sucesión de intervalos {Xi} está formada por variables
24 Generalidades sobre procesos puntuales aleatorias independientes con distribución común F(t) con densidad f{t) y con función de riesgo r{t) (proceso de renovación), la función de intensidad condicional con respecto a la historia interna T-ít viene dada por, X{t\nt) = r{t - Tn-i) donde {Tn-i < t < Tn} (1.8p) Nota 1 Respecto a la definición de función de intensidad condicional hemos de decir que algunos autores condicionan respecto de Tit- = o'{N{s) : O < s <t}. Esto se hace para garantizar que A(í) sea predecible y por tanto única. La definición dada por nosotros coincide con Cox [3] y Bremaud [2j. Este último afirma en su libro (página 2)1) que si existe un función de intensidad puede siempre encontrarse una versión predecible. 1.5 Modelos Básicos 1.5.1 Proceso de Poisson De acuerdo con el teorema 1, un proceso puntual A'^ en M queda determinado al conocer P{N{Ai) = Ui \i = l,2,...n} para toda familia finita Ai,... ,An de conjuntos disjuntos de un semianillo de conjuntos acotados que genera a la tr-álgebra de Borel B. Como la clase de conjuntos formada por los intervalos de la forma (a, b] es un semianillo de conjuntos acotados que genera a la cr-álgebra de Borel B podemos decir que, un proceso puntual N en la recta queda determinado al conocer para todo n, P{N{ai,bi] = ni;i = 1,2,... ,n} (1.8q) donde ai < bi < aj+j con i = 1,... ,n. Un proceso de Poisson en IR es un proceso puntual para el cual {H{bi)-H{ai)r^ nA P{N{aM=ni;i = 1,2,... ,n} = n J e^p {-{H (h) - H (a.))} (1.8r)
Modelos Básicos 25 siendo H(t) una función no negativa, no decreciente y continua a la derecha. A partir de la definición se deduce fácilmente que M(t) = E[N{t)] = H{t). Por esta razón, la función H{t) recibe el nombre de función de medias. La función H{t) determina las propiedades del proceso de Poisson : 1. Si H{t) está definida en un intervalo de la recta real entonces el proceso está definido en dicho intervalo. 2. Si H{t) tiene asíntotas verticales entonces el proceso es explosivo, es decir, el proceso tiene un número infinito de puntos en tiempo finito. 3. Si H{t) es tal que limt^oo H{t) < oo entonces se puede demostar que el proceso es finito, es decir, el número de puntos del proceso es finito con probabilidad 1. En este trabajo nos vamos a centrar en el proceso de Poisson definido en R"*", no explosivo y no finito. Por esta razón, la función H(t) va a estar definida en [O, oo) con limt_>+oo H{t) = +oo. Desde luego la función H{t) puede ser continua, discontinua, derivable, etc. Estas propiedades afectan a las propiedades del proceso de Poisson: 1. El proceso de Poisson es simple si y sólo H{t) es una función continua. 2. Si H(t) es discontinua en ÍQ entonces la variable aleatoria N{to} tiene una distribución de Poisson de parámetro J = ií(ío) ~ H(to—). 3. Si H{t) es absolutamente continua entonces el proceso es simple y existe una función H'{t) = m(t) la cual representa la razón instantánea de variación del número esperado de puntos con respecto al tiempo. Esta función m(t) recibe el nombre de función de intensidad del proceso. Aunque la función H{t) pueda ser continua singular, en este trabajo no vamos a considerar estos casos. Por lo general, trataremos con funciones H{t) de la forma H{t) = / m{u)du. (1.8s) J —oo
32 Generalidades sobre procesos puntuales superposición de los procesos de renovación es más bien un proceso de estadísticos ordenados. Si embargo, en este caso los fallos en cada dispositivo son independientes pero no tienen que ser indénticamente distribuidos. Sin duda, esta condición no es plausible para sistemas reales, dado que para valores de t suficientemente grandes es posible que ciertos dispositivos sean reemplazados dos o más veces. Esta condición parece más apropiada en fiabilidad del software donde un fallo adecuadamente reparado no vuelve a aparecer nunca más. La función de razón de fallos de la distribución exponencial es constante. Esto quiere decir que si un equipo falla de acuerdo a esta distribución la propensión al fallo no cambia con el uso. Por esta razón, la distribución exponencial fue raramente considerada como distribución de fallos de un sistema. Sin embargo, por las razones expuestas anterioremente hay situaciones donde la distribución exponencial juega un papel prominente. 1.7 El problema general de regla de pcirada Supongamos que vamos observando gradualmente una sucesión de variables aleatorias yi,y2, • • • y que debemos parar este proceso de observación en alguna etapa n. Si paramos en dicha etapa n, recibiremos una "recompensa" Z^ que es función de los valores yi,... ,y„. El problema de regla de parada consiste en encontrar reglas de parada que maximice o minimicen nuestra "recompensa" esperada. Para definir formalmente este problema son necesarios los siguientes elementos: (i) Un espacio de probabilidad {n,J-,P). (ii) Una sucesión creciente J-n de sub-a-álgebras de J-. (iii) Una sucesión de variableas aleatorias Zi,Z2, • • • , tal que Z„ medible respecto a Jr„, 71 = 1,2, — A partir de estos objetos hacemos las siguientes definiciones:
8 El problema general de regla de parada 33 Definición 4 Una regla de parada es una variable aleatoria { con valores 1,2,3,... , +oo, tal que P(^ < oo) = 1 y el suceso {^ = n} E TnDefinición 5 El par de sucesiones {Zn,J^n}'^=i recibe el nombre de sucesión estocástica. Una sucesión estocástica se dice integrable si E[\Zn\] < oo {n > 1). A partir de estas definiciones, el problema de regla de parada puede plantearse de la siguiente manera: dada una sucesión estocástica integrable {Zn,J'n\'^=i encontrar dentro del conjunto de reglas de parada V aquella regla ^* tal que E[Z^*] = supií'[Z^] = V donde el supremo recorre el conjunto de regla de parada tal que ¿'[Z^] exista, siendo n=\ \ O, IC = oo} i Para este problema el interés se centra en responder a las siguientes preguntas: • ¿Existe la regla de parada óptima ^* tal que -E[Zg*] = y?¿Cómo es? • ¿Cómo podemos calcular el valor VI En algunas ocasiones, el problema de parada óptima se estudiará en un subconjunto propio D de F. Precisamente en el campo donde vamos aplicar estos conceptos, la fiabilidad, existen numerosos problemas de reemplazamiento que han sido resueltos para un subconjunto D concreto de reglas, las cuales, dependen por lo general de algún número finito de parámetros. A este subconjunto se le suele conocer en fiabilidad , y en otros contextos, con el nombre de política. Ahora vamos a comentar como debe entenderse cada uno de los elementos de un problema general de parada para los problemas de fiabilidad que quieren resolverse, a saber; los problemas de reemplazamiento de sistemas. En primer lugar, debe observarse, que el problema general de parada se ha planteado en tiempo discreto. Esto se debe precisamente a que en los problemas de reemplazamiento que estudiaremos, y por razones que
34 Generalidades sobre procesos puntuales posteriomente se justificarán, el reemplazamiento del sistema se realizará en uno de los instantes de fallos a los que está sujeto el sistema. Es decir, después de haber observado n instantes de fallos TI^TQ,,. • • Tn habrá que decidir si se continúa con la producción o si por el contrario se realiza el reemplazamiento del sistema. Así, la subcr-álgebra J^n debe entederse como la cr-álgebra generada por las variables aleatorias Ti,T2,...r„. A partir del problema general de problema de regla de parada descrito anteriormente, surge otro problema muy interesante al considerar finita la sucesión estocástica {Zn-,Tn\^^iEn este caso, de no haber parado antes de observar Tm hay que parar obligatoriamente en la etapa TU. A este problema se le conoce como problema de regla de parada con horizonte finito. Este problema puede verse también como un caso especial del problema de horizonte infinito, donde Zm+i = • • • = Zoo = — oo. Este tipo de problemas pueden resolverse de forma óptima por el llamado método de inducción regresiva. En general, los problemas de horizonte infinito no tienen una solución que pueda expresarse mediante una expresión matemática concreta y por tanto es necesario el estudio de métodos o reglas que permitan acercarse a la solución óptima. En principio, es posible encontrar soluciones aproximadas del problema al considerar una versión truncada (eligiendo un valor de m bastante grande) del problema original. Aparte de este método, llamado método de truncamiento, existen otros caminos que nos permiten encontrar otras soluciones aproximadas del problema. Tal es el caso de la regla de parada de las k etapas futuras; una regla simple que mejora el método de truncamiento. En la siguiente sección describimos esta regla y sus propiedades, para finalmete estudiar el llamado caso monótono de un problema de regla de parada. 1.7.1 Caso monótono En un problema de regla de parada, la regla de las k etapas futuras (k-ef) es aquella regla que estando en la etapa n para o continúa si la regla óptima entre las etapas n + 1 y n + k (ambas inclusivas) para o continúa. Una propiedad importante de
El problema de parada y el reemplazamiento de sistemas reparables 35 estas reglas es que si en una determinada etapa n la regla A;-e/recomienda continuar entonces la regla {k~l)-ef también recomienda continuar. Además, si la regla óptima existe, y si la k-ef recomienda continuar entoces la regla óptima también recomienda continuar. Esta propiedad sugiere una simplificación de la k-ef : aplicar la regla 1-e/ hasta que pare, después aplicar la regla 2-ef hasta que pare, y así sucesivamente hasta llegar a la regla k-ef. En este contexto resulta interesante saber cuanto de próximo está la regla óptima de la más simple de las reglas k-ef la 1-e/ (llamada tanbién regla miope), la cual puede expresarse de esta otra manera, iVi = {n>0:Z„>£:(Z„+i|Zi,... ,Z,)} (1.9) Así, la regla miope es aquella que para en el primer n donde la ganancia obtenida por parar es al menos tan grande como la ganancia esperada al parar en la siguiente etapa. Definición 6 Denotamos por An = {Zn > E{Zn+i\J^n)}- Diremos que un problema de regla de parada es monótono si, AQC A1CA2C... es. Teorema 7 Si E{swp,^Zn) < 00 , lim Z„ = Z^ c.s. y las variables Hn = n—i-oo supj>^{Zj —Z„} son uniformemente integrables entoces el problema de regla de parada monótono tiene por regla óptima a la regla miope. Para un estudio completo en teoría de paradas óptimas puede consultarse [12]. 1.8 El problema de parada y el reemplazamiento de sistemas reparables En la industria es habitual que una máquina deba ser reemplazada por otra de características similares. Debido a que esta operación de reemplazo se realiza reiteradamente a lo largo del tiempo, es conveniente reemplazar la máquina de tal
36 Generalidades sobre procesos puntuales manera que consigamos el mayor beneficio posible. Como objetivo, parece apropiado maximizar el beneficio promedio por unidad de tiempo. Esto es, al repetirse el problema de reemplazamiento un número n de veces de forma independiente y de acuerdo con la misma regla de parada ^, conseguiríamos ^i,...,Cn reglas de parada independientes e idénticamente distribuidas y Z^^,...,Z^ beneficios, independientes e idénticamente distribuidos. De esta manera el beneficio total conseguido en el tiempo total T^j + ... + T^^ es Z^^ + ... + Z^^, por lo que el beneficio promedio por unidad de tiempo es el cociente {Z^^ + ... + Z^J/(T^^ + ... + T^„). Si tanto numerador como denominador se divide entre n entonces, por la ley de los grandes números, el cociente anterior converge a E[Z¿\/E\T^, siempre y cuando las esperanzas correspondientes existan. Por lo tanto, se trata de elegir una regla de parada ^ que maximice el cociente E[Z^/E\T^., siendo Z^ el beneficio conseguido hasta el momento T^ ( momento en el cual reemplazamos la máquina actual por la nueva). Con esta función objetivo, el problema de parada puede replantearse de la siguiente manera: dada una sucesión estocástica integrable {Z^, •^n}^=i encontrar dentro del conjunto de reglas de parada T aquella regla ^* tal que E[Z^*]/E[T^*] = sup E[Z¿/E[T¿ = V donde el supremo ahora recorre el conjunto de regla de parada tal que E[Z^] < oo y ^ > 1 (al menos observaremos un fallo). A primera vista parece que se trata de otro problema diferente al problema clásico de parada óptima antes definido, pero en realidad, es una generalización de este problema ya que permite que los tiempos enti'e etapas sean diferentes y no, unitarios y fijos como el problema clásico. No obstante, en los problemas de fiabilidad que resolveremos es preferible trabajar con una formulación clásica del problema de parada. En resumidas cuentas lo que queremos es eliminar el denominador en nuestra función objetivo E[Z^]/E[T^]. Para ello haremos lo siguiente: Como E{Z^) < VE(T^), para toda ^ &T, podemos decir que ^* es óptima si E{Z^^ - VT^*) = supE{Z^ - VT¡) (1.11) Con otras palabras, la sucesión de variables aleatorias Z\,Z2T • • , que aparecen en el problema clásico de parada es ahora de la forma Zj = Zi — VT\, Z2 =
El problema de parada y el reemplazamieato de sistemas reparables 37 Z2 — VT2,... ,. La equivalencia entre estas dos formas de ver el problema queda confirmada con el siguiente teorema. Teorema 8 a) Si para algún 7, supE{Z^ — jT^) — O, entonces sup£'[Z^]/£'[T^] = 7. i& Cer Además, si sup£'(Z^ — 7T¿) = O se alcanza en ^* e F, entonces ^* es un regla óptima para maximizar E[Z^]/E[T^]. (b) Recíprocamente, si supE[Z¿/E[T^] = ^ y el supremo se alcanza en {* e F, entonces supi?(Z^ — jT^) = O y el supremo se alcanza con la regla ^*. En caso de encontrar la regla óptima ^*, la expresión matemática de la regla óptima va a depender del valor óptimo V, es decir, ^* = ^*(V). De esta manera para resolver completamente el problema es necesario calcular dicho valor V. Ahora bien, si consideramos el valor V no como un valor fijo sino como un valor variable, llamémoslo 7, tendremos una familia de reglas de paradas ^(7) con 7 G IR. Así, para cada valor de 7 tendremos una regla ^(7) cuyo beneficio promedio a largo plazo es ^(7) = E{Zci^) — jTfíry)). En general, lim ^^(7) = 00 y hm 1/(7) = —00.y de 7—>—00 7—>oo acuerdo con el teorema anterior hay que buscar el valor 7 tal que V^j) = 0. Además, según resultados de teoría de paradas óptimas se tiene el siguiente teorema. Teorema 9 ^(7) es decreciente y convexa A partir de este resultado podemos describir un simple método iterativo para calcular el valor 7 tal que ^^(7) = O y la regla de parada óptima. Se trata del método de Newton, el cual, converge cuadráticamente. Sea 7o un valor inicial para el valor óptimo. En el punto 70^ la recta y = V^(7o)~£'[T'$(7o)](7~7o) ^s un hiperplano soporte, ya que y(7o) - £^[%7o)](7 - 7o) = E^Í^J - W'{-fj < V{-f). De acuerdo con el método de Newton, los sucesivos valores de 7^, , rz = 0,1,... se calculan mediante la recurrencia, 7n+l=7n + ^^(7n)A^'(7n)- (1-12)
38 Generalidades sobre procesos puntuales Y como V (7„) = —E[T^^j^)] se tiene que, Por tanto, el valor V es el punto fijo de la función, E[Ta,J t/(7) = ^^í^^. (1.14)
Capítulo 2 MODELOS DE SISTEMAS REPARABLES ¿Qué es un sistema reparable? ¿Qué es una reparación mínima? ¿ Cuáles son los modelos existentes en la actualidad para sistemas reparables ? En el caso de sistema reparables reparados mínimamente y teniendo en cuenta costes y beneficios, ¿Cuál es el momento idóneo de reemplazamiento? Estas y otras cuestiones tendrán respuesta a lo largo de este capítulo. 2.1 Introducción En la actualidad, el rendimiento de la industria y de cualquier persona en su actividad diaria depende, por lo general, de la disponibilidad de numerosos aparatos y/o máquinas*. Desde luego, la disponibilidad de la mayoría de estos sistemas depende, en buena medida, de la acciones de mantenimiento preventivo y/o correctivo que se lleven a cabo. El mantenimiento correctivo, también llamado reparación, tiene por objeto restaurar las funciones propias del sistema cuando estas han cesado por alguna rotura. El mantenimiento preventivo, como su nombre indica, se realiza para prevenir posibles fallos y para reducir al máximo los procesos de desgaste propios del funcionamiento del sistema. A aquellos sistemas a los que únicamente se mantiene correctivamente se les denomina sistemas reparables. De acuerdo con Ascher y Feingold [13], un sistema reparable puede ser definido *En adelante, para referirnos genéricamente a todas esas herramientas utilizaremos el término, sistema industrial, o simplemente, sistema
40 Modelos de sistemas reparables como una colección de dos o más dispositivos que después de perder una o varias de sus funciones puede recuperarlas satisfactoriamente a través de cualquier forma distinta al reemplazamiento total del sistema . En esta memoria nos dedicaremos al estudio de sistemas reparables que recuperan inmediatamente la operatividad tras perderla. Esta suposición teórica se debe a que en la práctica el tiempo empleado en realizar una reparación al sistema es insignificante en comparación al tiempo en funcionamiento. Los modelos probabilísticos más apropiados para estudiar la disposición de los fallos de un sistema reparable a lo largo del tiempo son los procesos puntuales. Después de una reparación es normal que el propietario de un sistema quiera conocer su estado. Entre otras cosas desearía saber si la propensión al fallo del sistema va a ser la propia de un sistema de su edad que nunca ha fallado o como la de un sistema nuevo. A las reparaciones que dejan al sistema en una de esas situaciones extremas se les conoce como reparaciones mínimas y reparaciones máximas, respectivamente. En la práctica, por lo general, la reparaciones del sistema serán algo intermedio entre una reparación mínima y una reparación máxima. Fijar el tipo o los tipos de reparaciones posibles que se van a realizar en un sistema es fijar un modelo para el sistema reparable en cuestión. En las tres secciones siguientes vamos a revisar los modelos existentes hasta la fecha en la literatura para modelos reparables. Otra cuestión importante para el propietario de un sistema es saber, de acuedo con algún criterio económico, cuando es el momento idóneo para reemplazarlo por uno igual o de mejor calidad. En este caso es importante conocer los parámetros económicos que influyen en el sistema: costes de las distintas reparaciones, coste de reemplazamiento, los beneficios de la producción, etc. A un modelo de sistema reparable al cual se le añade una estructura de costes y beneficios al objeto de hallar el instante óptimo de reemplazamineto del sistema por otro exactamente igual se le denomina modelo de sistema reparable con costes. En la última sección de este capítulo haremos una revisión de los distintos modelos de sistemas reparables con
Reparaciones mínimas y perfectas 41 costes. 2.2 Reparaciones mínimas y perfectas El concepto de reparación mínima fue introducido por Barlow y Proschan [14] para mimetizar el comportamiento de un sistema complejo cuando una de sus múltiples componentes es sustituida o reparada tras un fallo. Un ejemplo ilustrativo es la reparación del pinchazo de un neumático de un coche. En términos matemáticos Barlow y Proschan definen el concepto de la siguiente manera: si un sistema (con función de distribución de fallos F{x) absolutamente continua y función de razón de fallos r(a;)) falla en el instante t entonces, después de ser reparado mínimamente, la probabilidad de que falle después de s + í unidades de tiempo es 1 — F{t + s)/(l — F{t) y su razón de fallos es r(s + í). De acuerdo con esta definición el proceso de fallos de un sistema reparable sujeto a reparaciones mínimas tiene función de intensidad condicional \{t\'Ht) = r(í); y es por tanto un proceso de Poisson no homogéneo con función de intensidad r{t). Sin embargo, si el sistema es muy simple (como por ejemplo un sistema en paralelo con dos componentes Ci y C2, ambas con distribución de vida exponencial de parámetro 1) la reparación mínima física de un fallo del sistema (en el sentido de Barlow y Proschan de abrir el sistema y sustituir o reparar la pieza que causó el fallo del mismo) está lejos de corresponderse con el significado matemático de reparación mínima. Si el sistema en paralelo anterior falla en un instante t es porque las dos componetes han fallado y como ambas no pueden fallar simultáneamente, la función de razón de fallos después de t es constante e igual a la unidad en cualquiera de los casos. Sin embargo, la función de razón de fallos después de t, cuando se realiza una reparación mínima en el sentido matemático es r(t) = 2(1 — e~*)/(2 — e~*). Por esta razón Bergman [15] denominó a la reparación mínima en el sentido matemático reparación mínima estadística y a la reparación mínima en el sentido físico de Barlow y Proschan reparación mínima física. Desde un punto de vista estrictamente
48 Modelos de sistemas reparables reemplazar el sistema en vez de seguir realizando reparaciones mínimas. En otras palabras, el reemplazamiento de un sistema reparable encargado de la producción initerrumpida de un determinado bien debe realizarse en algún momento del tiempo, bien por sus costes de mantenimiento o bien por un mal desempeño de sus funciones. Si asumimos que el sistema se reemplaza por otro de naturaleza idéntica, que los fallos del sistema son reparados mínimamente, y que esta situación se repite indefinidamente en el tiempo podemos plantearnos el siguiente problema: encontrar la regla de parada ^ que minimice la función objetivo CÍO = E[Z¿/E[T¿ (2.11) siendo T^ la variable aleatoria que mide el tiempo entre dos reemplazamientos consecutivos (un ciclo) del sistema y Z^ la vajñable aleatoria que mide el coste de mantemiento de un ciclo. Esta última variable puede ser a veces una recompensa más que un coste. En ese caso habría que maximizar en (2.11), en vez de minimizar. La función objetivo (2.11) tiene su fundamento en el teorema 5 del primer capítulo (véase también el primer párrafo de la última sección del mismo capítulo). El conjunto de reglas de parada de una determinada manera, y dependiente de un parámetro (o varios parámetros) recibe el nombre de política. Muchas veces y debido a la dificultad en encontrar la regla óptima el problema anterior se restringe a un subconjunto de reglas posibles (una política, por ejemplo). Los modelos de reparaciones mínimas con costes consideran generalmente las siguientes hipótesis: 1. La función razón de fallos r{t) del sistema subyacente es creciente. 2. El coste de las reparaciones mínimas c^ es menor que el coste de reemplazamiento del sistema Cj.. 3. Los fallos del sistemas son detectados y reparados mínimamente de forma inmediata
Modelos de sistemas reparables con costes 49 2.5.1 Políticas básicas de reemplazamiento En los últimos años, los investigadores han prestado especial atención al problema de la edad óptima de reemplazamiento de sistemas complejos sujeto a reparaciones mínimas. El primer trabajo en este sentido se remonta al año 1960 cuando Barlow y Hunter [27] trataron por primera vez el problema, usando un modelo de reemplazamiento periódico con reparaciones mínimas. El objetivo de este modelo de reparaciones mínimas era encontrar un edad de reemplazamiento t* que minimizara el coste esperado de reemplazamientos y reparaciones mínimas a largo plazo. La política estudiada fue: POLÍTICA 1: Los fallos que ocurran antes de t (fijo) son reparados mínimamente. Cuando el sistema alcance la edad t se realiza el reemplazamiento. El coste de mantenimiento esperado por unidad de tiempo a largo plazo es: C„(í) = íl±f=«ll (2.12) donde N{t) representa el número de fallos (reparaciones mínimas) en el periodo (O, í]. La edad óptima de reemplazamiento t* es el valor t que satisface la ecuación t • r(í) - / r{u)du = — (2.13) Un solución única T* existe si r(oo) = oo. En este caso el coste de mantenimiento esperado por unidad de tiempo a largo plazo es Cpj(T*) = Cmr{T*) Este modelo básico de reparaciones mínimas ha sido generalizado y modificado por muchos autores con el objeto de ajustarse a situaciones más reales. Tilquin y Cléroux [28] añadieron a los costes del sistema, un coste de ajuste Ca{ik) en la edad ¿A;, z = 1, 2, 3,... j k > O, e investigaron una política óptima de reemplazamiento. Respecto a los valores de Ca{ik), ellos suponen que Ca{0) = O y que Ca{s) > O, Vs = ik.
50 Modelos de sistemas reparables Tilquin y Cléroux argumenta que su modelo es más verosímil que el modelo básico, pues los costes de ajuste Ca{ik) pueden usarse para reflejar coste de depreciación, intereses bancarios, costes de ajuste, etc. Al igual que en el modelo básico, el problema es encontrar la edad óptima t* de reemplazamiento del sistema que minimice el coste esperado por unidad de tiempo a largo plazo, que este caso viene dado por, C^_ft),^-~gW')l+'^+ <("(')), (2.14) donde c*(t;(í)) = Xl¿=o''<i(^^) y '^(0 representa el número de ajustes realizados en el periodo (O, í]. Tilquin y Cléroux probaron que el mínimo global de la ecuación (2.14) existe en el intervalo [O, oo). En otro modelo de reparaciones mínimas Muth [29] estudió una política que presentaba un menor coste esperado a largo plazo que el modelo estándar. POLÍTICA 2: Todos los fallos son reparados mínimamente. Sin embargo, el sistema es reemplazado en el primer fallo después de una edad t. A diferencia del modelo estándar el tiempo de reemplazamiento ya no es fijo. En este caso es un tiempo aleatorio superior a un valor fijo t. La función de costes a minimizar en el modelo de Muth para obtener t es: C^N{t)-]rCr donde q{t) = E[T — Í | T > Í] es la función de vida media residual del sistema en el instante t. En la ecuación (2.15) el valor óptimo t* puede hallarse con simples procedimientos de cálculo infinitesimal. Sin embargo, en los casos en que dichas técnicas no son aplicables Muth no dio algotitmo alguno para hallar t*. POLÍTICA 3: Seguir la política 2. Sin embargo, si no ha habido reemplazamiento en el intervalo [r, T] con r < T, entonces se realiza un reemplazamiento preventivo en el instante T.
Modelos de sistemas reparables con costes 51 Makabe y Morimura [30] modificaron por completo el concepto de tiempo de reemplazamiento bajo reparaciones mínimas introducido por Barlow and Hunter [27]. Posterlómente, el modelo fue estudiado por Park [31] para el caso WeibuU. En este modelo se estudió la siguiente política: POLÍTICA 4 : Reparar mínimamente los primeros n—1 fallos y reemplazar el sistema en el siguiente fallo. El coste de mantenimiento esperado por unidad de tiempo a largo plazo es, C,An) = '- ^^^^^^¡^""^ (2.16) donde el valor Tn es el instante en que ocurre el n-ésimo fallo. El valor óptimo n* es el entero más pequeño que satisface la desigualdad: EiTn) - (n - 1 + —)E(T„+i - Tn) > O (2.17) Para una de las distribuciones de fallo más habituales en fiabilidad, la distribución de WeibuU ( función de razón de fallos r{t) = pt^,t > 0,k > 1), Park resolvió el modelo y encontró una expresión explícita para el cálculo del valor óptimo n*, a saber. n = 1 / Cr_ _ + 1 (2.18) "^ 1 \ Cm Park comparó su nueva solución con la solución tradicional basada en edades óptimas propuesta por Barlow y Hunter. Su política da a largo plazo mejores rendimientos que la política de Barlow y Hunter. Además, el número de fallos antes del reemplazamiento es menor en la política de conteo de Park que en la política de tiempos de Barlow y Hunter. Sin embargo, todos estos resultados fueron expuestos numéricamente para la distribución de WeibuU y no se justificó matemáticamente. Phelps [32] comparó los modelos de reparaciones mínimas estudiados por Barlow y Hunter [27], Muth [29], y Park [31] suponiendo que la razón de fallos
52 Modelos de sistemas reparables es creciente. Phelps demuestra que la política de Muth (reemplazar en el primer fallo después de un tiempo t*) es la mejor de las tres políticas y además pone en evidencia que la política de Muth es mejor que la política de Barlow y Hunter. En un artículo posterior, Phelps [33] generalizó su trabajo usando los resultados de procesos de decisión semi-Markovianos para probar que la política de Muth es óptima en el conjunto de todas las políticas de reemplazamientos posibles para modelos de reparaciones mínimas con razón de fallos creciente.
Capítulo 3 UN MODELO DE REPARACIONES MÍNIMAS PARA UN SISTEMA REPARABLE COMPUESTO. Las estrategias de reemplazamiento para diversos modelos de sistemas reparables con reparaciones mínimas están ampliamente estudiadas en la literatura. Sin embargo, cuando un sistema está formado por varios subsistemas, surgen nuevos problemas en relación con la determinación del instante óptimo de reemplazamiento. El propósito de este capítulo es estudiar un modelo para este nuevo problema y encontrar dicho instante óptimo. El contenido de este capítulo ha sido publicado en la revista. Revista Canaria de La Ciencia. 3.1 Introducción Gran parte de los trabajos publicados sobre sistemas reparables asumen que cuando tras una avería se repara un equipo, éste queda en el mismo estado que si fuese nuevo. Tal hipótesis permite elaborar modelos tratables desde el punto de vista matemático, pero resultan poco verosímiles en la práctica. Algo más realista son los modeos considerados por Ascher y Feingold [13] que tratan sistemas cuyo estado, después de una reparación, es idéntico al estado inmediatamente anterior a la ocurrencia del fallo. Los modelos en los que se asume esta hipótesis reciben el nombre de modelos de reparaciones mínimas. Brown y Proschan [17] consideran también modelos de reparaciones mínimas en sistemas de fiabilidad. Block, Borges y Savits [18] estudian un sistema en el que no siempre es posible la reparación mínima, siendo
54 Un modelo de reparaciones mínimas para un sistema reparable compuesto. la probabilidad de que tal reparación sea posible dependiente de la edad del equipo. Stadje y Zuckerman [34] consideran un sistema para el que los sucesivos periodos durante los que está operativo son estocásticamente decrecientes, mientras que los tiempos que duran las reparaciones crecen también en sentido estocástico. Dagpunar y Jack [35] estudian también sistemas de reparaciones mínimas con periodos de reparación no nulos. Una característica común a todos estos trabajos es que las distintas estrategias de mantenimiento se analizan exclusivamente en sistemas consistentes en una única estructura operativa. Sin embargo, cuando se consideran sistemas compuestos por varios subsistemas con distintas funciones, surgen nuevos problemas en la determinación de la estrategia óptima de mantenimiento. En este capítulo se considera un equipo formado por una estructura principal y un subsistema que se encarga de la producción de ciertos ítems. La duración de la estructura principal del equipo hasta que ocurra una avería, signe una distribución de probabilidad con razón de fallo creciente, siendo siempre posible la realización de reparaciones mínimas. No obstante, cada fallo de la estructura principal puede deteriorar el subsistema de producción, de tal forma que la tasa residual de producción de ítems disminuye aleatoriamente después de cada fallo. El subsistema, por su parte, no es reparable, y por tanto la tasa de producción sólo puede restaurarse a su valor inicial mediante el reemplazamiento del equipo. De acuerdo con esta descripción, cualquier estrategia admisible de reemplazamiento deberá, tener en cuenta no sólo la edad del equipo sino también su tasa residual de producción de ítems, que supondremos observable después de cada fallo. No obstante, si este valor no fuese directamente observable, podría sustituirse por alguna estimación adecuada del mismo. En los epígrafes siguientes determinaremos la estrategia óptima de reemplazamiento de este sistema para, una cierta estructura de costes y beneficios, y probaremos que, bajo condiciones específicas, el reemplazamiento del equipo se lleva a cabo casi seg'uramente en tiempo finito. Por último
Introducción 55 analizaremos un caso particular de sistema con estas características, obteniendo una aproximación de la regla óptima de reemplazamiento. Denotamos por X a la variable aleatoria que mide el tiempo que tarda en producirse el primer fallo en el equipo principal. Por hipótesis, X es de razón de fallo creciente, siendo F (t) = P {X > t) su función de supervivencia. Suponemos que tras cada fallo es siempre posible efectuar una reparación mínima, que se realiza de forma instantánea. Llamaremos {Xn} a las duraciones de los sucesivos periodos entre reparaciones mínimas consecutivas, T„ = Y17 = i-^i ^^ tiempo transcurrido hasta el n-ésimo fallo ( TQ = 0), y N (t) = Yl'^= i -^|o,í| (^n) al proceso de recuento de fallos, siendo IE la función indicatriz del conjunto E. Bajo estas condiciones {N [t) ,t > 0} es un proceso de Poisson con función de medias M (t) = E [N (í)] = - In (7 (í)) [18]. Asimismo, suponemos que durante el periodo comprendido entre los fallos i — 1 e ¿-ésimo, el equipo produce ítems a una tasa ai , tomando la tasa inicial siempre un valor fijo «1 , y siendo {a,} una sucesión aleatoria no creciente casi seguramente con E[ai] < aiP^~ j O < P < 1. Por último, consideramos que cada ítem producido reporta un beneficio B, cada reparación mínima tiene un coste C y la sustitución por un equipo nuevo un coste D. Al igual que en los modelos de reparaciones mínimas con costes del capítulo anterior, el problema aquí es encontrar la estrategia de mantenimiento C, que maximiza el cociente .«) = f|| (3.1) siendo T^ la variable aleatoria que mide el tiempo entre dos reemplazamientos consecutivos (un ciclo) del sistema y Z^ la variable aleatoria que mide el beneficio en un ciclo. Las distribuciones de probabilidad tanto de la duración del correspondiente periodo de renovación Tg como del rendimiento Z^ obtenido durante este periodo, quedarán determinadas por la estrategia de reemplazamiento ^ elegida. Deduciremos a continuación la expresión de esta función de utilidad en el modelo considerado. Para ello, y como es habitual en los modelos de reparaciones mínimas.
56 Un modelo de reparaciones mínimas para un sistema reparable compuesto. asumiremos que después de cada reparación la supervivencia del equipo es independiente del número de fallos y subsiguientes reparaciones realizadas hasta ese momento. Por tal motivo, la estrategia óptima de reemplazamiento deberá depender del tiempo de supervivencia hasta el siguiente fallo y no de los fallos anteriores. Como además cada fallo del sistema afecta a la tasa de producción de ítems {Q!„} , la estrategia óptima dependerá también de la tasa de productividad residual en el instante inmediatamente posterior a la avería. Resulta claro, además, que la sustitución del equipo debe realizarse en algún instante de fallo T„ . El estado del sistema en el i/-ésimo instante de fallo queda completamente especificado por el vector (Ty,0!¡y+i). El proceso {(TI/, QÍ¡/+I)}¡^>O es un proceso markoviano con valores en [O, oo) x [O, CXD) . De acuerdo con lo indicado en el párrafo anterior, la estrategia de mantenimiento óptima deberá basarse en este proceso. Como ya se ha señalado, no procede realizar la sustitución entre dos fallos consecutivos, por lo que las reglas de sustitución admisibles consisten en efectuar el reemplazamiento en algún instante de fallo u, cuando el sistema se encuentra en el estado {T^,a¡y^i) . Denotaremos por T al conjunto de dichas reglas. Si una regla .^ G F dispone la sustitución del equipo cuando el sistema está en el estado u , el valor de la función de utilidad (3.1) es: ^ (^) ^ B • E Er=i ex,. (T, - r._i)] -C-{EW]-1)-D ^32) E [T,y] Es inmediato observar que tp está acotada superiormente dado que Q;„ < Oíi , Vn casi seguramente y por tanto ip {^) < B • ai para cualquier regla .^ G F. Sea entonces: ^* = sup^(<^) (3.3) Una estrategia C,* es entonces óptima si: Deduciremos en la siguiente sección la forma de la estrategia óptima ^*.
Determinación de la Estrategia óptima 57 3.2 Determinación de la Estrategia Óptima De acuerdo con la sección 1.9 del capítulo 1, determinar la estrategia óptima de nuestro problema es equivalente a determinar la regla óptima de parada de la sucesión estocástica {Z^}'^i donde, Z, = B-y" ai-{Ti-T,_^)-C-{u-l)-rn. (3.5) •'——'1=1 A continuación probaremos que el problema es monótono y que la regla miope es óptima. En primer lugar verificaremos las tres hipótesis del teorema 16 del capítulo inicial de esta memoria. • E[sup^^Z^] < oo. Z. = BEtl «i • {T^ - T,_i) - C • (i^ - 1) - rn < B • Y.U ^^ • (Ti - Ti-y) < B • EZiC^i • Ti. Por lo tanto, E[snp,Z,] < B • E"i^[«¿ • Tj] = B • E[Ti] E.=i E[a,] < B . E[T,] • a, YZi P'~' < ^- • lim Zi, = —oo. Dado que Z^ = B • Y^i=\ (<^¿"" '^*)' {T ~ T¿-i) — C-{u—l) , ip* > O y la sucesión o¡rj es decreciente a cero casi seguramente se tiene que, P({ai — 'ip*) > O, Vi) = 0. Así, la probabilidad de que un número numerable de términos 0!¿ — i/,* < O es 1. Y por lo tanto lim Ziy = — oo, casi seguramente. • La sucesión de variables aleatorias Y¡y — supjy^[Zj — Z,^) es uniformemente integrable. En este caso, al ser la sucesión a„ decreciente a cero casi seguramente se puede comprobar con facilidad que i?[|y¡/|] -—> O a medida que i^ ^ oo y por consiguiente es uniformemente integrable la sucesión de variables aleatorias Tan sólo resta por comprobar la monotonía del problema. Para ello vamos a demostrar la implicación Zj^ > E{Z¡y^i\Zi,- • • , Z^) =4> Z¡^+i >
64 Teoría de paradas óptimas y fiabilidad Muth es óptima en el conjunto de todas las políticas de reemplazamientos posibles para modelos de reparaciones mínimas con razón de fallos creciente y costes fijos de reparaciones y reemplazamiento. En otro artículo Boland junto con Proschan [36] estudiaron el problema de reemplazamiento de sistemas reparables a través de un modelo con reparaciones mínimas y costes de reparaciones crecientes que depende del número de reparaciones en el ciclo*. Para este modelo consideraron una política de reemplazamiento al estilo de la estudiada por Barlow y Hunter. Sin embargo, esta política no era óptima. Hubo que esperar a 1992 para que Makis and Jardine |37] encontraran la política óptima de reemplazamiento para este modelo. En su artículo Makis and Jardine consideraron un modelo general con reparaciones imperfectas que incluía como caso especial al modelo de Boland y Proschan. Al igual que Phelps, Makis y Jardine resolvieron el problema de encontrar la política óptima utilizando resultados de la teoría de los procesos de decisión semi-Maxkovianos. No obstante, las condiciones que deben verificarse para poder aplicar los teoremas de la teoría de procesos de decisión semi-Markovianos que permiten encontar la política óptima de reemplazamiento son numerosas y no tan elementales de verificar. En este capítulo se obtiene un nuevo procedimiento, dentro del marco de la teoría paradas óptimas, para encontrar la política óptima de reemplazamiento del modelo de Boland y Proschan. En este caso las condiciones que permiten la obtención de la política óptima son más elemetales que las propuestas por Makis y Jardine. La teoría de paradas óptimas parece, como lo demuestran las publicaciones recientes [38], una teoría próspera en el estudio de políticas óptimas de reemplazamientos de sistemas reparables. *Un ciclo es el tiempo entre dos reemplazamientos vecinos.
Modelo de Boland-Proscban y procesos de decisión semi-Markovianos 65 4.2 Modelo de Boland-Proschan y procesos de decisión semi-Markovianos En esta sección vamos a explicar con un poco más de detalle los resultados del artículo de Makis y Jardine en lo que se refiere al hallazgo de la política óptima del modelo de Boland y Proschan. Debe tenerse en cuenta que el modelo estudiado por Makis y Jardine es un modelo más general que incluye al modelo de Boland y Proschan como caso particular. De acuerdo con nuestro objetivo usaremos a lo largo de esta sección la siguiente notación: * Cr = Coste de reemplazamiento. * c„ = Coste de reparación en el n-ésimo fallo, siendo t la edad del sistema. * Fxit) = P{T < x + t\T > x) =Distribución condicional de vida residual cuando el sistema tiene edad x. * m(^x) = Vida media residual. * Tn — rz-ésimo fallo dentro de un ciclo de reemplazamiento. Las hipótesis del modelo son las siguientes: (i) Cr > 0. Cn < k Vn. (ii) Existe un valor cr > O tal que para todo x > 0,m(x) > a, m{0) < oo. (iii) Cn es un sucesión no decreciente. (iv) La razón de fallos del sistema es creciente. A partir de la estructura de costes se deduce que sólo deben tenerse en cuenta políticas que reemplazan en un instante de fallo. Por tanto en cada fallo n las decisiones a tomar son reemplazar con coste c^ ó reparar con coste c„. A partir de las hipótesis (i) y (ii) anteriores podemos aplicar un resultado de la teoría de procesos de
66 Teoría de paradas óptimas y fiabilidad decisión semi-Markovianos [39] que garantiza la existencia de una función acotada w y una cosntante g* tal que, w{n,x) =mm<Cn+ w{n+ l,x-\-t)F^{dt) - g*T{x),Cr + ¡ w{l,y)F{dy) - g*r{0) De acuerdo con un teorema (ver, [39]), la política que minimiza el término derecho de la función anterior es óptima y g* es el coste promedio esperado por unidad de tiempo. A partir de ese resultado Makis y Jardine obtienen el siguiente teorema (que resuelve el problema). Teorema 11 Bajo las hipótesis (i)-(iv), la política óptima de reemplazamiento del modelo de Boland y Proschan es la siguiente : Reemplazar en el n-ésimo fallo si Tn > t*^ donde Tn es el instante del n-ésimo fallo ytl = inf{í > O : c„ > g*r(í)} La sucesión {í* } no es creciente, íí > ¿2 — • • • 4.3 Modelo de Boland-Proschan y teoría de paradas óptimas En esta sección vamos a obtener la política óptima de reemplazamiento del modelo de Boland y Proschan utilizando algunos resultados de la teoría de paradas óptimas. Recuédese que es preciso tener en cuenta que deben considerarse tan solo las políticas que remplacen en instante de fallo. Como criterio de optimalidad para encontar la política óptima, adoptaremos el criterio usual del costo promedio a largo plazo. Por argumentos clásicos de la teoría de la renovación, el coste promedio a largo plazo del sistema gobernado por la política de reemplazamiento T viene dado por, VT = E(RT)/E(T) (4.1) donde RT es el coste total necesario para mantener el sistema en funcionamiento hasta el instante T. Sea V* = inf Vy, donde T es el conjunto de todas las políticas que
Modelo de Boland-Proscban y teoría de paradas óptimas 67 reemplazan en un instante de fallo. Una política de reemplazamiento T* es óptima si, VT* = infür (4.2) Ter Obviamente, E{RT) > V*E(T), para todo T e F, and T* es óptima si y solo sí E{RT* - V*T*) = iníE{RT - V*T) (4.3) Atendiendo a la anterior ecuación y no olvidando que las únicas políticas que deben tenerse en cuenta son aquellas que paran en un fallo, el problema de encontrar la política óptima para el modelo de Boland y Proschan puede plantearse como: hallar la regla de parada óptima para la sucesión estocástica, n - 1 Zn = cr+J2 ""'- \/*T„ , n > 1 (4.4) i = 1 Proposición 1 El problema de regla de parada anterior es un problema de caso monótono. Demostración. Tenemos que probar la siguiente implicación, Zn ^ E{Zn+l\Zi, • • • , Zn) => Zn+1 ^ E\ZnJ^2\Z\, • • • , Zn+l) Es claro que, Zn+i = Z^ + Cn — V*{Tn+i — Tn). Entoces teniendo en cuenta las hipótesis anteriores Z„ < E{Zn+i\Zi,- • • , Z^) es equivalente a c„ > V*m{Tn). Además, como c„+i > c„ y m{Tn) > "^(T„+i), se tiene que, Zn+i < E{Zn+2\Zl,- • • ,Zn+l)- • Por tanto y de acuerdo con los teoremas de la teoría de paradas óptimas (ver [12], pág 113) la regla de parada, N = mí{n >l\Zn< E{Z^+,\Z,,- • • , Z^)} es óptima. Es decir , la política óptima de reemplazamiento es N = inf{n > 1 I c„ > V*m{Tn)} (4.5)
68 Teoría de paradas óptimas y fiabilidad Desde luego esta política no estará completamente determinada hasta que no se conozca el valor V* que aparece en (4.5). Para calcular dicho valor podemos utilizar el algoritmo de punto fijo que mencionamos en la última sección de primer capítulo. Otra alternativa sería aplicar el algoritmo propuesto por Makis y Jardine, el cual se basa en un algoritmo mucho más general dado por Aven y Berman [40]. Para ver comparaciones entre la política óptima de reemplazamiento y la política de reemplazamiento periódico propuesta por Boland para el caso particular de distribuciones WeibuU y exponencial puede consultarse de nuevo el trabajo de Makis y Jardine.
Capítulo 5 DIMENSIONAMIENTO ÓPTIMO DE UN SISTEMA DE COLAS Hemos visto cómo la teoría de la renovación proporciona una potente herramienta para resolver problemas de optimización asociados a procesos estocásticos que se caracterizan por la presencia de instantes de renovación, a partir de los cuales el proceso repite su comportamiento (en sus aspectos probabilistas). En particular ello nos ha servido para obtener instantes óptimos de reemplazamiento en el contexto del problema de reemplazamiento de sistemas reparables. En este capítulo veremos una nueva aplicación de la teoría de la renovación; esta vez en el contexto de un problema de colas. 5.1 Motivación y presentación del modelo Las actuales redes de comunicaciones de banda ancha están diseñadas para soportar y acomodar, de manera flexible y eficiente, una amplia variedad de servicios tales como voz, vídeo, datos y sus combinaciones multimedia. Para cumplir con estos objetivos se han diseñado diversos estándares de red, entre los que cabe destacar ATM como uno de los más importantes. En este estándar la información que viaja por la red se organiza en pequeños paquetes de longitud fija llamados células. Los diferentes tipos de aplicaciones que hacen uso de la red pueden variar en sus requerimientos de servicio. Así, por ejemplo, las aplicaciones en tiempo real, tales como la videoconferencia, requieren prestaciones extremas en términos de volumen de tráfico (throughput), de retardo, de la variación del retardo [delay jitter, jitter o varianza en el retardo) y de la tasa de pérdidas. La cada vez mayor generalización
70 Dimeiisionamiento óptimo de un sistema de colas de estas aplicaciones ha convertido en urgente la necesidad de proporcionar servicios de red con prestaciones garantizadas y desarroUcir los algoritmos que soporten estos servicios. Uno de los mecanismos fundamentales para poder proporcionar servicios con prestaciones garantizadas es la elección de la disciplina de servicio de paquetes en los conmutadores, que son los dispositivos físicos encargados de combinar el tráfico procedente de distintas fuentes. En una red de conmutación de paquetes, los paquetes de distintas conexiones interactúan unos con otros en cada conmutador, y sin el control apropiado estas interacciones pueden llegar a afectar a las prestaciones de la red. La disciplina de servicio del nodo de conmutación controla el orden en el que los paquetes son servidos y determina cómo interactúan los paquetes de las distintas conexiones. Una forma de conseguir este objetivo es mediante la implementación, en los buffers del conmutador, de mecanismos de prioridad capaces de controlar el tiempo o espacio dedicado a cada célula. Debido a su simplicidad, rapidez y más bajo coste de implementación, en los conmutadores de alta velocidad se prefieren los mecanismos de prioridad que controlan el espacio (capacidad) disponible en el buffer, a los que deben tener en cuenta el instante de llegada de cada célula y controlar su tiempo de residencia en el conmutador. En este trabajo se presenta y analiza un esquema de dimensionado y gestión de buffers que tiene en cuenta el patrón de llegada de dos clases de tráfico. En particular, hemos considerado que estas clases de tráfico corresponden, respectivamente, a tráfico en tiempo real (voz, video) y a tráfico en tiempo no real (datos). Por simplicidad llamaremos TR al tráfico de la primera clase y TNR al de la segunda. En los últimos años se han desarrollado numerosas políticas de servicio para el tráfico resultante de la mixtura de estas dos clases, con el objetivo fundamental de que la red pueda ofrecer calidad de servicio al tráfico en tiempo real, a la vez que se garantiza un determinado nivel de prestaciones para el tráfico en tiempo no real. En particular la calidad de servicio para tráfico TR exige un bajo nivel de retardo en el tránsito de los paquetes
Motivación y presentación del modelo 71 (no es posible mantener una conversación telefónica si los paquetes de voz digitalizada llegan de manera muy asincrónica), mientras que para el tráfico TNR se requiere una muy baja tasa de pérdidas (este es el tráfico habitual en internet correspondiente a la descarga de ficheros; lo importante es no perder el contenido del fichero aunque tarde algo más en llegar a destino). Ello no quiere decir que para tráfico en tiempo real sea admisible una tasa de pérdidas excesivamente elevada, ni que el tráfico en tiempo no real pueda llegar a demorarse cualquier cantidad de tiempo, sino más bien que las pérdidas admisibles en tráfico TR son varios órdenes de magnitud superiores a las del tráfico TNR; y a la inversa, el nivel de retardo admisible en tráfico TNR puede llegar a ser también varios órdenes de magnitud superior al admisible para tráfico TR. En [41] puede encontrarse un análisis comparativo de diversas políticas para el multiplexado de tráfico en tiempo real con tráfico en tiempo no real, incluyendo una revisión de trabajos de investigación previos. La más simple de estas políticas es la clásica política PIFO, que es la que oñ:ece peores resultados para ambos tipos de tráfico. Los resultados mejoran cuando se asigna prioridad más alta a los paquetes del tráfico TR, siendo atendidos antes que los paquetes TNR, que resultan de esta forma penalizados con unos retardos excesivos. Otras políticas alternativas y mejores son MLT (Mínimum laxity threshold) que asigna prioridades en función del tiempo que ya hayan permanecido en cola los paquetes de las distintas clases y del tiempo máximo en cola admisible para los paquetes TR, y la QLT (Queue Length Threshold) en que se da prioridad a los paquetes NRT sólo cuando el número de los mismos en cola supera un cierto umbral. El rendimiento de estas dos políticas es similar, si bien la última es más fácil de implementar físicamente, toda vez que no requiere contabilizar el tiempo de permanencia en el buffer de cada uno de los paquetes presentes en el mismo, y resultando con ello, como ya hemos dicho más arriba, la política preferida. Otra clase de políticas, muy habitual para gestionar la multiplexación de estas dos clases de tráfico, es la formada por los mecanismos basados en rondas, consistentes básicamente en alternar el servicio entre los distintos canales de entrada
72 Dímensionamiento óptimo de un sistema de colas al conmutador. La más simple de estas políticas consiste en atender una célula de cada canal, desde el primero al último, y vuelta a empezar desde el primer canal (este es el mecanismo round-robin clásico [42], [43]). Una variación de esta política consiste en asignar prioridades a los canales en función de la clase de tráfico (weighted round robin), atendiendo en cada ronda más células en los canales de mayor prioridad que en los canales de prioridad más baja; por ejemplo, se podrían atender tres células de un canal de video por cada célula de un canal de datos. Se han presentado numerosas propuestas sobre la forma en que debería distribuirse la atención del servidor entre los diversos canales. Algunas de estas políticas fijan las prioridades de cada clase de tráfico de modo estático (de una vez para siempre) [44], [45] mientras que otros asignan las prioridades dinámicamente, en función de las condiciones de la red y de la carga del sistema [46], [47]. Muchas de estas políticas para la asignación dinámica de prioridades especifican umbrales: mientras en el canal A haya menos de n células esperando, se atiende al canal B; una vez que en A haya n células, el servicio se dedica exclusivamente a A hasta que en A queden menos de m células. Estos umbrales pueden también ser fijos, determinados en el diseño del hardware que constituye el conmutador [48], o flexibles/adaptativos, controlados por software en función de las condiciones de tráfico en cada momento [49], [50], [45]. El mecanismo que presentamos en esta tesis, está basado en un sistema de rondas que incorpora a los buffers de entrada al conmutador propios de cada canal, un buffer adicional que es compartido por las dos clases de tráfico. Este sistema es gestionado por una política que, en cierta medida, prioriza al tráfico TR, para evitarle retardos excesivos, a la vez que permite cursar el tráfico TNR con un mínimo nivel de pérdidas. Un correcto dimensionado de los buffers que componen este mecanismo permite que esta política pueda proporcionar una reducción en los retardos de las células de alta prioridad (tiempo real), sin que por ello se vean afectadas considerablemente las prestaciones dadas al tráfico de baja prioridad (tiempo no real).
Motivación y presentación del modelo 73 TRAFICO EN TIEMPO NO REAL TRAFICO EN TIEMPO REAL BUFFER TNR (CAPACIDAD R) BUFFER TR (CAPACIDAD N) BUFFER COMPARTIDO (CAPACIDAD M) SERVIDOR Figura 1 Diseño del sistema de colas Tal como se observa en la figura 1, el tráfico en tiempo real (TR) accede a su propio bufi:er, que tiene una capacidad limitada para R células. Asimismo, el tráfico en tiempo no real (TNR) accede a un segundo buffer con capacidad A^. Las células que salen de ambos buffers se mezclan en un tercer buffer compartido, con capacidad para M células. La salida de este tercer buffer es el canal de transmisión, sobre el que se multiplexan ambos tráficos. La gestión del sistema se produce del siguiente modo: 1. En cada instante, en el buffer compartido puede haber sólo una célula TNR, y como máximo M — 1 células TR. 2. Si no hay ninguna célula TNR en el sistema, la primera célula TNR que llegue al mismo pasa directa e instantáneamente al buffer compartido. Si hay ya una célula TNR en el buffer compartido, cualquier nueva célula TNR que llegue al sistema se incorpora al buffer TNR. ^,->
80 Dimensionamiento óptimo de un sistema de colas • durante un servicio el sistema puede alcanzar el estado (a, 0,0) solamente si comenzó en un estado (¿,0,0) con i < a, • durante un servicio, el sistema puede alcanzar el estado (a, b, c) con 1 < c < M sólo si el servicio comenzó con el sistema en algún estado (i,j,c), con i < a, j ^ b (ya que la posición c del cliente TNR en la cola compartida no se altera durante un tiempo de servicio), o bien si el sistema empezó en algún estado (i, 0,0) con i < a, i < c, podemos escribir las siguientes ecuaciones: Sic-l<a<R + M-l, l<c<M,0<b<N: , a b a E [Tabc] = . . ^(l,0,0)(a,b,c) + V] Y] -^^ [%c] ^(¿,i,c)(a,6,c) + V] -E" [-^¿Oo] ^(i,0,0)(a,b,c) (5.10) Si 0<a<i? + M-l, 0<6<iV ^ f'^""^ ^ X M x,,Ao,0,l)(a,fe,l) + 5Z S -^ [-^^^lí -4(¿j,l)(a,b,l) (5.11) Si 0<a<R + M -1 . a b —I Afí + AAÍ • n • n A " -£^ [TaOo] = -J —T—^(l,0,0)(a,0.0) + / ^ [NÍOQ] ^(¿,0,0)(a,0,0) (5.12) M + ^N -^ Dado que las llegadas y salidas en este sistema se producen de una en una, cuando el sistema está en equilibrio el número medio E[Nabc] de salidas que dejan el sistema en el estado {a,b,c) es igual al número medio de llegadas que encuentran el sistema en este estado. Ahora bien, puesto que las llegadas se producen según un proceso de Poisson, (siempre que el sistema disponga de espacio disponible para alojar a cada nueva llegada), este último número medio es X^^^E [Tabc], donde: XR + XN sia<R + M-lyb + c<N + l XR sia<R + M-lyb + c>N + l \bc — \ XN si a > R + M-lyb + c<N + l O sia>R + M-lyb + c>N + l
Cálculo de las probabilidades estacionarias del sistema 81 Por tanto: E [Na,e] = XltcE [Tabc] Sustituyendo estos valores en el sistema de ecuaciones (5.l0),(5.11)y(5.12), llamando PR = ^ ^^^ , PN — ^ +A ^ dividiendo todos los términos por la duración media del ciclo, E[T], y teniendo en cuenta (5.8) y (5.9), se llega a: Sic-l<a<i? + M-l, l<c<M,0<b<N: a b a T^abc = PiíA*(,c7r000^(l,0,0)(a,b,c) + 2^ 2^ KhcT^o.bcA{i,j,c){a,b,c) + ¿^ A*5^7r¿oO-4(¿,o,0)(a,6,c) i=c—1 j=0 i=\ (5.13) Si Q<a<R + M-l, Q<h<N a b TTafel = PArA*fc^7roooA(o,0,l)(a,6,l) + ¿J zJ -^abc^¿jl^(¿J,l)(a,fe,l) (5-14) Si 0<a<fí + M-l a TTaOO = í'JíA*^c'^O0O^(l,0,O)(a,O,0) + 2_^ A*^^7r¿00^(z,0,0)(a,0,0) (5.15) Si en este sistema se dividen todas las ecuaciones por TTOOOÍ llamando O^hc = TTafcc/TTOOO, puedeu obtenerse con facilidad de modo recursivo las 6abeLas Habc se obtienen luego fácilmente sin más que observar que: de donde: ^000 = ^ 7— y 7r„fcc = T—e^ — J- (5-16) Obviamente, aún falta determmar los términos A{i^j^k)(a,b,c)- Comencemos por calcular ^(¿,j,c)(a,b,c) para 1 < c < M, O < í < a, O < j < 6. Para ello definimos la variable aleatoria:
82 Dimensionamiento óptimo de un sistema de colas ^{ij,k)(a,b,c) * si en el instante t el sistema está en el estado (a, b,c), y aún 1 \ no ha terminado un servicio que comenzó en el instante O con el sistema en el estado (i,j, c) O en otro caso Es evidente entonces que: A(i,j,c)(a,b,c) - E Ahora bien: /•oo "I roo ^0 J Jo E [Xj = P (x* = 1) = (1 - B{t)) e-^^«*ÍM!2e->-*ÍM b-j {a-i)l {b-j)\ donde B{t) es la función de distribución del tiempo de servicio. En el caso particular de servicio determinista de duración D se tiene; B{t) = 0 t < D 1 t> D Luego, en este caso: A(¿, J,c),(a,í),c) — / Jo \-U>^Bty Á^Ntf Si llamamos: G(m.n) ^ ff e-^-'íi^e-^'"i^dt í'(r„,n)=e-(^»«»)°Slg£7 puede comprobarse fácilmente la relación recursiva: G{m,n) = Aií con valores iniciales: G{ml,n) + ^^ G{m, n-l)- F{m, n) (5.17) ^R + ^M G (m, 0) 1 Ai? + XM A R Afí + AM _ g-(Afl+A„)D E h=0 X R ' {XRD) m—h >^R + ^MJ {m-h)\ (5.18)
Cálculo de las probabilidades estacionarias del sistema 83 G{0,n) = ^R + XM •'"E >^R + >^MJ r^V^ñ + ^M/ {n-h)\ (5.19) De esta forma, Aiij,c)(aM = G{a-i,b-j),l<c<M,0<i<a,0<j<b (5.20) y su valor puede calcularse utilizando recursivamente (5.17) con los valores iniciales (5.18) y (5.19). Para calcular ahora A(,^o,0)(a,6,c); con 1 < c < M debemos notar que para que durante un tiempo de servicio se pase del estado {i, 0,0) al (a, b, c), deben haber llegado a — i clientes TR y b + 1 clientes TNR, con la condición de que el primer cliente TNR haya llegado cuando hay exactamente c — 1 clientes TR en el sistema. Utilizando la propiedad del proceso de Poisson de que si en un periodo (0,í) se producen n ocurrencias del mismo, éstas se distribuyen uniformemente el el intervalo, la probabilidad de que la primera llegada de un cliente TNR sea la que ocupe la posición c en la cola compartida habiendo llegado a — i clientes TR y 6 + 1 clientes TNR en (0,í), viene dada por: {a-c + iy.{a + b + l-i)l Procediendo ahora como para el cálculo de A(¿^j^c)(a,fc,c), llegamos a: A..o..,,(.V, = ^^:f,^!^tltl:'|, (* + 1)!G (a - >,. + 1) (5.22) Un razonamiento similar, teniendo en cuenta ahora que para que un cliente TNR ocupe la posición M debe haber llegado cuando en el sistema hay M — 1 ó más clientes TR nos permite obtener: {a-ij. (a + 6 + 2-Af)!^, A(,o,o),(.,M) = (,_M + 1)! (a + 6 + 1-0!^ {a-^,b+l) (5.23)
84 Dimensionamiento óptimo de un sistema de colas Por último, también de modo muy sencillo se deduce que: ^(¿,o,o)(a,o,o) =G{ai, 0) (5.24) De esta forma, las ecuaciones (5.20), (5.22), (5.23) y (5.24) junto con (5.17) nos proporcionan el esquema recursivo preciso para obtener finalmente las probabilidades en el equilibrio 7r¿jfc a partir de (5.13),(5.14),(5.15) y (5.16). 5.4 Probabilidades de pérdida. Un cliente TR es rechazado por el sistema cuando a su llegada no hay espacio en buffer para alojarlo; ésto ocurre cuando en total en el sistema hay R + M — 1 cientes TR. Por tanto, la probabilidad de pérdida en el estado estacionario para los clientes TR viene dada por: M N ITR = ^R+M-1,Q,0 + / ,7 ^'^R+M-l,b,c c=l b==:0 Dado que durante un ciclo tratan de acceder al sistema por término medio \iiE[T] clientes TR, si llamamos LTR{T) al número de clientes TR rechazados por ciclo, se tiene, haciendo uso de (5.9): E [LTR (T)] = ^T^XnE [T] .= ITR^R {XR + Xp¡) TTooO Asimismo, la probabilidad de pérdida en es estado estacionario para los clientes TNR viene dada por: R+M-l M ITNR = ZZ Z^ ^"^'^ a=0 c==l y el número medio de clientes TNR rechazados por ciclo es: E [LTR (T)] = ^^^X^E [T] = ^^f ^ (5.25) [ÁH + ÁN) TTOOO
Tiempos de espera. 85 5.5 Tiempos de espera. Situémonos en nuestro sistema en el preciso instante en que se acaba de completar un servicio (se transmite una célula), que ha dejado el sistema en estado (a, fe, c), y sea , con i < a, el tiempo que aún debe esperar en cola el cliente TR que tiene delante i — 1 clientes TR. Obviamente, si z < M — 1: ^ Xj sii<cóc = b = 0 u^rtc = 'f (5.26) Y^Xj si i>c>l siendo Xj la duración de un tiempo de servicio. Ahora bien, si ^ > M, el tiempo de espera de este cliente no se verá afectado por los nuevos clientes TR que lleguen a partir de ahora, pero sí podría verse afectado por los clientes TNR que llegasen a partir de este momento. En efecto, existe la posibilidad de que durante el tiempo que tarde nuestro cliente TR en llegar al buffer compartido, en virtud de la política de gestión empleada puedan acceder a este buffer clientes TNR que llegaron después que él, pero que encontraron ninguna o poca cola en su buffer específico y pudieron entrar pronto en el buffer compartido. Podemos establecer entonces las siguientes relaciones de recurrencia para el tiempo de espera de nuestro cliente TR: • Si c = 0: /• X + a;¿_i,o,o con prob. f3 u^m = I X + u;¿_ij,M-i con prob. (3^^^, 0<j<N (5.27) X + a;¿_i,7v,M-i con prob. /?^^i donde X es la duración de un tiempo de servicio y /?^ es la probabilidad de que durante un tiempo de servicio lleguen al sistema k clientes TNR. Por su parte, Pl.es la probabilidad de que durante un servicio Uegnaen k ó más clientes TNR. • Sic= 1:
86 Dimensionamiento óptimo de un sistema de colas í^iOl = < X + «^¿,0,0 con prob. /?o ^i,3,M con prob. /^^-^j, Q < j < N X + uji,N-i,M con prob. ^^ (5.28) OJibl = x + u}i.b-i+j,M con prob. (3^,0 < j < N — b,0 < b < N X + Ui_ij^M-i con prob. P''i^._^ (5.29) <^ií,JV,l ~ X + LüK,N-l,M (5.30) • Si 1< c < M: X + a;¿_i,t+^-c-i con prob. ¡3,¡,0 < j < N - b,0 < b < N (^ibc = <\ ^ (5.31) A^ + c<;¿_i,iv,c-i con prob. /?-v_6 í^i.Mc — A + Ci;,:_i jv,c-i (5.32) De estas ecuaciones de pueden obtenerse las siguientes relaciones de recurrencia para los tiempos medios de espera: • Sii < M-1: E [uJibc] = {i - l)E[X] si. i<cóc = b = 0 iE[X] sii>c>l (5.33)
Tiempos de espera. 87 • Sii>M: N-l E[U;ÍOO\ = E[X]+(3oE[u;i_i^o,o] + E /?J+I£^[C^¿-IJ.M-I] +/5^+IÍ^N-I,JV,M-I] i=o E[Lüm] = E[X] + PoE['^r,o,o] + ¿ PJ+,E[LÜ,J_M] + /3*j,E[u,,N_r^M] E[UJM] = E[X] + ¿ p^E[cüi,b-i.M] + P*N-bE[uJi,N-i,M] conO <b<N E[uim] = E[X] + E E[ujibc] = E[X] + ¿ pjE[uJi_,,b+j.c-i] + f3N-bE[u)i-i,N,c-i] conO <b<N E[Lüim] = E[X] + E (5.34) Las ecuaciones (5.34) junto con los valores iniciales dados por (5.33) permiten obtener recursivamente las esperanzas E[ujijk] para todos los estados {i,j, k) posibles. La resolución de estas ecuaciones será más o menos difícil en función de cuál sea la función de distribución de probabilidad del tiempo de servicio. En el caso particular de tiempo de servicio determinista de duración D se tiene: E[X]^D , /9, = e-^-^í^ , /?* = l_ge-^-^í^ (5.35) Ahora bien, las esperanzas obtenidas en (5.34) corresponden a los tiempos medios de espera en cola medidos a partir del momento en que termina un servicio. El tiempo de espera global de un cliente TR que a su llegada encuentra el sistema en estado (a, b, c) es: • Si a < M1: W, XRES + '^^XÍ slc = b = 0 abe 1=1 XRES +Y^Xi si c> 1 (5.36) ¿=1 donde X^^s es el tiempo de servicio residual que falta para que termine el servicio del cliente que ocupa la cabecera de la cola compartida a la llegada del cliente TR.
Dimensionamiento óptimo de un sistema de colas • Si a > M - 1: Si durante el tiempo de servicio residual del cliente que ocupa la cabecera de la cola llegan nuevos clientes TR, éstos no afectan al tiempo de espera del cliente TR que acaba de llegar. Sin embargo, por la misma razón señalada más arriba, sí que afectan los clientes TNR que lleguen durante este tiempo. Si llamamos ak a la probabilidad de que durante el tiempo de servicio residual posterior a la llegada del cliente TR lleguen k clientes TNR, y a la probabilidad de que lleguen k ó más, tenemos: Wabc = < XRES + ^a-l,j,M XRES + í^a-l,N,M ^RES + í^a-1,0,0 XRES + ^a,j,M XRES + l^a,N-\,M XRES + í^a,b+j-l,M XRES + <^a,N,M con prob. a^+i,0 < j < N con prob. a*j^_^-^ con prob. ao con prob. ctj+i, O < j < A^ — 2 con prob. a*¡^ con prob. aj,0 < j < N — b con prob. cx*j^¡_^ XRES + üJa-i,b+j,c-i con prob. a^,O < j < N XRES + t^a-i,N,c~i con prob. a^_b XRES + ^a-1,0,0 con prob. «o {b = {b = (c = (c = (c = (c = (c = (c > (c > {b = c c 1, 1, 1, 1, 1, 1) 1) c = 0) = 0) 6 = 0) 6 = 0) 6 = 0) 6>0) 6>0) = 0) (5.37) De modo similar a como hicimos anteriormente paxa las a;¿jfc, podemos ahora hallar a partir de (5.37) el tiempo medio de espera en cola para un cliente TR que a
Tiempos de espera. 89 SU llegada encuentra el sistema en el estado (a, b, c): N E[Wam] = E[XRES] + O¡0-E[a;a-I,0,o] + E aj+iE[cüa-l,j,M] + Ol*^+iE[íJa-l,N,M] j=Q N E[WaOl\ = E[XRES] + aoE[u;a,Q,o] + E «i+l£^[^aj,M] + «Wl-^ [^a,N,M\ N-b E[Waba] = E[XRES] + E ajE[Ua.b+j-l,M] + a*pf-bE[uJa,N,M]^ COn O < b < N N-b E[Waba] = E[XRES] + E «,-£^[^a-l,fe+i-l,c-l] + a%_i,EK-l,N,c-l], COU O < b < N, C > 1 (5.38) Estas esperanzas pueden calcularse recursivamente utilizando como valores iniciales las esperanzas que se obtienen directamente de (5.36): E[W,oo] = E[XREs] + {a-l)E[X] ,1 < a < M - 1 (5.39) E[Wabc] = E[XRES] + aE[X] c > 1 y la condición obvia: iífW^ooo] = 0. Como ya ocurrió con las E[ujijk], la obtención de las esperanzas en (5.38) depende de la dificultad de cálculo de las «fc. En el caso particular de servicio determinista de duración D puede probarse que: Jo k\ D XMD -x.(D-t){MD-t))'l,^ _ _1 , ^-,,D s^ {XNDY .^0 r. (5.40) En este caso, además E[XRES] — D/2. De esta forma, estamos ya en condiciones de poder calcular el tiempo medio de espera de un cliente TR arbitrario. Simplemente condicionando por el estado del sistema a la llegada de este cliente tenemos: EW^] = Y, ElWahcUa^c (5.41) (a,b,c) El valor de esta esperanza se calcula haciendo uso de (5.38) y (5.39), con las probabilidades estacionarias halladas en (5.13,5.14,5.15) y (5.16).
96 Dimensionamiento óptimo de un sistema de colas Probabilidad de Pérdida TNR M mult 1 0.10 0.95 N = 2 Probabilidad de Pérdida TR a -^ _ Q. M mult 1 0.10 0.95 N = 2 ce ITiempo Medio de Espera TNR E - - Q@ooooooooo< —r10 -1 T" 15 20 M 25 —r 30 mult 1 0.10 0,95 N = 2 Tiempo Medio de Espera TR 10 15 M 20 25 30 mult 1 0.10 0.95 N = 2 Figura 4 Caso N = 2. Probabilidades de pérdida y tiempos medios de espera frente a la suma de los tamaños de los buffers M y R. (Negro N = 1, Rojo N = 2, Verde N = 3, Azul A^ = 4, Celeste TV = 5, etc.)
Análisis de los resultados 97 Probabilidad de Pérdida TNR •Oí a. o o§g§88§88888889«@§0§§oooooooo( 10 15 M I 20 I 25 30 mult 1 0.10 0.95 N Probabilidad de Pérdida TR ce I- (D T_ O. 0) -^ _ M mult 1 0.10 0.95 N = 4 Tiempo Medio de Espera TNR E ^ - M mult 1 0 10 0.95 N = 4 Tiempo Medio de Espera TR E 0) í88^ CX5CX300 OOOOOO „°ooooo °ooooo OC3000 oooo ooo OO o 10 15 M 20 25 "T" 30 mult 1 0.10 0.95 N = 4 Figura 5 Caso A'^ = 4. Probabilidades de pérdida y tiempos medios de espera frente a la suma de los tamaños de los buffers M y R. (Negro A^ = 1, Rojo N = 2, Verde N = 3, Azul N = A, Celeste A^ = 5, etc.)
98 Dimensionamiento óptimo de un sistema de colas ce z Probabilidad de Pérdida TNR 5 - OOOOOOOOOOOOCXJOOOOOOOOOOOCXDOOC 10 15 M 20 25 T 30 mult 1 0.10 0.95 N = 8 o: z Tiempo IVIedio de Espera TNR PSg®Í§8^^^ 10 15 M 20 25 mult 1 0.10 0.95 N = 8 30 •0) Probabilidad de Pérdida TR M mult 1 0.10 0.95 N = 8 Tiempo IVIedio de Espera TR DT- — o" obSooc OOCXDC» OOOOOO Oooooo "OOOOO °CIO0O oooo ooo oo o 10 15 M 20 26 30 mult 1 0.10 0.95 N = 8 Figura 6 Caso N = 8. Probabilidades de pérdida y tiempos medios de espera frente a la suma de los tamaños de los buffers M y R. (Negro A^ = 1, Rojo N = 2, Verde N = 3, Azul iV = 4, Celeste iV = 5, etc.)
Análisis de los resultados 99 De esta forma, observamos que, en estas condiciones, el diseño óptimo del sistema consiste en: • Un buffer compartido de tamaño reducido, que acortaría los tiempos de espera de los clientes TNR, a la vez que no causaría gran impacto en los tiempos de espera de los TR, ya que los TNR llegan con una tasa relativa muy baja. • Un buffer específico para los clientes TR con un tamaño R ajustado de tal manera que el tiempo de espera de estos clientes no sea excesivo, a la vez que las pérdidas que necesariamente se producen no superen el umbral preespecificado. • Un buffer específico para los clientes TNR que garantice que las pérdidas para esta categoría serán reducidas; dado que estamos en condiciones en las que Xi\¡ es pequeño, dicho buffer podrá tener un tamaño N no demasiado grande. Las expresiones obtenidas en este capítulo para probabilidades de pérdida y tiempos medios de espera permiten determinar exactamente los valores M, N, y R que cumplan los requisitos especificados. 5.7.2 Caso 2: XR « XN, p = 0.95 Ahora nos encontramos ante un sistema en el que la tasa de llegadas dominante corresponde al tráfico TNR, como ocurre en redes orientadas fundamentalmente a la transmisión de datos y que pueden emplearse de modo más o menos esporádico para la transmisión de voz o video. Asimismo hemos considerado una intensidad de tráfico elevada (0.95) lo que, al igual que en el caso anterior, nos indica que el sistema se encuentra cargado, con un servidor cuya velocidad de servicio se equipara prácticamente a la velocidad con que llegan los clientes, que en su mayor parte son de clase TNR. Por ello podemos esperar que se poduzcan colas largas de clientes TNR, lo que significa que para evitar pérdidas en esta categoría deberemos contar con un buffer específico para este tráfico con un tamaño A^ holgado, aún a costa de incrementar los tiempos de espera para esta clase de clientes.
100 Dimensionamiento óptimo de un sistema de colas De nuestro análisis de los resultados numéricos obtenidos con el modelo, que se muestran en la figura 7, podemos observar que la tasa de pérdidas en el tráfico TNR depende sólo de N y es bastante insensible al tamaño del buffer compartido M, y al tamaño del buffer R de los clientes TR. No obstante, observamos que el tiempo de espera de los clientes TR (que, recordemos, nos interesa que sea reducido), sí que se incrementa con TV, sobre todo si el tamaño del bufl'er compartido es pequeño. Esto es fácil de entender, ya que al ser muy elevada la tasa de llegadas de clientes TNR, en el buffer compartido habrá casi siempre un cliente TNR esperando ser atendido. Si nos situamos en el caso extremo de que fuese M = 2, ello signficaría que la cola de clientes TR se formaría en su buffer específico y cada cliente TR que accediera al buffer compartido debería esperar casi siempre por un cliente TNR. Ello terminaría dando lugar a tiempos de espera inaceptables para el tráfico TR. Por tanto, el diseño óptimo de este sistema sería el siguiente: • Un buffer compartido con un tamaño M adecuado a la tasa de llegadas (que es baja) de los clientes TR y que garantice que sus tiempos de espera no sean elevados. • Un buffer específico para los clientes TR que no debe ser demasiado grande ya que con su baja tasa de llegadas podrían caber casi siempre en el buffer compartido; esa baja tasa de llegadas, a su vez, garantiza que las pérdidas no serán elevadas. • Un buffer específico para los clientes TNR que sí que debe tener el tamaño suficiente para que puedan esperar sin que se produzcan pérdidas significativas. Al igual que en el caso anterior, las expresiones obtenidas en este capítulo para probabilidades de pérdida y tiempos medios de espera permiten determinar exactamente los valores M, N, y R que cumplan los requisitos especificados.
Análisis de los resultados 101 Probabilidad de Pérdida TNR a. o ce 2 ni '- — OOOOOOOOOOOOOOOOOOOOOOOOCXDOOC OOOOCX3CXD(X>OOOOOOOOOCXX)03C»CX5C OOOOCK30OO0OOO0OOO0OOCX5OO0OOOC CXDCX30OOO0OOOO0OO0OOCXX>0OOOCX3< 0O000000CX30O00000000OO0O0OOOC ooooooooooooooooooooooooooooc I QQQQQQQQQQQQQQQQQQPQQQQPQPQQC 1 0 1 5 1 1 10 15 M + R mult 1 50.00 1 20 0.95 1 25 1 30 LU Tiempo lUledlo de Espera TNR CX)0O<X)<X)CX30OOOO0OCX5CXX5CX3CIOCX)C CX>OO0OOO0O000CX)00CX3000CX)CXD00C 0O0OOOOO0O0OO0OCX)000OOCX)0O<X)C ooooooooooooooooooooooooooooc ooooooooooooooooooooooooooooc CX3CX300COCOCXX)CX3CX)CX3COOCX500CX3C CX5CX)(X>OOOOOOOOOOOCX3CXX5CX3CX5C»C CX>OOCX)CX3000CX)CX>CX3CX3CXX3CX3CX3C»C T" 10 —r15 20 25 30 M + R mult 1 50.00 0.95 Probabilidad de Pérdida TR Tiempo Medio de Espera TR rr 1- (0 •o •O) Q. 0) •o "D ;o co JD n •^ o o — o o o — o — o o o o o O O O O O o d W00000000CXX5000000CXX)000000< 1 1 1 1 1 1 1 0 5 10 15 20 25 30 M + R mult 1 50.00 0.95 OCXJCXDCXDCXD CX)OO<X)OO0O OOOOCX5CX30OCX3OCX>CX3C»CXX5CX>CX)C»C CX>CX)CX3CX3CX>CXX>CX3CX300CXX5CX)CX>OOC OOOO0OOOCXI0OOOOCX3OOCXX3CX3CX3CXIC CX3OOCX)C»C»0OOCX>OOCX>CXX5<X3CXDC»C 1 1 1 1 1 1 r o 5 10 15 20 25 30 M + R mult 1 50.00 0.95 Figura 7 Probabilidades de pérdida y tiempos medios de espera frente a la suma de los tamaños de los buffers M y R.
102 Dimensionamiento óptimo de un sistema de colas 5.1.3 Caso 3: XR ^X^, p = 0.95 Analizamos ahora algunos caso en que las tasas A^ y XM son comparables, siendo también ahora alta la intensidad de tráfico, del orden del 95%. Hemos considerado el caso XN = O-^XR (figura 8) y X^ = 2XR (figura 9). Puede apreciarse que en los dos casos el comportamiento del sistema es similar. La probabilidad de pérdida de los clientes TNR disminuye a medida que aumenta N. Asimismo, cualquiera que sea el valor de N, las tasas de pérdida más bajas para esta clase de clientes se alcanzan cuando el tamaño M + i? es pequeño, si bien a partir de un cierto valor de M + i? en adelante estas tasas se estabilizan. El tiempo medio de espera para los clientes TNR aumenta con N y con M + i?, y al igual que en el caso anterior, a partir de cierto valor de M + i? en adelante este tiempo se estabiliza. Por tanto, el mejor rendimiento ofrecido por el sistema para los clientes TNR se alcanza para valores de A^ grandes y valores de M + i? pequeños. En cuanto a los clientes TR, puede apreciarse también que los menores tiempos medios de espera corresponden a valores M + R pequeños, si bien a dichos valores corresponden también tasas de pérdida altas. Incrementar ligeramente el valor de M + R redunda en un rápido decrecimiento de la tasa de pérdidas de este tráfico a costa de cierta ralentización en sus tiempos de espera. Puede observarse que cuando se incrementa M + R, los tiempos de espera más cortos para el tráfico TR se obtienen para los valores de N más pequeños. Para evaluar el efecto por separado de M y i?, observemos las figuras 10, 11, 12; todos ellos obtenidos para N = 10, representando M en abcisas y utilizando un color distinto para cada valor de R: En lo que se refiere al tráfico TNR, vemos que tanto las probabilidades de pérdida como los tiempos medios de espera son crecientes tanto con M como con R; para cada M fijo las pérdidas y tiempos de espera crecen con R; para cada R fijo dichas variables crecen con M. Como puede observarse se alcanza una tendencia asintótica relativamente pronto; a partir de ciertos valores MQ y Ro (que dependen
Análisis de los resultados 103 Q. Probabilidad de Pérdida TNR -Q00000OOCX3OO' OOOCXDOOOOt O QQOOOOOOOOOOOOOOOOOOC O°OO°QOO2SOOOOOOOO§8OOOO§§§OC r 10 1 r 20 25 30 M + R mult 1 0.50 0.95 a: 2 H LU Tiempo IVIedio de Espera TNR |g8888S: ,oooooO( lOOOOCXJl 1°. «000000 ooooooc aooooooooooooi Qeooooooocx)cx>c oooooooooooc g00000ocx>oocx>ooc Oeooooooooo(x>oo< 1 0 1 5 1 1 10 15 M + R mult 1 0.50 1 20 0.95 1 25 1 30 Probabilidad de Pérdida TR Tiempo IVIedio de Espera TR O) 2 Q. 1 5 1 10 mult 1 15 M + R 1 0.50 1 20 0.95 1 25 30 LU (U ^l^^^ntaoOOOOOOOOC m lie 001 gegooooooooc OOCXJCXJC OOOOOOOCXDOOC oooooooooooooc 3000O<XXDOO0O0O( ySy@ooocx30oooocx}cx>ooc 1 1 1 1 1 1 r o 5 10 15 20 25 30 M + R mult 1 0.50 0.95 Figura 8 Ajv = O.^XR. Probabilidades de pérdida y tiempos medios de espera frente a la suma de los tamaños de los buffers M y R.
104 Dimensionamiento óptimo de un sistema de colas Probabilidad de Pérdida TNR Tiempo IMedio de Espera TNR cu z •0) O oooooooooooooooooooooooocoooí 300O00000OCX)OOC»CX30OOC»OOOOC QOOOOOOOOOOOCXDCXDOOOOOOOOOOOC o QOOOOOOOOOOOOCXDOOOCXJCXXXJCIOC 0°ROOOOOOOCXX)OOOOOOOOOOOOOOOC oroOQOoooooooooooooooooooooc cP uQixiOBBOOQQOOQOOOOFiOnOOOt —r10 —r15 20 I 25 r 30 M + R mult 1 2.00 0.95 Q: O _ LU o "O o o .r^ gQQgg0OCX30O0OOOOCX)CX30OC Q8gQQQQ0O0OOO0OOOOOOCX>CX)( l^oooo ^AOggoogoooooocxjcooooooooc ^QggggggggOOOOOOCXSOCIOCIOCXSOOC ^2§§§§§§§§CXDCX30O0OOOO0O0OOO< „8oooooooo °QnaaéaÉaegoooocx3oocxx}ooooooc DO0OO0OC«O0O000O( 1 0 1 5 1 1 1 10 15 20 M + R mult 1 2 00 0.95 1 25 30 Probabilidad de Pérdida TR Tiempo Medio de Espera TR í (U -a •n -c3 (U CM d ~ CO O _ 0 8 o o o °l — o _ Í^s@ SS0OOOOCIOCX3CX3OOOOOOOOOC 10 15 20 25 30 (- o o. E a> iO0CX3000OO0O0OCX3C OOOOCXDOOOOOOOOOÍ OOOOOOCXX30OOOOO< 10 15 20 25 "T 30 M + R mult 1 2.00 0.95 M + R mult 1 2.00 o 95 Figura 9 Ajv = 2Xji. Probabilidades de pérdida y tiempos medios de espera frente a la suma de los tamaños de los buffers M y R.
Análisis de los resultados 105 Probabilidad de Pérdida TNR Tiempo IVIedio de Espera TNR o: z Oí z E - - 10 I 15 I 20 25 —r 30 M mult 1 0.50 O 95 N = 10 M mult 1 0.50 O 95 N = 10 Probabilidad de Pérdida TR Tiempo Medio de Espera TR í Q. <u I M mult 1 0.50 0.95 N = 10 M mult 1 0.50 0.95 N = 10 Figura 10 Probabilidades de pérdida y tiempos medios de espera frente M.
112 Dimensionamiento óptimo de un sistema de colas 14. R. E. Barlow and F. Proschan, Mathematical Theory of Reliability. John Wiley Sons, 1965. 15. B. Bergman, "On reliability theory and its applications," Scandinavian Journal of Statistics, vol. 12, pp. 1-41, 1985. 16. M. S. Filkelstein, "Some notes on two types of mininial repair," Advances in Applied ProhaMlity, vol. 24, pp. 226-228, 1992. 17. M. Brown and F. Proschan, "Imperfect repair," Journal of Applied Probahility, vol. 20, pp. 851-859, 198.3. 18. H. W. Block, W. S. Borges, and T. H. Savits, "Age-dependent mininial repair," Journal of Applied Probability, vol. 22, pp. 370-385, 1985. 19. C. Dorado, M. Hollander, and Y. Sethuranian, "Nonparanietric estimation for a general repair model," Annals of Statistics, vol. 25, pp. 1140-1160, 1997. 20. L. Doyen and O. Gaudoin, ''Modelling and assessnient of niaintenance efhciency for repairable systems," in ESREL, 2002. 21. H. Phaní and H. Wang, "Imperfect maintenance," European joumal of Operations Research, vol. 94, pp. 425-428, 1996. 22. M. Berman and T. R. Turner, "Approximate x>oint process likelihoods with GLIM," Applied Staitstics, vol. 41, pp. 31-38, 1992. 23. .]. Lawle.ss and K. Thiagarajah, "A point process model incorporating renewals and time trends, with application to repairable systems," Technometrics, vol. 38, pp. 131138, 1996. 24. D. Cox, "The statistical analysis of dependencies in point processes," in Stochastic Point Prvcesses (P. Lewis, ed.), pp. 55-66, New York: Wiley, 1972. 25. B. H. Lindqvist, "The thend-renewal process, a useful model for repairable systems," in Society of Reliability Engineers, Scandinavian Chapter. Anual Conference, 1993. A'lalmo, Sweden. 26. M. Berman, "Inhomogeneous and modulated gamma processes," Biometrika, vol. 68, pp. 143-152, 1981.
Conclusión. 113 27. R. Barlow and L. Hunter, "Optimun preventive maintenance policies," Operations Research, vol. 8, pp. 90-100, 1960. 28. C. Tilquin and R. Cléroux, "Periodic replacement with minimal repair at failure and adjustnient costs," Naval Reserach Logistics Quarterly, vol. 22, pp. 243-254, 1975. 29. E. J. Mnth, "An optimal decisión rule for repair vs replacement," IEEE Transactioiis on Reliahility, vol. R-26, pp. 179-18L 1977. •30. H. Makabe and H. Morimura, "A new policy for preventive maintenance," Journal of the Operational Research Society of Japa?i, vol. 5, no. 2, pp. 17-47, 1963. 31. K. S. Park, "Optimal number of minimal repair before replacement," IEEE Transactions on Reliahility, vol. R-28, pp. 137-140, 1979. 32. R. Plielps, "Replacement policies under minimal repair," Joimial of the Operational Research Society, vol. 32, pp. 549-554, 1981. 33. R. I. Phelps, "Optimal policy for minimal repair," Journal ofthe Operational Research, Society, vol. 34, pp. 425-427, 1983. 34. W. Stadje and D. Zuckerman, "Optimal maintenance strategies for repairables systems with general repair," Journal of Applied Prohability, vol. 28, pp. 384-396, 1990. 35. .J. S. Dagpunar and N. .Jack, "Optimizing system availability under minimal repair with non-negiigible and replacement times," Journal of Operational Reseach Society, vol, 11, pp. 1097-1103, 1993. 36. P. .J. Boland and F. Proschan, "Periodic replacement with increasing minimal repair costs at failure," Operations Research, vol. 30, pp. 1183-1189, 1982. 37. V. Makis and A. .Jardine, "Optimal replacement policy for a general model with imperfect repair," Journal of the Operational Research Society, vol. 43, no. 2, pp. 111120, 1992. 38. V. A4akis, X. .Jiang, and K. Cheng, "Optimal preventive replacement under minimal repair and random repair cost," Mathematics of Operations Research, vol. 25, pp. 141156, febrero 2000.
114 Dimerisionamiento óptimo de un sistema de colas 39. S. Ross, "Average cost semi-markov decisión processes," Journal of Applied Probahility, vol. 7, pp. 649-656, 1970. 40. T. Aven, "Optimal replacement under a minimal repair strategy-a general set-up," Advances in Applied Probahility, vol. 15, pp. 198-211, 1983. 41. R. Chipalkatti, J. Kurose, and D. Towsley, "Scheduling policies for real-time and non-real-time traffic in a stastistical multiplexer," tech. rep.. Universidad de Massachusets, Enero 1989. 42. L. Kleinrock, Queueings Sytems. Vol. 1: Theory. Wiley, 1975. 43. L. Kleinrock, Queueings Systems. Vol. 2: Computer Application. Wiley, 1976. 44. K. I. A. T. Takine, H. Sunahara, and Y. Oie, "Delay analysis for CBR traffic under static-priority scheduling," IEEE/ACM transactions on networking, vol. 9, no. 2, pp. 177-185, 2001, 45. ,J. Shim, W. Lee, .]. Pyun, and S. Ko, "A new implementable sheduling algorithm supporting various traffics in ATM networksAWRR/DT," IEEE Transactions on Communications, vol. 38, no. 10, pp. 974-977, 1999. 46. D. Gan and S. McKenzie, "Performance of an ATM networking with multimedia traffic - a simulation study," in InteiiiaMonal Broadcasting Convention, no. Coference Publication No. 413, pp. 26.3-268, lEE, 14-18 septiembre 1995. 47. F. Isliizaki, T. Takine, and Y. Oie, "Delay analysis for real-time and non realtime traffic streams under a priority cell scheduling," IEEE Transactions on Communications, vol. 23, no. 5, pp. 3007-3012, 1998. 48. D. Clioi, B. Choi, and D. Sung, "Performance analysis of priority leaky bucket scheme with ciueue-length-threshold scheduling policy," lEE Proc.-Commun., vol. 145, no. 6, pp. 395-401, 1998. 49. W. Zhu and S. T. Chanson, '"Adaptive threshold-based sheduhng for real-time and non-real traffic," IEEE transactions on Computers, vol. C-36, no. 8, pp. 125-132, 1992. 50. M.Ñakamura and I. S. A. S. ]\4ori, "'Two parallel ciimes with dynamic routing under a
Conclusión. 115 threshold-type scheduling," IEEE Trans., vol. COM-34, no. 12, pp. 1145-1449, 1989. 51. S. FaizuUah and I. Marsic, "Pricing QoS : Simulation and analysis," IEEE/ACM transactios on Networking, vol. 1, no. 6, pp. 193-199, 2001. 52. H. C. Tijms, Stochastic Modelling and Analysis: A Computational Appwach. Wiley, 1986.