El Problema de Programación de la Tienda de Trabajo Flexible (FJSSP) continúa siendo estudiado extensamente para probar nuevas metaheurísticas y debido a su cercanía a los sistemas de producción actuales. Una variante del FJSSP utiliza tiempos de procesamiento difusos en lugar de tiempos fijos. Este artículo propone un nuevo algoritmo para FJSSP con tiempos de procesamiento difusos llamado algoritmo de vecindario global con escalada de colinas (GN-HC). Este algoritmo realiza la exploración de soluciones utilizando operadores simples de forma concurrente para el manejo de la vecindad de búsqueda global. Para la búsqueda local, se aplica una escalada de colinas de reinicio aleatorio en cada solución para encontrar la mejor máquina para cada operación. Para la selección de operaciones en la escalada de colinas, se emplea un registro de las operaciones que definen el makespan difuso para utilizarlas como un camino crítico. Finalmente, se realiza una estimación del makespan nítido con los tiempos de procesamiento más largos en la escalada de colinas para mejorar la velocidad del GN-HC. El GN-HC se compara con otros métodos recientemente propuestos reconocidos por su excelente rendimiento, utilizando 6 instancias de FJSSP con tiempos difusos. Los resultados obtenidos muestran una competitividad satisfactoria para GN-HC en comparación con algoritmos de última generación. La implementación de GN-HC se realizó en Matlab y se puede encontrar en GitHub (consulte la Declaración de Disponibilidad de Datos al final del artículo).