Approximation algorithms for the oriented two-dimensional bin packing problem

Approximation algorithms for the oriented two-dimensional bin packing problem

0.00 Avg rating0 Votes
Article ID: iaor2000893
Country: Netherlands
Volume: 112
Issue: 1
Start Page Number: 158
End Page Number: 166
Publication Date: Jan 1999
Journal: European Journal of Operational Research
Authors: , ,
Keywords: heuristics
Abstract:

Given a set of rectangular items which may not be rotated and an unlimited number of identical rectangular bins, we consider the problem of packing each item into a bin so that no two items overlap and the number of required bins is minimized. The problem is strongly NP-hard and finds practical applications in cutting and packing. We discuss a simple deterministic approximation algorithm which is used in the initialization of a tabu search approach. We then present a tabu search algorithm and analyze its average performance through extensive computational experiments.

Reviews

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