![Page 1: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/1.jpg)
Capítulo 8 Capítulo 8 Modelos de Líneas Modelos de Líneas
de de Espera Espera
Prof. Héctor Allende O.
Departamento de Informática
Universidad Santa María
![Page 2: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/2.jpg)
IntroducciónIntroducción
Una línea de espera es la resultante de un sistema cuando la demanda por un servicio supera la capacidad que puede proporcionar dicho servicio.
Un sistema está formado por un conjunto de entidades que en paralelo proporcionan servicio a las transacciones que aleatoriamente ingresan al sistema
![Page 3: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/3.jpg)
Ejemplos de Líneas de Espera• Cajas en Bancos• Tráfico en una Ciudad ( Terrestre o Aéreo)• Redes de Comunicaciones y Computadores• Tareas en un Computador• Líneas de Producción e Inventario• Talleres de Reparación• Hospitales• Estaciones de Bomberos• Sistemas de Distribución o Logísticos• Trabajos o Tareas que tenemos que hacer
![Page 4: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/4.jpg)
IntroducciónIntroducción
Elementos de estudio de dichas líneas de espera serán
entonces los tiempos asociados a cada uno de los
procesos que se desarrollan y las llegadas de las
transacciones al sistema.
Debido a que las variables están fuera del control del
tomador de decisiones, será necesario realizar el
modelado utilizando procesos estocásticos.
![Page 5: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/5.jpg)
Esquema Líneas de Espera
Población o Fuente deEntrada deClientes alSistema
Instalacionesde Servicio
SISTEMA de SERVICIO
Clientes Servidossalen del Sistema
de Servicio y vuelven a laPoblación
Algunos Clientespueden no entrar
al sistema deServicio
Clientes que entran al Sistema de Servicioy Esperan ser Atendidos
![Page 6: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/6.jpg)
Definición BásicaDefinición Básica
Una línea de espera puede modelarse como un
proceso estocástico en el cual la variable aleatoria se
define como el número de transacciones en el
sistema en un momento dado.
El conjunto de valores que puede tomar dicha variable
es { 0, 1, 2, 3, 4,.......,N } y cada uno de ellos tiene
asociada una probabilidad de ocurrencia {P0, P1,
P2... ........., PN }
![Page 7: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/7.jpg)
Objetivo del EstudioObjetivo del EstudioDeterminar el nivel de servicio del sistema:
• Cantidad de entidades presente
•Velocidad del Servicio en el sistema
Interesa minimizar el costo total del sistema
Los costos de transacciones dan cuenta de la pérdida por
tiempo de espera o la pérdida de clientes por abandono del
sistema.
Los costos de proporcionar el servicio, dan cuenta de los
salarios, energía, mantención, etc.
![Page 8: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/8.jpg)
Objetivo del estudioObjetivo del estudio Matemáticamente :
Min {Ct} = Ce S + C q Lq
dondeS = 1,2,3,4.........
Lq= f {S,E(t),.......}
Donde:
S: Número de entidades que proporcionan servicio.E(t): tiempo promedio de Servicio.
Lq: : Número de transacciones en espera.
Ce : Costo de servicio por entidad - tiempo.
Cq : Costo de servicio por transacción - tiempo.
Ct : Costo total por unidad de tiempo
![Page 9: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/9.jpg)
Optimización de CostosOptimización de Costos
No. de Servidores
Costo de servicio
Ce.S
Costo de servicio
Ct
Costo de espera
Cq.Lq
$/tiempo
Ct min
S*
![Page 10: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/10.jpg)
Líneas de Espera• Los modelos de LE nos permitirán estudiar
este tipo de fenómeno y determinar (en algunos casos):– Tiempo de Espera Promedio de los Clientes– Largo Promedio de la LE– Factor de Utilización de Servidores– Distribución Tiempos de Espera (Difícil)– Tiempos Ociosos– Eficiencia del Sistema– Pérdidas de Clientes
![Page 11: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/11.jpg)
• Población: Fuente de Entradas– Tamaño :
Infinito Finito
– Patrón de Llegadas : Tasa de Llegada– Patrón de Salidas :
Cliente Satisfecho Cliente vuelve a la l.e.
– Actitudes de los Clientes Cambios Renuncias Elusión
Elementos Básicos de Modelos de Espera
![Page 12: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/12.jpg)
Estructura General Sistema Espera
Estructura General Sistema Espera
Salida del Sistema
Entrada al Sistema
Servidores en paralelo
Fuente detransaccionespotenciales
Fila
![Page 13: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/13.jpg)
EstructuraEstructura
Los elementos básicos constituyentes de un
sistema de espera son los siguientes:
Servidor
Fila
Transacciones Potenciales
![Page 14: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/14.jpg)
ServidorServidor
Representa el mecanismo por el cual las transacciones reciben de una manera completa el servicio deseado.
Sus principales características son:
La Cantidad asignada a cada fila existente en el
sistema.
La distribución de probabilidad del Tiempo de
Atención a las transacciones o (Velocidad de
Servicio)
![Page 15: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/15.jpg)
FilaFilaEs el conjunto de transacciones que espera ser atendido por alguno de los servidores del sistema.
Sus principales características son:
Capacidad : es la cantidad máxima de transacciones que puede albergar cada fila existente en el sistema.
De acuerdo a esto se clasifican en finitas o infinitas.
Orden : es la forma como las transacciones son extraídas de la fila para su atención.
Ejemplos: FIFO, prioridad, aleatorio, etc.Forma de salir : como sale de la fila
mediante el proceso de serviciomediante factores de abandono : insatisfacción, desesperación, etc.
![Page 16: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/16.jpg)
Transacciones Potenciales
Transacciones Potenciales
Representan el número de clientes potenciales que podría requerir el servicio proporcionado por el sistema.
Sus principales características son:
El Tamaño del conjunto de potencial de
clientes.La distribución de probabilidad del Tiempo entre
llegadas o tasa de entrada promedio.
![Page 17: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/17.jpg)
NomenclaturaNomenclatura
S número de servidoresn número de clientes en el sistemaN número máximo de clientes permitidos en el sisteman flujo de clientes que entran cuando hay n clientes en el sisteman capacidad del servidor cuando hay n clientes en el sistemaE(t) tiempo promedio de proceso por clienteV(t) varianza del tiempo de procesoE(a) tiempo promedio entre llegadasV(a) varianza del tiempo entre llegada
C a
2
C s
2
C p
2
Coeficiente cuadrado de variación del flujo de clientes que entran al sistema.Coeficiente cuadrado de variación del tiempo de servicio.
Coeficiente cuadrado de variación del flujo de clientes que salen del sistema.
![Page 18: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/18.jpg)
NomenclaturaNomenclatura
pij probabilidad de que el sistema cambie del estado i a un estado j
después de un intervalo de tiempo
Pn probabilidad en estado estable de que existan n clientes en el sistema
L número promedio de clientes en el sistema
Lq número promedio de clientes en la fila
W tiempo promedio de permanencia en el sistema
Wq tiempo promedio de permanencia en la fila
utilización promedio del servicio
Ct costo total promedio del sistema de líneas de espera por unidad de
tiempo
Ce costo promedio de servicio por cliente por unidad de tiempo
Cq costo promedio de espera por cliente por unidad de tiempo
![Page 19: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/19.jpg)
Clasificación de Kendall y Lee
Clasificación de Kendall y Lee
Kendall y Lee 1953
Proponen un sistema de clasificación para los sistemas
de líneas de espera, el cual considera seis de las
características mencionadas en la estructura de los
modelos.
El cual tiene el siguiente formato
(a/b/c)(d/e/f)
![Page 20: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/20.jpg)
Clasificación de Kendall y Lee
Clasificación de Kendall y Lee
Donde
a distribución de probabilidad del tiempo entre llegadas de las transacciones
b distribuciones de probabilidad del tiempo de servicio.
Símbolos utilizados en estos dos primeros campos son:D: constanteEk: distribución Erlang con parámetro kG: cualquier tipo de distribuciónGI distribución general independienteH distribución hiperexponencialM distribución exponencial
![Page 21: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/21.jpg)
Clasificación de Kendall y Lee
Clasificación de Kendall y Leec número de servidores
d orden de atención de los clientes
Símbolos utilizados en este campo son:
FIFO : primeras entradas, primeros serviciosLIFO: últimas entradas, primeros servicios SIRO: orden aleatorioPR: con base en prioridadesGD: en forma general
e número máximo de clientes que soporta el sistema en un mismo instante de tiempo
f número de clientes potenciales del sistema de líneas de espera
![Page 22: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/22.jpg)
EjemplosEjemplos
Un modelo(M/D/3)(FCFS/20/20) representa la
clasificación de un sistema donde existen 3 servidores
en paralelo atendiendo de acuerdo con un orden de
primeras entradas, primeras salidas, con un tiempo de
servicio constante. El sistema tiene sólo 20 clientes
potenciales, los cuales podrían encontrarse dentro del
sistema en un mismo instante. El tiempo entre llegadas
de los clientes sigue una distribución exponencial y, en
caso de llegar y encontrar todos los servidores
ocupados, pasan a formarse de una fila común.
![Page 23: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/23.jpg)
Clasificación de Kendall y Lee
Clasificación de Kendall y Lee
Respetando la clasificación Kendall y Lee anterior, es
posible agrupar los diferentes modelos de una manera
donde los procesos Markovianos y los no Markovianos
se separan claramente.
Los Markovianos se dividen en modelos de capacidad
finita y modelos de capacidad Infinita.
Los No Markovianos, se clasifican en modelos con
tiempos entre llegadas exponenciales y tiempos de
servicios con cualquier tipo de distribución.
![Page 24: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/24.jpg)
Clasificación de Kendall y Lee
Mediante cadenas deMarkov de estadofinito
Mediante el factor de corrección K
(G/G/1) (FCFS/ / )
Mediante la fórmula de Pollaczek- Khintchine
(M/G/1) (FCFS/ / )
(M/M/S) (d/N/f)
(M/M/1) (FCFS/N/)
(M/M/1) (FCFS/N/N)
(M/M/S) (FCFS/N/)
(M/M/S) (FCFS/N/N)
Mediante cadenas de Markov y series geométricas
(M/M/S) (d/ / )
(M/M/1) (FCFS/ / )
(M/M/S) (FCFS/ / )Mediante el cálculo de límite superior
(G/G/S) ( FCFS //)
Mediante fórmulas generales
![Page 25: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/25.jpg)
Medidas de desempeñoMedidas de desempeño
Medidas de desempeñoUtilización de Servicio
Tasa de entrada Promedio
Número Promedio de Clientes en el sistema
Número promedio de Clientes en la fila
Tiempo promedio de espera en el sistema
Tiempo promedio de espera en la fila
Coeficiente cuadrado de variación
![Page 26: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/26.jpg)
Ecuaciones GeneralesEcuaciones Generales
Utilización de Servicios
Tasa de entrada Promedio
N
nnnP
0
Número Promedio de clientes en el sistema
SLL
nL
q
N
nnP
0
![Page 27: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/27.jpg)
Ecuaciones GeneralesEcuaciones Generales
Número promedio de clientes en la fila
Tiempo Promedio de espera en el sistema
)(tEWW
LW
q
Tiempo promedio de espera en la fila
N
snn
q PsnL )(
q
qL
W
![Page 28: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/28.jpg)
Ecuaciones GeneralesEcuaciones Generales
Coeficiente cuadrado de variación
)(
)(2
2
aE
aVCa Tiempo entre llegadas
Tiempo de servicio
Tiempo entre salidas del servicio
)(
)(2
2
tE
tVCs
22222 )1( sap CCC
![Page 29: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/29.jpg)
Procesos MarkovianosProcesos Markovianos
El proceso estocástico asociado a una línea de espera
tiene la propiedad markoviana, es decir la probabilidad
condicional de llegar a un estado futuro depende
exclusivamente del estado actual en el que se
encuentre el sistema, sin importar el estado inicial de
dicho sistema.
Las probabilidades condicionales deben cumplir con
ip
jipN
jij
ij
0
1
,0
![Page 30: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/30.jpg)
Procesos MarkovianosProcesos Markovianos
Las probabilidades de estado estacionario Pj
representan el comportamiento probabilístico de cada
estado del sistema a largo plazo y se calculan a partir
de las probabilidades de transición de un paso de
acuerdo con las probabilidades de transición de
acuerdo con
N
jj
N
jijij
P
pPP
0
0
10
lim
j
jijn
n
P
Pp
![Page 31: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/31.jpg)
NNNNN
N
N
N
pppp
pppp
pppp
pppp
...
...............
...
...
...
210
2221220
1121110
0020100
Estado Futuro
0 1 2 . . . N
0
1
2
. .
.
N
Estado
Actual
Matriz de probabilidades a un pasoMatriz de probabilidades a un paso
![Page 32: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/32.jpg)
Procesos MarkovianosProcesos Markovianos
La matriz probabilidades a un paso genera un sistema de
ecuaciones con N+1 incógnitas, N+1 ecuaciones
independientes y una ecuación redundante que debe ser
eliminada.
1......
......
......
......
......
210
221100
22221120022
12211110011
02201100000
N
NNNNNNN
NN
NN
NN
PPPP
PpPpPpPpP
PpPpPpPpP
PpPpPpPpP
PpPpPpPpP
![Page 33: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/33.jpg)
Matriz de probabilidadesMatriz de probabilidades
La solución a este sistema de ecuaciones origina los
valores de las probabilidades estacionarias independientes
del estado en que se encuentra el sistema inicialmente.
N
N
N
N
PPPP
PPPP
PPPP
PPPP
...
...............
...
...
...
210
210
210
210
Estado Futuro
0 1 2 . . . N
0
1
2
. . .
N
Estado
Actual
![Page 34: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/34.jpg)
Datos del ejemplo:• Número total de observaciones del SM: 73• Intervalo entre observación: 5 Minutos• Tabla de relaciones existente entre datos
EjemploEjemplo
10001
001005
55555
41078
00253
Estado Futuro
0 1 2 3 4
0
1
2
3
4
Estado
Actual
![Page 35: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/35.jpg)
La matriz anterior se explica como:
• De las 73 observaciones, en 10 de ellas el
sistema estuvo en estado 0 y 5 minutos
después el sistema había permanecido igual
en 3 ocasiones, había cambiado a estado 1
en 5 ocasiones, había cambiado a estado 2
en 2 ocasiones, y no se obsevaron cambios a
los estados 3 y 4.
EjemploEjemplo
![Page 36: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/36.jpg)
EjemploEjemplo
Calculando la probabilidad condicional de estado presente i al estado futuro j, se obtiene la siguiente matriz a un paso:
5.00005.0
0066.0033.0
2.02.02.02.02.0
2.005.0035.04.0
002.05.03.0
Estado Futuro
0 1 2 3 4
0
1
2
3
4
Estado
Actual
![Page 37: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/37.jpg)
EjemploEjemplo
Donde claramente
4....1,010
iparapN
jij
Aplicando las ecuaciones de estado estacionario a la matriz de un paso, se obtienen las ecuaciones
1
5.02.02.0
2.005.0
66.02.02.0
2.035.05.0
5.033.02.04.03.0
43210
4214
213
3202
2101
432100
PPPPP
PPPP
PPP
PPPP
PPPP
PPPPPP
![Page 38: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/38.jpg)
EjemploEjemplo
Resolviendo el sistema de ecuaciones
173.0
041.0
122.0
310.0
355.0
4
3
2
1
0
P
P
P
P
P
Número promedio de transacciones en la cola
7179.0
)173.0(3)041.0(2)122.0(1)310.0(0)(
q
N
snnq
L
PsnL
![Page 39: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/39.jpg)
Procesos MarkovianosProcesos Markovianos
Característica principal:
Distribución de probabilidad que define la llegada y salida de transacciones del sistema: Poisson.
Para un intervalo de tiempo t esta dado por:
.... 2, 1, 0!
) () | (0
00
0
xx
e tt x X p
t x
![Page 40: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/40.jpg)
Procesos MarkovianosProcesos Markovianos
Condiciones que se deben cumplir
•Solamente puede ocurrir una llegada entre t y t.•Solamente puede ocurrir una salida entre t y t.•Solamente puede ocurrir una llegada o una salida entre t y t.Por lo que el cambio de estado de n a n+1 se lleva
a cabo al ocurrir una llegada.
Un cambio de estado de n a n-1 solo ocurre
cuando se produce una salida.
![Page 41: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/41.jpg)
Matriz de probabilidad a un paso
Matriz de probabilidad a un paso
NNNN
NNNN
pp
pp
pp
ppp
ppp
pp
,1,
,11,1
...0000
...0000
.......
00...00
00...0
00...0
00...00
3332
232221
121110
0100
Estado Futuro
0 1 2 3 . . . N-1 N
0
1
2
3
.
N-1
N
Estado
Actual
![Page 42: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/42.jpg)
Procesos MarkovianosProcesos Markovianos
Lo cual conduce a:
Nntn
tnnnp
Nntnt
etnnnp
Nntntetnnn
p
n
n
,......,2,1,01,
,......,2,1,0)(1,
1,......,2,1,0)(1,
![Page 43: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/43.jpg)
Ecuaciones de BalanceEcuaciones de Balance
1............10
1,1
1,11,121,2
2211110011
1100000
1
N
NNNNNN
NNNNNNNNN
PPP
PpPpP
PpPpPpP
PpPpPpP
PpPpP
N
N
De la matriz se obtienen las ecuaciones de balance
![Page 44: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/44.jpg)
Ecuaciones de BalanceEcuaciones de Balance
1............
)1()1(
)111(2
)1(
)()1(
10
1
121
22111001
11000
N
NNNN
NNNNNNNN
PPP
PtPtP
tPPtttPP
tPPtttPP
PtPtP
N
Sustituyendo se obtiene
Resolviendo el sistema
321
02103
21
0102
1
001
PP
PP
PP
![Page 45: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/45.jpg)
Ecuaciones de Balance*****
Ecuaciones de Balance*****
Generalizando
Finalmente se obtiene
0321
13210
.....
.....PP
n
nn
1
321
1210
321
210
21
10
1
00 .....
....1
n
nP
![Page 46: Capítulo 8 Modelos de Líneas de Espera Prof. Héctor Allende O. Departamento de Informática Universidad Santa María](https://reader035.vdocumento.com/reader035/viewer/2022081503/5665b4711a28abb57c917f66/html5/thumbnails/46.jpg)
Ejemplo • Una sala de espera de un servicio de emergencia (SE) tiene
capacidad para 3 pacientes. Los usuarios llegan con una tasa de 8 por hora, con distribución de Poisson y son atendidos por una unidad de cuidados de emergencia (UCE) en 10 minutos con distribución exponencial. Si alguien llega al SE, y esta lleno, se retira a otro servicio cercano.
• Analizar el desempeño del servicio de emergencia (M/M/1) (FIFO/4/)
• Si se aumenta a dos UCE, evalúe el mejoramiento del desempeño del sistema (M/M2) (FIFO/5/)