Online LIB problems: Heuristics for Bin Covering and lower bounds for Bin Packing

Online LIB problems: Heuristics for Bin Covering and lower bounds for Bin Packing

0.00 Avg rating0 Votes
Article ID: iaor20071289
Country: France
Volume: 39
Issue: 3
Start Page Number: 163
End Page Number: 183
Publication Date: Jul 2005
Journal: RAIRO Operations Research
Authors: ,
Keywords: heuristics
Abstract:

We consider the NP Hard problems of online Bin Covering and Packing while requiring that larger (or longer, in the one dimensional case) items be placed at the bottom of the bins, below smaller (or shorter) items – we call such a version, the LIB version of problems. Bin sizes can be uniform or variable. We look at computational studies for both the Best Fit and Harmonic Fit algorithms for uniform sized bin covering. The Best Fit heuristic for this version of the problem is introduced here. The approximation ratios obtained were well within the theoretical upper bounds. For variable sized bin covering, a more thorough analysis revealed definite trends in the maximum and average approximation ratios. Finally, we prove that for online LIB bin packing with uniform size bins, no heuristic can guarantee an approximation ratio better than 1.76 under the online model considered.

Reviews

Required fields are marked *. Your email address will not be published.