LÍNEAS DE ESPERA

UNIDAD 5: SISTEMA DE COLAS O LÍNEAS DE ESPERA

INTRODUCCIÓN

Una línea de espera es el efecto resultante en un sistema cuando la demanda de un servicio supera la capacidad de proporcionar dicho servicio. Este sistema está formado por un conjunto de entidades en paralelo que proporcionan un servicio a las transacciones que aleatoriamente entran al sistema. Dependiendo del sistema que se trate, las entidades pueden ser cajeras, máquinas, semáforos, grúas, etcétera, mientras que las transacciones pueden ser: clientes, piezas, autos, barcos, etcétera. Tanto el tiempo de servicio como las entradas al sistema son fenómenos que generalmente tienen asociadas fuentes de variación que se encuentran fuera del control del tomador de decisiones, de tal forma que se hace necesaria la utilización de modelos estocásticos que permitan el estudio de este tipo de sistemas.

Una línea de espera puede moderarse 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,... N} y cada uno de ellos tiene asociada una probabilidad de ocurrencia {P0, P1, P2,... PN} -

OBJETIVO

En las líneas de espera, existen dos costos perfectamente identificados: el costo de las transacciones, que representa la cuantificación monetaria de la pérdida de tiempo al esperar recibir un servicio o la pérdida de clientes por abandono del sistema, y el costo de proporcionar el servicio, que representa la cantidad de dinero que hay que pagar por cuestión de sueldos y salarios, energía, mantenimiento y depreciación del personal o equipo.

De tal forma que en un estudio de líneas de espera el objetivo es determinar qué nivel de servicio, ya sea por cantidad de entidades o por la velocidad de ella, proporcionar para minimizar el costo total del sistema. Este costo está formado tanto por costo de servicio como por el que causa la espera. Matemáticamente podemos representarlo de la siguiente forma:

Min Ct = CeS + CqLq

Sujeto a

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 espera por transacción - tiempo.

Ct costo total por unidad de tiempo.

Estos conceptos se pueden representar gráficamente de acuerdo con el esquema mostrado en el siguiente gráfico:

ESTRUCTURA

Un sistema de espera se representa mediante la llegada de transacciones a un sistema con el fin de recibir un servicio por cualquiera de una o más entidades dispuestas para ello, conocidas como servidores. En caso de que todas las entidades se encuentren ocupadas, la transacción permanece en espera en la fila hasta que decide abandonar la fila sin ser atendido, o bien, es seleccionado de acuerdo con cierta regla para recibir atención. Una vez que el servicio ha sido completamente proporcionado, la transacción sale del sistema y se convierte de nuevo en una transacción potencial.

Servidores

Representan al mecanismo por el cual las transacciones reciben de una manera completa el servicio deseado. Estas entidades se encuentran dispuestas en forma paralela a la fila, de tal manera que las transacciones pueden seleccionar a cualquiera de ellas para el suministro de dicho servicio. Las dos características principales de los servidores son: la cantidad asignada por cada fila existente en el sistema y la distribución de probabilidad del tiempo de atención a las transacciones o de la Velocidad de servicio; dentro de las distribuciones más comunes están la exponencial, la Erlang, la hiperexponencial, la degenerada.

Transacciones potenciales

Representan el número total de clientes que podrían requerir el servicio proporcionado por el sistema y es necesario definir dos características para este conjunto de elementos; la primera tiene que ver con el tamaño del conjunto potencial de clientes, dando, en consecuencia, conjuntos limitados o finitos y en otros casos conjuntos ilimitados o infinitos. La segunda característica se refiere a la distribución de probabilidad del tiempo entre llegadas o bien a la tasa de entrada promedio. Es común encontrarse la suposición de tasas de llegada que siguen un proceso Poisson, el cual ocurre cuando las llegadas a un sistema se llevan a cabo de forma aleatoria; es importante hacer notar que una de las propiedades de esta distribución es su relación con el tiempo entre llegadas consecutivas, que se representa en forma paralela, de acuerdo con un proceso de tipo exponencial. Existen algunos sistemas donde la tasa de llegadas se ve afectada por la decisión de una transacción de rehusar su entrada al sistema Por razones diversas, por ejemplo del tamaño de la fila. En el caso en que un elemento sale de una cola, usualmente por su longitud, suele llamárselo Balked (resistirse, fracaso).

Fila

Es el conjunto de transacciones que espera ser atendido por alguno de los servidores del sistema. Una fila tiene tres características principales, la primera, se refiere a la capacidad, o sea, al número máximo de transacciones que pueden permanecer en ella en un mismo instante y de acuerdo con este número se clasifican como finitas o infinitas. Hay que hacer notar que en el caso de los modelos de tamaño finito, la solución es mucho más fácil de encontrar a partir de las ecuaciones generales ya que la solución del modelo se reduce a un sistema de ecuaciones simultáneas y a la evaluación de las medidas de desempeño mediante promedios ponderados, mientras que, en el caso de modelos de tipo ilimitado o infinito, es necesario recurrir a la solución del sistema de ecuaciones así como a la evaluación de las medidas de desempeño y a algunas series geométricas que dificultan en cierto grado el manejo algebraico de la solución. La segunda característica es el orden en que las transacciones son extraídas de la fila para su atención, en ese caso podemos encontrar: primeras llegadas, primeros servicios, por prioridad, aleatorio, etcétera y, por último, la forma de salir de la fila, que puede darse mediante el proceso de servicio o bien, mediante el abandono por factores como desesperación, hastío, etcétera.

 

Las colas también pueden describirse según su numero de canales y de fases.

Canales: Numero de líneas que hay en el sistema.

Fases: Numero de facilidades de servicio para completarlo.

SIMPLE CANAL SIMPLE FASE

Boletería de cine.

Lavadero de auto.

Camiones arribando para descarga.

MULTICANAL SIMPLE FASE

Cajeros de Banco.

Operadores telefónicos.

Jueces en un sistema judicial atendiendo casos.

MULTICANAL MULTIFASE

