2. GENETIC ALGORITHMS (GAs)

GAs are a new approach to solving complex problems. As a result of the enormous increase in the capacity of computer technology, applying GAs, in recent years in particular, has become more and more widespread, because the problem of the cost of using computer facilities that might have arisen, is in reality only a minor one.

GAs came to the fore in the 1970s, through the work of Holland (1975). The aim was to provide solutions to the many problems that arose in different industrial and service sectors that proved extremely difficult to solve with the methods that were known at the time. The main contribution of GAs is solving optimization and search problems by providing a solution that is not the optimal one but that is, nevertheless, a good approximation to the optimal one.

How GAs work, which is also summarized in Figure 1, will next be explained. The starting point is an initial population of solutions, which is usually randomly generated. This population undergoes a number of transformations designed to improve the solutions provided. Such transformations are made in the main loop of the algorithm, and have three basic stages: selection, reproduction, and replacement (Goldberg, 1989; Michalewicz, 1996).

The structure of a genetic algorithm adapted from Michalewicz (1996); P(t), the population of the solution.

The selection stage consists of sampling the initial population, thereby obtaining a new population with the same number of individuals as the initial one. This stage aims at improving the quality of the population by favoring those individuals that are more adequate for a particular problem (the “quality” of an individual is gauged by calculating its fitness, which indicates how good a solution is). Although there are numerous techniques around for the selection process, the most widely used one is Stochastic Universal Sampling (Baker, 1987).

The reproduction stage employs what are called “generic operators.” “Crossover” and “mutation” operators are the ones that are most widely applied. Generally speaking, the crossover operator works by taking two parents and exchanging part of their strings, thereby generating two new individuals, the offspring. For its part, the mutation operator is applied to an offspring and alters its string in some way, for example, by changing the order of some of its genes. A further offspring is obtained in this way. At the end of the reproduction phase there are two independent populations: the parents and the offspring. The final stage of the process is called replacement, and it consists of forming a new population by mixing the two initial ones.

3. AN APPROACH TO THE PACKING PROBLEM

Cutting problems like the one this particular company has are common to the textile, leather, shipbuilding, metal, and many other industries where obtaining pieces from a base plate is a recurrent activity. Since the 1960s, many researchers have tackled the problem and attempted to design algorithms to solve it.

The cause of the problem lies in the fact that the raw materials that industry uses are available in certain standard sizes that usually need cutting down before they can be used in the industrial process. The obvious aim of this cutting phase is to make the maximum use of the raw material. Outstanding among early work in this field was that carried out by Gilmore and Gomory (1961, 1963) in resolving single dimension problems; the scope of this work was widened in 1965 to 2-dimensional problems (Gilmore & Gomory, 1965). Analyses of these problems have since spread rapidly, although no global solution has been offered for all of them because of their complexity.

One way of solving this type of problem is to divide it into several subproblems (Dyckhoff, 1990), and try to solve each of them separately. This study will focus in particular on one such subproblem, the packing problem, which fits perfectly into the kind of industrial process that a solution is needed for.

Various authors have confronted this particular problem, although none have found a method that provides the optimum solution for every case (Hopper & Turton, 2001; Lodi et al., 2002). Healy et al. (1999) presented an efficient algorithm for identifying the empty space that can be used to cut a new piece when the existing cutting pattern does not have the bottom-left property. A cutting pattern has the bottom-left property when each cut piece is as far down, and as far left, as possible in the stock rectangle.

Lai and Chan (1997) presented a heuristic algorithm based upon an evolutionary strategy approach. Their algorithm includes an improvement (hill-climbing) procedure based on dividing the ordered list into active (cut) and inactive (uncut) pieces and seeing if any (currently) uncut pieces can be cut. Their mutation process involves swapping two pieces in the ordered list. Leung et al. (2001) used the ordered representation of Lai and Chan (1997) and discussed producing a cutting pattern from it using both the difference process algorithm of Lai and Chan (1997) and a standard bottom-left algorithm (Jakobs, 1996). They showed that problems exist such that the optimal solution cannot be found by these two approaches. They presented a simulated annealing heuristic with a move corresponding to either swapping two pieces in the ordered representation or moving a single piece to a new position in the representation. They also presented a genetic approach involving five different crossover operators.

