Abstract: The guillotine rectangular strip packing problem is NP-hard.This problem has industrial applications such as glass cutting and integrated circuit layout design.These real world applications can be formulated as packing problems with the objective of maximize the usage ratio of the materials.The whole sketch is as follows.Firstly,a hybrid search algorithm is presented for solving the two dimensional guillotine rectangular packing problem (2D-GRPP),then the hybrid search algorithm is adopted for solving the two dimensional guillotine rectangular strip packing problem (2D-GRSPP) in the manner of jump search and binary search.According to the quasi-human approach,the basic definitions such as corner-occupying,action space,maximal height and rectangle combination are presented so as to induce the basic algorithm.Based on the basic algorithm,the hybrid search algorithm involves three phases.In the first phase,the initial solution is generated.In the second phase,the local search procedure runs to adjust the priority numbers of the rectangles.When the local search procedure encounters local optimal solutions,the off-trap strategy procedure is used to jump out of the trap and guide the search into the new areas.In the third phase,the beauty degree enumeration procedure is adopted to improve the selection of the corner-occupying actions.The hybrid search algorithm (called HS) is tested on two sets of 91 benchmark instances.The computational results show that the proposed algorithm generally outperforms the best heuristics (called SPTRS) in the literature up to now.The mean relative errors of HS and SPTRS are 3.83% and 4.26%,respectively.The HS algorithm is efficient for solving the problem.

Key words: Global optimization, Guillotine, Heuristic, Quasi-human, Rectangular strip packing