Cómo calcular la Utilización de un servidor, Tiempo de Espera y Tiempo de Flujo de una Línea de Espera

El siguiente artículo aborda de forma práctica cómo calcular algunos indicadores de desempeño básico de un sistema de espera con un único servidor. Entre ellos, la tasa promedio de flujo (λ), la capacidad promedio del servidor (μ), la utilización promedio del servidor (ρ=λ/μ), el tiempo promedio que un cliente esta en la fila esperando ser atendido (Wq) y el tiempo promedio que un cliente esta en el sistema (Ws), esto incluyendo tanto los tiempos de espera como los tiempos de atención.

Considere un proceso de línea de espera que tiene un servidor y una única fila (caja de atención) como el que se describe a continuación. Se opera bajo una regla de prioridad FIFO, es decir, se atienden los clientes por orden de llegada. Los registros tomados para la primera hora de trabajo de un día en particular son los siguientes:

linea-de-espera-1-servidor
tabla-llegada-de-clientes-l

Por ejemplo el Cliente 3 llega exactamente 9 minutos después de iniciada las actividades y una vez que comienza su atención (por el servidor) el tiempo requerido para completar ésta es de 7 minutos. Es decir, el tiempo de flujo de este cliente es de 11 minutos, donde 7 minutos corresponde a la atención en sí y los 4 minutos restantes son los minutos que debe esperar que se desocupe el servidor (que esta atendiendo al Cliente 2). Con este ejemplo queda en evidencia que contar con la información de las primeras 3 columnas se puede completar la información de las columnas restantes.

Ahora desarrollaremos algunos cálculos básicos que permite tener una noción del desempeño de esta línea de espera.

Calcular la tasa de flujo promedio (λ) y la capacidad promedio del servidor (μ): Pasaron 12 clientes por el servicio en 60 minutos, luego la tasa de flujo promedio es λ=0,2[clientes/minuto]=12[clientes/hora]. El tiempo de servicio promedio es 4[min] (corresponde al promedio de los valores de la columna Ws), luego la capacidad promedio es μ=1[clientes]/4[min]=0,25[clientes/min]=15[clientes/hora].

La utilización promedio del servidor (ρ): Esto permite estimar que porcentaje del tiempo en promedio el servidor esta ocupado (atendiendo clientes). En nuestro ejemplo ρ=λ/μ=12[clientes/hora]/15[clientes/hora]=80%. Notar que de este ejemplo sencillo se obtiene una importante conclusión que se puede extrapolar a otros sistemas de espera más complejos:

Si existe variabilidad en las llegadas y/o atenciones, entonces hay colas (aunque de largo finito). A pesar de que λ<μ, es decir, de que ρ<1. Si λ>μ el sistema es inestable (colas infinitas). Es decir, las colas se deben a la variabilidad y no al hecho de que λ>μ (ρ>1).

El tiempo promedio que un cliente pasa en el sector de caja (espera + atención) (Ws): El tiempo promedio que un cliente pasa en el sector de caja corresponde al promedio de los valores de la columna “Tiempo Sistema”: Ws=8[min].

Evalúe si el proceso de llegada es estacionario: Un proceso de llegada es estacionario si el número esperado de clientes que llegan al sistema sólo depende de la longitud del intervalo de tiempo y no del tiempo de inicio del intervalo. Lo anterior por simple inspección no se cumple para el ejemplo. En este sentido se puede apreciar que en la primera media hora de observación han llegado 8 clientes (de un total de 12 clientes en la hora completa). Por tanto el sistema tiene un requerimiento mayor en el primer período de observación.

clientes-acumulados

El gráfico anterior corrobora esta conclusión. Se muestra la cantidad de clientes (acumulados) que han llegado al sistema al cabo de un determinado tiempo. La línea roja mostraría teóricamente el comportamiento de un proceso estacionario, donde un cliente llega exactamente cada 5[min]. La línea azul muestra el comportamiento real del proceso en estudio.

Reglas de Prioridad en la Programación de Trabajos con el Software LEKIN®

