Teoría de Colas

Introducción 
Todos hemos experimentado en alguna ocasión la sensación de estar perdiendo el tiempo al esperar en una cola. El fenómeno de las colas nos parece natural: esperamos en el coche al estar en un tapón, o un semáforo mal regulado, o en un peaje; esperamos en el teléfono a que nos atienda un operador y en la cola de un supermercado para pagar....

Como clientes no queremos esperar, los gestores de los citados servicios no quieren que esperemos.... ¿Por qué hay que esperar?

La respuesta es casi siempre simple, en algún momento la capacidad de servicio ha sido (o es) menor que la capacidad demandada.

Generalmente esta limitación se puede eliminar invirtiendo en elementos que aumenten la capacidad.

En estos casos la pregunta es: ¿Compensa invertir?
La teoría de colas intenta responder a estas preguntas utilizando análisis matemáticos detallados.

Descripción de un problema de colas
Un sistema de colas se puede describir como: “clientes” que llegan buscando un servicio, esperan si este no es inmediato, y abandonan el sistema una vez han sido atendidos. En algunos casos se puede admitir que los clientes abandonan el sistema si se cansan de esperar.

El término “cliente” se usa con un sentido general y no implica que sea un ser humano, puede significar piezas esperando su turno para ser procesadas o una lista de trabajo esperando para imprimir en una impresora en red.

image

Aunque cualquier sistema se puede representar como en la figura 1, debe quedar claro que una representación detallada exige definir un número elevado de parámetros y funciones.
La teoría de colas fue originariamente un trabajo práctico. La primera aplicación de la que se tiene noticia es del matemático danés Erlang sobre conversaciones telefónicas en 1909, para el cálculo de tamaño de centralitas. Después se convirtió en un concepto teórico que consiguió un gran desarrollo, y desde hace unos años se vuelve a hablar de un concepto aplicado aunque exige un importante trabajo de análisis para convertir las fórmulas en realidades, o viceversa.


Características de los sistemas de colas
Seis son las características básicas que se deben utilizar para describir adecuadamente un sistema de colas:
a) Patrón de llegada de los clientes
b) Patrón de servicio de los servidores
c) Disciplina de cola
d) Capacidad del sistema
e) Número de canales de servicio
f) Número de etapas de servicio
Algunos autores incluyen una séptima característica que es la población de posibles clientes.

Patrón de llegada de los clientes
En situaciones de cola habituales, la llegada es estocástica, es decir la llegada depende de una cierta variable aleatoria, en este caso es necesario conocer la distribución probabilística entre dos llegadas de cliente sucesivas. Además habría que tener en cuenta si los clientes llegan independiente o simultáneamente. En este segundo caso (es decir, si llegan lotes) habría que definir la distribución probabilística de éstos.

También es posible que los clientes sean “impacientes”. Es decir, que lleguen a la cola y si es demasiado larga se vayan, o que tras esperar mucho rato en la cola decidan abandonar.
Por último es posible que el patrón de llegada varíe con el tiempo. Si se mantiene constante le llamamos estacionario, si por ejemplo varía con las horas del día es no-estacionario.

Patrones de servicio de los servidores
Los servidores pueden tener un tiempo de servicio variable, en cuyo caso hay que asociarle, para definirlo, una función de probabilidad. También pueden atender en lotes o de modo individual.

El tiempo de servicio también puede variar con el número de clientes en la cola, trabajando más rápido o más lento, y en este caso se llama patrones de servicio dependientes. Al igual que el patrón de llegadas el patrón de servicio puede ser no-estacionario, variando con el tiempo transcurrido.


Disciplina de cola 

La disciplina de cola es la manera en que los clientes se ordenan en el momento de ser servidos de entre los de la cola. Cuando se piensa en colas se admite que la disciplina de cola normal es FIFO (atender primero a quien llegó primero) Sin embargo en muchas colas es habitual el uso de la disciplina LIFO (atender primero al último). También es posible encontrar reglas de secuencia con prioridades, como por ejemplo secuenciar primero las tareas con menor duración o según tipos de clientes.

En cualquier caso dos son las situaciones generales en las que trabajar. En la primera, llamada en inglés “preemptive”, si un cliente llega a la cola con una orden de prioridad superior al cliente que está siendo atendido, este se retira dando paso al más importante. Dos nuevos subcasos aparecen: el cliente retirado ha de volver a empezar, o el cliente retorna donde se había quedado. La segunda situación es la denominada “no-preemptive” donde el cliente con mayor prioridad espera a que acabe el que está siendo atendido.

Capacidad del sistema
En algunos sistemas existe una limitación respecto al número de clientes que pueden esperar en la cola. A estos casos se les denomina situaciones de cola finitas. Esta limitación puede ser considerada como una simplificación en la modelización de la impaciencia de los clientes.

