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

Authors

  • 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

Abstract

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.

 

Author Biographies

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

References

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

Additional Files

Published

2012-03-17

How to Cite

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

Issue

Vol. 13 No. 1 (2012)

Section

Original Article

License

Authors who publish in this journal agree to the following terms: 

  1. Authors retain copyright and grant the journal the right of first publication, with the work simultaneously licensed under the Creative Commons Attribution License that allows the sharing of the work with acknowledgment of authorship and initial publication in this journal.

  2. Authors are authorized to assume additional contracts separately, for non-exclusive distribution of the version of the work published in this journal (eg, publish in an institutional repository or as a book chapter), with acknowledgment of authorship and initial publication in this journal.
     

  3. Authors are allowed and encouraged to publish and distribute their work online (eg, in institutional repositories or on their personal page) at any point before or during the editorial process, as this can generate productive changes as well as increase impact and the citation of the published work (See The effect of open access).

  4. This is an open access journal which means that all content is freely available without charge to the user or his/her institution. Users are allowed to read, download, copy, distribute, print, search, or link to the full texts of the articles, or use them for any other lawful purpose, without asking prior permission from the publisher or the
    author. This is in accordance with the BOAI definition of open access

 

Intellectual Property

All the contents of this journal, except where otherwise noted, is licensed under a Creative Commons Attribution License under attribution BY.