Aplicacion de la Regla de jhonson

Aplicación de la Regla de Johnson a la programación de n trabajos en 2 máquinas
jul.28, 2011 en Programación de Trabajos
Una de las variantes de la programación de tareas es la asignación de 2má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 omakespan.
El Método de Johnson considera los siguientes pasos:
1. Se anota el tiempo de operación de cada trabajo en ambas máquinas.
2. Se elige el tiempo más breve.
3. Si el tiempo breve es parala 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.
4.Repetir los pasos 2 y 3 con los restantes trabajos hasta completar la programación.
A continuación se presenta un ejemplo que considera 7 trabajos a programar en 2 máquinas. Para que un trabajo seaterminado 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) enprocesar 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 segundamá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), sinembargo, 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 enpenú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...