Bidirectional best-fit heuristic considering compound placement for two dimensional orthogonal rectangular strip packing

The two dimensional orthogonal rectangular strip packing problem is a common NP-hard optimisation problem whereby a set of rectangular shapes must be placed on a fixed width stock sheet with infinite length in such a way that wastage is minimised and material utilisation is maximised. The bidirectional best-fit heuristic is a deterministic approach which has previously been shown to outperform existing heuristic methods as well as many metaheuristics from the literature. Here, we propose a modification to the original bidirectional best-fit heuristic whereby combinations of pairs of rectangles are considered generating improved results over standard benchmark sets.

► A modified version of the bidirectional best-fit heuristic is presented. ► The modified heuristic also considers placement of rectangles in pairs. ► Modified BBF is tested on five different benchmark sets from the literature with varying properties. ► The modified heuristic offers improved performance in over two-thirds of benchmark instances. ► The performance of this deterministic method is comparable to state-of-the-art methods.