Semáforos de calles.

Una gran clínica.

Órdenes que están siendo recibidas, llenadas y facturadas.

SIMPLE CANAL MULTIFASE

Ruta de ómnibus.

Clientes en cafetería.

Estaciones de inspección en sistemas de producción.

Problemas:

- Identifíquese a los clientes, a los servidores y a aquellas características evidentes de La línea de espera, en el caso de un establecimiento automático de lavado de automóviles, en una sola fila.

Los clientes son los automóviles que entran al establecimiento a fin de ser lavados. Un servidor es el aparato que realiza la limpieza y la 61a única indica la existencia de uno o más servidores en serie.

Por lo general, los servicios de lavado funcionan tipo primero en llegar, primero en atenderse; así que la disciplina de la línea de espera es FIFO. La capacidad del sistema es el número de automóviles que pueden maniobrarse con seguridad dentro del lugar de lavado. Si se permite que haya automóviles en la calle esperando turno para entrar, entonces la capacidad del sistema es infinita.

- Identifíquese a los clientes, a los servidores y a aquellas características evidentes de la línea de espera, en el caso del departamento de facturación de un gran almacén.

Los clientes son los cargos que hacen quienes realizan compras en el almacén después de que estos cargos se reciben en el departamento de facturación, pero antes de que se terminen de procesar. Los servidores son personas del departamento de facturación que se encargan de realizar el proceso.

El proceso de facturación sigue a menudo una disciplina de línea de espera LIFO, ya que el último cargo recibido por el departamento de facturación se coloca encima de las hojas pendientes de procesar y es entonces el primer cargo que procesa el servidor que se desocupa. En general, no hay límite para el número de cargos que pueden turnarse al departamento de facturación; de ahí que la capacidad del sistema sea infinita.

- Cada 3 minutos llega un nuevo aparato de televisión, que es tomado por un ingeniero de control de calidad siguiendo un orden del tipo primero en llegar, primero en atenderse. Hay solamente un ingeniero a cargo del proceso y le toma exactamente 4 minutos en inspeccionar cada nuevo aparato. Determínese el número promedio de aparatos en espera de ser inspeccionados durante la primera media hora de un turno, si no había aparatos al inicio del turno.

- Para cierta prueba, en una clínica se ha citado cada 5 minutos a los pacientes, empezando a las 9:00 a.m. La prueba dura exactamente 8 minutos y normalmente la realiza un solo médico contratado para este fin. Siempre que llegan a juntarse tres o más pacientes en la sala de espera, un segundo médico de la clínica también realiza la prueba y continúa haciéndolo hasta que la sala está vacía cuando él concluye una prueba. En este momento, el segundo médico reanuda sus ocupaciones anteriores, hasta que nuevamente resulten necesarios sus servicios. a) ¿En qué momento empieza el segundo doctor a realizar pruebas y cuándo se detiene por primera vez? ; b) ¿Cuál es el promedio de pacientes en la sala de espera de las 9:00 a las 10:00 a.m.? ; c) ¿Cuál es el número promedio de pacientes en la clínica, de las 9:00 a las 10:00 a.m.?

- Los trabajos llegan a un centro, cada 15 minutos, de tres en tres. El centro dispone de un empleado que tarda exactamente 6 minutos en concluir cada trabajo. Los trabajos que el empleado no está procesando, se almacenan en el centro y luego se toman aleatoriamente. Considérese que los trabajos empiezan a llegar en cuanto el empleado se presenta a trabajar y que inicialmente no hay trabajos pendientes del turno anterior. a) ¿Cuál es el número promedio de trabajos en el centro durante las primeras 2 horas de este turno? ; b) ¿De qué longitud será la línea de espera después de un turno de 8 horas?

- Un ortodoncista cita a sus pacientes cada I S minutos para una revisión de rutina y limita el total de pacientes a 10 diarios. Toma 12 minutos examinar al primer paciente, pero debido a que el dentista se cansa rápidamente, cada examen subsecuente toma I minuto más que el anterior. Determínese el tiempo promedio que permanece un paciente en el consultorio, esperando y siendo examinado, considerando que cada paciente llega exactamente a la hora que se le citó.

- ¿A cuántos clientes se les niega la entrada a un sistema de espera D/D/1/3 durante la primera hora, si los clientes llegan cada 4 minutos para un servicio que dura 8 minutos? Considérese que el primer cliente llega cuando las instalaciones de servicio abren.

NOMENCLATURA

S número de servidores

n número de clientes en el sistema

N número máximo de clientes permitidos en el sistema

l n flujo de clientes que entran cuando hay n clientes en el sistema

m n capacidad del servidor cuando hay n clientes en el sistema.

E(t) tiempo promedio de proceso por cliente

V(t) variancia del tiempo de proceso

E(t) tiempo promedio entre llegadas

V(a) variancia del tiempo entre llegadas

C 2a coeficiente cuadrado de variación del flujo de clientes que entran al sistema

C 2s coeficiente cuadrado de variación del tiempo de servicio

C 2p coeficiente cuadrado de variación del flujo de clientes que salen del sistema

pij probabilidad de que el sistema cambie de un estado i a un estado j después de un intervalo de tiempo

Pn probabilidad en estado estable de que existan n clientes en el sistema

L número promedio de clientes en el sistema

Lq número promedio de clientes en la fila

W tiempo promedio de permanencia en el sistema

Wq tiempo promedio de permanencia en la fila

r utilización promedio del servicio

Ct costo total promedio del sistema de líneas de espera por unidad de tiempo

Ce costo promedio de servicio por cliente por unidad de tiempo

Cq costo promedio de espera por cliente por unidad de tiempo

CLASIFICACION DE KENDALL Y LEE

En 1953 Kendall y Lee propusieron un sistema de clasificación de los sistemas de líneas de espera, ampliamente utilizado en la actualidad. Esta clasificación considera seis de las características mencionadas en la estructura de los modelos de líneas de espera, expresándoles en el formato (a / b / c) (d / e / f), donde:

a distribución de probabilidad del tiempo entre llegadas de las transacciones.

b distribución de probabilidad del tiempo de servicio.

Los 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.

c número de servidores

d orden de atención a los clientes.

Los símbolos utilizados en este campo son:

FCFS: primeras entradas, primeros servicios.

LCFS: últimas entradas, primeros servicios.

SIRO: orden aleatorio.

PR: con base en prioridades.

GD: en forma general.

e número máximo de clientes que soporta el sistema en un mismo instante de tiempo.

f número de clientes potenciales del sistema de líneas de espera.

Por ejemplo, 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 en una fila común. En otro caso, un modelo (M / M / 1 ) (LCFS / ¥ / ¥ ) es la clasificación de una línea de espera donde hay 1 servidor atendiendo de acuerdo con un orden de últimas entradas, primeras salidas, con tiempo de servicio exponencial. El sistema da servicio a un número infinito de clientes potenciales, mismos que al llegar serán aceptados por el sistema. El tiempo entre llegadas de los clientes sigue una distribución exponencial y en caso de llegar y encontrar al servidor ocupado, pasan a formarse en una fila común.

 

 

ECUACIONES GENERALES

Las medidas de desempeño con que se trabaja en teoría de colas son principalmente las siguientes:

Utilización de servicio

Representa el porcentaje de tiempo en que los servidores atienden a los clientes y se calcula como la razón entre la tasa promedio de llegadas y la capacidad total del sistema para proporcionar el servicio.

 

__

r =

l .

 

sm

Tasa de entrada promedio

Es el valor ponderado de las tasas de entrada a un sistema y representa el número promedio de clientes que, efectivamente, ingresan al sistema convirtiéndose de clientes potenciales en clientes reales. A su vez, esta variable es la tasa de salida del sistema; en el caso de sistemas de manufactura esta variable representa la producción que en promedio está logrando el sistema.

Número promedio de clientes en el sistema

Es el promedio ponderado de los diferentes estados del sistema, definiendo el estado del sistema como el número de clientes que se encuentran acumulados tanto en espera como en servicio en cualquier momento.

Número promedio de clientes en la fila

A diferencia de la variable anterior en este caso el promedio ponderado se obtiene solamente sobre el número de clientes que se encuentran en espera de ser atendidos en cualquier momento.

Tiempo promedio de espera en el sistema

Es el promedio de los tiempos de estancia de los clientes y se contabiliza desde el punto en el tiempo en que un cliente entra a la fila hasta el momento en que termina de ser atendido por el servidor. La ecuación de conservación conocida como la ecuación de Little permite calcular esta medida de desempeño.

Tiempo promedio de espera en la fila

Se entiende por esta variable al promedio de los tiempos de permanencia de los clientes en espera de ser atendidos y se contabiliza desde el momento en que un cliente se une a la fila hasta que cualquiera de los servidores comienza a atenderlo.

Coeficiente cuadrado de variación

Representa la relación entre la variancia y el cuadrado del valor esperado de una distribución de probabilidad. Algunos de los modelos se representan en función de esta variable, la cual puede ser calculada tanto para el tiempo entre llegadas, para el tiempo de servicio y el tiempo entre salidas del servicio.

 

 

 

 

SIMULACION DE SISTEMAS DE COLAS

Aproximaciones a los problemas de colas.

En resumen podemos decir que existen tres formas de resolver el problema:

  1. Método de prueba y error: Método muy costoso y de larga duración. Es poco práctico aplicarlo a sistemas nuevos o sistemas con parámetros variables. No es necesario la modelización del sistema.
  2. Método analítico: No tiene las desventajas del método anterior. Consiste en modelar el sistema y resolverlo mediante expresiones matemáticas y estadísticas relativamente complejas. Permite evaluar rápidamente la influencia de los distintos parámetros que gobiernan el sistema. Está limitado a sistemas no muy complejos.
  3. Método numérico: No tiene las desventajas del método de prueba y error. Consiste en modelar el sistema y resolverlo mediante simulación numérica. La determinación de cómo afecta la variación de los diferentes parámetros al sistema no es tan evidente como con el método analítico. Permite evaluar cualquier tipo de sistema sin importar su complejidad.

Veamos un ejemplo de aproximación analítica:

Sistema de arcón para herramientas: simple canal simple fase.

Arribo: con distribución Poissón. Servicio: exponencial negativa sin balking.

Disciplina de la cola: Primero que llega primero que se atiende. No consideraremos el transitorio.

La probabilidad de que no haya trabajadores es:

p(0) = 1 – ( l / m ).

La probabilidad de n trabajadores es:

p(n) = [ 1 – ( l / m ) ] * [ ( l / m ) ^n ] .

Supongamos l = 15 trabajadores / hora y m = 18 trabajadores / hora.

p(0) = 1 – ( 15 / 18 ) = 0.17

p(n) = [ 1 – ( 15 / 18 ) ] * [ ( 15 / 18 ) ^2 ] = 0.12

Porcentaje de utilización del servicio:

r = ( l / m ).

15 / 18 = 0.83 %

Número esperado de trabajadores en el sistema:

l / ( m - l )

15 / ( 18 – 15 ) = 5 trabajadores

Número esperado de trabajadores en la cola:

( l ^ 2 ) / [ ( m - l ) * m ]

[ ( l ) / ( m - l ) ] * ( l / m )

