modelos de lineas de espera
TRANSCRIPT
MODELOS DE LINEAS DE ESPERA
Ing. Jorge Moya Delgado Facultad de Ciencias Informticas
Hacer cola... me trauma
Descripcin formal del Modelo Lneas de Espera
INTRODUCCIN Las
colas son frecuentes en nuestra vida cotidiana: En un banco En un restaurante de comidas rpidas Al matricular en la universidad Al lavar el automvil
Introduccin En
general, a nadie le gusta esperar Cuando la paciencia llega a su lmite, la gente se va a otro lugar Sin embargo, un servicio muy rpido tendra un costo muy elevado Es necesario encontrar un balance adecuado cuando la demanda excede a la capacidad de servicio proporcionada
DESCRIPCION FORMAL DE MODELOSOBJETIVOS CATEGORIA TIPOS
OBJETIVOS El
objetivo es encontrar el estado estable del sistema y determinar una capacidad de servicio apropiada Minimizar el tiempo de atencin y servicio a los clientes o usuarios que llegan en un determinado tiempo
CATEGORIAPREDICTIVOS SIMBOLICOS DISCRETOS DETERMINISTICO PROBABILISTICO GENERALES MATEMATICOS
TIPOS DE MODELOS
MODELO BASICO MODELO BASICO CON COLA FINITA
UN SERVIDOR VARIOS SERVIDORES UN SERVIDOR VARIOS SERVIDORES
MODELO DE VARIAS LINEAS DE ESPERA:
MODELO DE UNA LINEA Y SERVIDORES SECUENCIALES
2. ESPECIFICACIONES1.
COMPONENTES
ESTRUCTURALES OPERATIVOS FLUENTES
COMPONENTES ESTRUCTURALES MODELO BASICO
Los modelos que requieren un servicio se generan a travs del tiempo de unamomento se selecciona un miembro de la cola, para proporcionarlo un servicio, mediante alguna regla conocida como disciplina de servicio, luego se lleva a cabo el servicio requerido por el cliente en un mecanismo de servicio, despus el cliente sale atendido.
fuente de entrada estos clientes entran al sistema y se unen a una cola, en determinado
MODELO BASICO DE LINEAS DE ESPERASistema de colas Fuente De entrada Disciplina de la cola
Cola
Mecanismo de servicio
Clientes Servidos
MODELO DE UNA COLA Y VARIOS SERVIDORESSistema de colas Servidor Fuente De entrada Cola Servidor Servidor Salidas Salidas Salidas
MODELO VARIAS COLAS MULTIPLES SERVIDORESSistema de colas Cola Fuente De entrada Cola Cola Servidor Servidor Servidor Salidas Salidas Salidas
MODELO DE UNA LINEA Y SERVIDORES SECUENCIALESFuente De entrada Sistema de colasLlegadas
Cola Servidor Cola Servidor Salidas
COMPONENTES OPERATIVOSFUENTES DE ENTRADA (Poblacin de Entrada) LINEAS DE ESPERA O COLA (Nmero mximo permisible de clientes que puede admitir) MECANISMOS DE SERVICIO (una o ms instalaciones de servicio) CLIENTES SERVIDOS (atendidos)
COMPONENTES FLUENTESPERSONAS MATERIALES OPERACIN DE VENTAS CARGA DESCARGA DE MATERIALES REPOSICIN DE INVENTARIOS DATOS INFORMACION, MENSAJES CONEXIONES
VARIABLES DESCRIPTIVAS
VARIABLES EXOGENASLq: Longitud de la cola es el nmero de clientes que hay en la cola N : numero de clientes o unidades en el sistema de colas Pn: Probabilidad que se encuentren n clientes en cola
Variables de estado (o del sistema)S: Nmero de servidores (servicios en paralelo) en el sistema de colas L: Longitud o nmero medio de unidades en el sistema (finito o infinito)
Variables Endgenas (salida)W: Tiempo de espera medio en el sistema Wq: Tiempo de espera medio en la cola E(WC): Costo de Espera E(SC): Costo de Servicio E(TC): Total de costos
PARAMETROS n : Tasa
media de llegada cuando se encuentran n clientes en el sistema n: Tasa media de servicio cuando se encuentran n clientes en el sistema : Factor de utilizacin del sistema
. ITERACCION ENTRE COMPONENTES
RELACIONES MATEMATICASIDENTIDADES CARACTERISTICAS OPERATIVAS
FUNCIONES
LINEALES FUNCIONES DE PROBABILIDAD TENDENCIAS
RED DE RELACIONES
IDENTIDADES
(MODELO BASICO)
Nmero esperado de clientes en el sistema L= W Longitud medio de la cola Lq = Wq
Relaciones Entre L w lq wqW ! L/P Wq ! Lq / P V ! P / sQn L ! PWLq = P2 / (Q - P)* Q
1 W ! Wq Q L ! PW Lq ! PWq P L ! Lq Q
Notacin Kendall A / B / C/m/d
A = distribucin de tiempos de llegada B = distribucin de tiempos de servicio C = Nmero de canales de servicio (s) m = Nmero mximo de unidades permitidas en el sistema (finito o infinito) d = Disciplina de cola, Puede ser:
FIFO (FCFS): primero en entrar primero en ser servido LIFO: ltimo en entrar, primero en ser servido SIRO (RANDOM): servicio aleatorio RRI Orden de prioridad
Distribucin =
M D G
Markov Determinista General
Distribuciones de ProbabilidadMarkov Corresponde a distribuciones de probabilidad de eventos sin memoria, no recuerdan el pasado. Determinista. Ocurren en forma constante y sin cambio. General. Otras distribuciones
Modelo M/M/1
Tiempo de llegadas aleatorias (Markoviano), independientes entre si. Tiempo de servicio Markoviano, es decir no depende de cuando ocurre sino de la longitud del intervalo EXP POISSON 1 servidor
Modelo M/M/1
Si en un periodo T, existe llegadas en promedio, entonces la probabilidad de n llegadas en el mismo periodo esta dado por:
Si es la tasa de servicio promedio, entonces la probabilidad de que el tiempo de servicio sea t, est dado por:
f(t) =
e-
t
Ejemplo
Una gra desplaza objetos de una mquina a otra y se utiliza cada vez que la maquina requiere carga o descarga. La demanda de servicios es aleatoria. Los datos tomados del registro de tiempos entre llamadas de servicios siguen una distribucin exponencial, con una media de llamada de cada 30 minutos. De manera semejante, el tiempo real de servicio de carga y descarga toma un promedio de 10 minutos. Si el tiempo de maquina esta avaluado en $8,50 por hora, cunto vale el tiempo perdido por da.a) b) c) d) e) f)
notacin de kendal tiempo perdido por maquina la probabilidad de espera en cola y servicio numero esperado en la cola tiempo esperado en la cola costo del tiempo perdido en da
Solucin Analtica
P = 2 = media de llegada = 30 minutos = 2 por hora Q = 6 = media de servicio 10 minutos por servicio = 6 por hora
a) notacin de kendal M/M/1 b) tiempo perdido por maquina = tiempo promedio en el sistema W = 1 / (Q - P) = 1 / ( 6 2 ) = 0,25 hora c) Probabilidad de espera V = P / Q Lq = P2 / (Q - P)* Q = 36 / (6 2) * 6 = 36 / 24 = 1,5 e) tiempo esperado en la cola Wq = P / Q (Q - P) Wq = 2 / 6 (6 2) Wq = 2 / 24 Wq = 0.08 f) Demanda diaria = 8P ocho horas diarias = 8 * 2 = 16 llamadas costo diario = 8,50 * 0,25 * 16 = $34 /da
Ejercicio # 2
a) b) c)
Una tienda de alimentacin es atendida por una persona. Aparentemente, el patrn de llegada de clientes durante los sbados se comporta siguiendo un proceso de Poisson con una tasa de llegada de 10 personas por hora. A los clientes se les atiende siguiendo un orden tipo FIFO y, debido al prestigio de la tienda, una vez que llegan, estn dispuestos a esperar el servicio. Se estima que el tiempo que lleva a atender a un cliente se distribuye exponencialmente con un tiempo medio de 4 minutos. Determinar: La probabilidad que haya una lnea de espera La longitud media de la lnea de espera El tiempo medio que un cliente permanece en cola
Solucina)
Se trata de una cola infinita con servidor (M/M/1//FIFO)
(10/60) clientes / servicio Q = (1 / 4) servicio /minuto V = P / Q = (10/60) / (1/4) = 2/3 = 0.6 < 1 condicin de estabilidad el sistema p0 = 1 p = (1 (2/3) = 1/3 a) La probabilidad de n clientes en el sistema viene dado por pn = (1 p)pn p1 = (1 p)p = (1 2/3 ) (2/3) = 2/9 b) Longitud esperada (media) de la cola (19/60)2 Lq = P2 / (Q - P)* Q = ---------------------------------------- = 1.3 aprox 1 cliente 1 / 4 (( 1 / 4) (10/60)) c) Tiempo medio que un cliente espera en cola Wq = P / Q (Q - P) Wq = (10 / 60) / 1 / 4 (( 1 / 4) (10/60)) Wq = 7.98 aprox 8 minutos
P=