Approximation algorithms for the oriented two-dimensional bin packing problem |
| |
Affiliation: | 1. Warwick Business School, University of Warwick, Coventry, CV4 7AL, UK;2. School of Management, University of Bath, Claverton Down, Bath BA2 7AY, UK;3. Econometric Institute, Erasmus University Rotterdam, 3000 DR Rotterdam, The Netherlands |
| |
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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|