An effective heuristic for the two‐dimensional irregular bin packing problem

This paper proposes an adaptation, to the two‐dimensional irregular bin packing problem of the Djang and Finch heuristic (DJD), originally designed for the one‐dimensional bin packing problem. In the two‐dimensional case, not only is it the case that the piece’s size is important but its shape also has a significant influence. Therefore, DJD as a selection heuristic has to be paired with a placement heuristic to completely construct a solution to the underlying packing problem. A successful adaptation of the DJD requires a routine to reduce computational costs, which is also proposed and successfully tested in this paper. Results, on a wide variety of instance types with convex polygons, are found to be significantly better than those produced by more conventional selection heuristics.