Número de canales del servicio
Es evidente que es preferible utilizar sistemas multiservidos con una única línea de espera para todos que con una cola por servidor. Por tanto, cuando se habla de canales de servicio paralelos, se habla generalmente de una cola que alimenta a varios servidores mientras que el caso de colas independientes se asemeja a múltiples sistemas con sólo un servidor.
En la figura 1 se dibujó un sistema mono-canal, en la figura 2 se presenta dos variantes de sistema multicanal. El primero tiene una sola cola de espera, mientras que el segundo tiene una sola cola para cada canal
TOC1
Se asume que en cualquiera de los dos casos, los mecanismos de servicio operan de manera independiente.

Etapas de servicio
Un sistema de colas puede ser unietapa o multietapa. En los sistemas multietapa el cliente puede pasar por un número de etapas mayor que uno. Una peluquería es un sistema unietapa, salvo que haya diferentes servicios (manicura, maquillaje) y cada uno de estos servicios sea desarrollado por un servidor diferente.
En algunos sistemas multietapa se puede admitir la vuelta atrás o “reciclado”, esto es habitual en sistemas productivos como controles de calidad y reprocesos.


image

Con el paso del tiempo se ha implantado una notación para representar los problemas de colas que consta de 5 símbolos separados por barras.
A / B / X /Y / Z
A: indica la distribución de tiempo entre llegadas consecutivas
B: alude al patrón de servicio de servidores
X: es el número de canales de servicio
Y: es la restricción en la capacidad del sistema
Z: es la disciplina de cola
tocvv
El símbolo G representa una distribución general de probabilidad, es decir, que el modelo presentado y sus resultados son aplicables a cualquier distribución estadística (siempre que sean Variables IID- Independientes e Idénticamente Distribuidas).
Si no existe restricción de capacidad (Y = ∞) y la política de servicio es FIFO, no se suelen incorporar dichos símbolos en la notación así:
M/D/3 es equivalente a M/D/3/∞/FIFO y significa que los clientes entran según una distribución exponencial, se sirven de manera determinista con tres servidores sin limitación de capacidad en es sistema y siguiendo una estrategia FIFO de servicio.
La notación anteriormente representada, por general, deja demasiados casos por resolver, pero
es suficiente para los casos más importantes.

Cómo medir el rendimiento de un sistema
La tarea de un analista de colas puede ser de dos tipo: a) establecer mecanismos para medir la efectividad del sistema o b) diseñar un sistema “óptimo” (de acuerdo a algún criterio).
Diseñar eficientemente consiste, básicamente, en definir un sistema cuyo coste (de diseño y de operación) se justifique por el servicio que da. Dicho servicio se puede evaluar mediante el coste de “no darlo”. De este modo al diseñar se pretende minimizar unos supuestos costes totales. 
A partir de los datos que nos suministra la teoría de colas se puede obtener la información necesaria para definir el número de asientos necesarios en una sala de espera, o la estructura de etapas de un proceso de atención al cliente.
En cualquier caso, para poder tomar decisiones hacen falta datos que la teoría de colas puede dar en alguno de los siguientes tres aspectos:
a) tiempo de espera (en el total del sistema o en la cola)
b) cantidad de clientes esperando (en el sistema o en las colas)
c) tiempo ocioso de los servidores (total o particular de cada servicio)

NOMENCLATURA BÁSICA
Antes de presentar los resultados es necesario establecer una notación básica:
tocnomen

Resultados y relaciones
Si ρ≥1 el sistema tenderá a crecer inexorablemente.
El número de clientes en el instante t, n(t), es el número de llegadas que han ocurrido hasta t
menos el número de servicios completados hasta t.
El número medio de clientes en el sistema y en la cola se puede calcular de diferentes maneras:
tocfor









Little, en su famosa fórmula, establece una relación entre la longitud de la cola y el tiempo de
espera:
tocfrr
El tiempo de estancia de un cliente en el sistema se relaciona con el tiempo de espera de un
cliente en la cola,
tocfrr2
El número de clientes que por término medio se están atendiendo en cualquier momento es:
for1
En un sistema de un único servidor:
for2
La probabilidad de que un sistema de un único servidor esté vacío es p0=1-ρ
La probabilidad de que un servidor (de un sistema de c servidores en paralelo) esté ocupado en
el estado estable es:
for3
El tiempo de estancia del cliente (i+1) en la cola es:
1f
donde S(i) es el tiempo de servicio del cliente i, y T(i) es el tiempo que transcurre desde la
llegada del cliente y hasta la llegada del cliente (i+1)


Como recoger datos en un sistema de colas
A priori se puede pensar que el método más adecuado para recoger datos al analizar un sistema
es establecer una plantilla y recoger los datos sobre el sistema cada cierto tiempo. Esta técnica es
“orientada al tiempo”
Es mejor, sin embargo, utilizar una técnica de recogida de información asociada a eventos.
“La información se recoge cuando algo ocurre”
En una cola convencional los únicos datos a recoger son:
a) cada cuánto llega un cliente
b) cuánto se tarda en servir a cada cliente
No es necesario recoger más información para, a partir de las relaciones expuestas en el
apartado anterior, definir cualquier medida de efectividad.

Ejemplo
Sea un sistema G/G/1. Sean los siguientes datos de entrada:
image
De la tabla anterior se puede extraer la siguiente información:
image
image
A partir de la anterior información obtenida se puede decir que:
image
image
image
image

