VISUAL THINKING CHECKLIST

Reversibilidad

Las principales características son:

fLOW SHOPS

El Makespan no cambia si los trabajos atraviesan el taller de flujo en la dirección opuesta en orden inverso.

• m máquinas, n trabajos.
• Un trabajo consiste de operaciones, que se realizan en cada máquina.
• Los trabajos se procesan en serie en las máquinas, cada trabajo tiene la misma ruta de máquinas.
• El tiempo de procesamiento del trabajo j en la máquina i es pij.

Representación

fm|block|cmax

F2||Cmax

fm|prmu,pij=pj|cmax

fm|no-wait|cmax

Fm|prmu|cmax

Corresponde al caso con almacenamiento intermedio 0 que bloquea la maquina hasta que la siguiente esté disponible.

F2|nwt|Cmax (no-wait)

El tiempo de procesamiento no cambia entre máquinas y se encuentra que el makespan es:

Mantienen la misma permutación en todas las máquinas, usando la regla FCFS(Firts-come-first-served). Los tiempos de terminación se pueden calcular así:

Cuenta con algoritmo que corre en t polinomial usando el algoritmo de Johnson que consiste en:

Este modelo es comparable a F2|block|Cmax

Notación:

• D_ij: : tiempo en que el trabajo j sale de la máquina i
• D_0j: tiempo en que el trabajo j comienza a ser procesado en la máquina 1

Dividir los tabajos en dos grupos

No-wait significa que el almacenamiento intermedio es limitado.

• Es NP-hard
• F2||Cmax y F3||Cmax mantienen el orden de las máuinas
• f3|prmu|Cmax es NP-hard en sentido estricto

Trabajos con p1j ≤ p2j

El min Cmax es equivalente al problema del agente viajero con n+1 ciudades y se puede resolver con los mismos métodos.

El Flow Shop con tiempos proporcionales tiene similitudes a las configuraciones de 1 máquina, que se muestran a continuación.

Dentro de los metodos para solucionarlo estan:

Formulación matemática

Trabajos con p2j ≤ p21

Ruta más larga

Prog Entera Mixta

Grafo dirigido

Huerística Slope

Fm|nwt|Cmax

Secuencia SPT(1)-LPT(2)

Al igual que el Fm|prmi|Cmax se puede solucionar con un grafo ajustado

Este problema se puede formular como un TSP, con distancias:

• Se calcula el ìndice Slope por trabajo

Se puede representar en un grafo dirigido y buscando la ruta mas larga para encontrar el Cmax

Se puede proponer un modelo que minimice el tiempo de inactividad de la máquina m con la siguiente FO:

Hacer secuencia SPT

Heurítica Porfile fitting

Hacer secuencia LPT

• Se selecciona el trabajo que va a ir primero (menor tiempo)
• Se prueba los trabajos que generan menos inactividades
• Si todos los trabajos se han asignados termina

Para que el grafico se pueda correr en tiempo polinomial debe:

• Secuenciar los trabajos en orden decreciente del índice calculado

Y se transforma en la siguiente formulación:

• Ser aciclico
• Tener arcos negativos y calcular ruta mas corta

• Si existen valores iguales hay optimos alternos

Formulación matemática