Abstract: Cutting Stock Problems (which are NP-hard), have numerous applications in industry (iron, steel, glass, wood, paper industry) and in studies of computer operations (multi-programmed computer systems, multiprocessor systems). The crucial step in this problem is generating cutting patterns, especially when we have a non-guillotine cutting. This kind of problem also called trim loss problem have several methods: Bottom Left, Best Fit, Difference Process. We propose an algorithm of generating patterns using Difference process method which guarantee improved non-guillotine cutting patterns.
INTRODUCTION
The Cutting Stock Problem (CSP) arises in many mass production industries, when small items (forms) are being cut out from large objects (gross proceeds). The first formulation of the CSP was produced by Kantorovich (1939), leading to the following Integer Linear Programming problem as detailed by Benhamamouch (1979):
| • | M = (L, H) dimensions of large objects to be cut. |
| • | di = (li, hi) (I = 1,...,m) dimensions of small items to satisfy in quantity qi. |
| • | The matrix A (aij) is built such as each column is a generated cutting pattern. |
| • | The solution is represented by using xj times of the jth cutting pattern (j = 1,...,n where, n is the number of generated cutting patterns). cj is its correspondent loss. |
The CSP have two parts. The first one is the assortment problem addressing the issue of choosing proper dimensions for the large objects. The second one is the trim loss problem addressing the issue of how to cut out the small items from the given large objects in such a way that wastage material will be minimized (Karelahti, 2002).
MATERIALS AND METHODS
Related works: The Cutting Stock Problem has two difficulties:
| • | Automatic generation of high quality cutting patterns. |
| • | The number of cutting patterns which increases exponentially with the number of entities to place. |
The use of Meta-heuristics (Tabu search, Simulated annealing, Genetic algorithms …) usually generates faster an acceptable solution. But the solution quality depends essentially of the quality of generated cutting patterns. The case of guillotine cutting has been widely studied by Benhamamouch (1979), Zissimopoulos (1984), Zennaki (1998) and Black (2005). However current industries use more sophisticated cutting tools which can perform a non-guillotine cutting.
Guillotine and non-guillotine cuttings are illustrated in Fig. 1. Hereafter, Gray areas represent trim loss.
It’s clear that the amount of generated guillotine cutting patterns is lower than those generated by non-guillotine cutting. In this study we are interested by generating higher quality of non-guillotine cutting patterns by using difference process approach.
| Fig. 1: | Guillotine and non-guillotine cutting |
| Fig. 2: | Difference process approach |
Trim loss problem
Bottom left: We can assimilate this algorithm to the well known Tetrice game (Leung et al., 1997). First, the form is placed in the right superior coin of the gross proceeds. Next the form is moved as possible to the bottom, then as possible to the left. These moves are repeated until obtaining a stationary state (i.e., the form can’t move). This algorithm has been improved by Liu and Teng (1999) by including rotation of forms.
Best fit: The best fit algorithm is inspired from the techniques used in operating system (Leung et al., 1997). A list called loss is updated in order to contain the losses in the actual pattern cutting. The best fit (i.e., the smallest loss) in this list is chosen when a candidate form is to be placed.
Difference process: The main drawback of the precedent approaches is that they can only deliver guillotine cutting patterns. The D.P. algorithm is different in the way that we consider all the available space in the gross proceeds (Liu and Teng, 1999) and can consequently deliver non-guillotine cutting pattern.
The loss in the cutting pattern (Fig. 2) is viewed as a set of 5 losses (the largest rectangular spaces). After placing a form, the spaces must be re-calculated. Thus, the obtained cutting patterns are better than those obtained by bottom-left or best-fit algorithms and are furthermore non-guillotine.
DIFFERENCE PROCESS ALGORITHM
Representation of cutting pattern: We represent a cutting pattern on a gross proceeds (L, H) in a orthogonal reference (O, X, Y). Thus each form (li, hi) is represented by its coordinates (x, y) as shown in Fig. 3.
Localisation: The first part of our algorithm is the localisation of all potential points in which we can place the next form. First, we consider the horizontal (BH = {bhi}) and the vertical (BV = {bvi}) bands of the current cutting pattern, then we determine the potential points in each band, respectively named EMPLBH and EMPLBV (Fig. 4).
Initially the single potential point is (0,0), i.e.,
The cutting pattern is represented by the array ACT:
Horizontal and vertical bands are respectively:
| Fig. 3: | Representation of cutting patterns |
| Fig. 4: | Localisation of potential points |
| Fig. 5: | Example of D.P cutting pattern. Represented by ACT |
| Fig. 6: | Illustration of Step 1 |
The element bhi = H (respectively bvi = L) is eliminated from BH (respectively BV).
The determination of potential points EMPLBH and EMPLBV is realised in two steps.
Step 1: Determination of all potential points (possible and impossible).
For each horizontal band bhi:
| • | Search element of ACT such as y = bhi with greatest value of x. |
| • | If such element exist (li, hi) then add the point (x+li, bhi) to EMPLBH. |
| • | Else add the point (0, bhi). |
For each vertical band bvi:
| • | Search element of ACT such as x = bvi with greatest value of y. |
| • | If such element exist (li, hi) then add the point (bvi, y + hi) to EMPLBV. |
| • | Else add the point (bvi, 0). |
Example: Consider the cutting pattern (L, H) = (11, 6) as shown in (Fig. 5).
The horizontal and vertical bands are:
After execution of step 1, the potential points obtained are shown in Fig. 6.
Step 2: Pre-test of potential points (Test before placement of the form). This step is a correction of Step 1 which can give some wrong points.
A point (a, b) is wrong if: ∃ [(x,y), (li,hi)] ∈ ACT such as: x≤a<x+li and y≤b<y+hi
The correction of wrong points is detailed as follows:
| Fig. 7: | Illustration of Step 2 |
| Fig. 8: | Localisation of potential points |
| Fig. 9: | Placement of form (4,3) |
| Fig. 10: | Post-test |
The correction of wrong points in the previous example give results as shown in Fig. 7.
At the end of this step we set EMPL = EMPLBH U
EMPLBV
Thus EMPL = { (7,0) (6,2) (10,3) (3,4.5) (0,5) (4,4.5) (10,0) }
Remark: The points (10, 3) and (4, 4.5) are useful for the second part of our algorithm but ignored in the final (Fig. 8)
Placement of the form: After localisation of potential points (EMPL), we continue the test by trying the placement of the form in each potential point. For that, two tests are realised:
Overflow test: This test eliminates potential points which cause overflowing. Let take the case of disposing the form (4,3) in the following cutting pattern (Fig. 9).
The set of potential points is EMPL = {(0, 5) (7, 0) (3, 4.5) (6, 2) (4, 4.5) (10, 0) (10, 3)}
While trying to place the form in each point, we obtain:
Thus the set EMPL become {(7, 0) (6, 2)}.
Post-test: We do this test in order to eliminate wrong points which appear after placement of the form. In the precedent example, it’s impossible to place the form (4,3) at the point (6,2) even if it doesn’t cause overflowing. To move away these kinds of points, the Post-Test consist to look through the vertical and horizontal bands (Fig. 10).
The potential point (6,2) is eliminated by the Post-Test because of horizontal band BH3 (EMPLBH3 = (10,3)). The post-test is realised as follows:
Let (X, Y) a potential point to be tested,
Test BVsupRESULTS AND DISCUSSION
The results confirm the high quality of cutting patterns. Furthermore, no constraint in the cutting process is imposed (Non-guillotine). This is illustrated in the following example:
Example: Let dispose the following forms in a gross proceeds (L, H) = (15, 7)
The placement of the 3 first forms lead to the cutting pattern as shown in Fig. 11.
At this stage, our algorithm give 3 potential points:
| EMPL | = | {(4, 3) (4, 6) (9, 6)} |
While disposing the last form (11, 1) we have:
| • | (4, 3) is wrong because of BVsup = 9. |
| • | (9, 6) cause overflowing. |
| • | (4, 6) is correct. This leads to the cutting patterns which cannot be obtain with a guillotine cutting process (Fig. 12). |
| Fig. 11: | Current cutting pattern |
| Fig. 12: | Non-guillotine cutting pattern |
CONCLUSIONS
The automatic generation of non-guillotine cutting patterns has been our principal goal. The proposed algorithm can give high quality solutions in the case of 2-dimension rectangular forms. We will extend our work to an efficient heuristic which can generate a sufficient number of non-guillotine cutting patterns for solving the CSP problem.