In the last years, the paradigm of the Portuguese footwear industry has improved drastically to become one of the main world players. In fact, a lot has changed, from low-cost mass production to serving clients consisting of small retail chains, where orders are small and models are varied. In order to deal with such modifications, the footwear industry started investing in technological solutions. The industrial case presented in this paper fits that purpose. The goal is to contribute to the solution of complex scheduling problems arising in the new mixed-model flexible automatic stitching systems of an important footwear factory. The project starts by building an optimization model. Although the model has its own usefulness, the CPLEX program is only capable of reaching optimal solutions for small problem instances. Therefore, a recent metaheuristic, the Imperialist Competitive Algorithm (ICA), has been chosen to tackle larger problems. The ICA is capable of finding optimal results for smaller instances and achieving adequate solutions for real problems in short periods of time. Moreover, ICA improves the results obtained so far by the method currently used in the factory.