MIP approaches for a lot sizing and scheduling problem on multiple production lines with scarce resources, temporary workstations, and perishable products

Abstract

This paper addresses a lot sizing and scheduling problem inspired from a real-world production environment apparent in food industry. Due to the scarcity of resources, only a subset of production lines can operate simultaneously, and those lines need to be assembled in each production period. In addition, the products are perishable, and there are often significant sequence-dependent setup times and costs. We first propose a standard mixed integer programming model for the problem, and then a reformulation of the standard model in order to allow us to define a branching rule to accelerate the performance of the branch-and-bound algorithm. We also propose an efficient relax-and-fix procedure that can provide high-quality feasible solutions and competitive dual bounds for the problem. Computational experiments indicate that our approaches provide superior results when benchmarked with a commercial solver and an established relax-and-fix heuristic from the literature.

Keywords:

• Lot sizing and scheduling problem
• production
• scarce resources
• branch and bound
• heuristics

Acknowledgments

The research of the first author was supported in part by the Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) and by the Universidade Federal de Mato Grosso do Sul. Research was carried out using the computational resources of the Center for Mathematical Sciences Applied to Industry (CeMEAI), funded by FAPESP (Grant 2013/07375-0). The authors are also grateful to three anonymous referees for their valuable comments, which helped improve the presentation of the paper.

Disclosure statement

No potential conflict of interest was reported by the authors.