Capítulo 8
Modelos de Líneas
de
Espera
Prof. Héctor Allende O.
Departamento de Informática
Universidad Santa María
Introducció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
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
Introducció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.
Esquema Líneas de Espera
Clientes que entran
al Sistema de Servicio
y Esperan ser Atendidos
Instalaciones
de Servicio
Población o
Fuente de
Entrada de
Clientes al
Sistema
SISTEMA de SERVICIO
Algunos Clientes
pueden no entrar
al sistema de
Servicio
Clientes Servidos
salen del Sistema
de Servicio y
vuelven a la
Población
Definició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 }
Objetivo del Estudio
Determinar 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.
Objetivo del estudio
Matemáticamente :
Min {Ct} = Ce S + C q Lq
donde
S = 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
Optimización de Costos
$/tiempo
Costo de servicio
Ct
Costo de servicio
Ct min
Ce.S
Costo de espera
Cq.Lq
S*
No. de Servidores
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
Elementos Básicos de Modelos de Espera
• 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
Estructura General Sistema Espera
Servidores
en paralelo
Entrada al
Sistema
Fila
Fuente de
transacciones
potenciales
Salida del
Sistema
Estructura
Los elementos básicos constituyentes
sistema de espera son los siguientes:
 Servidor
 Fila
 Transacciones Potenciales
de un
Servidor
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)
Fila
Es 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 servicio
mediante
factores
de
abandono
:
insatisfacción, desesperación, etc.
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.
Nomenclatura
S
n
N
n
n
E(t)
V(t)
E(a)
V(a)
C
C
C
2
a
2
s
2
p
número de servidores
número de clientes en el sistema
número máximo de clientes permitidos en el sistema
flujo de clientes que entran cuando hay n clientes en el sistema
capacidad del servidor cuando hay n clientes en el sistema
tiempo promedio de proceso por cliente
varianza del tiempo de proceso
tiempo promedio entre llegadas
varianza del tiempo entre llegada
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.
Nomenclatura
pij
Pn
L
Lq
W
Wq

