This paper presents a new composite heuristics approach for solving the N-product, M-stage lot sizing and scheduling problem with dynamic demands and limited production capacity. The first phase of these composite heuristics aims at finding a feasible solution. This solution is such that for each period and for each product, the lot size equals the net demand of the considered period plus the demand of a number of upcoming periods. If capacity does not satisfy all demands of a given period, we try to find earlier periods where we can produce the missing units. The second phase is an improvement procedure which recursively attempts to move back each lot, provided that it is both more economical to do so and capacity feasible. We also provide two variants of this heuristic to handle the case where production capacity can be increased by using overtime. Overtime is a usual practice in real life which, in many cases, allows a reduction of the overall cost. The first variant constructs the initial solution without recourse to overtime and introduces overtime only during the solution improvement phase. The second one considers overtime during both the first and second phases. The performance of the proposed heuristics is numerically assessed and the most efficient ones are identified.
