Secuenciacion de n trabajos en multiples centros de trabajo

SECUENCIA DE N TRABAJOS EN MÚLTIPLES CENTROS DE TRABAJO

Se considera el problema (n/múltiples/F/F) consistente en secuenciar n trabajos (n>1) en múltiples centros de trabajo o maquina.

ALGORITMO DE JOHNSON

Considere el problema de secuenciación (n/2/F/Fmax) consistente en ordenar n trabajos seriados independientes en 2 maquinas tal que minimice el tiempo de fluido máximo; cada trabajorequiere de dos procesos secuenciales distintos, realizándose el primero en una maquina y el siguiente en la otra. La secuencia de los procesos no se altera.

Sea t [ij] el tiempo de proceso j (j=1,2), del trabajo i, (1, 2,…,n). el algoritmos que resuelve este problema, diseñado por Jonson prosigue de la siguiente manera:

1.- Sea k = 1 y p = n.
2.- Encuentre el mínimo t [ij]. Si este ocurrepara j=1 se le hace t [k] , 1 y t [k],2 se elimina del análisis posterior. Si, por el contrario el mínimo t [ij] ocurre para j=2, se le hace t [p],1 y t [p],2 . Se elimina del análisis posterior.
3.- Con los t [ij] restantes se repite el procedimiento del paso anterior haciendo k= k+1, o
p=p-1 si j=2. los empates se resuelven arbitrariamente. El algoritmo termina en n iteraciones.

EjercicioSeis trabajos deben pasar por dos maquinas herramientas diferentes, pero la secuencia tecnológica es diferente. Los tiempos de proceso son:

Trabajo (i) 1 2 3 4 5 6
Maquina 1 4 8 1 7 4 5
Maquina 2 6 2 3 9 2 10

Los tiempos de proceso están dados en horas. Calcular la secuencia aplicando el algoritmo de Johnson.

Solución

Iteración 1
1.- Sea k =1 y p =6
2.- El mínimo valor tijcorresponde a t31 = 1. Como j =1, se asigna el primer lugar (k =1) al tercer trabajo.
3.- Se elimina el tercer trabajo del análisis.

Iteración 2
1.- Sea k =2 y p =6
2.- El mínimo valor tij corresponde a t52 = 2. Como j =2, se asigna el sexto lugar (p =6) al quinto trabajo.
3.- Se elimina el quinto trabajo del análisis.

Iteración 3
1.- Sea k =2 y p =5
2.- El mínimo valor tij corresponde at22 = 2. Como j =2, se asigna el quinto lugar (p =5) al segundo trabajo.
3.- Se elimina el segundo trabajo del análisis.
Iteración 4
1.- Sea k =2 y p =4
2.- El mínimo valor tij corresponde a t14 = 4. Como j =1, se asigna el segundo lugar (k =2) al primer trabajo.
3.- Se elimina el primer trabajo del análisis.

Iteración 5
1.- Sea k =3 y p =4
2.- El mínimo valor tij corresponde a t61 = 1.Como j =1, se asigna el tercer lugar (k =3) al sexto trabajo.
3.- Se elimina el sexto trabajo del análisis.

Entonces la secuencia óptima es: {3, 1, 6, 4, 2, 5}

Algoritmo de Jonson, n trabajos en 3 maquinas o Centros de Trabajo

El algoritmo de Jonson sirve para resolver un caso particular de problema de secuenciación (n/3/F/Fmáx) correspondiente a n trabajos en 3 maquinas. Laparticularidad del caso la proporciona las siguientes condiciones:

Min  t [i1] Max  t [ij2] i= 1, …, n
Ó
Min  t [i3] Max  t [i2] i= 1, …, n

Ejercicio

Encuentre la secuencia óptima del siguiente problema (5 / 3 / F / F máx.) cuyos datos se proporcionan a continuación, aplicando el algoritmo de Johnson.

Tiempo de proceso en horas
Trabajo (i) Maquina 1 Maquina 2 Maquina3
1 8 3 2
2 6 4 5
3 4 2 6
4 9 1 4
5 5 3 9

Solución

(5 / 3 / F / F máx.); Min {ti1} ≥ Máx { ti2} ó Min { ti3} ≥ Máx{ ti2} cuando i =1,…,n
Como Min {ti1} = 4 ≥ Máx { ti2} = 4, se puede utilizar el algoritmo de jhonson

Trabajo (i) Pro. A( Maq. 1+Maq. 2) Pro. B( Maq. 2+Maq. 3)
1 11 5
2 10 9
3 6 8
4 10 5
5 8 12
Tabla

Iteración 1
1.- k = 1, p = 5
2.- min tij es t42 = 5. Como j=2, se asigna el quinto lugar (p =5) al cuarto trabajo.

Iteración 2
1.- k = 1, p = 4
2.- min tij es t12 =5. Como j =2, se asigna el cuarto lugar (p =4) al primer trabajo.

Iteración 3
1.- k = 1, p = 3
2.- min tij es t31 =6. Como j =1, se asigna el primer lugar (k =1) al tercer trabajo.

Iteración 4
1.- k = 2, p = 3
2.- min tij es t51 =8. Como j =1, se asigna el segundo lugar (k =2)...