Period Decompositions for the Capacitated Lot Sizing Problem with Setup Times
Carregando...
Fontes externas
Fontes externas
Data
Orientador
Coorientador
Pós-graduação
Curso de graduação
Título da Revista
ISSN da Revista
Título de Volume
Editor
Informs
Institute for Operations Research and the Management Sciences (INFORMS)
Institute for Operations Research and the Management Sciences (INFORMS)
Tipo
Artigo
Direito de acesso
Acesso aberto
Fontes externas
Fontes externas
Resumo
We study the multi-item capacitated lot sizing problem with setup times. Based on two strong reformulations of the problem, we present a transformed reformulation and valid inequalities that speed up column generation and Lagrange relaxation. We demonstrate computationally how both ideas enhance the performance of our algorithm and show theoretically how they are related to dual space reduction techniques. We compare several solution methods and propose a new efficient hybrid scheme that combines column generation and Lagrange relaxation in a novel way. Computational experiments show that the proposed solution method for finding lower bounds is competitive with textbook approaches and state-of-the-art approaches found in the literature. Finally, we design a branch-and-price-based heuristic and report computational results. The heuristic scheme compares favorably or outperforms other approaches.
Descrição
Palavras-chave
Idioma
Inglês
Citação
Informs Journal On Computing. Catonsville: Informs, v. 27, n. 3, p. 431-448, 2015.
