Sequence based heuristics for two-dimensional bin packing problems

This article addresses several variants of the two-dimensional bin packing problem. In the most basic version of the problem it is intended to pack a given number of rectangular items with given sizes in rectangular bins in such a way that the number of bins used is minimized. Different heuristic approaches (greedy, local search, and variable neighbourhood descent) are proposed for solving four guillotine two-dimensional bin packing problems. The heuristics are based on the definition of a packing sequence for items and in a set of criteria for packing one item in a current partial solution. Several extensions are introduced to deal with issues pointed out by two furniture companies. Extensive computational results on instances from the literature and from the two furniture companies are reported and compared with optimal solutions, solutions from other five (meta)heuristics and, for a small set of instances, with the ones used in the companies.This work was supported by project SCOOP - sheet cutting and process optimization for furniture enterprises (Contract NoCOOP-CT-2006-032998), financed by the European Commission, 6th Framework Programme on Research, Technological Development and Dissemination, specific actions for SMEs, Cooperative Research Projects. The fifth author was also supported by Grant SFRH/BD/42259/2007 from Fundacao para a Ciencia e Tecnologia, Portugal