Division of Research School of Business Administration CNE-DIMENSIONAL CIITING STOCK DECISIONS FOR ROLLS WITH MULTIPIE QUALITY GRADES Working Paper #571 Paul E. Sweeney Robert W. Haessler The University of Michigan FOR DISCUSSION PURPOSES ONLY None of this material is to be quoted or reproduced without the expressed permission of the Division of Research Copyright 1988 University of Michigan School of Business Administration Ann Arbor Michigan 48109 June 1988

ONE-DIMENSIONAL CUTTING STOCK DECISIONS FOR ROLLS WITH MULTIPLE QUALITY GRADES by Paul E. Sweeney and Robert W. Haessler ABSTRACT This paper presents a model for solving one-dimensional cutting stock problems when both the master rolls and customer orders have multiple quality gradations. Solution procedures for problems with these characteristics have not been previously published. The model described here is two-stage and heuristic. A sequential, shadow price based procedure is first used to select slitting patterns for master rolls with variable quality characteristics. Then a residual problem for any remaining first-quality ("perfect") rolls is solved with a linear programming model. An important characteristic of the approach is its robustness. The model can deal effectively with problems of varying size and complexity and can also easily adapt to to changing circumstances with respect to production quality and demand. 2

3 One-dimensional cutting stock (trim loss) problems arise when production items must be physically divided into pieces with a diversity of sizes in one dimension (e.g., when slitting master rolls of paper into narrower width rolls). Such problems occur when there are economies of scale associated with the production of the large master rolls, but also economic advantages from: 1) minimizing trim loss, 2) avoiding production over-runs, and/or 3) avoiding unnecessary slitter setups. This paper presents a model for solving such problems when both the master rolls and customer orders have multiple quality gradations. Solution procedures for problems with these characteristics have not been previously published. The model described here is two-stage and heuristic. A sequential, shadow price based procedure is first used to select slitting patterns for master rolls with variable quality characteristics. Then a residual problem for any remaining first-quality ("perfect") rolls is solved with a linear programming model. An important characteristic of the approach is its robustness. The model can deal effectively with problems of varying size and complexity and can also easily adapt to to changing circumstances with respect to production quality and demand. The Basic One-Dimensional Cutting Stock Problem The problem of interest here is a variation on the

4 basic one-dimensional cutting stock problem, which was described by Pierce (1964) as follows: Suppose that a mill has received customers' orders for rl, r2,... rn rolls of a certain grade1 of paper, these rolls to be of widths w!, w2,... Wn and (the same) diameter D. The mill has one paper machine which can manufacture the desired grade, this machine producing rolls of width W (where W > wi for all i). Since customer widths demanded are smaller than, or equal to, the production width of the paper paper machine, the production scheduler tries to find combinations of the customers' widths [patterns] with which to fill out the width W of the paper machine rolls. Usually there will be a "side roll" of trim loss left over from such combinations which is reprocessed or disposed of in some other manner. The paper trim problem, then, is to find the trimming combinations of customer widths and to determine the number of machine rolls to be produced and cut according to each combination- so as to satisfy customers' demand most efficiently. For this basic problem, efficient production has usually been defined as the solution to the following integer programming problem: 1 In the paper industry, "grade" is used to denote substantially different products. In this chapter, "style" will have that meaning and "grade" will refer to quality variations within a style.

5 n (IP1) Minimize: E Tj xj j=l n S.T. (1) E aij xj > ri i = 1,2,... m j=l aij, ri, xj > 0 xj, aij, and ri integer where: xj is the variable for the usage of pattern j aij is the number of rolls of width i in pattern j ri is the demand for width i (in rolls) Tj is the trim loss for pattern j The selected patterns must be feasible with respect to the sum of the widths they contain: m a aij wi < W j = 1,2,... n i=l where: wi is the width for demand i W is the master roll width m (Tj = W - aij w j = 1,2,... n) i=l In IP1, the constraints ensure that all demand is satisfied, while the objective function minimizes the total amount of trim loss. Because of the large number of variables in these mixed integer programming problems, efficient exact solution methods are not available and the answers are usually found by rounding solutions from the

6 relaxed linear programming formulation of the problem. Although solutions to this problem usually provide good results with respect to trim loss, they may not adequately address the concern for the avoidance of excess finished product inventories. Because only the demand amounts ri are shipped to customers, any production in excess of those amounts is retained in inventory. This can be directly addressed by including explicit constraints on production in the model: n (2) E aij xj < Ui i = 1, 2,... m j=l where: ui is an integer production limit on width i (in rolls, ui > ri) Depending on how the n alternative slitting patterns are defined, there may be a risk that such constraints will result in infeasibility. That can occur if only dominant patterns are permitted (a dominant pattern cannot have trim loss which equals or exceeds the narrowest demand width). Thus the basic one-dimensional problem addresses the criteria of yield and inventory. The third concern with the the number of slitter setups is not important here because of the quality issues discussed in the next section. A Modification for Rolls with Multiple Quality Grades In this case, when a master roll for a given style of material is being produced, random variations in quality can

