TEORÍA DE COLAS

introducción

El origen de la Teoría de Colas está en el esfuerzo de Agner Krarup Erlang (Dinamarca, 1878 - 1929) en 1909 para analizar la congestión de tráfico telefónico con el objetivo de cumplir la demanda incierta de servicios en el sistema telefónico de Copenhague. Sus investigaciones acabaron en una nueva teoría llamada teoría de colas o de líneas de espera. Esta teoría es ahora una herramienta de valor en negocios debido a que muchos de sus problemas pueden caracterizarse, como problemas de congestión llegada - partida. Una Cola es una línea de espera y la teoría de colas es una colección de modelos matemáticos que describen sistemas de líneas de espera particulares o de sistemas de colas. Los modelos sirven para encontrar un buen compromiso entre costes del sistema y los tiempos promedio de la línea de espera para un sistema dado. El problema es determinar que capacidad o tasa de servicio proporciona el balance correcto. Esto no es sencillo, ya que un cliente no llega a un horario fijo, es decir, no se sabe con exactitud en que momento llegarán los clientes. También el tiempo de servicio no tiene un horario fijo. Los problemas de “Colas” se presentan permanentemente la vida diaria: un estudio de EE.UU. concluyó que un ciudadano medio pasa 5 años de su vida esperando en distintas Colas, y de ellos casi 6 meses parado en los semáforos.

Problemas típicos de Teoría de Colas son:

DEFINICIÓN Teoría de Colas es el estudio matemático del comportamiento de líneas de espera. Estas se presentan cuando "clientes" llegan a un "lugar" demandando un servicio a un "servidor" el cual tiene cierta capacidad de atención. Si el servidor no está disponible inmediatamente y el cliente decide esperar, entonces se forma en la línea de espera.

CONCEPTOS BÁSICOS Clientes: Término usado en un sistema de colas para referirse a: · Gente esperando líneas telefónicas desocupadas. · Máquinas que esperan ser reparadas. · Aviones esperando aterrizar. Instalaciones de Servicio: Este término se usa para referirse a:

· Líneas telefónicas. · Talleres de reparación. · Pistas de aeropuerto. Llegadas: Es el número de clientes que llegan a las instalaciones de servicio. Tasa de Servicio: Este término se usa para designar la capacidad de servicio, por ejemplo:

· Un sistema telefónico entre dos ciudades puede manejar 90 llamadas por minuto. · Una instalación de reparación puede de media, reparar máquinas a razón una cada 8 horas. · Una pista de aeropuerto en la que aterrizan dos aviones por minuto. Número de servidores de servicio: Es la cantidad de servidores de que disponemos: · Número de conmutadores telefónicos. · Número de puestos de reparación. · Número de pistas de aterrizaje de un aeropuerto. El número de servidores no tiene porqué ser siempre en paralelo, es decir, puede que un sistema de colas tenga varias fases.

COSTES ASOCIADOS A UN SISTEMA DE COLAS ¿Por qué es necesario contar con herramientas de optimización para los problemas de Colas? Normalmente en cualquiera de estos sistemas existen dos tipos de costes: a) Los costes asociados a la espera de los clientes Por ejemplo, el valor del tiempo perdido o la gasolina malgastada en los atascos o los semáforos. Lo normal es pensar que estos costes de espera decrecen conforme aumenta la capacidad de servicio del sistema. b) Los costes asociados a la expansión de la capacidad de servicio

Contra la reducción anterior de costes de espera, es también normal que el coste asociado a incrementar la capacidad de servicio crezca con alguna proporcionalidad en relación a esta capacidad. c) Los costes totales del sistema de servicio La suma de los dos costes anteriores da una función de costes totales del sistema en función de la capacidad, que tendrá una forma similar a la siguiente:

OBJETIVOS DE LA TEORÍA DE COLAS