15^2 / [18 * ( 18 – 15 ) = 4.17 trabajadores.

El tiempo que pasan en el sistema es:

1 / ( m - l )

1 / (18 – 15 ) = 0.33 horas

El tiempo que pasan en la cola es:

l / [ m * ( m - l ) ]

15 / 18 * (18 – 15) = 0.28 horas

Si el arribo cambia a distribución uniforme, variarían las fórmulas.

Si añadimos costos: Trabajadores = $ 10 / hora servidores = $ 6 / hora.

Costo por hora del tiempo perdido: 0.33 * 15 * 10 = 49.50

Costo del servidor: 6.00

Costo total: 55.50 $

Añadiendo otro servidor: el m = 36 trabajadores / hora en lugar de 18.

Costo por hora del tiempo perdido: 0.05 * 15 * 10 = 7.50

Costo de 2 servidores: 2 * 6 = 12.00

Costo total: 19.50 $

 

COLAS DE POISSON DE CANAL SIMPLE

Iniciaremos nuestro estudio sobre la simulación de sistemas de colas, investigando el sistema de colas de Poisson para un canal simple. A continuación, construiremos un modelo de simulación de este sistema y analizaremos algunos de los aspectos que es preciso tener en consideración al diseñar un modelo de simulación. Luego, cambiaremos algunas de las condiciones del sistema para mostrar cómo se puede utilizar la simulación para el análisis de sistemas más avanzados. En la Figura 1 se ilustra el sistema en el que las unidades llegan a las instalaciones del sistema en busca de servicio. Si el canal o la instalación de servicio no está ocupada, la unidad entra y recibe atención. Si existe ya una unidad en el canal de servicio, la unidad que llega debe tomar su lugar en la línea de espera y aguardar su turno para recibir el servicio que se da por orden de llegada. Se atiende a las unidades sobre la base "el primero que llega el primero que se sirve". La distribución del tiempo entre llegadas sucesivas al sistema, así como la distribución del tiempo necesario para servir a una unidad, se supone que siguen alguna ley de probabilidad (exponencial, normal, gamma, hiperexponencial, etc.). Este concepto de búsqueda de la distribución del tiempo intermedio resultará muy útil en la simulación de sistemas de colas.

Figura 1: Sistema de colas de Poisson de canal simple

El sistema de colas de canal simple suele presentarse mucho en la vida cotidiana. Cada vez que vamos al cine, entramos a un sistema de canal simple para adquirir nuestros boletos de entrada. Otro ejemplo de sistema de canal simple es un sistema de lavado automático de vehículos. Otro más es la cola de estudiantes, ante la oficina de matriculas o la línea de alumnos que esperan para ir al consejero de estudios.

Así pues, nos ocuparemos a continuación de cómo construir un modelo de simulación de este sistema simple. Primeramente, debemos tener en consideración en qué consiste nuestro objetivo al estudiar este sistema. La formulación de objetivos no es tarea sencilla y puede variar de un problema a otro. Seguidamente se listan los más comunes:

  1. Tiempo promedio que pasa una unidad en el sistema y su distribución de frecuencias.
  2. La utilización promedio de las instalaciones de servicio.
  3. El número promedio de unidades en el sistema y su distribución de frecuencias.

El objetivo final, como siempre, es lograr dimensionar el sistema para que cumpla con lo que se espera de él al mínimo costo posible.

A este respecto, podemos decir que el objetivo de la simulación es proporcionar información respecto al funcionamiento de un sistema de colas de Poisson de canal simple. Por el momento, supondremos que esto es suficiente para permitirnos pasar a la construcción del modelo.

Ahora, vamos a ocuparnos del modelo real que construiremos para la solución del sistema de colas de canal simple. Nos enfrentamos a un sistema al que llegan las unidades en forma aleatoria a alguna instalación de servicio. Debemos ser capaces de "hacer" que suceda esto en el modelo usando alguna distribución de probabilidad. Además, el sistema debe servir a esas unidades sobre la base del orden de llegada. El tiempo de servicio de cada unidad dependerá también de una distribución de probabilidad, siendo esta ley no necesariamente igual a la usada para estimar los tiempos de llegada. Por lo tanto, es probable que algunas unidades se vean obligadas a esperar en la cola hasta que les llegue el turno para recibir el servicio. Examinaremos el sistema desde el punto de vista del análisis del "evento siguiente". De este modo, podemos comenzar a observar nuestro sistema en algún punto arbitrario del tiempo y tratar de descubrir lo que va a suceder. Así, lo que nos preguntamos es: ¿qué va a suceder?. En este sistema simple sólo hay dos posibilidades: una unidad puede entrar en el sistema de la misma manera que las instalaciones de servicio pueden poner fin a la atención prestada a una unidad. De este modo, simplificamos todavía más nuestro análisis, porque lo único que haremos a continuación es tomar una decisión respecto a lo que se debe hacer en caso de que ocurra alguno de esos eventos. Examinemos el esquema de la Figura 2 para ver qué debe realizar el simulador cuando se produce el segundo evento. Recuérdese que nos interesa que sucede con las instalaciones de servicio al completarse el servicio.

Figura 2: Diagrama de operaciones de instalaciones de servicio al completar el servicio dado.

Al examinar la Figura 2 podemos ver que las instalaciones de servicio tienen sólo dos estados: están ocupadas (el servicio a la siguiente unidad en espera comienza inmediatamente) o inactivas (ninguna unidad espera para recibir servicio). A continuación, veamos lo que ocurre cuando una unidad entra al sistema para recibir servicio (Figura 3).

Figura 3: Diagrama de operaciones de una unidad que entra en el sistema.

Al examinar la Figura 3 podemos ver también que una unidad que entre en el sistema estará también en uno de dos estados posibles: se encuentra en la línea de espera o recibe servicio.

Siguiendo con esta idea de análisis del evento siguiente, investigaremos cómo se puede modelar todo el sistema, que incluye las unidades en cola, la unidad que está recibiendo servicio y las instalaciones de servicio propiamente dichas. Vamos a ver que es posible incluir en el modelo la idea de los "estados" de una unidad dada o las instalaciones de servicio. En la Figura 4 se muestra una tabla de toma de decisiones para una unidad que acaba de entrar al sistema. Muestra las condiciones que pueden existir y los resultados para la unidad cuando existen los estados dados. En este caso, el criterio utilizado es el de decidir si la unidad entrará a la cola o si pasará inmediatamente al canal de servicio, lo que implica una cola de longitud cero.

En la Figura 4 se muestra que cuando una unidad entra en el sistema, irá inmediatamente al canal de servicio sólo cuando este último esté inactivo y no haya otras unidades en la cola por delante de ella.

Figura 4: Tabla de decisión para la posición de una unidad después de su entrada al sistema

Condición

Eventos al entrar una unidad en el sistema

Resultados para la unidad

Instalación de servicio

Cola

Entra en la cola

Entra en el servicio

Ocupada

Inactiva

No vacía

Vacía

A

ü

   

ü

ü

 

B

ü

 

ü

 

ü

 

C

 

ü

 

ü

 

ü

 

De la tabla anterior se deduce que existen dos estados posibles para la unidad: a) esperando en cola, o b) recibiendo servicio.

