analisis de colas
TRANSCRIPT
Modelación y Simulación
Unidad 2: Teoría de Colas o Líneas de espera
Introducción
Ing. Margarita Aucancela [email protected]
Modelación y Simulación Ing. Margarita Aucancela Msc. 2
Escuela de Ingeniería en Sistemas y Computación
Objetivo: Conocer los diferentestipos de problemas de colasexistentes y su formulaciónmatemática.
Modelación y Simulación Ing. Margarita Aucancela Msc. 2
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 3
Escuela de Ingeniería en Sistemas y Computación
Índice: Introducción Elementos del modelo de colas Análisis de problemas de colascon población infinita canalsimple. Análisis de problemas de colascon población infinita canalmúltiple.
Modelación y Simulación Ing. Margarita Aucancela Msc. 3
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 4
Escuela de Ingeniería en Sistemas y Computación
Introducción
Modelación y Simulación Ing. Margarita Aucancela Msc. 4
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 5
Escuela de Ingeniería en Sistemas y Computación
Introducción
En las líneas de espera, existen dos costos perfectamenteidentificados: el costo de las transacciones, que representa lacuantificación monetaria de la pérdida de tiempo al esperarrecibir un servicio o la pérdida de clientes por abandono delsistema, y el costo de proporcionar el servicio, que representala cantidad de dinero que hay que pagar por cuestión desueldos y salarios, energía, mantenimiento y depreciación delpersonal o equipo.
De tal forma que en un estudio de líneas de espera el objetivoes determinar qué nivel de servicio, ya sea por cantidad deentidades o por la velocidad de ellas, proporcionar paraminimizar el costo total del sistema.
Modelación y Simulación Ing. Margarita Aucancela Msc. 5
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 6
Escuela de Ingeniería en Sistemas y Computación
Definición de términos
Modelación y Simulación Ing. Margarita Aucancela Msc. 6
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 7
Escuela de Ingeniería en Sistemas y Computación
Definición de TérminosLos modelos de tiempo discreto cuenta con los siguientes componentes:
1. Entidades,
2. Atributos,
3. Variables,
4. Recursos,
5. Colas,
6. Contadores estadísticos y
7. Eventos
Modelación y Simulación Ing. Margarita Aucancela Msc. 7
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 8
Escuela de Ingeniería en Sistemas y Computación
EntidadesSon objetos o individuos cuyas actividades modelamos.
Características:
Son dinámicos es decir: son creados y se mueven por el
sistema, cambiando el valor de sus atributos, afectados
por otras entidades y por el estado del sistema.
Puede o no abandonar el sistema
Ejemplos:
productos, clientes, documentos, transacciones pacientes.
Modelación y Simulación Ing. Margarita Aucancela Msc. 8
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 9
Escuela de Ingeniería en Sistemas y Computación
AtributosSon las propiedades o características de las entidades.
Características: Permiten describir cuantitativamente al sistema.
Los atributos son imprescindibles para controlar el flujo
de entidades en el sistema
Ejemplos:
tamaño, precio, prioridad, etc.
Modelación y Simulación Ing. Margarita Aucancela Msc. 9
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 10
Escuela de Ingeniería en Sistemas y Computación
VariablesEstán asociadas al concepto matemático de variable.
Características: Pertenecen al conjunto del sistema. Son accesibles desde todas las entidades y pueden ser
modificadas por todas las entidades. Puede considerarse que cada variable es como una
pizarra colgada en la pared, en la que se escribe el valorde la variable.
EjemplosEl número de clientes(entidades) que hay en cada instanteen cada cola, el número de empleados (recursos)ocupados, el estado de cada recurso (ocupado o libre), etc.
Modelación y Simulación Ing. Margarita Aucancela Msc. 10
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 11
Escuela de Ingeniería en Sistemas y Computación
Variables
Pueden clasificarse en:
Exógenas, de entrada o independientes: son las queafectan al sistema, pero éste no puede modificarlas.Pueden modificarse arbitrariamente desde el medioambiente.
Endógenas o Dependientes: Son variables del sistemaque se modifican de acuerdo a relaciones, no puedenser modificadas arbitrariamente.
Modelación y Simulación Ing. Margarita Aucancela Msc. 11
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 12
Escuela de Ingeniería en Sistemas y Computación
Variables
Pueden clasificarse en:
De estado: Es el conjunto mínimo de variablesdependientes que permiten describir el sistema en t+Δt, si se conocen sus valores más los valores de lasindependientes en t.
De salida: Es el conjunto mínimo de variables de estadoque permiten evaluar los objetivos del modelo.
Modelación y Simulación Ing. Margarita Aucancela Msc. 12
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 13
Escuela de Ingeniería en Sistemas y Computación
Variables
Ejemplo:Se desea analizar el inventario de piezas de tipo A. Para ello se realiza la modelización de la evolución de la cantidad de piezas A en el depósito.
Modelación y Simulación Ing. Margarita Aucancela Msc. 13
Escuela de Ingeniería en Sistemas y Computación
Componentes Variables Exógenas Variables Endógenas
Variables de Salida
Piezas A Velocidad de arribo de piezas al depósito
Cantidad de piezas a procesas
Cantidad de piezas en el depósito
Modelación y Simulación Ing. Margarita Aucancela Msc. 14
Escuela de Ingeniería en Sistemas y Computación
Recursos(Servidores)
El recurso puede ser individual o estar compuesto por ungrupo de elementos individuales, cada uno de los cuales sellama una unidad del recurso .
Características Son los medios gracias a los cuales se pueden ejecutar
las actividades Definen quién o qué ejecuta la actividad, su número
permanece constante a lo largo de la simulación ysuelen parametrizarse por características tales comocapacidad, velocidad o tiempo de ciclo.
Modelación y Simulación Ing. Margarita Aucancela Msc. 14
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 15
Escuela de Ingeniería en Sistemas y Computación
Recursos(Servidores)
Ejemplos:
Personal (en nuestro caso, el empleado): operarios
Máquinas (por ejemplo, si las entidades son piezas que
deben ser procesadas): ordenadores
Espacio (por ejemplo, en un almacén).
Modelación y Simulación Ing. Margarita Aucancela Msc. 15
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 16
Escuela de Ingeniería en Sistemas y Computación
Contadores estadísticosA fin de calcular el valor de las variables de salida, espreciso calcular durante el curso de la simulación el valorde determinadas variables intermedias. Estas se llamanacumuladores estadísticos .
Características Los contadores son inicializados a cero al comenzar la
simulación. Cuando “algo sucede” en la simulación (es decir, se
ejecuta un evento), los contadores estadísticos afectados deben ser convenientemente actualizados.
Modelación y Simulación Ing. Margarita Aucancela Msc. 16
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 17
Escuela de Ingeniería en Sistemas y Computación
Contadores estadísticos
Variables utilizadas para almacenar información sobre elcomportamiento del sistema y que al final, mediante algúncálculo matemático, darán respuesta al objetivo delestudio.
Ejemplos: el número total de clientes atendidos hasta ese
momento, la suma de los tiempos de espera en cola de los clientes
hasta ese momento, el número total de clientes que han comenzado a ser
atendidos hasta ese momento, el mayor tiempo de espera en cola hasta ese momento,
etc.Modelación y Simulación Ing. Margarita Aucancela Msc. 17
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 18
Escuela de Ingeniería en Sistemas y Computación
Contadores estadísticos
Variables utilizadas para almacenar información sobre elcomportamiento del sistema y que al final, mediante algúncálculo matemático, darán respuesta al objetivo delestudio.
Ejemplos: el número total de clientes atendidos hasta ese
momento, la suma de los tiempos de espera en cola de los clientes
hasta ese momento, el número total de clientes que han comenzado a ser
atendidos hasta ese momento, el mayor tiempo de espera en cola hasta ese momento,
etc.Modelación y Simulación Ing. Margarita Aucancela Msc. 18
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 19
Escuela de Ingeniería en Sistemas y Computación
EventosSon las propiedades o características de las entidades.
Características:
Permiten describir cuantitativamente al sistema.
Los atributos son imprescindibles para controlar el flujo
de entidades en el sistema
Ejemplos: tamaño, precio, prioridad, etc.
Modelación y Simulación Ing. Margarita Aucancela Msc. 19
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 20
Escuela de Ingeniería en Sistemas y Computación
Eventos
Un evento es un suceso que ocurre en un determinadoinstante de tiempo (simulado) y que puede cambiar el valor delos atributos, las variables y los acumuladores estadísticos.Los valores de los atributos, las variables y los acumuladoresestadísticos se mantienen constantes durante el intervalo detiempo entre eventos sucesivos.
Modelación y Simulación Ing. Margarita Aucancela Msc. 20
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 21
Escuela de Ingeniería en Sistemas y Computación
Eventos
Cada evento tiene asociado dos tipos de información: Su condición de activación, es decir, la condición que
hace que el evento pase de estar desactivado a estaractivado.
Las acciones que deben realizarse en el instante en que el evento es activado.
En función del tipo de su condición de activación, los eventos pueden clasificarse en:
eventos en el tiempo y eventos en el estado
Modelación y Simulación Ing. Margarita Aucancela Msc. 21
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 22
Escuela de Ingeniería en Sistemas y Computación
Colas
Cuando una entidad no puede circular, debido a quenecesita usar una unidad de un recurso, que en esemomento no se encuentra disponible, entonces la entidadnecesita un sitio donde esperar: este es el propósito de lacola. Se caracteriza por el número máximo de clientes quepuede admitir. Las colas pueden ser finitas o infinitas.
Modelación y Simulación Ing. Margarita Aucancela Msc. 22
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 23
Escuela de Ingeniería en Sistemas y Computación
Problemas que ocasionan las líneas deespera(colas)
Modelación y Simulación Ing. Margarita Aucancela Msc. 23
Escuela de Ingeniería en Sistemas y Computación
Pérdida de proveedores
Pérdida de prestigio
Pérdida de dinero
Pérdida de clientes
Modelación y Simulación Ing. Margarita Aucancela Msc. 24
Escuela de Ingeniería en Sistemas y Computación
Proceso básico de colas
Los clientes que requieren un servicio se generan en unafase de entrada. Estos clientes entran al sistema y se unen auna cola. En determinado momento se selecciona unmiembro de la cola, para proporcionarle el servicio,mediante alguna regla conocida como disciplina de servicio.Luego, se lleva a cabo el servicio requerido por el cliente enun mecanismo de servicio, después de lo cual el cliente saledel sistema de colas.
Modelación y Simulación Ing. Margarita Aucancela Msc. 24
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 25
Escuela de Ingeniería en Sistemas y Computación
Proceso básico de colas
Modelación y Simulación Ing. Margarita Aucancela Msc. 25
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 26
Escuela de Ingeniería en Sistemas y Computación
Proceso básico de colas
Modelación y Simulación Ing. Margarita Aucancela Msc. 26
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 27
Escuela de Ingeniería en Sistemas y Computación
Mecanismos de servicio
Modelación y Simulación Ing. Margarita Aucancela Msc. 27
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 28
Escuela de Ingeniería en Sistemas y Computación
Proceso básico de colas
Capacidad de la cola: Es el máximo número de clientesque pueden estar haciendo cola (antes de comenzar a serservidos). De nuevo, puede suponerse finita o infinita.
Mecanismo de servicio: El mecanismo de servicio consisteen una o más instalaciones de servicio, cada una de ellascon uno o más canales paralelos de servicio, llamadosservidores.
Redes de colas: Sistema donde existen varias colas y lostrabajos fluyen de una a otra. Por ejemplo: las redes decomunicaciones o los sistemas operativos multitarea.
El proceso de servicio: Define cómo son atendidos loscliente
Modelación y Simulación Ing. Margarita Aucancela Msc. 28
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 29
Escuela de Ingeniería en Sistemas y Computación
Disciplina de la colas
Se refiere al orden en el que se seleccionan sus miembros para recibir el servicio. Por ejemplo, puede ser: FIFO (first in first out) primero en entrar, primero en
salir, LIFO (last in first out) atendiende primero al cliente que
ha llegado el último. RSS (random selection of service) selecciona los clientes
de manera aleatoria, de acuerdo a algún procedimientode prioridad u orden.
Tiempo de servicio mayor Tiempo de espera mayor Processor Sharing – sirve a los clientes igualmente.
Modelación y Simulación Ing. Margarita Aucancela Msc. 29
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 30
Escuela de Ingeniería en Sistemas y Computación
Proceso de llegadas/ Patrón de arribo
Modelación y Simulación Ing. Margarita Aucancela Msc. 30
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 31
Escuela de Ingeniería en Sistemas y Computación
Proceso de llegadas/ Patrón de arribo
Modelación y Simulación Ing. Margarita Aucancela Msc. 31
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 32
Escuela de Ingeniería en Sistemas y Computación
Patrón de arribo
Aspectos que influyen en el patrón de arribo son:
• Configuración de la fila: 1 o mas canales de servicio• Tramposos: clientes que se mueven a través de la cola sin seguir los
criterios de avance• Contrariedades: ocurre cuando los clientes evitan llegar a la fila
porque perciben que esta es demasiada larga• Reglas de prioridad: definidas por las disciplina de la cola• Homogeneidad: Una población homogénea de clientes es aquella
en la cual los clientes requieren esencialmente el mismo servicio. Una población no homogénea es aquella en la cual los clientes pueden ser ordenados de acuerdo:
• A los patrones de llegada • Al tipo de servicio requerido
Modelación y Simulación Ing. Margarita Aucancela Msc. 32
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 33
Escuela de Ingeniería en Sistemas y Computación
Patrones de servicio
Los servidores pueden tener un tiempo de servicio
variable, en cuyo caso hay que asociarle, para
definirlo, una función de probabilidad. También
pueden atender en lotes o de modo individual.
El tiempo de servicio también puede variar con el
número de clientes en la cola, trabajando más rápido
o más lento, y en este caso se llama patrones de
servicio dependientes.
Modelación y Simulación Ing. Margarita Aucancela Msc. 33
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 34
Escuela de Ingeniería en Sistemas y Computación
Patrón de servicio
Algunos sistemas de servicio requieren de un tiempo de
atención fijo. Sin embargo, el tiempo de atención en
muchos casos varía de acuerdo a la cantidad de clientes.
Cuando el tiempo de atención varía, se trata como una
variable aleatoria.
La distribución exponencial es usada, en algunos casos para
modelar el tiempo de atención del cliente.
Modelación y Simulación Ing. Margarita Aucancela Msc. 34
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 35
Escuela de Ingeniería en Sistemas y Computación
Patrón de servicio
Distribución Exponencial
Modelación y Simulación Ing. Margarita Aucancela Msc. 35
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 36
Escuela de Ingeniería en Sistemas y Computación
TERMINOLOGIA Y NOTACION
n Cantidad de clientes: Que están en el sistema
en un momento dado
L Valor esperado de clientes en el sistema
L E (n)=
W Valor esperado de tiempo de atención
cliente en el sistemaW E (w)=
de un
w: tiempo específico que tarda un cliente particular
dentro del sistema. Es una variable aleatoria
Modelación y Simulación Ing. Margarita Aucancela Msc. 37
Escuela de Ingeniería en Sistemas y Computación
P0 : Probabilidad de que el sistema esté vacío
P1 : Probabilidad de que el sistema tenga 1 cliente
P2 : Probabilidad de que el sistema tenga 2 clientes
Pn : Probabilidad de que el sistema tenga n clientes
Probabilidad de que hayan “n” clientes en el
sistema en un instante determinadoPn
Asimismo es posible definir:
Lq
Wq
Valor esperado de clientes en la cola
Valor esperado del tiempo en la cola
TERMINOLOGIA Y NOTACION
Modelación y Simulación Ing. Margarita Aucancela Msc. 38
Escuela de Ingeniería en Sistemas y Computación
Probabilidad de que hayan “n” clientes en el
sistema en un instante determinadoPn
Esto tiene dos interpretaciones:
(1)
(2)
Probabilidad de que en un instante cualquiera se
observe el sistema y esté presente un estado n.
Por ejemplo, P3 = 0,1 indica que la probabilidad
de encontrar 3 clientes en el sistema es 0,1 o del
10%
Pn es la fracción del tiempo en que el
sistema permanece en el estado n
TERMINOLOGIA Y NOTACION
Modelación y Simulación Ing. Margarita Aucancela Msc. 39
Escuela de Ingeniería en Sistemas y Computación
Valor esperado de clientes en el sistemaL
L n PnL E (n)= = n=0
8
En consecuencia:
TERMINOLOGIA Y NOTACION
Modelación y Simulación Ing. Margarita Aucancela Msc. 40
Escuela de Ingeniería en Sistemas y Computación
LLEGADA DE CLIENTES AL SISTEMASe define:
Tasa media de llegada de clientes al sistema
Indica el número promedio de clientes que
ingresa al sistema en un instante específico de
tiempo
1 Tiempo promedio entre llegadas
es el tiempo promedio que transcurre entre dos
llegadas sucesivas, entre el arribo de dos
clientes consecutivos
Modelación y Simulación Ing. Margarita Aucancela Msc. 41
Escuela de Ingeniería en Sistemas y Computación
SALIDA DE CLIENTES DEL SISTEMASe define:
Tasa media de prestación del servicio en el
sistema Indica el número promedio de clientes
que reciben el servicio en el sistema en un
instante específico de tiempo. Es la tasa media
del servicio, implica el concepto de velocidad de
atención del sistema
1 Tiempo promedio entre prestaciones del
servicio es el tiempo promedio que se demora
en atender a un cliente en el sistema
Modelación y Simulación Ing. Margarita Aucancela Msc. 42
Escuela de Ingeniería en Sistemas y Computación
Población ColaMecanismo
de Servicio
Clientes
servidosClientes
Sistema de Colas
ESTRUCTURA BASICA DE UN MODELO DE COLAS
Lq,Wq
L , W(clientes / tiempo)
1
(tiempo / clientes)
Poisson Exp
Modelación y Simulación Ing. Margarita Aucancela Msc. 43
Escuela de Ingeniería en Sistemas y Computación
UNIDADES DIMENSIONALES
• W (tiempo)
• L (clientes)
• (clientes / tiempo)
• (clientes / tiempo)
• (tiempo / clientes)
• (tiempo / clientes)
1
1
Modelación y Simulación Ing. Margarita Aucancela Msc. 44
Escuela de Ingeniería en Sistemas y Computación
Análisis de colas
Notación de los modelos de colasReconociendo la diversidad de los sistemas de colas, Kendall (1953)propuso un sistema de notación para sistemas de servidores paralelosque ha sido adoptado universalmente.
Una versión resumida de esta convención está basada en el formatoA/B/X/Y/Z. Estas letras representan las siguientes características delsistema:
A = Distribución de tiempo entre llegadas o arribos.B = Distribución del tiempo de servicio.Los siguientes son símbolos comunes para A y B:
M = exponencial o MarkovD = constante o determinística
Modelación y Simulación Ing. Margarita Aucancela Msc. 44
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 45
Escuela de Ingeniería en Sistemas y Computación
Análisis de colas
Notación de los modelos de colas
Ek = Erlang de orden k
PH = Tipo fase
H = Hiperexponencial
G = Arbitrario o general
GI = General independiente
X: es el número de canales de servicio
Y: es la restricción en la capacidad del sistema
Z: es la disciplina de cola
Modelación y Simulación Ing. Margarita Aucancela Msc. 45
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 46
Escuela de Ingeniería en Sistemas y Computación
NOMENCLATURAUn modelo de colas se caracteriza
por los siguientes símbolos:
Tiempo entre
llegadas, que se
asocia a una
distribución
exponencial (la
tasa de llegada
es poisson)
Tiempo de servicio,
que es exponencial
Cantidad de
servidores en
paralelo
Cantidad en la
población potencial
(población finita)
Cantidad admisible
en el sistema
(capacidad finita)
M / M / S / K / N
Modelación y Simulación Ing. Margarita Aucancela Msc. 47
Escuela de Ingeniería en Sistemas y Computación
MODELOS DE COLAS
Según se combinen las diferentes características
(población finita o infinita, uno o más servidores,
capacidad admisible finita o infinita), se da origen a
una combinación de distintos modelos de colas:
• Modelo M / M / 1
• Modelo M / M / S
• Modelo M / M / 1 / K
• Modelo M / M / S / K
• Modelo M / M / 1 / N
• Modelo M / M / S / N
Modelación y Simulación Ing. Margarita Aucancela Msc. 48
Escuela de Ingeniería en Sistemas y Computación
MODELOS DE COLAS
Por ejemplo:
M/M/1// significa un solo servidor, capacidad de cola
ilimitada y población infinita de arribos potenciales. Los
tiempos entre arribos y los tiempos de servicio son
distribuidos exponencialmente.
Cuando Y y Z son infinitos, pueden ser descartados de la
notación. M/M/1// es reducido a M/M/1.
Modelación y Simulación Ing. Margarita Aucancela Msc. 48
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 49
Escuela de Ingeniería en Sistemas y Computación
MODELOS DE COLAS
Existe una cantidad enorme de modelos de colas que puedenutilizarse. Nos vamos a concentrar en 4 de los modelos más usados.Los 4 modelos de colas a estudiar asumen:
Arribos según la Distribución de Poisson Disciplina FIFO Una sola fase de servicio.
Modelo A: Un canal, llegadas según la Distribución de
Poisson; Tiempos de Servicio exponenciales
Modelo B: Multicanal
Modelo C: Tiempo de Servicio constante
Modelo D: Población Limitada
Modelación y Simulación Ing. Margarita Aucancela Msc. 49
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 50
Escuela de Ingeniería en Sistemas y Computación
Análisis de colas
Modelación y Simulación Ing. Margarita Aucancela Msc. 50
Escuela de Ingeniería en Sistemas y Computación
MODELO NOMBRE N° DE CANAL
ES
N° DE FASES
PATRÓN DE
ARRIBO
PATRÓN DE
SERVICIO
TAMAÑO DE LA POBLACIÓN
DISCIPLINA DE COLA
A SIMPLE
M/M/1
UNO UNA POISSON EXPONENCIAL
INFINITA FIFO
B MULTI-
CANAL
M/M/S
MULTI
CANAL
UNA POISSON EXPONENCIAL
INFINITA FIFO
C SERVICIO
CONSTANTE (M/D/1)
UNO UNA POISSON CONSTANTE
INFINITA FIFO
D POBLACION
LIMITADA
UNO UNA POISSON EXPONENCIAL
FINITA FIFO
Modelación y Simulación Ing. Margarita Aucancela Msc. 51
Escuela de Ingeniería en Sistemas y Computación
Análisis de colas
Modelo A: M/M/1
• Proceso de llegada de Poisson
• El tiempo de atención se distribuye exponencialmente
• Existe un solo servidor
• Cola de capacidad infinita
• Población infinita
Modelación y Simulación Ing. Margarita Aucancela Msc. 51
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 52
Escuela de Ingeniería en Sistemas y Computación
Análisis de colas
Modelo A: M/M/1
Asumimos que existen las siguientes condiciones:
1. Los clientes son servidos con una política FIFO y cada arribo espera a
ser servido sin importar la longitud de la línea o cola.
2. Los arribos son independientes de arribos anteriores, pero el
promedio de arribos, no cambia con el tiempo.
3. Los arribos son descritos mediante la distribución de probabilidad de
Poisson y proceden de una población muy grande o infinita.
4. Los tiempos de servicio varían de cliente a cliente y son
independientes entre sí, pero su rata promedio es conocida.
Modelación y Simulación Ing. Margarita Aucancela Msc. 52
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 53
Escuela de Ingeniería en Sistemas y Computación
Análisis de colas
Modelo A: M/M/1
Modelación y Simulación Ing. Margarita Aucancela Msc. 53
Escuela de Ingeniería en Sistemas y Computación
1
servicio) de tiempo espera de (tiempo
sistema elen permanece unidad una que promedio Tiempo
sistema deln utilizació deFactor
sistema elen (clientes) unidades de promedio Número
sistema elen unidades de número
tiempode períodopor servidos cosas o gente de promedio Número
tiempode períodopor arribos de promedio Número
S
S
SS
W
W
LL
n
Modelación y Simulación Ing. Margarita Aucancela Msc. 54
Escuela de Ingeniería en Sistemas y Computación
Análisis de colas
Modelo A: M/M/1
Modelación y Simulación Ing. Margarita Aucancela Msc. 54
Escuela de Ingeniería en Sistemas y Computación
1
2
sistema elen estén unidades k"" de más que de adProbabilid
11
vacía)está servicio de unidad (la sistema elen unidades cero de adProbabilid
11
sistema elen estén clientes "n" que de adProbabilid
cola laen espera unidad una que promedio Tiempo
cola laen unidades de promedio Número
k
kn
kn
o
o
n
n
n
n
Sq
Sq
P
P
P
P
P
P
WW
LL
Modelación y Simulación Ing. Margarita Aucancela Msc. 55
Escuela de Ingeniería en Sistemas y Computación
Ejercicios (M/M/1)
Determinar las medidas de desempeño para este servicio:
Modelación y Simulación Ing. Margarita Aucancela Msc. 55
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 56
Escuela de Ingeniería en Sistemas y Computación
Ejercicios (M/M/1)
Modelación y Simulación Ing. Margarita Aucancela Msc. 56
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 57
Escuela de Ingeniería en Sistemas y Computación
Ejercicios (M/M/1)
Determinar las medidas de desempeño para este servicio:
Suponga que en una estación con un solo servidor llegan enpromedio 45 clientes por hora, Se tiene capacidad paraatender en promedio a 60 clientes por hora. Se sabe que losclientes esperan en promedio 3 minutos en la cola.Se solicita: a) Tiempo promedio que un cliente pasa en elsistema. b) Número promedio de clientes en la cola. c) Númeropromedio de clientes en el Sistema en un momento dado.
Modelación y Simulación Ing. Margarita Aucancela Msc. 57
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 58
Escuela de Ingeniería en Sistemas y Computación
Ejercicios (M/M/1)
λ= 45 clientes/hora (media de llegada de los clientes)= 45/60clientes/minutosμ= 60 clientes/hora (media de servicio a los clientes) = 60/60clientes/minutos=Wq = 3 minutos (tiempo promedio de espera de un cliente en lacola)a) Para calcular el tiempo promedio que un cliente pasa en elSistema (Ws). Lo podemos calcular a partir de Wq y μ.
𝑾𝒔=𝑾𝒒+ 𝟏𝝁= 3 minutos + 𝟏𝟏=𝟑+𝟏=𝟒𝒎𝒊𝒏𝒖𝒕𝒐𝒔Es decir en promedio un cliente pasa 4 minutos en el Sistema: distribuidos así 3 minutos pasa esperando en la cola + 1 minutos en servicio.
Modelación y Simulación Ing. Margarita Aucancela Msc. 58
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 59
Escuela de Ingeniería en Sistemas y Computación
Ejercicios (M/M/1)
b) Para calcular el número de clientes en la cola (Lq), usaremos la fórmula siguiente:
Lq= λ Wq. 𝐿𝑞=𝜆∗𝑊𝑞=0.75𝑐𝑙𝑖𝑒𝑛𝑡𝑒𝑠𝑚𝑖𝑛𝑢𝑡𝑜𝑠* 3 minutos = 2.25 clientes.
Es decir los cálculos nos muestran que en la cola puede haber más de dos clientes en la cola. c) Para calcular cual es el número de clientes en la cola (Ls). Lo podemos hacer con la fórmula: Ls= λ Ws. 𝐿𝑆= 𝜆∗𝑊𝑆=0.75𝑐𝑙𝑖𝑒𝑛𝑡𝑒𝑚𝑖𝑛𝑢𝑡𝑜𝑠∗4 𝑚𝑖𝑛𝑢𝑡𝑜𝑠=3 𝑐𝑙𝑖𝑒𝑛𝑡𝑒𝑠Es decir en promedio hay tres clientes en el sistema, como se nos ha dicho que solo hay un servidor, sabemos que solo un cliente puede estar en servicio, por lo que los demás deben estar en la cola. Esto indica que hay dos clientes en espera. Modelación y Simulación Ing. Margarita Aucancela Msc. 59
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 60
Escuela de Ingeniería en Sistemas y Computación
Análisis de colas
Modelo B: M/M/S
• Clientes llegan de acuerdo a una distribución de Poissoncon una esperanza λ
• El tiempo de atención se distribuye exponencialmente• Existen k servidores, cada uno atiende a una tasa de μ
clientes• Existe una población infinita y la posibilidad de infinitas
filas.
Modelación y Simulación Ing. Margarita Aucancela Msc. 60
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 61
Escuela de Ingeniería en Sistemas y Computación
Análisis de colas
Modelo B: M/M/S
Asumimos que existen las siguientes condiciones:1. Dos o más servidores o canales están disponibles para atender a
los clientes que arriban.
2. Los clientes forman una sola cola y se los atiende de acuerdo alservidor que queda libre.
3. Asumimos que los arribos siguen la distribución de probabilidadde Poisson y los tiempos de servicio son distribuídosexponencialmente.
4. Los servicios se los hace de acuerdo a la política FIFO
Modelación y Simulación Ing. Margarita Aucancela Msc. 61
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 62
Escuela de Ingeniería en Sistemas y Computación
Análisis de colas
Modelo B: M/M/S
Modelación y Simulación Ing. Margarita Aucancela Msc. 62
Escuela de Ingeniería en Sistemas y Computación
PoMM
L
L
M
M
M
Mn
P
P
M
M
S
s
MMn
n
no
o
2
1
0
.!.1
:sistema elen unidades o personas de promedio número
para
!
1
!
1
1
sistema elen unidades o personas CEROexistan que de adProbabilid
canal cadaen servicio de promedio tasa
arribo de promedio tasa
abiertos canales de número
Modelación y Simulación Ing. Margarita Aucancela Msc. 63
Escuela de Ingeniería en Sistemas y Computación
Análisis de colasModelo B: M/M/S
Modelación y Simulación Ing. Margarita Aucancela Msc. 63
Escuela de Ingeniería en Sistemas y Computación
q
Sq
q
SSq
q
S
M
S
s
LWW
W
LLL
L
LPo
MMW
W
1
serviciopor esperando cola laen da tar
se unidad o persona una que promedio Tiempo
servicio de esperaen cola, o línea laen unidades o personas de promedio Número
1
! 1
)(atendida) servida siendoy cola la(en
sistema, elen permanece unidad una que promedio Tiempo
2
Modelación y Simulación Ing. Margarita Aucancela Msc. 64
Escuela de Ingeniería en Sistemas y Computación
Ejercicios (M/M/k)
Modelación y Simulación Ing. Margarita Aucancela Msc. 64
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 65
Escuela de Ingeniería en Sistemas y Computación
Ejercicios (M/M/k)
Modelación y Simulación Ing. Margarita Aucancela Msc. 65
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 66
Escuela de Ingeniería en Sistemas y Computación
Análisis de colas
Modelo C: M/D/1
• Los clientes llegan de acuerdo a un proceso de Poisson con
esperanza λ
• El tiempo de atención tiene una distribución general con esperanza
μ
• Existe un solo servidor
• Se cuenta con una población infinita y la posibilidad de infinitas filas
Modelación y Simulación Ing. Margarita Aucancela Msc. 66
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 67
Escuela de Ingeniería en Sistemas y Computación
Análisis de colas
Modelo C: M/D/1
Modelo de Tiempo de Servicio Constante
Algunos sistemas tienen tiempos de servicio constantes en lugar de
exponencialmente distribuídos. Cuando los clientes son atendidos o
equipos son procesados con un ciclo fijo como es el caso de una
lavadora de carros automatizada o ciertos entretenimientos en los
parques de diversiones, el asumir servicio constante es adecuado.
Modelación y Simulación Ing. Margarita Aucancela Msc. 67
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 68
Escuela de Ingeniería en Sistemas y Computación
Análisis de colas
Modelo C: M/D/1
Modelación y Simulación Ing. Margarita Aucancela Msc. 68
Escuela de Ingeniería en Sistemas y Computación
1 sistema, elen espera de promedio Tiempo
sistema, elen clientes de promedio Número
2 cola, laen espera de promedio Tiempo
2 cola, la de promedio Longitud
2
qS
qS
q
q
WW
LL
W
L
Modelación y Simulación Ing. Margarita Aucancela Msc. 69
Escuela de Ingeniería en Sistemas y Computación
Análisis de colas
Modelo C: M/D/1
Un restaurante de papas fritas, tiene el servicio Drive-In enla cual los clientes arriban al restaurante a una tasa de 45por hora siguiendo una distribución de Poisson.
Las órdenes son procesadas con un modelo FIFO, y existeun solo servidor, el cual se demora 1.2 minutos en prepararla orden.
Modelación y Simulación Ing. Margarita Aucancela Msc. 69
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 70
Escuela de Ingeniería en Sistemas y Computación
Análisis de colas
Modelo C: M/D/1
Determinamos el λ y μ en las mismas unidades: λ = 45 clientes/horaμ= 1.2 min=72 clientes/horaLuego obtenemos las medidas de desempeño:
Modelación y Simulación Ing. Margarita Aucancela Msc. 70
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 71
Escuela de Ingeniería en Sistemas y Computación
Análisis de colas
Modelo C: M/D/1
Modelación y Simulación Ing. Margarita Aucancela Msc. 71
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 72
Escuela de Ingeniería en Sistemas y Computación
Análisis de colas
Modelo D:Este modelo puede ser usado por ejemplo si estamosconsiderando reparaciones de equipo en una fábrica que tiene 5máquinas. Este modelo permite cualquier número dereparadores a ser considerados.
La razón por la cual este modelo difiere de los otros tres es queahora hay una relación de dependencia entre la longitud de lacola y la rata de arribo. La situación extrema sería si en la fábricatenemos 5 máquinas, todas se han dañado y necesitanreparación; siendo en este caso la rata de arribo CERO. Engeneral, si la línea de espera crece, la rata de llegada tiende aceroModelación y Simulación Ing. Margarita Aucancela Msc. 72
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 73
Escuela de Ingeniería en Sistemas y Computación
Análisis de colas
Modelo D
Modelación y Simulación Ing. Margarita Aucancela Msc. 73
Escuela de Ingeniería en Sistemas y Computación
servicio deFactor
cola laen espera unidad una que promedio Tiempo
unidad la aatención de ntosrequerimie entre servicio Tiempode
promedio servicio de Tiempo
spotenciale clientes de Número
servicio de canales de Número
servicio el esperando unidades de promedio Número
servicio desector elen o colaen están no que unidades de promedio Número
servidas siendo unidades de promedio Número
eficiencia deFactor
cola laen esperar que tengaunidad una que de adProbabilid
:NOTACIÓN
X
W
U
T
N
M
L
J
H
F
D
Modelación y Simulación Ing. Margarita Aucancela Msc. 74
Escuela de Ingeniería en Sistemas y Computación
Análisis de colas
Modelo D
Modelación y Simulación Ing. Margarita Aucancela Msc. 74
Escuela de Ingeniería en Sistemas y Computación
HLJN
FNXH
XNFJ
XF
FT
LN
UTLW
FNL
UT
TX
............. Población la de Cuantía
servido siendo promedio Número
1 entofuncionamien promedio Número
1 ........ espera de promedio Tiempo
1 ........ esperaen promedio Número
....................... Servicio deFactor
:FÓRMULAS
Modelación y Simulación Ing. Margarita Aucancela Msc. 75
Escuela de Ingeniería en Sistemas y Computación
Ejercicios (Modelo D)Hace casi tres años, Gear Tandil SA instaló un conjunto de 10 robots, queincrementó considerablemente la productividad de su mano de obra, peroen el último tiempo la atención se ha enfocado en el mantenimiento. Laempresa no aplica el mantenimiento preventivo a los robots, en virtud de lagran variabilidad que se observa en la distribución de las averías. Cadamaquina tiene una distribución exponencial de averías(o distribución entrellegadas), con un tiempo promedio de 200 horas entre una y otra falla. Cadahora-maquina perdida como tiempo ocioso cuesta $30, lo cual significa quela empresa tiene que reaccionar con rapidez en cuanto falla una maquina.La empresa contrata solo a una persona de mantenimiento, quien necesita10 horas de promedio para reparar un robot. Los tiempos demantenimiento real están distribuidos exponencialmente. La tasa desalarios es de $10 por hora para el encargado de mantenimiento, el cualpuede dedicarse productivamente a otras actividades cuando no hay robotsque reparar. Calcule el costo diario por concepto de tiempo ocioso de lamano de obra y los robots.
Modelación y Simulación Ing. Margarita Aucancela Msc. 75
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 76
Escuela de Ingeniería en Sistemas y Computación
Ejercicios (Modelo D)
El modelo con la fuente finita es apropiado para esteanálisis, porque solo 10 máquinas constituyen la poblaciónde clientes y las suposiciones se han cumplid. En este caso,λ = 1/200, o sea, 0.005 averías por hora y μ=1/10=0,10robots por hora. Para calcular el coste del tiempo ociosopara la mano de obra y los robots, tenemos que estimar lautilización promedio del empleado de mantenimiento y L,es decir, el número promedio de robots incluidos en elsistema de mantenimiento.
Modelación y Simulación Ing. Margarita Aucancela Msc. 76
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 77
Escuela de Ingeniería en Sistemas y Computación
Ejercicios (Modelo D)
Modelación y Simulación Ing. Margarita Aucancela Msc. 77
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 78
Escuela de Ingeniería en Sistemas y Computación
Ejercicios (Modelo D)
Modelación y Simulación Ing. Margarita Aucancela Msc. 78
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 79
Escuela de Ingeniería en Sistemas y Computación
Ejercicios (Modelo D)
Modelación y Simulación Ing. Margarita Aucancela Msc. 79
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 80
Escuela de Ingeniería en Sistemas y Computación
OTROS MODELOS
Modelación y Simulación Ing. Margarita Aucancela Msc. 81
Escuela de Ingeniería en Sistemas y Computación
Supuestos
• Los clientes llegan de acuerdo a un proceso Poisson conesperanza λ.
• El tiempo de atención tiene una distribución general conesperanza µ.
• Existe un solo servidor.
• Se cuenta con una población infinita y la posibilidad deinfinitas filas.
Modelo M/G/1
Modelación y Simulación Ing. Margarita Aucancela Msc. 82
Escuela de Ingeniería en Sistemas y Computación
Modelo M/G/1
Modelación y Simulación Ing. Margarita Aucancela Msc. 83
Escuela de Ingeniería en Sistemas y Computación
Modelo M/G/1
Modelación y Simulación Ing. Margarita Aucancela Msc. 84
Escuela de Ingeniería en Sistemas y Computación
Modelo M/G/1
Modelación y Simulación Ing. Margarita Aucancela Msc. 85
Escuela de Ingeniería en Sistemas y Computación
Formula para L de Pollaczek - Khintchine.
- Nota : No es necesario conocer la distribución particular del tiempo de atención. Solo la esperanza y la desviación estándar
son necesarias.
L
22
2 1
Modelación y Simulación Ing. Margarita Aucancela Msc. 86
Escuela de Ingeniería en Sistemas y Computación
Modelo M/G/1
Modelación y Simulación Ing. Margarita Aucancela Msc. 87
Escuela de Ingeniería en Sistemas y Computación
Modelo M/G/1
Modelación y Simulación Ing. Margarita Aucancela Msc. 88
Escuela de Ingeniería en Sistemas y Computación
Modelo M/G/1
1
1
1
)1(2
0
222
w
q
qqs
qqs
PP
LWWW
LLL
Modelación y Simulación Ing. Margarita Aucancela Msc. 89
Escuela de Ingeniería en Sistemas y Computación
Modelo M/G/1: Ejemplo
• Un carwash puede atender un auto cada 5 min. y la tasa mediade llegadas es de 9 autos/hora, = 2 min.
• Obtenga las medidas de desempeño de acuerdo con el modeloM/G/1
• Además la probabilidad de tener 0 clientes en el sistema y laprobabilidad de que un cliente tenga que esperar por el servicio
Modelación y Simulación Ing. Margarita Aucancela Msc. 90
Escuela de Ingeniería en Sistemas y Computación
Modelo M/G/1: Ejemplo
75.025.01
min7.8145.0
min7.13228.01
31.1)1(2
06.275.31.1
0
222
w
q
q
qs
q
qs
PP
hrsL
W
hrsWW
clientesL
clientesLL
Modelación y Simulación Ing. Margarita Aucancela Msc. 91
Escuela de Ingeniería en Sistemas y Computación
Ejercicios (M/G/1)
Modelación y Simulación Ing. Margarita Aucancela Msc. 91
Escuela de Ingeniería en Sistemas y Computación
Modelación y Simulación Ing. Margarita Aucancela Msc. 92
Escuela de Ingeniería en Sistemas y Computación
Ejercicios (M/G/1)
Modelación y Simulación Ing. Margarita Aucancela Msc. 92
Escuela de Ingeniería en Sistemas y Computación