Facultad Regional Mar del Plata – TECNICO UNIVERSITARIO EN SISTEMAS INFORMÁTICOS

Investigación Operativa II
Teoría de Colas o Fenómenos de Espera

Introducción

En general, pueden aplicarse los modelos de colas cuando se tienen unidades de llegada
que solicitan un servicio y que están dispuestas a esperar si el servicio no está inmediatamente
disponible.
Las aplicaciones más evidentes de los modelos de líneas de espera ocurren cuando llegan
personas o clientes para obtener algún servicio, como en una caja en un comercio, en un banco,
en un restaurante, etc. Sin embargo, con un poco de creatividad, es posible aplicar los modelos
de líneas de espera a muchas situaciones diferentes; por ejemplo, llamadas telefónicas que
esperan su conexión, pedidos por correo y que esperan ser procesados, máquinas que aguardan
su reparación, trabajos de manufactura o paquetes de datos que deben ser procesados, dinero
que espera ser invertido o gastado, y así sucesivamente.
Con el objeto de verificar si una situación determinada del sistema de líneas de espera se
ajusta o no a un modelo conocido, se requiere de un método para clasificar las líneas de espera.
Esa clasificación debe de responder preguntas como las siguientes:

 ¿El sistema de líneas de espera tiene un solo punto de servicio o existen varios puntos de
servicio en secuencia?
 ¿Existe solo una instalación de servicio o son múltiples las instalaciones de servicio que
pueden atender a una unidad?
 ¿Las unidades que requieren el servicio llegan siguiendo algún patrón o llegan en forma
aleatoria?
 ¿El tiempo que requieren para el servicio se da en algún patrón de o asume duraciones
aleatorias de tiempo?

Componentes

Podemos establecer como componentes de la teoría de colas a:

1. La población fuente y la manera que los clientes llegan al sistema.
2. El sistema de prestación del servicio.
3. La condición del cliente que sale del sistema.

1 La población fuente y la manera que los clientes llegan al sistema

La población que arriba al sistema puede ser finita o infinita:

 Finita, cuando el tamaño es tal que si el grupo de usuarios se reduce en uno, luego de
cada atención, se reduce la probabilidad de la siguiente ocurrencia.
 Infinita, cuando el tamaño es tan grande que la atención de los usuarios no modifica la
probabilidad de la siguiente ocurrencia.

La distribución de llegadas es la manera en que un cliente llega a la fila (o sistema).

 Constante.
 Variable (aleatoria).
2 El sistema de prestación del servicio

Caso 1: El sistema lo constituyen la fila o línea de espera y el canal de atención.

Sistema

Empleado

Toma y surte
Línea de espera o cola el pedido
El cliente sale después que
se surte su pedido

Caso 2: El sistema lo constituyen la fila o línea de espera y dos o más canales de

atención.

Canal 1

Empleado A
El cliente pasa al
siguiente canal El cliente sale después
abierto que se surte su pedido

Canal 2
Línea de espera o cola

Empleado B

El modelo de costos totales en función de los canales de servicios disponibles incluye el

costo asociado al tiempo que las unidades esperan para ser atendidas y el costo en el que se
incurre para operar la instalación de servicio.

Costo

N° de
canales de
servicios

2
3 La condición del cliente que sale del sistema

Una vez atendido el cliente existen dos posibilidades:

 Puede regresar a la población fuente y volverse de inmediato un candidato que

compite nuevamente por el servicio.
 Puede haber una ligera probabilidad de un nuevo servicio.

Notación Kendall

Por lo general, las tasas de llegada y de servicio no se conocen con certeza sino que son de
naturaleza estocástica o probabilística. Es decir los tiempos de llegada y de servicio deben
describirse a través de distribuciones de probabilidad y las distribuciones de probabilidad que se
elijan deben referir la forma en que se comportan los tiempos de llegada o de servicio.
En teoría de líneas de espera o de colas se utilizan tres distribuciones de probabilidad
bastante comunes, que son: Markov, Determinística y General.
 La distribución de Markov, en honor al matemático A.A. Markov quien identifico los eventos
"sin memoria", se utiliza para describir ocurrencias aleatorias, es decir, aquellas de las que
puede decirse que carecen de memoria acerca de los eventos pasados.
 Una distribución determinística es aquella en que los sucesos ocurren en forma constante
y sin cambio.
 La distribución general sería cualquier otra distribución de probabilidad. Es posible
describir el patrón de llegadas por medio de una distribución de probabilidad y el patrón de
servicio a través de otra.
 Para permitir un adecuado uso de los diversos sistemas de líneas de espera, Kendall,
