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

• Processo: 07/02099-3
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de setembro de 2007
• Data de Término da vigência: 28 de fevereiro de 2009
• Área de 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
• Palavra(s)-Chave do Pesquisador: dimensionamento de lotes | Geração de Colunas | Planejamento da Produção | programação inteira | Otimização

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 (ICMC/SB) São Carlos.