Al examinar una tabla similar para las instalaciones de servicio, nos interesaremos por las condiciones que deben existir para que las instalaciones de servicio estén ocupadas u ociosas después de concluir el servicio dado a una unidad. En la Figura 5 se ilustra esto. En ese caso, podemos ver que la instalación estará ocupada después de concluir un servicio a una unidad dada, sólo cuando la cola no esté vacía.

Figura 5: Tabla de decisión para los estados de la instalación después del servicio

Condición

Situación de la Cola

Resultados para la Instalación

No vacía

Vacía

Ocupada

Inactiva

A

ü

 

ü

 

B

 

ü

 

ü

Aquí se ve que para este caso los estados de la instalación también son dos: a) ocupada prestando servicio, o b) inactiva.

Hasta aquí hemos visto dos métodos de análisis para determinar lo que puede ocurrir a continuación en el sistema, según las condiciones dadas. La siguiente pregunta a la que nos enfrentamos es la de saber cómo podemos hacer que ocurran esos eventos en un tiempo simulado. Para este análisis, adoptaremos la idea de "relojes" para "vigilar" lo que debe ocurrir a continuación en el modelo. En la mayoría de los sistemas de colas, nos ocuparemos del tiempo como variable aleatoria. Lo que importa es cómo poder emplear esa idea del análisis del evento siguiente en beneficio propio, al construir un modelo. Afortunadamente tenemos sobre el analista del mundo real la ventaja de que sabemos de antemano lo que ocurrirá a continuación. Cuando un hombre comienza a lavar un automóvil en un servicio de lavado de vehículos, no sabe exactamente la cantidad de tiempo que necesitará para ello. De manera similar, la mujer que vende boletos de entrada en la taquilla de un cine no sabe cuándo llegará la persona siguiente para adquirir una entrada. Podemos estudiar los dos casos y proponer varias distribuciones de tiempo, pero, esencialmente, en el mundo real, los eventos no suelen ser determinísticos. No obstante, en un modelo sabemos cuándo se producirá la llegada siguiente y, asimismo, la duración de un servicio dado, por la sencilla razón de que podemos "generar" esos momentos en nuestro modelo.

Para entender cómo funciona un simulador de cola simple veamos lo siguiente. Supongamos que llamamos Ai a los momentos o instantes en que ingresan las unidades al sistema y Si los instantes en que concluyen los servicios prestados. En la Figura 6 se puede observar un ejemplo de como se distribuyen los diferentes hitos a lo largo del tiempo.

Figura 6: Representación de la escala de tiempo del sistema de canal simple

 

 

 

 

 

 

 

El reloj que registra el tiempo simulado lo llamaremos Reloj Maestro (MCT). TMAX es el tiempo máximo de simulación. En general, el tiempo entre llegadas de unidades al sistema está dado por Ai+1-Ai, este valor es uno de los que generamos en forma aleatoria siguiendo alguna ley de probabilidad. Además hemos supuesto, de manera inherente, que cuando llega una unidad al sistema pasa inmediatamente a las instalaciones de servicio, si no hay unidades en la cola antes que ella. Esto quiere decir que el servicio se inicia en Ai cuando la cola está vacía. Por consiguiente, el tiempo total que pasa que pasa la unidad en el sistema se puede expresar como Si-Ai. Así, resulta evidente que cuando hay unidades en la cola, el tiempo de servicio para la iésima unidad está dado por Si-Si-1. Recordar que el tiempo de servicio es el otro valor que generamos en forma aleatoria. No obstante, si no hay unidades en el sistema, la cantidad de tiempo de inactividad que tendrá el canal en cualquier punto, entre el servicio a la unidad i y a la (i+1), está dado por Ai+1-Si. Cuando se traza una flecha que sobrepasa el límite de la escala, la simulación estará terminada.

  1. En resumen, se inicia la simulación con MCT=0 sin clientes. Se genera la llegada de la primera unidad A1. Se adelanta el reloj maestro a A1.
  2. Se genera la duración del servicio S1-A1. Se genera la llegada del segundo cliente A2.
  3. Nos hacemos la pregunta ¿Cuál es el siguiente evento y cuándo se producirá? :

  1. Se reinicia el ciclo a partir del punto 1 (incrementando en 1 el valor de los subíndices) y se sigue así hasta alcanzar el tiempo final de simulación TMAX.

En muchos casos se limita la cola a una longitud máxima. Es decir no se permite el ingreso de una nueva unidad a la cola cuando ésta tiene su longitud máxima.

Un buen método para construir un modelo de computadora para este sistema de cola consiste en diseñar dos matrices básicas. La primera matriz la denominaremos "matriz unitaria". Contiene la información pertinente sobre cada una de las unidades del sistema. La siguiente es la "matriz de evento siguiente" y contendrá esencialmente los relojes que gobiernan los tiempos de llegada y de servicio. Finalmente, mantendremos un reloj maestro T para la acumulación del tiempo total simulado.

CANALES MULTIPLES EN PARALELO

El sistema que nos interesa aquí es similar al que vimos antes, porque a medida que llegan las unidades, van tomando su lugar en la línea de espera, si no es posible obtener el servicio inmediatamente. No obstante, suponemos aquí que hay más de un canal disponible para el servicio. Este sistema se ilustra en la Figura 7. La primera unidad de la línea de espera entra en el canal de servicio que queda disponible.

Figura 7: Canales de servicio en paralelo