matemático británico elaboro una notación abreviada para describir en forma sucinta los
parámetros de un sistema de este tipo. En la notación Kendall un sistema de líneas de
espera se designa como
A/B/C
En donde:
A = se sustituye por la letra que denote la distribución de llegada.
B = se sustituye por la letra que denote la distribución de servicio.
C = se sustituye por el entero positivo que denote el número de canales de servicio.

La notación kendall también utiliza

M = Markoviano, D = determinística, G = General

Por ejemplo un sistema de líneas de espera con llegadas aleatorias, servicio determinístico
y tres canales de servicio se identificará en notación Kendall como

M/D/3

En todos los casos se supone que solo existe una sola línea de entrada.

Características de los sistemas de colas

Las características de operación del sistema que se pretenden determinar incluyen las
siguientes:
 La probabilidad de que no haya unidades en el sistema.
 El número promedio de unidades en la línea de espera.
 El número promedio de unidades en el sistema.
 El tiempo promedio que una unidad pasa en la línea de espera.
 El tiempo promedio que una unidad pasa en el sistema.
 La probabilidad de que las unidades que llegan tengan que esperar para ser atendidas.
 La probabilidad de que se esté utilizando la instalación de servicio.

3
Modelos o sistemas Poissonianos

En las situaciones cotidianas es fácil encontrar ejemplos de llegadas aleatorias. Las

llegadas serán aleatorias en cualquier caso en la que una de ellas no afecte a las otras. Un
ejemplo clásico de llegadas aleatorias son las llamadas que arriban a un conmutador telefónico o
un servicio de emergencia.
Se ha determinado que las ocurrencias aleatorias de un tipo especial pueden describirse a
través de una distribución discreta de probabilidad bien conocida como es la distribución de
Poisson.
e  x
P x   para _ x  0,1,2,3,4,...
x!
Siendo:
P(x) = Probabilidad de x arribos
x = número de arribos por unidad de tiempo
 = tasa promedio de arribo
e = 2.71828

Este tipo especial de llegadas aleatorias supone características acerca de la corriente de

entrada. En primer lugar, se supone que las llegadas son por completo independientes entre sí y
con respecto al estado del sistema. En segundo lugar, la probabilidad de llegada durante un
periodo específico no depende de cuando ocurre el periodo, sino más bien, depende solo de la
longitud del intervalo. Se dicen que estas ocurrencias carecen de "memoria".
Si conocemos el número promedio de ocurrencias por periodo, podemos calcular las
probabilidades acerca del número de eventos que ocurrirán en un periodo determinado, utilizando
las probabilidades conocidas de la distribución de Poisson.
Al igual que las llegadas aleatorias, la ocurrencia de tiempos de servicios aleatorios,
carentes de memoria, es suceso bastante común en las situaciones cotidianas de líneas de
espera. Y al igual que las llegadas aleatorias los tiempos de servicio carentes de memoria se
describen a través de una distribución de probabilidad.
La diferencia entre las llegadas aleatorias y los tiempos de servicio aleatorios es que estos
se describen a través de una distribución continua en tanto que las llegadas se describen a través
de una distribución de Poisson, que es discreta. Si la duración de los tiempos de servicio es
aleatoria, la distribución exponencial negativa describe ese tipo de servicio. Si la µ es la tasa
promedio de servicio entonces la distribución esta dada por:

F(t) = µ e-µt

Los modelos o sistemas Poissonianos se basan en las siguientes suposiciones:

 Llegadas con distribución Poisson.

 Tiempos de servicio con distribución exponencial negativa.
 Primer elemento que llega, primero que sale.

Para trabajar con estos modelos usaremos la siguiente nomenclatura:

: número promedio de llegadas por período de tiempo (tasa de arribo).

: número promedio de unidades que pueden ser atendidas por período de tiempo (tasa media de
servicio).
ts: tiempo que transcurre entre dos servicios sucesivos (tiempo de servicio). ts = 1/
tl: tiempo que transcurre entre dos llegadas sucesivos. tl = 1/

: factor de tráfico o factor de ocupación.  = /

 Si  > 1 la cola es infinita, existe estrangulamiento o cuello de botella (la instalación de

servicio no tiene suficiente capacidad para manejar las unidades que arriban).

4
  Si  = 1 el sistema es inestable ya que puede existir estrangulamiento.
 Si  < 1 la instalación de servicio tiene suficiente capacidad para manejar las unidades
que arriban.
Definimos entonces a s como el número de canales de atención, debiendo mantenerse la
condición:  / s = ( /) / s < 1

En la Tabla 1 se presentan las fórmulas para el cálculo de los parámetros.

Ejemplo: En un servidor de la universidad se procesan los correos que se reciben para los
miembros de la comunidad universitaria. Los correos llegan al servidor a una tasa de 100 por
minuto. El tiempo promedio de procesamiento de cada correo es de 0,5 segundos y tanto los
tiempos entre llegadas como los tiempos de ejecución se distribuyen exponencialmente.
1. ¿Qué proporción del tiempo está el servidor desocupado?
2. ¿Cuál es el tiempo total esperado de salida de un correo?
3. ¿Cuál es el número medio de correos esperando en la cola para ser procesados?

