Resumen de Heurísticas eficaces para el problema del taller de flujo de permutación

Rubén Ruiz García , Shahriar Farahmand Rad, Naser Boroojerdian

• La conocida heur´ýstica NEH para el problema del taller de flujo ha sido reconocida en varios estudios como el mejor m´etodo heur´ýstico para este problema.

  Una buena implementaci´on del m´etodo NEH puede dar como resultado secuencias no m´as all´a de un 3-4% de desviaci´on con respecto a la soluci´on ´optima y todo ello en apenas 30 milisegundos de tiempo de CPU en ordenadores actuales. Es por ello que la heur´ýstica NEH es la �campeona� para este problema de programaci´on de la producci´on tan com´un. En este trabajo presentamos nuevas heur´ýsticas que superan ampliamente los resultados proporcionados por la heur´ýstica NEH. Si bien todas las heur´ýsticas presentadas son ligeramente m´as lentas que la NEH pero dan resultados de mucha mejor calidad. Adem´as se presentan experimentos y an´alisis que apoyan la idea que usar los nuevos m´etodos presentados como semilla en avanzados algoritmos metaheur´ýsticos proporciona ventajas frente al uso de la NEH como semilla.