LEKIN® es un software gratuito e intuitivo que permite entre otras cosas la programación de n trabajos en una máquina. Este programa fue desarrollado en Stern School of Business, NYU, siendo la mayor parte de su diseño y programación a cargo de estudiantes de la Universidad de Columbia en Estados Unidos. El software LEKIN® fue creado como herramienta educacional con el propósito principal de difundir en los estudiantes conceptos de programación de trabajos y sus aplicaciones en la industria.

En el siguiente artículo detallaremos como implementar la regla de prioridad FIFO (First In First Out) o análogamente en su acrónimo en español PEPS (Primero en Entrar Primero en Salir). Para ello consideraremos un problema que consiste en la programación de 5 trabajos a una máquina, donde los tiempos de proceso son determinísticos (es decir, se asume que no hay incertidumbre respecto a la duración de cada trabajo) y el patrón de llegada es estático (Todos los trabajos llegan simultáneamente y de manera previa al inicio de las operaciones).

tabla-trabajos-con-fecha-de

Paso 1: Descargar el software LEKIN® (seleccionando Lekin.exe (1.67MB) según se muestra en la imagen) y seguir las instrucciones las instrucciones para su instalación.

descargar-lekin

Paso 2: Una vez instalado el programa y dadas las características de nuestro ejemplo, en el Menú Principal debemos seleccionar “Single Machine” (Una Máquina).

main-menu-lekin

Paso 3: A continuación ingresamos la cantidad de trabajos que necesitamos programar. En nuestro ejemplo son 5 trabajos. Luego seleccionamos “OK”.

single-machine-lekin

Paso 4: Ingresamos los datos de los trabajos en la interfaz que se muestra a continuación. Notar que hemos editado el nombre o etiqueta que identifica el trabajo (Job ID) el Tiempo de Procesamiento (Processing Time) y la Fecha de Entrega (Due Date). Al presionar “OK” se puede repetir el procedimiento para el resto de los trabajos.

add-jobs-lekin

Paso 5: En el menú del programa seleccionamos “Schedule” ==> “Rule” ==> “4 FCFS” (FCFS es equivalente a FIFO o PEPS).

fcfs-lekin

LEKIN® genera una Carta Gantt donde se muestra la programación de los trabajos y el tiempo total o makespan para concluir la totalidad de éstos (80 días). Adicionalmente según se aprecia en “Job Pool” se detalla el día en que se da inicio y término a cada uno de los trabajos.

carta-gantt-lekin

Paso 6: Finalmente en el Menú “Tools” (Herramienta) ejecutamos la opción “Performance”.

tools-lekin

Esto permite obtener un cuadro resumen con los principales indicadores de gestión de la programación según se observa en la imagen:

shop-perfomance-lekin

De donde se corrobora los siguientes resultados según lo obtenido previamente en el artículo: Reglas de Prioridad para la Programación de n Trabajos en una Máquina.

  • Tiempo de Flujo Promedio = 245[días]/5[trabajos]=49[días/trabajo]
  • Tiempo de Atraso Promedio = 108[días]/5[trabajos]=21,6[días/trabajo]
  • Atraso Máximo = 40[días]
  • Número de Trabajos Atrasados = 3[trabajos]
  • Makespan = 80[días]

Conclusiones: El software LEKIN® puede ser utilizado tanto para la aplicación de otras reglas de prioridad en el contexto del ejemplo anterior (según se puede apreciar en el Paso 5 de este tutorial) como también en otras problemáticas relativas a la Programación de Tareas. Una de las ventajas del programa es que su distribución es gratuita y además resulta ser compatible aún con las versiones más recientes de Windows (teniendo en cuenta que su última actualización data de Abril de 2002). Lo anterior ha sido corroborado en la utilización de este software sin inconvenientes en un computador con sistema operativo Windows 7 Home Premium de 64 bits. Lo anterior constituye una ventaja en comparación a otras herramientas como WINQSB que requiere el uso de máquinas virtuales si se desea utilizar en versiones recientes del sistema operativo Windows.

Actualización (Febrero 2017): Se dispone de una versión más reciente del software LEKIN® que la utilizada en este tutorial y cuya fecha de actualización corresponde al mes de Octubre de 2010 y puede ser descargada en el siguiente enlace: Descargar LEKIN® (2010).

