Sin ttulo de diapositiva

Teora De colasNotacin de Kendall1Rafael Gonzlez PintorInvestigacin de Operaciones2Notacin de los Modelos de ColasReconociendo la diversidad de los sistemas de colas, Kendall (1953) propuso un sistema de notacin para sistemas de servidores paralelos que ha sido adoptado universalmente.

NOTACION DE KENDALL

Por convencin los modelos que se trabajan en Teora de Colas se etiquetan:Notacin de KendallLa notacin de Kendall se utiliza para describir un sistema de colas, definiendo sus caractersticas.La notacin de Kendall tiene la siguiente forma:Investigacin de OperacionesRafael Gonzlez Pintor

A/B/c/K/m/ZUna versin resumida de esta convencin est basada en el formato A/B/c/m/K. Estas letras representan las siguientes caractersticas del sistema:A = Distribucin de tiempo entre arribos.B = Distribucin del tiempo de servicio.Los siguientes son smbolos comunes para A y B:M = exponencial o Markov (1)D = constante o determinstica4Notacin de KendallInvestigacin de OperacionesRafael Gonzlez Pintor

A/B/c/K/m/Z la distribucin de llegada se denota como:

Si la llegada es exponencial:

5Notacin de KendallInvestigacin de OperacionesRafael Gonzlez Pintor

A/B/c/K/m/ZValores tpicos para A: GI:Tiempo entre arribos general independiente. G:Tiempo entre arribos con distribucin general. Hk:Distribucin de tiempo entre arribos para k etapas de tipo hiperexponencial. Ek:Distribucin de tiempo entre arribos de tipo Erlang-K. M:Distribucin de tiempo entre arribos de tipo exponencial. D:Distribucin de tiempo entre arribos de tipo determinista.6Investigacin de OperacionesRafael Gonzlez Pintor

7Notacin de los Modelos de ColasEk = Erlang de orden kP H = Tipo faseH = HiperexponencialG = Arbitrario o generalGI = General independiente.c = nmero de servidores paralelosN = Capacidad del sistemaK = Tamao de la poblacin.Nota(1): A causa de las suposiciones de distribucin exponencial en los procesos de arribo, estos modelos son llamados MARKOVIANOS

Notacin de KendallInvestigacin de OperacionesRafael Gonzlez Pintor

A/B/c/K/m/ZDescribe la distribucin de tiempo de servicio La exponencial es generalmente utilizada para describir el tiempo de servicio, esto es, debido a su propiedad memoryless. Si se consideran n servidores con tiempo de servicio exponencial de parmetro y todos ellos estn ocupados, el tiempo hasta que el prximo cliente sea atendido ser una exponencial de parmetro n. 8Notacin de KendallInvestigacin de OperacionesRafael Gonzlez Pintor

A/B/c/K/m/ZValores tpicos para B: GI:Tiempo de servicio general independiente. G:Tiempo de servicio con distribucin general. Hk:Distribucin de tiempo de servicio para k etapas de tipo hiperexponencial. Ek:Distribucin de tiempo de servicio de tipo Erlang-K. M:Distribucin de tiempo de servicio de tipo exponencial. D:Distribucin de tiempo de servicio de tipo determinista.9Notacin de KendallInvestigacin de OperacionesRafael Gonzlez Pintor

A/B/c/K/m/ZIndica el nmero de servidores disponibles El sistema ms simple considera un slo servidor, es decir c=1, por lo tanto, el sistema atiende slo a un cliente a la vez. En cambio, para uno multiservidor, con c=s, se pueden atender s clientes simultneamente. En un sistema con infinitos servidores, cada cliente que arriba al sistema es atendido inmediatamente. 10Notacin de KendallInvestigacin de OperacionesRafael Gonzlez Pintor

A/B/c/K/m/ZIndica la capacidad del sistema, que es el nmero mximo de clientes permitidos en el sistema. Si la capacidad del sistema es infinita, cada cliente nuevo que llega espera hasta ser atendido. Si la capacidad es igual al nmero se servidores, es decir k=c, cada cliente nuevo es rechazado cuando las facilidades de servicio estn siendo utilizadas. 11Notacin de KendallInvestigacin de OperacionesRafael Gonzlez Pintor

A/B/c/K/m/Z Para K:Si se considera que la capacidad de la cola es infinita, el valor de k se omite. 12Notacin de KendallInvestigacin de OperacionesRafael Gonzlez Pintor

A/B/c/K/m/ZIndica el nmero de fuentes presentes en el sistema.13Notacin de KendallInvestigacin de OperacionesRafael Gonzlez Pintor

A/B/c/K/m/ZPara m: Si se considera que el nmero de fuentes es infinito, el valor de m se omite. 14Notacin de KendallInvestigacin de OperacionesRafael Gonzlez Pintor

A/B/c/K/m/ZIndica la disciplina de la cola. Es la regla con que se seleccionar al prximo cliente que recibir servicio, como son: FIFO LIFO RSS o SIRO(seleccin aleatoria de clientes). En este sistema, cada usuario tiene la misma probabilidad de ser seleccionado. PRI ( servicio por prioridad). 15Notacin de KendallInvestigacin de OperacionesRafael Gonzlez Pintor

A/B/c/K/m/ZPara Z: Si se asume que la disciplina de atencin para la cola es FIFO, el valor de Z se omite. 16Notacin de KendallInvestigacin de OperacionesRafael Gonzlez Pintor

A/B/c/K/m/Z M: Distribucin de tiempo entre arribos es exponencial. E4: Distribucin de tiempo de servicio idntico Erlang-4. 3 : Nmero de servidores. 20 : Capacidad del sistema. : Fuentes infinitas, esto implica una tasa de arribo constante. SIRO: Disciplina de la cola, servicio en orden aleatorio. Ejemplo:M/E4/3/20//SIRO

3 en servicio y 17 en colaSi el sistema esta completo, estn siendo atendidos 3 clientes y esperan por servicio los otros 17.

17Ejemplo de clasificacin de colasClasificacin de las colas.

- Los sistemas de colas pueden ser clasificados por:+ Proceso de llegada de clientes+ Proceso de atencin+ Nmero de servidores+ Tamao (lineas de espera finitas/infinitas)+ Tamao de la poblacin

- Notacin+ M (Markovian)= Proceso de llegada Poisson o tiempo de atencin exponencial.+D (Determinstico) = Tasa constante de llegada o de atencin+G (General) = Probabilidad general de llegada o de atencin Ejempo:

M / M / 6 / 10 / 20

Notacin de los Modelos de ColasPor ejemplo: M/M/1// significa un solo servidor, capacidad de cola ilimitada y poblacin infinita de arribos potenciales. Los tiempos entre arribos y los tiempos de servicio son distribudos exponencialmente. Cuando N y K son infinitos, pueden ser descartados de la notacin. M/M/1// es reducido a M/M/1.