Este trabajo aborda un caso particular del problema de programación de tiendas de grupo (GSSP), que se denominará como el problema de programación de tiendas de grupo fijo (FGSSP). En un FGSSP, las operaciones de trabajo se dividen en etapas y cada etapa tiene un conjunto de máquinas asociadas que no se comparten con las otras etapas. Todos los trabajos pasan por todas las etapas en un orden específico, donde las operaciones del trabajo en cada etapa deben finalizarse antes de que el trabajo avance a la siguiente etapa, pero las operaciones dentro de una etapa pueden realizarse en cualquier orden. Esta configuración es común en empresas como fabricantes de muelles de hojas y otras empresas automotrices. Para resolver el problema, proponemos un procedimiento heurístico novedoso que combina un enfoque de descomposición con un solucionador de programación de restricciones (CP) y un mecanismo de reinicio tanto para evitar óptimos locales como para diversificar la búsqueda. El rendimiento de nuestro enfoque se probó en instancias derivadas de otros problemas de programación que subsume el FGSSP, considerando tanto los casos con como sin tiempos de configuración dependientes de secuencia anticipada. Los resultados del algoritmo propuesto se comparan con métodos de CP y programación lineal entera mixta (MILP) listos para usar, así como con los límites inferiores derivados del estudio del problema. Los experimentos muestran que el algoritmo heurístico propuesto supera a los otros métodos, especialmente en instancias de gran tamaño con mejoras de más del 10% en promedio.