7 occur across the width of the roll. The results are lengthwise lanes of different quality gradations (see Figure 1). A lane's grade is defined by the worst quality occurring within it over the length of the roll. The number, position, and quality level of the lanes are random and can only be determined after the rolls are produced. Likewise, when orders are accepted, they specify a minimum acceptable quality level. The highest quality material (grade 1) can be used to satisfy orders for any quality level, grade 2 material can be used for all orders except grade 1, and so forth. Because of the variable quality of both the master rolls and the orders, a slitting consideration arises which is not present in the basic problem. Thus, in addition to the priorities on yield and the avoidance of unnecessary inventory and setups, there is also a value in assigning material to the highest quality orders possible. In general, the importance of doing so depends on the revenue differentials between the various quality grades. However, even in those cases where the differences are relatively small, such assignments are still important if the production batch contains so much lower quality material that it may constrain the ability to satisfy higher quality orders. In addition, even if the current production batch were relatively rich in good quality material it would still be better to have any uncut rolls held over for future orders be of the higher quality material (because of its greater

8 Figure 1. Example of Variable Quality on a Master Roll

9 flexibility for future use). Therefore, except in unusual circumstances, it is important to place some priority on matching the quality of material to the quality of the orders for which it is used. The level of importance depends on both economic factors and on the balance between supply and demand for the various quality grades. The mathematical formulation for the basic onedimensional problem assumes master rolls which are uniform in both width and quality. It also assumes that the same, single quality level applies for all orders. For this revised problem, each non-perfect master roll can be unique and a slitting pattern's feasibility depends not only on its total width, but also on its appropriate use of material only for equal or lower quality demand widths. That represents a significant increase in the complexity of this combinatorial problem. Because the formulation for this modified problem does not lend itself to any exact solution procedures, it is deferred to Appendix 1. Solution Priorities In the previous sections, the four decision criteria for the modified cutting stock problem were described as: 1) minimization of trim loss, 2) minimization of excess finished product inventory (FPI), 3) avoidance of excess slitter setups, and 4) maximum usage of material for high quality

10 orders. If an optimal solution could be found, it would result from the economic tradeoffs among these four criteria. For the problems we have studied, the highest priorities are for the minimization of trim loss and the avoidance of excess FPI and the direct economic incentive to avoid using high quality material for low quality orders is small. That is because the marginal revenues and production costs are nearly uniform across the various quality grades. Because the master rolls in this problem tend to be unique, it is very difficult to avoid individual setups for their slitting patterns. In such an environment, avoiding slitter setups is of relatively little concern. Other Problem Characteristics The proportion of the rolls in any given production batch which are perfect is highly stochastic. It is dependent on both the style and the conditions during production. The total number of rolls to be slit for any one batch of orders will range from about 25 to 400, with most of that variation based on style-to-style sales volume differences. The specific sets of widths ordered also varies significantly from style to style and batch to batch. Literature Review Although it has been more than twenty years since Gilmore and Gomory (1965) presented a recursive approach for

11 considering the value of one-dimensional patterns when the quality of the master rolls vary, there have been relatively few subsequent articles which consider quality in the context of a cutting stock problem. The great majority of those that do are concerned with two- or three-dimensional problems. The only author which deals with quality in a onedimensional problem is Sculli (1981). However, his situation is not at all similar to the one presented here. He presents a probabilistic analysis for knife positioning when the width of the master roll is a random variable and all rolls slit are of equal width. The only issue is the tradeoff between setup time and the amount of edge waste resulting from the variation in usable width. Cheng and Pila (1977) present a model for cutting boards from wood stock in order to exclude random defects. Hahn (1968) presents a model for sequentially dividing sheets by three stages of guillotine cuts into sections, strips, and pieces, also in a way that excludes random defects. Foster and Lesyna (1978) deal with slitting a large production master roll into rolls of varying widths and lengths. Random defects affect the quality of the sheet and thereby its market value (isolating defects on as few rolls as possible is desirable). The decisions on roll length (chopping) and width (slitting) are decoupled. Slitting decisions are made using standard Gilmore and Gomory

12 techniques (1961a, 1963b, and 1965c), except that each permutation of a given pattern must be analyzed for its economic value. Chopping decisions are similarly evaluated. However, their procedure does not address quality feasibility or the need to satisfy demands for specific grades of product. Overview of the Solution Procedure It would be preferable, of course, to solve these problems globally by simultaneously considering all master rolls in a large mathematical programming model. Because that approach is not viable computationally (see Appendix 1), a sequential heuristic procedure is used instead. During the first stage of the procedure, slitting decisions are made for the non-perfect master rolls. Figure 2 provides a flow chart for the procedure. References below to steps shown on flow chart will be indicated with a <<STEP>> designation. During this stage, there are three points at which the operator provides control parameters to the model (PARAM 1, PARAM 2, and PARAM 3). These parameters, which affect the model's priorities on yield, inventory, and the degree to which material is downgraded for inferior quality orders, can allow for changes in production quality or in business conditions. Some of the parameters affect the solutions in well understood, easily predictable ways (e.g., the inventory multiplier in PARAM 2). For others, the effects are more subtle and less predictable (e.g., the

