Research On The Two-Dimensional Variable-sized Bin Packing Problem

The two-dimensional variable-sized bin packing problem (2DVSBPP) mainly research on how to layout the rectangular products with different shapes on the chose variable-sized bins so that producing the least waste and making the best of materials. As a well-known NPC problem,2DVSBPP has two constraints:the one is guillotine constraint, the other is the rotation of the workpieces. A Relaxed Search Approach (RSA) is proposed to solve the 2DVSBPP with guillotine constraint of bin and rotatable workpieces. The contents of RSA can be described as follows.The first one is a constructed algorithm for bin group. The algorithm based on the total area of rectangular products is considered to choose the feasible bin group, and then sort for the bins according to the area of increasing order.The second one is a single bin packing algorithm. The algorithm is a group-based heuristic algorithm which combines workpieces to be group which act as the unit of packing problem. After putting a group on the chose bin by the designated rule, a ’placing & splitting’ recursive structure is used to pack the remains. The backtracking rule is the quest of lowest given utilization, which is also cooperating with a binary-search algorithm to converge the solutions and improve the utilization rate of the single bin.The third one is a relaxed search approach. RSA is executed by relaxing the total area of workpieces and replacing the bins, until all workpieces layout on the bins.The last one is a reprocessing algorithm. The algorithm is considered to perform a task of breaking up and recombining the packed workpieces to further improve the utilization rate of materials.Computational experiments on the benchmark instances show that the RSA has achieved good results and outperforms existing algorithms.Besides, based on the RSA and the enterprise’s production needs, we designed computer aided system for two-dimensional variable-sized bin packing problem.