Due to a varying product demand (changing product mix) and different production speeds, bottlenecks may shift between the stages. In that case, a simultaneous lot-sizing and scheduling of these stages is recommendable. Hence, an improved version of the General Lot-Sizing and Scheduling Problem for Multiple production Stages (GLSPMS) was developed. Moreover, several reformulation techniques were applied to this model to solve it exactly. Besides, a new meta-heuristic which combines the principles of Variable Neighborhood Decomposition Search (VNDS) and Exchange was implemented to find good solutions, even for a real-world problem case. Finally, further model extensions, e.g., for scarce setup resources, were proposed.