reglas de prioridad Archivos - Gestión de Operaciones

Regla de la Razón Crítica

La Regla de la Razón Crítica (conocido en inglés por CR o Critical Ratio) es una heurística que permite la secuenciación de trabajos en una máquina. El criterio que establece la Regla de la Razón Crítica es que los trabajos se deban procesar en orden creciente de acuerdo al cuociente ente el tiempo que falta a la entrega y el tiempo de proceso (recomendamos al lector revisar el artículo Reglas de Prioridad para la Programación de n Trabajos en una Máquina donde se detalla a través de un ejercicio resuelto la aplicación de otras heurísticas típicas de la programación de operaciones).

En este contexto la fórmula para el cálculo del ratio crítico es:

Ejemplo Regla de la Razón Crítica (Ratio Crítico)

Hoy es el día 22 en un centro de trabajos y 4 trabajos están esperando ser atendidos en una máquina. La máquina puede procesar sólo un trabajo a la vez. Determine el ratio crítico para cada trabajo y establezca un ranking de prioridad para su procesamiento.

Por ejemplo, el trabajo A tiene como fecha de entrega el día 28 y requiere 8 días de proceso en la máquina.

Utilizando la Regla de la Razón Crítica los trabajos deben ser asignados en la siguiente secuencia: D, A, C, B. Se puede observar que sólo el trabajo B tiene holgura (esto debido a que su CR es mayor a 1). Por otra parte los trabajos A y D tienen ratios críticos menores a 1, lo cual significa que dichos trabajos no serán terminados a tiempo a menos que sean apurados. Finalmente el trabajo C tiene un ratio crítico igual a 1 que implica que podría ser terminado a tiempo en la medida que sea el primer trabajo en ser considerado en la secuencia (situación que no es la que ocurre en este caso).

Cabe recordar que los resultados propuestos al utilizar distintas reglas de prioridad deben ser analizados en virtud de su desempeño y en lo general no existe una regla que garantice el mejor desempeño en todos los aspectos.

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

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.

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

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

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.

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

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.

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

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

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

Algoritmo de Moore aplicado a la Programación de Trabajos

En el contexto de las Reglas de Prioridad para Programar n trabajos en una Máquina, el Algoritmo de Moore tiene por objetivo minimizar el número de trabajos atrasados, independientemente de cuán atrasados estén.

Este criterio es especialmente útil cuando existen penalizaciones por concepto de atraso, las cuales en algunas ocasiones se activan por el hecho de no responder a tiempo una fecha de entrega comprometida aun cuando el atraso en su magnitud pudiese haber sido mínimo. La descripción general del algoritmo consta de 4 pasos según se describe a continuación:

Algoritmo de Moore

Paso 1. Ordenar los trabajos de acuerdo a la regla de prioridad EDD (Earliest Due Date o Fecha de Entrega más Próxima).
Paso 2. Seleccionar el primer trabajo atrasado en la secuencia actual, digamos el trabajo i. Si no hay ninguno atrasado siga al Paso 4.
Paso 3. Considere los trabajos 1 al i. Rechace el trabajo con mayor tiempo de proceso, vuelva al Paso 2.
Paso 4. Forme la secuencia que resulta de tomar la secuencia actual y colocar todos los trabajos rechazados al final.

Si luego de realizar la primera iteración del Algoritmo de Moore existe un nuevo trabajo atrasado (asumiendo que en la iteración 1 se rechazo un trabajo, digamos trabajo A), dicho trabajo se rechaza (digamos trabajo B) y se envía al «final de la secuencia», entendiendo por ello que desde la perspectiva del número de trabajos atrasados (objetivo del algoritmo) resulta indistinto que la secuencia final termine con A-B o con B-A. Si fuese necesario realizar una tercera iteración (o más) se procede bajo el mismo criterio.

Ejemplo Algoritmo de Moore en Programación de Trabajos

Consideremos el siguiente ejemplo en el cual se deben programar 6 trabajos en una máquina, donde se ilustra la aplicación del Algoritmo de Moore:

Paso 1. Ordenamos los trabajos según la regla de prioridad EDD obteniendo la secuencia B-A-E-D-C-F (notar que los trabajos se secuencian desde el que tiene fecha de entrega más próxima al que tiene fecha de entrega más lejana).

Paso 2. Seleccionamos el primer trabajo atrasado en la secuencia actual (al que llamaremos trabajo «i«). En el ejemplo dicho trabajo corresponde a E.

Paso 3. Consideramos los trabajos del 1 al i (en el ejemplo de B a E) y rechazamos el que tiene mayor tiempo de proceso (en el ejemplo el trabajo A).

Paso 4. En la secuencia actual colocar los trabajos rechazados al final. De esta forma la nueva secuencia sería B-E-D-C-F-A que por supuesto tiene idéntico makespan (23[días]) y sólo un trabajo atrasado (trabajo A).

La Carta Gantt para la secuencia propuesta por el Algoritmo de Moore es la siguiente:

Se propone al lector aplicar otras reglas de prioridad (por ejemplo FIFO, LIFO, SPT, LPT, EDD, etc) y corroborar que el Algoritmo de Moore permite efectivamente minimizar el número de trabajos atrasados en el contexto de las características del problema anterior.

Por cierto pueden existir otras reglas de prioridad que permitan tener un trabajo atrasado para el ejemplo propuesto, sin embargo, no debiésemos esperar que exista una secuencia que omitamos que evite tener trabajos atrasados.