A Two-dimensional Trim-Loss Problem with Sequencing Constraints

Abstract

A two-dimensional trim-loss problem is con­ sidered in which the cutting is two-stage but there are constraints on the sequencing of the cutting of orders. A method is developed in which problem reduction is used to generate a set of possible cutting patterns at each step and an heuristic choice made of a pattern from that set, The sequences of patterns produced, although slightly sub-optimal as regards trim­ loss, fully satisfy the sequencing constraints,

A. I. Hinxman University of Liverpool Liverpool, England

being specified by its length (longer dimension) and breadth (shorter dimension), Each order is designated by a code, If the order is for glass with high quality edges the first character of the code is "F". We refer to these as~ K orders and to the remainder as ~orders.

I, Introduction

The trim-loss, or cutting stock, problem arises whenever material manufactured continuous­ ly or in large pieces has to be cut into pieces of sizes ordered by customers. The basic problem is to so organize the cutting as to mini­ mize the amount of waste (trim-loss) resulting from the cutting,

In the one-dimensional case order lengths of some material such as steel bars have to be cut from the stock lengths held by the supplier. Gilmore and Gomory (1961, 1963) have formulated a linear programming solution of this problem, which also arises in the slitting of steel rolls, cutting of metal pipe, and slitting of cellophane

rolls.

In the two-dimensional case the stock is held as large rectangular sheets from which smaller rectangles must be cut. Work has been done on this problem by Gilmore and Gomory (1965), who use a linear programming method, Adamowicz and Albano (1976), whose method is one of dynamic programming,· and Hinxman ( 1976) , using a problem reduction method, Hahn (1968) con­ siders the problem that arises when the stock sheets contain flaws, and gives a dynamic programming algorithm.

Dyson and Gregory (1974) consider a problem ar~s~ng in the flat glass industry in which the problem is not simply to determine a set of cutting instructions (known as cutting patterns) which minimize trim-loss, but to find a set which whilst leading to low trim-loss are also an acceptable sequence according to other opera­ tional criteria. Their method is to produce a minimum loss set of cutting patterns and then to find an acceptable way of sequencing them. This report describes an alternative approach to a similar problem, in which the sequencing and trim-loss criteria are considered together,

2. Statement of the problem

The ~aterial under consideration is glass. Each order received from a customer consists of a demand for specified numbers (demands) of pieces of each of o~e or more shapes, a shape The cutting of the stock sheets is a two stage process, and corresponding to each stage of the cutting there is a stripping process, to produce edges of the required quality, that may be manual or automatic. During the first stage of the cutting the sheet is moving in the direction of its longitudinal axis and may be considered to have a "leading" and a "trailing" edge with respect to this motion, The first set of cuts are perpendicular to the direction of motion and are cross cuts. The sub-sheets resulting from the fi~stage of cutting will be cut into pieces according to the corresponding sub-patterns.

Operational constraints on the design of cutting patterns due to the design of the cutting machinery impose:

1. an upper bound on the number of shapes in a sub-pattern,
2. ii) an upper bound on the number of sub­ patterns in a pattern,
3. iii) a lower bound on the distance of the first cross cut from the leading edge of the sheet,
4. iv) a lower bound on the distance of the last cross cut from the trailing edge of the sheet.

The pick-off length of a sub-sheet or piece is its dimension in the direction of the length of the sheet from which it was cut, its other dimension being its pick-off breadth (see figure 1), The stripping following each stage of cut­ ting may be manual or automatic, This affects the reduction in dimensions of the initially cut pieces by the stripping process.

The pieces resulting from the cutting and stripping process are picked off for despatch from one of four legs, a~ being a conveyor belt with its associated washing and handling facilities. All the pieces resulting from the cutting of a sub-pattern must be routed to the same leg. The routing of pieces to legs must be consistent with the dimension constraints on the legs and also with the requirement that type F pieces must be picked off from legs with wash­ ing facilities. There is a further restriction that pieces for not more than three different orders may be picked off any leg during the cut­ ting of any one pattern.

The restrictions on the design of individual cutting patterns having been described it is now necessary to consider how a set of cutting patterns is used to provide instructions for cutting all the orders in an order list. Initially a cutting pattern is selected.

It will specify the size of stock sheet to be used and the order pieces to be cut from this sheet. For each shape, s, in the pattern there is a number, n , such that if the pa~tern s is repeated ns times the demand for that shape will be satisfied, whilst if the pattern is only repeated ns-1 times this will not be the case. The number of stock sheets cut to this pattern will be the smallest of the n 's. s

When this has been done the original order list will be converted to a new one reflecting the demands that have not yet been satisfied. A new cutting pattern is selected and the pro­ cess repeated until all the demands have been satisfied.

Operational costs connected with the pick­ ing off and packing of orders will affect the choice of cutting patterns and the sequence in which they are used. Suppose the use of a cut­ ting pattern has just been completed. The next cutting pattern to be used should include all the shapes in the last cutting pattern the demands for which have not yet been satisfied. In addition, if there were any shapes, the d:mands for which were satisfied at the comple­ t~on of use of the last cutting pattern, belong­ ing to orders which include other shapes, the demands for which have not been satisfied, then such a shape from each such order should be in­ cluded in the new cutting pattern. For each failure to make the appropriate inclusion the sequence break cost is incurred.

There is also an absolute constraint on the sequence of cutting patterns. If a shape belongs to a loose load order, which will have a code starting with the characters "FD", then it must not be cut until demands for all larger shapes in that order have been satisfied.

Table I shows the dimensions of the avail­ able stock sheets.

3. The top-level state-space

The process of choosing and utilizing cut­ ting patterns described above can be represented in terms of a state-space (Nilsson, 1971; chaps. 2, 3). The states are lists of unsatisfied orders, and the operators are cutting patterns together with the number o£ times they are used. The start state is the original order list and the ~oal state the empty order list. We require to f~nd the path between the two for which the combined cost of trim-loss and sequence breaks is minimal.

In order that the resources required by a program to compute a sequence of cutting pat­ terns may be kept within reasonable bounds back­ tracking must be restricted. A certain a~ount o~ time_is allocated for the generation of pos­ s~ble f~rst patterns. At the end of this time the "best" of the generated patterns is selected. The number of times it is to be used is calcul­ ated, the demands in the order list are adjusted to.take account of the pieces cut by the use of th~s pattern, and the adjusted order list to­ gether with the first pattern defines the start­ ing point for the generation of possible second patterns. The process is repeated until all the demands in the order list have been satisfied.

This method of working corresponds to the development of a path across the state-space graph without backtracking. The generation of a subset of the possible cutting patterns at each step (done in the work presented here by a problem reduction technique) corresponds to partial develo~ment of the corresponding node, and the select~on of the "best" pattern repre­ sents the application of an evaluation function.

The evaluation function used in the present case combines a measure of the possibly avoid­ able trim-loss (it can be determined that the cutting of some of the pieces included in the pattern will unavoidably involve trim-loss) in the pattern, the "urgency" (see section 6.2) of the pieces included in it, the cost of sequence breaks that would occur at the present point in the sequence if it were used, and the possible costs of sequence breaks that might occur later in the sequence if it were introduced at this point. The evaluation function is not in Nilsson's terms "admissible", but has b~en chosen on the basis of experience as one whose use should not result in seriously sub-optimal solutions.

The quality of solutions generated will be limited by the correctness of the partial devel­ opment (whether the operator corresponding to the arc belonging to the optimal path from this node is generated) and the accuracy of the evaluation function (whether when generated the operator is correctly identified).