4. A DESCRIPTION OF THE PROBLEM

Before analyzing the solution that we have proposed, more in-depth comments should first be made on the characteristics of the problem to be solved.

The first point to be noted is that the dimensions of the metal sheets are always the same. This simplifies the problem a great deal, as pieces are always placed on the same type of sheet. Furthermore, as customers generally order pieces that are of large dimensions, the number of pieces that fit onto a single metal sheet generally ranges between 5 and 20.

Each customer order is generally made up of several hundred pieces, and as they are usually large, more than 50 metal sheets are generally involved in each order.

Furthermore, the particular conditions of the L-type guillotine used by the company entails space on the metal sheets being lost, which is an important point to be kept in mind. On its first approximation to the metal sheets the guillotine makes two “approximation cuts” of 5 mm, one vertically and the other horizontally, besides which the clamping system used to hold the metal causes a further loss of 20 mm horizontally. Figure 2 shows the material loss that results from using this particular L-type guillotine.

Leftovers.

The initial dimensions of the surface are 2992 × 1250 mm; but, considering the above factors, the new dimensions of the metal sheets are (2992 − 5) × (1250 − 20 − 5) mm.

Having commented on the particular nature of the problem that was analyzed, two independent algorithms are developed next: the position algorithm and the cutting sequence algorithm.

5. THE SOLUTION PROPOSED FOR CUTTING

This section will analyze the GA designed to minimize the number of steel sheets that were used. The steps that were followed to do this will be described next. The codification used in the algorithm is based on integer numbers; each piece to be placed on the metal sheet is assigned a number, and an individual chromosome is formed with a string of numbers. The order in which the numbers appear in the string represents the positions on the metal sheet of the pieces.

An example will be worked through to explain codification clearly: imagine you have four rectangular pieces to be placed on the metal sheet, and that each of these pieces is assigned a correlative number, the first piece is assigned the number 1, the second is number 2, and so forth. The individual (1, 3, 4, 2) could be a solution to the problem, which would mean that piece 1 is first onto the metal sheet, followed by 3, then 4, and finally by 2.

In the case being analyzed in this study, this codification needs some modification, because, as has already been mentioned, not all the pieces fit onto the same metal sheet, and several sheets must be used to make all the pieces ordered by the client.

The first problem to solve is the way in which a piece is assigned to a metal sheet when the individual is analyzed. When the first value of the individual (the first piece) is read, a metal sheet is “activated,” and the piece is places on the sheet; the individual' second value is then read, and an analysis determines whether it can be fitted onto the sheet or not (the “free fall with replacement algorithm” is used to determine if a piece fits in a sheet; see the next paragraph). If the piece fits, then that piece is assigned to the metal sheet and the third value is read off. This reading process continues until one of the pieces fails to fit onto the metal sheet. On detecting that a piece cannot be assigned to a metal sheet because the space available is not large enough, a second metal sheet is “activated” and the piece is assigned to this second sheet. The process is iterated until all the pieces have been placed.

For the positioning of the pieces on the sheets, a modification of the “bottom-left algorithm” (Jakobs, 1996) was used. The reason for using this modification lies in the fact that Jakob's algorithm does not permit certain positions of pieces on the sheet (Gómez et al., 2000).

This algorithm, called the “free fall with replacement algorithm,” works as follows: the first piece assigned to the metal sheet is placed in the bottom left-hand corner (piece 1, Fig. 3), and the others are places as low down in the space as they can possibly fit. Once the piece has been placed, a check is made as to whether there is a space below it. If there is a space, then a search ensues to see if one of the rectangles still to be placed fits into it. If such a rectangle shows up, it is slotted into the space.

