The two-dimensional strip-packing problem arises frequently in stock-cutting, scheduling, and VLSI design. In this problem, a finite list of rectangles is to be packed into a rectangular bin of finite width and infinite height. The objective is to minimize the height of the region occupied by the packed rectangles. Since the problem in NP-hard, heuristic algorithms have been used for finding a good solution.
This thesis proposes three new heuristic algorithms for solving the two-dimensional strip packing problem. The first two algorithms are employed as underlying strategies for the last. Based on the idea of filling the lowest place in the bin, these two strategic algorithms show similar behaviors to the well-known Baker's bottom-left algorithms. However, both of them can pack n rectangles in O (n log n) time, which lowers the O($n^2$) upper bound in time complexity for the Baker's algorithms. The last algorithm adopts a strategy of combining the better aspects of the two algorithms. Specifically, it starts with the width-based algorithm and then changes to the height-based one as it is appropriate. Experimental results support that the strategy-combining algorithm outperforms other algorithms including the two strategic ones.
