Hybrid methods for lot sizing on parallel machines

Autor(es)

Fiorotto, Diego Jacinto ^[1] ; de Araujo, Silvio Alexandre ^[1] ; Jans, Raf ^{[2, 3]}

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

^[1] Univ Estadual Paulista, Dept Matemat Aplicada, BR-15054000 Sao Jose Do Rio Preto, SP - Brazil

^[2] HEC Montreal, Montreal, PQ H3T 2A7 - Canada

^[3] CIRRELT, Montreal, PQ H3T 2A7 - Canada

• Tipo de documento: Artigo Científico
• Fonte: Computers & Operations Research; v. 63, p. 136-148, NOV 2015.
• Citações Web of Science: 9

Resumo

We consider the capacitated lot sizing problem with multiple items, setup time and unrelated parallel machines, and apply Dantzig-Wolfe decomposition to a strong reformulation of the problem. Unlike in the traditional approach where the linking constraints are the capacity constraints, we use the flow constraints, i.e. the demand constraints, as linking constraints. The aim of this approach is to obtain high quality lower bounds. We solve the master problem applying two solution methods that combine Lagrangian relaxation and Dantzig-Wolfe decomposition in a hybrid form. A primal heuristic, based on transfers of production quantities, is used to generate feasible solutions. Computational experiments using data sets from the literature are presented and show that the hybrid methods produce lower bounds of excellent quality and competitive upper bounds, when compared with the bounds produced by other methods from the literature and by a high-performance MIP software. (C) 2015 Elsevier Ltd. All rights reserved. (AU)

• Processo FAPESP: 11/22647-0 - Problemas de dimensionamento de lotes: integrações e métodos de solução
• Beneficiário: Silvio Alexandre de Araujo
• Modalidade de apoio: Auxílio à Pesquisa - Regular
• Processo FAPESP: 10/16727-9 - Relaxação lagrangiana e decomposição dantzig-wolfe: aplicação ao problema de dimensionamento de lotes em máquinas paralelas
• Beneficiário: Diego Jacinto Fiorotto
• Modalidade de apoio: Bolsas no Brasil - Doutorado
• Processo FAPESP: 13/00965-6 - Decomposição de Dantzig-Wolfe e relaxação Lagrangiana: métodos híbridos
• Beneficiário: Diego Jacinto Fiorotto
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Doutorado