A New Branching Rule to Solve the Capacitated Lot Sizing and Scheduling Problem with Sequence Dependent Setups

Abstract

In this paper, we deal with the Capacitated Lot Sizing and Scheduling Problem with sequencedependent setup times and costs - CLSD model. More specifically, we propose a simple reformulation for the CLSD model that enables us to define a new branching rule to be used in Branch-and-Bound (or Branch-and-Cut) algorithms to solve this NP-hard problem. Our branching rule can be easily implemented in commercial solvers. Computational tests performed in 240 test instances from the literature show that our approach can significantly reduce the running time to solve this problem using a Branch-and-Cut algorithm of a commercial MIP solver.Therefore, our approach can also improve the performance of other approaches that need to solve partial sub problems of the CLSD model in each iteration, such as Lagrangian approaches and heuristics based on the mathematical formulation of the problem.

Keywords

• Lot Sizing
• Scheduling
• Mixed Integer Linear Programming
• Branch-and-Bound Algorithm