New data-dependent dual-feasible functions and lower bounds for a two-dimensional bin-packing problem

Authors: Clautiaux, Francois¹; Moukrim, Aziz²; Carlier, Jacques²

Source: International Journal of Production Research, Volume 47, Number 2, January 2009 , pp. 537-560(24)

Buy & download fulltext article:

Price: $56.94 plus tax (Refund Policy)

Abstract:

The bin-packing problem consists of determining the minimum number of bins needed to pack a given set of n items. It has been shown that the dual-feasible functions (DFF) proposed by Johnson and the data-dependent DFF (DDFF) proposed by the present authors can be used to obtain good lower bounds for bin-packing problems. In a recent paper we proposed fast bounds for the two-dimensional bin-packing problem using three (D)DFF. In this paper we discuss two new methods for generating (D)DFF, at a higher computational cost, to improve the results obtained. The first method consists of iteratively composing the three functions previously proposed. We show that the obtained set of functions contains a dominant set whose size is of O(n2). The second method uses the enumerative method of Carlier and Neron to generate discrete DFF. We provide computational experiments to compare the effectiveness of the two methods against classical benchmarks derived from the literature.

Keywords: Bin-packing; Dual-feasible functions; Data-dependent dual-feasible functions

Document Type: Research article

DOI: http://dx.doi.org/10.1080/00207540802426656

Affiliations: 1: Universite des Sciences et Technologies de Lille, LIFL UMR CNRS 8022, France 2: HeuDiaSyC, UMR CNRS 6599, Universite de Technologie de Compiegne, France

Publication date: 2009-01-01

More about this publication?