Relaxação Lagrangiana Aplicada ao Problema de Dimensionamento de Lotes em Máquinas Paralelas: Limitantes Inferiores
DOI:
https://doi.org/10.5540/tema.2012.013.01.0013Abstract
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.
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
How to Cite
Issue
Section
License
Authors who publish in this journal agree to the following terms:
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.
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.
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).
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.