More complicated search strategies than the one adopted could have been followed. A wider ranging search of the top-level state-space might have been performed. This would have required the use of more computer time. Alternatively the problem reduction at a node might have used information about the path on which the node lay, rather than simply information local to the node, to decide on reductions. This would require a great deal more information to be simultaneously present in the store of the machine. The method chosen was one in which it seemed that low com­ putational costs would be paid for the finding of acceptably good solutions.

4. Problem reduction

When a problem reduction method is applied to a complex problem, this problem, or goal, is re­ duced by successive refinement to a number of simpler problems, subgoals, whose solutions, when taken together, can be combined to provide a solution to the original goal. Usually there will be more than one way in which the goal, or a subgoal, can be broken down into subgoals. It is, of course, only necessary to solve the sub­ goals corresponding to one breakdown in order to solve the goal or subgoal from which they were generated.

A good general description of problem reduc­ tion methods is given by Nilsson (1971; chaps.4, 5). Here will be described only the structure of the method used in the present work. Let G 0 be the goal. Then there is a set of actions {A 01 , A 02 , ··· }which may be taken towards achieving G 0 · After action Aon has been taken G 0 will have been reduced to subgoal Gon· AOn followed by the actions necessary to achieve GOn will achieve G 0 · GOn may be indivisible. In this case either it can be achieved by some basic action, in which case a solution to G 0 has been found,or no such appropriate basic action exists, in which case there is no solution of G 0 including Aon· If GOn is not indivisible then it can be reduced to some action AOnm and a further sub­ goal GOnm· this process being repeated until an indivisible subgoal is defined. If no solution to any subgoal of a divisible subgoal can be found then . that higher subgoal is itself in­ soluble.

This process can be represented graphically (see figure 2). Let Go be the root of a tree·

Then A 01 , A 02 , ··· are represented as directed arcs connecting G 0 with its successor nodes G 01 , G 02 , ··· ,a similar representation applying to the connection of these with their successors. A terminal node represents an indivisible sub­ goal. If it is soluble, its solution action can be associated with it. This together with the labels of the arcs connecting it with G 0 defines a solution of G 0 · If it is not soluble then an "insoluble" marker can be attached to it. Simi­ larly an insoluble marker can be attached to a node all of whose successors are insoluble.

X denotes insoluble

Yn denotes solution of indivisible subgoal Thus G 0 is solved by

or

Note that G 02 is deduced to be insoluble by virtue of the insolubility of its successors.

This form of problem reduction, in which all the nodes of the problem reduction tree are OR nodes, can be regarded as a state-space method, with start node an empty list of actions to be taken to achieve the goal and goal nodes complete lists of such actions. However, two features of the present work make it more desirable to con­ sider it as a problem reduction method. Firstly, when a successor node of the tree is generated it contains a more complete list of actions than its parent; the subgoal it specifies is less complex and the problem is indeed "reduced". Secondly, whereas in state-space methods the available operators usually have some similarity to each other, here there are very distinct classes of action that may be taken, depending on what part of the list of actions remains to be completed.

5. Structure of the problem reduction

Each node of the problem reduction tree in­ cludes in its label a subgoal description and the name of a function that is capable of generating

a sequence of alternatives for the reduction of that subgoal. For a primitive subgoal such a reduction is a solution. Let us refer to the occurrence of a function at a node as an instance of that function.

In an iteration of the problem reduction process, a node of the problem reduction tree is selected, The function at that node is invoked to give the reduction for the subgoal that is next in the sequence after those reductions that were generated by previous invocations of that function at that node. It will either create a new node in whose label are included the subgoal resulting from the reduction and the name of the function to be used for reducing this subgoal, or report that the sequence of reductions has been exhausted, Iterations of the process continue until what is regarded as an adequate number of alternative solutions of the goal have been generated.

It has been said that when a function creates a node it places a function name in its label, Figure 3 shows the relationships of the subgoal processing functions in this respect, An arrow directed from one function name to another in­ dicates that the label of the node created by the first may include the name of the second. Where more than one arrow leaves the name of a function, this indicates that a choice of func­ tions is made according to the features of the subgoal set up.

