This paper presents a new heuristic algorithm for the task of lot sizing and scheduling for identical parallel machines. The new algorithm is based on the rolling-horizon approach and the fix-and-relax decomposition technique. Two variants of the algorithm are finally proposed for solving the problem of lot scheduling with parallel machines where the number of products and machines is greater than that of the machines. A computational experiment has been conducted for a group of 30 data sets. The results showed that the new algorithm efficiently provided good solutions for tasks with large numbers of machines and products.