Viewed abstractly, producing a layout requires assigning a given stock of items to given space. Historically, layout research has been carried out in at least two research fields, namely operations research and artificial intelligence. The layout problems studied in these fields may roughly be divided into two categories: the minimization of empty space within a given, fixed area, and the minimization of area used for a given, fixed set of items.
In certain layout problems the aim is to fit the given contents to the
given, fixed area, or conclude that this is impossible. These may be
formulated as quadratic assignment problems (QAP), i.e. assigning N
items to N locations
. The
precise formulation depends on the problem. Unfortunately, the QAP is
NP-complete (well-known, see e.g. Kouvelis et al.,
1992), and does not suit well to 2-dimensional or
3-dimensional problems with varying-sized elements, because the
available positions depend on what elements have already been
inserted.
In some problems, all the given material must be laid out, simultaneously minimizing the total space or transportation of resources between items, or while some additional constraints between the items are obeyed.
In this set of problems, active research can be found for instance from operations research. The problems vary from VLSI chip layout design to plant machinery layout design and to deciding the placement of interacting departments and facilities in an office building. Further taxonomy for machine layout problems has been described in [Heragu, 1992]. Also some problems mostly studied in artificial intelligence may be viewed as falling into this category: in pagination of yellow page telephone directories or newspaper advertisements all the items must be placed into the publication whose length is not exactly fixed in advance.
A number of optimal algorithms have been developed to solve the layout problem. However, due to the NP-completeness of QAP, these algorithms cannot be used to solve large-scale layout problems, such as problems with fifteen or more items [Heragu and Alfa, 1992]. Therefore, also different types of suboptimal algorithms have been designed, falling into the following classes:
In some problems the space to be filled is fixed and must be used as efficiently as possible by items from the given stock. Application areas falling under this category include cutting required shapes and sizes from cow skin, textiles or metals and filling a series of trucks with material to be transported. Sometimes additional constraints are defined e.g. for the the cutting equipment, such as that the machine only can make "slice cuts" (i.e. cut a piece with a straight line from side to side with no turns or corners on the way). Another example of such constraints is found for instance from filling a truck with given material having handling orders, with constraints like some items may not be placed under other items.
The goal is thus to fill the given space with items selected from the stock and to minimize wasted space. It is not, however, necessary to place all the items from the stock to the layout.
Problems of this kind can be formulated as some variant of the knapsack problem (fill a sack as full as possible from the given stock, or fill the given stock to as few sacks as possible). In this group of problems the sacks have fixed sizes, but the items to be fitted into each sack may vary. The problem of filling any single page of a newspaper falls into this category.