Con fines de análisis, utilizaremos las definiciones y los términos que siguen. El sistema consiste en N canales en paralelo. El iésimo canal del sistema funciona con un índice medio de servicio de m i. La cola formada ante los N canales tendrá una longitud máxima de NQ. Una unidad que intente entrar en la cola cuando esté llena, tendrá que salir del sistema. En este caso, por definición, el sistema incluye a todas las unidades de la cola, así como también los N canales de servicio. Inicialmente, supongamos que la disciplina de la cola exige el servicio por orden de llegada con un tiempo medio entre llegadas de l para las unidades que entran en el sistema.

Investigaremos este sistema como de costumbre, utilizando el análisis del evento siguiente. Como antes, se considera que las entidades de este sistema son las unidades y los canales de servicio. Para comenzar, examinaremos el sistema en un momento dado, cuando la iésima unidad intenta entrar al sistema. En la Figura 8 se muestra un diagrama de operaciones de los resultados posibles para la unidad en este evento.

A continuación, examinaremos el iésimo canal en un momento en que acaba de dar servicio a una unidad. Esto se muestra en la Figura 9.

Obsérvese la semejanza entre el funcionamiento que se muestra en la figura 9 y el diagrama de operaciones para el canal de servicio en el sistema de colas de canal simple (Figura 2). En realidad, desde el punto de vista de las instalaciones de servicio, los sistemas son casi idénticos. La única diferencia, en este caso, es que cada canal en paralelo debe "competir" para obtener unidades de la cola. Podría considerarse que el sistema de canal simple es un caso especial de este sistema; aunque no suele hacerse así.

Al construir tablas de decisión para el análisis de eventos y resultados para cada una de las entidades del sistema, vemos que para todos los fines prácticos, la tabla de decisión para una instalación dada es la misma que se muestra en la Figura 5. Además, la tabla de decisión para las unidades que entran al sistema no es muy diferente a la que aparece en la Figura 4. En la Figura 10 se ilustra la tabla de decisión para una unidad que trata de entrar al sistema. En esta figura se ilustra el hecho de que sólo cuando la cola está vacía y hay por lo menos un canal inactivo, entrará una unidad en el canal de servicio inmediatamente, en cuanto ingresa al sistema. Si existen otras condiciones, la unidad abandonará el sistema o entrará en la cola para esperar el servicio. Si se encuentra disponible más de un canal cuando la unidad se dispone a entrar al servicio, irá al primer canal disponible. Esto implica que no existe una relación de preferencia entre los canales y que la elección es suficientemente aleatoria. En realidad, pueden existir preferencias basadas, por ejemplo, en la rapidez del servicio; o sea la unidad irá al canal que tenga el menor tiempo esperado de servicio. No obstante, en la mayoría de los casos se puede pasar por alto ese efecto.

Figura 10: Tabla de decisión para el estado de una unidad al entrar al sistema

Condición

Eventos al entrar una unidad en el sistema

Resultados para la unidad

Instalación de servicio

Cola

Entra a la cola

Entra al primer canal libre

Sale del sistema

Los N canales ocupados

Al menos un canal inactivo

Llena

No llena

Vacía

A

   

ü

       

ü

B

     

ü

 

ü

   

C

ü

     

ü

ü

   

D

 

ü

   

ü

 

ü

 

A partir de analizar la Figura 10 podemos suponer, por conveniencia, que una unidad dada se puede encontrar en cualquiera de uno de los (N+1) estados posibles. El primer estado es el de estar en la cola y los últimos N estados indican en cuál de los N canales recibe servicio la unidad. Para ir de acuerdo a los análisis anteriores sobre los estados de una unidad, debemos entender que una cierta unidad se encuentra sólo en una de dos situaciones posibles en el sistema: a) en la cola, o b) en servicio. Sin embargo, es mucho más fácil entender y posteriormente programar el modelo de simulación con la suposición de (N+1) estados.

La metodología para simular este sistema de canales en paralelo es exactamente la misma que se utilizó en el caso anterior. Obsérvese el modo en que podría "reducirse" este modelo al del sistema de canal simple.

CANALES MULTIPLES EN SERIE

A continuación examinaremos el análisis de la simulación de sistemas de colas que contienen canales múltiples en serie. En la Figura 11 se ilustra este tipo de sistema en el que cada unidad que llega al sistema debe pasar por cada canal de servicio.

Figura 11: Canales de servicio en serie

Definiremos el sistema de colas para incluir N canales de servicio o instalaciones y, asimismo, N colas, una ante cada canal. La distribución del tiempo entre llegadas para unidades que entran en el sistema tiene una media l y se supone que el tiempo de servicio para cada canal tiene una media de m i(i=1,2...N). Además, cada cola del sistema tendrá una longitud máxima permisible, denominada NQi(i=1,2,...,N). Una unidad que intente entrar en la cola inicial cuando esté llena será eliminada del sistema. Una unidad saldrá de cualquier canal de servicio sólo cuando la cola siguiente no esté llena. Si la cola que sigue está llena la unidad permanecerá en el canal de servicio hasta que pueda entrar en la cola siguiente, impidiendo en esa forma que el canal dé servicio. Supondremos que en todas las colas hay una disciplina de servicio por orden de llegada. Obsérvese que el proceso de llegada de las unidades a cada uno de los canales de los canales de 2 a N, está regido no sólo por el proceso de llegadas a la instalación inicial sino también por la distribución del tiempo de servicio de cada una de las instalaciones anteriores.

Para aplicar a este sistema nuestro concepto de análisis del evento siguiente, veamos lo que le puede ocurrir a cierta unidad en el momento en que termina el servicio que recibe en el iésimo canal. En la Figura 12 se muestra un diagrama de operaciones con los resultados posibles. Además, veamos lo que pudiera ocurrir en el iésimo canal al concluir el servicio dado a una unidad determinada. Esto se muestra en la Figura 13.