13 rules for establishing the sequence in which the non-perfect rolls will be processed). For the latter category, there are still opportunities for further research to be done. The second stage of the procedure (<<DO PERF>>) is an LP model which solves the residual problem for net demand and the remaining perfect master rolls. Assuming that there are non-perfect rolls to be processed (<<ANY NP?>>), the first stage in the procedure sequentially processes the non-perfect master rolls in order of their increasing flexibility of use. Any other sequence would increase the likelihood of incurring trim or inventory penalties when the less flexible rolls are matched later with the reduced sets of demand widths. Any other sequences could also result in master rolls being held longer before they are used. In the course of establishing the sequence in which the rolls will be processed, the model also assigns a value to each roll (<<SET RV>>). If a cutting pattern for the roll is found which meets or exceeds that value (<<PV > RV?>>), the pattern is accepted. If no such pattern can be found, the master roll is held back for use with some subsequent demand batch. Roll values are based on parameters supplied to the model (PARAM 1). Pattern values are derived from the shadow prices from an LP for net demand (<<CALC SP's FOR DEMAND WIDTHS>>). The details of these techniques are provided in subsequent sections. An important aspect of the sequential procedure is that

14 KtL pAPAW I iP - NON-rPRFECT RULCS FOR NP I COUrNCC WAITER ROLL RULtI FOR NP IV RV - ROLL VALUE PARAM 2 INVENTORY MULTIPLIER PV -rArrTERN VALUE PARAM 3 PERF - PERFECT MAX PATTERN Tr0 EVALUATE MASTER ROLLS PER NP ROLL D p SHADOW PRIC ES ____________ L N I~ AN I.I 4. -------- 1DEMAND (2) ', / OuEt IV 4'.t HIGT4HEST DECREWENT lPE N ^^ l^\ I- I1DEHI DEMAND SLIT tYES O HOLD UASTERI * Y N- ASTER ROLL Jt ROLLt Figure 2. Flow Chart of the Solution Procedure

15 it makes decisions in such a way that there is a predetermined probability that each roll will be used with a demand batch (i.e., so that roll usage follows a geometric probability distribution). By setting the probability target as low as possible (i.e., by setting the roll value hurdles higher), each roll is more likely to be eventually used in a more desirable way with a more appropriate set of demands. If a roll's value is lowered, the probability of the roll's usage increases at the expense of decreased yield and/or increased FPI. If too many variable quality rolls are held back until "good" usages are found for them, there could be three kinds of problems: 1) The storage facility for uncut master rolls might fill to capacity and become a production bottleneck. 2) There would be more risk of quality problems remaining undiscovered for a longer period of time. 3) If there were product or process changes, future shipments might include an undesirable diversity of product characteristics. If too small a proportion is held back, yield and FPI penalties are incurred. The input parameters which are used to place values on rolls can be automatically or manually adjusted if the rate of roll usage drifts away from the target. That might occur if the model were not initially parameterized correctly, if production quality changes, or if the nature of demand shifts.

16 Stage 1: A Sequential Procedure for Non-perfect Rolls As stated previously, the order in which rolls are processed is ideally from least to most flexible. However, because of the tremendous diversity possible for both roll descriptions and demand sets, not to mention the difficulty of accurately predicting flexibility (see Gilmore and Gomory 1963), it is only possible to approximate such a sequence. One way to do so is by grouping rolls into approximately homogeneous categories according to surrogate measures of flexibility. Rolls will generally increase in flexibility as the widths of their usable sections increase and as their quality improves. The following are, therefore, reasonable examples of the kinds of measures which can be used to establish processing sequences: 1) number of usable sub-sections (separated by waste) 2) widths of usable sub-sections 3) number of quality grades 4) amount of usable material (by quality grade) The model attempts to select patterns for a non-perfect master roll which are composed of widths that are relatively difficult to combine with other demand widths. Such a pattern is denoted as being more "valuable". By doing so, those difficult items are removed from the demand list and the quality of solutions to the residual problem is pre

