Content area
"Packing", to stow as if in a container, especially under physical constraints, is a common phenomenon. These problems have wide applicability and suitability as a testbed for algorithm analysis.
This dissertation covers several issues about packing problems with physical constraints. They are: on-line packing (2-dimensional bin packing and "potato" sack packing), balanced packing and a box-stacking problem. Among them, the 2-dimensional bin packing problem is a well-studied topic and the others are first considered in this dissertation. The on-line potato sack problem is a fresh version of the famous scottish book problem and the balanced packing problem and the box-stacking problem are newly defined.
In practice, physical factors play important roles in many packing problems. The problems cannot be adequately modeled without consideration of these factors. For example, in applications that involve packing, it is advantageous or even necessary to construct the packing "on-line"; that is to construct a solution as data is being accepted. Another physical consideration in packing is balance; for example, the load on an aircraft must be balanced so that the plane flies with the correct pitch. This balance requirement may greatly affect the capacity of the aircraft. A third physical consideration is stability. Consider, for example, palletizing cartons in a warehouse. To ensure the stability of each pallet, each box should be fully supported either by the pallet or by the faces of other boxes. Suitable packing models in these application areas must account for these physical factors. The analysis of an on-line 2-dimensional bin packing heuristic and the study of the balanced packing problem and the box-stacking problem are directly motivated by such applications.
In the first and the second chapter we give the average-case and the worst-case performance analysis for the shelf-heuristic; in the third chapter we define balanced packing and analyze several algorithms; in the fourth chapter we solve the on-line potato sack problem and in the last chapter we define the box-stacking problem and find the maximum number of ways to stack boxes into a stable column.