Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

Exact algorithms for class-constrained packing problems

Texto completo
Autor(es):
Borges, Yulle G. F. [1] ; Miyazawa, Flavio K. [1] ; Schouery, Rafael C. S. [1] ; Xavier, Eduardo C. [1]
Número total de Autores: 4
Afiliação do(s) autor(es):
[1] Univ Estadual Campinas, Av Albert Einstein 1251, Cidade Univ, Campinas, SP - Brazil
Número total de Afiliações: 1
Tipo de documento: Artigo Científico
Fonte: COMPUTERS & INDUSTRIAL ENGINEERING; v. 144, JUN 2020.
Citações Web of Science: 1
Resumo

We consider a generalization of the classic Bin Packing Problem, called the Class-Constrained Bin Packing Problem (CCBPP), in which given a set of items, each one with a size and a class, one must pack the items in the least amount of bins respecting the bin capacity and the number of different classes that it can hold. We also consider the Class-Constrained Knapsack Problem (CCKP), in which items also have a value and one must select a subset of items with a maximum value which fits in a single bin. We consider a Branch-and-Price framework for CCBPP, exploring several options in the design of a Branch-and-Price algorithm. For the Pricing Problem, which is equivalent to the CCKP, we present two dynamic programming algorithms and a Branch-and-Bound algorithm. We also present other exact algorithms for generalizations of CCKP. These generalized problems also appear as Pricing Problems when solving the CCBPP. Our best algorithm for CCBPP was able to solve 95% of the instances considered in less than 15 min. (AU)

Processo FAPESP: 16/23552-7 - Problemas de Corte e Empacotamento: Abordagens Práticas e Teóricas
Beneficiário:Rafael Crivellari Saliba Schouery
Linha de fomento: Auxílio à Pesquisa - Regular
Processo FAPESP: 16/01860-1 - Problemas de corte, empacotamento, dimensionamento de lotes, programação da produção, roteamento, localização e suas integrações em contextos industriais e logísticos
Beneficiário:Reinaldo Morabito Neto
Linha de fomento: Auxílio à Pesquisa - Temático
Processo FAPESP: 14/25892-4 - Problemas de corte de estoque com restrições de classe
Beneficiário:Yulle Glebbyo Felipe Borges
Linha de fomento: Bolsas no Brasil - Mestrado
Processo FAPESP: 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural
Beneficiário:Flávio Keidi Miyazawa
Linha de fomento: Auxílio à Pesquisa - Temático