Abstract
In this thesis, we consider the three-dimensional orthogonal bin packing problem, which is a generalization of the well-known bin packing problem. The problem is useful to many practical applications, such as logistics industry, transportation industry and manufacturing industry. A better packing result can obviously reduce inventory costs and transportation costs. In order to evaluate the quality of algorithms for the bin packing problem, we study the literatures and look into lower bounds of the problem. We present new low-er bounds for this problem and demonstrate that they improve the best previous results, the results proposed by Boschetti [3] in 2004. We also provide a strictly better example to emphasize the difference between the lower bounds. The asymptotic worst-case performance ratio, which can show that our lower bounds are bounded within a constant ratio in the worst case, is also proved. In addition, we study an extension of this problem, the non-oriented model, which allows items to be rotated in 90 degrees. We study how to compute lower bounds for this model and demonstrate that our lower bounds improve the best previ-ous results for this model.