A two-dimensional bin packing problem with size changeable items in the open die forging
Full paper: J. Lee and B. Kim, and A. L. Johnson ¡°A two-dimensional bin packing problem with size changeable items in the open die forging¡±, working paper, 2011
1. Introduction
Open die forging is a metal forming process in which a workpiece is pressed between flat or simple curved dies to create a specific shape and characteristics. There are seven steps to final product: cutting, heating, forging, heat treatment, machining, inspection, and packing. The cutting procedure uses a gas flame or a cutting machine to cut the raw material into smaller pieces. The sales of custom open die forging industry in North America is over 1.6 billion dollars in 2010 (Rothaermel, 2011[1]). Since the raw material is very expensive, manufacturers seek to avoid producing unnecessary scrap.
The real-world case study company manufactures various components of wind turbines from three types of raw materials, steel slab, steel bloom, and round bar, based on the requirements of the components and the characteristics of the raw materials. When the raw material is a bloom or a round bar, it is cut in lengths of specific dimensions, meaning that the cutting design problem described in this paper could be considered a typical one-dimensional cutting stock problem or bin packing problem. However, when the raw material is a steel slab, it is cut in lengths and widths whose sizes vary within a range if the cut volume remains the same. The forging machine¡¯s size limitation can also be a factor. Thus, the problem differs from the well-known two-dimensional bin packing problem (2DBP). Although we researched the range of raw materials, we limit our discussion to steel slabs for specificity and because steel slab is the most prevalent raw material.
To improve productivity and reduce costs, of cutting, the design of cutting utilizes a guillotine cut, i.e. the knives or flame cut from edge to edge of the raw material. Thus, the problem becomes a two-dimensional guillotine cut bin packing problem with items having fixed areas and whose width and length can vary within a specific range.
We present a non-linear mathematical model and propose a knapsack based heuristic algorithm. The algorithm is successfully applied to the real-world company and the annual cost reduction is estimated to be about 2 million US dollars.
2.Benchmark Data
2.1 Practical Data
Benchmark data is originated from the company and we changed them to fit our problem. The sizes of items can be changed and the sizes of bins are fixed in our problem. 10 problem sets were generated. The same slabs are used for each problem set but the items are different and each set has 91~111 items to be cut. Each slab has different size but all the slabs have the same area size of 14532484 mm2 to make the calculation of lower bound(LB) easy. Parameters are assumed as follows: limit ratio=2.3, press limit length (L) = 2500mm, cut loss (B) = 0 and 9 mm. Slab data can be downloaded (here)
Table 1 shows the
experimental results. The first column and the second column shows problem
number and the number of items in the problem set, respectively. The third
column shows the lower bound of the number of slabs required to pack the items.
The lower bounds were calculated as 
assuming cut loss = 0 mm. In
other words, lower bound of a problem is the minimum LB which satisfies 
.
|
Table 1. Benchmark data and result |
||||||
|
Problem |
number |
Lower bound |
Number of slabs used |
Computation time(sec) |
||
|
of items |
B = 0 mm |
B = 9 mm |
B = 0 mm |
B = 9 mm |
||
|
97 |
7 |
7 |
8 |
264 |
249 |
|
|
93 |
6 |
6 |
7 |
194 |
192 |
|
|
100 |
7 |
7 |
7 |
227 |
234 |
|
|
111 |
4 |
4 |
5 |
169 |
173 |
|
|
91 |
3 |
3 |
4 |
91 |
107 |
|
|
96 |
8 |
9 |
9 |
244 |
256 |
|
|
100 |
13 |
13 |
14 |
358 |
345 |
|
|
102 |
5 |
6 |
6 |
205 |
204 |
|
|
100 |
4 |
4 |
5 |
144 |
145 |
|
|
94 |
8 |
8 |
9 |
268 |
258 |
|
* Download practical data in zip format : click here
2.2. Historical Averaged data
For the historical averages data set we generate 200 different combinations of the item sizes and the number of items as shown in Table 2. Within each set of instances, there are 5 sub-sets each with a different number of items. The first set of instances, Small (1), has smaller items to pack. The area of the items is drawn from a uniform distribution on the range 63,700 to 849,300 mm2. Column 4 defines the uniform range over which the item sizes are drawn. The ranges are based on the turbine flange manufacturer¡¯s customer order history. All problem instances in the historical averages data set have 300 slabs with different areas. The widths of slabs are drawn from U[1000, 3000] mm, and the lengths from U[2000, 8000] mm. The range of the distribution widths and lengths of slabs are also derived from the company¡¯s prior experience. Slab costs are randomly generated from U[100,500].
Table 2. Historical averages data set
|
Item size |
Number of items |
Number of problem instances |
Area distribution (mm2) |
|
Small(1)¡¡ |
100 |
10 |
U[63700, 849300] |
|
200 |
|||
|
300 |
|||
|
400 |
|||
|
500 |
|||
|
Medium(2)¡¡ |
100 |
10 |
U[849300, 1698500] |
|
200 |
|||
|
300 |
|||
|
400 |
|||
|
500 |
|||
|
Large(3) |
100 |
10 |
U[1698500, 3397000] |
|
200 |
|||
|
300 |
|||
|
400 |
|||
|
500 |
|||
|
All(4) |
100 |
10 |
U[63700, 3397000] |
|
200 |
|||
|
300 |
|||
|
400 |
|||
|
500 |
¡ØU[lower, upper]: uniform distribution between lower and upper in mm2 scale
Size(number): size category and the nominal number of each category
* Download historical averaged data in zip format : click here