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