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.)

A NOTE ON DUAL APPROXIMATION ALGORITHMS FOR CLASS CONSTRAINED BIN PACKING PROBLEMS

Texto completo
Autor(es):
Xavier, Eduardo C. [1] ; Miyazawa, Flavio Keidi [1]
Número total de Autores: 2
Afiliação do(s) autor(es):
[1] Univ Estadual Campinas, UNICAMP, Inst Comp, BR-13083970 Campinas, SP - Brazil
Número total de Afiliações: 1
Tipo de documento: Artigo Científico
Fonte: RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS; v. 43, n. 2, p. 239-248, APR-JUN 2009.
Citações Web of Science: 1
Resumo

In this paper we present a dual approximation scheme for the class constrained shelf bin packing problem. In this problem, we are given bins of capacity 1, and n items of Q different classes, each item e with class c(e) and size s(e). The problem is to pack the items into bins, such that two items of different classes packed in a same bin must be in different shelves. Items in a same shelf are packed consecutively. Moreover, items in consecutive shelves must be separated by shelf divisors of size d. In a shelf bin packing problem, we have to obtain a shelf packing such that the total size of items and shelf divisors in any bin is at most 1. A dual approximation scheme must obtain a shelf packing of all items into N bins, such that, the total size of all items and shelf divisors packed in any bin is at most 1 + epsilon for a given epsilon > 0 and N is the number of bins used in an optimum shelf bin packing problem. Shelf divisors are used to avoid contact between items of different classes and can hold a set of items until a maximum given weight. We also present a dual approximation scheme for the class constrained bin packing problem. In this problem, there is no use of shelf divisors, but each bin uses at most C different classes. (AU)

Processo FAPESP: 08/01490-3 - Algoritmos para problemas de empacotamento e em grafos
Beneficiário:Eduardo Candido Xavier
Linha de fomento: Auxílio à Pesquisa - Regular