programación de trabajos Archivos - Página 3 de 3

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.

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:

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.

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.

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.

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.

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.

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

Regla de Jackson en la Programación de n Trabajos en 2 Máquinas

A diferencia de la Regla de Johnson aplicable a la programación de n trabajos en 2 máquinas bajo un esquema de atención fijo (es decir, los trabajos siguen siempre el mismo orden, por ejemplo primero pasan por la máquina A y luego por la máquina B), la Regla de Jackson (Método de Jackson) permite generar una Programación de Trabajos cuando la secuencia de dichos trabajos es aleatoria, es decir, se elimina el supuesto de que los trabajos siguen la misma secuencia.

En este contexto el Método de Jackson considera los siguientes pasos:

Paso 1: Clasificar los trabajos existentes en las 4 familias posibles: Los que requieren sólo la máquina 1 (A) – Los que requieren sólo la máquina 2 (B) – Los que pasan primero por máquina 1 y luego la 2 (AB) – Los que pasan primero por máquina 2 y luego la 1 (BA).
Paso 2: Ordenar los trabajos de (AB) y (BA) aplicando la Regla de Johnson.
Paso 3: Ordenar los trabajos de (A) y (B) en forma arbitraria.
Paso 4: Programar en la máquina 1 en primer lugar los trabajos de (AB), luego los trabajos en (A) y finalmente los trabajos en (BA).
Paso 5: Programar en la máquina 2 en primer lugar los trabajos de (BA), luego los trabajos en (B) y finalmente los trabajos en (AB).

Ejemplo Regla de Jackson

A continuación se presenta un ejemplo donde se deben programar 10 trabajos que tienen los siguientes tiempos y secuencias (Paso 1):

Paso 2: Los trabajos que siguen la secuencia A-B son el 1, 5, 6 y 9. El trabajo 9 es el más breve es en la máquina A por tanto se asigna y ejecuta en primer lugar. El trabajo 1 y 6 siguen con el tiempo más breve (10), sin embargo, el criterio de desempate nos indica que el trabajo 6 se asigna y ejecuta en segundo lugar. Posteriormente el tiempo más breve es en el trabajo 1 (máquina B) por lo cual se asigna este trabajo en tercer lugar y se ejecuta al último. La secuencia por tanto de los trabajos que siguen el orden A-B es: 9-6-5-1. Análogamente, siguiendo un procedimiento similar, los trabajos que siguen la secuencia B-A se ordenan 3-7-10 según la Regla de Johnson.

Paso 3: Los trabajos que sólo requieren la máquina A son el 2 y 8. De forma arbitraria seleccionaremos la secuencia 8-2. Finalmente existe un único trabajo que sólo requiere de la máquina B (trabajo 4).

Paso 4: La programación para la máquina A es: (9-6-5-1)-(8-2)-(3-7-10)

Paso 5: La programación para la máquina B es: (3-7-10)-(4)-(9-6-5-1)

Se propone a nuestros usuarios desarrollar una Carta Gantt considerando la secuencia anterior para ambas máquinas que permita encontrar el makespan asociado a dicha programación.

Regla de Johnson en la Programación de n Trabajos en 2 Máquinas

Una de las variantes de la Programación de Tareas es la asignación de 2 máquinas al procesamiento de n trabajos siguiendo un orden común. Una estrategia a aplicar es la Regla o Método de Johnson con el objetivo de minimizar el tiempo requerido para finalizar los n trabajos en el taller de trabajo (conocido también como makespan).

El Método de Johnson considera los siguientes pasos:

Se anota el tiempo de operación de cada trabajo en ambas máquinas.
Se elige el tiempo más breve.
Si el tiempo breve es para la primera máquina, se hace el primer trabajo; si es para la segunda máquina, se hace el trabajo al último. En caso de empate (igualdad de tiempo) se hace el trabajo en la primera máquina.
Repetir los pasos 2 y 3 con los restantes trabajos hasta completar la programación.

Ejemplo Método de Johnson

A continuación se presenta un ejemplo que considera 7 trabajos a programar en 2 máquinas. Para que un trabajo sea terminado debe pasar primero por la máquina A y luego por la máquina B. Nos interesa aplicar la Regla de Johnson para generar una asignación que tenga asociado el menor tiempo posible (en minutos) en procesar los 7 trabajos:

Paso 1: Listo. Tiempos de procesamiento disponibles en la tabla.

Paso 2, 3 y 4: Se elige el tiempo más breve (Trabajo 4 Máquina B). Como el tiempo más breve es en la segunda máquina, el Trabajo 4 se hace al final. El siguiente tiempo más breve es en el Trabajo 7 Máquina A y se programa en primer lugar. Luego el Trabajo 6 y 1 tienen el tiempo más breve que sigue (10), sin embargo, dado el empate se hace el trabajo en la Máquina A y por tanto se programa el Trabajo 6 en segundo lugar. Ahora tomamos el Trabajo 1 y siendo su menor tiempo en la Máquina B se programa en penúltimo lugar. Sigue el Trabajo 2 el cual se programa en tercer lugar. Posteriormente el Trabajo 3 en antepenúltimo lugar y finalmente el Trabajo 5 en cuarto lugar.

La secuencia óptima luego de aplicar la Regla de Johnson sería: 7-6-2-5-3-1-4. Luego, para determinar el tiempo requerido para completar los 7 trabajos se puede construir una Carta Gantt que muestre dicha planificación. El tiempo requerido es de 119 minutos (makespan).

El software WINQSB entre sus distintas aplicaciones nos permite generar una programación de los trabajos siguiendo el Método de Johnson según se muestra en el siguiente tutorial: