New resolution algorithm and pretreatments for the two-dimensional bin-packing problem (Q2482368): Difference between revisions

The authors consider the two-dimensional bin-packing problem, i.e. the problem of finding the minimum number of identical rectangles called bins that must be used to pack a given set of rectangular items without overlapping. The items can be rotated. The authors introduce the concept of dependent orientation items, and propose three pretreatments that allow to reduce the cardinality of the set of items. A new heuristic based on a best-fit strategy is proposed. The algorithm and the pretreatments are tested on benchmarks from the literature.