Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/105698
Type: Artigo de periódico
Title: A One-dimensional Bin Packing Problem With Shelf Divisions
Author: Xavier E.C.
Miyazawa F.K.
Abstract: Given bins of size B, non-negative values d and Δ, and a list L of items, each item e ∈ L with size se and class ce, we define a shelf as a subset of items packed inside a bin with total item sizes at most Δ such that all items in this shelf have the same class. Two subsequent shelves must be separated by a shelf division of size d. The size of a shelf is the total size of its items plus the size of the shelf division. The class constrained shelf bin packing problem (CCSBP) is to pack the items of L into the minimum number of bins, such that the items are divided into shelves and the total size of the shelves in a bin is at most B. We present hybrid algorithms based on the First Fit (Decreasing) and Best Fit (Decreasing) algorithms, and an APTAS for the problem CCSBP when the number of different classes is bounded by a constant C. © 2007 Elsevier B.V. All rights reserved.
Editor: 
Rights: fechado
Identifier DOI: 10.1016/j.dam.2007.05.053
Address: http://www.scopus.com/inward/record.url?eid=2-s2.0-40149086823&partnerID=40&md5=6126c8868bb4de974376a3376fa8fc84
Date Issue: 2008
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File SizeFormat 
2-s2.0-40149086823.pdf698.02 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.