Qué es la Ley de Little y su aplicación en Líneas de Espera

La Teoría de Colas o Líneas de Espera hace uso de modelos matemáticos para encontrar un balance adecuado entre el nivel de servicio ofrecido a los clientes y los costos asociados a su prestación. El objetivo es reducir el impacto desfavorable de la espera de los clientes o usuarios de un sistema a niveles tolerables.

Notar que la tolerancia de un cliente a la espera depende de muchos factores que resulta imposible enumerar de forma exhaustiva, incluso en un análisis introspectivo se puede apreciar que nuestra propia tolerancia no es rígida y se ve afectada por condiciones del ambiente, congestión del sistema, temperatura, urgencia, etc.

Una descripción general de la estructura de los modelos que representan lo que sucede en un proceso o línea de espera es la siguiente:

  1. Clientes con una fuente de entrada (población finita o infinita). Una población finita se refiere a un conjunto limitado de clientes que usarán el servicio y en ocasiones formarán una línea. Por el contrario una población infinita es lo bastante grande en relación con el sistema de servicio.

  2. Clientes entran al sistema y se unen a una cola (tiempo entre llegada de clientes). Por lo general se supone que el tiempo entre llegada de clientes se distribuye de forma exponencial. No obstante se puede corroborar lo anterior a través de un ajuste de curva para lo cual se puede utilizar software estadístico como Easyfit.

  3. Se proporciona el servicio (tiempos de servicio) por un servidor (uno y/o múltiples servidores) a un miembro de la cola, según una disciplina de servicio (disciplina de la cola). La disciplina de la cola más común es FIFO, es decir, se atiende por orden de llegada.

  4. El cliente sale del sistema.

En este contexto uno de los escenarios más sencillo para el análisis es aquel donde existe una fase de servicio, un único servidor, con una fuente de entrada infinita y una longitud permisible de la fila ilimitada.

linea-de-espera-un-servidor

Ley de Little

Un importante resultado matemático es el demostrado por John Little en 1961, el cual relaciona las siguientes variables:

L : Número promedio de clientes en un sistema
W : Tiempo promedio de espera en un sistema
λ : Número promedio de clientes que llegan al sistema por unidad de tiempo

Luego la Ley de Little establece que el número promedio de clientes en un sistema (L) es igual a la tasa promedio de llegada de los clientes al sistema (λ) por el tiempo promedio que un cliente esta en el sistema (W).

formula-ley-de-little

La fórmula es válida para sistemas y para subsistemas, es decir:

formula-ley-de-little-esper

Donde Lq es el número promedio de clientes que esperan en la fila y Wq el tiempo promedio que un cliente espera en la fila. Adicionalmente µ representa el ritmo del servicio o capacidad del sistema.

Ejemplo Ley de Little

Un pequeño banco está considerando abrir un servicio para que los clientes paguen desde su automóvil. Se estima que los clientes llegarán a una tasa promedio de 15 por hora. El cajero que trabajará en la ventanilla puede atender a los clientes a un ritmo promedio de uno cada tres minutos. Suponiendo que el patrón de llegadas es Poisson y el patrón de servicios es Exponencial, encuentre:

La utilización promedio del cajero:

utilizacion-cajero

El número promedio de clientes en la línea de espera es:

Lq-ley-de-little

El número promedio de clientes en el sistema:

Ls-ley-de-little

El tiempo promedio de la espera en la fila:

Wq-ley-de-little

El tiempo promedio de espera en el sistema:

Ws-ley-de-little

En el libro de Investigación de Operaciones de Hamdy Taha se puede encontrar un archivo en formato Excel que permite automatizar este tipo de cálculos y que facilita el análisis de las líneas de espera. El archivo lo puedes descargar aquí: Formulas Sistemas de Espera.

Para la utilización de la planilla se deben completar los datos de entrada (Input Data) y se obtienen automáticamente los resultados que son consistentes con lo detallado anteriormente.

salida-planilla-linea-de-es