Free fall with replacement.

Having established the methods used to codify the placement of the pieces and to calculate their fit, the type of crossover and mutation to be used must next be decided on. In the light of earlier work that we have carried out (Gómez & De la Fuente, 2000), a partial matching-type crossover was opted for, along with an order-based mutation.

The partial matching crossover (PMX; Goldberg & Lingle, 1985) is a crossover type that is widely used in published work on how to resolve the travelling salesman problem by using GAs with decimal coding. Adapting this crossover to packing problems is simple, and will now be described. Given two parent chromosomes, the operator copies a substring of one of the parents directly into the same positions in the offspring. The remaining positions are then filled with the values that have yet to be used, in the same order as they occur in each of the parents.

The mutation, called order-based mutation, is based on the work of Davis (1991). It consists of interchanging the positions of two rectangles of the same individual.

6. CUTTING THE PIECES

As has already been pointed out, a second algorithm had to be applied to instruct the guillotine's numeric control on how to cut the metal sheets to obtain the pieces. It is useful to explain the way the guillotine approaches the steel sheets to understand how the algorithm works. The guillotine starts at the top, right-hand corner of the sheet, and after making the initial two cuts that have already been mentioned in Section 4, it proceeds to cut the pieces.

The algorithm responsible for carrying out this task acquires the distribution of the pieces in the metal sheet from the GA, and generates an output file that tells the guillotine's numeric control in what order to cut the pieces. The algorithm simulates the guillotine working process.

To indicate this sequence the X and Y coordinates of the different cuts need to be known. Thus, for example, to cut pieces 1 and 2 of Figure 4, the coordinates of the bottom left-land corner of both pieces should be given. The guillotine first cuts up to coordinates X and Y of the second piece and then cuts the first piece.

An example of the cutting sequence.

The problem of this cut lies in the areas where there is no piece assigned, which also has to be cut if the pieces ordered by the client are to be produced. Figure 5 highlights the problems that cutting these pieces involves; if the useful pieces are the rectangles (1, 2, 3, 4), and (A, B) represent the wasted parts of the metal sheet, then piece B cannot be obtained from a single cut, and must be divided in two because of its nonrectangular shape.

The cutting sequence.

The task of the sequencing algorithm that was designed consists of detecting these problematical parts and of deciding how to divide them. To do this, the algorithm simulates how the guillotine works. First, it acquires the positions of the pieces to be cut from the GA and then it fictitiously places the guillotine in the top, right-hand corner of the metal sheet and attempts to start cutting the different pieces one by one. When it detects that a piece cannot be cut because there is a waste piece in the guillotine's cutting area, it tells numeric control to eliminate this leftover piece before proceeding to cut the customer's piece.

Figure 5 serves to illustrate this process. First, an attempt is made to cut piece 1. To see if this piece can be cut, the guillotine is “placed” in the lower left-hand corner of this same piece, and the metal sheet is “cut” in this position. If the piece is produced cleanly, the following piece is tried; if it is not, then the extra material on piece 1 is eliminated. In this example, the piece is obtained without extra material and the cut is accepted; once liberated, the simulator attempts to cut the next piece, which in this particular case is piece 2. However, a problem arises, because if the guillotine is placed in the bottom, left-hand corner of this piece and the cut is made, the piece that is produced is L-shaped and is made up of pieces A, 2, and part of B. Once this problem is detected the algorithm must determine how to obtain piece 2 without extra material. In this case, the algorithm tells numeric control that first piece A should be cut, and for this to occur it provides numeric control with the relevant coordinates for the bottom, left-hand corner; then one part of piece B must be cut, so the algorithm must provide numeric control with the coordinates. When these cuts have been made, piece 2 can easily be cut out. Piece 3 is the next to be cut; but before doing so, the part of piece B that has yet to be cut must be cut; finally, piece 4 is cut out.