Abstract (EN)

The Variable-sized Bin Packing Problem with Color Constraints (VSBPP-CC) is a generalization of the classical one-dimensional Bin Packing Problem known to be NP-hard. The VSBPP-CC can be introduced with the following notations. Let N be a set of n items. Then, let C be a set of p colors such that each item i ∈ N is characterized by a weight ai and a color ci ∈ C. Finally, let B denotes the set of q possible used bins, 1 ≤ q ≤ n, and M = {b1, . . . , bk, . . . , bm} a set of m different available capacities to be assigned to the bins. The VSBPP-CC consists in assigning to each used bin from B a capacity from M. The objective is to minimize the residual capacity in the used bins such that : (i) each item is assigned to exactly one type of the bins, (ii) the total weights of items assigned to each bin does not exceed its capacity, and (iii) no more than two colors appear in each used bin. The latter condition may be seen as a maximum color capacity for each bin.