El ejemplo que hemos presentado ha sido obtenido del Libro de Administración de Operaciones duodécima edición de los autores Chase, Jacobs y Aquilano el cual puede ser adquirido a través del siguiente enlace:

Reglas de Prioridad para la Programación de n Trabajos en una Máquina

En la Programación de Trabajos en una máquina se pueden implementar distintas políticas o reglas de prioridad que en particular buscan mejorar el desempeño de la programación en un indicador en particular (minimizar la cantidad de trabajos atrasados, minimizar el atraso promedio, minimizar el atraso máximo, minimizar el tiempo de flujo promedio, etc), sin embargo, el makespan o tiempo requerido para completar los trabajos será idéntico independiente de la regla de prioridad.

A continuación mediante un ejemplo mostraremos la aplicación de las reglas de prioridad más comunes en la programación de 5 trabajos. Asumiremos para efectos prácticos que los tiempos de proceso y fechas de entrega se expresan en días y son fijos, es decir, no existe incertidumbre en cuanto a su duración:

tabla-trabajos-con-fecha-de

FIFO (First In First Out)

Es una de las reglas de prioridad más utilizada y considera atender los trabajos según orden de llegada. En nuestro ejemplo consideraremos que los trabajos fueron recibidos en el siguiente orden: A, B, C, D, E.

FIFO

  • Tiempo de Flujo Promedio = 245[días]/5[trabajos]=49[días/trabajo]
  • Tiempo de Atraso Promedio = 108[días]/5[trabajos]=21,6[días/trabajo]
  • Atraso Máximo = 40[días]
  • Número de Trabajos Atrasados = 3[trabajos]

LIFO (Last In First Out)

Se atienden los trabajos en orden inverso al orden de llegado. En este caso E, D, C, B y finalmente A.

LIFO

  • Tiempo de Flujo Promedio = 235[días]/5[trabajos]=47[días/trabajo]
  • Tiempo de Atraso Promedio = 73[días]/5[trabajos]=14,6[días/trabajo]
  • Atraso Máximo = 30[días]
  • Número de Trabajos Atrasados = 4[trabajos]

SPT (Shortest Processing Time)

Los trabajos se procesan en orden creciente de tiempo de proceso.

SPT

  • Tiempo de Flujo Promedio = 180[días]/5[trabajos]=36[días/trabajo]
  • Tiempo de Atraso Promedio = 50[días]/5[trabajos]=10[días/trabajo]
  • Atraso Máximo = 35[días]
  • Número de Trabajos Atrasados = 3[trabajos]

LPT (Largest Processing Time)

Los trabajos se procesan en orden decreciente de tiempo de proceso.

LPT

  • Tiempo de Flujo Promedio = 300[días]/5[trabajos]=60[días/trabajo]
  • Tiempo de Atraso Promedio = 133[días]/5[trabajos]=26,6[días/trabajo]
  • Atraso Máximo = 58[días]
  • Número de Trabajos Atrasados = 4[trabajos]

EDD (Earliest Due Date)

Los trabajos se atienden por fecha de entrega.

EDD

  • Tiempo de Flujo Promedio = 215[días]/5[trabajos]=43[días/trabajo]
  • Tiempo de Atraso Promedio = 55[días]/5[trabajos]=11[días/trabajo]
  • Atraso Máximo = 30[días]
  • Número de Trabajos Atrasados = 2[trabajos]

Por supuesto existen otros criterios que permiten secuenciar «n« trabajos en una máquina y cada uno de ellos se debe evaluar en su merito. En nuestro ejemplo podemos apreciar lo que generalmente ocurre en este tipo de procedimientos respecto a que es difícil encontrar una regla de prioridad que en términos comparativos sea mejor que las restantes en todos los indicadores.

En consecuencia, el tomador de decisiones deberá privilegiar aquel indicador que en su caso en particular resulte ser más crítico. Por ejemplo, si se busca la menor cantidad de trabajos atrasados podría seleccionar EDD, sin embargo, si lo más importante es el tiempo de flujo promedio podría seleccionar SPT. Notar finalmente que independiente de la regla de prioridad utilizada el makespan es de 80[días].