The problem of packing two‐dimensional items into two‐dimensional bins is considered in which patterns of items allocated to bins must be guillotine‐cuttable and item rotation might be allowed
. Three new constructive heuristics, namely, first‐fit insertion heuristic, best‐fit insertion heuristic, and critical‐fit insertion heuristic, and a new justification improvement heuristic are proposed. All new heuristics use tree structures to represent guillotine‐cuttable patterns of items and proceed by inserting one item at a time in a partial solution. Central to all heuristics are a new procedure for enumerating possible insertions and a new fitness criterion for choosing the best insertion. All new heuristics have quadratic worst‐case computational complexity except for the critical‐fit insertion heuristic which has a cubic worst‐case computational complexity. The efficiency and effectiveness of the proposed heuristics is demonstrated by comparing their empirical performance on a standard benchmark data set against other published approaches.