17 served. The procedure for generating and testing alternative patterns to consider for use with a master roll is lexicographic (<<FIND HIGHEST VALUE FEASIBLE PATTERN>>). In order for a candidate pattern to be selected for use with a master roll, its "value" must exceed a cutoff value assigned to the roll (<<PV > RV?>>). The pattern's value is assumed to be the sum of the shadow prices for its component widths (found by solving the LP relaxation of IP1). Those prices carry "information" regarding both the relative sizes of the demand widths and the ease or difficulty of combining those widths into viable patterns.2 A pattern's value will 2 If the next marginal unit of demand for a width can be satisfied from a pattern where that material would otherwise go to waste, the cut is free and the width would carry an opportunity cost of 0. On the other hand, widths that are difficult to fit can cause such waste and would have inflated opportunity costs. If patterns could only contain cuts of a single width, the shadow prices would reflect the maximum number of times a width could fit across a master roll. For the case where master rolls are 120" wide: Demand Widths Max Cuts Shadow Price Greater than 60" 1 1/1 40" 2 1/2 30" 3 1/3 24" 4 1/4 Because combinations of widths are allowed, however, the shadow prices reflect combinatorics as well as material usage. For example: Width Demand Shadow Price Problem 1: ---- 61" 1 1.0 25" 1 0.0 Problem 2: ----- 61 1 0.5 25" 2 0.25

18 be relatively high if such difficult widths are included and relatively low if they are not. The usage of high value patterns during the sequential procedure will tend to enhance the quality of the solutions to the residual problem by satisfying demand for hard to fit widths and preserving demand for those widths which combine more easily into high yield patterns. The only modification to that problem is that the RHS's for the demand constraints are net demand (total demand less any cuts from previous master rolls). Standard GilmoreGomory solution techniques (including column generation methods) are used to solve the LP. If optional inventory widths are allowed, once the above LP has been solved, it is expanded by the addition of new "demand" constraints for each inventory width. The RHS for each new row is the maximum allowable inventory for that width. An artificial shadow price is assigned to each of these new rows and the Gilmore-Gomory procedure resumes. The shadow price for the inventory widths are some fraction of the ratio of the inventory width to the master roll width (F x w/W). Low values for F (PARAM 2) discourage the inclusion of inventory widths in the LP's optimal patterns; high values for F have the opposite effect.3 3 For example, the following problem includes 1 demand width and 2 inventory widths (master rolls are 120" wide): Width: 35" 25" 10" Demand: 3 0 0

19 Once the revised LP is solved, it provides the shadow prices for each width which are then added to find the values of the lexicographically generated candidate patterns. The LP solution itself is not used. The lexicographic procedure is necessary because of the need to explicitly test for the quality feasibility of permutations of each pattern. If a candidate pattern's value is greater than an incumbent's value (or equal in value but with greater yield), it is tested for feasibility against the quality characteristics of the master roll (<<FIND HIGHEST VALUED FEASIBLE PATTERN>>). To avoid processing patterns which offer a very small marginal improvement, patterns are not considered unless their value is at least.001 greater than the incumbent's value or, for value "ties", unless there is at least a 0.25" yield improvement. Before a candidate pattern's feasibility can be confirmed, it may be necessary to implicitly test each permutation of the pattern's widths. It is computationally reasonable to do so only if patterns contain relatively few cuts (generally 1-5). Pattern feasibility is tested by If F=0.10, only "free" inventory cuts are included in the optimal solution: 1 master roll 35"-35"-35"-10" (115" used) If F=1.0, inventory cuts are used to improve yield: 2 master rolls 35"-35"-25"-25" (240" used) At some intermediate value of F, an indifference point between these two solutions exists (at about F=.91752).

20 packing the widths up against the left edge of the roll and sliding them to the right (similar to beads on a string) until the leftmost cut is found to be either feasible or impossible. Once a feasible location for a cut is found, the next width to the right is similarly tested. Eventually, the pattern permutation's feasibility is either proved or disproved. In some cases, it may be possible to skip the pattern evaluation procedure for a master roll. That could be done if all of the following conditions are satisfied: 1) The consecutively processed master rolls are identical. 2) Shadow prices were not affected by the processing of the previous roll. 3) The rolls cut from the preceding master roll did not result in a production level which exceeded (or is too near) an inventory limit. In such cases, the solution for the previous roll could be reused. Such occurrences would be rare, but would most likely occur when the model is processing full width, lower quality rolls. A feasible pattern is accepted for use only if its calculated value meets or exceeds the cutoff value for the master roll <<PV > RV?>>. Otherwise, the roll is held back for use with some subsequent demand batch. The roll value is determined by the following formula: Vi = (Ui - Ci)/ where: Vi = the value for roll i Ui = the usable width (waste excluded) for roll i

21 Ci = the parameter for the roll class for roll i W = the maximum possible usable width (for our example, 120") The parameters for each of the roll classifications (PARAM 1 in Figure 5) are determined experimentally. They can be thought of as approximately equal to the trim loss permitted on a roll. The goal is to set them in such a way that the probability of roll usage (i.e., pattern acceptance) is approximately equal to a predetermined target (P). The value selected for P (in conjunction with policies on perfect roll safety stocks) will determine the mean and variance for the level of master roll inventory. P should be set high enough so that it is unlikely that the need for storage of uncut rolls will exceed capacity. It should also be high enough so that rolls can be expected to be used within a reasonable amount of time. The latter would be especially important if the product were subject to deterioration or obsolescence. If neither of the above concerns are limiting, however, P should be set so that the expected level for the inventory is economically optimal. It would correctly trade off master roll carrying costs against the marginal improvement in performance to be gained from having a greater variety of uncut rolls to choose from (improvements would be in the form of higher yield and/or lower FPI). Because it is intended that rolls will be processed in sequence from least to most flexible, and because a larger

22 roll parameter is an indication that greater trim or inventory sacrifices may be necessary in order to accept patterns with the desired regularity, the parameters should be non-increasing for the sequence in which master rolls are processed. If the model were originally parameterized incorrectly, if production quality improves or declines, or if there is a shift in the nature of demand, then it may be necessary to alter the parameters so that the desired probability of master roll use is maintained. It would, of course, be very easy to automate that adjustment procedure. But if the parameters were thereby changed to such a degree that they were no longer non-increasing, the roll sequence should also be adjusted. If individual rolls within a classification are held for longer periods than would be reasonable given their targeted probability of use, it is an indication that the roll classification scheme does not provide sufficiently homogeneous roll classes. Two steps are possible: 1) Once the rolls have been held for some extended period of time, assign them to a less flexible classification. They would then have a chance to be processed earlier, when there are more combinations of demand widths available and when there might also be a looser (bigger) roll valuing parameter. 2) The definitions of roll classifications could be adjusted. The first approach could easily be automated. The second might require some minor reprogramming effort.

