Problemas da mochila compartimentada: casos unidimensional e bidimensional

• Processo: 08/09046-5
• Linha de fomento: Bolsas no Brasil - Doutorado
• Vigência (Início): 01 de abril de 2009
• Vigência (Término): 31 de janeiro de 2013
• Área do conhecimento: Engenharias - Engenharia de Produção - Pesquisa Operacional
• Pesquisador responsável: Marcos Nereu Arenales
• Beneficiário: Aline Aparecida de Souza Leão
• 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
• Vinculado ao auxílio: 06/03496-3 - Teoria e prática dos problemas de corte e empacotamento, AP.TEM
• Assunto(s): Dimensionamento de lotes Otimização matemática

Resumo

O Problema da Mochila Compartimentada é uma extensão do Problema da Mochila, em que os itens solicitados são divididos em classes, de modo que a mochila deve ser subdividida em compartimentos, os quais têm capacidades limitadas e são carregados com itens de mesma classe. Além disso, a construção de um compartimento tem um custo fixo e ocasiona uma perda no espaço da mochila. O objetivo consiste em maximizar a soma dos valores dos itens, descontado o custo fixo de inclusão de compartimentos. Uma aplicação da Mochila Compartimentada surge em problemas de corte com vários estágios, nos quais os objetos em estoque devem ser cortados em objetos intermediários até a obtenção dos itens finais. Na literatura, o caso unidimensional deste problema foi aplicado em problemas de corte, em que bobinas de aço sujeito à laminação devem ser cortadas para obtenção de fitas, e no corte de bobinas de papel, em que dois estágios distintos de corte ocorrem. O problema foi modelado como otimização não linear inteira e métodos heurísticos foram propostos. Neste projeto buscamos desenvolver um método exato tipo branch-and-price para o Problema da Mochila Compartimentada Unidimensional. Pretende-se também estender esta abordagem na geração de padrões de corte para o caso bidimensional, visto que surgem naturalmente na prática, pelas mesmas razões que o caso unidimensional, ou seja, corte em vários estágios. (AU)

Publicações científicas

(Referências obtidas automaticamente do Web of Science e do SciELO, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores)

LEAO, ALINE A. S.; FURLAN, MARCOS M.; TOLEDO, FRANKLINA M. B. Decomposition methods for the lot-sizing and cutting-stock problems in paper industries. Applied Mathematical Modelling, v. 48, p. 250-268, AUG 2017. Citações Web of Science: 3.

LEAO, ALINE A. S.; CHERRI, LUIZ H.; ARENALES, MARCOS N. Determining the K-best solutions of knapsack problems. Computers & Operations Research, v. 49, p. 71-82, SEP 2014. Citações Web of Science: 3.

Publicações acadêmicas

(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)

LEÃO, Aline Aparecida de Souza. Extensões em problemas de corte: padrões compartimentados e problemas acoplados. 2013. Tese de Doutorado - Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação São Carlos.