Desde su creación por Nawaz, Enscore y Ham en 1983, NEH sigue siendo el mejor método heurístico para resolver problemas de programación de flujo en taller. En el amplio cuerpo de literatura que trata sobre la aplicación de esta heurística, se puede notar claramente que los resultados difieren de un artículo a otro. En este artículo, se proponen dos métodos para mejorar el NEH original, basados en los dos puntos del método donde se deben tomar decisiones, en caso de equivalencia entre dos órdenes de trabajo o secuencias parciales. Cuando ocurre una igualdad en un método de clasificación, dos resultados son equivalentes, pero pueden llevar a diferentes resultados finales. Para proponer la primera mejora al NEH, se introduce el método de descomposición factorial de base, que hace que un número corresponda computacionalmente a una permutación. Este método es muy útil para la primera mejora y permite probar todas las posibilidades de secuenciación para problemas con hasta 50 trabajos. La segunda mejora se encuentra donde NEH mantiene la mejor secuencia parcial. De manera similar, se mantiene una lista de secuencias parciales equivalentes en lugar de solo una, para brindar a la metodología global una oportunidad de un mejor rendimiento. Los resultados obtenidos con el uso sucesivo de los dos métodos de mejora presentan una mejora promedio del 19% sobre los resultados ya efectivos del método NEH original.