El sistema es M/M/1 con = 100 correos por minuto y = 120 correos por minuto.

Considerando la población infinita,  = / = 0,833 < 1 el sistema es estable.

1. Conocer qué proporción del tiempo el servidor esté desocupado equivale a calcular la
probabilidad de que no haya unidades en el sistema, es decir, P0 es:

P0 = 1- = 0,167 que representa un 16,67% del tiempo o 10 segundos cada

minuto.

2. El tiempo total esperado de salida de un correo es equivalente al tiempo promedio que

una unidad espera en el sistema, W s , es:

W s = 1/(-) = 0,5 minutos por correo.

3. El número medio de correos esperando en la cola para ser procesados es:

Lc =  /·(-) = 0,5 correos

2

5
Parámetros único canal s canales

Probabilidad de que las unidades que llegan tengan que 𝑠

 = /  𝑠
esperar para ser atendidas ∙ ∙ 𝑃0
𝑠! 𝑠−

Probabilidad de que no haya unidades en el sistema (P0) 1

1- = 1-/
𝑠 𝑛
𝑠.  𝑠−1 
+
𝑠! ∙ (𝑠 −  ) 𝑛=0 𝑛!

Probabilidad de que haya n unidades en el sistema (Pn) 𝑛

(1-). n . 𝑃0
𝑠! ∙ 𝑠 (𝑛−𝑠)

Probabilidad de que se esté utilizando la instalación de 1 - P0

servicio

Probabilidad de mas de k unidades dentro del sistema

k+1 𝑘 𝑘
P(n>k) ∙ ∙ 𝑃0
𝑘! 𝑘−

Número promedio de unidades en la línea de espera (Lc)

2  𝑠+1
= . 𝐿𝑠 ∙ 𝑃0
 . ( − ) (𝑠 − 1)! ∙ (𝑠 −  )2

Número promedio de unidades en el sistema (Ls)  𝐿𝑐 Lc + 

=
− 
Tiempo promedio que una unidad pasa en la línea de espera  𝐿𝑐 𝐿𝑐
(wc) = = 𝑤𝑠 . 
 . ( − )  

Tiempo promedio que una unidad pasa en el sistema (ws) 1 𝐿𝑠 1 𝐿𝑠

= = 𝑤𝑐 +
( − )   
Costo total del sistema Cs + Cw . Ls [Link] + Cw . Ls

Tabla 1: Fórmulas para el cálculo de parámetros en sistemas de colas

6
Para simplificar el uso de ecuaciones de múltiples canales, la tabla siguiente contiene
valores de Po para valores seleccionados de (/) y k.

Los valores que aparecen en la tabla siguiente corresponden a casos en los que k.> , y
por consiguiente la tasa de servicios es suficiente para procesar todas las llegadas.

(extraída del capítulo 15 del libro Métodos Cuantitativos para los Negocios – Anderson et al – 11° Edición, 2011)

7
Problemas

1. En una fábrica, un mecánico destinado al mantenimiento de las máquinas, atiende todos los
desperfectos que en ellas se presentan.
Se ha observado que la demanda de servicios sigue la ley Poisson con un parámetro  = 2,5
por hora, y que el mecánico atiende los pedidos con una velocidad  = 4,6 siguiendo un
riguroso orden de espera en fila.
Se pide:
a) Número promedio de máquinas en espera de ser atendidas y sin funcionar por
desperfectos. Rta.: Lc= 0.647 Ls= 1.1905
b) Tiempo promedio de despacho. Rta.: ts= 0.2175 h/maq.
c) Tiempo medio entre desperfectos. Rta.: tl= 0.4 h/maq.
d) Tiempo promedio de espera de las máquinas y tiempo promedio hasta que se reintegran.
Rta.: ws= 0.476 h/maq.; wc= 0.2588 h/maq.
e) Determinar si conviene pagar un incentivo al mecánico para que se eleve su rendimiento
del 90% al 120%. ¿Cuánto es dicho incentivo si la hora-hombre cuesta $200 y la hora-
máquina cuesta $500? Rta.: 250$/h

2. Frente a la ventanilla de franqueo de una oficina de correos se presentan 70 personas por día
(jornada de 10 horas). La ventanilla puede atender a 10 personas por hora. Con la hipótesis
de que las llegadas y salidas responden a procesos poissonianos, se pide determinar:
a) Longitud media de la cola frente a la ventanilla. Rta.: Lc= 1.633
b) Probabilidad de que exista una fila de más de 2 personas. Rta.: 0.343
c) Tiempo promedio de espera en el sistema y en la fila. Rta.: ws=0.333; wc=0.223h/p
d) Probabilidad de tener que esperar. Rta.: 0.7

3. En la sección expedición de una perfumería trabajan 5 empleados que embalan pedidos en

forma independiente a un promedio de 18 minutos por pedido. Las facturas necesarias para
controlar el pedido antes de proceder al embalado, son procesadas por un equipo contable
que las suministra a razón de 12 por hora.
Se desea saber:
a) Probabilidad de que no haya pedidos para embalar. Rta.: 0.0228
b) Número promedio de empleados trabajando. Rta.: 3.6
c) Tiempo de espera de cada pedido hasta que es embalado. Rta.: 5.312 minutos
d) Probabilidad de tener que esperar. Rta.: 0.412

4. En una fábrica se cumple una jornada de 16 horas (2 turnos). Al depósito de materiales

acuden término medio 100 operarios/hora con un salario promedio de 400$/hora. Cada
empleado del depósito atiende a un ritmo promedio de 60 pedidos de materiales por hora, y
cada uno de ellos tiene un salario de 250$/hora. Determinar el número de empleados
necesarios en el depósito para que el pago total por horas improductivas sea mínimo.
Rta.: se necesitan 3 canales de atención.

5. Un supermercado tiene en la actualidad 3 bocas de salida adyacentes, cada una de ellas con
un cajero. El número promedio de clientes por día es de 600, no habiendo horas de mayor
afluencia. El horario de atención al público es de 8 a 13 y de 14 a 19 horas; y el tiempo de
contabilización y cobro en cada boca de salida es de 2 minutos en promedio.
Se desea saber:
a) ¿Cuál es la probabilidad de que se forme cola?
b) ¿Cuánto será el tiempo promedio de espera de cada cliente?
c) ¿Cuántas bocas de salida adicionales había que habilitar en las horas de mayor afluencia
si el 60% del público concurre entre las 15 y las 19, y se desea que el tiempo de espera no
supere los 2 min?

Respuesta:
Si se admite que todos los clientes forman una misma cola al salir, cola simple con 3 canales.
a) 0.444; b) 0.89; c) una boca más.

8
 Si se forma una cola frente a cada salida con una equidistribución de clientes, 3 colas simples.
a) 0.66; b) 4; c) tres bocas más.

6. El departamento de investigación de operaciones de una universidad tiene dos líneas

telefónicas. Un promedio de 30 personas por hora trata de llamar al departamento, y la
longitud promedio de cada llamada es de 1 minuto. Si una persona trata de llamar cuando
ambas líneas están ocupadas, cuelga y se pierde del sistema. Suponer que el tiempo entre
las llamadas que tratan de comunicarse, así como los tiempos de servicio, son
exponenciales.
a) ¿Qué fracción del tiempo estarán libres ambas líneas? Rta.: 60%
b) ¿Qué fracción de tiempo están ocupadas las dos? Rta.: 10%
c) ¿Qué fracción de tiempo habrá desocupada exactamente una línea? Rta.: 30%

7. Supongamos que tenemos una CPU con 2 terminales conectados, y que de cada terminal
sólo puede recibir un trabajo a la vez, es decir que hasta que cada terminal no ha recibido
contestación de la CPU a su trabajo anterior, no inicia el proceso para enviar el siguiente
trabajo. De cada terminal activa (que no está esperando contestación de la CPU) se envía un
trabajo cada 4 minutos en promedio. Los tiempos entre envíos consecutivos siguen una
distribución exponencial. El tiempo de servicio promedio de la CPU es de 2 trabajos/minuto y
también sigue una distribución exponencial.
a) Calcular el nivel de ocupación de la CPU. Rta.: 12,5%
b) Calcular la probabilidad de que haya 0, 1 y 2 clientes en el sistema de colas de la CPU.
Rta.: 87,5%; 10,94%; 1,37%
c) Calcular el número medio de clientes en la CPU, y tiempo medio que pasan los clientes en
la cola de la CPU. Rta.: 0,1429 clientes; 0.0714 minuto

8. Sol y Playa es una cadena de hoteles que opera en el partido de la costa. La compañía utiliza
un número telefónico gratuito para hacer reservaciones en cualquiera de sus
establecimientos. El tiempo promedio para tomar cada llamada es de 3 minutos y se reciben
un promedio de 12 llamadas cada hora. No se conoce la distribución de probabilidad que
describe las llegadas. Después de cierto tiempo se determina que la persona que llama
emplea 7.5 minutos, entre la espera y el proceso de recibir el servicio. Encuentre:
a) el tiempo promedio que pasa en la cola, Rta: 0,075 horas
b) el tiempo promedio en el sistema, Rta: 0,125 horas
c) el número promedio en la cola y Rta: 0,90
d) el número promedio en el sistema. Rta: 1,50

9
10