Dada la función de costes anterior, los objetivos de la Teoría de Colas consisten en: · Identificar el nivel óptimo de capacidad del sistema que minimiza el coste global del mismo. · Evaluar el impacto que las posibles alternativas de modificación de la capacidad del sistema tendrían en el coste total del mismo. · Establecer un balance equilibrado (“óptimo”) entre las consideraciones cuantitativas de costes y las cualitativas de servicio. Hay que prestar atención al tiempo de permanencia en el sistema o en la Cola: la “paciencia” de los clientes depende del tipo de servicio específico considerado y eso puede hacer que un cliente “abandone” el sistema. TIPOS DE COLAS Según el tipo de sistema de colas, tenemos varios tipos de éstas, las cuales son: a) Una línea, un servidor

El primer sistema que se muestra se llama un sistema de un servidor y una cola o puede describir una consulta de un médico. b) Una línea, múltiples servidores El segundo, una línea con múltiples servidores, es típico de una peluquería o una panadería en donde los clientes toman un número al entrar y se les sirve cuando les llega el turno. c) Varias líneas, múltiples servidores El tercer sistema, en que cada servidor tiene una línea separada, es característico de los bancos y las tiendas de autoservicio. Para este tipo de servicio pueden separarse los servidores y tratarlos como sistemas independientes de un servidor y una cola. Esto sería válido sólo si hubiera muy pocos intercambios entre las colas.

Cuando el intercambio es sencillo y ocurre con frecuencia, como dentro de un banco, la separación no sería válida.

LA DISTRIBUCIÓN DE POISSON

Esta distribución es muy frecuente en los problemas relacionados con la investigación operativa, sobre todo en el área de la gestión de colas. Suele describir, por ejemplo, la llegada de pacientes a un ambulatorio, las llamadas a una central telefónica, la llegada de coches a un túnel de lavado, etc. Todos estos casos pueden ser descritos por una variable aleatoria discreta que tiene valores no-negativos enteros. LA DISTRIBUCIÓN EXPONENCIAL

La distribución de Poisson describe las llegadas por unidad de tiempo y la distribución exponencial estudia el tiempo entre cada una de estas llegadas. Si las llegadas son de Poisson, el tiempo entre ellas es exponencial. La distribución de Poisson es discreta, mientras que la distribución exponencial es continua, porque el tiempo entre llegadas no tiene por qué ser un número entero. Esta distribución se usa mucho para describir el tiempo entre eventos, específicamente, la variable aleatoria que representa el tiempo necesario para servir a la llegada. Un ejemplo típico puede ser el tiempo que un médico dedica a un paciente. CURIOSIDADES 1ª Ley de Harper: No importa en qué cola se sitúe: La otra siempre avanzará más rápido. 2ª Ley de Harper: Y si se cambia de cola, aquélla en que estaba al principio empezará a ir

más deprisa.

Medidas del sistema Existen dos tipos de medidas para poder valorar un sistema en donde pueden aparecer colas: medidas “duras” y medidas “blandas”. Estas últimas están relacionadas con la calidad del servicio. Por ejemplo, no es lo mismo esperar 15 minutos de pie haciendo cola en un ambulatorio sin refrigeración y poco ventilado que esperar el mismo tiempo en una sala de espera con butacas confortables, revistas, aire acondicionado y música clásica de fondo. El paciente valorará mucho más 1 minuto de espera en el primer caso ya que representa un coste mucho más elevado en términos de confort. En otras palabras, seguramente un minuto de cola en el ambulatorio equivale a muchos minutos de espera en la sala de espera confortable. La gestión cuantitativa de las colas no se ocupa de estos aspectos cualitativos (que no por ello dejan de ser importantes) sino que da valores a una serie de medidas “frías” o “duras”. Las medidas duras más utilizadas en los modelos de gestión de colas y su notación estándar son las siguientes: • Número medio de personas en la cola, Lq • Número medio de personas en el sistema, Ls • Tiempo medio de espera en la cola, Wq • Tiempo medio de estancia en el sistema, Ws • Número medio de personas en la cola, Lq • Número medio de personas en el sistema, Ws • Porcentaje de ocupación de los servidores, Pw • Probabilidad de que hayan x personas en el sistema, Px

MODELO DE COLAS SIMPLE: LLEGADAS EN POISSON Y TIEMPOS DE SERVICIO EXPONENCIALMENTE DISTRIBUIDOS.

