Lagrangian-based heuristics for production planning with perishable products, scarce resources, and sequence-dependent setup times

In this paper, we study a lot-sizing and scheduling problem apparent in the food industry that stemmed originally from the Brazilian meat production sector. More specifically, we consider a production environment in which various production lines share a set of scarce production resources. Therefore, only a subset of the existing production lines can simultaneously operate in each period under the limitations of the availability of resources. Moreover, we consider sequence-dependent setup times and costs, significant inventory holding costs, backlogging, and perishable products. The problem is formulated as a mixed integer programming model, and we propose four Lagrangian-based heuristics to find high-quality solutions for challenging instances. A computational study shows that proposed approaches are very competitive in solving the problem, outperforming methods already established in the literature.