Johnson Archivos - Gestión de Operaciones

Método de Johnson (Ejercicio Resuelto)

El Método de Johnson permite determinar una secuencia u orden para realizar trabajos en un taller que considera 2 máquinas, donde todos los trabajos siguen un orden común (por ejemplo, primero se ejecutan labores en una máquina 1 y luego en una máquina 2), asumiendo que todos los trabajos se encuentran disponibles para su programación al inicio del horizonte de evaluación y que los tiempos requeridos para pasar por cada máquina son conocidos (es decir, se asume que no existe incertidumbre). De esta forma se busca determinar el tiempo mínimo para completar los trabajos en el taller lo cual se conoce como makespan. En este contexto a continuación se presenta un ejemplo resuelto del Método o Algoritmo de Johnson.

Ejercicio Resuelto del Método de Johnson

Una imprenta se dedica a la copia y encuadernación de documentos. Esta mañana recibió los trabajos que se muestran a continuación, todos los cuales requieren ambas operaciones en ese orden:

La imprenta comienza a trabajar puntualmente a las 09:00 y no se detiene hasta que termina de procesar todos los trabajos. La hora de entrega para todos los trabajos corresponde a las 13:00. Determine una secuencia de manera que el tiempo que tardan en ser procesados los trabajos sea el menor posible, esto es minimizando el makespan. Construya una Carta Gantt para complementar su respuesta.

Este problema trata de máquinas en paralelo sin interrupción con trabajos cuyo tiempo de proceso es determinista y la llegada al comienzo (estática), de modo que se puede aplicar el Algoritmo de Johnson.

El tiempo más breve corresponde al trabajo A en encuadernación, por tanto se asigna en primer lugar y se ejecuta al final de la secuencia. Luego el tiempo más breve es para el trabajo B en encuadernación, siendo este trabajo asignado en segundo lugar y ejecutado penúltimo. De los trabajos remanentes el tiempo más breve es 40[min] existiendo un empate en encuadernación (trabajo C) y copia (trabajo E). En caso de empate el Método de Johnson establece que se prioriza la máquina 1 (en este caso copia) y por tanto E se asigna en tercer lugar y se ejecuta primero. A continuación naturalmente se asigna el trabajo C en cuarto lugar y se ejecuta antepenúltimo. El quinto trabajo en asignar será el D el cual se realiza inmediatamente antes del trabajo C (al tener su menor tiempo en encuadernación). Finalmente se asignan los trabajos F y G (en ese orden) ejecutándolos en segundo y tercer lugar, respectivamente. De esta forma la secuencia es:

E-G-F-D-C-B-A

El makespan para este problema de Programación de Trabajos es de 440 minutos, terminando de atender el último trabajo a las 16:20.

En relación a los resultados obtenidos anteriormente determine: ¿A qué hora se termina de atender el último trabajo?, ¿Cuántos trabajos atrasados tiene la imprenta?, ¿Cuál es el tiempo de flujo promedio?, ¿Cuál es el atraso promedio?, ¿Cuál es el atraso máximo?.

Para responder a esta pregunta confeccionamos una tabla resumen la cual se basa en los resultados obtenidos a través de la Carta Gantt y los horarios de entrega de los trabajos.

Total Atrasos: 5 (Trabajos A, B, C, D y F)
El último trabajo se termina de atender a las 16:20 (Trabajo A)
Tiempo de Flujo Promedio: 06:01
Atraso Promedio: 1:48
Atraso Máximo: 3:20

Cabe recordar que el Tiempo de Flujo (TF) corresponde al tiempo total que cada trabajo se encuentra en el taller, es decir, esto es la suma del tiempo de espera más el tiempo de atención o procesamiento en las distintas máquinas. Por ejemplo si bien el trabajo A requiere en total un tiempo de 30[min] éste comienza a ser atendido recién a las 15:20 en copia, terminando a las 16:20 en encuadernación (total 60[min] o 1[hora]). Adicionalmente el trabajo A debe esperar 7 horas con 5 minutos (es decir, de las 08:15 a las 15:20) para comenzar su atención en copia. Luego el Tiempo de Flujo es 1:00+7:05=8:05 (8 horas y 5 minutos).

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: