Scheduling Algorithms for new Emerging Applications

May, 29th - June, 2nd 2006, CIRM, Marseille, France

New lower bounds for the two-dimensional bin-packing problem

SpeakerJacques Carlier

Co-authorsFrançois Clautiaux and Aziz Moukrim

The two-dimensional bin-packing problem consists in determining the minimum number of bins (large rectangles) needed to pack a given set of items (small rectangles) . It has been shown by Fekete et Schepers (2001) that Dual-Feasible Functions (DFF) proposed by Johnson (1973) can be used to get good lower bounds. In this talk we will introduce the notion of Data-Dependent Functions and we report computational results obtained with three families of functions. We also discuss two new methods for generating other functions, with a higher computational cost. The first method consists in iteratively composing the three functions previously proposed. The second one uses the enumerative method of Carlier et Neron (2002) to generate discrete DFF. We provide computational experiments to compare the effectiveness of the two methods against classical benchmarks derived from the literature.