The Bin Packing Problem with Fragile Objects

Franēois Clautiaux, Mauro Dell’Amico, Manuel Iori and Ali Khanafer

Problem description

We are given a set of items, each characterized by a weight and a fragility, and a large number of uncapacitated bins. Our aim is to find the minimum number of bins needed to pack all items, in such a way that in each bin the sum of the item weights is less than or equal to the smallest fragility of the items in the bin. The problem is known in the literature as the Bin Packing Problem with Fragile Objects, and appears in the telecommunication field, when one has to assign cellular calls to available channels by ensuring that the total noise in a channel does not exceed the noise acceptance limit of a call.