Cutting and Packing Problems
Prof. Flavio Keidi Miyazawa
Packaging problems, like many of a combinatorial nature, can be easily formulated and understood, hiding behind their apparent simplicity, their real complexity. These are NP-difficult problems that cannot be approximated --- in absolute terms --- in addition to certain constants, unless P = NP. This complex character in terms of absolute approximability, justifies the study of these problems in terms of their approximation in asymptotic terms.
We consider several bi- and three-dimensional packaging problems here, many of them already investigated under this approach, and describe for these problems approximation algorithms whose limits of asymptotic performance are better than those found in the literature.
First, we will introduce the reader to several packaging problems, illustrating the occurrence of several of them in the process of building a building.
First, consider the reinforced concrete structure of a building. More precisely, consider the concrete columns containing steel bars inside. These columns can have different lengths and therefore each requires bars with a certain length. In general, the factory that produces these bars only produces them with a specific length, say 12 meters. Thus, the construction company must buy these large bars and cut them according to their needs. Clearly, to minimize costs, your goal is to purchase the fewest bars needed in construction. This is a very common problem that also appears in problems of cutting beams, metal structures, pipes, frames, etc. It is a one-dimensional packaging problem. Example:
Proceeding with the construction of the building, now consider the rectangular glass windows and partitions, which are needed in different quantities and sizes. The construction company makes the purchase order to a glass company, specifying the dimensions and quantities of each item. The glass manufacturer must cut these pieces from fixed-sized glass plates, which are supplied by the glass manufacturer. Again, to minimize costs, the purpose of glass making is to use the fewest of these plates. This problem also appears when cutting sheets, partitions, plywood, etc. We have here a packaging problem (two-dimensional) in plates. Example:
Now consider the following problem. The construction company, having finished the construction of the building, hires an advertising company to make flags, banners, caps and T-shirts with the advertisement of the building. To make all this advertising material, the company needs to buy a certain amount of fabric. The weavers produce fabrics with a fixed width and variable length, the cost of which is proportional to the length. So, to minimize your expenses, the advertising company's goal is to buy the shortest length of fabric needed to cut all the items requested. This is a banding (two-dimensional) packaging problem. Example:
Another problem that occurs is related to the transport of products and cargo to the building construction site. Various products (such as glass, floors, tiles) must be boxed and then transported in fixed-size vans. To minimize costs the goal here is to make the fewest trips from the hardware store to the construction site. The problem is to pack the boxes in the smallest number of vans and, consequently, to minimize the number of trips. This is a problem of packaging in containers. Example:
Once the products are transported to the construction site, they must be stored in a shed (in a rectangular shape), in order to be protected until use. The problem arises here of packing these boxes inside the shed. The goal is to find a package whose height is as small as possible.
The problems involved in the examples above are called cutting problems and / or packaging problems. According to the definition of packaging we present, the problems of cutting bars, glass, fabrics or other materials can be seen as packaging problems (of pieces of bars in bars, molds in glass or fabrics).
Generally speaking, packaging problems consist of packing a list of items in containers. Depending on the nature of the items being packaged, we say that the problems are uni-, bi- or three-dimensional.
The problems addressed may differ in two lines depending on the objective function of the optimization problem in question. In one of these lines, the objective is to minimize the number of containers used to package the items on the list. In another line, the items must be packed in only one container, this container has only an unlimited dimension and all others are limited (for example, a box with a limited bottom and unlimited height). In this case, the objective is to minimize the `size 'of the packaging in relation to the unlimited size of the container. We refer to this size as the height of the packaging.
Some of the applications for cutting and packaging problems are: allocation of TV commercials, allocation of programs on discs and magnetic tapes, vehicle loading, vehicle programming problems, cutting of reels (paper, steel, ...), cutting of beams (in lumber, civil construction, ...), pre-paging, cutting of plates (glass, plates, wood, plywood, ...), cutting of scraps in a fabric factory, or in the making of clothes, packaging of boxes in warehouses, packaging in containers, loading cargo in vans and cutting foam for mattresses.