Abstract: The 2-D strip packing problem is the problem of loading a subset of a given set of rectangular boxes with profits into a rectangular container so that the stowed profits is maximized.The paper presented u-Block optimization algorithm to find more efficient parameter of block for any value.A new data structure was introduced for different classes of rectangles.At last,u-points of the X axis of the different kinds of rectangular boxes were filled to the maximum profits of the items.Two algorithms were developed,one is an effective block parameter u,another is block selection algorithm based on a simplified data structure.In particular,we presented polynomial time approximation for any value. In the case of polynomial time complexity and ε,we can reduce the required box width from 1+ε to 1,while the beight remains the same.

Key words: u-Block,2-D packing problem,Approximation scheme,NP-hard,Heuristics