Como en el caso del canal simple, las entidades del sistema son las unidades y las instalaciones o los canales de servicio. Para cada entidad del sistema, los mencionados diagramas de operaciones ilustran el proceso de decisión de eventos y resultados. A continuación construiremos las tablas de decisión para esas entidades, tal y como se hizo antes. En la Figura 14 se muestra la tabla de decisión para una unidad que acaba de recibir el servicio en el iésimo canal. Obsérvese la modificación pequeña de lógica que se requiere al analizar una unidad que trata de entrar en la primera cola.

 

Figura 14: Tabla de decisión para una unidad que intenta salir del canal de servicio i

Condición

Eventos que influyen en el intento

de salir del canal de servicio i

Resultados para la unidad

Instalación de servicio

Cola

Se queda en el canal i

Entra en la cola (i+1)

Entra al canal (i+1)

El canal (i+1) está bloqueado

El canal (i+1) está ocupado

El canal (i+1) está inactivo

La cola (i+1) está llena

La cola (i+1) no está vacía

La cola (i+1) está vacía

A

     

ü

   

ü

   

B

 

ü

   

ü

   

ü

 

C

 

ü

     

ü

 

ü

 

D

   

ü

   

ü

   

ü

E

ü

     

ü

   

ü

 

F

ü

       

ü

 

ü

 

A partir de la Figura 14 llegamos a la conclusión de que cualquier unidad que se encuentre en el sistema estará en uno de tres estados: a) bloqueada en el canal de servicio, b) recibiendo servicio en algún canal, o c) esperando en una cola. Si multiplicamos esto por N canales, el número total de estados por los que puede pasar cualquier unidad dada es 3N-1, puesto que la unidad no puede quedar bloqueada en el Nésimo canal.

A continuación examinaremos la tabla de decisión para la iésima instalación del sistema al concluir el servicio a determinada unidad. En la Figura 15 se ilustra la tabla de decisión para una instalación dada.

Figura 15: Tabla de decisión para la instalación i, al concluir un servicio

Condición

Eventos al concluir el

servicio a una unidad dada

Resultados para la Instalación

La cola (i+1) está llena

La cola (i+1) no está llena

La cola i no está vacía

La cola i está vacía

Instalación bloqueada

Instalación inactiva

Instalación ocupada

A

ü

 

ü

 

ü

ü

 

B

ü

   

ü

ü

ü

 

C

 

ü

ü

     

ü

D

 

ü

 

ü

 

ü

 

En este sistema hay tres estados en los que puede encontrarse una instalación (excepto la Nésima): a) bloqueada, por el hecho de que hay una cola completa ante la siguiente instalación de servicio, b) ocupada, dando servicio a una unidad, o c) inactiva.

El funcionamiento general del modelo de simulación para este caso es muy similar a los dos modelos presentados anteriormente.

 

 

OTROS SISTEMAS DE COLAS

Los tres sistemas analizados anteriormente son los considerados como básicos de los que se encuentran en la teoría de colas. Estos sistemas pueden considerarse como la estructura básica para la construcción de la teoría de colas, hasta el punto de que la mayoría de los sistemas de colas que se encuentran comúnmente se pueden desarrollar mediante la alteración de las condiciones que rigen a los sistemas básicos. Por lo común, las soluciones para esos sistemas modificados son más complejas que para los sistemas básicos.

El control del funcionamiento de un sistema de servicio se rige por la distribución de las llegadas, el comportamiento de las llegadas individuales, el mecanismo de servicio, la disciplina de colas y la capacidad del sistema.

Cuando una llegada se presenta en el sistema puede comportarse de diverso modos. Puede decidir no entrar al sistema en absoluto debido a la longitud de la línea de espera. Esa conducta se denomina frustración. La llegada puede entrar al sistema y, luego, decidir abandonarlo (rechazo) o puede decidir salirse de una línea de espera del sistema para colocarse en otra. El denominador común de cada uno de esos modos de comportamiento es el de que la acción de la unidad que llega es completamente voluntaria.

El mecanismo de servicio en un sistema de colas se especifica por medio del número de canales de servicio, su disposición (en paralelo o en serie), y la distribución del tiempo de servicio en cada canal. Muchas veces en el caso de sistemas que involucran secuencias de canales (simples o múltiples en paralelo) en serie, como sucede en el caso del sistema que se ilustra en la Figura 16, es imposible resolver el modelo utilizando el método analítico. No obstante, se puede encontrar una solución mediante la simulación utilizando los métodos numéricos similares a los que hemos visto.

La disciplina de colas de un sistema controla el orden en que se da servicio a las unidades que llegan. Por lo común se da servicio por orden de llegada; pero no son raros los servicios aleatorios y los de prioridad. Las prioridades son de derecho asegurado si una unidad que llega puede entrar al servicio inmediatamente, tanto si están dando servicio a otra unidad como si no es así. Esto quiere decir que si una unidad que llegue tiene una prioridad superior a la que esté recibiendo servicio, esa prioridad será de derecho asegurado cuando la unidad que esté recibiendo el servicio se vea remplazada inmediatamente por la que llega.

La capacidad de un sistema se determina por el número máximo de unidades que se permite en el sistema al mismo tiempo. Por lo común se considera que la capacidad es constante para un sistema; aunque hay situaciones en las que se puede considerar a la capacidad como variable aleatoria.

Figura 16: Sistemas complejos

 

RESUMEN DE LA SIMULACION DE SISTEMAS DE COLAS

Hasta aquí hemos presentado los conceptos básicos de la simulación de sistemas de colas. En esta sección, revisaremos los temas presentados y analizaremos los aspectos del modelado de sistemas de colas.

Todos los sistemas de colas consisten en tres entidades básicas, unidades a las que se debe dar servicio, una o varias instalaciones para el servicio una cola para las unidades que esperan recibir servicio. Veamos cada una de esas entidades y resumamos las características que podemos desear incluir en un modelo de simulación en computadora. La mayoría de esas características se vieron ya antes. Las otras se incluyen para completar la exposición y no deben presentar grandes dificultades para insertarse en un modelo ya establecido.

Unidades

