A relax-and-fix with fix-and-optimize heuristic applied to multi-level lot-sizing problems

Autor(es)

Motta Toledo, Claudio Fabiano ^[1] ; Arantes, Marcio da Silva ^[1] ; Bressan Hossomi, Marcelo Yukio ^[1] ; Franca, Paulo Morelato ^[2] ; Akartunali, Kerem ^[3]

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

^[1] Univ Sao Paulo, Inst Math & Comp Sci, BR-13566590 Sao Carlos, SP - Brazil

^[2] UNESP, Dept Math & Comp Sci, BR-19060080 Presidente Prudente, SP - Brazil

^[3] Univ Strathclyde, Dept Management Sci, Glasgow G1 1QE, Lanark - Scotland

• Tipo de documento: Artigo Científico
• Fonte: Journal of Heuristics; v. 21, n. 5, p. 687-717, OCT 2015.
• Citações Web of Science: 13

Resumo

In this paper, we propose a simple but efficient heuristic that combines construction and improvement heuristic ideas to solve multi-level lot-sizing problems. A relax-and-fix heuristic is firstly used to build an initial solution, and this is further improved by applying a fix-and-optimize heuristic. We also introduce a novel way to define the mixed-integer subproblems solved by both heuristics. The efficiency of the approach is evaluated solving two different classes of multi-level lot-sizing problems: the multi-level capacitated lot-sizing problem with backlogging and the two-stage glass container production scheduling problem (TGCPSP). We present extensive computational results including four test sets of the Multi-item Lot-Sizing with Backlogging library, and real-world test problems defined for the TGCPSP, where we benchmark against state-of-the-art methods from the recent literature. The computational results show that our combined heuristic approach is very efficient and competitive, outperforming benchmark methods for most of the test problems. (AU)

• Processo FAPESP: 10/10133-0 - Problemas de corte, empacotamento, dimensionamento de lotes e programação da produção, e suas integrações em contextos industriais e logísticos
• Beneficiário: Reinaldo Morabito Neto
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 11/15581-3 - Ambiente para desenvolvimento de métodos aplicados a problemas de otimização
• Beneficiário: Márcio da Silva Arantes
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Processo FAPESP: 11/15534-5 - Heurísticas e metaheurísticas híbridas aplicadas ao problema capacitado de dimensionamento de lotes multi-nível
• Beneficiário: Claudio Fabiano Motta Toledo
• Modalidade de apoio: Auxílio à Pesquisa - Regular