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 sequence dependent 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.
| Main Authors: | , |
|---|---|
| Format: | Digital revista |
| Language: | English |
| Published: |
Sociedade Brasileira de Matemática Aplicada e Computacional
2017
|
| Online Access: | http://old.scielo.br/scielo.php?script=sci_arttext&pid=S2179-84512017000300515 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|