Regla de johnson

Secuencia de N trabajos en dos máquinas: regla de Johnson

El siguiente paso en complejidad es cuando N trabajos (donde N es 2 o más) deben pasar por dos máquinas o centros de trabajo distintos en el mismo orden. Este problema se conoce como problema N/2.

La Regla de Johnson es un método heurístico  el cual es utilizado para programar un número ‘n’ de trabajos en dos centros sucesivos del trabajo. El objetivo primario de la regla de Johnson es encontrar una secuencia óptima de trabajos de reducir la cantidad de tiempo total que toma para terminar todos los trabajos. También reduce el número del tiempo ocioso entre los dos centros del trabajo. Antes de comenzar a desarrollar ese método será necesario cumplir con 4 condiciones, si alguna de ellas no es cumplida a regla, la aplicación de este algoritmo no podrá ser realizada:

• La época para cada trabajo debe ser constante.
• Los tiempos del trabajo deben ser mutuamente exclusiva de la secuencia de trabajo.
• Todos los trabajos deben pasar a través del primer centro del trabajo antes de pasar a través del segundo centro del trabajo.
• No debe haber prioridades del trabajo.

Ahora se enunciaran los 4 pasos que componen este método:

1. Es necesario tener en consideración todos los trabajos y colocarlos en una lista, así como el tiempo requerido por cada una de ellas en cada máquina.
2. Seleccionar el trabajo con el tiempo de actividad más corto. Si el tiempo más corto está en la primera máquina, ese trabajo se programa primero. Si el tiempo más corto está en la segunda máquina, ese trabajo se programa al final. Los empates en los tiempos de actividad se pueden romper de manera arbitraria.
3. Una vez que se programa un trabajo, debe eliminarse de la lista.
4. Deben de aplicarse los pasos 2 y 3 a los trabajos restantes, trabajando hacia el centro de la secuencia.

REGLA DE JOHNSON AMPLIADA.

Para que la regla de Johnson para m maquina nos dé una solución óptima a nuestro problema será preciso que cumpla una serie de condiciones, en realidad 2 condicione

1. El tiempo de proceso más corto en la máquina 1 es >= tiempo más largo en la máquina 2

2. El tiempo de proceso más corto en la máquina 3 es >= tiempo más largo en la máquina 2

3. Si no se cumplen estas condiciones la solución es cercana a la óptima.

Para realizar una programación de n trabajos en 3 maquinas se agrega tan solo un paso extra a la metodología mencionada anteriormente, este paso consiste en:

Combinar los tiempos de procesamiento a solo 2 ‘’maquinas’’, para así obtener solo 2 ‘’Maquinas’’ y poder realizar el procedimiento de n trabajos en 2 maquinas.

Esto se lograra sumando los tiempos de procesamiento de la maquina 1 y 2, para obtener los nuevos tiempos para la ‘’Máquina 1’’ e igual, sumar los tiempos de procesamiento de las maquinas 2 y 3 para obtener los nuevos tiempos para la ‘’Máquina 2’’.

N tareas en M Máquinas

Para generalizar la regla de Johnson y abarcar las posibilidades de que haya 2 o más maquinas inmiscuidas en n numero de tareas, donde todas las tareas se procesen en todas las maquinas, se ha diseñado un algoritmo, llamado Algoritmo CDS, el cual fue  sugerido por Campbell, Dudek y Smith, este proporciona una solución cercana a la optima.

El algoritmo genera m-1 soluciones de dos maquinas, esto se refiere a que si contamos con 5 maquinas, obtendremos 4 soluciones, donde inevitablemente tendremos que programas todas las opciones para así elegir la opción que nos dé un resultado más eficiente.

Considerando un tamaño de m igual a 4, las posibles soluciones serán obtenidas de la siguiente forma:

Solución 1:

Esta solución será obtenida considerando solamente el tiempo de la primera y la ultima maquina, y así tener n trabajos sobre 2 maquinas

Solución 2:

De forma similar que se hizo en el método de n trabajos en 3 maquinas, se tomaran los tiempos de las primeras 2 maquinas, para obtener los numero de la ‘’Máquina 1’’ y los números de las ultimas 2 máquinas para obtener los de la ‘’Máquina 2’’

Solución 3:

Esta vez se tomaran los tiempos de procesamiento de las 3 primeras maquinas para obtener los tiempos de la ‘’Máquina 1’’ y de igual forma los tiempos de las ultimas 3 máquinas para obtener los tiempos de la ‘’Máquina 2’’

EJERCICIO DE N TRABAJOS EN 2 MÁQUINAS

EJEMPLO

Una fábrica  de ensamblado, tiene cinco trabajos que se deben procesar  en dos centros de trabajo, es decir 2 maquinas, una perforadora y un torno. El tiempo de procesamiento de cada trabajo son los establecidos en la tabla anterior.

Al estar el tiempo menor en la maquina 2, se pondrá el trabajo A al final de la secuencia.

...