Generating Pallet Loading Patterns: A Special Case of the Two-Dimensional Cutting Stock
Problem
Author(s): Harold J. Steudel
Source: Management Science, Vol. 25, No. 10 (Oct., 1979), pp. 997-1004
Published by: INFORMS
Stable URL: [Link]
Accessed: 27/01/2010 05:41
Your use of the JSTOR archive indicates your acceptance of JSTOR's Terms and Conditions of Use, available at
[Link] JSTOR's Terms and Conditions of Use provides, in part, that unless
you have obtained prior permission, you may not download an entire issue of a journal or multiple copies of articles, and you
may use content in the JSTOR archive only for your personal, non-commercial use.
Please contact the publisher regarding any further use of this work. Publisher contact information may be obtained at
[Link]
Each copy of any part of a JSTOR transmission must contain the same copyright notice that appears on the screen or printed
page of such transmission.
JSTOR is a not-for-profit service that helps scholars, researchers, and students discover, use, and build upon a wide range of
content in a trusted digital archive. We use information technology and tools to increase productivity and facilitate new forms
of scholarship. For more information about JSTOR, please contact support@[Link].
INFORMS is collaborating with JSTOR to digitize, preserve and extend access to Management Science.
[Link]
MANAGEMENT SCIENCE
Vol. 25, No. 10, October 1979
Printed in U.S.A.
GENERATING PALLET LOADING PATTERNS: A
SPECIAL CASE OF THE TWO-DIMENSIONAL CUTTING
STOCK PROBLEM*
HAROLD J. STEUDELt
A heuristic algorithm employing dynamic programming is presented for solving the
two-dimensional cutting stock problem where all the small rectangles are of the same
dimensions, but without the usual restriction that the cutting be done with "guillotine" cuts,
i.e., cut which must be made in stages from one edge to the opposite edge of the large
rectan,glebeing cut. The objective of the algorithm is to determine a cutting or layout pattern
for which the ratio of the unused area to the total area of the large rectangle tends to be
small. To demonstrate the method, the common problem of establishing standardized loading
patterns for rectangular items on pallets is examined in detail. The algorithm is described with
a minimum of mathematics through the use of several pictorial displays and a simple
example. The efficiency of the heuristic is then evaluated by comparing computer generated
loading patterns for 182 different size items to the loading patterns recommended by the U.S.
Navy, and shown to be 10.4 percent more efficient for 64 out of 182 cases when the number
of items per layer were not identical. The algorithm is also shown to be an effective aid to
management both in establishing standardized loading patterns and procedures, and in
communicating these loading standards to production personnel via computer generated
"shop paper." This type of computer design flexibility and control is a valuable management
tool not only for standardizing pallet arrangements, but for carton design and consolidation,
warehouse design and layout, bin and shelf stocking, designing tapes for numerically
controlled gas cutting machines, and numerous other industrial problems involved with the
efficient layout of rectangular objects.
(DYNAMIC PROGRAMMING-APPLICATIONS; PRODUCTION/SCHEDULING-
CUTTING STOCK; PRODUCTION/SCHEDULING-MATERIAL HANDLING)
1. Introduction
A common problem for consumer goods industries is establishing standardized
procedures for loading finished packaged goods onto pallets for subsequent storage
and distribution. These standards are usually distributed as a specification or methods
sheet consisting of a sketch showing how to position the product on the pallet, plus a
product description and loading instructions. Generating these sheets manually is
largely routine, but nevertheless draws on the experience of an analyst to determine
loading patterns which yield good utilization of the pallet. The task is laborious and
often time consuming. Thus, using a computer to automatically generate loading
specification sheets for pallet loading has considerable practical value to many
companies.
The pallet loading problem can be viewed as a special case of the two-dimensional
cutting stock problem where all the small rectangles are of identical dimensions. The
task consists of partitioning a rectangular pallet of length L and width W into smaller
rectangular areas of length I and width w so as to determine a loading pattern which
tends to minimize the amount of unused pallet deckboard area. The problem is
constrained by maximum load height and weight limitations.
Considerable work has been done on both the one-dimensional and the two-
dimensional cutting stock problem. A recent review of approaches to and computa-
tional experience with one-dimensional cutting problems is given by Golden [3]. The
two-dimensional problem also has been studied by several authors [2], [4], [6]. Most
*Accepted by David G. Dannenbring; received July 5, 1977. This paper has been with the author 7
months for 3 revisions.
tMarquette University.
997
0025-1909/79/25 1O/0997$O1.25
Copyright?5 1980, The Instituteof ManagementSciences
998 HAROLD J. STEUDEL
recently, Christofides and Whitlock [1] have presented an effective tree-search algo-
rithm for solving two-dimensional cutting problems in which a constraint is imposed
to limit the number of each size of small rectangle to be cut. The algorithm is also
constrained to consider only cutting patterns made by guillotine type cuts, that is,
straight cuts made in stages from one edge to the opposite edge of the object being
cut, such as with a common paper cutter. These constraints are common to solutions
currently available.
The requirements for solving pallet loading problems, however, differ in two ways.
For one, items loaded and transported on any one pallet are generally identical in
dimensional size and weight. Secondly, practical experience suggests that considerable
advantage in terms of the utilization of the deckboard area often can be gained by
employing loading patterns which could not be obtained with guillotine type cuts.
In this paper a heuristic algorithm based on dynamic programming is presented for
solving two-dimensional cutting stock problems in which all the small rectangles are
of the same dimensions and nonguillotine cuts are allowed. The algorithm has been
coded using FORTRAN IV to generate pallet deckboard loading patterns which
satisfy commonly accepted criteria of load stability. The effectiveness of the algorithm
is evaluated by comparing 182 computer generated loading patterns with the loading
patterns recommended by the U.S. Navy Supply Research and Development Facility.
The results indicate that the algorithm is both effective and computationally efficient.
2. Model Formulation
The problem is to determine a cutting or "loading" pattern for which the ratio of
the unused area to the total area of the large rectangle tends to be small. To solve this
two dimensional problem, dynamic programming is first used to determine four
optimum sets of length and/or width placements of the small rectangles along the
inside edges of the large rectangle. The objective is to maximize the utilization of the
perimeter of the large rectangle. In the second phase of the algorithm the optimum
arrangement of rectangles along the perimeter is projected inward to fill in the center
portion of the large rectangle so as to minimize the amount of unused area. Each of
the two phases of the resulting heuristic will now be discussed.
Description of the Recursive Procedure
To determine the placement of small rectangles which maximizes the utilization of
the perimeter of the large rectangle, the following recursion is defined:
F,(S,) = MAX[X, * I + Yn * w + Fn l(Sn-01) (1)
subject to:
Xn 1+
l Yn w < D n n=1 .............
.4, (2)
where
Fn(Sn) = the maximum value of the sum of the length and width placements
through stage (edge) n of the large rectangle with state variable Sn entering that stage.
Xn = the number of small rectangles of length I placed lengthwise along edge n.
Yn= the number of small rectangles of width w placed widthwise along edge n.
Dn= the dimensional size of edge n for the large rectangle (either length L or width
W).
Sn= the state variable which defines the initial conditions for edge n. Sn has three
possible values:
S =1: Xn = , Yn=2,
S= 2: Xn = 2, Yn=
GENERATING PALLET LOADING PATTERNS 999
To establish the necessary geometry relationships, a pattern layout is defined to
consist of a set of from one to four of the following "blocks" of small rectangles
where:
B1: the block of rectangles formed by X1 and Y4,
B2: the block of rectangles formed by X2 and Y1,
B3: the block of rectangles formed by X3 and Y2,
B4: the block of rectangles formed by X4 and Y3.
Figure 1 is an example layout pattern which shows the arbitrarily selected designa-
tion of edge n (i.e., stage n) n = 1, . . , 4. Also shown are the four blocks of rectangles
which define the convention for the relative placement of the small rectangles along
edge n. For example, if X1 > 1 (and hence Y4 > 1), then block B1 exists and its
relative placement will be as shown at the intersection of edge 1 and edge 4. Likewise,
if at edge 2 (stage 2) the optimal value of X2 > 1 for some value of the state variable
S2, then block B2 exists which defines the positions of both the X2 rectangles and the
Y1 rectangles. This convention thus prohibits intermixing length and width place-
ments along an edge. Furthermore, all rectangular items are assumed to be stacked on
the bottom or largest area surface.
Description of the Inward Projection Procedure
The second phase of the model projects the arrangement of rectangles along the
perimeter inward to fill in the center portion of the large rectangle. Two potential
problems must be considered. For one, a condition of overlap or interference between
the blocks could occur. An example was shown in Figure 1 where the inward
projection of the perimeter layout results in a condition of interference between
blocks B1 and B3 as indicated by the cross hatched area. The second problem is that
the inward projection could result in a layout pattern which has a central hole larger
than a small rectangle.
The condition of interference is checked for by evaluating simple linear constraints.
For example, interference between blocks B1 and B3 occurs only if both of the
following conditions are true:
(D1-XI-1)<X3 l and (D4- Y4. w)< Y2-W
Likewise, interference occurs between block B2 and B4 when,
(D1- Y1.w)< Y3 w and (D2-X2.l)<X41.
Interference conditions are relieved by treating blocks B1 and B2 as fixed in size.
Blocks B3 and B4 are then modified by redefining values of X3, Y2, X4 and Y3 in
order to satisfy the constraint which was initially in conflict. For the case shown in
Figure 1, the interference condition would be relieved by reducing the value of X3 by
EDGE 1
BLOC BLOC
1 ~~~2
EDGE 4 TEDGE 2
BLC BLOC
4 3
EDGE 3 29 ITEMS/LAYER
FIGURE1. Layout Pattern FIGURE2. Final Layout Pattern
Defined as Four Blocks, after Overlap Correction.
1000 HAROLD J. STEUDEL
one. Accordingly, the value of Y3 would be increased by one. The final layout pattern
is shown in Figure 2. For this layout, the area of the resulting central hole is less than
that of a small rectangle, and hence is insignificantly small. Furthermore, this layout
pattern provides for 29 items per layer (95.2%deckboard utilization), whereas the best
layout which could be obtained with guillotine type cuts would only yield 27 items per
layer (88.6% deckboard utilization). The nested loading pattern also offers good
stability.
In some cases, projection of the perimeter layout inward results in a central hole
which is larger than a small rectangle. This type of situation is shown in Figure 3a.
Although the resulting internal hole is quite large, it cannot be filled in efficiently by
further projection. At this point, the model checks for multiple optimum solutions to
the recursion, and returns to the beginning of Phase 2 if other solutions exist. If no
other optimum solutions exist, blocks Bi and B2 are again held fixed, and blocks B3
and B4 are modified in size. In this case, B4 is expanded and B3 is reduced as shown
by the resulting loading pattern in Figure 3b.
HOLE
la) lb)
FIGURE 3a. Layout Pattern FIGURE 3b. Final Layout Pattern
with Large Central Hole. after Hole Correction.
3. An Example
Consider the problem of determining the pallet loading pattern where L = 48,
W = 40, 1 = 15.5 and w = 9.5. At stage 1 (edge 1) the algorithm determines the
following optimal values of Xi and Y1for the three possible values of S1 subject to the
constraint
15.5(X1) + 9.5(Y1) < 48.0
STAGE 1
State
SI X, Y* Ft (SI)
I 0 5 47.50
2 3 0 46.50
3 1 3 44.00
*Denotes optimum values
At Stage 2 (edge 2) with S2 = 1, the optimum values of the decision variables are
X2 = 0, Y2= 4. The value of the objective function at this stage is 38.00 + 46.50 =
84.50. The additional 46.50 is the optimum value of the objective function at Stage 1
for the entering state variable SI = 2, which is a consequence of the decision of Stage
2. In a similar manner for S2 = 2, the optimal decisions are X2 = 2, Y2 = 0 which
yields the maximum value of F2*(2)= 78.50. These stage 2 decisions allow the state
variable at stage 1 to assume values of either S1 = 1 or SI = 3. The alternative S1 = 1
is selected since this is the better choice. (Fj"(1)= 47.50) Similarly the maximum value
GENERATING PALLET LOADING PATTERNS 1001
of the decision through stage 2 for entering state S2 = 3 is F2*(3)= 34.50 + 47.50 =
82.00. The results are summarized below for stage 2.
STAGE 2
State
S2 X2 Y2 F2(S2)
1 0 4 84.50
2 2 0 78.50
3 1 2 82.00
The solution for the problem through the third stage is obtained in a similar manner
and shown below.
STAGE 3
State
S2 X3 Y3 F*(S3)
1 0 5 126.00
2 3 0 131.00
3 1 3 128.50
The optimum decisions through the third stage yields F3*(2)= 131.00. This value was
obtained under the state variable conditions S3 = 2 and S1 = 2 which in turn dictates
the value of the state variable S4. Thus the result can be obtained in one step.
STAGE 4
State
S4 X4 Y4 F4*(4)
1 0 4 169.00
The optimal solution can now be written for this four stage problem by tracing back
from stage 4 to stage 1. The result at stage 4 determines that S3 = 2 and X3 = 3,
Y3 = 0. This leads to the second stage with S2 = 1 the best choice for S2 and yields
X2 = 0, Y2= 4. Finally at the first stage we get Xl = 3, Y1= 0. In this case, blocks B,
and B3 are identical, no interference or central hold occurs, and the resulting layout
pattern shown in Figure 4a results.
It is interesting to note the value of using the recursive relation expressed by
equation (1). If the decisions were made independently at each stage, (i.e., without a
recursion) suboptimum solutions result. At stage 1, in the above example, the best
"independent" decisions would be obtained with XI = 0, Y1= 5, yielding a "edge 1"
value of 47.50. If these decisions were fixed at this time, the best decisions possible at
(a) 12 ITEMS/LAYER (b) 11 ITEMS/LAYER
FIGURE4a. Layout Pattern Obtained with Recursive FIGURE4b. Layout Pattern
Where L = 48, W= 40, 1 = 15.5 and w = 9.5. Obtained Without Recursive.
1002 HAROLD J. STEUDEL
"edge 2" would be X2 = 1, Y2 = 2. Proceeding to make decisions independently would
finally yield the layout pattern shown in Figure 4b. This pattern, however, is only
93.8%as efficient as that of Figure 4a.
4. ComputationalResults
To evaluate the performance of the algorithm, layout patterns for a 40 inch x 48
inch pallet were generated in 0.50 inch increments for items ranging in size from 5.00
inches to 14.00 inches in width, and from 7.00 inches to 15.00 inches in length. The
TABLE 1
Boxes per Layer on a 40" x 48" Pallet via the Algorithm vs. the Navy Standard (in parenthesis),
Identical Loading Patterns Shown by Asterisk(*)
Box
Width Box Length (inches)
(inches) 7.00 7.50 8.00 8.50 9.00 9.50 10.00 10.50
5.00 52 (51) 48 (45) 48 (45) 45 (45) 40 (39) 40 (39) 36 (34) 36 (36)
5.50 50 (50) 44 (44) 44 (44) 38 (38) 38 (38) 34 (33) 34 (33) 32 (31)
6.00 46 (43) 40 (38) 40 (38) 37 (37) 34 (33) 33*(33) 30 (28) 30 (30)
6.50 37 (37) 37 (37) 32 (32) 31 (27) 30 (27) 28 (27) 26 (26)
7.00 29 (26) 27 (26) 26 (26) 26 (26)
7.50 26 (26) 26*(26) 26 (26) 25 (25)
8.00 26 (26) 26 (26) 24 (22) 22 (20)
8.50 20 (20) 20*(20) 20 (20) 19 (19)
9.00 20 (20) 20 (20) 18 (18)
9.50 18*(18)
10.00
10.50
11.00
11.50 In forming a UNIT LOAD, the over-all
12.00 lateral dimensions shall not exceed
12.50 52 in. in length nor 43 in. in width.
13.00
13.50
14.00
Box
Width Box Length (inches)
(inches) 11.00 11.50 12.00 12.50 13.00 13.50 14.00 14.50 15.00
5.00 34 (29) 33 (29) 31 (29) 30 (29) 30 (30) 26 (22) 26 (22) 24 (20) 24 (20)
5.50 28 (25) 28 (25) 28 (25) 25 (25) 27 (27) 23 (20) 22 (20) 22 (18) 21 (18)
6.00 28 (24) 24 (24) 24 (24) 24 (24) 24 (24) 22 (18) 22 (18) 20 (18) 20 (18)
6.50 25 (21) 24 (21) 24 (21) 21 (21) 20 (18) 20 (18) 20 (18) 18 (16) 18 (16)
7.00 22 (20) 22 (20) 22 (20) 20 (20) 20 (19) 18 (16) 15 (14) 15 (14) 15 (14)
7.50 21 (20) 20 (20) 20 (20) 20 (20) 18 (16) 18 (16) 15 (14) 15 (14) 15 (14)
8.00 20*(20) 20*(20) 20*(20) 20*(20) 17*(17) 16*(16) 16 (16) 17 (17) 15*(15)
8.50 18 (18) 18*(18) 18*(18) 18*(18) 16*(16) 16*(16) 15 (14) 14 (14) 14 (14)
9.00 18 (18) 18*(18) 18*(18) 17*(17) 16*(16) 16*(16) 14*(14) 14*(14) 14*(14)
9.50 18*(18) 18*(18) 17*(17) 17*(17) 15 (15) 15 (15) 14*(14) 14*(14) 13*(13)
10.00 18*(18) 17*(17) 17*(17) 15 (15) 15 (15) 15 (15) 14*(14) 13*(13) 12*(12)
10.50 15 (15) 15 (15) 14*(14) 14*(14) 14*(14) 12*(12) *12*(12)
11.00 12 (12) 12 (12) ll*(1l) ll*(ll) 11*(I1)
11.50 12 (12) 12 (12) ll*(1l) ll*(1l) 11*(I1)
12.00 12 (12) 12 (12) ll*(ll) 1l*(l1) 11*(I1)
12.50 12 (12) 12 (12) 11*(l1) ll*(ll) 9*(9)
13.00 9 (8) 8*(8) 8*(8)
13.50 8*(8)
14.00 8*(8)
GENERATING PALLET LOADING PATTERNS 1003
resulting patterns were then compared in terms of the number of items per layer to the
pallet patterns recommended by the U.S. Navy Supply Research and Development
Facility as reported by Haynes [5]. These patterns will be referred to hence as the
"standard." Loading specifications and requirements relating to load stability were
identical for the comparison. The results of the comparison for 182 different size items
are shown in Table 1. For each item size, the number of items per layer obtained via
the algorithm is given along with the number of items per layer (in parenthesis)
specified using the "standard" pattern. Those sizes for which identical loading
patterns were obtained from each method are further indicated by an asterisk (*). In
some cases, a larger item is shown to have more pieces per layer than an adjacent
smaller item. This apparent discrepancy results when a different pallet load pattern is
recommended by the Navy specification sheet, and a larger amount of the potential
overhang is utilized. Accordingly, the algorithm is run with the same amount of
overhang which was more overhang than was assumed for loading the smaller item.
Consequently, a larger number of items per layer resulted. (The amount of overhang
stated in Table 1 was from the Navy specification sheet, and was used only as
required to maintain consistency. In general, the maximum overhang should not
exceed 50% of the smallest dimension of the item being stacked up to some upper
limit.)
These results show that for identical restrictions, the proposed algorithm always
generates a loading pattern which is at least as good as the "standard." For items
under 8.00 inches width, the algorithm often yields layout patterns with better
utilization of the deckboard. With the larger items, the results are generally equiva-
lent. This is due largely to the limited number of items, and accordingly loading
pattern combinations, which are possible on the relatively small 40 inch x 48 inch
pallet deckboard. For the results given in Table 1, however, the proposed algorithm
exceeds the "standard" by an average improvement of 10.4 percent in deckboard
utilization for the 64 out of 182 cases where the number of items per layer were not
identical.
P A L L E T L O A D I N G S P E C I F I C A T I ON N S
aTOP VIEW ***
. . . . . + + +
* + + + . +. +. .
+ + ...................
.................. + +i
+ + + + +
* +. . . . . . +I
*++ ++ +
* + + + +. +. .
* + + + +
+ + + +
.......
.....+ ...+ .... +... +. +
++++ + 45678 AS + ++
SHOWN ABOVE ..........WITH:
+ I
:++++++++++++++++++++++++ + I
* +I
++ ,+, + ++ + +
*++++++++++++++++++++++++ + I
I ++ + + +
+ 7 + + +OI +
:++
" ~~ ~ ~ 2
++
BOE PE LAYER
++ ++ +
* ~~ ~~ 6 3+ERET+EKBAR+TIIATO
FIUR [Link] aotPten
203 TOTAL BOXES PER PALLE,T LOAD
1827. LBS . TOTAL WYEIGHT PER PALL^ET LOAD
BOX SIZE --- LENGTH 8.50 IN., WIDT 7. 50 IN., HEIGHiT 7.40 IN.
1004 HAROLD J. STEUDEL
Figure 5 is an example of computer generated shop paper which serves to commu-
nicate the loading standards to production personnel. In addition to the layout
pattern, this sheet provides part identification, inventory status, and loading instruc-
tions. The level of control this type of standardization provides is especially valuable
for multiplant companies.
The computer code for the algorithm is quite efficient. Various runs made on a
Xerox Sigma 9 computer using the FLAG compiler showed that approximately 1.25
CPU seconds are required to solve any of the problems tested. The total memory
requirements of the code is 14K words.
5. Concluding Remarks
The heuristic presented provides good solutions to two-dimensional cutting stock
problems in which cuts other than guillotine type cuts are allowed. Potential applica-
tions are numerous since many industrial operations involve decisions regarding the
method or pattern to use in partitioning a large rectangle into smaller rectangles of
equal dimensions. In the case of establishing standardized pallet loading patterns, the
computerized algorithm provides a practical way to generate shop paper for specifying
the method for loading rectangular goods on pallets. The program also provides
management with a viable means to evaluate and select the best size of pallet to
accommodate the range of product sizes which are handled and stored.
The next step in this research would be to extend the heuristic to consider the case
where all the small rectangles are not the same size. A recursion could be easily
defined in terms of 1j, Wi, X,1iand Y,,jfor a known (and relatively small) number (K)
of different small rectangle i = 1, . . . , K. Likewise state variable values could be
defined for pairs of different size rectangles. The challenge in this extension would be
in defining the geometry relationships for determining the relative placement of the
items along an edge so as to minimize the frequency of internal holes in the layout
pattern. This task does not seem impossible, however, and the resulting heuristic
would have considerable application, such as in the area of plate cutting using gas
torches where nonguillotine cuts are both applicable and advantageous.'
lThe author wishes to thank the referees for their many useful comments and suggestions. Appreciation
is also expressed to Dr. T. Heintz for his comments in the earlier stages of this work, and to Dr. T. R.
Martin, former Dean of Business at Marquette University, for his support of this research.
References
1. CHRISTOFIDES,N. AND WHITLOCK, C., "An Algorithm for Two-Dimensional Cutting Problems,"
OperationsRes., Vol. 13 (1977), pp. 30-44.
2. GILMORE,P. C. AND GOMORY, R. E., "Multistage Cutting Stock Problems of Two and More Dimen-
sions," OperationsRes., Vol. 13 (1965), pp. 94-120.
3. GOLDEN, BRUCE L., "Approaches to the Cutting Stock Problem," AIIE Trans. (June 1976), pp.
265-272.
4. HAHN,S., "On the Optimal Cutting of Defective Glass Sheets," I.B.M. New York Scientific Center
Report No. 320-2916, 1967.
5. HAYNES, D. O., Material Handling Equipment,Clinton, Philadelphia, Pa., 1957.
6. HERZ, J. C., "A Recursive Computing Procedure for Two-Dimensional Stock Cutting," I.B.M. J. Res.
Dev., Vol. 16 (1972), pp. 462-469.