Algoritmo de Johnson

En la industria, la regla de Johnson se ha aplicado con gran éxito para minimizar el tiempo de procesamiento global.

La regla de Johnson es un algoritmo heurístico utilizado para resolver situaciones de secuenciación de procesos que operan dos o más órdenes ( operaciones) que pasan a través de dos máquinas o centros de trabajo. Su principal objetivo es minimizar el tiempo de procesamiento total del grupo de trabajos.

Para resolver, se debe listar todos los trabajos con su tiempo de procesamiento en cada máquina, luego seleccionamos el tiempo de procesamiento más corto, si un trabajo tiene un tiempo de procesado corto en la máquina 1, debe ir al principio del programa, mientras que un trabajo con un tiempo corto en la segunda máquina debe ser programado al final del programa, una vez se programa un trabajo, sea al inicio o al final, este se elimina de la lista inicial.

Cuando existan más de 3 máquinas se procede de la siguiente manera: ubicar los tiempos en una máquina que se encuentren dominados por los tiempos de las otras máquinas, es decir, aquellos tiempos que sean menores a los otros tiempos de otras máquinas. Luego, esos tiempos dominados se suman a los tiempos en las otras máquinas, obteniendo tiempos para máquinas M1' y M2'. Si no existen tiempos dominados, se puede resolver igual con otros tiempos, aunque no se garantice el óptimo pero sí será bueno.