Two-staged two-dimensional bin packing
optimization with flexible bin size for steel mother plate design: Benchmark
problems
Full paper: J. Wi and B. Kim, ¡° Two-staged two-dimensional bin packing optimization with flexible bin size for steel mother plate design¡±, working paper, 2008
1. Introduction
The two-staged two-dimensional bin packing problem
with flexible bin size is a new variant of two-dimensional bin packing problem
(2DBP). Generally, in the 2DBP, small rectangular items are assigned to large
rectangular bins without overlapping, with the objective of minimizing the
number of bins required (Lodi et al., 1999). Depending on the constraints and
the assumptions considered, 2DBP is classified into many variants. The
guillotine cut requires that each item must be cut with a sequence of
edge-to-edge cuts parallel to the edges of the bin. The maximum number of cuts
permitted is another important constraint. When at most two guillotine cuts are
permitted to obtain an item from the large rectangular bin, the 2DBP becomes a
two-staged problem (Vasco et al., 1989). In the two-staged 2DBP, an item is cut
by at most two cuts, but an additional trimming cut is allowed as figure 1.
Most studies assume the single bin size. When more than one bin sizes are
available, the problem becomes the variable size bin packing problem (Correia
et al., 2008). In our problems the bin size is not predetermined but should be
determined during the optimization procedure. While there are numerous studies
for bin packing problems, it is difficult to find earlier studies that take up
the problem with all peculiarities stated earlier.
Figure 1. two-staged guillotine cut bin
packing
The issues of our study are derived from the steel
mother plate design problem in the steel industry. The plate product is a thick
steel sheet that is mainly used for shipbuilding, bridge construction, and
large oil pipelines. The plate product is cut from a big rectangular plate
called ¡°mother plate¡±. The mother plate is rolled from a slab through a series
of rolling processes, while the slab is manufactured through a series of
processes including iron making, steelmaking, and continuous casting. Since a
slab is rolled into a mother plate through a series of horizontal and vertical
rolling processes, different-sized mother plates can be generated from a
single-slab type. When a plate is cut from a mother plate, the guillotine cut
is required for production efficiency and cost reduction. The steel mother
plate design problem requires placing the order plates (items) on the mother
plates (bins) in a guillotine-cut pattern and determining the sizes of mother
plates with the objective of minimizing the number of slabs or mother plates.
We consider a single-slab type and we assume that
all the order plates have the same thickness. Order plates with a different thickness cannot be cut from the same mother plate and as such, cannot be placed into the same mother plate. Since the volume of a slab does
not change through the rolling processes, the volumes of the slab and its
rolled mother plate are the same. Thus, assuming a single-slab type and the
same order plates¡¯ thickness in the problem, the area of any mother plate is
fixed. However, the sizes (width and length) of mother plates can vary in
numerous ways.
With this explanation, our problem can be stated as
follows.
Input:
sets of items (order plates), the area of a bin (mother plate),
the
maximum and minimum width of a bin,
the
maximum and minimum length of a bin
Objective:
minimize the number of bins required
Output:
the size of each bin (width and length), arrangement of items in bins
Figure
2. Mother plate design problem
2. Benchmark Problems
Park (2007) analyzed the real order plate data of a large steel company and made the
benchmark problems with his problem generator. The optimal solutions for the
benchmark problems are known.
Table 1 shows the characteristics of the benchmark problem sets. The first and third columns show the problem set name as well as the number of bins in the optimal solutions. For example, the optimal solution of problem set 10 needs 10 bins. Each problem set consists of 10 instances. The second and fourth columns show the range of the number of items in each problem and the average number of items in each problem set. The benchmark problem sets consist of 11 problem sets, thus the total number of problem instances is 110.
Table 1. Benchmark problems
|
Problem set (=optimal
number of bins) |
Range of the number of items
(average) |
Problem set (=optimal number of bins) |
Range of the number of items
(average) |
|
35 ~ 45 (40.0) |
733 ~ 784 (762.3) |
||
|
72 ~ 82 (78.8) |
1505 ~ 1552 (1529) |
||
|
145 ~ 162 (153.5) |
2247 ~ 2336 (2299.4) |
||
|
216 ~ 237 (229.4) |
3038~3135 (3070.8) |
||
|
295 ~ 319 (308.0) |
3048~3903 (3735.4) |
||
|
367 ~ 397 (382.9) |
|
|
Table 2. Problem file
format
|
Item
ID |
Item width |
Item length |
|
1 |
4185 |
11400 |
|
2 |
1900 |
6100 |
References
Lodi, A., Martello, S. and Vigo, D., 1999. Heuristic and metaheuristic approaches for a class of two-dimensional packing problems. INFORMS Journal on Computing, 11(4), 345-357.
Vasko, F.J., 1989. A computational improvement to Wang¡¯s two-dimensional cutting stock problem. Computers & Industrial Engineering, 16(1), 109-115.
Correia, I., Gouveia, L., Saldanha-da-Gama, F., 2008. Solving the variable size bin packing problem with discretized formulations. Computers & Operations Research, 35(6), 2103-2113.
Park, S., 2007. Two-dimensional bin packing problems in steel industry. Thesis (PhD). Pohang University of Science and Technology (POSTECH), Korea.