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

Autor(es)

Tamara Angélica Baldo

• Tipo de documento: Dissertação de Mestrado
• Imprenta: São Carlos.
• Instituição: Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação (ICMC/SB)
• Data de defesa: 2009-05-29

Membros da banca

Marcos Nereu Arenales; Reinaldo Morabito Neto; Marcos Antonio Pereira

• Orientador: Marcos Nereu Arenales

Resumo

O problema de dimensionamento de lotes com restrições de capacidade (CLSP) consiste em determinar um plano de produção que satisfaça a demanda requerida, respeitando as limitações de capacidade, com o menor custo possível, ou seja, minimizando os custos de produção, estocagem e preparação de máquina. Encontrar uma solução factível para o CLSP, considerando tempo de preparação de máquina, é NP-completo. Nesta dissertação, para a resolução do CLSP, utiliza-se a decomposição de Dantzig-Wolfe e o procedimento de geração de colunas, encontrando bons limitantes inferiores. Duas diferentes estratégias de decomposição são exploradas, decomposição por itens e períodos. Para a obtenção de uma solução inteira para o problema (limitante superior) foram exploradas heurísticas lagrangianas, onde a solução inicial para as heurísticas provém da geração de colunas. Os limitantes obtidos podem ser utilizados em métodos exatos, como por exemplo, em algoritmos do tipo branch-and-price. Experimentos computacionais, baseados em exemplares gerados aleatoriamente, foram realizados e os resultados analisados, as variações dos parâmetros das instâncias foram sugeridas na literatura (AU)

• Processo FAPESP: 07/02099-3 - Geração de colunas para o problema de dimensionamento de lotes com limitações de capacidade
• Beneficiário: Tamara Angélica Baldo
• Modalidade de apoio: Bolsas no Brasil - Mestrado