Busca avançada
Ano de início
Entree

Geração de colunas para o problema de dimensionamento de lotes com limitações de capacidade

Processo: 07/02099-3
Linha de fomento:Bolsas no Brasil - Mestrado
Vigência (Início): 01 de setembro de 2007
Vigência (Término): 28 de fevereiro de 2009
Área do conhecimento:Engenharias - Engenharia de Produção - Pesquisa Operacional
Pesquisador responsável:Marcos Nereu Arenales
Beneficiário:Tamara Angélica Baldo
Instituição-sede: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brasil
Assunto(s):Dimensionamento de lotes

Resumo

O problema de dimensionamento de lotes determina um plano de produção para vários itens com o objetivo de atender uma demanda conhecida (ou estimada) sem atrasos. Os itens a serem produzidos podem dividir recursos comuns, sendo estes recursos, na maioria das vezes escassos (capacidade limitada). Deste modo, o objetivo do problema é determinar um plano de produção que minimize os custos de produção, estoque e preparação e que satisfaça as restrições do atendimento das demandas e as limitações das capacidades, as quais são utilizadas para preparação e produção.Existem na literatura abordagens heurísticas e exatas que obtêm planos de produção viáveis para o problema. As abordagens heurísticas determinam soluções viáveis em um tempo computacional razoável, porém não garantem que a solução seja ótima. Neste projeto estudaremos a abordagem de geração de colunas para a resolução do problema. A abordagem consistirá em reformular o modelo de programação inteira (MIP) do problema utilizando o princípio da decomposição de Dantzig-Wolfe (Dantzig e Wolfe (1960)) e utilizar o método de geração de colunas para obter soluções para o problema. Neste projeto pretendemos escrever a decomposição de Dantzig-Wolfe para o problema para futuramente desenvolver um algoritmo de partição e avaliação, também conhecido como branch-and-price para obter soluções inteiras. No algoritmo branch-and-price, a solução inteira é obtida combinando o método branch-and-bound e a geração de colunas para resolver uma relaxação do MIP em cada nó da árvore. A geração de colunas corresponde a resolução de subproblemas que mantém a natureza combinatória do problema original. Desta forma, pretende-se aplicar o princípio da decomposição de Dantzig-Wolfe e utilizar o método de geração de colunas para obter soluções para o problema de dimensionamento de lotes monoestágio, como proposto por Pimentel (2005) e Degraeve e Jans (2007). Além disso, pretende-se estudar a decomposição para o problema multiestágio com limitações de capacidade, utilizando para esta decomposição da formulação deste problema em estoque de escalão e estoque convencional, sendo esta aplicação, uma das futuras extensões propostas por Degraeve e Jans (2007). (AU)

Publicações acadêmicas
(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)
BALDO, Tamara Angélica. Geração de colunas para o problema de dimensionamento de lotes de produção com limitações de capacidade. 2009. Dissertação de Mestrado - Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação São Carlos.

Por favor, reporte erros na lista de publicações científicas escrevendo para: cdi@fapesp.br.