23 Stage 2: The Residual Problem (Perfect Rolls) This stage in the solution procedure is quite straightforward. The residual problem is, in fact, indistinguishable from the basic one-dimensional problem and it is appropriate to solve the problem using standard Gilmore-Gomory LP techniques. In cases where there are larger numbers of demand widths and/or the demand widths are relatively narrow in comparison to the master roll width, it would be appropriate to use heuristic problem solving techniques instead. Sample Problem Appendix 2 provides a sample problem to demonstrate the solution procedure described above. Although systematic studies to evaluate the quality of the solutions from this this procedure are still underway, anecdotal evidence from its implementation with the company which supported this research is very favorable. Conclusion This work extends the literature on cutting stock problems by describing a class of problems not previously treated - i.e., one-dimensional problems which include multiple quality grades. A solution technique for this important, complex problem has been provided that out-performs current manual approaches with respect to the criteria of yield

24 maximization and inventory minimization. The approach is robust with respect to the great variety of problems encountered and is also easily implemented. Because it provides very fast solution times, the model can be used to create and evaluate alternative solutions or to respond to last minute changes in demand. Although the model is designed for a situation in which the quality of production is variable, it is structured so that it would automatically adapt if quality improved. In the extreme, if the quality of production were to improve to 100% first grade, the procedure reverts to the approaches used for basic one-dimensional problems. Further research is currently underway on the following questions: 1) How should procedures vary when uncut inventories are high and it is necessary to create more finished product inventories? What about when production quality constrains solutions? Or when there is a shift in the relative importance of the four decision criteria? 2) What are the tradeoffs between improved solution quality and greater computational effort? 3) Could the procedure be enhanced by making it multiple pass instead of purely sequential? 4) In some cases, the sequential procedure could be curtailed before all non-perfect rolls have been processed. That could be done when some of the patterns selected for the perfect rolls could be used with the most flexible of the non-perfect rolls. How can such situations be identified in advance?

25 Appendix 1: MATHEMATICAL FORMULATION OF THE PROBLEM The following formulation is for the cutting stock problem when rolls can have multiple quality grades. Because of the possibilities for alternative positionings of slit widths on any given roll, the size of these problems can be enormous. Because of that complexity and the requirement for integral, 0-1 decisions for each roll, exact solutions for realistic sized problems cannot be efficiently found. Minimize: m n n m. E cijxij + S[ 7 F( E xij)] i=l 1j= j=l i=l S.T.: (1) m n i - ajkxij rk i=l j=l k = 1, 2,...K m n (2). Z ajkxij ek i=l j=l k = 1, 2,..K xij is 1 if pattern j is used for roll i and 0 otherwise A pattern specifies the position, width, and quality of each cut. To be feasible for use with a particular master roll, the total of the cut widths cannot exceed the master roll width, and each cut must be quality feasible.

