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

Autor(es)

W.A. DE OLIVEIRA ^[1] ; M.O. SANTOS ^[2]

Afiliação do(s) autor(es)

^[1] Universidade Federal de Mato Grosso do Sul. Instituto de Matemática - INMA - Brasil

^[2] Universidade de São Paulo. ICMC. Departamento de Matemática Aplicada e Estatística - Brasil

• Tipo de documento: Artigo Científico
• Fonte: TEMA (São Carlos); v. 18, n. 3, p. 515-529, 2017-12-00.

Resumo

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. (AU)

• Processo FAPESP: 13/07375-0 - CeMEAI - Centro de Ciências Matemáticas Aplicadas à Indústria
• Beneficiário: Francisco Louzada Neto
• Modalidade de apoio: Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs