Rolling-horizon and fix-and-relax heuristics for the parallel machine lot-sizing and scheduling problem with sequence-dependent set-up costs

In this paper we develop newrolling-horizon and fix-and-relax heuristics for the identical parallel machine lot-sizing and schedulingproblem with sequence-dependent set-up costs. Unlike previous papers, our procedures are based on a compact formulation relyingon the hypotheses of identical machines. This feature makes our approach suitable for large-scale applications (with hundreds ofmachines) arising in the textile and fiberglass industries. Moreover, our procedures are shown to provide a feasible solution for anyfeasible instance. Comparisons with lower bounds provided by a truncated branch-and-bound show that the gap between the bestheuristic solution and the lower bound never exceeds 3%.