A Hybrid Genetic Algorithm for Bin Packing Problem Based on Item Sequencing

Abstract

The bin packing problem based on item sequencing is defined as follows: given a set of sequenced items of different sizes, how should one pack them all into bins of different capacity, in order to make the utility ratio of bin capacity as higher as possible? In this paper, next fit algorithm, a heuristic method for bin packing problem, is introduced into simple genetic algorithm, and a hybrid genetic algorithm is proposed for solving bin-packing problem based on item sequencing. In the hybrid genetic algorithm, the idea of simple genetic algorithm is used to search the solution of the bins sequence, and the idea of next fit algorithm is used to pack the sequenced items into the bins sequence obtained. Finally, the effectiveness of the hybrid genetic algorithm is convinced through computational results of an example.