En su sentido más amplio, la teoría de las colas es el estudio de la contención por el uso de un recurso compartido, pero limitado. Se compone de modelos y fórmulas que describen las relaciones entre las solicitudes de servicio, la congestión y el retraso.
La teoría de las colas puede extenderse para cubrir una amplia variedad de situaciones de disputa, como cómo se forman las líneas de pago de los clientes (y cómo se pueden minimizar), cuántas llamadas puede manejar un conmutador telefónico, cuántos usuarios de computadoras pueden compartir un mainframe, y cuántas puertas debe tener un edificio de oficinas. De manera más general, la teoría de las colas se utiliza en entornos comerciales principalmente en la gestión de operaciones y problemas de investigación como la programación de la producción, la logística / distribución y la gestión de redes informáticas. Se trata de aplicaciones diversas, pero todas sus soluciones implican la misma dinámica.
La naturaleza de la cola es de cambio de costos y promediado de cargas. Un proveedor de algún servicio cuyos recursos son limitados puede atender solo a un pequeño número de personas a la vez. Cualquier cantidad de personas más allá de eso están obligadas a esperar su turno.
Suponiendo que el tiempo de todos vale algo, aquellos que deben esperar el servicio están gastando una posesión valiosa: su tiempo. Al esperar en la fila, el proveedor de servicios se asegura de que ninguno de sus recursos quede inactivo. En efecto, el cliente que espera se ve obligado a pagar a tiempo por el privilegio de ser atendido, trasladando los costos del proveedor del servicio al cliente.
En una oficina de correos, donde generalmente hay una fila pero varios empleados, la siguiente persona a la que se atiende es la que ha permanecido más tiempo en la fila. La carga de la espera la comparten todos los que están en la fila: cuanto más grande es la fila, más larga es la espera promedio.
La carga se comparte de manera menos equitativa en una tienda de comestibles, donde cada empleado tiene una fila. Si una línea tiene cinco pedidos simples y otra tiene cinco clientes con pedidos grandes, cupones y frutas para pesar, la línea simple probablemente se moverá mucho más rápido. Los que tengan la suerte de estar en esa línea serán atendidos antes que los de la línea compleja. Por lo tanto, los compradores de comestibles no compartirán la carga de la espera de manera tan equitativa como en la oficina de correos.
La pregunta para el proveedor de servicios es simple: cómo brindar un buen servicio. De hecho, el nivel más alto de servicio se lograría proporcionando recursos iguales al número de usuarios; un cajero para cada comprador. Sin embargo, esto sería extremadamente costoso y logísticamente impráctico; decenas de cajeros permanecían inactivos entre pedidos.
Para minimizar los costos, el gerente puede proporcionar solo un cajero, lo que obliga a todos a formar una fila larga y lenta. Es probable que los clientes cansados de la espera abandonen sus compras y comiencen a comprar en una nueva tienda. Surge la pregunta: ¿cuál es un nivel aceptable de servicio a un costo aceptable para el proveedor?
Estos ejemplos parecen simples, pero las preguntas que plantean se extienden mucho más allá de la tienda de comestibles promedio. La teoría de las colas es la base para la gestión del tráfico: el mantenimiento de un flujo de tráfico fluido, manteniendo la congestión y los cuellos de botella al mínimo. Una vez que se comprende la naturaleza del flujo de tráfico, se pueden ofrecer soluciones para aliviar las demandas de un sistema, aumentando así su eficiencia y reduciendo los costos de operación.
DESARROLLO HISTÓRICO DE
LA TEORÍA DE LAS COLAS
El primero en desarrollar una teoría de colas viable fue el matemático francés SD Poisson (1781-1840). Poisson creó una función de distribución para describir la probabilidad de un resultado prescrito después de repetidas iteraciones de ensayos independientes. Debido a que Poisson usó un enfoque estadístico, las distribuciones que usó podrían aplicarse a cualquier situación en la que se realicen demandas excesivas sobre un recurso limitado.
La aplicación más importante de la teoría de las colas se produjo a finales del siglo XIX, cuando las compañías telefónicas se enfrentaron al problema de cuántos operadores poner en servicio en un momento dado. En ese momento, todas las llamadas fueron conmutadas manualmente por un operador que conectó físicamente un cable a una centralita. Cada cliente requirió al operador solo durante los pocos segundos que le tomó transmitir las instrucciones y tener el enchufe insertado y el tiempo registrado. Una vez establecida la llamada, el operador podía aceptar otra llamada. El problema para uno de los primeros ingenieros de tráfico telefónico era cuántas centralitas debían instalarse en un área.
Más allá de eso, los supervisores se enfrentaron al problema de cuántos operadores mantener en las juntas. Demasiados, y la mayoría de los operadores permanecerían inactivos durante minutos a la vez. Demasiados pocos, y los operadores se verían abrumados por las solicitudes de servicio, tal vez nunca se pondrían al día hasta que se agregara ayuda adicional.
A menudo, las personas que llamaban que no podían llamar la atención de un operador simplemente colgaban frustradas y, sospechando que era un momento muy ocupado para los operadores, esperaban varios minutos antes de volver a intentarlo. Otros permanecieron en la línea, esperando su turno para hablar con el operador. Sin embargo, otros llamaban repetidamente, esperando que el operador estuviera lo suficientemente molesto por las llamadas repetidas para atenderlos a continuación.
Estas discrepancias de comportamiento causaron problemas a los ingenieros de tráfico porque afectaron el nivel de demanda de servicio de un operador. Una llamada rechazada se perdió, no volvería hasta mucho más tarde, y estaba efectivamente fuera del sistema. Las personas que llamaban en espera eran más predecibles, mientras que las personas que llamaban repetidas solo aumentaban las demandas del sistema al aparecer como varias solicitudes. La fórmula de Poisson estaba destinada únicamente a esta última situación.
Debido a que pocas personas que llamaron actuaron tan agresivamente como suponía la fórmula de Poisson, los sistemas a menudo se diseñaron en exceso, lo que resultó en un desperdicio sustancial de recursos. Las oficinas de los operadores estaban equipadas con 24 cuadros de distribución cuando nunca utilizaron más de 20.
Un matemático danés llamado AK Erlang desarrolló un enfoque diferente para la ingeniería de tráfico basado en el trabajo de Poisson. Estableció fórmulas para las llamadas que se abandonan (llamadas Erlang-B) y para las que se retienen hasta que se otorga el servicio (Erlang-C).
Las fórmulas de Poisson y dos de Erlang hicieron algunas suposiciones básicas sobre el sistema. Dado que el comportamiento del usuario es impredecible, se supone que los tipos de llamadas que se reciben se distribuyen aleatoriamente. Es decir, es probable que las características de llamadas inusuales en un período se normalicen con el tiempo y produzcan una distribución más normal.
MODELOS DE COLAS
El modelo más básico de una cola se conoce como sistema M / M / l. Esta notación significa que los elementos (personas, paquetes de datos, unidades de producto) llegan a la cola siguiendo una distribución aleatoria de Poisson (también llamada Markoviana, que produce la primera “M”), que la distribución de los intervalos de servicio es el primero en entrar / primero en salir. y exponencial (segunda “M”), y que la cola procesa o atiende solo un elemento a la vez (número “1”). Este modelo corresponde a una cola ordinaria, como la fila de una tienda de comestibles, donde los clientes llegan en horarios aleatorios, se atienden uno a la vez en el orden en que vienen (nadie tiene prioridad) y un servidor se ocupa de todos. Sin más información, Este modelo también asume implícitamente que no existe un límite superior en la capacidad del sistema (al menos ninguno que pueda especificarse) o en la población de elementos que pueden ingresar a la cola, dos suposiciones que, por supuesto, son erróneas en muchas aplicaciones de la vida real. Una cola M / M / I con limitación de capacidad c y la restricción de población p estarían representadas por la notación M / M / l / c / p.
Con base en las tasas de llegada promedio y las tasas de servicio promedio, las fórmulas que describen el modelo M / M / I, o cualquier otro modelo de cola, se pueden utilizar para calcular medidas importantes del sistema, como la utilización de la capacidad, los tiempos promedio de espera para el servicio o el número promedio de elementos en la cola en un momento dado. Usando el modelo M / M / I, por ejemplo, podemos determinar la velocidad promedio de procesamiento de clientes necesaria para que una tienda de comestibles mantenga su promesa de que no más de tres personas esperarán en una línea de comestibles determinada en cualquier momento (asumiendo que cada line es una cola M / M / l independiente). Para mantener un promedio de aproximadamente tres clientes en el sistema en un momento dado, la tienda necesitaría revisar 1.33 clientes por cada uno que llegara por unidad de tiempo. Si, En aras de la simplicidad, asumimos que llega un cliente por minuto, esto significaría una espera promedio de poco más de tres minutos por cliente. En este nivel, la tienda está utilizando aproximadamente el 75 por ciento de su tiempo o capacidad de servidor (cajero).
Si la tienda quisiera ahorrar dinero en personal aumentando el uso de su capacidad al 90 por ciento, su tasa efectiva de servicio tendría que reducirse a una tasa efectiva de 1,1 clientes por minuto. Por supuesto, esto no significa que los empleados trabajarían más lentamente, sino que el sistema en su conjunto (que requeriría un modelo más elaborado para articularse completamente) está procesando la misma cantidad de clientes en niveles de personal más bajos. En el nivel de utilización del 90 por ciento, habría un promedio de nueve clientes en la cola en cualquier momento, y la espera promedio sería de aproximadamente 9 minutos. En efecto, una ganancia del 20 por ciento en la tasa de utilización de la tienda le costaría al cliente promedio un aumento de tres veces en el tiempo de espera.
Un modelo diferente, y más preciso, del sistema de colas de la tienda arrojaría valores diferentes, pero este ejemplo ilustra cómo se pueden aplicar los modelos a problemas de la vida real. Otros modelos de colas varían en los patrones de llegada, patrones de servicio, número de servidores y otras limitaciones. Ejemplos de otros patrones de llegada y servicio incluyen patrones deterministas (p. Ej., D / D / 1), donde los eventos ocurren en intervalos conocidos en lugar de aleatorios, y patrones generales (p. Ej., G / GIl), donde los eventos pueden ser aleatorios o deterministas. Estos patrones pueden usarse en diferentes combinaciones en el mismo modelo, como en M / D / I o D / G / I. El orden de procesamiento / servicio también puede variar. En el M / M / I se asume que el orden es primero en entrar, primero en salir (FIFO),
EJEMPLOS DE
APLICACIONES DE LA TEORÍA DE COLAS
El período recurrente más inusual es la “hora pico”, que proporciona un patrón sobre el que se debe diseñar el sistema. Por ejemplo, si un sistema recibe su mayor número de llamadas entre las 9 y las 10 am, la oficina debe estar equipada con suficientes centralitas para manejar ese nivel de solicitudes. La cuestión de cuántos operadores asignar depende de los patrones de llamada de una hora a la siguiente.
Lo interesante de las fórmulas de Poisson y Erlang es que la relación entre los operadores y la congestión no es paralela. Por ejemplo, suponga que 10 operadores se ven inundados por un 30 por ciento más de llamadas de las que suelen atender. Un supervisor llama a un undécimo operador y, aunque la tasa de solicitudes de servicio entrantes permanece constante, la acumulación de pedidos se reducirá gradualmente. Una vez que se elimina la acumulación, el undécimo operador puede obligar a otros a permanecer inactivos durante períodos prolongados.
Podríamos suponer que 10 operadores que manejan el 130 por ciento de su volumen normal requerirían 13 operadores. De hecho, la adición de solo uno es más que suficiente para resolver el problema. Esto se debe a que se eliminan las llamadas repetidas y la espera agregada de todos los que tienen (que crece geométricamente) se reduce un factor a la vez. La acumulación simplemente no puede regenerarse lo suficientemente rápido.
Dicho de otra manera, 11 operadores pueden deshacerse de las solicitudes de servicio a un ritmo más rápido de lo que ingresan. Es posible que se necesiten unos minutos para eliminar la acumulación, pero la acumulación se reducirá con el tiempo.
Considere la situación en una tienda de comestibles donde hay cinco filas abiertas y 12 personas en cada fila. La adición de un solo cajero adicional reducirá rápidamente las filas a una o dos personas, aunque la misma cantidad de personas ingresen a las filas de caja. Cuando se elimina la acumulación, el sexto cajero puede ser retirado y puesto en otro trabajo.
Así como se puede diseñar un sistema, las perturbaciones no aleatorias inusuales pueden hacer que el sistema colapse de manera espectacular. Esto quedó demostrado por un problema con el sistema de agua de Nueva York durante la década de 1950. Los ingenieros descubrieron que la presión del agua se redujo significativamente, y para los bomberos, peligrosamente, durante un período de horas todos los domingos por la noche. Un estudio reveló un culpable inusual: Milton Berle.
El comediante presentaba un programa de televisión semanal inmensamente popular todos los domingos que era visto por casi todos con un set. Cuando el espectáculo fue a una pausa comercial, decenas de miles de personas, habiendo terminado de cenar, se retiraron a sus baños al mismo tiempo.
Con miles de inodoros que se descargan en cuestión de minutos entre sí, las alcantarillas se inundaron. Más importante aún, los tanques de los inodoros se estaban llenando y cada uno consumía dos o tres galones de agua dulce. La demanda coordinada de agua en un breve período de tiempo prácticamente eliminó la presión del agua. De hecho, algunos inodoros tardaron media hora en rellenarse y la presión del agua tardó horas en recuperarse.
Se consideró seriamente cancelar el programa. Sin embargo, la solución fue relativamente sencilla. La adición de solo unas pocas torres de agua más fue suficiente para mantener una presión de agua adecuada. En esencia, el sistema fue rediseñado para manejar picos más exigentes.
Esta situación puede repetirse en un sistema telefónico cuando todos están motivados para realizar una llamada al mismo tiempo. Durante el terremoto de San Francisco de 1989, un gran número de personas en el área metropolitana intentaron hacer una llamada al mismo tiempo, inmediatamente después de que el terremoto amainó, con la esperanza de saber si sus amigos y familiares estaban a salvo. Aunque los sistemas de conmutación estaban automatizados, no pudieron manejar el volumen de solicitudes de tono de marcado.
Solo se permitió que se realizara un pequeño porcentaje de llamadas (suficiente para cumplir con la capacidad del sistema). De hecho, los reporteros de radio y televisión instaron a la gente a que se mantuviera alejada de las líneas para poder atender las llamadas de emergencia.
No hubo necesidad de rediseñar el sistema porque la ocurrencia de terremotos, aunque aleatoria, no se repite consistentemente. No sería rentable diseñar la red telefónica para usos máximos que ocurren solo una vez cada década aproximadamente. Como resultado, cada terremoto produce una falla temporal en la red telefónica.
Otros casos un poco menos ofensivos ocurren cada vez que un presentador de radio ofrece un premio al “llamador número x”. Las compañías telefónicas y los funcionarios públicos han convencido a muchas estaciones de radio para que suspendan la práctica.
APLICACIONES FUTURAS DE LA
TEORÍA DE COLAS
Es probable que las aplicaciones futuras más relevantes y prometedoras de la teoría de las colas se produzcan en las áreas de informática y sistemas de fabricación. En informática, las colas son una consideración necesaria en la contención de los recursos de procesamiento. Dado que el componente de mayor costo en la computación avanzada es la potencia de procesamiento, los sistemas se están moviendo cada vez más hacia soluciones de red en las que se distribuye la potencia de procesamiento. El resultado de esta tendencia hacia una mayor distribución es que los sistemas competirán por el acceso a una red y a diversos procesadores y archivos.
En la fabricación, las colas son un elemento necesario de los sistemas flexibles en los que los factores de producción pueden ajustarse continuamente para manejar los aumentos periódicos en la demanda de capacidad de fabricación. El exceso de capacidad en períodos de baja demanda puede convertirse en otras formas de capital de trabajo, en lugar de verse obligado a gastar esos períodos como activos inactivos e improductivos.
El concepto de sistemas de fabricación flexibles es muy interesante. Tenga en cuenta que hoy en día una empresa como Boeing soporta largos períodos de baja demanda de sus aviones comerciales (como resultado de los ciclos en la industria del transporte aéreo), pero debe prepararse rápidamente para aumentar la producción cuando aumenta la demanda. La empresa debe alternativamente abrir y reducir millones de dólares en capacidad de fabricación (y contratar y despedir a miles de trabajadores) a lo largo de cada ciclo de demanda.
Durante períodos de baja demanda, el espacio de piso, la maquinaria y los inventarios permanecen inmovilizados. Si, por otro lado, los flujos de demanda pudieran administrarse mejor, Boeing podría convertir estos activos en aplicaciones más productivas. El enfoque principal de la teoría de las colas en la fabricación flexible sigue centrado en la confiabilidad y la depreciación de la máquina y los tiempos de procesamiento y ciclo.