El modelo que presentaremos a continuación tiene que cumplir las condiciones siguientes: 1. El número de legadas por unidad de tiempo sigue una distribución de Poisson 2. Los tiempos de servicio siguen una distribución exponencial 3. La disciplina de la cola es de tipo FIFO 4. La población potencial es infinita 5. Existe un único canal de servicio 6. La tasa media de llegadas es menor que la tasa media del servicio 7. El tamaño potencial de la cola es infinito Si estas condiciones se cumplen y si conocemos la tasa media de llegada λ, y la tasa media de servicio μ, las ecuaciones para obtener valores de las medidas descritas anteriormente son: Probabilidad de que no existan unidades en el sistema:

Po= 1-(λ/µ) Probabilidad de n unidades en el sistema:

Pn=( λ/µ)n

*Po

Número medio en la cola:

Número medio en el sistema:

Tiempo medio de espera en la cola:

Tiempo medio en el sistema:

Factor de utilización:

Un ejemplo Suponga un negocio de comidas rápidas en el cual los clientes llegan a hacer su pedido y

existe en el momento un único empleado que acepta el dinero del cliente y surte su pedido,

para luego continuar con el siguiente cliente.

Asuma que los clientes llegan a este negocio a una tasa de 45 por hora y el empleado procesa

las ordenes a una tasa de 60 por hora.

Determine las métricas del sistema.

MODELO MÚLTIPLE DE COLAS: LLEGADAS EN POISSON Y TIEMPOS DE SERVICIO EXPONENCIALMENTE DISTRIBUIDOS. En muchos casos podemos tener situaciones en donde existe más de un servidor en el sistema. A medida que van llegando los clientes, los servidores se van ocupando y cada vez que uno de ellos acaba su servicio, el primero de la cola lo vuelve a ocupar. El sistema está representado en la Figura 6.6

En este tipo de modelos la tasa de llegada siempre tiene que ser inferior a la tasa agregada de servicio, que no es más que la tasa de servicio individual multiplicada por el número de canales. En este modelo se supone, además de las condiciones expuestas anteriormente, que la tasa individual de cada canal es la misma. Las expresiones matemáticas para la obtención de las medidas de eficiencia del sistema dependen de P0 que es la probabilidad de que no haya nadie en el sistema (cola más servicio).

*Sµ/(kµ-λ)

Tiempo medio en el sistema

W= Wq+(1/µ)

Probabilidad de que una unidad que llega tenga que esperar por servicio:

Pw=(1/s!)(λ/µ)s (sµ/(sµ-λ))*Po

Probabilidad de que existan n unidades en el sistema

Pn=((λ/µ)n /n!)*Po para n<=s

Pn=((λ/µ)n /s!*s(n-s))*Po para n>s

Ejemplo Suponga que para la situación del anterior restaurante la administración esta interesada en

evaluar la conveniencia de abrir una segunda estación de pedidos de manera que se pueda

atender simultáneamente a dos clientes.

Algunas relaciones de tipo general para los modelos de líneas de espera

John Little demostró que existe una relación importante entre las siguientes métricas:

Lq, L, Wq, W las cuales se muestran a continuación:

L=λ*W Lq= λ*Wq

Notación de kendall

David G. Kendall introdujo una notación de colas A/B/C en 1953 para describir las colas y sus características. Esta ha sido desde entonces extendida a 1/2/3/(4/5/6) donde los números se

reemplazan con:

1. Un código que describe el proceso de llegada. Los códigos usados son: o M para "Markoviano" (la tasa de llegadas sigue una distribución de Poisson),

significando una distribución exponencial para los tiempos entre llegadas. o D para unos tiempos entre llegadas "determinísticas". o G para una "distribución general" de los tiempos entre llegadas, o del régimen de

llegadas. 2. Un código similar que representa el proceso de servicio (tiempo de servicio). Se usan

los mismos símbolos. 3. El número de canales de servicio (o servidores). 4. La capacidad del sistema, o el número máximo de clientes permitidos en el sistema

incluyendo esos en servicio. 5. El orden de prioridad en la que los trabajos en la cola son servidos:

o First Come First Served (FCFS) ó First In First Out (FIFO) , o Last Come First Served (LCFS) o Last In First Out (LIFO) ,

