Informatica 20 (1996) 211-221 211 Optimization of One Dimensional Cutting in Clothing Industry Miro Gradišar and Jože Jesenko University of Maribor, Faculty of Organizational Sciences, 64000 Kranj, Prešernova ulica 11, Slovenia Phone: +386 64 222 804, Fax: +386 64 221 424 Keywords: cutting, optimisation, heuristics, clothing industry Edited by: Rudi Murn Received: September 21, 1995 Revised: December 20, 1995 Accepted: April 11, 1996 The article examines the procedure for optimisation of roll cutting in the clothing industry. The issue of roll cutting can be defined as a bicriterial multidimensional knapsack problem with side constraints. In general one may not find an optimal solution within reasonable time limits. For this reason we have found a solution through a combination of approximation and heuristics. On the basis of the achieved algorithm the computer program COLA has been developed. The article presents an example of the implementation of the program. 1 Introduction The first phase of a technological process in a number of industrial branches is cutting stock which has been obtained from warehouses. This often results in incurring trim loss which is generally unwanted. The most straightforward type of cutting is one-dimensional which can be defined as guillotine cutting of a small number of long pieces into a large number of short pieces. The problem of reducing trim loss at one-dimensional stock cutting can be observed in various branches of industry (Ferreira et al. 1990, Stadtler 1990). In the clothing industry it arises as the problem of optimal utilisation of stock at roll cutting into pattern shapes. A pattern shape consists of pattern parts which make up a piece of clothing. It is rectangular and usually drawn on paper. The width of the rectangle equals the width of fabric rolls. The width of a fabric roll is standardized and generally remains the same within one customer order. The length of the rectangle depends on the number and the size of pattern parts which make up a piece of clothing. Pattern parts such as a trouser leg, a sleeve, a pocket etc., are generally of irregular shape. They are placed on a rectangular surface in such a way that there are the fewest possible unutilized parts of the surface as well as making pattern shape as short as possible. A particular item of clothing can be produced in large series which consist of a number of groups of the same products. Groups differ, according to size numbers, colours and fabric. As there is a great number of different types of pattern parts of various sizes, to have only one pattern shape would mean that it would be too long. Therefore, it is necessary to make several pattern shapes for a particular item of clothing within the framework of one order. The number of different pattern shapes generally ranges from three to eight. Obtained pattern shapes of various lengths (hereinafter referred to as order lengths) need to be cut into a number of required pieces by guillotine cuts out of fabric rolls as illustrated in Figure 1. Cutting order lengths is determined by two features. First, the width of a stock roll equals the width of the order length. Second, the length of the cut piece is the same as the order length. The roll lengths usually range between 10 - 100 metres, whereas order lengths are mainly up to 5 metres long. Most commonly, 10 to 50 pieces of a particular order length are required. Our objective is to create a plan of roll cutting by finding such a combination of individual order lengths within a certain number of pieces in each roll that will minimise the overall trim loss. However, in practice fabric is often cut without a plan. 212 Informatica 20 (1996) 211-221 M. Gradisar et al. Stock of large lenghts - 3 different lenghts 1 H Orders for small lenghts - 4 different order lenghts in the necessary number ofpieces □ □ □ □ □ □ 1 2 3 Cutting without a plan ] □ 4 ■ I i r Trim . loss II Unfulfilled order: | 11 | Cutting according to a plan ■ LI 3 t Order requirements are fully met Figure 1: Stock cutting Creating a plan for optimal one-dimensional roll cutting with respect to trim loss belongs to the group of the so called NP complete problems which can not be solved in real life because of their great complexity in terms of place and time. However, it is possible to find a sub-optimal heuristic solution by designing a computer program which generally surpasses human capabilities and reformulates a poorly structured cutting problem into a completely structured one. In this case, full computerisation is feasible and justified. The human role is restricted to the input of data and setting parameters. This article describes the mathematical model of the cutting problem, solution development in the form of computer program, and an example of the practical implementation of the program. 2 Problem Description and a Formal Model The problem of optimization of roll cutting in the clothing industry exists within the framework of a particular customer order for which there is a certain number of rolls differing in length, fabric and colour. Each customer order is planned for individually. The following notation is used: m number of rolls, d number of different colours, e number of types of fabric, djk/ roll lengths; j = 1,..., m; k € {1,..., d}; /€{!,.•■, e}. We need a certain number of order lengths which consist of a particular number of pieces. The fabric and colours are the same as in rolls. We can denote the following: n number of varying order lengths, Si order lengths; i — 1,..., n, bikf Required number of pieces which are determined by length i, color k, and fabric /; i = 1,... ,n; k = 1,..., d; / = 1,..., e. Every kf combination represent independent cutting problem, so we can omit indexes k and / in further description. We want to obtain: 'ij number of pieces which are defined by order length i having been cut from roll j under the following conditions: (1) minA minimize number of uncut order lengths, distribute evenly; (2) min ZT=1tj minimize trim loss which is smaller than UB s.t. (3) £?=i si Xij + Sj = dj Vj knapsack constraints; (4) E;n=1 xl3 > bi - A Vi demand constraints; (5)£?=1^<4 Vj maximum number of different order lengths for a roll; 8j> 0 tj > 0 (6). x^ > 0, integer Vz, j Vj V; A > 0 ^€{0,1} Vz, j ^•€{0,1} Vj ^€{0,1} Vj OPTIMIZATION OF ONE DIMENSIONAL CUTTING. For the above model the following functions are used: = f 0 if xij = 0 Vi 3 1 1 otherwise to indicate whether roll j is used in the cutting plan, _ f 0 if x^ = 0 ^ 1 1 otherwise to indicate whether order length i is cut from roll j and t _ / 6j if Zj = 1 A 6j < UB 3 | 0 otherwise. tj indicates the extent of the trim loss relating to roll j. Data: UB upper bound for the trim loss - it can be set e.g. to the smallest or longest order length. At roll cutting, it is necessary to pay attention to two limitations which arise from the practical conditions in clothing industry. The first one is related to the requirement that in the case of material shortage the lack of fabric should be evenly distributed among the order lengths. If the shortage had been accumulated with one order length this would cause deficit in clothes of one or two size groups. This would in turn bring about difficulties in sales. The second limitation refers to the fact that the number of different order lengths which are cut out of one roll can be maximally four. The model makes a distinction between two groups of unutilized parts of rolls. First, there are unutilized parts which are long enough to be used again even though the requirements of the order have been met. Second, there are unutilized parts which are too short to be used again. Hence, unutilized roll length which could be used further is not considered to be trim loss. We are addressing the issue of defining which unutilized length is so short that it could be referred to as trim loss. The answer depends on the quantity of available fabric. Overall trim loss can be defined in two ways: 1. Overall trim loss is the sum of those trim losses in particular rolls which are shorter than the shortest order length. Informática 20 (1996) 211-221 213 2. Overall trim loss is the sum of those trim losses in particular rolls which are shorter than the longest order length. In the cases when there is enough required fabric available we refer to definition 1, whereas in other cases we refer to definition 2. If definition 1 was referred to in both cases this would - in cases of shortage of fabric - give rise to the following problem. As the aim of the algorithm is minimization of the overall trim loss, this could lead to unfulfilled requirements for the longest order lengths, although the overall trim loss would be small and even though the aim would be achieved according to the logic of the algorithm. The trim losses which would be longer than the shortest order length but shorter than the longest order lengths could remain unutilized. The residual length which is larger than a certain lower bound (e.g. longest order length) is not considered as a trim loss. If there are sufficient rolls available, then there will be cutting plans with "no trim loss" but ever growing stocks. To prevent this an aditional condition must be set: only one residual length may be longer than the longest order length. 3 Solution Development The authors have not come across an algorithm in literature which would be directly applicable to the described situation. Similar problems are solved by heuristic algorithms. A similar kind of problem is the classical "bin packing problem", which can be solved by the "First Fit Decreasing" (FFD) (Coffman et al. 1984) heuristic procedure. However, the basic feature of this type of problem is that all stock lengths are the same. The literature abounds in solutions to problems of a similar kind based on a hybrid algorithm, which was developed by Gilmore and Gomory (Gilmore and Gomory 1961, 1963). The implementation of this algorithm would also be feasible in our case if all rolls were of the same length, as described in Stadtler 1990, or of the few standard lengths, as described in Gilmore and Gomory 1961. An extensive review of the relevant literature up to 1992 is given in Sweeney and Paternoster 1992, while a review of different types of problems and solution methods related to reducing trim loss is given in Dyckhoff 1990. 214 Informatica 20 (1996) 211-221 M. Gradisar et al. The cutting model we described could be termed a bicriterial multidimensional knapsack problem with side constraints. To handle the bicriterial objective function a lexicographic approach is proposed. In general one may not find an optimal solution within reasonable time limits. The algorithm which would check all possible cutting patterns while taking into account all rolls of generally different lengths would provide solution without unnecessary trim loss and would have exponential time complexity. A basic simplification which was used to transform this exact algorithm into an approximate one with polynomial complexity is the limitation of processing one roll at a time. The algorithm was developed on a step by step basis. The number of basic steps equals the number of rolls necessary for fulfilment of an order. At the beginning, all rolls belong to the set of unprocessed rolls. The set of processed rolls is empty. At each step, the set of unprocessed rolls is reduced by one and the set of processed rolls increases by one. Also, the number of cut pieces of particular order lengths changes, as well as the length of the processed roll, which becomes equal to trim loss. While developing the algorithm, we had to address two basic questions. First, which roll is to be chosen from the set of the not yet processed rolls and second, which order lengths are to be cut out of it. The algorithm was developed in such a way that it is based on the following assumptions: 1. It is easier to find a good solution referring to one roll provided it is selected from the largest possible set of different rolls. 2. It is easier to find a good solution for the selected roll provided it is selected from the largest possible set of feasible solutions. This happens in case when: a) the roll is as long as possible, b) the ordered lengths are as short as possible, c) the number of different order lengths and the number of pieces is as large as possible. All the assumptions are statistically proven and this is shown by the analysis described in section 5. However, we cannot be completely sure that the assumptions are valid in each individual case. The issue of roll selection can be tackled in accordance with the assumption 1 by calculating the solutions for all unprocessed rolls and selecting among them the one with the lowest trim loss. As it is possible that more rolls have the lowest trim loss, we apply the 2.a assumption and choose the shortest roll. This can be achieved by the initial arranging of the rolls according to increasing lengths. By doing so, the longer rolls will be processed later when the conditions become more difficult due to the first assumption. The remaining question to be dealt with is the selection of order lengths. According to condition (5) the number of order lengths cut up from the same roll is limited by a parameter whose value can be 1, 2, 3 or 4. Consistent with the assumption 2.c and the condition (1) stipulating that the possible trim loss should be distributed among order lengths as evenly as possible, we select those order lengths which consist of the largest number of pieces. This can be achieved by arranging the order lengths according to the decreasing number of pieces. This selection does not take into consideration the assumption 2.b, nevertheless, due to the condition (1) there is no other choice. For this reason this solution is reached only in case when there is not enough fabric. When there is abundance of fabric we face a dilemma while selecting the order lengths, as to what assumption should be given priority - either assumption 2.b or 2.c. The dilemma can be resolved by developing three algorithmic variants and selecting the best result. The first variant is the same as the one which is applied when there is not enough fabric. The second variant is based on assumption 2.b. We select those order lengths which are the longest. This is achieved by arranging order lengths according to decreasing lengths. This means that shorter order lengths are processed later, i.e., when there is less room for manoeuvre and according to assumption 1 the cutting problem is becoming more complicated. The third variant is a compromise between assumptions 2.b and 2.c. Order lengths are chosen from the arrangement which is made according to the decreasing value of the product obtained by multiplying order lengths by the number of necessary pieces. OPTIMIZATION OF ONE DIMENSIONAL CUTTING. Informática 20 (1996) 211-221 215 The decision to deal with each case separately, whether or not there is a shortage or abundance of fabric, stems from the definition of the overall trim loss within the framework of a customer order, the latter being different in both cases. Due to the nature of fabric the order lengths are defined precisely up to 1 cm, and the roll lengths up to 1 dm. Because of that all lengths can be expressed in centimetres and we refer fully to integer problem. The loss of fabric incurred due to a certain cut width can be compensated by lengthening all order lengths by 2 cm. The algorithm for the optimisation of roll cutting for the needs of the clothing industry is shown in Figure 2 by a flowchart of basic steps. The creation of a cutting plan is repeated for each combination k and /. 4 Program COLA The proposed algorithm was formulated in FORTRAN program language, as it is relatively fast at carrying out numerical operations. The program consists of 2,000 lines. The data input and the printout of the results were made in 4GL, as it is the most suitable for this purpose. The program can be run on a personal computer and it enables the achievement of 0.1% of the average planned trim loss per order. It was called COLA (Computerized LAying out). COLA program has been used in industry for about 10 years. The most recent and significant changes were made in 1994. The program is being used by several clothing manufacturers and has been used the longest by Modena. The program is used to process an order in sequence of the following 3 stages: — data input, — creation of a cutting plan, — printout of results. 4.1 Data input Data input is carried out in three stages. First, setting parameters, second, input of details about order lengths, and third, input of details about rolls of fabric. The parameters of an order are as follows: — reference number of the order, — short description of the order, — programmed trim loss: - fixed part, - variable part, — maximum number of different order lengths for cutting a roll of fabric. The fixed part of the programmed trim loss is entered in centimetres and means that there will remain at least that much fabric in each roll. The common value of this parameter is 0. It has been observed that rolls of some manufacturers tend to contain somewhat less fabric than declared. This discrepancy can be taken into account by setting the programmed trim loss. Second possibility of the use of this parameter can apply to cases when we want to have certain trim loss in each roll because we want to use it later on. When we want each roll to have trim loss which is in proportion to the roll length, we have to enter the required percentage as the variable part of the programmed trim loss. The fixed and variable part are not mutually exclusive. A parameter of great importance is the number of different order lengths which are cut out from a particular roll. A higher number means on the one hand more possible combinations and less trim loss. On the other hand, the cutting procedure at higher numbers becomes more complex and more time consuming. It has been experienced in practice that the highest reasonable number of different order lengths combined in a roll is four. At number 4 the trim loss becomes so low, that any further reduction would not outweigh the extra efforts at cutting. Possible values of this parameter range from 1 to 4, we usually select 3 or 4. A customer order normally consists of a few order lengths. An individual order length can be of different colours and fabrics. It can be determined by the following details: — the reference number of the order length, — the order length given in centimetres, — size numbers of ready-made clothes, which are taken account of in order lengths. 216 Informatica 20 (1996) 211-221 M. Gradisar et al. C start ) _QpO (filter the set of rolls according to k and f ) (sort the rolls according to djkf ) (filter the set of order lenghts according to k and f (sort order lenght according to bj^f ( select order lenghts select and cut the roll with the lowest trim lpss according to all possible combinations of selected order lenghts C st°P ) C cutting plan=T2) (overall trim loss—'T1 e- ( T2=cutting plan *) CT1=T3 ) T (sort order lenght according to bju ) ( select order lenghts ) 1 with the. lowest ' select and cut trim lpss according to combinations of set (calculation of the overall tnm loss ) (Tl=overall trim loss } (T2~cuttmp plan ") (set to the start ) Jt (sort order lenghts according to sj | select order lenghts | select and cut the roll with the. lowest trim lpss according to all possible combinations of selected order lenghts ( change roil lenght ) ( change the number of cut pieces ( calculation c overall trim loss D C T1=T3~) (T2=cutting plan ) (set to the start j ( sort order lenghts according to s j * bikf) ( select order lenghts-") select and cut the roll with the lowest trim lpss according to all possible combinations of selected order lenghts (change roll lenght (change the number of cut pieces ) ( calculation of the overall tnm loss (T3—overall trim loss ) T1 >T3 yes Figure 2: Flowchart of the cutting algorithm OPTIMIZATION OF ONE DIMENSIONAL CUTTING. Informática 20 (1996) 211-221 217 OPTIMIZATION OF CUTTING date: 05-24-94 customer order: 635 model: jacket DETAILS ABOUT ORDER LENGHTS No. order lenght lenght size numbers pieces colour fabric 1 1 239 74 80 86 92 140 6449 BL-72 2 1 239 74 80 86 92 145 7209 BL-100 3 2 188 80 86 92 55 6449 BL-72 4 2 188 80 86 92 35 7209 BL-100 5 3 134 86 92 25 6449 BL-72 6 3 134 86 92 30 7209 BL-100 DETAILS ABOUT ROLLS No. roll lenght colour fabric 1 15 10280 6449 BL-72 2 16 10220 6449 BL-72 3 17 10160 6449 BL-72 4 19 10180 6449 BL-72 5 20 10100 6449 BL-72 6 9 10200 7209 BL-100 7 10 10790 7209 BL-100 8 11 10100 7209 BL-100 9 13 10070 7209 BL-100 10 14 900 7209 BL-100 11 12 3000 7209 BL-100 RESULTS ARRANGED ACCORDING TO ORDER LENGHTS order lenght pieces correction roll color fabric foll.o.l. size numbers 1 32 15 6449 BL-72 2 74 80 86 92 1 34 16 6449 BL-72 2 74 80 86 92 1 36 17 6449 BL-72 2 74 80 86 92 1 28 19 6449 BL-72 2 74 80 86 92 1 10 20 6449 BL-72 2 74 80 86 92 1 30 9 7209 BL-100 2 74 80 86 92 1 42 10 7209 BL-100 2 74 80 86 92 1 28 n 7209 BL-100 2 74 80 86 92 1 40 13 7209 BL-100 2 74 80 86 92 1 4 12 7209 BL-100 2 74 80 86 92 2 14 15 6449 BL-72 0 80 86 92 2 9 16 6449 BL-72 3 80 86 92 2 4 17 6449 BL-72 3 80 86 92 2 10 19 6449 BL-72 3 80 86 92 2 18 20 6449 BL-72 3 80 86 92 2 4 9 7209 BL-100 3 80 86 92 2 4 10 7209 BL-100 0 80 86 92 2 11 11 7209 BL-100 3 80 86 92 2 2 13 7209 BL-100 3 80 86 92 2 4 14 7209 BL-100 3 80 86 92 2 10 12 7209 BL-100 3 80 86 92 3 3 16 6449 BL-72 0 86 92 3 6 17 6449 BL-72 0 86 92 3 12 19 6449 BL72 0 86 92 3 4 20 6449 BL-72 0 86 92 3 17 9 7209 BL-100 0 86 92 3 10 11 7209 BL-100 0 86 92 3 1 13 7209 BL-100 0 86 92 3 1 14 7209 BL-100 0 86 92 3 1 12 7209 BL-100 0 86 92 TRIM LOSS UTILIZED ROLLS roll trim loss colour fabric 15 0 6449 BL-72 16 0 6449 BL-72 17 0 6449 BL-72 19 0 6449 BL-72 20 3790 6449 BL-72 9 0 7209 BL-100 10 0 7209 BL-100 11 0 7209 BL-100 13 0 7209 BL-100 14 14 7209 BL-100 12 30 7209 BL-100 UNUTILIZED ROLLS roll lenght colour fabric OVERALL TRIM LOSS..................................................: 44 cm (0,0512%) PROGRAMMED TRIM LOSS - fixed..............................: 0 cm PROGRAMMED TRIM LOSS - variable..........................: 0% OVERALL TRIM LOSS WITHOUT OPTIMIZATION...: 1074 cm (1,2508%) SAVING OF STOCK........................................................: 103 0 cm (1,1996%) Figure 3: Example of the COLA program printout 218 Informatica 20 (1996) 211-221 M. Gradisar et al. For each combination of the colour and fabric it is necessary to feed in three more items of information : — colour reference number, — fabric reference number, — the number of necessary pieces. In addition, we need information about the rolls. Each roll is determined by the following details: — the roll reference number, — the length of the roll in centimetres, — colour reference number, — fabric reference number. The information about the width of rolls and order lengths is not significant, because we assume that the widths of order lengths and rolls match. 4.2 Creation of a cutting plan and calculation of statistics The program operates at great speed. Creating a cutting plan and the calculation of statistics for an extensive order consisting of 50 rolls and 1000 pattern pieces takes less than 10 seconds on a personal computer (486DX4, 100MHz). The time spent on creating the plan is negligible. This is especially evident when we compare it to the manual laying out for orders of average size, which can take about four to eight hours. The speed enables the users to carry out a "what-if' analysis by changing the parameters of the order. For instance, a possible question could refer as to what extent the result would be worse if we cut only two different order lengths out of one roll. 4.3 Printout of results After the final calculation, the results are displayed on the VDU where they can first be checked and then printed out on paper. They can be printed out completely or partially, depending on the parameter which is used to set the printout variant. The longest variant contains 10 or 20 pages. The printout consists of the following four basic headings: - details about order lengths and rolls, - plan of roll cutting, - trim loss, - statistics. The plan of roll cutting is presented in a table form. The three most important columns are: the order length reference number (order length), the number of pieces (pieces) and the roll reference number (roll). Therefore, each line provides information as to which order length is to be cut and out of which roll. The trim loss is generally the smallest if the roll contains more fabric than necessary. In such a case some rolls are not utilized at all, whereas others are not cut up to the end. If the remaining part is longer than or the same length as the shortest order length, it cannot be considered a trim loss. The trim loss is higher when all rolls are used and there is approximately as much fabric as we need or less. In the case that there is shortage of fabric, the program operates in accordance with the condition (1) in such a way that it distributes the loss to approximately the same number of pieces to all order lengths. The statistics which follow are very straightforward. The program calculates the differences between the required and the obtained values and sums them up according to order lengths, colours and size numbers. Finally, it calculates the overall trim loss as well as the average overall trim loss which could be incurred without laying out. The difference is a saving. Further details are shown by the example of results given in Figure 4. Statistics have been left out. The example shown in Figure 3 contains real data, however, the customer order related to is rather small, containing only three different order lengths and only 11 rolls in two colours and two fabrics. The devised cutting plan assumes complete cutting of 10 rolls and partial cutting of 1 roll. The anticipated trim loss is only 44 cm, which makes 0.05% of total length. The saving of the fabric in this order is 10 metres. To clarify the printout of results, some further explanations need to be provided. The column "the following order length" (foll.o.l.) contains order length reference numbers which are about to be cut from the rolls given in the column "rolls". OPTIMIZATION OF ONE DIMENSIONAL CUTTING. Informática 20 (1996) 211-221 219 32,52- trimloss(%) 1,510,50- without manual computerised laying out laying out laying out Figure 4: Dependence of trim loss on the type of laying out This item of information is helpful to the worker dealing with the rolls at the placing machine. The column "size numbers" refers to the size numbers of ready-made clothes, whose pieces make up a particular order length. Size numbers do not affect the creation of a cutting plan. They are added only to provide records and statistics. The "corrections" column contains possible deviations between the planned and actually cut number of pieces. 5 Factors Affecting Utilization of Stock Computerized creation of a cutting plan or computerized laying out leads to less than one percent of trim loss. Without laying out the trim loss accounts for three percent. In industry manual laying out is also used. The results of manual laying out largely depend on individual skills and experience of a particular worker. Average amount of trim loss depending on the manner of laying out is shown in Figure 4. Factors affecting the amount of stock savings are as follows: — the average roll length, — the average order length, - the average difference between the longest and the shortest order length in a particular customer order, - the number of different order lengths cut out of the same roll. 0,5 -■ 0,45 -0,4 -0,35 -trim loss 0,3 - (%) 0,25 -0,2 -■ 0,15 -■ 04 -0,05 - 0 -1-1-1-1-1 0 10 20 30 40 50 average number of pieces cut out of a roll Figure 5: Dependence of the trim loss on the average number of pieces cut out of a roll The influence of the above factors has been analysed by calculating a large number of fictitious orders with different values of particular factors and obtaining the average values of trim loss. The value of a particular factor has been tested in 50 to 250 cases. Although we have generated orders randomly, the values remained within the limits which are typical of the clothing industry. Average roll length and average order length determine the average number of pieces cut out of each roll. The higher the number the more room there is for manoeuvre when seeking the optimal combination as well as the better result and respective utilization of the fabric is the best. Very good results can be achieved if we have more than 20 pieces. Figure 5 shows the conditions. Figure 6 shows the dependence of the trim loss on the average difference between the longest and the shortest order length of a customer order expressed as a percentage. It can be observed that 10 to 20% of difference can suffice for the optimal utilization of fabric. A crucial factor which is set as a parameter of the program is the number of different order lengths cut out of a roll. A higher number means more possible combinations and, therefore, also lower trim loss. Analysis shows that in case of a combination of two order lengths in a roll the average trim loss accounts for 0.165%. In combinations of three the average trim loss is reduced to 0.101%. 220 Informatica 20 (1996) 211-221 M. Gradisar et al. differences in order lenghts (%) Figure 6: Dependence of trim loss on differences in order lengths 12 3 4 number of different order lenghts cut out of the same roll Figure 7: Dependence of trim loss on the number of different order lengths cut out of the same roll In the combinations of four the average trim loss is 0.082%. It is noteworthy that even when cutting only one order length out of a roll as in the case of the traditional procedure without laying out, implementing the COLA program can lead to reductions of the trim loss of up to 70%. This can be achieved by merely placing the rolls about to be cut into a sequential arrangement proposed in the program as shown in Figure 7. We have carried out an analysis of 200 randomly generated samples, containing factors with values which are favourable, common in real life and have an affect on trim loss. This means that the average number of pieces which were cut from a roll was approximately 30. The order lengths differed by approximately 40%. The number of different order lengths which were cut out of a roll was 4. In 100 cases there was about 5% shor- tage of fabric, in other 100 cases there was about 5% surplus. We have obtained the following results: In the first 100 cases the average trim loss was 0.03% and it was 0.17% in the worst case. In other 100 cases the average trim loss was 0.01% and it was 0.06% in the worst case. In 98 out of first 100 cases the sum of all trim losses was lower than the shortest order length. This means that we have certainly found an optimal solution. In the remaining 100 cases all solutions were optimal. 6 Conclusion The issue of roll cutting in clothing industry is essentially a bicriterial multidimensional knapsack problem with side constraints. In general one may not find an optimal solution within reasonable time limits. For this reason we have found a solution through combination of approximation and heuristics. The result is the COLA program which facilitates a reduction in trim loss on average by 0.1%. Processing an average customer order takes less than 10 seconds when using the COLA program. The speed is of utmost importance in those cases when there should be the shortest possible lapse of time between the point of receiving the fabric in the warehouse and processing of the order. References [1] Coffman Jr., E.G., Garey, M.R., and Johnson, D.S.(1984): Approximation algorithms for bin packing - An updated survey, in: Ausiello G., Lucertini M., and Serafini P. (eds.), Algorithm Design for Computer Systems Design, Springer-Verlag, New York, 49-106. [2] Dyckhoff, H.(1990): A typology of cutting and packing problems, European Journal of Operational Research 44/2, 145-159. [3] Ferreira, J.S., Neves, M.A., and Fonseca, P.(1990): A two-phase roll cutting problem, European Journal of Operational Research 44/2, 185-196. [4] Gilmore, P.C., and Gomory, R.E.(1961): A linear programming approach to the cutting stock problem, Operations Research 9, 849-859. OPTIMIZATION OF ONE DIMENSIONAL CUTTING. Informática 20 (1996) 211-221 221 [5] Gilmore, P.C., and Gomory, R.E.(1963): A linear programming approach to the cutting stock problem, Part II, Operations Research 11, 863-888. [6] Stadtler, H.(1990): A one-dimensional cutting stock problem in the aluminium industry and its solution, European Journal of Operational Research 44/2, 209-223. [7] Sweeney, P.E., and Paternoster, E.R.(1992): Cutting and packing problems: A Categorised, Application-Orientated Research Bibliography, Journal of the Operational Research Society 43/7, 691-706.