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:

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

edd-algoritmo-de-moore

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

algoritmo-de-moore-final

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

carta-gantt-algoritmo-de-mo

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.