We consider {\em class constrained}
packing problems, in which we are given a set of
bins, each having a capacity $v$ and $c$ compartments, and $n$
items of
$M$ different classes and the same (unit) size. We need
to fill the bins with items, subject to capacity constraints,
such that items of different classes are placed in separate
compartments; thus, each bin can contain items of at most $c$
distinct classes.
We consider two optimization goals. In the
{\em class-constrained bin-packing problem (CCBP)}, our goal is to
pack all the items in a minimal number of
bins; in the {\em class-constrained multiple knapsack problem
(CCMK)}, we wish to maximize the total number of
items packed in $m$ bins, for $m > 1$.
The CCBP and CCMK model
fundamental resource allocation problems in computer and
manufacturing systems. Both
are known to be strongly NP-hard.
In this paper we derive tight bounds for the online variants of
these problems.
We first present a lower bound of $(1+\alpha)$
on the competitive ratio of {\em any} deterministic algorithm for the online
CCBP,
where $\alpha \in (0,1]$ depends on $v,c,M$ and $n$. We show that
this ratio is achieved by the algorithm {\em first-fit}.
We then consider the {\em temporary CCBP}, in which items may be
packed for a {\em bounded} time interval (that is {\em unknown}
in advance). We obtain a lower bound of $v/c$ on the competitive ratio of
{\em any} deterministic algorithm. We show that this ratio is achieved by all
{\em any-fit} algorithms.
Finally, tight bounds are derived for
the online CCMK and the {\em temporary} CCMK problems.