Division of Research February 1980
Graduate School of Business Administration
The University of Michigan
A 0-1 MODEL FOR SOLVING
THE CORRUGATOR TRIM PROBLEM
Working Paper No. 205
Robert W. Haessler
and
F. Brian Talbot
The University of Michigan
FOR DISCUSSION PURPOSES ONLY
None of this material is to be quoted or
reproduced without the express permission
of the Division of Research.
1:
1I
i
I

I
I
I~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

ABSTRACT
This paper describes a new 0-1 formulation for solving the corrugator
trim problem. This approach eliminates the spreading of orders over several
stock sizes, a characteristic which has plagued the linear programming-based
procedures that have been proposed for solving the problem. The improved
material handling characteristics of the solution are obtained through the
controlled generation of solution elements. The elements that provide a
minimum cost solution are then selected using a 0-1 backtracking algorithm
that has been modified for this application.

-2 -
Introduction
Over the last 20 years, there have been a number of attempts to develop
computer models for solving the trim problem in the corrugated container
industry. The starting point for these efforts can be traced to the early
papers by Paull and Walter [7] and Eisemann [1] which described linear
programming formulations for the general trim problem in the paper industry.
The improvements in the linear programming algorithms for solving these
problems by Gilmore and Gomory [3,4] provided further impetus. However,
there was an early recognition that the corrugator trim problem could not
be completely modelled using linear programming [6] because of the nature
of the production process. This in turn, led to the development of sequential
heuristic procedures, the most notable of which was due to Van Wormer [8]..
These heuristic procedures were unreliable, however, because of their inability
to consider economic tradeoffs in a systematic manner., As a result, corrugator
trim problems are still for the most part solved manually [5].
The purpose of this paper is to present a new approach to the corrugator
trim problem that overcomes the major difficulties with previous attempts to
solve this problem. The use of conveyorized material handling systems in
plants makes it extremely important that orders are produced contiguously and
not spread out over the entire production run as it typical in linear programming
solutions to cutting stock problems. The elimination of order spreading is
accomplished by the controlled generation of solution elements that completely
satisfy one or more orders. An optimal solution is obtained by selecting that
subset of elements with minimum cost that covers the orders to be produced. This
is an improvement over heuristic procedures because it does permit an explicit
economic tradeoff among corrugator utilization, trim loss, and slitter and stock
size changes.

-3 -
An overview of the operation of a corrugator plant is presented in the
following sections along with a detailed discussion of the economic factors
tlit rnutr.t be taken into c:onsideration when combining orders across the width
of the corrugator. The remaining sections of the paper are devoted to a discussion of a 0-1 model and the solution algorithm that can be used to solve
the problem.
I
Ir

-4 -
Corrugator Plant
A corrugator processes stock rolls of liner and medium to form corrugated
material from which shipping containers are made. These input rolls are generally stocked in a variety of widths to limit the amount of scrap generated. Because
corrugated material is bulky and rigid, it must be cut into rectangular blanks
of the sizes needed to fill customer orders while still on the corrugator. The
solution to the corrugator trim problem is simply a specification of what must
be done to obtain the needed quantities of rectangular blanks of the sizes
ordered. This involves specifying the stock roll sizes to be used, the feet
of corrugated material to be produced from each stock size and the cutting instructions for each stock size to produce the required order sizes and quantities.
A key determinant of the capacity of a corrugator is the maximum width of
the stock rolls it can process. A typical corrugator is able to process rolls up
to 87 inches in width. To obtain a high degree of utilization of the corrugator,
orders for various sizes should be combined across the width so that the total
width of the orders is close to but does not exceed the usable width of the
output of the corrugator. This combining problem is more difficult than
solving a one-dimensional trim problem because the manner in which the blanks
are cut on the corrugator and handled in the plant severely restrict the ways
orders can be combined across the width of the corrugator. The cutting is done
by slitting the corrugated material into strips of the appropriate width and
then chopping the strips into pieces of the ordered lengths. On most corrugators,
the strips can be chopped to at most two different lengths, thereby restricting
the number of ordered sizes that can be combined across the width of the corrugator. Once the rectangular blanks have been cut, they may be shipped directly
to the customer or processed through various operations to obtain finished shipping containers. In modern plants, material is moved to the primary finishing

