A simplified steel plate stacking problem
Full paper: B. Kim and J. Koo, ¡° A simplified steel plate stacking problem¡±, working paper, 2009
1. Introduction
Stacking problems occur in many
areas such as container ship stowage planning, container terminal stacking
planning, shunting of rail cars, steel slab stacking, and steel plate stacking
problems.
This paper studies a steel plate
stacking problem which was introduced by Ko (2007). Manufactured thick steel
plates arrive at a storage area one at a time as shown in Figure 1(a). Each
plate has its incoming and outgoing order and they are known in advance. The
arriving plates are first stacked on beds in the storage area, after which the
plates are then removed in the pre-defined delivery sequence. We assume that
all the plates are stacked before any plates start to be removed from the
stacks. There are a given number of beds in the storage area. No more than one
plate can be moved simultaneously. Each bed is assumed to take a unlimited
number of plates. Although this is not a realistic assumption, it is not a
critical one since the thicknesses of plates are very small compared to the
possible height of a yard and in practice many plates can be stacked on a
single bed.
The plates can be stacked in many
different ways. Figure 1(b) and 1(c) show two stacking examples for the plates
of Figure 1(a). Note that a plate with a higher incoming order cannot be placed
under any plates with a lower incoming order. When the plates are stacked like
Figure 1(b), in order to remove the first outgoing plate noted (1,1), two
plates, (2,5) and (3,6), must be relocated. These relocations are called shifts.
We assume that the relocated plates will be moved back and stacked in their
original order immediately after the target plate (1,1) is taken out. Thus,
when plate (2,5) is to be delivered, plate (3,6) must be relocated again. Note
that Tang et al. (2002) also assumed the same. We count a plate¡¯s relocation
and return together as one shift. Thus, the total numbers of shifts for Bed #1
and Bed #2 of Figure 1(b) are 3 and 4, respectively. The stacking of Figure
4(c) requires 4 shifts (each bed needs 2 shifts) and so it is a better solution
than Figure 4(b) which requires 7 shifts. The objective of this problem is to make
a storage plan to minimize the total number of shifts required.
Figure
1. The plate stacking problem
2. Benchmark Problems
Ko (2007) made some benchmark problems. He generated and used two sets of
100 problem instances: a 30 plate- 3 bed set and a 1000 plate– 50 bed set. The
outgoing order for each plate was randomly generated without duplication. The
benchmark problems can be downloaded from Table 1. Table 2 shows the problem
file format.
Table 1. Benchmark problems
|
Problem set |
Number of plates |
Number of beds |
|
30 |
3 |
|
|
1000 |
50 |
Table 2. Problem file
format
|
PlateID |
Incoming_order |
Outgoing_order |
|
1 |
1 |
5 |
|
2 |
2 |
23 |
References
Ko, S., 2007. An
Efficient Stacking Policy for the Steel Plate, Thesis(M.S.). Pohang University of Science and
Technology, Pohang, Korea (in Korean).