Advanced search
Start date
Betweenand
(Reference retrieved automatically from Google Scholar through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

A one-dimensional bin packing problem with shelf divisions

Full text
Author(s):
Xavier‚ EC ; Miyazawa‚ F.K.
Total Authors: 2
Document type: Journal article
Source: DISCRETE APPLIED MATHEMATICS; v. 156, n. 7, p. 1083-1096, 2008.
Abstract

Given bins of size B, non-negative values d and Delta, and a list L of items, each item e is an element of L with size s(e) and class c(e), we define a shelf as a subset of items packed inside a bin with total item sizes at most Delta 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. (C) 2007 Elsevier B.V. All rights reserved. (AU)

FAPESP's process: 03/09925-5 - Foundations of computer science: combinatory algorithms and discrete structures
Grantee:Yoshiharu Kohayakawa
Support Opportunities: PRONEX Research - Thematic Grants