-5 -
operations on conveyors with limited room for in-process storage. This
makes it important that each order is produced contiguously so that it can
be kept together on the conveyors.
Scheduling Environment
Because of the bulky nature of corrugated shipping containers and the
absolute necessity of having them available when needed, good customer service
is a key success factor in this business. Every effort is made to supply the
material to the customer on time. To insure on time delivery, the production
scheduler typically maintains an order file of items not yet scheduled that is
sorted by grade of corrugated material and due date. The additional information
that must be maintained to schedule the order is:
- blank size (width and length)
- required quantity
- finishing operations required
The production scheduler will typically review the entire order file each
day and generate a corrugator schedule one day at a time. It is possible that
virtually every grade a plant makes will be run every day. This is unlike the
paper industry where a given grade may be run no more frequently than every two
weeks. The service requirements in the box business do not permit large scale
batching of orders for infrequent runs to attain production economies. Fortunately,
the changeover costs from one grade to an6.ther are not very large. Therefore the
production economies foregone by frequent runs of a grade relate primarily to
combining options rather than changeover costs.
The set of factors that the scheduler must consider in determining which
orders to make and how to combine them is given below.
1) Order date - This is sused to determine what must be made, what can be
made if it improves corrugator utilization, and what should not be made yet

-6 -
because the shipping date is too far off. The determination of which noncritical orders get made on any day is based on the economics of corrugator
utilization in conjunction with the supply-demand situation. The corrugator is
normally scheduled to run 24 hours a day, 5 days a week. Except during times
of very high demand, orders are accepted based on the customers required date
without checking schedule feasibility. When demand is low, future orders are
pulled forward to keep the corrugator running as long as possible. When demand
is high, only the orders absolutely needed are scheduled. Weekend overtime is
used to try to keep up during peak periods. During periods of slack demand,
the corrugator may be shut down during the week for one or more shifts.
2) Finishing equipment backlogs - It is desirable to keep the backlog
on the primary pieces of finishing equipment balanced. As a result, this
consideration may influence the orders to be scheduled and the way in which
orders are combined.
3) Corrugator width utilization - Productivity of the corrugator is
partially controlled by the width of usable material produced. By utilizing
more of the width capacity, the time required to produce a given set of orders
can be reduced. It should be noted that the value of corrugator time will vary
depending on the supply-demand situation. During periods of slack demand, the
incremental value of an hour of corrugator may be low, reflecting only the
out-of-pocket operating costs. Whereas whendemand is high, the value of corrugator time should reflect the opportunity cost of incremental business and
margin.
4) Side trim - To limit scrap losses, rolls of liner and medium are
generally stocked in more than one width. For example, if three 25 inch width
blanks are to be run on an 87 inch corrugator, they might be cut from 77 inch
stock rolls with 2 inch side trim instead of the 12 inches that would result

-7 -if only 87 inch width rolls were available. However, it is impossible to completely
eliminate trim losses. In general a loss of about.375 inches per side is required
in order to insure that blanks meet dimensional tolerance criteria. So even if
the paper were available in 75 inch rolls, this size could not be used for the
three 25 inch blanks.
5) Cutting pattern changes - Because the blanks are cut on the corrugator
itself, there is a loss of both time and materials when the blank sizes are
changed. Therefore, the scheduler attempts to minimize the cutting pattern
changes. Changing cutting patterns involves rotating a mechanism which holds
three sets of slitters and adjusting the length cutoff. The setting of the
slitters for two cutting patterns can be done while the corrugator is running.
However, care must be taken so that pattern changes do not occur so frequently
that there is insufficient time to set the slitters before the corrugator stops
for the next pattern change.
6) Upgrading - In certain situations, because of excessive side trim or
low corrugator utilization, it may be more economical to provide the customer
with a higher quality box than was ordered. The customer pays the regular price
for the box ordered. The incremental value of the material "given away" is
recovered by combining the order in question with orders for different sizes of
the higher quality grades and thereby reducing side trim or increasing corrugator
utilization.
7) Partial orders - Processing and handling costs after the corrugater may
be increased substantially if each order is not produced contiguously during a
run. Failure to accumulate all the blanks needed for an order before starting
the finishing operations may result in multiple setups on these machines. To
avoid multiple setups for orders which are produced in partial lots, the material
must be staged after the corrugator. This can be difficult and expensive in a
plant that uses conveyors for movement and storage.

-8 -
8) Stock width changes - There.is a cost when a stock width change is made
in addition to the cost of the accompanying knife change. For corrugators that
have automatic splicers and process control this may be nothing more than the
cost of moving stock rolls in and out of inventory. Without automatic splicers
there is also some lost time and material associated with a stock width change.
9) Stock availablity - At times there may be limited amounts of any roll
stock size in inventory. The availability of roll stock must be considered
in solving the corrugator trim problem.
It should be clear from the proceeding list that there are a number of
tradeoffs that must be considered in combining orders for production on a
corrugator. A simple example can be used to demonstrate the nature of the
tradeoffs and the type of information required to make them. Suppose an
order for 48,000 lineal feet of 161 inch blanks is to be produced. The stock
sizes available range from 67-87 inches in 2-inch increments. Assume that
there are no other orders available that can be combined with this one. The
order can be run either 4-out from 67 inch stock rolls or 5-out from 85 inch
stock rolls. The question is which is the most economical way to run the order?
The key issue in this case is the tradeoff between the value of paper and time
on the corrugator. Running the order 5-out requires 9,600 feet of corrugator
production and results in 2.5 inches of side trim, whereas running 4-out
requires 12,000 feet of corrugator production and results in 1 inch of side
trim. The total scrap generated by running 5-out is 2,000 square feet and 4 -out is 1,000 square feet. The determination of which way to run the order rests
on a comparison of the value of 1,000 square feet of scrap and the value of the
corrugator time required to produce 2,400 lineal feet.
Although the above tradeoff is straightforward and easy to make if the
required data is available, it should be clear that in a multi-order- problem the

-9 -
tradeoffs can become much more difficult to identify and evaluate. In a
multi-order problem there may be a large number of possible ways to combine
sizes on the corrugator. These alternative solutions may involve differences
in pattern and stock width changes as well as differences in scrap generated
and corrugator time required. What is needed to identify and evaluate the
tradeoffs in a systematic way is a mathematical statement of the problem that
is computationally feasible. It is possible to formulate the problem as an
extension of the one-dimensional cutting stock problem (see 5). But, the resulting model can only be solved heuristically because of the combinatorial
nature of the problem. The difficulty with heuristic procedures for generating
solutions is that they have either attempted to generate patterns sequentially
and as a result have had trouble with trim loss at the end of the procedure, or
have used linear programming to minimize scrap losses and have performed poorly
with regard to pattern changes and order contiguity.
The next section presents an alternative formulation of the problem which
is based on observed scheduling practices in modern corrugator plants where the
primary objective is to avoid making only part of an order from a given stock
size. This approach overcomes the drawbacks mentioned above.
0-1 Formulation
Instead of formulating the problem in terms of cutting pattern variables,
a much more manageable formulation can be developed by focusing on solution
elements. A solution element is a specification of the way in which one or
more orders can be completed from a single stock size. The four types of
solution elements currently being considered are listed below.
1. Producing one order by itself. For example cutting
three 25 inch width blanks from a 77 inch stock size.

-10 -
2. Producing two orders from a single cutting pattern.
For example, cutting two 20 inch blanks and two 18 inch blanks
from a 77 inch stock size. This can be done if and only if
the quantity requirements are such that both orders are simultaneously completed within the allowable quantity tolerances.
Typical industry practice is to produce an amount that is in
an interval from the order quantity to the order quantity plus
10%
3. Producing two orders from two cutting patterns from
a single stock size. For example, cutting one 25 inch blank
and one 51 inch blank from a 77 inch stock roll until the order for
51 inch blanks is filled and then finishing the order for 25
inch blanks by cutting them three across.
4. Producing three orders from two cutting patterns from
a single stock size. For example, cutting two 25 inch blanks and one
26 inch blank from a 77 inch stock size until the 26 inch order
is completed, and then cutting two 25 inch blanks and two 12
inch blanks until these two orders are completed. This again
requires a specific relationship among the quantities required.
In both the third and fourth elements an order is spread over 2 pattern
setups from the same stock size. This, however, is not considered partialling
the order because the patterns are run sequentially.
The corrugator trim problem can be formulated as a 0-1 model by using
elements of the type listed above as follows:

-11 -
Min Z.cjxj + Eks.a ix = 1 for i = 1,..., m
J ii J
jujkxj < AYk for k = 1,..., k
x. = 0 or 1 yk 0 or 1
3
Where
x. is 1 if element j is used and 0 otherwise
J
(j = l1*,.,n)
y is 1 if stock size k is used and 0 otherwise
a.. is 1 if order i is completed in element j and
ij
0 otherwise
u. is the feet of stock size k required by element j
kk
c. is the total cost of using element j exclusive of
J
the cost of changing to the required roll stock
size. It includes the cost of corrugator time
and paper used plus the cost of pattern changes;
This value is adjusted if any order is not produced
at the maximum quantity to reflect the cost of
producing the whole order.
sk is the cost of loading stock size k on the machine.
It is assumed that if two or more elements use the
same stock size, they will be run sequentially so
there will only be one setup for each stock size.

-12 -
The upgrading of orders and the use of optional sizes can be easily
handled in this formulation. An order can be included in several elements
involving different stock sizes and grades of paper. The only requirement
is that an order not be included in an element using lower quality paper
than specified on the order. Optional items can be handled by reducing the
cost of the elements in which that item is produced by itself. If that element is in the solution, it is not scheduled. If the optional order is
produced in some other element in the solution it is because there is sufficient cost saving on some other order to overcome the reduced cost
available from producing the order by itself.
Solution Procedure
The solution procedure for the 0-1 model is an adaption of the setpartitioning algorithm introduced by Garfinkel and Nemhauser [2]. Although
there exist a number of approaches for solving 0-1 integer problems, several
factors motivated the use of this particular procedure. Typically, corrugator
plants have available only small, relatively slow computer systems which can
be used for scheduling purposes. These limitations mitigate against the
adoption of optimizing codes which require either large amounts of computer
core, or if they are to be cost effective, much computer time. Garfinkel and
Nemhauser's approach is a list processing, implicit enumeration technique
that has very low core requirements and has been shown [2] to be a relatively
fast method for optimally solving the set-partitioning problem, which is a
subproblem of (1)-(3). In addition, this approach, is attractive because
of the ease with which inventory constraints and changeover costs can be
included without significantly increasing core requirements. Finally, this
0-1 backtracking method yields good feasible solutions very quickly. This
characteristic permits the scheduler to terminate program execution prior to