Figure 3

Hierarchy of subgoal processing functions

Consider the situation that can occur for the generation of any cutting pattern other than the first. The previous cutting pattern may have included one or more sub-patterns that each included two shapes (pair~). If the demand for a shape belonging to a pa1r has not yet been satisfied, then there is a choice to be made as to whether it should belong to a pair with the same or a related partner in the proposed new pattern. The choices on the retention of pair­ ings are made in USED-PAIR-SELECT,

There may be a number of shapes included in the previous pattern the demand for which has not yet been satisfied, Some of these may have been included in the proposed pattern by choices made in USED-PAIR-SELECT. The choices as to which of the remainder should be included, and what their orientations should be, in the proposed pattern, are made in MID-SHAPE-SELECT.

There may be one or more shapes completed at the end of the use of the previous cutting pat­ tern that belong to orders containing shapes the demands for which have not yet been satisfied, In MID-ORDER-SELECT the choices are made as to which shapes, if any, from such orders should be included in the proposed pattern, and what their orientations should be,

The choices made in MID-SHAPE-SELECT, MID­ ORDER-SELECT and MOST-URGENT-PIECE-CONSIDER, are that shapes shall be included in a pattern in separate sub-patterns. Each instance of SUB­ PATTERN-EXTEND is concerned with one such sub­ pattern and chooses whether it should include one or two shapes, If the choice is for two shapes the· choice of the second shape is made.

The choice of stock sheet size to be used by the proposed pattern is made in STJB-PATTERN­ DESIGN-CONTINUE. A further sub-pattern may also be included in the pattern by this function.

Each instance of SUB-PATTERN-CONTINUE­ KNOWN-SHEET chooses whether a further sub­ pattern should be included in a partially com­ pleted pattern, and if so, what this sub-pattern

should be,

In LEG-ALLOCATE an allocation of sub­ patterns to legs is made if a possible one exists. If it does not, then the proposed pattern is ruled out of further consideration, otherwise an evaluation is made of the "merit" of the proposed pattern. The allocation of sub-patterns to legs is a primitive subgoal.

6, Heuristics

Space does not permit the description in detail of all the heuristics used. Scme of the more significant ones will be outlined here.

6.1 Orientations

For each shape a preferred orientation can be defined. For a shape which the constraints of the problem require to be cut with a certain orientation it is this orientation, For any other shape, all possible sub-patterns that could be formed including this shape are con­ sidered, The orientation in that sub-pattern within which there is least trim-loss is the preferred orientation. When the possibility of including a shape in a pattern is considered, it will usually be with this orientation. The principle applied here is that if the trim-loss in each sub-pattern is minimized the overall trim-loss is likely to be minimized,

6,2 Urgency

The urgency of a shape reflects the desira­ bility that the shape should feature in the early cutting patterns of a solution sequence and is a function of its dimensions and demand, Two cases are identified in which particularly high urgencies are assigned,

The highest urgencies are given to shapes with lengths above a certain limit, since it will be difficult to introduce these later in the sequence when sequencing desiderata lead to in­ clusion in a pattern of several other shapes.

The next most urgent set of shapes are those which can only occur in leading sub-patterns. If such shapes were left until late in the pattern sequence, this might be forced to finish with patterns consisting only of leading sub-patterns, with consequent extreme trim-loss.

Adjustments to urgencies are made in the light of sequencing considerations. For ex­ ample, the largest shape in a loose load order will have its urgency increased to exceed the highest urgency, as determined by the initial calculations, of any shape in the order. This takes account of the fact that the smaller can­ not be cut before the larger and therefore its own higher urgency would still not lead it to be introduced into an early pattern.

6.3 Forcing shapes in

The four subgoal processing functions at the top of the hierarchy are all concerned with giv­ ing direct consideration to the possible inclu­ sion in the current pattern of shapes that are deemed at this point to be particularly desir­