DISTRIBUCIÓN DE LAS LLEGADAS
La distribución del proceso de las llegadas para una línea de espera involucra determinar la distribución de probabilidades del numero de llegadas en un periodo dado
Las llegadas ocurren de manera aleatoria e independientes
Distribución de probabilidad poisson da una buena descripción del patrón de llegada
clip_image002 Para X=0,1,2,3…
X= Número de llegadas en el periodo
λ= Promedio o número medio de llegadas por periodo
e= 2,71828

DISTRIBUCIÓN DE LOS TIEMPOS DE SERVICIO
El tiempo de servicio es aquel que pasa un cliente en la instalación de servicio una vez que este se ha iniciado
Los tiempos de servicio son rara vez constantes
Los tiempos de servicio siguen una distribución de probabilidad exponencial
La probabilidad de que el tiempo de servicio sea menor o igual a un tiempo de duración t es:
clip_image002[5]
µ= Promedio o número medio de unidades que pueden atenderse por periodo

HIPÓTESIS:
  • La línea de espera tiene un solo canal
  • Las llegadas, siguen una distribución de probabilidad poisson
  • Los tiempos de servicio siguen una distribución de probabilidad exponencial
  • La disciplina en la cola es, primera llegada, primer servicio
FORMULAS para desarrollar las características de operación en estado estable de una línea de espera de un solo canal, aplicables solo cuando µ>λ
  • Factor de utilización clip_image002[19]
  1. Probabilidad de que no existan unidades en el sistema clip_image002
  2. Número promedio de unidades en la línea de espera clip_image002[5]
  3. Número promedio de unidades en el sistema clip_image002[1]
  4. Tiempo promedio que utiliza la unidad en la línea de espera clip_image002[3]
  5. Tiempo promedio que una unidad ocupa en el sistema clip_image002[5]
  6. Probabilidad de que una unidad que llega tiene que esperar servicio clip_image002[7]
  7. Probabilidad de que el sistema este n unidades  clip_image002[15]


(M/M/K) MODELO DE LINEA DE ESPERA DE MÚLTIPLES CANALES CON LLEGADAS POISSON Y TIEMPOS DE SERVICIO EXPONENCIAL

Una línea de espera de canales múltiples, esta formada de dos o mas canales o localización de servicio, que se suponen idénticos en función de su capacidad de servicio. En el sistema de canales múltiples, las unidades de llegada esperan es una sola línea de espera que a continuación pasan al primer canal disponible para ser atendido
Características de operación en estado estable para una línea de espera de canal múltiple
  • La línea de espera tenga dos o mas canales
  • Las llegadas siguen una distribución de probabilidad poisson
  • El tiempo de servicio de cada canal sigue una distribución de probabilidad exponencial
  • La tasa media de servicio µ es la misma para cada uno de los canales
  • Las llegadas esperan en una sola línea de espera y entonces pasan al primer canal abierto para su servicio
  • La disciplina de la cola es PEPS(Primero en entrar, primero en salir)

FORMULAS, solo aplicables cuando: Kµ>λ
λ= Tasa media de llegadas del sistema
µ= Tasa media de servicio de cada canal
K= Número de canales

  1. Probabilidad de que no exista unidades en el sistema clip_image002[9]
  2. Número promedio de unidades en la línea de espera clip_image002[11]
  3. Número promedio de unidades en el sistema clip_image002[13]
  4. Tiempo promedio que ocupa una unidad en la línea de espera clip_image002[15]
  5. Tiempo promedio que una unidad ocupa en todo el sistema clip_image002[17] 
  6. Probabilidad que existan n unidades en el sistema
        clip_image002[31]
                                                                                 clip_image002[33]






    λ= Tasa de llegada
    1/λ= Tiempo promedio entre llegadas
    µ= Tasa de servicio
    1/µ= Tiempo promedio de servicio

    VÍDEOS Y EJERCICIOS PROPUESTOS











    Vídeos descargados de You Tube


    EJERCICIO PROPUESTO

    Una franquicia de comidas rápidas está considerando operar una operación de ventanilla para automóviles de servicio de alimentos. Suponga que las llegadas de los clientes siguen una distribución de probabilidad de Poisson, con una tasa media de llegadas de 24 automóviles por hora y que los tiempos de servicio siguen una distribución de probabilidad exponencial. Los clientes que llegan colocan sus pedidos en una estación de intercomunicación en la parte trasera del estacionamiento y a continuación conducen hasta la ventanilla de servicio para pagar y recibir sus compras.
    El tiempo de espera del cliente se evalúa en 25 dólares la hora, para reflejar el hecho de que el negocio de las comidas rápidas el tiempo de espera es costoso; el costo de cada empleado es de 6,50 dólares la hora; al tomar en consideración espacio y equipo, se le asigna un costo adicional de 20 dólares la hora a cada uno de los canales.
    ¿Cuál es el diseño del negocio de comida rápida con un costo más bajo?
    .λ=24
    .µ=30
    .Cs= 6,50
    .Cw=25

    ejerrrrr









    Referencia:
    “Fundamentals of Queueing Theory” por Donald Gross y Carl Harris