-13 -
reaching optimality with good heuristic solutions in-hand, if program running
time does become excessive.
The basic approach is to solve the set-partitioning subproblem (1) and
(2) using Garfinkel and Nemhauser's six-step algorithm but with additional
tests included to insure that stock availability (3) is not exceeded and that
changeover costs in (1) are considered when appropriate. The adaptation
details which follow use the notation in [4] for consistency.
During the initialization phase the rows in the aij matrix are dynamically
sorted such that i < e implies Z.aij <E.a. Dynamically sorted in this case
means that the sorting criterion is recalculated m-1 times, where the above
sums are taken each time over only those j where a.. = 0 in all rows i that
ij
have been renumbered. This procedure appears to be superior to the single
pass sort suggested in [2], although in either case the objective is the same:
number the most restrictive constraints so that they will be evaluated first
by the implicit enumeration algorithm.
Also during the initialization phase the variables x. are assigned to
m lists as in [2] such that x. is in list i if and only if a = 1 and
= for all e < i. Rather than sorting the variables within each list
aej = 0 for all e < i. Rather than sorting the variables within each list
in order of nondecreasing cost c. as is suggested in [2], however, they are
sorted in nondecreasing order of a surrogate cost priority index. This sort
is much more effective for the corrugator problem because of the nature of
the solution elements. The priority index is set at -1 for all type 1 elements
(elements involving only an order). For all other element types involving more
than one order the priority index is calculated as the potential saving by
using this element instead of the set of type 1 elements that satisfy the
same orders.

-14 -
Both stock changeover costs and stock availability constraints are
evaluated during step III (building the partial solution). Ak and yk are
used, respectively, to indicate the lineal feet of each stock width currently
available and whether a given stock width is in the current partial solution.
Variable x. is only brought into solution if u < Ak, and the sum of the
jk - and the sum of the
current partial solution costs plus all the costs of bringing j into solution
do not exceed the cost of the best (incumbent) heuristic solution generated.
Of course, during the backtracking step, Ak is increased by ujk when x. comes
out of solution. Similarly, all cost elements are updated.
out of solution. Similarly, all cost elements are updated.

-15 -
Example Problem
An example problem with 15 orders is presented in Table 1. The width and
length refer to the size of the blank required to fill the customer's order.
The quantity is the number requested by the customer. An order is within tolerance
if the number scheduled does not exceed the order quantity by more than 10%. Given
a choice, the quantity scheduled will be the upper limit.
An optimal solution to the example problem is given in Table 2. The solution
is presented in terms of the patterns and stock sizes to be used and the lineal
feet of corrugated material to be produced for each pattern. This solution was
obtained and verified as being optimal in.696 seconds of CPU time on an AMDAHL V/7
computer using the standard FORTRAN G compiler. The problem solved had 62 solution
elements.
Because the practical usefulness of this technique is closely related to the
computer costs of running the program, it is worth discussing several computational
issues. In order to further reduce CPU core and time requirements, the a.i matrix
is replaced with a matrix of column and row indices indicating the location of
unit coefficients. The a.. matrix is sparse (density is typically under 15%) with
no more than three unit coefficients in each column. This permits the mxn a..
matrix to be replaced by a 3xn matrix. Core requirements are reduced somewhat by
this procedure, but more important is the 300% improvement in CPU time this approach
affords because it reduces tha amount of list processing required. Even though the
resulting algorithm is fast enough to be run to optimality for most problems, there.are occasions when the cost of obtaining the optimal solution simply outweighs the
benefit of having it. To accomodate this situation, the algorithm can easily be
programmed with stopping rules based on running time, or number of iterations. One
method which seems to have merit is to terminate program execution when an improved
solution is not found within three times the cumulative CPU time needed to obtain
the previous solution. We have found that this rule almost always permits the

