Relaxação Lagrangiana Aplicada ao Problema de Dimensionamento de Lotes em Máquinas Paralelas: Limitantes Inferiores

Autores

  • Silvio Alexandre de Araujo Univ. Estadual Paulista/ São José do Rio Preto
  • Diego Jacinto Fiorotto Univ. Estadual Paulista/ São José do Rio Preto

DOI:

https://doi.org/10.5540/tema.2012.013.01.0013

Resumo

Este trabalho aborda o problema de dimensionamento de lotes monoestágio em um ambiente com máquinas paralelas distintas. Cada item pode ser produzido em qualquer máquina, acarretando um tempo de preparação que é gasto antes de começar a produção. O objetivo do trabalho consiste em obter limitantes inferiores de boa qualidade para este problema. Para tanto, é desenvolvido um método de solução baseado numa reformulação do problema e na relaxação Lagrangiana de um conjunto de restrições. Alguns resultados computacionais são apresentados comparando o método proposto com um trabalho da literatura e com um pacote computacional.

 

Biografia do Autor

Silvio Alexandre de Araujo, Univ. Estadual Paulista/ São José do Rio Preto

Departamento de Ciências da Computação e Estatística

Diego Jacinto Fiorotto, Univ. Estadual Paulista/ São José do Rio Preto

Departamento de Ciências da Computação e Estatística

Referências

P. M. Camerini, L. Fratta, F. Maffioli, On Improving Relaxation Methods by Modified Gradient Techniques, Mathematical Programming Study, 3 (1975), 26–54.

W. H. Chen, J. M. Thizy, Analysis of relaxation for the multi- item capacitated lot-sizing problem, Operations Research, 26 (1990), 29–72.

Z. Degraeve, R. Jans, A new dantzig-wolfe reformulation and branch-and-price algorithm for the capacited lot-sizing problem with setup times, OperationalResearch, 55 (2007), 909–920.

M. Diaby, H. Bahl, M. H. Karwan, S. Ziont, Capacitated lot-sizing and scheduling by lagrangean relaxation, European Journal Of Operational Research, 59(1992), 444–458.

G. B. Eppen, R. K. Martin, Solving Multi-Item Capacitated Lot-Sizing Problems Using Variable Redefinition, Operations Research, 6 (1987), 832–848.

R. Jans, Z. Degraeve, Improved lower bounds for capacitated lot sizing problem with setup time, Operation Research Letters, 32 (2004), 185–195.

C. M. O. Pimentel, F. P. Alvelos, J. M. V. Carvalho, Comparing Dantzig-Wolfe decompositions and branch-and-price algorithms for the multi-item capacitatedlot sizing problem, Optimization Methods and Software, 25 (2010), 229–319.

H. Sural, M. Denizel, L. N. vanWassenhove, Lagrangean relaxation based heuristic for lot sizing with setup times, European Journal of Operational Research,195 (2009), 51–63.

J. M. Thizy, L. N. V. Wassenhove, Lagrangean relaxation for the multi-item capacitated lot-sizing problem: a heuristic implementation, AIIE Transactions,17 (1985), 64-74.

F. M. B. Toledo, V. A. Armentano, A Lagrangian-Based Heuristic for the Capacitated Lot-Sizing Problem in Parallel Machines, European Journal of OperationalResearch, 175 (2006), 1070–1083.

Downloads

Arquivos adicionais

Publicado

2012-03-17

Como Citar

de Araujo, S. A., & Fiorotto, D. J. (2012). Relaxação Lagrangiana Aplicada ao Problema de Dimensionamento de Lotes em Máquinas Paralelas: Limitantes Inferiores. Trends in Computational and Applied Mathematics, 13(1), 13–24. https://doi.org/10.5540/tema.2012.013.01.0013

Edição

v. 13 n. 1 (2012)

Seção

Artigo Original

Licença

Direitos Autorais

Autores de artigos publicados no periódico Trends in Computational and Applied Mathematics mantêm os direitos autorais de seus trabalhos. O periódico utiliza a Atribuição Creative Commons (CC-BY) nos artigos publicados. Os autores concedem ao periódico o direito de primeira publicação.

Propriedade Intelectual e Termos de uso

O conteúdo dos artigos é de responsabilidade exclusiva dos autores. O periódico utiliza a Atribuição Creative Commons (CC-BY) nos artigos publicados. Esta licença permite que os artigos publicados sejam reutilizados sem permissão para qualquer finalidade, desde que o trabalho original seja corretamente citado.

O periódico encoraja os Autores a autoarquivar seus manuscritos aceitos, publicando-os em blogs pessoais, repositórios institucionais e mídias sociais acadêmicas, bem como postando-os em suas mídias sociais pessoais, desde que seja incluída a citação completa à versão do website da revista.