Este documento presenta un algoritmo estocástico efectivo que incorpora una técnica de descomposición de vecindario grande en una búsqueda de vecindario variable para resolver el problema de programación de flujo en tiendas de permutación. El algoritmo primero construye una permutación como una semilla utilizando una aplicación recursiva del problema de dos máquinas extendido. En este método, los trabajos se descomponen de forma recursiva en dos grupos separados y, para cada grupo, se calcula una permutación óptima basada en el problema de dos máquinas extendido. Luego, la permutación general, que se obtiene integrando las sub-soluciones, se mejora mediante la aplicación de una técnica de búsqueda de vecindario variable. Al igual que la primera técnica, esta también se basa en el paradigma de descomposición y puede encontrar un arreglo óptimo para un subconjunto de trabajos. En la búsqueda de vecindario grande empleada, se ha utilizado el concepto de camino crítico para ayudar al proceso de descomposición a evitar cálculos infructuosos y a organizar solo partes contiguas prometedoras de la permutación. De esta manera, el algoritmo deja aquellas partes de la permutación que ya tienen arreglos de alta calidad y se concentra en modificar otras partes. Los resultados de experimentos computacionales en las instancias de referencia indican que el procedimiento funciona de manera efectiva, demostrando que las soluciones, a una distancia muy corta de las mejores soluciones conocidas, se calculan en segundos en un ordenador personal típico. En cuanto al tiempo de ejecución requerido para alcanzar una solución de alta calidad, el procedimiento supera a algunos algoritmos metaheurísticos conocidos en la literatura.