Post on 15-Dec-2015
description
Ing. Vicente Campos Contreras
1
TEORIA DE COLAS O LINEAS DE ESPERA
De todos los conceptos tratados en las técnicas básicas de la
investigación de operaciones, la teoría de colas aparece como la mayor
aplicación potencial y sin embargo es quizás la más difícil de aplicar. Toda
clase de negocios, gobierno, industria, escuelas y hospitales, grandes y
pequeños tos tienen problemas de colas. Muchos de ellos se pueden
beneficiar de un análisis de I de O para determinar las condiciones de
operación de costo mínimo (máximo rendimiento)
El ejemplo clásico de una cola consta de dos elementos principales,
como se ilustra en la siguiente figura. Los clientes llegan a la cola y esperan
hasta que se les proporcione un servicio, o si el sistema está vacío, el cliente
puede ser atendido inmediatamente. Después de que el servicio queda
terminado el cliente abandona el sistema.
Definición de términos:
Los problemas de colas consisten en emparejar apropiadamente la tasa
de servicio del proceso con la tasa de llegadas de trabajos para realizar. Se
definen algunos términos básicos.
Cliente Unidad que llega requiriendo la realización de algún servicio. Los
clientes pueden ser personas, máquinas, partes, etc.
Cola (línea de espera) Número de clientes que esperan ser atendidos.
Normalmente la cola no incluye el cliente que está siendo atendido.
Canal de servicio Es el proceso o sistema que está efectuando el servicio
para el cliente. Este puede ser simple o multicanal.
Estructura básica de la línea de espera:
SISTEMA TOTAL
COLA
(CLIENTES)
UNIDAD DE
SERVICIO
SALIDA ENTRADA
Ing. Vicente Campos Contreras
2
Una línea de espera está constituida por un cliente que requiere de un
servicio (proporcionado por un servidor) en un determinado periodo. Los
clientes entran aleatoriamente al sistema y forman una o varias colas (líneas
de espera) para ser atendido. Si el servidor está desocupado de acuerdo a
ciertas reglas preestablecidas, conocidas con el nombre de disciplinas del
servicio, se proporciona el servicio a los elementos de la cola. El cliente
será atendido en un periodo determinado de tiempo, llamado tiempo de
servicio. Al finalizar éste, los clientes abandonan el sistema. Los clientes
que se forman en una cola lo hacen en un área de espera.
Las líneas de espera se pueden clasificar de acuerdo a:
a. El número de clientes que pueden esperar en la cola. Estos pueden
ser finitos o infinitos. En la realidad sólo existen los primeros;
matemáticamente se facilitan los cálculos de los segundos.
b. La fuente que genera la población de clientes. Esta fuente puede
tener una producción finita o infinita (no confundir con la
población que espera, que también puede ser finita o infinita).
c. A la manera como esperan los clientes (en una cola o en varias o
sin opción de cambiarse de cola).
d. El tiempo transcurrido entre la llegada de un cliente y el
inmediatamente anterior. El intervalo de tiempo que puede ser una
constante o una variable aleatoria independiente, cuya distribución
de probabilidad se puede o no conocer. El enfoque del análisis
matemático de las líneas de espera, está muy bien desarrollado para
el caso constante y variable, cuando la distribución de llegadas es
Poisson. Para otras distribuciones se utiliza el enfoque de
simulación.
Cuando las llegadas no son independientes (como sería el caso
de la llegada de un grupo de pacientes a un centro de emergencia,
cuando éstos sufrieron el mismo accidente), se utiliza un enfoque
de simulación.
e. El tiempo de servicio. Este intervalo de tiempo puede ser una
constante o una variable aleatoria dependiente o independiente cuya
distribución de probabilidad se puede o no conocer
El enfoque matemático ha proporcionado resultados de las líneas
de espera cuando el tiempo de servicio es constante tiene una
Ing. Vicente Campos Contreras
3
distribución exponencial negativa o una distribución Erlang. Para
otras distribuciones se utiliza el enfoque de simulación.
f. La disciplina de la cola. Se puede utilizar una política en la cual el
primero que llega a la cola es el primero en que se le proporciona el
servicio; existen políticas de prelación o prioridad, como es el caso
de los servicios médicos de emergencia en donde las características
del cliente indican en qué orden se le proporciona el servicio.
g. El número de servidores uno o más.
h. La estructura de las estaciones de servicio. Estas pueden estar en
serie, en paralelo, o mixtas.
i. La estabilidad del sistema, que puede ser estable o transitoria. Aquí
se cubre solo la condición de estable y específicamente aquellos
casos donde el periodo determinado sólo puede ocurrir una entrada
al sistema (nacimiento) y una salida del mismo (muerte). De ahí
que matemáticamente se conozca a estos procesos estables de
nacimiento y muerte.
La tasa a la cual llegan los clientes para ser atendidos se denota tasa de
llegadas (lambda), esta es una tasa cuyas unidades son clientes por hora,
clientes por día, etc.
La tasa a la cual la unidad de servicio puede atender al cliente se
denomina tasa de servicio (mu). Esta tasa tiene unidades iguales a las de
y representan la máxima capacidad de servicio suponiendo que la unidad de
servicio no está ociosa. Normalmente se supone que estas tasas representan
un promedio de muchos valores posibles que se pueden describir mediante
una distribución Poisson.
Notación en la teoría de líneas de espera:
En forma resumida se tiene la siguiente notación:
: Número promedio de llegadas al sistema por unidad de tiempo
: Número promedio de servicios por unidad de tiempo
Factor de utilización del sistema con un servidor
S: Número de servidores en el sistema
Ing. Vicente Campos Contreras
4
S Factor de utilización del sistema con servidores múltiples
Ts: Valor esperado de tiempo de espera para que se proporcione
servicio a la última llegada de la cola
Tw: Valor esperado de tiempo de espera para que la última llegada a
la cola abandone el sistema una vez que se le haya
proporcionado el servicio
1/: Tiempo promedio que transcurre entre dos llegadas consecutivas
1/: tiempo promedio de servicio a un cliente
n: Número esperado de llegadas de nuevos clientes por unidad de
tiempo, cuando ya existen n en el sistema
n: Número esperado de servicios por unidad de tiempo, cuando
existen n clientes en el sistema.
L: Valor esperado de número de gentes formadas en la cola
W: Valor esperado de número de gentes en el sistema, es decir,
esperando en la cola y recibiendo un servicio
Pn : Probabilidad de que en un momento de arribo a la cola se
encuentren n personas en el sistema, S recibiendo un servicio, en
el caso de S (S≥1) servidores, y n – S formados en la cola
P0: Probabilidad de que en el momento de arribo a la cola, el sistema
se encuentre vacío
s: Utilización promedio de cada uno de los S servidores (S≥1),
dada en porcentaje de tiempo
MODELOS DE LINEA DE ESPERA
Usando los términos de diferentes modelos de colas se pueden dividir
en clases con base a los tipos de problemas que se modelan. Esto permite
presentar un mejor punto de vista del tema.
Tipo de problema: Modelo de
Colas
Tamaño de la población: Infinito Finito
Número de canales: Simple Múltiple Simple Múltiple
Ing. Vicente Campos Contreras
5
Una cola un servidor-pobacion infinita
Quizás el modelo de colas más fácil de resolver es el de una cola de
canal simple que da servicio a una población infinita. Por tal razón, se
considera primero. Hay siete ecuaciones básicas que pueden usarse para
analizar esta clase de problemas.
La probabilidad de hallar el sistema ocupado es
Las siguientes ecuaciones no son válidas sólo cuando
La probabilidad P0 de hallar el sistema vacío es P0 = 1-
La probabilidad de hallar n personas en el sistema Pn =
m
n
(1-
El número esperado de clientes en la cola L =
2
El número esperado de clientes en el sistema es W=
El tiempo esperado en la cola es )(
Ts
El tiempo esperado en el sistema es )(
1
Tw = Ts + (1/
Ejemplo: PEMEX estudia la utilización de la gasolinera que se
encuentra en el Km 70 de la carretera estatal Jiquilpan Morelia. La
gasolinera tiene 6 bombas, 4 para gasolina magna, una para nova y otra
para diesel.
Las llegadas de autobuses que cargan diesel muestran una distribución
que se aproxima a la Poisson de 5 autobuses por hora. Mientras que el
Ing. Vicente Campos Contreras
6
servicio muestra una distribución exponencial de 7 por hora.
Sólo se puede dar servicio en esa bomba a un autobús a la vez, y se
sirve a los autobuses en el orden que llegan a la bomba.
Encuentre todos los parámetros que describen cuantitativamente a
esta bomba diesel, para que posteriormente se pueda tomar una decisión,
acerca de la instalación de otras bombas diesel en ese lugar.
Se tiene que 5, , por lo que
La probabilidad de encontrar la bomba diesel vacía es:
P0 = 1- (
Mientras que la probabilidad de encontrar un autobús cargando y dos
en la cola es: P3 3
(1- 3
El número esperado de autobuses que hacen cola es:
L =
autobuses
El número esperado de autobuses en el sistema es:
W = autobuses
El tiempo promedio en la cola es:
Ts =horas
El tiempo promedio para salir del sistema es:
Tw = horas
Una cola, servidores múltiples en paralelo, población infinita:
Se supone un sistema con una sola cola, a la cual puede llegar un
número infinito de clientes en espera de recibir un mismo servicio por parte
de S (S>1) servidores en paralelo. La política del sistema es que se sirve a
los clientes en el orden de su llegada; el servicio lo proporciona el primer
servidor que se haya desocupado. Todos los servidores están desocupados
al principio y se irán ocupando en forma progresiva en la medida que vayan
llegando los clientes.
El número promedio de llegadas por unidad de tiempo es y se
Ing. Vicente Campos Contreras
7
supone que éste tiene una distribución Poisson.
El número promedio de servicios de cada servidor por unidad de
tiempo es el mismo y se denota por . Se supone que este número tiene una
distribución exponencial negativa.
Así como en el caso de un servidor se supone que (para
que no se formen colas de tamaño infinito), en el caso de servidores
múltiples se requiere que cumpla la condición S, la cual se puede
escribir como S. Las ecuaciones básicas que pueden usarse para
analizar esta clase de problemas.
La probabilidad de hallar el sistema ocupado es S
Las siguientes ecuaciones no son válidas sólo cuando S
La probabilidad P0 (t) de hallar el sistema vacío es
11
0
0!
1
!
1
S
S
SmP
SmS
m
La probabilidad de hallar m personas en el sistema
n
SnSS
PoPn
!; para n > S
n
n
PoPn
!; para n ≤ S
El número esperado de clientes en la cola
2)()!1(
SS
Po
L
S
El número esperado de clientes en el sistema es
LW
El tiempo esperado en la cola es Ts =L/
Ing. Vicente Campos Contreras
8
El tiempo esperado en el sistema es Tw = Ts + (1/
Ejemplo: Suponga que en un cruce fronterizo se bifurcan 5 garitas de
inspección migratoria y aduanera.
Suponga que la llegada de automóviles tiene una distribución Poisson
con = 15 llegadas por hora, Mientras que el número de servicios tiene una
distribución exponencial con8 servicios por hora.
Por decreto gubernamental, no existe prioridad en el trato, y así
atienden en primer término al primer automóvil de la cola y así
sucesivamente.
Encuentre todos los parámetros que describen cuantitativamente éste
problema.
Primero se corrobora que el parámetro S
S
Se tiene y
1
1
0
0!
1
!
1
S
S
SmP
SmS
m
1
5432104
0
015)8(5
)8(5875.1
!5
1875.1
!4
1875.1
!3
1875.1
!2
1875.1
!1
1875.1
!0
1
m
P
={1 + 1.875 + 1.7578 + 1.0986 + 0.515 + 0.196 (1.6)}
= {6.5552}
Lo anterior implica que existe un 15% de probabilidades de que, al
llegar un automóvil a cualquier garita en un tiempo t, las 5 estaciones de
servicio se encuentran vacías.
Por lo tanto, no se forma una cola asta que m ≥ 6
Ing. Vicente Campos Contreras
9
El largo de la cola, L, es:
2)()!1(
SS
Po
L
S
2
5
)15)8(5()!15(
)1526.0()875.1)(8(15
L automóviles
El número de elementos en el sistema, W, es:
W = L + (
W = 0.0283 + 1.875 = 1.9033 automóviles
El tiempo esperado en la cola es Ts =L/
Ts = 0.0283/15 = 0.0019 de hora
El tiempo esperado en el sistema es
Tw = Ts + (1/
Tw = 0.0019 + 1/8 = 0.1269 de hora
La probabilidad de encontrar m personas en el sistema se muestra en la
siguiente probabilidad.
Una cola – un servidor – población finita.
Se supone una población finita de m elementos (0 < m <)
requiriendo servicios.
Si m es la población que pudiera requerir un servicio determinado y n
(n < m) elementos de esa población piden ese servicio, entonces, las
ecuaciones son:
1
n
nm
m
p
np
!
!
0
m
n p
np
p
0 0
1
0
Ing. Vicente Campos Contreras
10
n
nm
m
np
!
!
01 pmL
01 pLW
0
1 p
L
ST
1
ST
WT
Una cola – servidores múltiples en paralelo – población finita
Para S servidores y una población finita de tamaño m se tienen las
siguientes ecuaciones:
0
0
p
n
nC
mp
np
para 0 n S
m
n Po
Pn
m
n pn
pp
0
11
0 00
0
!!
!
0
p
n
snSSnm
m
p
np
para S < n m
n
pm
SnSnL
1
n
pm
nnW
0
LW
W
ST
1
ST
WT