Complexity on some bin packing problems.

摘要

The classical bin packing problem has been studied extensively since the 1970's, and it is known to be applicable to many different areas especially in Operation Research and Computer Science. In this dissertation, we first study the two dimensional bin packing problem, i.e., the problem of determining whether a set of rectangles can be packed into a bounding rectangle. This problem can be related to some practical applications in VLSI floor planning, placement, or job scheduling problems. As the problem is found to be NP-hard, we introduce an effective heuristic, Less Flexibility First, for solving the classical rectangle packing problem. This algorithm can consistently produce packing densities of around 99% on most randomly generated large examples. After that, we continue our work to study a variant of bin packing problems which allows the packing to exceed the bin size but at least a fraction of the last piece is within the bin, and we call it open-end bin packing problem. The goal of the open-end bin packing problem is to find a packing that uses the minimum number of bins. We present the complexity result and give fully polynomial approximation schemes for the open-end bin packing problem. As the problem is shown to be NP-hard, some efficient approximation algorithms which give sub-optimal solutions are derived, simulation experiments are done for investigating their performance and the results are discussed.