A new heuristic algorithm for the one-dimensional bin-packing problem

摘要

We describe a new heuristic algorithm to solve the one-dimensional bin-packing problem. The proposed algorithm is optimal if the sum of requirements of items is less than or equal to twice the bin capacity. Our computational results show that effectiveness of the proposed algorithm in finding optimal or near-optimal solutions is superior to that of the FFD and BFD algorithms, specifically for those so called 'difficult' problems that require an optimal solution to fill most of the bins if not all, exactly to capacity.