Last two fit augmentation to the well-known construction heuristics for one-dimensional bin-packing problem: an empirical study

Abstract

The bin-packing problem is a combinatorial optimization problem that has been widely applied in many manufacturing and logistics industries. It requires packing a set of different-sized items into a minimum number of identical bins. This paper introduces the last two fit (L2F) augmentation to the well-known next fit decreasing, first fit decreasing, and best fit decreasing algorithms for the one-dimensional bin-packing problem. L2F checks whether an additional item can be packed into the bin when an item is packed; if it cannot be done, replacement of the item with a pair of two unpacked items whose combined size is larger than the item is pursued. The focus of this paper is on improving the well-known construction heuristics with L2F and comparing their performance to the original heuristics. Experiments with benchmark problem sets show the effectiveness of the L2F augmented algorithms.