A Mixed-Integer Programming Formulation and Heuristics for an Integrated Production Planning and Scheduling Problem

This paper proposes a new mixed-integer programming formulation for an integrated multiproduct, multiperiod, and multistage capacitated lot sizing with hybrid flow shop problem (CLSP-HFS). Heuristics that combine relax-and-fix with fix-and-optimize are also proposed to solve it, using strategies for decomposing the set of variables by product, period and stage. A relax-and-fix heuristic takes an initial feasible solution, and a fix-and-optimize heuristic tries to improve it. In order to evaluate the performance of the combined strategy, some experiments were done considering seven datasets as a benchmark, each one composed of ten randomly generated instances with 5, 10, 15, 20, 25, 30, and 40 products. They are processed in parallel machines during three stages along a planning horizon of eight periods. Experimental results suggest that period-based strategies achieve a percentage deviation close to zero from the optimum, while product-based strategies offer a compromise between solution quality and computational time.