ALGORITHMS FOR AN INCREMENTAL BIN-PACKING SYSTEM

Abstract

This thesis describes the design, analysis, and implementation of a software system for the Incremental Rectangle Packing Problem. The general bin-packing problem is the problem of packing a collection of objects (of any dimension) into well-defined regions (called bins) such that they do not overlap, The overall aim is to maximise the utilization of the space inside the bins or equivalently, minimize the wastage. We choose to study the rectangle packing problem because it is one of the most extensively researched variant of the bin-packing problem. The problem arises in many industry sectors (such as manufacturing, construction and publication) where there is widespread industry used for solutions. However, although there has been extensive research work on the problem, there have been surprisingly few commercial software systems for rectangle packing. Furthermore, most of the rectangle packing systems perform only off-line packing in which all the rectangles are known before the packing process begins. Incremental changes to the packing require a re-execution of the packing process. Lastly, most of the packing algorithms used (namely, approximation algorithms or heuristic-based algorithms) suffers from the disadvantage that the quality of the packing deteriorates as the problem size increases. Therefore, what is required is a packing system that provides a "total solution" to the packing problems, namely, a system that are not only supports off-line packing, but also provide useful decision support features for users to interactively edit and improve the packing generated. This motivates us to develop the system I-RAS (Incremental Rectangle pAcking System) that supports such interactive manipulation of the packing. In addition to simple updates to the packing (insert/delete/move rectangles), the system also provides powerful decision support features for users to interactively optimize the packing. These include answering routine queries such as "Which rectangles can still fit and where?" and optimization queries such as "Where is the "best" location for this rectangle?". Based on the decision support for the optimization queries, the system also provides a feature for auto-packing of new rectangles. In addition, algorithm animation is also implemented in the prototype system. Basic file and edit operations are also included to make our prototype a complete stand-alone system. The emphasis in this thesis is on the design or efficient data structures and algorithms for implementing the various update and decision support features for I-RAS. The study or the Incremental Rectangle Packing Problem leads us to the study of the representations schemes to support fast update and decision support operations. We proposed two representations, namely the Rectangulation Graph (RG) and the Aspect Ratio Graph (AF). The RG (constructed based on a vertical space partitioning technique) allows incremental update operations to be done very efficiently. The AF is built from the set of maximal rectangles, that can be constructed using a plane-sweep algorithm. The AF supports efficient (logarithmic time) routine decision support features. The AF also aid in the implementation of heuristics for decision support for optimization queries. Incremental update of the AF is also studied. In conjunction with the RG representation, we also studied a related problem called the Optimum Partitioning Problem that has applications in layout of VLSI circuits. We first derived a new counting formula for the number of "free blocks" in a general partition. Then, based on this formula, a polynomial time algorithm is presented to solve the Optimum Partitioning Problem.