Problemas Algoritmos Johnson

PROBLEMAS DEL ALGORITMO JHONSON

Algoritmos para resolver el problema Job-Shop.

Los algoritmos heurísticos permiten encontrar soluciones aproximadas a la solución exacta, con la característica que la solución aproximada es encontrada en un tiempo mucho menor al de la solución exacta o teórica, lo cual permite que la solución heurística pueda ser calculada en un tiempo razonable. Los algoritmos heurísticos más comunes son Temple Simulado, Búsqueda Tabú, Algoritmos Genéticos, Búsqueda en Vecindarios Variables, Optimización de Colonias de Hormigas, Búsqueda Dispersa y Algoritmo de Jackson.

De todas las soluciones anteriores, la solución más utilizada, dada su sencillez de utilización es el algoritmo de Jackson.

Algoritmo de Jackson

Solución del Jobshop con algoritmo de Jackson

N trabajos en 2 máquinas.

• Formar 4 sets de trabajos;

• {A} = Los procesados solamente en la máquina 1.

• {B} = Los procesados en máquina 2 solamente.

• {AB} = Los procesados primero en máquina 1 y luego en la 2.

• {BA} = Los procesados primero en máquina 2 y luego en la 1.

• Secuenciar los trabajos de {AB} y {BA}, por separado, con algoritmo de Johnson.

• Defina secuencias arbitrarias para los trabajos {A} y {B}.

• Combine las secuencias de la siguiente manera.

• Máquina 1: primero se ejecutan los trabajos del set {AB}.

A continuación se ejecutan los trabajos del set {A}.

Y finalmente se ejecutan los trabajos del set {BA}.

• Máquina 2: primero se ejecutan los trabajos del set {BA}.

A continuación se ejecutan los trabajos del set {B}.

Y finalmente se ejecutan los trabajos del set {AB}.

N Trabajos en 3 máquinas.

• Todos los trabajos tienen la misma secuencia de proceso.

• Puede resolverse con el algoritmo de Johnson si:

• Min {pi1} > Máx {pi2}, o

• Min {pi3} > Máx {pi2}.

• La máquina 2 es dominada completamente por la máquina 1 o 3.

• Se aplica el procedimiento formando 2 máquinas “maniquí”, 1’y 2’, con tiempos de proceso:

• pi1’ = pi1 + pi2

• pi2’ = pi2 + pi3

• El procedimiento proporciona una secuencia factible y “buena” aún cuando no se cumplan las condiciones.

Ejemplo:

Secuenciar los siguientes trabajos:

Trabajos Maq 1 Maq 2 Naq 3

1 8 2 4

2 5 4 5

3 6 1 3

4 7 3 2

A continuación se debe formar la máquina 1’ sumando los tiempos de procesamiento de la máquina 1 y la máquina 2 de todos los trabajos. Para formar la máquina 2’ se deben sumar los tiempos de procesamiento de la máquina 2 y la máquina 3 de todos los trabajos.

Trabajos Maq 1' Maq 2'

1 10 6

2 9 9

3 7 4

4 10 5

Luego a

...