Considerations on 2D-Bin Packing Problem: Is the Order of Placement a Relevant Factor?

摘要

The problem of packing a given sequence of items of 2-dimensional (2D) geometric shapes into a minimum number of rectangle bins of given dimensions is called the 2D bin packing problem. This problem has various applications across many industries such as steel-, paper- and wood-industries where objects of certain shapes are needed to be cut from large rectangle panels with the most efficient use of materials. This problem, however, belongs to the class of NP-Hard problems, implying that no perfect solution exists. Many proposed solutions involve the use of advanced metaheuristic search techniques such as Local Search, Simulated Annealing or Genetic Algorithm, but most of them are still greedy-based, which means some greedy technique such as First-Fit is still used as their core placement algorithm and optimization techniques are employed only to search for a good ordering or orientation (rotation angles) of the objects so that the placement procedure can yield the best possible results. Practice has shown that greedy placement algorithm on the simple area decreasing order can produce excellent results comparable to those on orderings generated from advanced optimization techniques. This paper discusses the relevance of the order of placement in the 2D bin packing problem.