@techreport{TR-IC-04-08,
number = {IC-04-08},
author = {Eduardo Cândido Xavier and Flávio Keide Miyazawa},
title = {An Approximation Scheme for a One-Dimensional Bin Packing
Problem with Shelf Divisions},
month = {August},
year = {2004},
institution = {Institute of Computing, University of Campinas},
note = {In English, 10 pages.
\par\selectlanguage{english}\textbf{Abstract}
Given bins of size $B$, non-negative values $d$ and $dmax$,
and a list $L$ of items, each item $e\in L$ with size $s_e$ and
class $c_e$, we define a shelf as a subset of items packed
inside a bin with total items size at most $dmax$ such that
all items in this shelf have the same class. Two subsequent
shelves must be separated by a shelf divisor of size $d$. The
size of a shelf is the total size of its items plus the size of
the shelf divisor. The Class Constrained Shelf Bin Packing
Problem consists 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 an asymptotic approximation scheme for this problem
where the number of different classes is bounded by a constant
$C$. To our knowledge, this is the first approximation result
where shelves of non-null size are used in packing problems.
}
}