6. El tamaño de la población desde donde los clientes vienen.

MODELO M / G / 1

Sistema de líneas de espera con llegadas aleatorias, distribución general de los tiempos de servicio (para el cual se supone conocida la desviación estándar), un canal de servicio y

una línea de espera.

En este modelo las llegadas se distribuyen de acuerdo con la distribución de Poisson, al igual a los casos anteriores, pero los tiempos de servicio no necesariamente se distribuyen de acuerdo con la distribución exponencial. Si consideramos el caso en que solo existe un solo canal, estamos considerando el caso M / G / 1, es decir, llegadas de tipo Markov,

tiempo de servicio general y un canal de servicio.

La razón por la que podemos considerar el caso M / G / 1 es que las formulas que se utilizan para calcular sus características de operación son bastantes simples.

Ahora si conocemos la desviación estándar y la media de la distribución de los tiempos de

servicio, puede obtenerse formula para el valor de Lq a partir de la siguiente ecuación.

Si utilizamos Lq podemos determinar el valor de L, por medio de la siguiente ecuación:

Al igual que las características de operación de los modelos M / M / 1 y M / S / 1, podemos calcular el tiempo esperado en el sistema de líneas de espera (W), y el tiempo que se invierte antes de ser atendido (Wq), esto lo podemos realizar por medio de las siguientes ecuaciones:

W=Wq+(1/µ)

Probabilidad de que no existan unidades en el sistema

Po=1-(λ/µ)

Probabilidad de que una unidad que llegue deba esperar

Pw=(λ/µ)

Ejemplo

Un solo empleado maneja las ventas al menudeo en pepe´s seafood supply. Las llegadas de

los clientes son aleatorias y la tasa promedio de llegadas es de 21 clientes por hora, un estudio

del proceso de servicio muestra que l tiempo promedio de servicio es de 2 minutos por cliente

con una desviación estándar de 1.2 minutos. Calcule las métricas de este sistema.

Otros ejemplos

1. La mesa de consultas de una biblioteca recibe solicitudes de ayuda. Suponga que se

puede utilizar una distribución de poisson con una tasa media de 10 solicitudes por

hora y que los tiempos de servicio se distribuyen exponencialmente con una media de

12 solicitudes por hora.

Cual es la probabilidad de que no haya ninguna solicitud de ayuda en el sistema

Cual es el numero promedio de solicitudes esperando el servicio

Cual es el tiempo de espera promedio antes de que inicie el servicio

Cual es la probabilidad de que una nueva solicitud no sea atendida inmediatamente.

2. Agan interior design proporciona a sus clientes asistencia de decoración domestica y

de oficinas. en operación normal llegan un promedio de 2.5 clientes todas las horas. Un

asesor esta disponible para responder las preguntas de los clientes, tomandole esto en

promedio 10 minutos por cada cliente.

Calcule las características de operación de la línea de espera (suponga llegadas

poisson y servicio exponencial)

Las metas de servicio indican que un cliente no debe esperar mas de 5 minutos para

que le atiendan. Se esta cumpliendo esta meta?

Si el asesor puede reducir el tiempo de servicio hasta a 8 minutos, se cumplirá la meta

establecida?

3. Considere una línea de espera de dos canales con llegadas poisson y servicio

exponencial. La tasa media de llegadas es de 14 unidades por hora y la tasa media de

servicio es de 10 unidades por hora en cada uno de los dos canales:

Cuál es la probabilidad de que no haya ninguna unidad en el sistema

Cuál es el numero promedio de unidades en el sistema

Cuál es el tiempo promedio que una unidad esperara para que le den servicio

Cuál es el tiempo promedio que una unidad estará en el sistema

Cuál es la probabilidad que se tenga que esperar para obtener servicio

4. refiérase al problema 2 en el cual la administración desea evaluar dos alternativas:

Utilizar un asesor de tiempo promedio de servicio de 8 minutos por cliente

Ampliar a dos asesores, cada uno de los cuales tendrá un tiempo promedio de servicio de 10

minutos por cliente.

Si se les paga 16 dólares la hora a los asesores y el tiempo de espera de los clientes se evalúa

en 25 dólares la hora. Cual sería la mejor opción?