A search-based heuristic for the two-dimensional bin-packing problem

A heuristic algorithm combining priority rules with a restricted search procedure is presented for solving the two-dimensional, bin-packing problem. The method of solution is one of problem reduction, where the initial problem is decomposed into subproblems that are solved separately. The search procedure acts to minimize the number of subproblems created in the decomposition, while the priority rules force the search process to give due weight to the less combinatorially-inclined pieces. The algorithm was tested using four heuristic rules for assigning priorities, and data from two previously published algorithms. A good improvement was generally observed.