able.

Experience shows that once shapes from two different orders have appeared in the same sub­ pattern they should continue to do so. USED­ PAIR-SELECT introduces such pairs into the pro­ posed pattern.

Sequencing desiderata mean that other shapes for which demand has not been satisfied should be introduced into the proposed pattern. MID­ SHAPE-SELECT will introduce these shapes, and its first choice will be to give them their preferred orientations, provided a look-ahead indicates that this will not cause difficulties in MID­

ORDER-SELECT.

It is worth giving attention to several alternative developments of the partial proposals generated by these first two functions, so the search is organized in such a way that they are re-entered relatively less frequently.

Choices made in MID-ORDER-SELECT complete consideration of the inclusions desirable for reasons of sequencing. The reasoning that led to the definition of urgency suggests that the most urgent shape remaining unsatisfied in the order list should be specifically considered for inclusion. This is done by MOST-URGENT-PIECE­ CONSIDER.

6.4 SUB-PATTERN-DESIGN-CONTINUE

When SUB-PATTERN-DESIGN-CONTINUE considers which size of stock sheet should be used, it does so in the light of the specifications that have already been made that sub-patterns con­ taining certain shapes shall be present. For each stock sheet size the manner in which each sub-pattern can be constructed so as to include the stated shapes with minimum trim-loss is determined. The sheets are ranked on the aggregates of these minimum trim-losses, the lowest aggregate indicating the most preferred size. It is likely that a partial cutting pat­ tern for which the trim-loss already unavoidable is low can be completed in such a way that the total trim-loss is low.

Within a choice of stock sheet size a number of possible alternative additions of sub-patterns to the proposal may be generated. The evalua­ tion of these alternatives takes account of the urgency of the piece it has been decided to in­ clude in the sub-pattern, the trim-loss within the sub-pattern and, by means of a look-ahead, the likely amount of trim-loss in the pattern as a whole outside of the trim-loss in the individual sub-patterns. The evaluation also gives some preference to additions which keep the number of different shapes in the final pattern small as these will lead to fewer complications in the pattern sequencing.

7. Results

A program using these techniques has been written in Algol 68-R (Woodward and Bond, 1972) and tested on an ICL1906S against 16 sets of data. A typical data set is shown in table 2. The results from these test runs are shown in table

3. During the development of the program a con­ siderable number of heuristics were experimented with. These involved different methods of problem reduction, different orderings for the sequences of problem reductions, resulting in different subsets of the possible reductions be­ ing used, different ways of calculating the "urgency" of pieces, and different methods of evaluating the "best" pattern given a set of alternatives. Some of these heuristics pro­ duced very good results with some sets of data whilst performing unacceptably badly on others. These results have been collated to produce column 4 of table 3. Column 5 thus shows the known deficiencies of the program.

The execution time of the program depends on the size of the data set, the format of the output and whether the object code incorporates run-time checking. However, 4 minutes may reasonably be regarded as an average execution time. No sequence breaks occur in any of the pattern sequences.

8. Conclusions

The program succeeds in producing sequences of cutting patterns with no sequence breaks, which was one of the design ~ims. In this re­ spect it would appear to be superior to that of Dyson and Gregory (1976). Its trim-loss behaviour is known not to be optimal. However, on the test data used the percentage of the material lost as scrap never rose to 10% and the average discrepancy between the solutions pro­ duced and the known best solutions was 1% of the material used. Whether the benefits of absence of sequence breaks outweigh the sub-optimabil­ ity of the trim-loss behaviour would depend on the details of the industrial environment.

Heuristic information is embodied in the program in the urgencies, the evaluation of patterns, the chosen problem reduction structure and the extent to which the problem reduction tree is developed. The greatest gains in performance would be likely to result from the improvement of the first two of these.

Acknowled~ements

This research was supported by SRC research grant B/RG/83176. The grant holder is Dr. T. B. Boffey.