Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

Reformulation and a Lagrangian heuristic for lot sizing problem on parallel machines

Texto completo
Autor(es):
Fiorotto, Diego Jacinto [1] ; de Araujo, Silvio Alexandre [1]
Número total de Autores: 2
Afiliação do(s) autor(es):
[1] UNESP Univ Estadual Paulista, IBILCE, Dept Matemat Aplicada, BR-15054000 Sao Jose Do Rio Preto, SP - Brazil
Número total de Afiliações: 1
Tipo de documento: Artigo Científico
Fonte: ANNALS OF OPERATIONS RESEARCH; v. 217, n. 1, p. 213-231, JUN 2014.
Citações Web of Science: 10
Resumo

We consider the capacitated lot sizing problem with multiple items, setup time and unrelated parallel machines. The aim of the article is to develop a Lagrangian heuristic to obtain good solutions to this problem and good lower bounds to certify the quality of solutions. Based on a strong reformulation of the problem as a shortest path problem, the Lagrangian relaxation is applied to the demand constraints (flow constraint) and the relaxed problem is decomposed per period and per machine. The subgradient optimization method is used to update the Lagrangian multipliers. A primal heuristic, based on transfers of production, is designed to generate feasible solutions (upper bounds). Computational results using data from the literature are presented and show that our method is efficient, produces lower bounds of good quality and competitive upper bounds, when compared with the bounds produced by another method from the literature and by high-performance MIP software. (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
Linha de fomento: 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
Linha de fomento: Bolsas no Brasil - Doutorado