Las llegadas a un sistema de colas, llamadas unidades, poseen características o afectan al sistema en alguna forma. Esas características se dan a continuación:

  1. Distribución del índice de llegadas o distribución del tiempo entre llegadas. Es un proceso al azar que rige el número de llegadas al sistema.
  2. Prioridad. Es una medida relativa del valor de una unidad para el sistema, en comparación con otras. En general, establece la rapidez con la que pasará una unidad por el sistema, en relación con otras.
  3. Impaciencia. Este factor indica el tiempo que permanecerá una unidad en el sistema sin recibir servicio. Puede describir condiciones sobre una unidad, denominadas "alejamiento", "abandono" o "cambio de línea". El alejamiento es la condición en la que una unidad se niega a entrar en una cola, debido a su longitud. Abandono es cuando una unidad sale de la cola, después de esperar cierta cantidad de tiempo. El cambio de línea es la condición en la que una unidad sale de una cola para entrar en otra.

Otra característica que incluimos (sólo con fines de simulación) como descripción de una unidad, era el tiempo de servicio en una instalación. En realidad, se trata de una función del canal de servicio y la analizaremos aquí. La incluimos como información descriptiva sobre unidades en el sistema para normalizar el método y retirar los efectos de la generación de números aleatorios. Un aspecto final no analizado previamente, en relación con las llegadas es el de las "llegadas en grupo", que se pueden ilustrar mediante el ejemplo de un ascensor. La llegada al sistema puede considerarse que es cuando el ascensor se detiene en un piso. Sin embargo, contiene varias unidades. Anteriormente, vimos sólo las llegadas de una sola unidad. Otro ejemplo de llegadas en grupo es el de una caja de piezas, a una máquina, para su labrado.

Canal de servicio

Las instalaciones para dar servicio a las unidades del servicio tienen varias características que tomamos en consideración y que son:

  1. Proceso de servicio. Se trata de la distribución del tiempo de servicio. Se considera como proceso conjetural, cuya variación es inherente de la instalación. En general, tendemos a asignar valores de ese proceso a las unidades que llegan al sistema.
  2. Disposición de los canales. Esto rige la configuración del sistema. Los canales se disponen en serie o paralelo o en alguna combinación en serie y paralelo.
  3. Disciplina de servicio. Esta característica de la instalación indica si puede o no interrumpirse cuando está en servicio. Las prioridades unitarias van de la mano con este aspecto. Las unidades de mayor prioridad pueden exigir que la instalación detenga su proceso actual para darles servicio. Esto se denomina procesamiento prioritario.

Otro aspecto del servicio se relaciona con las llegadas en grupo de unidades al sistema. Esto se conoce como servicio colectivo. En este caso, la instalación funciona sobre grupos de unidades al mismo tiempo.

Cola

La línea de espera ante las instalaciones de servicio ofrece el principal campo de estudio. La línea de espera para el modelo de simulación tiene las características siguientes:

  1. Longitud -¿cuántas unidades pueden encontrarse en la línea de espera al mismo tiempo?
  2. Disciplina de la cola. Establece el método de disposición de las unidades de la cola. En general, consideramos que este aspecto depende de la cola; sin embargo, en realidad, depende generalmente de las unidades que hay en la cola. Existen varias posibilidades diferentes de disciplinas de colas. La más sencilla de todas es la de dar servicio según el orden de llegada.

Muchas investigaciones de colas giran en torno de la siguiente pregunta: "¿Qué sucedería si la disciplina de colas fuera...?" En este aspecto de los sistemas, la cola misma ofrece la mejor oportunidad de estudio en un campo bajo el control de la administración. Con frecuencia es mucho más fácil establecer una nueva disciplina de colas que modificar un proceso con un promedio dado de servicio. Por consiguiente, muchos análisis se ocupan de la investigación de varias disciplinas de colas o "planes de prioridades".

Finalmente el sistema en su conjunto tiene ciertas características que no se pueden incluir en las tres entidades. Entre ellas se encuentran las limitaciones al número de unidades en el sistema y los períodos operacionales. La restricción del número de unidades en el sistema suele tener muchas veces una enorme importancia, porque representa una limitación de la capacidad. El período operacional de un sistema es la cantidad de tiempo que puede funcionar el sistema continuamente. Algunos sistemas pueden funcionar continuamente durante ciertos períodos de tiempo. En otros sistemas, ese período puede estar limitado a cierto tiempo máximo.

El análisis de un sistema dado de colas incluye la síntesis de las características descritas antes. A veces, se encuentran presentes todas esas características. En otras oportunidades, sólo se toman en consideración unas cuantas. Desde luego, el sistema mismo dicta, en gran parte, las características que existen. No obstante, los objetivos de un análisis o un experimento dado pueden dictar qué otras características se incluyen. Otra característica que podemos desear incluir es la información de costos.

Finalmente es preciso desarrollar un sentido de conciencia hacia los problemas de la validez estadística de los modelos de simulación. Algunos aspectos a tener en cuenta son la validez de los generadores de números seudoaleatorios y la cantidad y la calidad de la información que se debe recoger. Desde luego, deben desempeñar un papel importante en la simulación de cualquier sistema. Aunque no analizamos de manera detallada la formulación de objetivos para el análisis, esto afecta también nuestras consideraciones estadísticas.

La simulación de sistemas de colas tal y como se presentó en esta aquí incluía el concepto de análisis del evento siguiente. Evidentemente, hay otros modos de construir modelos de simulación de sistemas de colas. Sin embargo, los métodos presentados aquí proporcionan un método unificado para abordar los análisis de este tipo. Cualquier sistema de colas se puede dividir en las entidades componentes y se puede utilizar cada una de estas últimas, utilizando el método de la tabla de decisión.

 

BIBLIOGRAFÍA:

"Simulación y Análisis de Sistemas Estocásticos" de Mohammad Azarang y Eduardo García Dunna, McGraw Hill, México 1996.

"Análisis y Simulación de Sistemas Industriales" de J.W. Schmidt y R.E. Taylor, Editorial Trillas, México 1979.

1