Ct
Ce
Cq
probabilidad de que el sistema cambie del estado i a un estado j
después de un intervalo de tiempo
probabilidad en estado estable de que existan n clientes en el sistema
número promedio de clientes en el sistema
número promedio de clientes en la fila
tiempo promedio de permanencia en el sistema
tiempo promedio de permanencia en la fila
utilización promedio del servicio
costo total promedio del sistema de líneas de espera por unidad de
tiempo
costo promedio de servicio por cliente por unidad de tiempo
costo promedio de espera por cliente por unidad de tiempo
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)
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:
constante
Ek:
distribución Erlang con parámetro k
G:
cualquier tipo de distribución
GI
distribución general independiente
H
distribución hiperexponencial
M
distribución exponencial
Clasificación de Kendall y Lee
c
número de servidores
d
orden de atención de los clientes
Símbolos utilizados en este campo son:
e
f
FIFO : primeras entradas, primeros servicios
LIFO: últimas entradas, primeros servicios
SIRO: orden aleatorio
PR: con base en prioridades
GD: en forma general
número máximo de clientes que soporta el
sistema en un mismo instante de tiempo
número de clientes potenciales del sistema de
líneas de espera
Ejemplos
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.
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.
Clasificación de Kendall y Lee
Mediante fórmulas generales
Mediante cadenas de
Markov de estado
finito
(M/M/S)
(d/N/f)
(M/M/1) (FCFS/N/)
(M/M/1) (FCFS/N/N)
(M/M/S) (FCFS/N/)
Mediante el factor de
corrección K
(G/G/1) (FCFS/ / )
Mediante la fórmula de
Pollaczek- Khintchine
(M/G/1) (FCFS/  / )
Mediante cadenas de Markov
y series geométricas
(M/M/S) (FCFS/N/N)
(M/M/S)
(d/  / )
(M/M/1) (FCFS/  / )
Mediante el cálculo de límite superior
(G/G/S) ( FCFS //)
(M/M/S) (FCFS/  / )
Medidas de desempeño
Medidas de desempeño
Utilizació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
Ecuaciones Generales
Utilización de Servicio
 

s
N
Tasa de entrada Promedio
 
 P
n0
n
N
Número Promedio de
clientes en el sistema
L 
nP
n0
L  Lq  S
n
n
Ecuaciones Generales
Número promedio de
clientes en la fila
Tiempo Promedio de
espera en el sistema
Tiempo promedio de
espera en la fila
N
Lq 
 (n  s) P
ns
W 
n
L

W  W q  E (t )
Wq 
Lq

Ecuaciones Generales
Coeficiente cuadrado de variación
Tiempo entre llegadas
Tiempo de servicio
C
2
a
C
2
s


V (a )
 E ( a )
2
V (t )
 E (t )
2
2
2
2
2
2
Tiempo entre salidas del
C p  C a (1   )  C s 
servicio
Procesos 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
p ij  0
 i, j
N

j0
p ij  1
i
Procesos 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
lim
n 
p
n
ij
 Pj
N
Pj 

Pi p ij
j0
Pj  0
N

j0
Pj  1
Matriz de probabilidades a un paso
Estado Futuro
0
 p 00

p 10
1

2  p 20

...
...

N p
 N0
0
Estado
Actual
1
2
...
p 01
p 02
...
p 11
p 12
...
p 12
p 22
...
...
...
...
pN1
pN 2
...
N
p0 N 

p1 N

p2N 

... 
p NN 
Procesos 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.
P0  p 00 P0  p 10 P1  p 20 P2  ......  p N 0 PN
P1  p 01 P0  p 11 P1  p 21 P2  ......  p N 1 PN
P2  p 02 P0  p 12 P1  p 22 P2  ......  p N 2 PN
PN  p 0 N P0  p 1 N P1  p 2 N P2  ......  p NN PN
P0  P1  P2  ......  PN  1
Matriz 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.
0
0
Estado
1
Actual
2
...
N
 P0

P
 0
 P0

 ...
P
 0
Estado Futuro
1
2
...
P1
P2
...
P1
P2
...
P1
P2
...
...
...
...
P1
P2
...
N
PN 

PN

PN 

... 
PN 

Ejemplo
Datos del ejemplo:
• Número total de observaciones del SM: 73
• Intervalo entre observación: 5 Minutos
• Tabla de relaciones existente entre datos
0
0
Estado
Actual
1
2
3
4
3

8

5

5
1

Estado Futuro
1
2
3
5
2
0
7
0
1
5
5
5
0
10
0
0
0
0
4
0

4

5

0
1

Ejemplo
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.
Ejemplo
Calculando la probabilidad condicional de estado
presente i al estado futuro j, se obtiene la siguiente
matriz a un paso:
0
Estado
Actual
0  0 .3

0 .4
1

2  0 .2

3  0 . 33
4 
 0 .5
1
Estado Futuro
2
3
0 .5
0 .2
0
0 . 35
0
0 . 05
0 .2
0 .2
0 .2
0
0 . 66
0
0
0
0
4
0 

0 .2

0 .2 

0 
0 .5 

Ejemplo
Donde claramente
N

p ij  1
para
i  0 ,1 .... 4
j0
Aplicando las ecuaciones de estado estacionario a la matriz de un
paso, se obtienen las ecuaciones
P0  0 . 3 P0  0 . 4 P1  0 . 2 P2  0 . 33 P3  0 . 5 P4
P1  0 . 5 P0  0 . 35 P1  0 . 2 P2
P2  0 . 2 P0  0 . 2 P2  0 . 66 P3
P3  0 . 05 P1  0 . 2 P2
P4  0 . 2 P1  0 . 2 P2  0 . 5 P4
P0  P1  P2  P3  P4  1
Ejemplo
Resolviendo el sistema de ecuaciones
P0  0 . 355
P1  0 . 310
P2  0 . 122
P3  0 . 041
P4  0 . 173
Número promedio de transacciones en la cola
N
Lq 
 (n  s) P
ns
L q  0 . 7179
n
 0 ( 0 . 310 )  1( 0 . 122 )  2 ( 0 . 041 )  3 ( 0 . 173 )
Procesos 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:
x0!
p ( X  x0 |  t ) 
x 0  0 ,1, 2 ....
(  t ) 0 e
x

t
Procesos 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.
Matriz de probabilidad a un paso
Estado Futuro
0
 p 00

1  p 10
2  0

3  0
.  .

N-1  0
N  0

0
Estado
Actual
1
2
3
...
N-1
p 01
0
0
...
0
p 11
p 12
0
...
0
p 21
p 22
p 23
...
0
0
p 32
p 33
...
0
.
.
.
.
.
0
0
0
...
p N 1 , N  1
0
0
0
...
p N , N 1
N


0

0 

0 
. 

p N 1 , N 
p N , N 
0
Procesos Markovianos
Lo cual conduce a:
p
 ( t )e
n
n, n  1
  n t
  n t
   t n  0 ,1, 2 ,......, N  1
n
p
 (  t )e
n
n, n  1
p
 1    t    t n  0 ,1, 2 ,......, N
n
n, n
n
   t n  0 ,1, 2 ,......, N
n
Ecuaciones de Balance
De la matriz se obtienen las ecuaciones de balance
P0  p 00 P0  p 10 P1
P1  p 01 P0  p 11 P1  p 21 P2
PN 1  p N  2 , N 1 PN  2  p N 1 , N 1 PN 1  p N , N 1 PN
PN  p N 1 , N PN 1  p NN PN
P0  P1  .......... ..  PN  1
Ecuaciones de Balance
Sustituyendo se obtiene
P0  (1   0  t ) P0  (  1  t ) P1
P1   0  tP0  (1   1  t   1  t ) P1   2  tP2
PN 1   N  2  tPN  2  (1   N  1 t   N  1 t ) PN 1   N  tPN
PN  (  N  1 t ) PN 1  (1   N  t ) PN
P0  P1  .......... ..  PN  1
 0 P0
1
 0  1 P0

1 2
 0  1  2 P0

1 2  3
P1 
Resolviendo el sistema
P2
P3
Ecuaciones de Balance*****
Generalizando
Pn 
 0 1  2  3 .....  n 1
 1  2  3 .....  n
P0
Finalmente se obtiene
  0  0 1
 0 1  2  0  1  2 ....  n 1 
P0  1 




 1  1  2  1  2  3  1  2  3 .....  n 

1
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/)
Descargar

Linea de espera