Advanced search
Start date
Betweenand
Related content
(Reference retrieved automatically from SciELO through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

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

Full text
Author(s):
W.A. DE OLIVEIRA [1] ; M.O. SANTOS [2]
Total Authors: 2
Affiliation:
[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
Total Affiliations: 2
Document type: Journal article
Source: TEMA (São Carlos); v. 18, n. 3, p. 515-529, 2017-12-00.
Abstract

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)

FAPESP's process: 13/07375-0 - CeMEAI - Center for Mathematical Sciences Applied to Industry
Grantee:Francisco Louzada Neto
Support Opportunities: Research Grants - Research, Innovation and Dissemination Centers - RIDC