Resumen

En este documento, estudiamos la resolución de un problema de flujo de trabajo de permutación con tiempo de preparación independiente de la secuencia. El objetivo es minimizar el máximo tiempo de finalización de trabajos, también llamado makespan. En esta contribución, proponemos tres métodos de resolución: un modelo de programación lineal entera mixta (MILP); dos heurísticas, la primera basada en la regla de Johnson y la segunda basada en el algoritmo NEH; y finalmente, dos metaheurísticas, el algoritmo de búsqueda local iterativo y el algoritmo codicioso iterado. Se simula un conjunto de problemas de prueba numéricamente para validar la efectividad de nuestros enfoques de resolución. Para problemas de tamaño relativamente pequeño, se ha revelado que la heurística NEH adaptada tiene un mejor rendimiento que la heurística basada en Johnson. Para problemas de tamaño mediano y grande, el estudio comparativo entre las dos metaheurísticas basadas en la exploración del vecindario muestra que el algoritmo codicioso iterado registra los mejores rendimientos.

• Materias:Modelo Matemático Simulación numérica Fraccionarios lineales Operadores diferenciales Matriz de transición
• Subjects:Mathematical model Numerical simulation Linear fractional Differential operators Transition matrix
• Palabras claves:Problema de flujo en tienda de permutación; Tiempo de preparación independiente de la secuencia; Tiempo de ejecución; Modelo de programación lineal entera mixta (MILP); Regla de Johnson; Algoritmo NEH
• Keywords:Permutation flow shop problem; Sequence-independent setup time; Makespan; Mixed-integer linear programming (MILP) model; Johnsons rule; NEH algorithm