Reglas de jhonson

N TRABAJOS EN UNA MAQUINA

Determinar la secuencia óptima de procesar n trabajos en una máquina.
Representemos los tiempos de proceso de los trabajos i como pi (i = 1,n).
La secuencia que minimiza el criterio es aquella en la que los trabajos se ordenan del menor tiempo al mayor.
Esta secuencia también minimiza el tiempo promedio de espera y la tardanza promedio
Cuando los trabajostienen diferente prioridad o peso, el objetivo puede ser el de minimizar el tiempo de flujo promedio ponderado. 
A mayor valor del índice, el trabajo es más importante.
La secuencia óptima sería ordenando los trabajos de menor pi/wi al mayor.

Determinar la secuencia óptima de procesar n trabajos en una máquina.
Todas las secuencias tienen el mismo makespan.
Minimizar el mean flow time es elcriterio a satisfacer.
Representemos los tiempos de proceso de los trabajos i como pi (i = 1,n).
La secuencia que minimiza el criterio es aquella en la que los trabajos se ordenan del menor tiempo al mayor.
Ésta secuencia también minimiza el tiempo promedio de espera y la tardanza promedio (mean lateness).
Cuando los trabajos tienen diferente prioridad o peso, el objetivo puede ser el deminimizar el tiempo de flujo promedio ponderado.
A mayor valor del índice, el trabajo es más importante.

[pic]La secuencia óptima sería ordenando los trabajos de menor pi/wi al mayor.
Minimizar el promedio ponderado del tiempo de flujo.
La secuencia óptima es (2, 5, 3, 6, 1,4).

TRABAJOS EN 2 MAQUINAS

Los n trabajos se procesan en 2 máquinas con el mismo orden. El criterio es el de minimizar elmakespan.
El procedimiento a utilizar es el de Johnson.
Si pij es el tiempo de proceso del trabajo i en la máquina j, seleccione el mínimo y si éste corresponde a la máquina 1, asígnelo a la primera posición de la secuencia.
Si corresponde a la máquina 2, el trabajo se asigna a la última posición de la secuencia.
Elimine el trabajo asignado del set y repita el procedimiento con los trabajosno asignados.
Procedimiento de Jonson
Determine la secuencia de proceso que minimice el makespan
[pic]

La secuencia es (2,4,5,3,1).

n Trabajos con Ruta Diferente en 2 Máquinas

Usar algoritmo de Jackson.
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: {AB} antes de {A} antes de {BA}.
Máquina 2: {BA} antes de {B} antes de {AB}.

n Trabajos en 3 Máquinas
Todos los trabajos tienen lamisma 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 dummy, 1´y 2´, con tiempos de proceso:
pi1´ = pi1 + pi2 y pi2´ = pi2 + pi3.
El procedimiento proporciona una secuencia factible y “buena” aún cuando no secumplan las condiciones
Secuenciar los siguientes trabajos.

[pic]

Secuencia óptima 
es {2, 1, 4,3}.

[pic]

N TRABAJOS EN M MÁQUINAS

No existe un método eficiente que proporcione una solución exacta.
Se utilizan métodos heurísticos tales como las Reglas de Despacho.
Éstas son reglas que determinan qué trabajo procesar al quedar éste disponible de manera secuencial en el tiempo, en lugarde suponer que todos los trabajos están disponibles.
Se maneja el concepto de prioridad en los trabajos.

Secuenciación Dinámica de Trabajos

Trabajos llegan a procesarse al azar durante un intervalo de tiempo.
Su secuencia se determina mediante el uso de reglas de despacho que proporcionan prioridades a los mismos.
Las reglas se derivan a través de análisis de líneas de espera,...