26 Notation: ajk is the number of rolls of width-quality k in pattern x.j rl is the demand for width-quality k (in rolls) ek is the production limit for width-quality k (in rolls) m m F( [ x.i) is 1 if [ xij > 1 and 0 otherwise i=l 1 i= cij is the cost of using pattern j with master roll i (includes trim loss and a penalty for the use of higher quality material for lower quality orders) S is the cost per slitter setup

27 Appendix 2: SAMPLE PROBLEM PERFECT ROLL WIDTH: 120.000 INVENTORY PARAMETER: 0.0300 DOWNGRADE PARAMETER: 0.9500 MINIMUM KNIFE GAP: 4 NUMBER OF PERFECT ROLLS: 1 COMPUTATIONAL EFFORT: 60000 DEMAND NO. WIDTH QLTY DEMAND MAX INV 1 40.500 1 0 2 38.500 1 8 0 3 38.500 6 0 6 4 28.000 6 0 6 5 25.000 6 0 6 6 24.750 1 89 0 7 24.625 1 25 0 8 20.000 6 0 6 9 19.000 1 20 0 10 19.000 4 4 0 11 18.500 6 0 9 12 16.000 6 0 9 TOTAL INCHES OF DEMAND 3622.875(EQUIV. ROLLS = 30.191) ROLL NUMBER: 1 PARAM: 80.000 WIDTH QUALITY 42 4 78 1 SOLUTION: WIDTH 19.000 QUALITY 4 STARTS AT 0.000 WIDTH 19.000 QUALITY 4 STARTS AT 19.000 WIDTH 4.000 WASTE CUT STARTS AT 38.000 WIDTH 38.500 QUALITY 1 STARTS AT 42.000 WIDTH 38.500 QUALITY 1 STARTS AT 80.500 WIDTH 1.000 WASTE CUT STARTS AT 119.000 115.000 ++++++++++++++++++++++++4+++++++++ ++++ THE FOLLOWING PATTERN IS ALSO FEASIBLE ++++++++++++++++++++++++++++++++++++++ WIDTH 19.000 QUALITY 4 STARTS AT 0.000 WIDTH 19.000 QUALITY 4 STARTS AT 19.000 WIDTH 5.000 WASTE CUT STARTS AT 38.000 WIDTH 38.500 QUALITY 1 STARTS AT 43.000 WIDTH 38.500 QUALITY 1 STARTS AT 81.500 ++++++++++++++++++++++++++++++++++++++ ROLL VALUE= 0.3333 PATTERN VALUE= 0.8572

ROLL NUMBER: 2 PARAM: 80.000 ______________ ROLL NUMBER: 4 PARAM: 80.000 ______________ WIDTH QUALITY 10 4 34 1 16 10 10 4 50 1 WIDTH QUALITY 13 4 31 1 2 5 36 1 8 4 30 1 SOLUTION: WIDTH 18.500 QUALITY 6 STARTS AT 0.000 WIDTH 24.750 QUALITY 1 STARTS AT 18.500 WIDTH 26.750 WASTE CUT STARTS AT 43.250 WIDTH 24.750 QUALITY 1 STARTS AT 70.000 WIDTH 24.750 QUALITY 1 STARTS AT 94.750 WIDTH 0.500 WASTE CUT STARTS AT 119.500 92.750 ++++++44-4-4-4-44++-4+4 —+++++++4-4-+4-4-+4-4-+. ---4-++++-4-4 -THE FOLLOWING PATTERN IS ALSO FEASIBLE 44++++4-++.4++4..++++ +++4-++++4-4+++++++ WIDTH 18.500 QUALITY 6 STARTS AT 0.000 WIDTH 24.750 QUALITY 1 STARTS AT 18.500 WIDTH 27.250 WASTE CUT STARTS AT 43.250 WIDTH 24.750 QUALITY 1 STARTS AT 70.500 WIDTH 24.750 QUALITY 1 STARTS AT 95.250 ++4-+-4+4.++ +++- 1-4-+-4-4-+4-4-4-4++-4 — ROLL VALUE= 0.2000 PATTERN VALUE= 0.7536 SOLUTION: WIDTH 19.000 QUALITY 4 STARTS AT 0.000 WIDTH 24.750 QUALITY I STARTS AT 19.000 WIDTH 4.000 WASTE CUT STARTS AT 43.750 WIDTH 24.750 QUALITY 1 STARTS AT 47.750 WIDTH 19.000 QUALITY 4 STARTS AT 72.500 WIDTH 24.750 QUALITY I STARTS AT 91.500 WIDTH 3.750 WASTE CUT STARTS AT 116.250 112.250 ++++++|++++4-++++++++++++++++++++++++++++ THE FOLLOWING PATTERN IS ALSO FEASIBLE +++-+++-WIDTH 19++.0+++0+++UAL 4 TAR A WIDTH 19.000 QUALITY 4 STARTS AT 0.000 WIDTH 24.750 QUALITY 1 STARTS AT 19.000 WIDTH 7.750 WASTE CUT STARTS AT 43.750 WIDTH 24.750 QUALITY 1 STARTS AT 51.500 WIDTH 19.000 QUALITY 4 STARTS AT 76.250 WIDTH 24.750 QUALITY 1 STARTS AT 95.250 ROLL VALUE= 0.3333 PATTERN VALUE= 0.8572 ROLL NUMBER: 3 PARAM: 80.000 ______________ WIDTH QUALITY _ _ _ _ _ - - - - - - - 10 35 4 i1 ROLL NUMBER: 5 PARAM: 80.000 _ _ _ _ _ _ _ _ _ _ _ _ _ 15 4 50 1 10 4 SOLUTION: WIDTH 20.000 QUALITY 6 STARTS AT 0.000 WIDTH 24.750 QUALITY 1 STARTS AT 20.000 WIDTH 16.000 QUALITY 6 STARTS AT 44.750 WIDTH 24.625 QUALITY 1 STARTS AT 60.750 WIDTH 24.625 QUALITY 1 STARTS AT 85.375 WIDTH 10.000 WASTE CUT STARTS AT 110.000 110.000 ROLL VALUE= 0.3333 PATTERN VALUE= 0.7540 WIDTH QUALITY 10 4 40 1 6 4 39 1 10 4 15 1 SOLUTION: WIDTH 16.000 QUALITY 6 STARTS AT 0.000 WIDTH 24.750 QUALITY I STARTS AT 16.000 WIDTH 16.000 QUALITY 6 STARTS AT 40.750 WIDTH 24.750 QUALITY 1 STARTS AT 56.750 WIDTH 38.500 QUALITY 6 STARTS AT 81.500 120.000 ROLL VALUE= 0.3333 PATTERN VALUE= 0.5136

ROLL NUMBER: 6 PARAM: 80.000 ROLL NUMBER: 8 PARAM: 70.000 WIDTH QUALITY _- -_ _- -_ _ - — _ 5 26 6 4 WIDTH QUALITY 8 4 721 7 4 5 1 3 6 25 1 2 6 38 1 2 6 47 1 SOLUTION: WIDTH 20.000 QUALITY 6 STARTS AT 0.000 WIDTH 20.000 QUALITY 6 STARTS AT 20.000 WIDTH 24.750 QUALITY 1 STARTS AT 40.000 WIDTH 16.000 QUALITY 6 STARTS AT 64.750 WIDTH 38.500 QUALITY 1 STARTS AT 80.750 WIDTH 0.750 WASTE CUT STARTS AT 119.250 119.250 ROLL VALUE- 0.3333 PATTERN VALUE= 0.5128 SOLUTION: WIDTH 16.000 QUALITY 6 STARTS AT 0.000 WIDTH 38.500 QUALITY 1 STARTS AT 16.000 WIDTH 24.750 QUALITY 1 STARTS AT 54.500 WIDTH 16.000 QUALITY 6 STARTS AT 79.250 WIDTH 24.750 QUALITY 1 STARTS AT 95.250 120.000 ROLL VALUE= 0.4167 PATTERN VALUE= 0.7572 ROLL NUMBER: 7 PARAM: 90.000 ______________ ROLL NUMBER: 9 PARAM: 70.000 ______________ WIDTH QUALITY _ _ _ _ _ - - - - - - - 68 2 50 4 6 4 WIDTH QUALITY 53 1 13 4 291 10 4 15 1 SOLUTION: WIDTH 25.000 QUALITY 6 STARTS AT 0.000 WIDTH 25.000 QUALITY 6 STARTS AT 25.000 WIDTH 25.000 QUALITY 6 STARTS AT 50.000 WIDTH 25.000 QUALITY 6 STARTS AT 75.000 WIDTH 20.000 QUALITY 6 STARTS AT 100.000 120.000 ROLL VALUE= 0.2500 PATTERN VALUE= 0.0232 SOLUTION: WIDTH 24.750 QUALITY 1 STARTS AT 0.000 WIDTH 24.750 QUALITY 1 STARTS AT 24.750 WIDTH 20.000 QUALITY 6 STARTS AT 49.500 WIDTH 24.750 QUALITY 1 STARTS AT 69.500 WIDTH 25.000 QUALITY 6 STARTS AT 94.250 WIDTH 0.750 WASTE CUT STARTS AT 119.250 119.250 ROLL VALUE= 0.4167 PATTERN VALUE= 0.7557 *** ROLL NOT CHARTED ***

ROLL NUMBER: 10 PARAM: 70.000 WIDTH QUALITY 53 1 6 4 36 i1 ROLL NUMBER: 12 PARAM: 60.000 WIDTH QUALITY 6 4 41 1 7 6 66 1 10 15 4 1 SOLUTION: WIDTH 24.750 QUALITY i STARTS AT 0.000 WIDTH 24.750 QUALITY I STARTS AT 24.750 WIDTH 20.000 QUALITY 6 STARTS AT 49.500 WIDTH 24.750 QUALITY I STARTS AT 69.500 WIDTH 25.000 QUALITY 6 STARTS AT 94.250 WIDTH 0.750 WASTE CUT STARTS AT 119.250 119.250 ROLL VALUE= 0.4167 PATTERN VALUE= 0.7557 SOLUTION: WIDTH 6.000 WASTE CUT STARTS AT 0.0 WIDTH 40.500 QUALITY i STARTS AT 6.000 WIDTH 7.500 WASTE CUT STARTS AT 46.500 WIDTH 38.500 QUALITY I STARTS AT 54.000 WIDTH 24.750 QUALITY I STARTS AT 92.500 WIDTH 2.750 WASTE CUT STARTS AT 117.250 103.750 THE FOLLOWING PATTERN IS ALSO FEASIBLE...4.4.4.4.4.4.4...+4.. +......++++... + WIDTH 6.000 WASTE CUT STARTS AT 0.000 WIDTH 40.500 QUALITY i STARTS AT 6.000 WIDTH 10.250 WASTE CUT STARTS AT 46.500 WIDTH 38.500 QUALITY 1 STARTS AT 56.750 WIDTH 24.750 QUALITY I STARTS AT 95.250 ROLL NUMBER: 11 PARAM: 70.000 WIDTH 61 QUALITY 1 6 4 30 1 8 4 15 1 ROLL VALUE= 0.5000 PATTERN VALUE= 0.8889 SOLUTION: WIDTH 24.750 QUALITY i STARTS AT 0.000 WIDTH 24.750 QUALITY 1 STARTS AT 24.750 WIDTH 20.000 QUALITY 6 STARTS AT 49.500 WIDTH 24.750 QUALITY I STARTS AT 69.500 WIDTH 25.000 QUALITY 6 STARTS AT 94.250 WIDTH 0.750 WASTE CUT STARTS AT 119.250 119.250 ROLL VALUE= 0.4167 PATTERN VALUE= 0.6754 PERFECT ROLLS NUMBER CUT / INCHES USED / PATTERN 3 112.375 38.500 (1) 24.625 (1) 24.625 (1) 24.625 (1) 4 117.500 24.625 (1) 24.625 (1) 24.625 (1) 24.625 (1) 19.000 (1) 17 118.000 24.750 (1) 24.750 (1) 24.750 (1) 24.750 (1) 19.000 (1) NO. PERFECT ROLLS USED = 24 NO. PERFECT ROLLS AVAIL = 1

SUMMARY OF NON-PERFECT ROLLS QUALITY GRADE 1 1039 INCHES ( 8.658 EQUIV. ROLLS) QUALITY GRADE 2: 0 INCHES ( 0.000 EQUIV. ROLLS) QUALITY GRADE 3: 0 INCHES ( 0.000 EQUIV. ROLLS) QUALITY GRADE 4: 362 INCHES ( 3.017 EQUIV. ROLLS) QUALITY GRADE 5: 2 INCHES ( 0.017 EQUIV. ROLLS) QUALITY GRADE 6: 21 INCHES ( 0.175 EQUIV. ROLLS) QUALITY GRADE 7: 0 INCHES ( 0.000 EQUIV. ROLLS) QUALITY GRADE 8: 0 INCHES ( 0.000 EQUIV. ROLLS) QUALITY GRADE 9: 0 INCHES ( 0.000 EQUIV. ROLLS) QUALITY GRADE 10: 16 INCHES ( 0.133 EQUIV. ROLLS) TOTAL - 12.000 ROLLS TOTAL PRODUCTION RESULTS TOTAL ROLLS= 35 TOTAL YIELD = 97.129 % TOTAL INVTY = 10.852 % WIDTH QUAL PROD DEMND INV MAX 40.500 1 1 1 0 0 38.500 1 8 8 0 0 38.500 6 1 0 1 6 28.000 6 0 0 0 6 25.000 6 3 0 3 6 24.750 1 90 89 1 0 24.625 1 27 25 2 0 20.000 6 6 0 6 6 19.000 1 2 20 1 0 19.000 4 4 4 0 0 18.500 6 1 0 1 9 16.000 6 6 0 6 9

28 References: Cheng, R.M.H. and A.W. Pila, "Maximized Utilization of Surface Areas with Defects by the Dynamic Programming Approach," ISA Transactions, V.17 (1977) No.4, pp. 61 -69. Foster, J.B. and W.R. Lesyna, "An Application of the TwoDimensional Cutting Stock Problem for Rolls with Defects," presented at ORSA/TIMS National Conference (Los Angeles), 1978. Gilmore, P.C. and R.E. Gomory, "A Linear Programming Approach to the Cutting Stock Problem," Operations Research, V.9 (November-December 1961), pp. 849-859. - and, "A Linear Programming Approach to the Cutting Stock Problem - Part II," Operations Research, V.ll (November-December 1963), pp. 863-888. and "Multistage Cutting Stock Problems of Two and More Dimensions," Operations Research, V.13 No.l (January-February 1965), pp. 94 -120. Hahn, S.G., "On the Optimal Cutting of Defective Sheets," Operations Research, V.16 No.6 (November-December 1968), pp. 1100-1114. Pierce, J.F., Some Large Scale Production Scheduling Problems in the Paper Industry. Englewood Cliffs, N.J.: Prentice Hall, 1964. Sculli, D., "A Stochastic Cutting Stock Procedure: Cutting Rolls of Insulating Tape," Management Science, V.27 No.8 (August 1981), pp. 946-952.