ft
Table 1
EXAMPLE PROBLEM
WIDTH LENGTH QUAN
ORDER INCHES INCHES ORDE
A 24.6250 62.250 40
B 22.5000 66.625 50
C 19.4375 54.500 20
D 19.1875 57.250 35
E 19.9375 63.250 50
F 18.0625 47.500 50
G 19.9375 47.500 50(
H 20.5625 54.500 36'
I 21.6250 48.250 24<
J 16.8125 83.750 304
K 21.6875 55.750 30(
L 21.5625 63.000 20(
M 16.5625 49.250 501
N 42.0000 37.875 72
0 43.3125 59.625 50(
Stock Sizes Available Range From 67 to 87 Inches:
Economic parameters for this problem
- corrugator value $100/hour
- corrugator speed 300 feet per minute
- slitter charge $10
- stock charge $5
- paper cost $15/thousand square feet
- paper weight 125 pounds/thousand square feet
- minimum edge trim.375 inches/side
TITY
ERED
00
00
00
00
00
00
00
00
00
00
00
00
00
50
00
In 2
Inch Increments

-16 -algorithm to find the optimal solution, but without consuming an inordinate
amount of time verifying optimality. Had this rule been applied in the example
problem, total CPU time would have been.219 seconds (it took.073 seconds to
find the best solution) instead of.696 seconds. Further justification for
using this rule is based on the observation that for all the problems solved
thus far, proving optimality consumes from three to ten times as much CPU time
as does simply finding the optimal solution.

Table 2
EXAMPLE PROBLEM SOLUTION
STOCK SIZE
87
'87
85
85
85
83
83
PATTERN*
4L
2A and 2F
2N
5J
5M
21 and 2C
2D and 2K
2D and 1P
4H
2E and 2G
3B
PRODUCTION IN
FEET
2,890
10,890
1,300
4,610
4,520
5,000
7,670
1,370
4,540
10,890
10,180
83
81
69
* A pattern designated as 4L means that 4 blanks for order L,
21.5625 inches wide, are combined across the width of the
corrugator.
Optimal Value of the Objective Function Is $7068.

-17 -Summary
The corrugator trim problem involves some very difficult tradeoffs between
linear and fixed costs. As such it appears doubtful that the problem can be
formulated and solved in the format of a cutting stock problem. The 0-1 approach
presented in this paper leads to a compact formulation which can be solved
optimally in a reasonable amount of time. The solution elements used are comparable
in complexity to those used by schedulers. One major advantage of this approach over
manual solution procedures is the ability to generate multiple elements that
contain the same order and to then select the one that gives the best overall
result with all economic factors and order requirements considered.
In addition to the obvious use in day-to-day scheduling of corrugator, the
approach defined above can be used to carry out studies that would otherwise be
impossible. One of the most important of these would be an analysis of the impact
that the number and choice of stock sizes has on total corrugator operating costs.
It is well known that raw material inventory is directly related-to the number of
sizes stocked. By using this model to solve the same problems with various
numbers and combinations of stock sizes, it will be possible to determine the
expected increase in corrugator operating costs associated with a reduction in
the number of sizes stocked. This can then be compared to the expected reduction
in carrying costs to come to a determination of a rational stocking size program
for any box plant.

References
1. E. Eisemann, "The Trim Problem," Management Science 3, 279-284 (1957).
2. R. S. Garfinkel and G. L. Nemhauser, "The Set-Partitioning Problem: Set
Covering with Equality Constraints," Operations Research 17, 848-856.
3. P. C. Gilmore and R. E. Gomory, "A Linear Programming Approach to the
Cutting-Stock Problem," Operations Research 9, 848-859 (1961).
4. P. C. Gilmore and R. E. Gomory, "A Linear Programming Approach to the
Cutting-Stock Problem," Operations Research 11, 863-888 (1963).
5. R. W. Haessler, "The Corrugator Trim Problem," Paper presented at the
1977 Joint National ORSA/TIMS Meeting in Atlanta.
6. J. L. Marley and D. Mahoney, "Can Cutting Trim Waste Cut Into Your
Profits?" Paperboard Packaging, (Oct. 1963).
7. A. E. Paull and J. R. Walter, "The Trim Problem - An Application of
Linear Programming to the Manufacture of Newsprint," Paper presented
at the Annual Econometric Society Meeting, Montreal (Sept. 1954).
8. T. Van Wormer, "The Trimmer: A Heuristic Solution to the Trim Problem in
the Corrugated Container Industry," Unpublished doctoral dissertation,
Carnegie Institute of Technology.(1963).