A NOVEL GRAPH BASED ALGORITHM FOR ONE DIMENSIONAL BIN PACKING PROBLEM

Debajit Sensarma, Samar Sen

Abstract

The Bin Packing Problem (BPP) is one of the most known combinatorial optimization problems. The main objective of the problem is to minimize the number of bins used and pack the items with different sizes in finite number of bins efficiently. This paper introduces a new graph based algorithm for one dimensional bin packing problem. The proposed algorithm is implemented and tested with the well known benchmark instances and a comparison with existing First-Fit Decreasing (FFD) algorithm is given with respect to number of bins and waste space. In most of the cases the new algorithm produces near optimal solutions and performs better than FFD.