Real Time Multiple-Grade Cutting Stock Optimization Using Adaptive Fuzzy and Recursive Algorithms by Reza Ghodsi B . S c , Sharif University o f Technology, 1989 M . Sc., University of Calgary, 1998 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY in THE FACULTY OF GRADUATE STUDIES Department of Mechanical Engineering We accept this thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA July 2004 © Reza Ghodsi, 2004 ABSTRACT In the production of commodities there exist many instances of cutting processes whereby decisions have to be made on how the cuts can be performed optimally. In other words, the question arises that " in what sequence should cutting o f a workpiece into smaller items be conducted so that the raw material used is minimized?" This is often synonymous to generating the "minimum waste". In its simplest form, this is referred to as the Classical One-dimensional Cutting Stock Problem or Classical 1D-CSP, for which very effective solutions for static off-line cases exist. The 1D-CSP is present in such industries as steel, apparel, paper, wood and food. A cut sequence is commonly referred to as a pattern. A n investigation into 1D-CSP reveals that many patterns or combinations must be evaluated before an optimal solution is found. Further, the number of such combinations dramatically rises with the number of problem parameters and operational features, making the solution computationally extensive. For this reason, beyond the classical 1D-CSP and in particular when real time online applications are involved, developing practical optimization solutions is a major challenge. In a high volume wood product manufacturing plant encountered in this research, a major production phase involves online inspection o f wood strips, for removing defects and quality grading, and subsequent chopping of the useful pieces to build up the inventory needed for the product on orders received. Specifically, the production line is to use wood as a defect-sensitive raw material, make decisions one strip at a time, deal with all non-identical pieces, use multiple grades of wood, cut strips to pieces, and at the same time satisfy objectives such as meeting customer due dates and generating least waste. This turns out to be is a complex case of dynamic 1D-CSP and a new solution approach needs to be instigated. In this work, in an attempt to develop an effective optimization tool, a mathematical formulation for an exact solution with multiple material grades is derived and it is demonstrated that even for small problems the computational times are prohibitive for online applications. Hence, an adaptive fuzzy algorithm is developed and tested which is able to produce results comparable to the exact solution for C S P . This fuzzy algorithm is then integrated with an innovative recursive pattern generation module into an optimization algorithm for real time problem. The combined optimization structure is examined with various objective functions, constraints and input data, and results are discussed. It is concluded that the developed optimization approach has an excellent performance and can adapt itself to extreme variations in raw material quality and most of all is applicable to real time decision-making. Hi Table of Contents Abstract ••• " Table of Contents *v List of Figures vii List of Tables w Acknowledgements x 1 Introduction 1 1.1 Background 1 1.2 Manufacturing Processes 3 1.3 Problem Discussion 9 1.4 Motivation, Objectives and Limitation of this Study 21 1.5 Organization of the Work 22 2 Problem Classification and Literature Survey 24 2.1 Classifying the Problem 24 2.2 Classical One-Dimensional Cutting Stock Problem 26 2.2.1 Solution of Classical 1D-CSP 28 2.3 Current Approaches and some Similar C S P 31 2.4 Concluding Remarks -. 37 3 Frequency Distributions of Industrial Data 38 3.1 Frequency Distributions of the Stock 38 3.2 Frequency Distribution o f the Demand 44 3.3 Concluding Remarks 45 4 Mathematical Analysis 46 4.1 Mathematical Formulation 46 4.2 Exact Solut ion. 5 3 4.2.1 The Exact Solution for a Small Example 5 4 4.2.2 The Program C P U Run Time 62 4.3 Size o f the Solution Space 64 4.3.1 Size without Kicker Limitation 65 4.3.2 Size with Kicker Limitation 68 4.4 Concluding Remarks 7 0 5 Classical 1D-CSP Optimization by Crisp and Fuzzy Ranking Methods q\ 5.1 Classical 1D-CSP Optimization Alori thm 72 5.2 Crisp 1 and 2 Methods 7 4 5.3 Fuzzy 1 and 2 Methods.. . . . 7 5 5.3.1 Notation and Definitions 76 5.3.2 Membership Functions for Fuzzy 1 7 7 5.3.3 Membership Functions for Fuzzy 2 gO 5.3.4 Inference Rules for Fuzzy 1 and Fuzzy 2 3 3 5.3.5 Defuzzification Method 3 4 5.4 Testing Crisp and Fuzzy Methods 3 4 5.5 Adaptive Fuzzy Ranking Method 3 7 5.5.1 Membership Functions for the Adaptive Fuzzy Method 3 3 5.5.2 Inferencing and Defuzzification for Adaptive Fuzzy. 9 0 5.6 Testing the Adaptive Fuzzy Method 91 5.7 Concluding Remarks 9 3 6 A Recursive Pattern Generator 9 4 6.1 A Recursive Algorithm for Cut Pattern Generation 9 4 6.2 Testing the Recursive Algorithm 101 6.3 Concluding Remarks 103 7 Real Time 1D-CSP Optimization 104 7.1 Optimization Algorithm - Fixed Cut Lists 105 7.1.1 Ranking the Cut List 106 7.2 Simulation Results 108 7.2.1 Simulation - without Ranking 109 7.2.2 Simulation - with Ranking H O 7.2.3 Comparison of Optimization with and without Ranking 111 7.3 Optimization Algorithm - Dynamic Cut Lists H 6 7.4 Optimization Algorithm - Prioritized Orders H 9 7.5 Concluding Remarks 123 8 Contributions, Conclusion and Future Research 124 8.1 Summary and Contributions 124 8.2 Conclusion 126 8.3 Future Research Directions 127 References 129 List of Figures Figure 1.1. Manufacturing processes. . . . 4 Figure 1.2. Lumber and strips 5 Figure 1.3. The defect and grade variation of a 3600 m m strip... . . 6 Figure 1.4. The pieces required to produce a table. 8 Figure 1.5. The grade pattern o f a clean piece 15 Figure 1.6. One cut pattern for the clean piece 16 Figure 1.7. Another cut pattern. 17 Figure 1.8. Another example for cut pattern. 17 Figure 2.1. Cutting and packing problems 25 Figure 2.2. Cutting paper ro l ls . . . . . 28 Figure 3.1. The distributions o f grade A sections . . . 40 Figure 3.2. The distributions of grade B sections 40 Figure 3.3. The distributions o f grade C sections 41 Figure 3.4. The distributions o f A B sections. 42 Figure 3.5. The distributions o f A C sections 42 Figure 3.6. The distributions o f B C sections 43 Figure 3.7. The distributions o f clean pieces u 43 Figure 3.8. The distribution o f some cut list lengths 44 Figure4.1. Four 3600 m m graded strips...... . 54 Figure 4.2. Infinite cut patterns 55 Figure 4.3. Four patterns to cut a 1800 m m grade C item from a 2400 m m clean piece. . . . . . . . 57 Figure 4.4. Five patterns for first clean piece •'. 57 Figure 4.5. The optimum solution for the small problem.. . . . . 60 Figure 4.6. Five types o f waste. 61 Figure 4.7. Program C P U run times for optimal solutions 63 Figure 5.1. Linguistic length and quantity classes for Fuzzy 1 79 Figure 5.2. Linguistic length and normalized quantity classes for Fuzzy 2 82 Figure 5.3. C P U usage for the classical 1D-CSP and AMPL®; 87 Figure 5.4. Adaptive Fuzzy length and quantity classes 90 Figure 6.1. A n example for recursive algorithm 96 Figure 6.2. A long clean piece 102 Figure 7.1. The decrease in cut waste 113 Figure 7.2. The decrease in total waste. 114 Figure 7.3. The changes in run time 115 Figure 7.4. Cut wastes of 12 sample sets with dynamic and fixed cut lists 118 Figure 7.5. Total wastes o f 12 sample sets with dynamic and fixed cut lists 118 List of Tables Table 1.1. A prioritized Order List 10 Table 1.2. Pieces needed for one unit o f "Dinner Table 1" 11 Table 1.3. Pieces needed for one unit of "Book Shelf 3" 11 Table 1.4. The aggregate cut list from Tables 1.1, 1.2, and 1.3 12 Table 1.5. A cut list with no order priority 14 Table 2.1. A cut list with no grades and order priorities 27 Table 4.1. A sample cut list. 54 Table 4.2. A n unbalanced cut list. 61 Table 4.3. C P U run times of sample problems 63 Table 5.1. Fuzzy Associated Map for Fuzzy 1 and 2 83 Table 5.2. Results of 12 cut list samples for four ranking methods 85 Table 5.3. Fuzzy Associative Map for the adaptive method 91 Table 5.4. Results for all five ranking methods 92 Table 6.1. Number o f combinations and run times for 14 sample sets 102 Table 7.1. A fixed cut list with no order priority 105 Table 7.2. The simulation results with no ranking 109 Table 7.3. The simulation results with ranking I l l Table 7.4. Comparison of optimization with and without ranking 112 Table 7.5. The simulation results for fixed and dynamic cut lists 117 Table 7.6. The aggregate cut lists with prioritized orders 119 Table 7.7. Simulation results using aggregate cut lists with prioritized orders . . . . . . . 122 Acknowledgements In God we trust First, and most of all , I wish to express my deepest appreciation and lasting gratitude to my supervisor, Dr. Farrokh Sassani for his professional guidance, valuable feedback, and support throughout this research. I would also like to thank Dr. Clarence de Silva, Dr. John Meech, and Dr. Taraneh Sowlati as the members of my thesis supervisory committee. M y thanks to the Department of Mechanical Engineering, the Faculty of Graduate Studies and The University o f British Columbia for their support during my enjoyable yet challenging studies. Furthermore, I am grateful to M r . Robert B i rd and other staff at Canwood Furniture Inc. for their help and cooperation in providing simulation data and in engaging very useful discussions. I deeply thank all members of my kind family for their support and encouragement, especially my parents for their constant prayers. M y special thanks and love go to my wife, Shiva, and my daughter, Anita, who showed patience and sacrificed a lot for me. There aren't enough words to thank them. M y wife's family was just as supportive and I thank them for this. M y friends and colleagues to name a few like M r . Reza Tafreshi and M r . Mohammad Mallakzadeh have all a share in this accomplishment. CHAPTER 1 Introduction This introductory chapter consists of five sections. A general background for the research work is provided in section 1.1. The manufacturing processes and the respective industrial setting where the subject of research was originated from are described in section 1.2. Next, in order to precisely define the research problem, a discussion of the different characteristics o f the problem is presented in section 1.3. The motivation, objectives and limitations o f this work are covered in section 1.4. Finally, in section 1.5 the organization of the remaining chapters of the thesis is outlined. 1.1 Background Furniture industries such as Canwood Furniture Inc. [1] or Palliser® [2] produce ready to assemble lacquered solid-wood products and ship them to customers all over the world. These companies produce an enormous variety o f products and practically accept orders of any size at any time. For example, Canwood Furniture Inc., where our visits and discussions lead to this research, produces over 180 different types and sizes of products such as tables, desks, beds, shelves, doors and windows. They purchase their raw material in the form of lumber from different sawmills that supply wood of different quality. Dealing with a highly defect-sensitive material like wood that plays a major role in the quality of the manufactured lacquered furniture, creates a very difficult and challenging task o f shop floor planning and decision making. One of the reasons for this level of difficulty is the fact that quality of the wood is not known prior to the needed primary cut-to-size process. This is in addition to the difficult jobshop scheduling problems common to many types o f manufacturing facilities. A t present, attempts to supervise and control the shop floor by conventional methods are not always successful. Despite best efforts, normally a wood waste o f over 15%, blocked stations, in progress inventory congestion and even stoppage of the production, delayed shipment, and rejecting new orders are common in these industries. If they do not, accept orders they lose revenue, and i f they do but are unable to deliver on time they face late penalties and possible loss of future orders. A n effective control over the manufacturing processes and production capabilities is therefore a very desired ability. The ultimate goal is to develop a decision support system that can be used to manage such a complex shop floor as a whole in real time with minimum waste and high output. The system should be capable of handling a very dynamic and uncertain environment using defect-sensitive material for production. To achieve this goal the overall problem needs to be broken down into smaller manageable problems. One of these problems, which is the subject o f this research, is minimizing the waste at the cutting process and trying to deliver the required pieces to the remainder of the shop floor based on the priority of the customer orders. This alone turns out to be a very complex combinatorial optimization problem. First, the relevant manufacturing processes are explained in the following section and then the specifics o f the problem are detailed. 1.2 Manufacturing Processes The manufacturing processes and steps in the typical solid-wood furniture industry considered are depicted in Figure 1.1. The production is carried out in two major sections. The first section usually referred to as "Rough M i l l " , shown above the dashed line in the figure, produces the needed inventory based on the requirement o f the second section. The second section, shown below the dashed line, is the remainder of the plant that ends with packaging and shipping. Lumber o f different size and quality is purchased from different suppliers. Therefore, each load o f lumber (a load is a bundle of lumber as supplied by the mills) is stored in the warehouse and an inventory tracking system tags the loads based on their supplier, length, and other necessary information. If needed, to reduce the moisture content of lumber to the required level, the loads have to reside in the drying k i ln for a specified period of time. Bins of Stacked Strip Pieces Based on Length & Grade t Laminating (Edge-gluing & Curing by Radio Frequency to Produce Panels and Parts) Rough M i l l Section o f the Plant Second Section Panels Sizing & Edging (Panels and Parts) 1 Shaping & Dri l l ing Pre-assembly & Packaging Finishing (Lacquering & Drying) Sanding & Inspection Figure 1.1. Manufacturing processes. After drying, the primary manufacturing process is the cutting of lumber into strips by the so-called "ripsaw" machine. The strips are produced online and in real time by 'ripping' lumber (the industry term for cutting along the length) with standard lengths of 10 feet (3000 mm), 12 feet (3600 mm), 16feet (4800 mm), etc. into strips of the same length. The ripsaw consists of a stack o f several circular saw blades that are appropriately spaced in advance based on the desired width for the strips. Figure 1.2 illustrates a lumber with knot and crack defects, and the strips that are produced from it. Large Knot Small Knot Lumber Strips > p i 4^— Defects must be cut away Figure 1.2. Lumber and strips. In the next station, immediately after the lumber is ripped into strips, a human operator visually inspects each of the strips one at a time and marks all defects (large knots, cracks and stains) and grade changes along the strips with a crayon. Small knots are accepted. Indeed, this process can be automated using vision and pattern recognition methods, but currently the company prefers the manual method. A simple bar-coding scheme is used to distinguish different grades and the defects as seen in Figure 1.3 for a 12 feet (3600 mm) strip. It should be noted that in the figure the code reading is from left to right. Start Grade and defect markings | : Best grade (A) starts | | : Medium grade (B) starts : Lowest grade (C) starts : Defect (Large knot, stain or crack) starts End B Knot A C Crack B 1 748 mm Figure 1. 147mr 3. The n 1227 mm defect and grade 733 mm variation of a 196 mm 541mm 3600 m m strip. Grade A (also called grade 1), the highest quality pieces, are used to produce the top and visible panels o f the furniture such as the tabletop. Grade B (also referred to as grade 2) pieces are used for the interior and less visible parts such as inside a drawer, and grade C (or grade 3) pieces with the lowest quality are used as structural members. Always, a few millimetres (4 mm in Figure 1.3) from each end o f the strips is cut out for quality reasons. Next, the strips are transferred via a conveyor through a scanner that scans the crayon-markings and records the distances between them. Each strip that arrives at the chopsaw has a different grade and defect markings along its length, which are unknown in advance of the cutting. This is a major uncertainty in the production. After the scanner, which has no in-process buffer, each strip is 'chopped' (chopping is the industry term for cutting normal to the strips) into pieces of shorter length for two purposes: - To take out the cracks, stains and large knots. - To produce the required lengths and grades from defect-free pieces. A defect-free or "clean" piece is part of the strip that is between any two defects or one defect and one end of the strip. A conveyor located adjacent to the chopsaw transfers the chopped pieces in front o f a number o f kickers. For example, Canwood Furniture Inc. has 8 kickers. Each of these kickers is programmed to kick (push) a required chopped piece with specific length and grade onto the table beside the conveyor. Then, a human operator picks these pieces from the table and sorts them into stacks on pallets based on their length and grade. The observation at the plant was that operators demonstrated acceptable speeds in matching pace with the kicker output. The rough m i l l section of the plant ends here. These stacks o f wood are then transferred to the second section of the plant. The second section of the plant starts with the laminator machines. Here, to produce the panels and other parts o f the furniture, such as tabletops and legs, the chopped strip pieces are laminated. Based on the size and shape o f the needed parts, a specified number o f pieces with the same length and grade are glued together and cured by radio frequency in the laminator machines. For instance, Figure 1.4 shows that 8 defect-free 1200 mm long pieces o f the highest grade are glued together to make the wooden panel for a tabletop. Also 16 pieces with the same grade and a length o f 800 mm are required to make the four table legs. For simplicity, we have skipped the mechanism for attaching the legs to the tabletop. Next, the panels and parts are sized, shaped, edged, and drilled in one of many available C N C machines. Then the parts are sanded and inspected for deficiencies and once passed they are lacquered and dried. The final processes are pre-assembly and packaging as these industries produce ready-to-assemble products and the customers assemble some parts o f the product after purchase. To satisfy customer orders, different daily lists of orders and required pieces to cut are prepared. These have been discussed in the following section where the features o f the problem are elaborated in detail. Chopped graded pieces if :a I -'i-A-. • -• A's A l, • A , — . — A J 1200 mm / -800 mm / all grade A Laminating Followed by Sizing, Shaping, Edging, Dri l l ing, Sanding & Lacquering Furniture parts c Figure 1.4. The pieces required to produce a table. 1.3 Problem Discussion A s mentioned earlier, the company accepts customer orders o f any size ranging from only one to any number of products i f the customer agrees with the company's proposed delivery date. Many different orders are accepted daily and therefore, this low-volume high-variety shop floor should be capable of scheduling and producing a varying demand of products. Based on the overall scheduling and planning criteria, the production managers create batches o f customer orders and prioritize these batches taking into account the delivery dates and the importance o f meeting their promised due dates. A s a result, a prioritized list o f customers' orders is prepared. Table 1.1 shows a simple case of such an order list. The prioritized order list has four columns as illustrated where the first and second columns are the product identification number (Product ID, which is a code number assigned by the company) and the product name. The third column is the required quantity and the forth column prioritizes the batch o f order as "high" or "low". The orders prioritized as high are produced first and this also helps to make sure that all required parts of a product in these orders are produced closer in time. It is not necessary to define more than the two high and low classes. The reason is that the other orders with less importance can always be added to the order list gradually based on their priority once some of the current orders have been processed. A s higher priority orders from the top o f the list are produced the remaining orders can be added to the bottom of the list. These orders are then classified as high or low based on their importance. Thus, having only two categories is sufficient for the chopping process. Table 1.1. A prioritized Order List. Product ID Product Name Quantity Order Priority 101 Dinner Table 1 35 High 503 Book Shelf 3 41 High 307 Study Desk 7 50 High 403 Computer Desk 3 28 High 202 Entertainment Unit 2 34 High 307 Study Desk 7 38 L o w 101 Dinner Table 1 50 L o w 603 Single Bed 3 20 L o w 208 Entertainment Unit 8 80 L o w 406 Computer Desk 6 22 L o w The required wood pieces to produce the high priority orders have' to be considered first in the choice of picking a size to cut out o f the strips. For example, the product "Study Desk 7" with a product ID of 307 has been listed twice. But only after the first 50 units o f this product and all the other orders with high priority are produced, the remaining 38 units o f "Study Desk 7" and other low priority orders should be considered for production. The illustrated list contains only few items whereas there are over 180 different products and the order list is often much longer. To satisfy these orders and chop the required pieces, another requirement list, referred to as the 'cut list ' , is prepared. Table 1.2 illustrates a unit cut list o f all the pieces needed to produce one unit of the product "Dinner Table 1", and Table 1.3 illustrates the same for one unit o f the product "Book Shelf 3". Each o f the products has one such unit cut list. The first column shows the required length o f the pieces. The second column is the required quantity. The last column in the unit cut list is the quality grade o f each item. For example, the first row on the unit cut list o f Table 1.2 shows that 22 grade A pieces of length 2000 mm are needed which are used to produce a laminated panel for the tabletop. Table 1.2. Pieces needed for one unit of "Dinner Table 1". Unit Cut List of Dinner Table 1 Length (mm) Quantity Grade 2000 22 A 1520 20 A 950 10 B 700 20 B 550 8 A 450 24 B 380 12 C Table 1.3. Pieces needed for one unit o f "Book Shelf 3". Unit Cut List of Book Shelf 3 Length (mm) Quantity Grade 1890 8 A 1710 10 A 1200 20 A 950 30 B 900 10 C 700 40 B 630 16 B 450 12 B 380 4 C Table 1.1 can be combined together with tables such as 1.2 and 1.3 into another table to form an "aggregate cut list". For example, i f the total o f 85 units o f "Dinner Table 1" and 41 units o f "Book Shelf 3" were to be produced, the aggregate cut list would be as is shown in Table 1.4. Table 1.4. The aggregate cut list from Tables 1.1,1.2, and 1.3. Items Length (mm) Grade Quantity (Total) Quantity (High Priority Portion) 1 2000 A 1870 770 2 1890 A 328 328 3 1710 A 410 410 4 1520 A 1700 700 5 1200 A 820 820 6 950 B 2080 1580 7 900 C 410 410 8 700 B 3340 2340 9 630 B 656 656 10 550 A 680 280 11 450 B 2532 1332 12 380 C 1184 584 It should be noted that because some of the orders in the Table 1.1 have been given higher priority, the quantity data are recorded in two columns. A quantity is given in the forth column of Table 1.4 that shows the total required quantity o f a size and the fifth column shows what portion of this quantity is for high priority orders. For example, 35 units of "Dinner Table 1" is ordered with high priority and therefore 770 pieces o f 2000 mm grade A have high priority and the remaining 1100 pieces are for low priority orders. A s discussed, the aggregate cut list o f Table 1.4 shows only the required lengths for products 101 and 503 listed in rows 1, 2, and 7 o f Table 1.1. However, in order to produce all o f the orders listed in Table 1.1, the ordered quantities for the other six products (307, 403, 202, 603, 208, 406) should also be multiplied by the quantities of the items in their unit cut lists and then added to the aggregate cut list. This is not shown here to save space, but the combined cut list w i l l have much more items than shown in Table 1.4 as the lengths required for each o f the ordered products might not be common with those o f the other products. On the other hand, all o f the items cannot be chopped at the same time because there is a limited number of kickers and limited space to stack the chopped pieces. Therefore, a subset o f the items of the combined and long cut list has to be selected for the primary or short cut list. One decision problem is the choice o f this subset and then the selection and adding o f the remaining items to the list, as one required item is completely produced and a kicker becomes available. For example, i f Table 1.4 is to be produced and only 8 kickers are available, then a set o f 8 items out o f the 12 items o f Table 1.4 has to be selected for the primary cut list. Also the 9 t h , 10 t h , 11 t h and 12 t h items must be specified so that once one item o f the first 8 is completely produced another item can be added to the list. A t present the production managers do this by some rule o f thumb and normally they try to include a variety of lengths from short to long such that the cut lists is not saturated with long size items only. When they batch and prioritize orders, they try to match orders that have many long pieces with orders that have many short pieces. This way the inventory needed for such a batch o f orders can be chopped out o f the strips with less waste. The managers know from experience that "Computer Desk 3" and "Entertainment Unit 2" have components that can be cut out o f 16 feet lumber with reasonable waste. Wi th such rules o f thumb, they categorize and batch the products. A cut list is then prepared according to the number o f available kickers. The high priority items are given preference and listed in the cut list first. The low priority items are added later. In order to further discuss other decision making problems in the chopping process, consider a cut list as shown in Table 1.5. It is assumed that there are 10 kickers available and all items of the cut list have the same priority and so there is no fifth column o f high priority quantities. Table 1.5. A cut list with no order priority. Items Length (mm) Grade Quantity 1 1900 A 1226 2 1200 A 770 3 1000 A 500 4 550 A 2880 5 900 B 340 6 600 B 3831 7 350 B 5098 8 1800 C 2057 9 550 C 800 10 400 c 222 A s mentioned earlier, each strip arrives at the chopsaw with a random defect and grade pattern. Let us assume that one 'clean' piece of strip with the overall length o f 4800 mm has arrived and is to be cut. The grading along the piece varies as illustrated in Figure 1.5. B A C I B 1200 mm 1200 mm 1700 mm '700 m m Figure 1.5. The grade pattern of a clean piece. A practice that the company has found useful, at no significant cost, is that grade A sections o f each strip can be downgraded and cut as grade B or C items. Also grade B sections can be used to cut items as grade C item. But grade C sections can only be cut for grade C items. Whenever required, downgrading is done for two reasons: - To overcome the shortage o f a grade by cutting higher grade sections as a lower grade. - To add the neighbouring sections and create longer pieces for optimum cuts. In either case, the action o f using better wood instead o f lower quality is in favour o f the customer. In order to show the scale of the strip-cutting problem in this introductory chapter, using the cut list o f Table 1.5, and 10 kickers, a program was written which determined that there were 321,725 possible ways to cut the single clean piece shown in Figure 1.5, out o f which 18,325 cut patterns had zero waste. But without any grading constraint and with total length as the only bound, there were 786,690 possible combinations o f the cut patterns including 159,151 zero-waste patterns. Although, the grading requirement reduces the number o f possible cut patterns the number of different patterns for a single graded clean piece is still large and a computer algorithm is needed to generate them. For example, the clean piece of Figure 1.5 and one such pattern to cut it are illustrated in Figure 1.6. The pattern has zero waste and the only downgrading was a 100 mm length o f the last grade B section for its neighbouring section o f grade C . Clean Piece-> B I A I C 1 B 1200 mm 1200 mm 1700 mm CutPattern-> 700 m m ll«f!' 600B 600 B 1200 A 1800 C \ > ^ 100 mm - > Downgraded 600 B Item 2 Item 8 Portion I t e m 6 (From B to C) Item 6 item 6 Figure 1.6. One cut pattern for the clean piece, Another example o f a cut pattern is illustrated in Figure 1.7. To produce this pattern a 50 mm of grade A section is downgraded to grade B to create a 350 mm grade B piece. The remaining 50 mm of grade A and also 50 m m of last grade B section are downgraded to cut 1800 mm as grade C. A t the end o f the strip a 50 m m piece remains that is of no use for the cut list and is considered as waste. Clean Piece B 1 A 1 C I B 1200 mm 1200 mm 1700 mm 700 mm Cut Pattern —-> 900B 350B 55QA 550A 1800 C 6 0 0 B 5 0 B t Waste Figure 1.7. Another cut pattern. Another possible pattern where the A section is completely downgraded to B , but not used as a neighbouring section, is shown in Figure 1.8. Clean Piece. Cut Pattern, B 1 A 1 C 1 B 1200 mm 1200 mm 1700 mm '700 mm 1 I K - - 1 600B 600B 600B 600B 1800C 600B Figure 1.8. Another example for cut pattern. It can be observed from the above examples that downgrading and use o f neighbouring sections to cut a longer item leads to generation o f many different cut patterns. Sometimes the number o f permissible cut patterns for a single strip or a clean piece is so high that the computer takes longer time than what can be considered reasonable for an online application to find a cut pattern with minimum waste. The computer has to generate a very large number o f possible combinations and compare their wastes and then select the best. In addition to this complexity, in order to produce the entire cut list optimally, a real time optimization algorithm is needed to find the best cut pattern not only for any arriving strip but also overall for all the required strips. Again, it should be noted that strips arrive with unknown defect and grade patterns. A good choice o f the cut pattern w i l l attempt to cut a single strip with least waste possible as well as to maintain a balanced build-up o f the required quantities of the cut list. The balanced build-up o f the cut list means that the cut list does not run short o f small length items too early. That is, there wi l l always be a favourable balance or mix o f short and long items left on the cut list, which can be used to create cut patterns with small waste for each strip. The mechanism in the final algorithm that can maintain this balance is addressed in chapter 5. Another characteristic o f the problem, is the prioritized order list where some portion o f the items on the aggregate cut list has higher priority over the remaining items. Therefore, the cut patterns have to be chosen such that the higher priority orders are delivered on time and thus the priority o f the order must somehow be accounted for i n the optimization algorithm. Those cut patterns that minimize waste over all cuts and also select higher priority items are considered as the best choices. The other feature of the problem is that the required pieces for an order have to be produced closer in time so that they can be further processed (laminated, shaped, machined, etc.) and shipped out to the customer. This means that the cut list should be created such that all parts of the orders can be produced in a timely manner. Production managers batch orders and release them to the shop floor based on their overall scheduling criteria and try to have all parts of an order to arrive at the packaging stations almost at the same time. A manual rule o f thumb approach works but lacks sufficient optimality. To summarize all the previously discussed features, the problem can be characterized as follows. Combinatorial: Decisions have to be made amongst a very large number o f possible cut pattern alternatives. Selecting the best alternative from all o f the possible combinations in a defect-sensitive production environment even for a small plant is very challenging. Large variety of product, abundance o f orders o f different size, limited number of kickers, downgrading and using the neighboring sections on clean pieces increase the number o f cut pattern options significantly. Fuzzy: Different workers assigned to the grading station in various shifts decide on the quality and grading scheme and mark the strips based on their judgment. These grading schemes overlap and the results can be argued to belong to a lower or higher grade. Uncertain: A major uncertainty arises from the fact that the quality o f each lumber is not exactly known prior to ripping. One might only have a general idea that a particular load o f lumber from certain area or supplier, overall, has a superior or inferior quality than the average experienced. The other uncertainty is that order arrivals are totally random and often have different priorities. Dynamic: The orders can be and are often changed on the run by the production managers. Thus, new items can be added to the cut list being processed. High Volume: The volume of material flow on the shop floor is very high. The reason is that numerous orders o f different products are normally released to the shop floor at the same time. This translates to a large quantity and variety of chopped pieces. Real time: N o buffers are available between grading, scanning, and chopping stations. The strips and chopped pieces are produced on the run based on the orders. The speed o f the optimization algorithm has to be suitable for the high pace chopping process. Multi Criteria: More than one objective has to be considered in the decision making. Beside the concern for wood recovery (minimizing waste) the required pieces for the orders with higher priority have to be cut earlier so that the due dates can be met. Dependency: The choice o f a cut pattern in one strip w i l l affect the choice o f cut pattern in the others. In addition, all parts of an order cannot be scheduled for chopping far ahead in time, otherwise there w i l l be a large work-in-progress. N o w that the problem has been discussed in detail, the objective o f the work and its limitations are presented in the next section. 1.4 Motivation, Objectives and Limitation of this Study The wood waste from the cutting process in Canwood Furniture Inc. is about 15%, which is a significant figure for such a major furniture company in British Columbia, Canada. The goal o f this work is to develop an optimization algorithm to reduce the wood waste, which consequently w i l l also save on the manufacturing costs and help preserve the nature. The optimization algorithm must be fast and applicable for real time on line decision making. It is important to emphasize again that the wood is not cut in advance and the cutting process where each wood strip is cut into shorter pieces is a high pace real time process. The algorithm should also be capable o f receiving cut lists as input and allow new items to be added to the list at any time. In addition, based on the due date consideration some of the orders might be prioritized higher than the others. Therefore, the real time optimization algorithm must consider the different priorities o f orders while minimizing waste. In this work three different sets of cut lists are considered for experimentation and evaluation of the optimization algorithm. First, fixed cut lists with no order priority are used with the optimization algorithm. For the second set o f experiments the algorithm is extended to include dynamic cut lists where new items replace those items o f the primary cut list that have been completely produced. Finally, the algorithm is further extended to take the prioritized order list into account and produce the pieces such that the waste is minimized and the more important orders are produced as early as possible. In all three cases it is assumed that the number o f items on the cut list are either equal to or less than the number o f available kickers. Although, as mentioned earlier, the high-low prioritization o f the order list can partially take care of the on-time production o f all parts o f an order, this work does not include the sequencing o f orders and their required pieces. Neither this work addresses the scheduling and batching of orders, nor it covers the selection o f the subset of the items for the primary cut list and the sequence o f adding the remaining items. In other words, kicker limitation and planning are not included in this thesis. This is because these phases o f the decision making process involve the well-known Low-Volume High-Variety ( L V H V ) job shop scheduling problem that is not the focus o f this work. This type o f job shop scheduling problems is known to be amongst the most difficult type o f such problems and falls into the NP-hard combinatorial category. Heuristic or distributed approaches are normally considered to solve problems o f this type [3,4]. 1.5 Organization of the Work The remainder o f this thesis is organized as follows. Chapter 2 discusses the problem classification, provides a literature survey and elaborates on the available related works on the minimization of waste in similar cutting processes. Chapter 3 describes the statistical distribution of the industrial data in an attempt to determine whether certain trends and patterns that can be utilized for optimization exist. A mathematical analysis of the problem is presented in chapter 4. In this chapter, first a formulation of the problem is provided. Next, the solution o f the mathematical model is discussed and several examples are presented. Last in this chapter, the size o f the problem is investigated. Chapter 5 presents the introduction and testing o f five different ranking methods. Ranking the items on the cut list, which is other than the prioritizing items due to prioritized order list, is one o f the major steps towards the development o f the optimization algorithm to solve the problem addressed in this work. A major part o f the optimization algorithm is the generation o f permissible cut patterns in a time-efficient manner. This is done through development o f a recursive algorithm in chapter 6 with experimentation to show that the algorithm can be applied for real time online decision making. Based on the two major procedures, an optimization algorithm is presented in chapter 7 along with its various versions o f the real problems and the test results. The work is concluded in chapter 8 with a statement of the contributions and suggestions for future research. CHAPTER 2 Problem Classification and Literature Survey Prior to providing a brief overview o f the related works, first the real time strip-cutting problem is classified within the current literature and presented in section 2.1. Section 2.2 discusses the well-known classical cutting stock problem and its solution, as the result obtained by this approach is used later in chapter 5 for comparison with the result o f one of the proposed algorithms. Section 2.3 elaborates on the current approaches and introduces some o f the available literature on different cutting stock problems. Section 2.4 concludes this chapter. 2.1 Classifying the Problem A significant body of literature and research material exist on combinatorial cutting and packing optimization problems. In these problems one or more pieces of material or space must be divided into smaller pieces or spaces (see Figure 2.1). I I D Cutting 2D Rectangular Cutting 2D Nesting or Irregular Cutting 3D Pallet or Container Loading Figure 2.1. Cutting and packing problems. The main objective in such problems is usually the minimization o f the total material or space used or consequently the minimization o f wasted material or space. The problem at hand is a complex extension o f the well-known Cutting Stock Problem (CSP), which has a wide variety o f applications in paper, meat, wood and other manufacturing industries [5]. C S P exist in one, two, and three-dimensional forms [6]. The problem in this work is a complex form o f one-dimensional cutting stock problem (1D-CSP) with the features discussed in chapter 1. The features included online production o f defect-sensitive strips, real time decision making, grading, downgrading and use o f neighbouring sections, dynamic cut lists and prioritized order list. In the literature, there are no mathematical solutions or any algorithms available for this real time problem, as the parameter values are not known in advance. If the above complexities are neglected, the problem can be expressed as a "classical one-dimensional cutting stock problem" (classical 1D-CSP). This is defined and presented in detail in the next section. 2.2 Classical One-dimensional Cutting Stock Problem In this section, the classical 1D-CSP is defined and one o f its solution approaches is explained. However, to simplify the complex problem described in chapter 1 to a classical 1D-CSP, all o f the strips have to be defect-free and without grading (all considered as same grade). In addition, cut lists should not have grading requirements, variability, and order priority. Then the problem would be, for example, i f strips o f 4880mm (16 feet) length and uniform quality are available, how many strips are needed to produce the cut list o f Table 2.1 optimally? In other words, what is the minimum number o f strips o f length 4880 mm needed to produce the entire cut list? Table 2.1. A cut list with no grades and order priorities. Items Length (mm) Quantity 1 1900 1226 2 1775 770 3 1080 500 4 550 2880 5 1420 340 6 380 3831 7 940 5098 8 1030 2057 9 1160 800 10 1290 222 In the field o f combinatorial optimization there is enormous amount o f literature on C S P [5, 7]. C S P is also referred to as "Tr im Loss" or "Stock Slitting" problem [8]. The minimization o f waste in the process o f cutting paper rolls in the paper industry is one case o f the classical 1D-CSP. A significant amount of research has been carried out on 1D-CSP for different industries and different solution approaches exist. In paper industry 1D-CSP is solved to cut rolls of paper shown in Figure 2.2. The solution for the classical 1D-CSP is presented in the following subsection. Figure 2.2. Cutting paper rolls. 2.2.1 Solution of Classical 1D-CSP A typical solution approach determines a set of cutting patterns that produce the cut list with a minimal scrap. Many o f these solutions have focused on generating an appropriate set o f candidate cutting patterns within the context of Integer Linear Programming (ILP) [9, 10, 11, 12, and 13]. Branch-and-Bound [14] and simulated annealing [15, 16] approaches have also been used. Heuristic approaches such as evolutionary programming and genetic algorithms (GA) have been considered as promising solutions [17, 18, and 19]. C S P may also be formulated as a Bin-Packing problem, for which successful G A solution approaches exist [20]. Regardless o f the adopted approach, the typical solution method has to identify a set of best cutting patterns and the number o f times these patterns should be used. This is described in what follows for the ILP approach in [10] where each column in the constraint matrix represents a specific cutting pattern. This heuristic approach is called the "Delayed Column Generation" method where a partial exhaustive search for the optimum cut pattern is attempted. The solution is derived from alternating iterations between a linear programming relaxation problem and a knapsack problem. Haessler [21] proves that the solution of this approach very often leads to optimum. The mathematical formulation of the relaxation and the knapsack problems follows. Linear Program Relaxation Ay = the number o f times the cut list item i is produced in pattern j. Xj = the number o f times they'th pattern is used (the integer requirement for Xj is relaxed). bi = the demand for the z'th item. n = the number o f patterns in the model. The linear program (LP) can then be formulated as: n Minimize X 1 ; 7=1 1 n Subject to: Y A.- y • > b-j = l lJ J 1 X j > 0 First, a random initial set of patterns is selected. A s this set o f patterns is probably not the best set for solving the problem, to obtain a new pattern (which w i l l reduce the number of rolls used), the dual variables (y) from this problem are used in the knapsack sub-problem below. Knapsack Problem Wi: = lengths of the required items. yt = dual costs from the L P relaxation problem. z, = the variable that represent the number o f required item with length Wi to include in the pattern. L = length o f stock (e.g. strip, roll o f paper). m = the number o f required items. This problem can then be formulated as: m Maximize Z = ^ y - • z. i=l 1 1 m Subject to: £ W, -z.<L i=l z- Integer After solving the knapsack problem, the integer variables z, represent the number o f required items to include in the new set of patterns. If the optimal value Z < I, the problem has been solved. Otherwise, this new set o f patterns w i l l be sent to the first L P relaxation problem as a new initial set. The L P and the knapsack problem are solved iteratively until there are no more patterns to include in the L P . The procedure in short is as follows. Procedure 1. Select a set o f patterns for the L P relaxation problem. 2. Solve the L P relaxation with the current set. 3. Solve the knapsack problem using the dual prices. 4. If Z > 1 (Z= the objective value o f the knapsack problem), add the new pattern to the current set and then go to step 2. 5. I f Z < 1, then apply an integer programming solver to the linear program to obtain an all integer solution. There are many types of C S P and different solutions available in the literature. In addition, there are some software currently utilized in the industry. These are discussed in the following section. 2.3 Current Approaches and some Similar CSP The integer programming solution described in previous section is embedded in different software such as AMPL® (A Modeling Language for Mathematical Programming) [22, 23]. AMPL® w i l l be used later in chapter 5 for comparison of results with one part o f the proposed algorithm. However, this readily available solution cannot be extended for optimization o f the problem at hand since the operations involve the features discussed in chapter 1. Because a major uncertainty arises from the fact that the quality o f each lumber is not known prior to ripping, one might consider a scanning device as a candidate to reduce the degree o f such uncertainty. Many different suppliers such as L U X S C A N [24] produce scanning machines for wood industries. Either lumbers prior to ripping or the ripped strips can be scanned offline and tagged. Extra space and a costly storage and retrieval system are needed to accommodate this approach of optimizing the cuts offline. However, i f the lumbers are scanned, to determine the quality o f wood a 3D-interior scanning system is needed to scan the wood and locate all the defects, stains, and quality variations inside each piece o f lumber. For the strips, a 2D surface-scanning machine might suffice. Even i f the expensive 3D-interior or 2D offline scanning system is acquired and used in the plant, still many difficult challenges remain. First, it has to be decided what number o f lumbers or strip pieces to scan and what size o f buffer to consider for keeping all the scanned and graded stock prior to making decision on cut patterns. Then, an optimization solution is needed to determine the best possible cut patterns out o f the graded defect-free sections o f the strips. The input data w i l l be large and the optimum cut patterns have to be sought amongst a very large number of permissible combinations. The resulting situation w i l l be similar to, but much more complex than the "Container Loading Problem". This is an NP-hard problem as well and may be solved by different heuristics [25, 26]. In addition, for the daily ongoing production, the large input data and the optimization program need to be revisited frequently when a new stock is scanned or orders are received. A n interior scanning equipment can provide information about the structural integrity of the wood and perhaps, only the durability o f the product can be assessed. But having a scanner w i l l not help much in the choice o f the cut patterns and minimizing waste in the cutting process. It w i l l change the problem to a larger combinatorial optimization problem with increased costs of the scanner, the storage, and the retrieval system. Therefore, it is not very practical to have an offline decision making process. Instead an optimization algorithm is needed that decides on the cut patterns in real time as soon as the present scanner reads the crayon marked strips. There are several commercial systems available for the optimization o f the cutting processes [24, 27, and 28]. But the optimality o f the embedded algorithms is unknown and some of the system providers mention that they have no control over waste. Canwood Furniture Inc. is currently using an optimizer provided by P A U L S A W S [27]. The wood waste at Canwood Furniture Inc. is over 15% and the production managers do not know how good this figure is. Generally, simple rules o f thumb and heuristic algorithms are used with no proof of optimality. In the literature, various approaches are used at present for many different types o f CSP . None o f the available literature considers all o f the problem features addressed in this work simultaneously. However, several o f these approaches have similarities to parts o f the problem addressed in this thesis. These are discussed next. Ronhqvist [29] provides a mathematical formulation and a heuristic solution for a similar 1D-CSP. The heuristic method is based on a combination o f the lagrangean relaxation of the mathematical model and subgradient optimization, which is claimed to converge to optimal solution but this has not been proved. Only one piece o f stock is optimized at a time. To be an accurate model the length o f the stock has to be divided into 1 mm elements. For example a 3600 mm (12 ft) stock has to be divided into 3600 elements. Then for each element a very large number o f 0-1 variables are defined. Quality grading and downgrading are considered but the defects are not to be cut out. A time o f 4 seconds is given as the acceptable time to choose the optimum cut pattern after the stock is scanned. This time is not acceptable for the problem discussed in this thesis, where each strip is chopped in a second after it is scanned. It w i l l be shown later that the algorithms provided in this thesis can find the zero waste cut patterns in much less time than one second. Ragsdale and Zobel [30] present a classical 1D-CSP with an added practical constraint to make sure that all the required items o f a job at hand are cut first, before attempting the others. They have implemented a genetic algorithm approach to solve this new C S P referred to as "Ordered Cutting Stock Problem". Although, the approach deals with order satisfaction in cut pattern generation, but due to the complexities such as downgrading it is not possible to use such an approach for the problem in this research. Scull i [31] presents a probabilistic analysis for knife positioning on the insulating tape rolls where both edges o f the rolls have defects. These defects have random width and this results in variable length of the defect-free part o f the rolls. Thus, the clean piece length o f stock is random and variable, but there is no grading. In addition, the cut list consists o f one item only as the rolls of paper are cut to a standard unique size o f width. Sweeney and Haessler [32] provide a two-stage sequential heuristic for cutting paper rolls with random multiple quality grades across the width o f the rolls with defects. Despite some similarities with the problem at hand, their approach cannot be used here. First, the cut pattern decisions are optimized based on a single roll only. Second, for each roll the operator has to provide a rol l value and set some parameters for downgrading and finding o f feasible patterns. But, as elaborated earlier, the chopping process o f wood strips has high speed and fast real time decision making is necessary. Human input for each wood strip is impossible. In addition, human intervention in downgrading decisions is not practical at all due to huge number o f possibilities. Sarker [33] implements a dynamic programming approach to maximize the revenue from the cut pieces for a single paper or sheet-metal roll with many defects along its length. It is not necessary to cut out the defects and the cut pieces can have several defects. The revenue from pieces with more defects is less than the revenue from pieces with fewer defects. Furthermore, the roll does not have any grade variation and the approach does not consider several rolls for optimization. Hence, the proposed approach cannot be used to optimize the online cut sequencing of the graded strips in the problem here. B y using another dynamic programming approach, Lembersky and C h i [34] solve a cutting problem at Rough M i l l s . The tree trunks resulting from harvesting mature trees have to be crosscut (chopped) into logs o f various lengths. The trunks are in a tapered shape and graded along their lengths. The developed method optimizes the revenue o f a tree based on the value o f the different logs produced. The method is for optimization of only one tree trunk independent of the other trunks. Besides, the crosscut can occur at any location along the length of the tree trunk, i.e. there are no prescribed lengths. The trunks have defects but these only reduce the value o f the defective part. Defects are not cut out and there is no downgrading. Due to these reasons the solution cannot be implemented for the problem of strip chopping process. Whitaker and Cammell [35] apply linear programming to a variant of C S P in the meat industry to maximize return from cutting beef or lamb carcasses. The carcasses as a whole have different grades. The meat o f a carcass is priced differently based on the location o f the meat on the carcass and the grade of the carcass. Different sets o f cutting patterns are predefined for the lamb and beef carcasses without any grade constraints. To reduce the number of cutting patterns, the carcass is partitioned into smaller sections such as leg and shoulder. Each cut pattern has a market value and their method tries to find the set of cut patterns with highest possible revenue. Their approach does not have grading or downgrading features similar to the wood cutting process discussed in the previous chapter. Moreover, there are no defects to cut out and there is no online decision making. The cut patterns and pricing of the meat are known ahead o f time contrary to the strip defect and grade pattern data. Gradisar et al [36] solve another variant o f classical 1D-CSP with many different known stock lengths by a hybrid approach combining a linear programming method and a heuristic method. Later, Cizman and Cernetic [37] used this approach to apply for longitudinal tailoring of logs in veneer production as a case study. Gradisar and Trkman [38] present another combined approach for the same type o f C S P with multiple known stock lengths. Their approach is based on using a branch and bound procedure and a heuristic. However, none o f these approaches can be used to solve a real time defect-sensitive cutting stock problem as they do not consider quality grades and defects, and the lengths o f the stock they use are known in advance. Yermal et al [39] present an approach based on genetic algorithms to schedule orders in paper mills . They use rolls with different grades, but each roll has only one grade along its length and thus the problem for each rol l is the same as a classical 1D-CSP . Vasko et al [40] solve a 1D-CSP by a hierarchical approach in the steel industry. They consider three grades o f A , B , and C for steel bars with multiple lengths. However, each bar has only one grade along the length o f the bar without any grade changes. The different lengths of stock material are known ahead of time. Furthermore, this problem does not incorporate the uncertainties that exist in the wood cutting process. Holthaus [41] suggests that keeping an inventory o f stock with multiple lengths is generally beneficial to reduce waste for the classical 1D-CSP. Thus, in addition to the CSP , an assortment problem (also referred to as stock-size selection problem) has to be solved as well . A procedure is developed for finding the best combination o f stock sizes to be maintained as inventory in order to minimize the objective function of C S P . This approach assumes a known set of stock lengths that does not exist in the case o f wood strips with unknown defect and grade patterns. Belov and Scheithauer [42] introduce a combined algorithm for the 1D-CSP with multiple stock lengths. Here also, a set of stocks with multiple known sizes is considered. The stocks are defect-free and without grading. 2.4 Concluding Remarks The strip cutting problem has been classified and shown that none of the 1D-CSP in the literature is applicable to the one addressed in this work. The existence o f the literature as reviewed indicated the importance of this class o f optimization problems in a range of industries and applications. To solve the problem in this research, all issues such as quality grading, downgrading, use of neighbouring sections, random variable lengths and online productions have to be considered simultaneously. In order to develop a solution approach, first the input data is investigated in chapter 3 to gain an insight into the nature o f the problem. CHAPTER 3 Frequency Distributions of Industrial Data In this chapter the distributions of industrial data from the Canwood plant are presented and discussed. This chapter has three sections. Section 3.1 reviews the frequency distributions of the raw stock. A typical frequency distribution for demand is depicted in section 3.2, and the concluding remarks are given in section 3.3. 3.1 Frequency Distributions of the Stock In order to experiment with real data in this work, many different data files have been recorded from the computer used at the scanner station at Canwood Furniture Inc. Each data file contains the readings of many strips that have been produced and graded on line. These files have been recorded on various days of the production using different loads of lumber with different standard lengths. A s it was mentioned in the first chapter, these industries purchase their wood from various sawmills each of which supply wood o f different quality. The quality of the wood depends on many factors such as the harvest location and time. Therefore, as a first attempt towards a solution for the problem at hand the defect and grade distributions should be visualized to see whether or not these distributions follow any particular patterns. If any specific patterns could be identified then these might be utilized later in the development of the optimization algorithm. From the data read by the scanner various distributions can be produced such as the following: - Distribution o f grade A sections. - Distribution of grade B sections. - Distribution o f grade C sections. Distribution of grade A B or B A sections. Distribution of grade A C or C A sections. - Distribution of grade B C or C B sections. - Distribution of the length of clean pieces (referred as A B C sections, which include any combination o f A , B , and C) . The above distributions data are from two complete sets of stock that have actually been cut and used. The distributions other than sole A , B or C grades are generated to account for the downgrading practice at the plant. The other distribution that is presented in the next section is the distribution of some of the cut lists in order to see whether there is a match between the demand and the available stock. Figure 3.1 shows the distributions of grade A sections on the clean pieces for two sets of data. Figure 3.1(a) is for the first set o f data accumulated from 913 strips and Figure 3.1(b) is for 749 strips. Such grade A distributions o f many other data files were also produced, but have not been shown here to save on space. Each o f these distributions was different arid no specific pattern could be observed. Number of pieces 200 180 160 140 120 100 80 60 40 20 0 A - data set 1 i Number of Pieces 150 0 1000 2000 3000 4000 5000 Length (mm) 0 1000 2000 3000 4000 5000 Length (mm) (a) Data set 1 with 913 strips (b) Data set 2 with 749 strips Figure 3.1. The distributions o f grade A sections. The distribution o f grade B sections on the clean pieces for the same 913 strips is given in Figure 3.2(a) and for the same 749 strips in Figure 3.2(b). Here also no specific pattern could be identified. Number of Pieces 200 180 160 140 120 100 80 60 40 20 0 B- data set 1 Number of Pieces 150 120 90 60 30 B- data set 2 0 1000 2000 3000 4000 5000 ^ m m ^ 0 1000 2000 3000 4000 5000 Length (mm) (a) Data set 1 with 913 strips (b) Data set 2 with 749 strips Figure 3.2. The distributions o f grade B sections. Figure 3.3(a) is the distribution o f grade C sections on the clean pieces produced from the same 913 strips. Figure 3.3(b) is the corresponding distribution for the data from 749 strips. These two and all o f such generated distributions verified the random nature of the available lengths. Number of Pieces 200 180 160 140 120 100 80 60 40 20 0 C - data set 1 Number of Pieces 150 120 90 60 30 C - data set 2 0 1000 2000 3000 4000 5000 L e n 8 t h ( m m ) 0 1000 2000 3000 4000 5000 (mm) (a) Data set 1 with 913 strips (b) Data set 2 with 749 strips Figure 3.3. The distributions of grade C sections. The following Figures 3.4, 3.5, and 3.6 show distributions for A B , A C , and B C sections accordingly. These are for the same data sets that were discussed above. These also show the random nature of the raw material as the input for the optimization algorithm. It is evident that the distribution of single and combined grades vary with data sets analyzed. Number of Pieces Number of Pieces 200 180 160 140 120 100 80 60 40 20 0 AB - data set 1 150 120 90 60 30 AB - data set 2 0 1000 2000 3000 4000 5000 ( m m ) 0 1000 2000 3000 4000 5000 Length (™m) (a) Data set 1 with 913 strips (b) Data set 2 with 749 strips Figure 3.4. The distributions of A B sections. Number of Pieces 200 180 160 140 120 100 80 60 40 20 0 AC - data set 1 Number of Pieces 150 120 90 60 30 AC - data set 2 0 1000 2000 3000 4000 5000 L e n i m ( ™ ) o 1000 2000 3000 4000 5000 Length (mm) (a) Data set 1 with 913 strips (b) Data set 2 with 749 strips Figure 3.5. The distributions of A C sections. Number of Pieces 200 180 160 140 120 100 80 60 40 20 0 BC - data set 1 Number of Pieces 150 120 .90 60 30 BC - data set 2 0 1000 2000 3000 4000 5000 L e n g t h ( ^ m m ^ 0 1000 2000 3000 4000 5000 Length (mm) (a) Data set 1 with 913 strips (b) Data set 2 with 749 strips Figure 3.6. The distributions of B C sections. Figures 3.7(a) and (b) are the distributions for the clean pieces (referred to as A B C ) for the same data samples. A s described earlier, the clean pieces might have any combination of the grades A , B , and C but do not have any defects. Number of Pieces 200 180 160 140 120 100 80 60 40 20 0 ABC - data set 1 \ 1 \ f V w V « • — , — Number of Pieces 150 120 90 60 30 0 \ ABC - data set 2 > -i—, , , , \+l 0 1000 2000 3000 4000 5000L e nS t n ( m m ) 0 1000 2000. 3000 4000 5000Length (mm) (a) Data set 1 with 913 strips (b) Data set 2 with 749 strips Figure 3.7. The distributions of clean pieces. 3.2 Frequency Distribution of the Demand The distribution of the demand is illustrated in Figure 3.8. The lengths of the required items and their quantities from several actual cut lists are depicted in this figure. This distribution does not match any of the previous supply distributions. Even i f any match could be observed with any of the above data or the data from other scanner files, there is no guarantee that such match w i l l repeat itself in future cases. The distributions generated from many other sample sets (not shown here) did not reveal any specific matching patterns either. Number of Pieces 5000 4500 4000 3500 3000 2500 2000 1500 1000 500 0 0 1000 2000 3000 4000 5000 Length (mm) Figure 3.8. The distribution of some cut list lengths. The distributions as depicted in Figures 3.1 to 3.7 and 3.8 w i l l also be a basis for calculating a lower bound to the problem size in chapter 4. 3.3 Concluding Remarks The defect, stain, and grade patterns are highly random and variable, and the wood quality depends on the forest location, time of the harvesting and many other unknown factors such as population o f insects responsible for wood staining. The distribution analysis above gave an insight to the variability o f raw material and thus precluded development o f any procedures or formalization of rules o f thumb for the optimum cutting of the strip pieces. This confirmed our belief that an online real time optimization can be beneficial as undertaken and outlined in the next four chapters. CHAPTER 4 Mathematical Analysis This chapter includes four sections. In section 4.1 a mathematical model is developed and presented for the strip-cutting problem. Next, in section 4.2, this model with its constraints and objective function is implemented in a program to find the optimum set o f cut patterns and the optimum total waste as an exact solution by assuming prior ripping and scanning of the strips. A n example is provided and analyzed in detail. Then, the program run times for various samples are presented in this section. The size o f the solution space is discussed in section 4.3. The concluding remarks follow in section 4.4. 4.1 Mathematical Formulation In this section a mathematical formulation for the strip cutting problem is developed. It was discussed in chapter 2 that the offline decision making is not very practical in these industries. However, it might still be possible to consider a buffer after the scanner before the chopsaw to first scan a batch o f strips online for production of a small portion of the cut list and then decide on the cut pattern. Therefore, to formulate the problem the online real time production requirement of the strips has been ignored and a mathematical model has been developed. The goal at this point is to investigate the usefulness or practicality o f implementing exact approaches to optimize the chopping process instead o f online decision making for a single strip. Thus, to minimize the waste during the production of any portion o f the cut list by an exact method, it is assumed that sufficient number o f strips have been produced and their defects and grade variations appropriately marked in advance. Except the absence of online ripping and prioritized orders all other features o f the problem such as graded cut lists, option of downgrading and use of neighboring sections are included in the mathematical formulation. First, the notation related to the available stock and demand wi l l be defined in this section and then the problem formulation w i l l be presented and discussed. Available Stock The notation for the strip data is listed below. B y cutting out the defects each strip w i l l become either one or more clean pieces. The cut list is produced from the clean pieces thus generated. The formulation uses these clean pieces. {P}= The set of all available clean pieces P„ = Length o f w t h clean piece It should be noted here that in the real case o f the problem the clean pieces arrive at the chopsaw randomly and thus the order of the set {P} is not known. Assuming that all clean pieces are available in advance, the set can be written as { P } = { P ; , P 2 , . . . . , P „ , . . . . , ? N } V « = i ,N N= Total number o f clean pieces used to produce the selected portion of cut list. Whatever portion of the cut list is selected for piling strips in a buffer ahead of time, N is not known prior to optimization as the number of strips needed for that portion is also not known and depends on the solution. N o matter whether the entire cut list or a portion o f it is selected, it is assumed that a set o f clean pieces is available and the goal is to completely produce the selection. Once the last item o f a cut list or the selection is cut, the waste for production o f the entire cut list or the selection is finalized and recorded as total waste. The next notation defined here is K„ as follows. K„ = Number o f graded sections on a clean piece (K„ is not constant and it can be different for each clean piece). Thus, the clean piece is made of K„ sections of lengths p „ / , p„2 , . . . . . . p ^ . K„ Hence: P „ = p„/ + pn2 + + P«A:„ = X P " * V N = 1 > N Gp„k= The grade o f kA section on clean piece n. Gp„ic& {1,2,3}, recalling that 1 corresponds to grade A , 2 to B , and 3 to C . Demand If the number o f items on the cut list is M i t can be said that we have a cut list o f size M. { L } = The set of cut list lengths = { L / , L ^ , . . . . , L M , LA/} V m=l,...., M {Q} = The set o f corresponding cut list quantities = {Qj, Q j , . . . . , Q m , . . . . , Oj/} {G} = The set o f corresponding cut list grades = {G; , G ^ , . . . . , G m , . . . . , Gm} Note that G m e {1,2,3}, where again 1 corresponds to grade A , 2 to B , and 3 to C . M T = Total required quantity = ^ Q, T includes the sum of the quantities for all three grades. Problem Formulation N o w the problem can be formulated in mathematical terms. Consider: 1 if clean piece n is cut with pattern j 0 otherwise N and \fj=l,....,Jn Jn - Number of all permissible cut patterns for clean piece n. J„ is not constant and varies based on the defect and grade pattern o f each clean piece. A cut pattern generation algorithm is necessary to create all permissible patterns and find J„ for each clean piece individually. Then, it is possible to find the variable: Onjm = Number o f occurrences of Length Lm in the cut pattern j on clean piece n. In other words, Onjm is the number of times Lm can be cut from clean piece n in the current cut pattern j. Once all values o f Jn are known the constraints and objective o f the problem are stated as follows. Objective: N J„ (1) Subject to the following constraints: X x „ . < l V«=7 , . . . . , JV (2) This is to make sure that only one cut pattern is chosen for every clean piece. f ^ O n j m x n J > Qm V m = i , M (3) n=l y=i This constraint is to meet the demand (satisfy all quantities of the cut list). In the constraint of equation (3), an equal sign can also replace greater-fhan-or-equal sign. In such formulation, the objective function w i l l make sure that no extra pieces are produced in excess to the cut list requirement. The above was the problem formulation in general. However, to produce permissible cut patterns, other constraint have to be considered. Constraints are necessary to ensure that the length and grade o f the items fit the grades and lengths o f the clean piece sections. The length o f the item must be either shorter than the section's length or neighboring section/s have to be added. I f the neighboring section/s are added because the length o f the section being considered is shorter than the length o f the item on the cut list, then the added neighbor/s must be of higher grade (have lower numerical grade value) than the grade o f the section. For example, to add to a section with grade 2 (or B) the neighboring section must have grade 1 (or A ) . In order to formulate such requirements, the following notation is necessary. S„y = A vector for pattern j containing the lengths of the pattern elements that are used to cut clean piece P„ V j=l,..... J„ J„ was the number of permissible cut patterns for clean piece n. ^nj ~ (s«/7j Snj2, , Snjh, SnjH) V —, Jn and s„jh£{L} V / * = / , . . . . , / / H= Number o f selected cut list items ( / / i s not constant and it can be different for each j). GS„y = The corresponding grade vector of the pattern j for clean piece n (grade vector for pattern S„j) GS„y = (g„j], gnj2,-• ••> gnjh, • ••; SnjH) Vj=l, Jn and gnjf,G {1,2,3} \/h=l,....,H Thus, to produce permissible cut patterns the following have to be true for all j: gnjh > Gp„k A N D Snfl, < p„k V /*=/,...., H and V k=l,...., Kn (4) Or by using the 1 s t neighboring section (downgrading may occur): gnjh > Gpnk A N D gnjh > Qpn(k+1) (5) A N D s„Jh <p„k + Vn(k+i) V h = l , H and V k=l,..... K„ Or by using the 2 n d neighboring section (downgrading may occur): gnjh > Gpnk A N D gnjh > Gp„(k+i) A N D gnjh > Opn(k+2) (6) A N D snjh < v„k + Vn(k+i) + Vn(k+2) V h = l , / / a n d V k=l,..... Kn Or by using the 3 r d neighboring section (downgrading may occur): gnjh ^ Gpnk A N D gnjh > Gp„(k+i) A N D gnjh > Gpn(k+2) A N D gnjh > Qpn(k+3) A N D S„jh ^ Vnk + Pn(k+1) + Vn(k+2) + pn(k+2) (7) V h=l,....,// and V k=l,..... Kn A n d so on . . . up to the last section (K„ section) of the clean piece. The model can be interpreted and presented mathematically in different forms. For example, the objective as stated in equation (1) is set to minimize the number of clean pieces that are used. Wi th the notation used above, the objective can also be considered as the minimization o f the leftover from each clean piece after it is cut with the selected pattern. This is shown as M i n £ (P„ - £ snJh) (8) n=l h=l A s another attempt, to ensure that the total length o f the whole cut pattern fits the clean piece length, constraints can be considered as in (9) or (10). M ^ O n J m L m x n J < V n Vn=l ,N and Vj=l,....,Jn (9) m=\ This means that the total length o f all items in 7 T H permissible cut pattern must fit the length o f the current clean piece. H Constraints on Length: ]jT snjh <?„ Vn=l,....,N and Vj=l,....,Jn (10) h=l H Note that: £ snjh = s„ji+s„j2+ + snJH h=l Equation (10) ensures that the total length o f selected cut pattern for each clean piece is smaller or equal than the length of that clean piece. In the next part o f this chapter using the constraints and objective function outlined above, a program has been coded to determine the optimal solution. 4.2 Exact Solution The formulation presented in the previous section has been coded in a program to find the optimum set o f cut patterns for the clean pieces. This section reports the results o f this program for some small problems and provides the C P U run time of the program. The program generates every permissible cut pattern for each clean piece and calculates its waste. The pattern generation algorithm is explained in chapter 6. The program produces all combinations of patterns for the clean pieces and calculates the total waste for each set o f combination. Those sets of cut patterns that satisfy the cut list quantity requirements are the solutions to the problem. The solution with the minimum total waste is then chosen as the optimum. In subsection 4.2.1, using a small example the solution approach and generated patterns are explained and the optimum solution of the example is determined. Next, as time is a concern in online applications, the C P U run times o f the exact approach for this sample problem and a few others are provided in subsection 4.2.2. 4.2.1 The Exact Solution for a Small Example Consider the short cut list o f Table 4.1 and the four 3600 mm long strips o f Figure 4.1. Table 4.1. A sample cut list. Items Length (mm) Grade Quantity 1 1000 A 4 2 600 B 8 3 500 C 7 M mi- -II B Knot A Crack B 1200 mm 150n i m 1100 mm 150 m m 1000 mm ' wmm ii IIWfcH A Knot A I B Knot C 600 m m 150m m 1600 mm ' 700 mm 150 mm 400 mm m C Knot B A c 500 mm 150mm 900 mm 1100 mm 950 m m - i 1 ,. -1 B A Knot A c 800 mm 1500 mm 150 mm 500 m m 650 m m Figure 4.1. Four 3600 m m graded strips. There are 10 clean pieces within the four strips o f Figure 4.1. The first strip has 3 clean pieces, each having only one grade section. These are a 1200 mm grade B , a 1100 mm grade A and a 1000 mm grade B clean pieces. The second strip has also 3 clean pieces but the middle piece contains two sections o f 1600 m m grade A and 700 m m grade B . The third and fourth strips both have one clean piece on each side o f their large knot. Each clean piece must be investigated separately to find out the number o f permissible cut patterns for all the four strips according to the cut list. Before doing this the following discussion is necessary to find and count the number o f permissible patterns for each clean piece. Assume items of the cut list in Table 4.1 except one piece o f 600 mm grade B have all been produced, and suppose that the first clean piece of Figure 4.1 (1200 mm long grade B) has not yet been chopped and is available. In other words, all other items o f the cut list have been chopped out o f the other clean pieces and the last single item is to be cut from first the clean piece. The remaining part o f the clean piece in this example is considered as waste. The number o f possible ways to cut the piece is infinite as illustrated in Figure 4.2 because the 600 mm item can be cut from any part of the clean piece with waste on one or both sides. 1200 mm Grade B W = Waste ; = Chop Line i = Many Other • • • i - " ' W 7 " * T " " 6 0 0 „ n m i > Figure 4.2. Infinite cut patterns. 600 mm ; W W | 600 mm W • ^600 nun m However, only the top and bottom patterns are considered. A l l the other patterns in between not only need two cuts but also create two small pieces mostly categorized as waste. If the leftover piece is kept as one piece as in the top or bottom patterns, it might be useful in a future cut. Thus, except the top and bottom patterns, none o f the others are considered as a cut pattern for optimization and hence are trivial patterns. The amount o f the waste is equal for all cases. In Figure 4.2 it did not matter where the 600mm item is cut on the clean piece, but for clean pieces with grade variation this is not the case. Assuming that an 1800 mm grade C item is to be cut from the 2400 m m clean piece, Figure 4.3 shows some o f the infinite number of patterns that can be considered, which except a few the rest are trivial. If the 600 mm leftover piece/s are going to be waste and the number of cuts is not a concern, then those patterns that make use o f all the A and B sections are a better pattern from the point o f view of quality. But i f the leftover is useful, then the top and bottom patterns in the figure are the best patterns because the leftover is kept as one piece and a single cut is needed for the production of the 1800 mm item. The program is coded such that it creates only three patterns, which are the top and the bottom patterns for material recovery purposes and the pattern that is the third from top for higher-grade utilization. A l l other patterns are ignored in order to produce less waste and have less number o f cuts, which saves production time. It should be noted that the program does produce all o f the non-trivial patterns. Now, returning to Figure 4.1 and as per Table 4.1 requirements, the total number of patterns for each clean piece w i l l be explored. The first clean piece (the 1200 mm grade B) can be cut in the 5 cut patterns shown in Figure 4.4. 2400 mm A B : c 1 18 00 mm Grade C * ** r ^ ^ 0 0 m m - G H a i e " C - • / T a T * ' • *c : - 1 ' ' ' ' ' 1 ' : 1800 mm Grade C Chop Line ! A B C 1800 mm Grade C Figure 4.3. Four patterns to cut a 1800 mm grade C item from a 2400 m m clean piece. 1200 mm Grade B 600 mm B l i i p f f l r i B * 600 rhnVfis?' 600 mm B '500 mm e | w j Pattern 4: 500 mm C 1500 mm C W W = Waste = Chop Line Pattern 5: 500 mm C ! W Figure 4.4. Five patterns for first clean piece. A s mentioned earlier, despite the fact that patterns 1 and 5 do not make use o f the leftover, but they are still counted as possible patterns. It was explained that pattern 1 or 5 might be for the case when it is the last item o f the cut list to be cut. Thus, the optimum solution might choose one of these two patterns for this specific case in spite o f the large waste, i f the total waste from all clean pieces for production of the entire cut list is the best overall. The other important point to reiterate here is that an infinite number o f patterns can be created but the algorithm considers only non-trivial patterns as discussed earlier. To save space and summarize, the number of non-trivial permissible cut patterns for the 10 clean pieces o f all four strips are given below stepping from the top left side of Figure 4.1 down to bottom right end. First strip (from Top), first clean piece (from left): 5 cut patterns. First strip, second clean piece: 5 cut patterns. First strip, third clean piece: 3 cut patterns. Second strip, first clean piece: 2 cut patterns. Second strip, second clean piece: 71 cut patterns. Second strip, third clean piece: 0 cut pattern. Third strip, first clean piece: 1 cut pattern. Third strip, second clean piece: 80 cut patterns. Fourth strip, first clean piece: 80 cut patterns. Fourth strip, second clean piece: 2 cut patterns. Having all possible combinations, using the demand constraint and the objective function the program finds the optimum solution, which is the combination that produces all required items of the cut list and has minimum waste. So, for the problem o f Table 4.1 and Figure 4.1 this solution is shown in Figure 4.5. A s illustrated in Figure 4.5, the waste produced by cutting out the defects cannot be avoided by any optimal or sub-optimal solutions. This waste is referred to as "Unavoidable Waste". Next, four other waste figures are defined, which are "Min imum Length Waste", "Uncut Waste", "Cut Waste" and "Total Waste". Based on the cut list given in Table 4.1 and the defects of second strip, the third clean piece o f this strip cannot be used in any pattern. This 400 mm grade C could have been used i f the cut list had a short item with grade C . Thus, no optimization procedure can prevent this type o f waste because it cannot cut the clean pieces that are shorter than the minimum length given in the cut list. This type of the waste is referred to as "minimum length waste". "Uncut waste" is the sum of all clean piece lengths that although they are longer than the shortest length once given in the cut list, they are not cut. This type o f waste is due to both bad cut pattern selection by the optimization algorithm and the nature o f the cut lists given by the user. These are the cut lists that either have few items or very few short items. Table 4.2 shows a cut list that requires only 28 pieces o f the shortest item. Strip 1: Optimum 4-.," - c - w iiinniiijuiniiiiwruiyiiiii, n B Knot A Crack B 1200 mm 150n l m 1100 mm 150 mm 1000 m m | | *s |*«Hfc:il | | * » I I ^ S & « l l - . t » | | | 600-B 600-B 1000-A 100-W 500-C 500-C Legend: 100-W = 100 mm Waste Strip 2: Knot 600 mm 150mm 1600 mm B ^H-,*-«f,r~,~"4=te»'.y 1 Knot 700 mm 150 mm 400 m m Optimum Pattern: i»»isa8»iai»«H«twa^»^~~f<PKi•>g- • ~Tt>i|^ '<r~ ^ -^^ n^ ir*^ i^r-^ g^*r~<^ n^ 6 0 0 - B 6 0 0 - B 1 0 0 0 - A 6 0 0 - B I Q Q - W 4 0 0 - W Strip 3: IE Knot B 500 mm 150mm 900 mm J L Optimum Pattern: i »«M^|jgfe!^H^a™ig^ta»^8g 1100 mm 950 m m 500-C 600-B 300-W 1000-A 500-C 500-C 50-W Strip 4: m B Optimum Pattern: i 800 mm Knot ..,.:...,*g 1500 mm 1 5 0 mm 5 0 0 m m 6 5 0 m m Z E E 6 0 0 - B 1 0 0 - W 6 0 0 - B 1000-A 500-C 600-B 150-W For Optimum Solution: Total Waste = 100+100+400+300+50+100+150 =1200 m m Cut Waste = 100+100+ 300+50+100+150 = 800 mm Unavoidable Waste (defects) = 6 x 150 = 900 mm Number of Combinations = 136,320,000 Program Run Time = 25.276 seconds Figure 4.5. The optimum solution for the small problem. Table 4.2. A n unbalanced cut list. Items Length (mm) Grade Quantity 1 1900 A 1226 2 1200 A 770 3 1000 B 500 4 550 C 28 After producing these 28 pieces, no clean piece shorter than 1000 mm can be cut. On the other hand, "Cut waste" is the accumulated waste from the clean pieces that are chopped to satisfy the cut list. Cut waste does not include the unavoidable waste, the minimum length waste and the uncut waste. "Total waste" is the sum o f the above wastes as illustrated in Figure 4.6. Total Waste Unavoidable Waste Min imum Length Waste Uncut Waste Cut Waste Figure 4.6. Five types o f waste. From the definitions o f these types o f wastes, it is clear that the assessment o f an optimization algorithm should not be solely based on any one waste. In this work, cut waste and total waste w i l l be used together as the performance measures in the simulation. The other output o f the program is the number of combination and the run time to produce the optimum result. This time is over 25 seconds for the small problem o f Table 4.1 and Figure 4.1. The total number of possible combinations to cut the four strips is calculated by multiplying the number o f permissible patterns for all clean pieces as follows: 5 • 5 • 3 • 2 - 71 • 1 • 80 • 80 • 2 = 136,320,000 This number o f combinations is not the size of the solution space, as it does not include the cut list quantity constraint. This w i l l be discussed later in this chapter. 4.2.2 The Program CPU Run Time In order to investigate the practicality of the developed exact approach for real time applications, the C P U run time of the program was recorded for nine small sample problems. In addition to the run times, the number o f clean pieces and the number o f combinations for each sample problem are given in Table 4.3. The run times versus the number o f combinations are also depicted in Figure 4.7. For a small problem with 8 clean pieces and 22,720,000 combinations, the run time was 2.61 seconds. But it took over 1275 seconds (over 21 minutes) to find the optimum solution among 5,452,800,000 possible combinations. Run time increases as the number o f clean pieces and consequently the number o f combinations increase. The number of combinations also grows when the length of the clean pieces are large. For example, sample problems 3 and 4 both have 10 clean pieces but these pieces come from different number o f strips. Sample problem 3 is the same as the example discussed in 4.2.1, where the 10 clean pieces were cut from 4 strips. But sample problem 4 has 5 strips and longer clean pieces. Table 4.3. C P U run times of sample problems. Sample Number of Number of Time Problems Clean Pieces Combinations (Second) 1 8 22,720,000 2.61 2 9 90,880,000 21.91 3 10 136,320,000 25.28 4 10 363,520,000 36.76 5 10 499,840,000 50.35 6 12 704,320,000 63.54 7 12 999,680,000 81.83 8 12 1,817,600,000 152.98 9 12 5,452,800,000 1275.27 Another reason for the increase in number of combinations is due to the cut list. Once the cut list consists more of shorter items compared to the length of the clean pieces, or once the number of items on the cut list grow, the number o f combinations w i l l also rise dramatically. Sample problems 5 to 9 represent such cases. It should be noted that sample problem 9 with such a significantly larger number o f combinations has only 12 clean pieces. 1400.00 1200.00 If 1000.00 oT 800.00 E j= 600.00 | 400.00 200.00 0.00 0 1,000 2,000 3,000 4,000 5,000 6,000 Number of Combinations (Millions) Figure 4.7. Program C P U run times for optimal solutions. Figure 4.7 shows how quickly the run time grows for even small problems as the number o f combinations grows suggesting that exact approaches are not suitable here. To justify this statement, the size o f the solution space has to be determined. It was mentioned that the number of combinations does not represent this size when the quantity constraint is not taken into account. However, it is necessary to elaborate on the size of the solution space mainly because o f the concern for time in online applications. This is done in the next section. 4.3 Size of the Solution Space This section provides a discussion on the size o f the solution space and the combinatorial complexity o f the problem. A s mentioned, this is necessary to investigate the practicality of solving the problem by exact approaches such as linear programming. In all o f the discussion in this section the same notation as o f section 4.1 is used. Furthermore, it was discussed in chapter 1 that there is a limited number o f kickers available to push the chopped pieces onto the sorting table. When the cut lists have more number of items than the number of kickers, the problem complexity w i l l grow because the number o f combinations for selecting a subset o f the cut list adds to the number o f possible combinations. Subsection 4.3.1 discusses the size o f the solution space and its lower and upper bounds without the kicker limitation. The effect o f the limited number of kickers on the size is included in 4.3.2. 4.3.1 Size without Kicker Limitation Consider the example in the subsection 4.2.1, where the number o f possible combinations was calculated as the product o f the number of permissible cut patterns for each clean piece. 5 • 5 • 3 • 2 • 71 • 1 • 80 • 80 • 2 = 136,320,000 In mathematical terms, this can be written as follows. a= The number o f possible combinations P„ = The number o f permissible patterns for clean piece n according to the given cut list a=P,p2 • ...fin- . . . A V « = 7 , N It should be noted that for clean pieces without any permissible pattern, fin is considered as one because it does not increase the number o f combinations, fin is highly variable and depends on the data of the clean piece and the required cut list lengths. This is obvious in the example of subsection 4.2.1 that has a clean piece with 2 permissible cut patterns and another clean piece with 80 cut patterns. In 4.2.1 it was also mentioned that a is not the "true" size of the solution space because it is the number o f possible combinations without cut list quantity constraints. Once one pattern is considered for a clean piece and the quantities o f the cut list are reduced, fewer items are left for the next clean piece and the number o f permissible patterns w i l l be less than fi„ for the case when all cut list items were available. In other words, fin becomes progressively smaller as clean pieces are processed by the program. For example, i f all nine items o f a cut list with 10 items are produced, only the tenth item can be used for the pattern generation of the next clean piece. The number of these patterns is less than when all 10 items were available. On the other hand, a cannot be considered as the true or minimum upper bound either. The reason is that the order of clean pieces w i l l make a difference in the number o f cut patterns. Wi th each order of clean pieces the true values o f the variable w i l l be different for each clean piece and denoted as #,/. There w i l l be JV7 orders o f clean pieces. The size can then be written as: N\ N Size = YJ[Pnt (11) /=1 n=l However, the variable fint cannot be "practically" specified ahead o f time in the online production of the strips. Consequently, the size cannot be precisely calculated. Hence, instead it might be useful to find a lower and upper bounds for the size using another approach as follows. First a simple lower bound can be calculated by assuming that each clean piece can be cut at least in two different ways based on the items of the cut list. Even with the quantity constraint included, this assumption can be considered valid because N WPnt ^ 2 ^ u s u a l l y holds. This conservative assumption is based on the earlier discussion o f Figure 4.2 and the observation of the industrial data depicted in Figures 3.1 to 3.7 and 3.8. In other words, statistically speaking, in the long run two items can be cut from any clean piece. Thus, for N clean pieces, there w i l l be 2N number o f possible combinations. In addition, this is without the ^ operand o f equation (11). Hence, 2N can be considered as a lower bound o f the size. Problems with 2N complexity are NP-hard and computers could run for centuries to find the optimal solution [43]. Next, an upper bound for the size is calculated. Here all o f the clean pieces are assumed to have the highest grade (A or 1). The vector of demand v is defined as follows. v = a vector of size T containing a permutation o f all required lengths v = ( L 1 , . . . . , L l , L2,....,L2 , ,Lm,....,Lm, , L u L M ) Q^imes Q2times Qmtimes QMtimes It was mentioned earlier that T is the total quantity o f the cut list. The number of all possible permutations for the vector v would then be [43]: Size = f M \ m=l M M (12) Y[QJ UQJ m=l m=l A vector ( P ; , P2,.---» P«v-j PJV) is written instead o f the set { P } o f the clean pieces. Essentially, this is the vector o f available stock. A l l possible permutations o f this vector must be considered in order to make a match between this vector and the vector of demand (v). The number o f possible permutation for the vector of available stock is N! and w i l l increase the size to that given by equation (13) as follows. ( M Size = N\-T\ m=l M M (13) m=l For the example in 4.2.1 equations (12) and (13) w i l l yield: (12) => 4!-8!-7! 121,645,100,408,832,000 4,877,107,200 = 24,942,060 (13)=* 10! 19! _ 3,628,800 19! 4!-8!-7!~ 4!-8!-7! = 90,509,747,328,000 The latter figure shows that the size in equation (13) is a valid but rather a wide upper bound for the size since the calculation is sequence dependant as discussed earlier in this subsection. In this work, equation (13) is considered as the upper bound and 2N as the lower bound o f size for problems with no kicker constraint. The next subsection addresses the upper and lower bound for the cases with kicker limitation. 4.3.2 Size with Kicker Limitation It was mentioned earlier that the limitation o f kickers increases the complexity o f the problem. Thus, the upper bound for the size of the solution space has to be adjusted but the lower bound can remain the same as 2N. Assuming that there are R kickers available, then all cut lists have to be o f size R or smaller. U = The number of items that need to be cut. {Y} = The length set of all U items to be cut (original cut list lengths o f U items). {Y} = {y ; ,y2 , . - - ,y» , ••-,yu} {L} = The set o f cut list lengths as a subset o f U = {Lj, L ^ , . . . . , Lr, LR} {L} c {Y} R < the number of kickers and 0 < R < U = The number o f R combinations o f a set with U elements. (u Ul Rl(U-R)\ For example i f there are 8 kickers then R =8 and U=20, then: 20! R\(U-R)\ 8! 12! « 5 . 0 8 x l 0 9 Therefore, the equations (12) and (13) w i l l turn into equations (14) and (15) respectively. Size = Tl Ul R\ (U-R)l ( R \ (14) Size = £ ! ( £ / - / ? ) ! (15) A l l o f the equations (12) to (15) produce very large numbers for a problem with cut list quantity figures that are common in industry. If the quantities o f the items on the cut lists are: Q , .= 3000, Q2 = 2500, Q 5 = 2000, Q4 = 1500, Q5 = 1000 Equation (12) yields: ( M \ m=l 10,000! M n e . 3000! • 2500! • 2000! • 1500! • 1000! S 6 . 5 6 1 0 6699 If the number of clean pieces required to produce the cut list is N = 5000, which is a common figure in industry, then equation (13) yields: \ m = l 1 s 5000!• 6.56-10 6 6 9 9 = 2.77 • 10 2 3 0 2 5 M t m=l A n d this very large number has yet to be multiplied by The above derivation with the aid o f numerical examples illustrated that the solution space o f the combinatorial problem is massively large. It quickly grows too large, even for small problems, to be solved by enumeration. The prospect of availability and use of a much faster C P U still leaves the problem well beyond practical limits for foreseeable future. 4.4 Concluding Remarks The analysis in this chapter illustrated that it is not practical to solve the problem in the offline case by exact methods. This is because the size o f solution space grows dramatically as the number of clean pieces grows. In addition, because even problems with as small as 10 clean pieces might take more than a minute to be solved by the exact method, it is not useful to consider a buffer before the chopsaw. The real time characteristic of the system requires very fast decision making. Hence, heuristic or artificial intelligence solution techniques seem to be a viable i f not the only option to optimize a problem o f this complexity. The following chapters present the developed algorithms to solve the problem in real time. CHAPTER 5 Classical 1D-CSP Optimization by Crisp and Fuzzy Ranking Methods In chapter 2, the classical one-dimensional cutting stock problems (classical 1D-CSP) were defined. Such problems deal with cut lists without the grade requirement such as Table 2.1. A n optimization algorithm with a new approach for solving such problems is presented in this chapter. One advantage o f this approach is that it can be extended to solve the "real time 1D-CSP". The real time optimization algorithm thus developed is presented in chapter 7. This chapter consists of seven sections. The procedure o f the algorithm, which is based on ranking o f the cut lists, is explained in section 5.1. Different cut list ranking methods can be used. Two crisp methods are presented in section 5.2 and two fuzzy methods in section 5.3. The experimental results o f these ranking methods are provided in section 5.4. Section 5.5 describes an adaptive fuzzy ranking method as an improvement over the others already investigated. The adaptive fuzzy ranking is tested in section 5.6. Section 5.7 provides the concluding remarks for the chapter. 5.1 Classical 1D-CSP Optimization Algorithm The developed algorithm utilizes the fact that values on the cut list are not merely numbers. Besides length and quantity data, they contain other useful information. For example, a grade A item on the cut list longer than half the length o f a strip might be hard to find especially i f the general quality of the raw material is low. Thus, we need to first produce such items whenever possible and then think o f how best to cut the leftover portion of a strip. In general, with or without grading, longer items are usually harder to plan and fit on the pattern than the shorter ones. Other useful information can be deduced from the quantity data in the cut list. Higher quantity values for an item indicate that this item, i f planned improperly, could contribute towards more waste. It was discussed in section 1.3 that it is desirable to have a mix of items on the cut list rather than one or very few items. A l l such information is embedded in the numerical values o f a cut list and in our interpretation of the data, which in fact we have used to develop the algorithm. Hence, one essence o f the algorithm is that it extracts information from the numerical values in the cut list and the inventory build-up o f each item. It then ranks the items based on their influence in generating waste. Many different approaches can be used to rank each item on the cut list. In this work, five different crisp and fuzzy ranking methods are developed for the 1D-CSP optimization. A l l these methods are explained and tested for performance in this chapter. But first the procedure o f the optimization algorithm is described as follows. Loop I: Iterate until all required quantities are cut. 1) Rank the cut list (higher value means higher rank). Use One of the following ranking methods: • Crisp 1 or 2 (described in section 5.2). • Fuzzy 1 or 2 (described in section 5.3). • Adaptive fuzzy (described in section 5.5). 2) Pick the highest rank item. 3) Find the number o f times this item can be cut out o f one strip (e.g. Strip Length /Item Length = 3.4). 4) Truncate the above number (e.g. 3.4 is truncated to 3). 5) Iterate with indexing from 1 to this truncated number (e.g. For Index = 1 to 3, do Loop II). Loop II: i . Calculate the leftover as Leftover = Strip Length - Index x Length of highest rank Item i i . F ind the waste from this leftover when testing remaining items on the cut list. i i i . Pick the case with minimum waste. iv. Compare with the minimum waste o f the previous index. v. Pick the index with the minimum waste (the Minlndex) and store the cut pattern, then loop. End Loop II 6) Cut based on the pattern that is stored for the final Minlndex in Loop II. i . Calculate the number o f strips to cut with this pattern as Number of strips = Quantity of highest rank item /Minlndex i i . Cut all these strips based on the stored cut pattern. i i i . Record waste. 7) Update the quantities o f the cut list. End Loop I The algorithm starts with Loop I and using any one of the five methods (details to be discussed later), ranks all items o f the cut list and picks the one with the highest rank. Then, it calculates how many times this item can be cut from a strip, which determines how many times a second loop (Loop II) should iterate to find the least waste cut pattern. This pattern is repeatedly used to produce all the required quantities o f the highest rank item. After the quantities on the cut list are updated, the cut list is re-ranked and the iteration of Loop I resumes until all items are produced, that is all the cut list quantities diminish to zero. The different ranking methods are explained in the following sections. 5.2 Crisp 1 and 2 Methods The rank of each item on the cut list can be calculated using many different crisp formulas. First, a very simple crisp function for the ranking was considered that assigns a rank value equal to the product o f length and quantity of the item. Thus: Rank of the item = Item Length x Item Quantity This is referred to as "Crisp 1" ranking method. After some trial and errors, this was modified to "Crisp 2" method as: Rank of the item = (Item Length/Strip Length) x (Item Quantity/Total cut list Quantity) + (Item Length/Strip Length) The denominators were introduced in this formulation to normalize the length and quantity o f each item. The third term in the formula was added to give further emphasis to the effect of item length on the rankings. It is not easy to define a crisp formula with reasonably good performance and it might need many trial and errors for fine-tuning. One way of overcoming this difficulty is to use fuzzy methods to determine the ranks o f the items that tend to need less trial and error and are more effective once established. Different fuzzy ranking methods are described in the next sections. 5.3 Fuzzy 1 and 2 Methods Two different approaches are presented in this section, namely "Fuzzy 1" and "Fuzzy 2". Fuzzy 1 was an initial attempt to define some linguistic descriptions. The linguistic classification can be deduced in many different forms. Interviews with the factory operators, reviewing the industrial cut lists lengths and quantities, strip lengths, and the frequency distribution analysis of the industrial data such as chapter 3, provided the insight necessary to define the classes used in the fuzzy methods. For both Fuzzy 1 and Fuzzy 2 methods four length and three quantity classes are considered. The test results, which w i l l be presented later, illustrate that the defined classes are satisfactory. It w i l l also be shown later in this chapter that much improved classification of the fuzzy variables is possible. The Fuzzy 1 and 2 approaches w i l l now be detailed as follows. 5.3.1 Notation and Definitions Notation X : The lengths universe o f discourse. Y : The quantities universe o f discourse. Z : Output fuzzy set (Rank). A , B , C , D : The length fuzzy subsets. A , B , C , D c X E , F , G : The quantity fuzzy subsets. E , F, G c Y [a,b] Interval of real numbers from a to b. x: A n element in X . y: A n element in Y . z: A n element in Z . \i: Membership function for fuzzy subsets (A , B , C, D , E , F, and G) . D o B : Degree of Belief. c f : Certainty factor. Definitions For both Fuzzy 1 and Fuzzy 2 methods, the following can be written: A = { ( X , , U A ( X , ) ) } V X , € X B = { ( X , , U B ( X ( ) ) } V x , e X C = {(x,,nc(xi))} V x,e X D = { ( X , - , H D ( X O ) } V x,e X E = {(y.-,ME(y/))} V y , e Y F = { ( y ; . M y , ) ) } V y , e Y G = { ( y . v M y O ) } V y,e Y a / : Length is Short Ct2 : Length is Medium 0L3: Length is Long CLf: Length is Very Long P / : Quantity is L o w P2: Quantity is Medium P5 : Quantity is High DoB(cty) = fiA(x,) D o B ( a 2 ) = H B ( X , ) DoB(aj ) = Hc(x,) DoB(ow) = ^ D ( X , ) D o B ( P / ) = |XE(yO DoB(p 2 ) = m<y/) D o B ( P 5 ) = M<s(yO Z = {Zi, Z2, Z3, Z4,Z5} or z , e Z where z, are rank singleton values for the five output classes: Lowest (zi), L o w (z2\ Medium (z3), High (z4) and Highest (zj). 5.3.2 Membership Functions for Fuzzy 1 The universe o f discourse for Fuzzy 1 are X = [0, 6000] and Y = [0, 30000]. Fuzzy subset for lengths within class S H O R T : 100 8 0 0 - x , . 0 < x ; <380 380 <x ( . <800 4.2 0 x,. >800 Fuzzy subset for lengths within class M E D I U M : 0<x, . <500 x,. - 5 0 0 500 < x ; <800 3 M x , ) = < 100 800 < x , < 1000 1 8 0 0 - x ; 8 0 x,. >1800 1000 <x ( . <1800 0 x.. - 1 0 0 0 8 M * , H 1 0 0 3 0 0 0 - x , . 0 0<x, . <1000 1000 <x,. <1800 1800 < x,. < 2500 2500 < x ( <3000 x ; >3000 Fuzzy subset for lengths within class V E R Y L O N G : u D ( x , ) = -0 0 < x ; <2500 x ; - 2 5 0 0 100 2500 <x,. <3000 x ; >3000 Fuzzy subset for quantities within class L O W : My,) = ' 100 700 - y , 0 0<y, . <100 100 < y ; <700 y, > 700 Fuzzy subset for quantities within class M E D I U M : v-F (y,) = < 0 y , - 1 0 0 100 2000 - y , 10 0<y,. <100 100<y,. <700 700 <y,. <1000 1000 < y, < 2000 y . > 2000 My,) = -0 0 < y ; <1000 y , - 1 0 0 0 10 100 1000 < y,. < 2000 y ; > 2000 The above classes can be visualized in the membership graphs o f Figures 5.1. Simple truncated triangular shapes represent each class and produce the fuzzy definitions at each boundary between adjacent sets. Note that the initial sets do not overlap by more than one adjacent set. Other shapes can be considered for the functions but the truncated triangular shapes are chosen for their simplicity and efficiency. u 09 Q CQ o D ISO 800 500 1000 1800 2500 3000 Short Medium Long Verj Long 100 Quantity Classes Figure 5.1. Linguistic length and quantity classes for Fuzzy 1. 5.3.3 Membership Functions for Fuzzy 2 It was mentioned earlier in this section that many different classes can be defined for the fuzzy methods. A variety of cut list lengths, quantities, and standard lumber lengths from the company data were used to define the Fuzzy 2 classes. The quantity values, however, were normalized such that the classes adapt themselves to various cut lists. The universe o f discourse for length is: X = [0,6000] Fuzzy subset for lengths within class S H O R T : M x , ) = 100 8 0 0 - x ; 4.2 0 Fuzzy subset for lengths within class M E D I U M : 0 x ; - 5 0 0 M x , ) = < 100 1 8 0 0 - x ; 8 0 Fuzzy subset for lengths within class L O N G : Co M x , ) = < x.. - 1 0 0 0 8 100 3 0 0 0 - x ; 0<x, . <380 380 <x,. <800 x,. >800 0 < x ; <500 500 <x,. <800 8 0 0 < x . <1000 1000 <x,. <1800 x,. >1800 0<x,. <1000 1000 <x,. <1800 1800 < x,. < 2500 2500 <x ( . <3000 x ; >3000 M x , ) = 0 x.. - 5 0 0 25 100 0<x, . <500 500 <x,. <3000 x ; >3000 The universe o f discourse for quantity is: Y = [ 0 , 1 ] Quantity values are normalized by the current total quantity, y, = Normalized quantity values Current Quantity of the Item For all the quantity classes y, = • Current Total Quantity Fuzzy subset for quantities within class L O W : My,) = 100 0.5 - y , 0.35 0 0 < y , < 0.15 X100 0.15 < y , < 0.5 y ( > 0 . 5 The fuzzy subset for quantities considered in class M E D I U M : 0<y,. <0.15 • x l O O My,) = -0 y , - 0 . 1 5 0.3 100 0.85 - y , 0.3 x l O O 0.15 < y , < 0.45 0.45 < y,. < 0.55 0.55 <y,. <0.85 y,. > 0.85 Fuzzy subset for quantities considered in class H I G H : fO 0 < y,. < 0.5 My,) = y , - 0 . 5 0.35 100 x lOO 0.5 < y , <0.85 y,. >0.85 Figures 5.2 illustrates the above membership functions. Comparing this figure with Figure 5.1 it is clear that in Fuzzy 2, only the quantities were normalized. Whi le the lengths, the longer ones were given increased emphasis. Note that for Fuzzy 2, the support of the "Very Long" class starts at 500 mm and gradually increases to 100 percent belief for a length of 3000 mm. This large degree o f overlap across several adjacent sets means that longer lengths have been given a greater importance. Similarly, the normalized quantity classes have been moved in Fuzzy 2 to provide higher ranking for those items that have medium to high quantities relative to the total quantity o f items to be cut. Next subsection shows how the Fuzzy 1 and Fuzzy 2 classes are used in the rule base to infer a linguistic rank for each item. 100 u o o & Q ) 500 ldoO 380 800 1800 2500 3000 * Short : : - '• Medium Long Very Long Length Classes IS 100 u 03 Q . 05 0.45 0.55 Low Medium High Normalized Quantity Classes Figure 5.2. Linguistic length and normalized quantity classes for Fuzzy 2. 5.3.4 Inference Rules for Fuzzy 1 and Fuzzy 2 The rule base for both fuzzy methods is as follows. If (a ; and P / ) Thenz ; ( c f / = l ) I f ( a y a n d p 2 ) O r ( a 2 a n d p 7 ) O r ( a 3 a n d P / ) T h e n z 2 ( c f 2 = l ) If ( 0 4 and P / ) Or (a^ and p^) Or (a ; and P5) T h e n z 5 (cfj = l ) If ( a i and p^) Or (a2 and Pj) Thenz* (c f*= l ) If (a* and P^) Or (a? and $3) Or (oc* and P5) Thenz j ( c f } = l ) The following singleton values for the output set were chosen through trial and error fine-tuning. However, other numbers can also be used. Z = {1,3, 6, 9, 12} A l l c f parameters are assumed 1 and the following single rule is used for each output state. DoB(z,)= cf ; • max [min(DoB(ct,) , DoB(p*)), • • • , min(DoB(a,) , D o B ( P * ) ) ] V i = l , . . . . , 5 The rule base can be presented by the Fuzzy Associative Map ( F A M ) as shown in Table 5.1. The F A M and rank singleton values are the same for both Fuzzy 1 and 2 methods. They were established through trial and error and examination o f results. Table 5.1. Fuzzy Associative Map for Fuzzy 1 and 2. ^ ^ \ L e n g t h Quantity Short Medium Long Very Long Low Lowest L o w L o w Medium Medium L o w Medium High Highest High Medium High Highest Highest Lowest = 1, L o w = 3, Medium = 6, High = 9, Highest = 12 5.3.5 Defuzzification Method The rules presented in the previous subsection together with output singletons are used to determine the rank o f each item in each loop of the algorithm. However, in order to produce a crisp output, a defuzzification method is necessary. The Weighted-Average defuzzification method [44] is used due its simplicity and provides satisfactory results shown later in this chapter. This method is as follows. 2 [ D o B ( z , ) z , ] Rank (x,y) = ^ — f X D o B ( z , ) 1=1 Note that the total number o f output fuzzy sets is five (f= 5). 5.4 Testing Crisp and Fuzzy Methods The test results o f the classical 1D-CSP optimization algorithm using all four Crisp 1, Crisp 2, Fuzzy 1 and Fuzzy 2 ranking methods are presented in this section. Here, to fit the category o f classical 1D-CSP, the grading, the defects and the real time production were not considered at this point. The efficiency of the optimization algorithm was determined by comparing the results with the optimal solution obtained using AMPL® [22]. This software implements the approach of Gilmore and Gomory [10]. In order to test the optimization algorithm with all four crisp and fuzzy methods, sample problems from industrial data have been used. Out of the many experiments carried out, the results of only 12 cut lists have been shown in Table 5.2 in the interest of space. The deviations o f the optimization results for the four ranking methods from the AMPL® optimal solution are recorded in the last four columns o f the table. To compare the results, the deviations are calculated as . . "Class ica l ID-CSPsolu t ion" - "AMPL® solution" Deviation = — " A M P L solution" Table 5.2. Results o f 12 cut list samples for four ranking methods. Results AMPL® Optimal Solution Solution by Classical 1D-CSP Optimization with 4 different ranking methods % Deviation from the Optimal Solution Sample Sets Needed strips Crisp 1 Crisp 2 Fuzzy 1 Fuzzy 2 Crisp 1 Crisp 2 Fuzzy 1 Fuzzy 2 1 3256 3285 3282 3283 3317 0.89 0.80 0.83 1.87 2 2137 2157 2213 2213 2204 0.94 3.56 3.56 3.14 3 2576 2633 2614 2624 2635 2.21 1.48 1.86 2.29 4 1109 1139 1152 1165 1152 2.71 3.88 5.05 3.88 5 10240 10641 10501 10517 10742 3.92 2.55 2.71 4.90 6 11963 12126 12043 12043 12568 1.36 0.67 0.67 5.06 7 4985 5058 5049 5049 5058 1.46 1.28 1.28 1.46 8 8975 9356 9234 9263 9263 4.25 2.89 3.21 3.21 9 4141 4155 4155 4155 4141 0.34 0.34 0.34 0.00 10 14400 14656 14652 14652 14584 1.78 1.75 1.75 1.28 11 10902 11045 11174 11184 11140 1.31 2.49 2.59 2.18 12 5390 5500 5410 5429 5397 2.04 0.37 0.72 0.39 Average 1.93 1.84 2.05 2.47 Standard Deviation 1.19 1.22 1.42 1.62 In examining the results in Table 5.2, it is apparent that all four methods produce reasonably good results, with an average deviation from the optimum of less than 3%. In addition, the small standard deviation shows that the good performance o f the algorithm holds for all sample problems and is stable. In all cases, it is clear that AMPL® does marginally better and this is because the AMPL® solution is an exact one. However, A M P L is not extendable to real time situation whereas the proposed solution is. This w i l l be shown in chapter 7. In addition, it would appear that the fuzzy approaches are more volatile than the two crisp approaches when comparing their respective standard deviation o f 1.19 and 1.62 percent. It is worthy to note that, as shown and highlighted in the table, the Fuzzy 2 method did produce one result identical to the true optimum and a second result within 0.39 percent o f it. However, each ranking method produces better result for some of the cut list samples than others. This suggests that an adaptive approach to vary the fuzzy set definitions could provide improved results for the fuzzy methods over the crisp ones. Before elaborating more on this issue, it is important to investigate the algorithm run time because the ultimate goal is to develop a fast optimization algorithm for online application. The computer time to solve each o f the above samples was less than a second for all solutions. The optimization algorithm with any one o f the four ranking methods needed less computer time and C P U usage in comparison to the AMPL® solver. The run time and C P U usage for one o f the data samples is shown in Figure 5.3. The first peak in the graph is for the optimization algorithm with the Fuzzy 2 ranking method while the second broader and higher peak illustrates the AMPL® run time and C P U usage. Clearly, the developed optimization approach has superior performance both in terms o f C P U consumption and computer time, and thus has a great prospect for online implementation. CPU Usage History Optimization algorithm 0 ° A M P L Figure 5.3. C P U usage for the classical 1D-CSP and AMPL®. Next section introduces and tests the adaptive fuzzy ranking of the cut list. 5.5 Adaptive Fuzzy Ranking Method The fluctuation in deviation from optimum for all four crisp and fuzzy ranking methods suggested the use of an adaptive fuzzy ranking that could improve the results by adjusting itself to the input data. In the Fuzzy 2 method the normalized quantity classes mean that the algorithm w i l l produce the same rank values for various problems that have equal quantity proportions. Thus, classes w i l l not need tuning for different problems with respect to quantity and w i l l still produce stable results. In retrospect, it might also be prudent to normalize the length classes. Therefore, an adaptive fuzzy method was conceived, the definition o f which follows. 5.5.1 Membership Functions for the Adaptive Fuzzy Method Same notation as in the previous section is used to provide the definitions in this subsection. The universe of discourse for length and quantity classes in the adaptive fuzzy approach are both between zero and one. X = [0, 1] and Y = [ 0 , 1] The definition o f both length and quantity classes are in the normalized form and the classes adjust or adapt themselves to various cut list data. Each have three classes as follows. r ,,^1. i . i . , Length of the item For all the length classes x . = - — Strip Length Fuzzy subset for lengths within class S H O R T : 0 . 5 - x , M X / ) = < 0.5 •xlOO 0 0<x, . <0.5 x ; >0.5 Fuzzy subset for lengths within class M E D I U M : 0 x ; - 0 . 2 5 0.25 0.75 - x •xlOO 0.25 i - x l 0 0 0 < x ; <0.25 0.25 < x,. < 0.5 0.5 < x , < 0.75 x , >0.75 0 < x, < 0.5 M x , ) = j x ( - 0 . 5 I 0.5 -xlOO x,. >0.5 For all the quantity classes y,- = Current Quantity of the item Current Total Quantity Fuzzy subset for quantities within class L O W : My,) = < 0.5 - y, 0.5 0 x lOO 0<y,. <0.5 y , * 0-5 Fuzzy subset for quantities within class M E D I U M : My,) = -0 y, - 0.25 0.25 0.75 - y , 0.25 0 0 < y, < 0.25 x l O O 0.25 < y , < 0.5 x l O O 0.5<y,. <0.75 y, > 0.75 Fuzzy subset for quantities within class H I G H : My,) = < 0 y , - 0 . 5 I 0.5 xlOO 0 < y ( <0.5 y, ^ 0.5 The above classes can be visualized in the membership graphs of Figures 5.4. o & Q Normalized Length Classes <4—I Normalized Quantity Classes Figure 5.4. Adaptive Fuzzy length and quantity classes. 5.5.2 Inferencing and Defuzzification for Adaptive Fuzzy The adaptive length and quantity classes are used in the rule base to infer a linguistic rank for each item. The rule base is as follows. If (a; and p;) Then z; (cf; = If(a/andp 2)Or((X2andp7) Thenz2 (cf? = If(aiandp/)Or(a2andP2)Or(a7andp3) Thenzjj (cf5 = If (a* and P^) Or (a2 and Pj) Then z4 (cf4 = If (a? and p3) Then z5 (cf5 = The rule base is also shown as F A M in Table 5.3 including the output singleton values of the set Z . Z = {1,5, 10, 20, 25} The set Z was arrived at through trial and error. A l l the other aspects o f the adaptive approach, such as the denazification method, are the same as for Fuzzy 1 and 2. Table 5.3. Fuzzy Associative Map for the adaptive method. ^^^^Length Quantity^^^ Short Medium Long Low 1 5 10 Medium 5 10 20 High 10 20 25 5.6 Testing the Adaptive Fuzzy Method The same data samples that were used to test the previous four ranking methods were considered here also and the results o f the adaptive fuzzy approach were added to Table 5.2 for ease of comparison. The combined results of all five crisp and fuzzy approaches are reported in Table 5.4. For all five methods, the average deviation from the optimum is less than 2.47 percent with a small standard deviation o f less than 1.62. However, only the adaptive fuzzy method is more stable as it produces good results for all the sample cases. The adaptive method has an average deviation o f 1.46% from the AMPL® optimum solution and a standard deviation o f 1.04 that are both smaller than the corresponding values for Crisp 1, 2, Fuzzy 1, and 2 methods. The adaptive fuzzy ranking provided improved results over the others tested as it uses dynamically updated cut list information. Generally, using any o f the five ranking methods, the optimization algorithm performs better with long cut lists that have a variety o f different lengths with somewhat large quantities. Cut list with many items allows the algorithm to generate large number of patterns, which improves the prospect of finding a better pattern, and thus results in smaller waste. In contrary, the sample set 4 has few items that results in the largest deviation from the optimum among all the sample sets. A s highlighted, 1109 strips are used to produce the few items o f its cut list. Table 5.4. Results for all five ranking methods. Sample Sets AMPL® Optimal Solution Solution Classical 1D-CSP < with 5 different rani by Optimization cing methods % Deviation from the Optimal Solution Crisp 1 Crisp 2 Fuzzy 1 Fuzzy 2 Adaptive Fuzzy Crisp 1 Crisp 2 Fuzzy 1 Fuzzy 2 Adaptive Fuzzy 1 3256 3285 3282 3283 3317 3282 0.89 0.80 0.83 1.87 0.80 2 2137 2157 2213 2213 2204 2157 0.94 3.56 3.56 3.14 0.94 3 2576 2633 2614 2624 2635 2624 2.21 1.48 1.86 2.29 1.86 4 n o y 1139 1152 1165 1152 1152 2.71 3.88 5.05 3.88 3.88. 5 10240 10641 10501 10517 10742 10501 3.92 2.55 2.71 4.90 2.55 6 11963 12126 12043 12043 12568 12043 1.36 0.67 0.67 5.06 0.67 7 4985 5058 5049 5049 5058 5037 1.46 1.28 1.28 1.46 1.04 8 8975 9356 9234 9263 9263 9174 4.25 2.89 3.21 3.21 2.22 9 4141 4155 4155 4155' 4141 4155 0.34 0.34 0.34 0.00 0.34 10 14400 14656 14652 14652 14584 14656 1.78 1.75 1.75 1.28 1.78 11 10902 11045 11174 11184 11140 11016 1.31 2.49 2.59 2.18 1.05 12 5390 5500 5410 5429 5411 5412 2.04 0.37 0.72 0.39 0.41 Average 1.93 1.84 2.05 2.47 1.46 Standard Deviation 1.19 1.22 1.42 1.62 1.04 The speed o f the adaptive fuzzy approach is also excellent and less than one second for all the sample sets. Despite the small deviation from the optimum solution, the speed and the extendibility to real problem suggest that the proposed adaptive fuzzy rule-based algorithm can be applied to the online real time decision making process. 5.7 Concluding Remarks A n optimization algorithm for the classical 1D-CSP with five different ranking methods has been developed, amongst which the adaptive fuzzy ranking was the most stable and produced reasonable and near-optimum results. The speed and required computer C P U resources are promising. To extend this optimization algorithm to the real problem at hand, the first step is to incorporate quality issues such as defects, grading and downgrading. But first a tool is needed to generate permissible cut patterns for each strip online in real time. The developed algorithm for cut pattern generation is presented in the next chapter. CHAPTER 6 A Recursive Pattern Generator This chapter has three sections. A novel recursive approach for generation of permissible cut patterns for a clean piece is explained in section 6.1. This recursive algorithm attempts to generate all permissible cut patterns but the embedded criteria prune the ineffective and unnecessary patterns in order to speed up the algorithm and make it suitable for online application. The test results for this recursive algorithm are reported in section 6.2. Section 6.3 is the concluding remarks for this chapter. 6.1 A Recursive Algorithm for Cut Pattern Generation This section presents the recursive algorithm developed for generating the permissible cut patterns for each clean piece o f the strips whose defects and grade variation have already been marked. This algorithm is designed for online application. Due to the high paced production o f the strips, the pattern generation algorithm has to be executed once for each clean piece of the arriving strip in real time. In addition to high speed, the algorithm must be capable of generating permissible patterns that are formed by downgrading and use o f neighboring sections. This turns out to be a challenging problem because sometimes a very large number of permissible cut patterns exists for a clean piece, which is time consuming to generate and not at all ideal for online applications. Furthermore, it was shown in earlier chapters that the features such as downgrading and use of neighbouring sections complicate the pattern generation because any part o f the neighbouring sections can be added to a section based on the cut list sizes. The recursive algorithm presented here is designed to include all these features in the cut pattern generation and to produce the entire or a selected subset of all permissible patterns. It should also be noted that recursive algorithms normally require more computation than the iterative algorithms. For example, a recursive algorithm to compute Fibonnaci Numbers requires more computation than an iterative algorithm to compute the same [43]. Although this might be true for most recursive algorithms, but sometimes it is preferable to use recursive schemes and in particular this is true when the recursive approach is easier to code and implement than the iterative one. This is the case for the problem at hand. This combinatorial problem needs a very complex generally untraceable if-then iterative algorithm to generate all the permissible patterns. Therefore, despite greater efforts needed to write the code, a recursive approach is a practical way to develop an algorithm for generating patterns. The only concern may be computation time and this w i l l be addressed later. To describe the algorithm, first a simple example is considered as in Figure 6.1 where all permissible cut patterns are given. A 1100 mm clean piece with only two sections has to be cut based on the given cut list requirements. Column 1 Column 2 Column 3 ! Pattern No. ' 900B) 1 Patterns 400C 600B 350B-550C 550A 600B 350B 550C 400C 400C Stock: 900B 600B - 350B 6 0 0 B - 4 0 0 C 350B - 600B 350B - 350B - 350B 350B - 350B - 400C 1100 mm Clean Piece B 500 mm 600 m m Demand: Cut List Items Length (mm) Grade Quantity 1 1900 A 1226 2 1200 A 770 3 1000 A 500 4 550 A 2880 5 900 B 340 6 600 B 3831 7 350 B 5098 8 1800 C 2057 9 550 C 800 10 400 C 222 26 L . Figure 6.1. A n example for recursive algorithm. The algorithm starts from the left of the clean piece and by using the items on the cut list in a top-down order it generates the patterns one at a time. In a column format from left to right, all 26 permissible cut patterns are generated as illustrated in the figure. These patterns are generated in a depth-first search format, starting from the top o f column 1 and moving to the bottom of column 3. In this example only 3 columns were necessary. A new pattern is generated once it is no longer possible to move to the column on the right. This happens in generation o f each pattern once the end of the clean piece is reached or once no other item can be fitted within the leftover. The generated pattern is recorded and then, to generate a new pattern, the algorithm steps back one column to explore other branches. Then, the next possible item in the cut list is selected. I f a new item fits the length and grading requirement, a new branch is formed to go to the next column on the right, otherwise the algorithm steps back one more column. Each branch is searched to its utmost right column. Once all the branches of a column are exhausted, the algorithm steps back one column towards the left. This continues until column 1 is reached. In this column, all possible-to-fit items o f the cut list are selected once. Then the procedure is terminated. The forgoing was a brief description o f the procedure for the example. The description did not include pruning. However, without any pruning, the exhaustive search w i l l generate a very large number of cut patterns for clean pieces that are longer in comparison to the items in the cut lists. Generating a very large number o f patterns could take a long time - not suitable for online application. Pruning techniques can be used in the procedure to eliminate undesired patterns and decrease the run time of the algorithm. The pruning can occur during the depth-first search at any level (or column as referred in Figure 6.1) and forces the algorithm to step back one column without having explored the current route to the end. Therefore, the pruning allows the generation o f a potentially useful subset o f all permissible patterns. Many different pruning criteria can be implemented, such as: 1. Zero-waste: Patterns with zero waste are generated. 2. Least-waste: Patterns that have a waste smaller than or equal the waste o f the previous pattern for the clean piece w i l l be generated. 3. Total-rank: In previous chapter, the items on the cut list were ranked. Total-rank is the sum of the ranks of the items that form a pattern. The patterns with higher than or equal total-rank than the previous pattern for the clean piece w i l l be generated. However, because prior to forming the pattern in full the value o f total-rank is unknown, an estimate of total-rank is used for pruning. This estimate is calculated as Estimate = Total-rank so far + Length o f Leftover * ^ (No. o f times that each item fits on the Leftover x Item Rank) For all items of the cut list ^ (No. of times that each item fits on the Leftover x Item Length) For all items of the cut list 4. Least-downgrading: Patterns that have equal or better grade-utilization than the previous pattern for the clean piece w i l l be generated. 5. Least-downgrading of grade A : Grade A sections are used for grade A items only. These are not the only possible pruning criteria and many others can be implemented due to the structure o f the algorithm. The first and third criteria are used in this chapter and the combination of the second and third criteria are used for the development of the real time optimization algorithm in chapter 7. Although, there is no specific reason for selecting the two pruning criteria in this section, but the selection of the pruning criteria must meet the overall objective o f the optimization algorithm. The intention in this chapter is only to prove that once the algorithm is equipped with proper pruning techniques it can be implemented for real time and online systems where a cut pattern must be chosen well within one second. The overall objective in this work is not to cut a single strip with minimum waste but to produce the entire cut list in such a manner. Whether minimizing waste over the production o f the entire cut list or just minimizing waste over a single strip is desired, the recursive procedure is the same and the only difference is the pruning criteria used. The algorithm and how the pruning criteria are implemented are explained in detail next. The algorithm has two parts, an initial main function and a recursive function referred to as 'CutChoice ' . Initialize For all clean pieces of the strip Call Recursive function 'CutChoice' Record the output data of the Recursive function End of Initial function Recursive Function 'CutChoice' If it is the end of the clean piece Check the pruning criteria and compare with best choice so far, if a pass Record this new pattern Else For all items on the cut list, If the grade and length fit Do the cut, update, If pruning criteria allow, Call CutChoice Ignore the last cut and update If the length does not fit then try both options below: Option 1: No downgrading of neighbouring sections on the clean piece Dump the piece and Update waste record Call CutChoice Ignore the dump and update waste record Option 2: Try to use neighbouring section/s by downgrading If the grade offirst neighbour fits If adding the length offirst neighbour is sufficient Downgrade, do the cut, Update records If pruning criteria allow, Call CutChoice Ignore the last cut and update Else if length offirst neighbour is not sufficient If the grade of second neighbour fits If adding the length of second neighbour is sufficient Downgrade, do the cut, Update records If pruning criteria allow, Call CutChoice Ignore the last cut and update Else try 3rd neighbour and so on till there is no more neighbour, then is the last section of the clean piece, dump the leftover piece Else if last item on cut list, update waste, Call CutChoice to go to next clean piece End of recursive function The recursive function is called from within itself as many times as necessary to generate the patterns. The efficiency of the algorithm w i l l be determined by measuring the time needed to generate those combinations o f cut list items that form the permissible patterns and the effect of pruning on run time. This is done in the next section. 6.2 Testing the Recursive Algorithm The results of the algorithm for 14 different sample sets are reported in Table 6.1. The program is run on a Pentium II - 300MHz computer. The run time and generated number o f combinations are recorded. For each of the sample sets, the program is run three times. First no pruning is considered and all permissible cut patterns are generated. The respective results are given in columns two and three o f the table and it can be observed that these are the most time expensive runs. Then, as shown in columns four and five the sets are run with the inclusion of only zero-waste pruning criterion. A n d finally, columns six and seven present the results when the sets are run with a combination o f two pruning criteria. In order to test the speed of the algorithm a very large number o f patterns for a clean piece are generated. This is done through using exaggerated test data for the cut list and the clean piece, especially for the sample sets 4 to 14 in Table 6.1. These sets use very long clean pieces and the cut list consists of very short items. For example, a 8600 mm clean piece with grade sections shown in Figure 6.2 is considered. A t the same time, the cut list contains many short items such as 500 mm grade B and 600 mm grade C . Table 6.1. Number o f combinations and run times for 14 sample sets. Sample Set No Pruning Zero-waste Pruning Zero-waste and Total-Rank Pruning Number of Combinations Time (Second) Number of Combinations Time (Second) Number of Combinations Time (Second) 1 321,725 0.591 18,325 0.140 3 < 0.001 2 1,548,193 2.915 94,772 0.641 3 < 0.001 3 3,757,708 7.010 13,181 1.162 2 < 0.001 4 14,222,298 27.630 841,357 5.869 1 < 0.001 5 86,361,544 164.586 416,234 26.398 2 < 0.001 6 115,060,353 239.164 7,015,766 47.819 3 < 0.001 7 190,885,727 330.989 10,462,726 58.984 3 < 0.001 8 258,947,488 491.206 1,181,371 84.381 2 < 0.001 9 633,772,130 1201.024 37,057,028 258.682 3 < 0.001 10 903,207,859 1661.018 51,547,403 299.541 2 < 0.001 11 1,735,924,064 2854.845 95,279,459 607.985 4 < 0.001 12 4,496,698,825 7931.405 248,443,833 1394.195 3 < 0.001 13 37,958,247,729 68426 = 19 hours 8,293,507,053 10876.566 3 < 0.001 14 112,580,924,328 237614 s 66 hours 6,593,744,767 8231.652 3 < 0.001 1 B A C B | 5000 m m 1200 mm 1700 mm 700 mm Figure 6.2. A long clean piece. It is apparent that there are many possible combinations o f these short items that fit within the first section o f the clean piece (5000 mm grade B) , which increases the number o f patterns significantly. Such sample sets are chosen to test the speed o f the algorithm when a very large number of combinations in the order of 10 1 1 is generated. The results in Table 6.1 illustrate that, when pruning with two criteria, the run time for all sample sets was less than a millisecond, much smaller than the time needed by each strip to be processed online. Even a single zero-waste pruning criterion may be sufficient for cases where the number o f combination is less than four mi l l ion (e.g. as the result for sample set 3). This is based on the use of the Pentium II-300MHz computer, but faster processors are available that can improve the time efficiency. 6.3 Concluding Remarks A recursive algorithm has been developed that generates all or a subset of all permissible cut patterns with inclusion of all quality issues, such as multiple grades and downgrading. The subset selection depends on the choice of the pruning criteria. Combination o f only two pruning criteria makes it possible to determine the best cut patterns among many millions of alternative patterns in less than a millisecond, which is well within the time needed for processing each strip in the actual production system. This shows that the algorithm is applicable for online decision making. Especially, the decisions in the real time optimization case are not based only on the zero-waste cut pattern o f single strips but also based on the overall waste and thus more than one criterion w i l l be used. In addition to waste criterion, the second criterion can help the optimization algorithm to maintain the balance o f the quantities in the cut list as it is being produced. The same recursive algorithm w i l l be used to optimize the real time 1D-C S P but with different pruning criteria. This is discussed in the following Chapter. CHAPTER 7 Real Time 1D-CSP Optimization Chapter 5 introduced an optimization algorithm for classical 1D-CSP based on ranking of the cut list with one of the five different methods. The experimental results demonstrated that adaptive fuzzy ranking was the best method for optimizing the classical 1D-CSP, which is an offline problem with no grading or stock length variation taken into account. The real time 1D-CSP, the focus o f this research, is far more involved than the classical 1D-CSP. The practical features of on-the-run real time strip production and chopping, unpredictable quality grades and defects, downgrading and use o f neighbouring sections, dynamic cut lists, and aggregate cut lists with prioritized orders introduce a significant degree o f complexity to problem formulation and solution. The optimization of the real time 1D-CSP is addressed in this chapter. In section 7.1, a real time optimization algorithm for various types of cut lists is introduced. Section 7.2 presents the simulation results for the real time optimization algorithm using fixed cut lists and also demonstrates the advantage of using the adaptive fuzzy ranking module within the optimization procedure. Section 7.3 explains the necessary changes to the algorithm and presents the simulation results of the optimization for problems with dynamic cut lists. Section 7.4 describes another enhancement o f the algorithm to include aggregate cut lists that result from prioritized orders. The simulation results are also given in this section. Section 7.5 is the concluding remarks. 7.1 Optimization Algorithm - Fixed Cut Lists Contrary to the classical 1D-CSP, the problems in this section and section 7.2 deals with fixed cut lists that have an additional column for quality grades as illustrated in Table 7.1 (this is a reproduction of Tablel.5). Table 7.1. A fixed cut list with no order priority. Items Length (mm) Grade Quantity 1 1900 A 1226 2 1200 A 770 3 1000 A 500 4 550 A 2880 5 900 B 340 6 600 B 3831 7 350 B 5098 8 1800 C 2057 9 550 C 800 10 400 C 222 To apply the optimization process for the real time 1D-CSP, the adaptive fuzzy procedure o f chapter 5 for cut list ranking and the recursive procedure o f chapter 6 for pattern generation are integrated into one algorithm. Both procedures are successively called for each arriving clean piece. The integrated algorithm is as follows. Integrated Algorithm for Optimization of Real Time 1D-CSP • Read the order data and produce the cut list. ^ • Read and record the strip data (i.e. location o f the defects and grade changes along the length o f the strip). • For each clean piece of the strip do: o Cal l the adaptive fuzzy method to rank the cut list items. o Ca l l me recursive algorithm to generate and select the best cut pattern for the current clean piece based on the pruning criteria (i.e. least-waste and total-rank). o Cut the selected items and update the cut list quantities. ' • Loop back for next strip until all the items o f the cut list are produced. A s the algorithm shows, the cut list is ranked by calling the adaptive fuzzy method for each clean piece, where each cut list item is assigned a rank. The calculation of ranks for cut list items o f classical 1D-CSP was explained in section 5.5, where normalization of length classes was based on the full length of the strip. However, to use the adaptive fuzzy ranking method in the optimization of the real time 1D-CSP, some enhancement are proposed as explained in the following subsection. 7.1.1 Ranking the Cut List In the adaptive fuzzy method normalized length values were calculated by dividing the length o f an item to the length of the defect-free strips. But for the real time case the arriving strips are made o f one or more clean pieces that each has unpredictable different length and grade variation. To normalize the length o f an item here, the fixed full length of the strips is not used. Instead, as each strip data is read by the scanner, the length of grade A , B , and C sections on that strip are recorded separately and the ongoing averages of these data are calculated. The length o f each item is then normalized against one of these averages based on the grade of the item. This way of normalizing has the advantage that the quality o f the wood is implicitly taken into account in the item ranking. Better wood quality w i l l result in longer A sections on the strips and consequently larger average length value for A pieces and thus the "normalized" ranking o f A items w i l l be reduced. But poorer wood quality w i l l have shorter and fewer A sections and thus the grade A items w i l l be given higher ranks. This ongoing procedure is a way of including the stock quality in the assignment of cut list ranks and improves the performance o f the real time optimization algorithm due to adaptation to the data. For example, in a simulation run, at the beginning of the production o f the cut list represented as Table 7.1, items 1 and 3 were assigned the ranks 12.13 and 10.93, respectively. Then, at randomly selected instant during the simulation, these values were 11.85 and 4.34. The examination of the simulation data at this instant showed that the quantity of item 1 had been reduced from the initial 1226 to 994 and the quantity o f item 3 from 500 to 293. This indicates that the ranking for item 3 was significantly reduced because its required quantity had been 40% satisfied and its length is shorter (easy to find) than item 1. On the other hand, the ranking o f item 1 had not noticeably changed because it is a long grade A piece (hard to find) and only 19% of the required quantity had been produced. For each clean piece the calculated ranks for the items of the cut list are passed to the recursive algorithm to generate a subset of permissible cut patterns based on the pruning criteria. Amongst the subset o f patterns, one with minimum waste and highest total rank is selected as the best pattern. Then, using this pattern the clean piece is cut and the algorithm updates the quantities o f the cut list and moves to the next clean piece. 7.2 Simulation Results Many simulations were carried out using strip data collected previously from the online scanner and the fixed cut lists and production data provided by Canwood Furniture Inc. The sequence o f the experiments is: • Subsection 7.2.1: The real time 1D-CSP optimization, without ranking the cut list, uses the recursive function with least-waste pruning criterion only. • Subsection 7.2.2: The same set o f simulation data as o f subsection 7.2.1 is used. The algorithm calls both adaptive fuzzy and recursive modules. Both pruning criteria are used. • Subsection 7.2.3: The results of the above simulations are compared to demonstrate the advantage o f using the adaptive fuzzy ranking module within the optimization algorithm. 7.2.1 Simulation - without Ranking Many industrial sample sets with fixed cut lists and no order priority (such as Table 7.1) are used to run the optimization algorithm without the ranking module. The simulation results for 12 sample sets are presented in Table 7.2. The table has 7 columns. The second column titled as "cut waste", reports the generated wastes due to the selected cut patterns. The third column is the "total waste". The different types o f waste were defined in section 4.2.1 and it was described that both o f these wastes are needed as a performance measure for the optimization. Table 7.2. The simulation results with no ranking. Sample Set % Cut Waste % Total Waste Number of strips Strip Size (mm) Algorithm RunTime (second) Average Run Time Per Strip (millisecond) 1 6.69 27.35 6814 3000 15.342 2 2 5.65 32.38 7322 3000 13.139 2 3 8.85 27.91 9285 3000 15.913 2 4 7.73 34.33 7835 3600 30.473 4 5 10.24 25.73 9178 3600 16.654 2 6 12.32 25.87 6338 4200 78.082 2 7 11.24 26.29 6596 4200 103.169 16 8 3.84 12.98 4572 4800 529.361 116 9 4.74 14.50 2964 4800 224.373 76 10 9.87 15.91 3947 4800 175.482 44 11 8.30 22.03 4053 4800 499.148 123 12 7.67 15.15 3794 4800 159.449 42 Average 8.09 23.37 155.049 37 The fourth column is the total number o f strips used to produce the given cut list completely. The strip size is given in millimeters in the fifth column. The sixth column is the total C P U run time used by the optimization algorithm to an accuracy o f millisecond. The seventh column is the average run time per strip. Time is another important performance measure because the proposed algorithm is for real time application. For example, in the sample set 1 it took only 15.342 seconds for the program to process 6814 strips, with an average of 2 milliseconds per strip. 7.2.2 Simulation - with Ranking The simulation results o f the real time optimization algorithm using the adaptive fuzzy ranking module are presented in this subsection. The same 12 industrial sample sets used as in previous simulation runs. The results are shown in Table 7.3. The company reports a waste of 15% within their current system. The algorithm performs well as the average cut waste is 6.20% and the average total waste is 9.80%. The cut waste and total waste o f optimization with ranking also demonstrate improvements once compared to the data o f Table 7.2. A more detailed comparison o f Tables 7.2 and 7.3 is presented in the next subsection. Table 7.3. The simulation results with ranking. Sample Set % Cut Waste % Total Waste Number of strips Strip Size (mm) Algorithm RunTime (second) Average Run Time Per Strip (millisecond) 1 4.30 8.51 5410 3000 35.252 6 2 4.46 12.09 5625 3000 76.690 13 3 5.61 10.17 7453 3000 100.184 13 4 5.06 18.57 6380 3600 36.764 5 5 8.60 12.66 7764 3600 96.950 12 6 8.74 8.76 5160 4200 67.287 13 7 8.84 9.78 5392 4200 68.859 12 8 3.81 6.50 3637 4800 13.499 3 9 6.08 12.32 3892 4800 51.274 13 10 7.43 13.54 3270 4800 43.302 13 11 5.87 7.49 3612 4800 50.893 14 12 7.55 8.08 3794 4800 51.514 14 Average 6.20 9.80 57.706 12 7.2.3 Comparison of Optimization with and without Ranking Table 7.4 is produced from results o f Tables 7.2 and 7.3 for comparison o f optimization algorithm with and without ranking. The objective in this section is to demonstrate that adaptive fuzzy ranking method improves the results i f used for the optimization o f real t i m e l D - C S P . Table 7.4. Comparison of optimization with and without ranking. N o Ranking Only Least waste Pruning Only Recursive With Ranking Least waste & Rank Pruning Recursive & Adaptive Fuzzy Sample Set Strip Size (mm) % Cut Waste % Total Waste Algorithm Run Time (second) % Cut Waste % Total Waste Algorithm RunTime (second) 1 3000 6.69 27.35 15.342 4.30 8.51 35.252 2 3000 5.65 32.38 13.139 4.46 12.09 76.690 3 3000 8.85 27.91 15.913 5.61 10.17 100.184 4 3600 7.73 34.33 30.473 5.06 18.57 36.764 5 3600 10.24 25.73 16.654 8.60 12.66 96.950 6 4200 12.32 25.87 78.082 8.74 8.76 67.287 7 4200 11.24 26.29 103.169 8.84 9.78 68.859 8 4800 3.84 12.98 529.361 3.65 3.66 13.499 9 4800 4.74 14.50 224.373 4.26 4.27 51.274 10 4800 9.87 15.91 175.482 7.43 13.54 43.302 11 4800 8.30 22.03 499.148 5.95 7.77 50.893 12 4800 7.67 15.15 159.449 7.55 8.08 51.514 Average 8.09 23.37 155.049 6.20 9.80 57.706 With adaptive fuzzy ranking, the cut waste and total waste decrease for all the sample sets. The table shows a decrease from 8.09% to 6.20% (a difference o f 2.11%) for the average cut waste and from 23.37% to 9.80% (a difference o f 13.57%) for the total waste. The large decrease in total waste is because the optimization algorithm without ranking cuts the short items too early and the long items are left for the later strips, creating an imbalance in the quantities of short and long items. Hence, further towards the completion of the cut list many of the clean pieces are left uncut, as the shortest available length remaining on the cut list is now larger than before. To visualize the difference between the waste data clearly, Figures 7.1 and 7.2 are provided. The decrease in cut waste is shown in the graph o f Figure 7.1. Except the sample sets 8 and 9 with a small difference, all other ten sample sets have obvious decrease in waste. The decrease in total waste is more and has been shown in the graph of Figure 7.2. e— No Ranking •-<>-• With Ranking 0 1 2 3 4 5 6 7 8 9 10 11 12 Sample Set Figure 7.1. The decrease in cut waste. e— No Ranking •-<>-• With Ranking 0 i 1 1 — 1 — i 1 1 1 1 1 1 1 1 0 1 2 3 4 5 6 7 8 9 10 11 12 Sample Set Figure 7.2. The decrease in total waste. The drastic decrease in both wastes is one of the advantages o f using the ranking method within the optimization algorithm. The other advantage is time. The average run time has also decreased from about 155 seconds to about 58 seconds. A s illustrated by Figure 7.3, the optimization run time is less for without ranking than for with ranking case in the first five sample sets and then the reverse in the next seven samples. The first five samples have strip sizes o f 3000 mm or 3600 mm. But the samples six to twelve have longer strips namely 4200 m m or 4800 mm. A s discussed in earlier chapters, long strips and short cut list items produce very large number of combinations. Thus, the number of generated patterns for sample sets 6 to 12 are much more than for the first five samples and the optimization run time is therefore larger when the optimization algorithm does not use the ranking module. But when the number o f permissible patterns is low, there is not much run time difference between the one criterion pruning (least-waste) and two criteria pruning (least-waste and total-rank) options. In both cases, the portion of time that the recursive function is being processed within the optimization algorithm by the computer is small and almost the same. However, the case of two criteria pruning requires some computer time for the processing of the adaptive fuzzy module whereas the one criterion pruning does not use this module. Therefore, there w i l l be only some increase in time for with ranking runs. -a— No Ranking ••<>•• With Ranking 600 I 400 <D E 300 0 1 2 3 4 5 6 7 8 9 10 11 12 Sample Set Figure 7.3. The changes in run time. On the other hand, once the number of permissible patterns is larger as for sample sets 6 to 12, both least waste and total rank pruning are necessary to prune sufficient number o f patterns. Total-rank pruning w i l l reduce the run time of the recursive function so much that it compensates for the small computer time required to process the ranking module. To conclude, the advantage of using the adaptive fuzzy ranking is that the performance o f the optimization algorithm improves significantly. In the next section, dynamic cut lists or the lists that vary during the chopping process are considered. 7.3 Optimization Algorithm - Dynamic Cut Lists The code o f the program written for the optimization algorithm presented in section 7.1 is modified to accept changes to the cut lists while its production is in progress. A s the cut list depletes, it is refreshed with new items. In other words, once the required quantity o f an item on the cut list reduces to zero, which means that the item has been completely produced, a new item is added to the cut list. Table 7.5 reports the simulation results for the same 12 industrial sample sets as the previous simulations for Tables 7.2. The second and the third columns are the results of Table 7.2 for fixed cut lists. Columns four and five are the waste results for simulations run with dynamic cut lists. It should be noted that for dynamic cut lists, the adding o f new items and the simulation must be terminated at some point in order to obtain the performance results. The program is set to terminate at a user-specified total number o f processed strips for each of the sample sets. In the simulation runs carried out the total numbers o f strips set to halt the program execution were equal to the respective cases with fixed cut lists. Table 7.5. The simulation results for fixed and dynamic cut lists. Fixed Cut Lists Dynamic Cut Lists Sample Set % Cut Waste % Total Waste % Cut Waste % Total Waste 1 4.30 8.51 4.22 4.22 2 4.46 12.09 3.94 3.94 3 5.61 10.17 5.57 5.57 4 5.06 18.57 5.00 5.03 5 8.60 12.66 5.75 5.75 6 8.74 8.76 5.45 5.45 7 8.84 9.78 4.7 4.71 8 3.65 3.66 3.72 3.72 9 4.26 4.27 4.00 4.01 10 7.43 13.54 5.27 5.32 11 5.87 7.49 4.39 4.39 12 7.55 8.08 4.67 4.73 Average 6.20 9.80 4.72 4.74 For the dynamic cut lists, the difference between the cut waste and the total waste values is not as much as for the fixed cut lists. This is because new items are being added to the cut list and thus the optimization algorithm has more items for cut pattern generation. The cut waste values in columns 2 and 4 o f the table are depicted in the graphs o f Figure 7.4 and the total waste values in columns 3 and 5 are illustrated in Figure 7.5. The wastes of dynamic cut lists are below fixed cut lists in all cases. Both figures illustrate clearly that cut waste and total waste for dynamic cut lists are consistently close to 5% with no drastic deviation. But this is not the case for fixed cut lists. The dashed lines in both graphs show large deviation based on the sample set. • o - - Fixed Cut Lists —a— Dynamic Cut Lists i 1 1 1 r 0 1 2 3 4 5 6 7 8 9 10 11 12 Sample Set Figure 7.4. Cut wastes of 12 sample sets with dynamic and fixed cut lists. - - o - - Fixed Cut Lists — b — Dynamic Cut Lists Sample Set Figure 7.5. Total wastes of 12 sample sets with dynamic and fixed cut lists. The algorithm performs well and the cut waste and total waste are both below 6% in all the simulation runs with an average of less than 5%. The waste results with dynamic cut lists prove further the hypothesis that the algorithm can perform very well in the cases where a good mix of sizes is maintained on the cut list. This is a confirmation that the algorithm can very well adapt itself to the flexibility required in everyday production environment. 7.4 Optimization Algorithm - Prioritized Orders In this section, aggregate cut lists that result from prioritized orders are considered. These cut lists have one extra column as the last column shown in Table 7.6 (this is reproduction o f Table 1.4). In this column, the required quantities of the items that belong to high priority orders are given. Table 7.6. The aggregate cut list with prioritized orders. Items Length (mm) Grade Quantity (Total) Quantity (High Priority Portion) 1 2000 A 1870 770 2 1890 A 328 328 3 1710 A 410 410 4 1520 A 1700 700 5 1200 A 820 820 6 950 B 2080 1580 7 900 C 410 410 8 700 B 3340 2340 9 630 B 656 656 10 550 A 680 280 11 450 B 2532 1332 12 380 C 1184 584 There is no change to the algorithm presented in section 7.1 except the calculation calculated for each item. A s it was explained before, this ranking is used to generate the cut patterns such that the balance of the long and short items in the cut list is preserved. But the order priority dictates otherwise. The items for high priority orders have to be produced may be even at the expense of some waste. In other words, the items in the aggregate cut list that belong to high priority orders must be produced even i f their calculated rank based on the adaptive fuzzy method is low. The routine procedure of the adaptive ranking method was that when the remaining quantity of an item is low, it would receive a low rank and thus would be planned later for production. But, for the problems in this section, an item o f a high priority order must be produced even when its quantity is low. Therefore, an adjustment factor is defined here to compensate for order priority. The total rank o f the item is calculated by multiplying this factor and the rank calculated by adaptive fuzzy method. This factor, denoted as F, was determined by trial and error. If the ratio of total remaining quantity of all items over the remaining quantity o f the item is denoted by R, the factor is computed as of the ranks for the cut list items. First, using the adaptive fuzzy module, a rank is for i = 1, . . . , m m w where R ; — w=l for i = 1 , . . . , m Q i and m is the number o f cut list items. The current required quantity of an item. A t the beginning o f the run these are the values reported in column 4 of Table 7.6 and then updated during the run as the items are produced. The current required quantity o f an item that belongs to high priority orders. A t the beginning of the run these are the values reported in column 5 o f Table 7.6 and then updated as the items are produced. If the orders are not given different priority, Q H , is considered zero. The adjustment factor is applied only when the item belongs to a high priority order. The adaptive fuzzy ranking is still necessary to distinguish amongst all items with high priority orders and also to calculate the ranks once the high priority orders are satisfied. To make sure that the rank calculated by adaptive fuzzy is always multiplied by a number larger than unity the term 1 has been added to the formula. For example, assume an item from an order with high priority. Case 1: If the total remaining quantity of all the items is 10,000 and the required quantity of the item is 100, then F = 3. Case 2: Same total quantity o f 10,000 and an item quantity o f 10, then F = 4. The adaptive fuzzy ranking w i l l assign a low rank to the item in the 2 n d case because it has a low quantity, but because the order that the item belongs to has high priority the rank is increased by a factor o f 4. The adjustment factor F increases as the quantity of this item decreases and this w i l l increase the rank of the item. Table 7.7 shows the simulation results for 12 sample prioritized order lists. Table 7.7. Simulation results using aggregate cut lists with prioritized orders. Sample Set % Cut Waste % Total Waste Run Time (sec) Run Time per Strip (millisecond / strip) 1 3.90 3.90 76.700 10 2 3.50 4.21 77.992 10 3 3.26 4.95 86.024 11 4 2.99 3.79 90.300 12 5 2.91 4.11 92.143 12 6 3.69 8.77 90.654 12 7 3.69 8.83 80.993 10 8 2.92 2.92 59.505 8 9 3.02 3.03 52.836 7 10 3.25 3.26 48.400 6 11 3.26 3.27 25.086 3 12 4.19 4.20 61.028 8 Average 3.38 4.60 70.138 9 Both cut waste and total waste in all o f the samples are below 5%, which shows that the performance of the algorithm is very satisfactory and promising to be implemented in the industry. In each run over 7700 strips were processed to produce a set of orders. Here the speed of the algorithm is also excellent and proves it is applicable to the real time online system. The run time to process these 7700 strips in all the 12 sample sets is below 2 minutes, with an average of 70.138 seconds, or 9 milliseconds per strip, which is much less than the time needed to cut 7700 strips by the chopsaw. 7.5 Concluding Remarks The adaptive fuzzy ranking method and the recursive function for pattern generation were integrated into an optimization procedure to solve the real time 1D-CSP. The simulation results illustrated the important role of the adaptive fuzzy ranking module in minimizing the overall waste and reducing the computation time. This chapter provided all the necessary modification to use the algorithm for real time 1D-CSP present in the company. These included problems with fixed cut lists, dynamic cut lists and aggregate cut lists resulting from prioritized orders. The results of the different simulation runs were reported. A l l o f the results in this chapter are consistently satisfactory and confirm the applicability o f the developed system for online application. CHAPTER 8 Contributions, Conclusion and Future Research 8.1 Summary and Contributions Chapter 1 introduced the industrial setting, discussed the complex operational features and precisely defined the optimization problem. In chapter 2, a review of the available literature on the cutting process optimization was conducted and it was argued that the available approaches are not applicable to the case at hand. The distributions o f available company data were investigated in chapter 3 in a search for repeating patterns that might have some utility in the optimization process. None was specifically observed and this enforced our belief that an algorithmic approach, rather than a statistical one, must be pursued. In Chapter 4, a mathematical formulation was provided for the 1D-CSP which incorporated multiple quality grades and the downgrading practice exercised in the company. Using the objective function and the applied constraints, an algorithm was developed that optimally solved the static offline 1D-CSP. Due to the complexity o f the combinatorial problem, it was shown that only small problems can be solved in reasonable time, and this did not meet the needs of the actual situation. Chapter 5 elaborated on five cut list ranking methods used in the optimization, and presented and discussed the positive results obtained from the tests. Chapter 6 presented the developed recursive algorithm for generating cut patterns. Test results proved the efficiency and the practicality of the algorithm for real time applications. Chapter 7 integrated the adaptive fuzzy and recursive algorithms into a final optimization procedure. The effectiveness of the adaptive fuzzy ranking method within the overall optimization procedure was demonstrated in this chapter. Modifications to the optimization algorithm were applied to include dynamic cut lists and the aggregate cut lists resulting from prioritized orders. Specifically, the developed optimization algorithm and procedure in the context o f wood processing is capable of handling complex cutting problems, where: - Raw material is defect-sensitive. The length o f individual pieces of the raw material is variable and not known in advance and all at once. - Raw material pieces have variable quality grade along their length. - Downgrading and use o f neighboring sections over the raw material is present. - The order list, and thus the cut list can vary during the piece production. - Real time application is involved. The contributions o f this thesis are as follows: - Mathematical modeling o f an offline 1D-CSP including quality grades, downgrading and length variation. Development o f an exhaustive search method as an exact solution approach. - Development o f an effective adaptive fuzzy algorithm as a ranking tool. - Development o f a novel recursive algorithm that is able to produce all or any desired subset of the permissible cut patterns. - Optimization of real time 1D-CSP with o Fixed cut lists, o Dynamic cut lists. o Aggregate cut lists with prioritized orders. 8.2 Conclusion It was demonstrated that exact approaches are not practical for large combinatorial real time optimization problems as encountered in this research. On the other hand, artificial intelligence techniques such as fuzzy logic, and innovative algorithmic schemes such as recursive pattern generation can be used to handle such problems with very good results. Since a complete solution is not possible with "real time" systems, any developed algorithm must adapt to dynamic data. In other words, it should be forward-looking as was the case for ranking and maintaining a balanced mix o f pieces for better pattern generation, and it must also be backward-looking, as it was the case for normalizing data with the cumulative averages. B y their nature these approaches require verification and fine-tuning through simulation. Once the developed optimization algorithm presented in this work is implemented in the industry, gross savings w i l l be considerably high especially i f in addition to reduced waste, manufacturing time and costs, the maximum use o f forest resources are also taken into account. 8.3 Future Research Directions In this section some directions for future research are suggested. The adaptive fuzzy parameters can be fine-tuned once the algorithm is applied to an industrial setting and some further experimentation is performed. In particular, adaptive membership functions and automatic class definitions- possibly based on statistical distributions- can be considered. Another possibility o f future research is to test other pruning criteria for the recursive algorithm such as a pruning based on least downgrading. Future work can also include the development of an algorithm for the optimum assignment o f kickers to produce a primary subset of the original cut list. Cut list kicker assignment and order batching are related decisions that can be done along with the shop floor scheduling using generally distributed decision making systems such as multi-agent or the so called "Holonic" manufacturing systems[44, 45, and 46]. Another interesting future research direction is to extend the developed optimization algorithm to the two- or three-dimensional defect-sensitive cutting stock problems. Glass or wood panels with defects and grades are examples o f such problems. Because, the solution procedure in this work is based on ranking the cut list items, the extension to more dimensions is feasible. References [1] http://www.canwood.com [2] http://www.palliser.com [3] Wolsey, L . A . , 1998, Integer Programming, (John Wi ley & Sons, Inc.). [4] Ask in , R. G . , and Standridge, C . R., 1993, "Modeling and Analysis of Manufacturing Systems", John Wi ley & Sons Inc., New York . [5] Sweeney, P. E . , and Paternoster, E . R., 1992, Cutting and packing problems: a categorized, application-orientated research bibliography.. Journal of the Operational Research Society, 43(7), 691-706. [6] Carravilla, M . A . , Ribeiro, C , and Oliveira, J. F. , 2003, Solving nesting problems with non-convex polygons by constraint logic programming. International Transactions in Operational Research, 10, 651-663. [7] Bischoff, E . E . , and Wascher, G . , 1995, Cutting and packing. European Journal of Operational Research, 84(3), 503-505. [8] Taha, H . A . , 1997, Operation Research—An Introduction, (New Jersey: Prentice Hall) , 6 t h edition. [9] Gilmore, P. C , and Gomory, R. E . , 1961, A linear programming approach to the cutting stock problem. Operations Research, 9, 849-859. [10] Gilmore, P. C , and Gomory, R. E . , 1963, A linear programming approach to the cutting stock problem: part 2. Operations Research, 11(6), 863-888. [11] Dyckhoff, H . , 1981, A new linear programming approach to the cutting stock problem. Operations Research, 29(6), 1092-1104. [12] Scheithauer, G . , Terno, J., and Muller, A . , 2001, Solving one-dimensional cutting stock problems exactly with a cutting plane algorithm. Journal of the Operational Research Society, 52(12), 1390-1401. [13] Valerio de Carvalho, J. M . , 2002, L P models for bin packing and cutting stock problems. European Journal of Operational Research, 141(2), 253-273. [14] Valerio de Carvalho, J. M . , 1998, Exact solution of one-dimensional cutting stock problems using column generation and branch-and-bound. International Transactions in Operational Research, 5(1), 35-44. [15] Chen, C , Hart, S., and Tham, W. , 1996, A simulated annealing heuristic for the one-dimensional cutting stock problem. European Journal of Operations Research, 93(3), 522-535. [16] Foerster, H . , and Wascher, G . , 1998, Simulated annealing for order spread minimization in sequencing cutting patterns. European Journal of Operations Research, 110(2), 272-281. [17] Hinterding, R., and Khan, L . , 1995, Genetic algorithms for cutting stock problems: with and without contiguity. In X . Yao (Ed.), Lecture notes in computer science, v. 956, progress in evolutionary computation. Selected papers. New York: Springer, 166-186. [18] Liang, K . , Yao , X . , Newton, C , and Hoffman, D . , 2002, A new evolutionary approach to cutting stock problems with and without contiguity. Computers and Operations research, 29(12), 1641-1659. [19] Wagner, B . J. , 1999, A genetic algorithm solution for one-dimensional bundled stock cutting. European Journal of Operational Research, 117(2), 368-381. [20] Falkenauer, E . , and Delchambre, A . , 1992, A genetic algorithm for bin packing and line balancing. Proceedings of the 1992 I E E E International Conference on Robotics and Automation, Nice, France. Los Alamitos, C A : I E E E Computer Society Press, 1186-1192. [21] Haessler, R. W . , 1988, Selection and design o f heuristic procedures for solving roll trim problems. Management Science, 34, 1460-1471. [22] http://www.ampl.com [23] http://www-fp.mcs.anl.gov/otc/Guide/CaseStudies/cutting [24] http://www.luxscan.lu [25] Pisinger, D . , 1998, A tree-search heuristic for the container loading problem. Ricerca Operativa, 28(87), 31-48. [26] Gehring, H . H . , and Bortfeldt, A . , 1997, A genetic algorithm for solving the container loading problem. International Transactions of Operations Research, 4(5), 401-418. [27] http://www.paulsaws.com [28] http://www.astrokettle.com [29] Ronnqvist, M . , 1995, Theory and methodology: a method for the cutting stock problem with different qualities. European Journal of Operational Research, 83, 57-68. [30] Ragsdale, C. T., and Zobel, C. W. , 2004, The ordered cutting stock problem. Decision Sciences, 35(1), 83-100. [31] Scull i , D . , 1981, A stochastic cutting stock procedure: cutting rolls o f insulating tape. Management Science, 27(8), 946-952. [32] Sweeney, P. E . , and Haessler, R. W. , 1990, One-dimensional cutting stock decisions for rolls with multiple quality grades. European Journal of Operational Research, 44, 224-231. [33] Sarker, B . R., 1988, A n optimum solution for one-dimensional slitting problems: a dynamic programming approach. The Journal of the Operational Research Society, 39(8), 749-755. [34] Lembersky, M . R., and Ch i , U . H . , 1984, 'Decision simulators' speed implementation and improve operations. The Institute of Management Sciences, Interfaces, 14, 1-15. [35] Whitaker, D . , and Cammell, S., 1990, A partitioned cutting-stock problem applied in the meat industry. Journal of the Operational Research Society, 41(9), 801-807. [36] Gradisar, M . , Resinovic, G . , and Kljajic, M . , 1999, A hybrid approach for optimization o f one-dimensional cutting. European Journal of Operational Research, 119, 719-728. [37] Cizman, A . , and Cernetic, J. , 2004, Improving competitiveness in veneers production by a simple-to-use DSS. European Journal of Operational Research, 156,241-260. [38] Gradisar, M . , and Trkman, P., 2004, A combined approach to the solution to the general one-dimensional cutting stock problem. Computers and Operations Research, article in Press. [39] Yermal, S., Anantharaju, S., and Shaik, A . B . , 2003, A genetic algorithm based approach to the winder run formation problem in paper mills . International Symposium on Process Systems Engineering and Control ( ISPSEC'03) for Productivity Enhancement through Design and Optimization, Mumbai , India. [40] Vasko, F. J. , Newhart, D . D . , and Stott, K . L . Jr., 1999, A hierarchical approach for one-dimensional cutting stock problems in the steel industry that maximizes yield and minimizes overgrading. European Journal of Operational Research, 114,72-82. [41] Holthaus, O., 2003, On the best number o f different standard lengths to stock for one-dimensional assortment problems. International Journal of Production Economics, 83, 233-246. [42] Belov, G . , and Scheithauer, G . , 2002, A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths. European Journal of Operational Research, 141, 274-294. [43] Rosen K . H . , 1995, Discrete mathematics and its applications (New York: M c G r a w - H i l l Inc.), 3 r d edition. [44] Smith, M . H . , and Takagi, H . , 1993, Optimization o f fuzzy systems by switching reasoning methods dynamically. International Conference on Fuzzy Systems, Seoul, Korea. [45] Cicirello, V . A . , and Smith, S. F., 2001, Ant colony control for autonomous decentralized shop floor routing. Fifth International Symposium on Autonomous Decentralized Systems (ISADS'01), IEEE Computer Society Press, 271-303. [46] Gou, L . , Luh, P. B . , and Kyoya, Y . , 1998, Holonic manufacturing scheduling: architecture, cooperation mechanism, and implementation. Computer in Industry, 37,213-231. [47] Lun, M . , and Chen, F. F. , 2000, Holonic concept based methodology for part routing on flexible manufacturing systems. International Journal of Advanced Manufacturing Technology, 16, 483-490.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Real time multiple-grade cutting stock optimization...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Real time multiple-grade cutting stock optimization using adaptive fuzzy and recursive algorithms Ghodsi, Reza 2004
pdf
Page Metadata
Item Metadata
Title | Real time multiple-grade cutting stock optimization using adaptive fuzzy and recursive algorithms |
Creator |
Ghodsi, Reza |
Date Issued | 2004 |
Description | In the production of commodities there exist many instances of cutting processes whereby decisions have to be made on how the cuts can be performed optimally. In other words, the question arises that "in what sequence should cutting of a workpiece into smaller items be conducted so that the raw material used is minimized?" This is often synonymous to generating the "minimum waste". In its simplest form, this is referred to as the Classical One-dimensional Cutting Stock Problem or Classical 1D-CSP, for which very effective solutions for static off-line cases exist. The 1D-CSP is present in such industries as steel, apparel, paper, wood and food. A cut sequence is commonly referred to as a pattern. An investigation into 1D-CSP reveals that many patterns or combinations must be evaluated before an optimal solution is found. Further, the number of such combinations dramatically rises with the number of problem parameters and operational features, making the solution computationally extensive. For this reason, beyond the classical 1D-CSP and in particular when real time online applications are involved, developing practical optimization solutions is a major challenge. In a high volume wood product manufacturing plant encountered in this research, a major production phase involves online inspection of wood strips, for removing defects and quality grading, and subsequent chopping of the useful pieces to build up the inventory needed for the product on orders received. Specifically, the production line is to use wood as a defect-sensitive raw material, make decisions one strip at a time, deal with all non-identical pieces, use multiple grades of wood, cut strips to pieces, and at the same time satisfy objectives such as meeting customer due dates and generating least waste. This turns out to be is a complex case of dynamic 1D-CSP and a new solution approach needs to be instigated. In this work, in an attempt to develop an effective optimization tool, a mathematical formulation for an exact solution with multiple material grades is derived and it is demonstrated that even for small problems the computational times are prohibitive for online applications. Hence, an adaptive fuzzy algorithm is developed and tested which is able to produce results comparable to the exact solution for CSP. This fuzzy algorithm is then integrated with an innovative recursive pattern generation module into an optimization algorithm for real time problem. The combined optimization structure is examined with various objective functions, constraints and input data, and results are discussed. It is concluded that the developed optimization approach has an excellent performance and can adapt itself to extreme variations in raw material quality and most of all is applicable to real time decision-making. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-01-16 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
IsShownAt | 10.14288/1.0080796 |
URI | http://hdl.handle.net/2429/18284 |
Degree |
Doctor of Philosophy - PhD |
Program |
Mechanical Engineering |
Affiliation |
Applied Science, Faculty of Mechanical Engineering, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2004-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-ubc_2004-103728.pdf [ 7.15MB ]
- Metadata
- JSON: 831-1.0080796.json
- JSON-LD: 831-1.0080796-ld.json
- RDF/XML (Pretty): 831-1.0080796-rdf.xml
- RDF/JSON: 831-1.0080796-rdf.json
- Turtle: 831-1.0080796-turtle.txt
- N-Triples: 831-1.0080796-rdf-ntriples.txt
- Original Record: 831-1.0080796-source.json
- Full Text
- 831-1.0080796-fulltext.txt
- Citation
- 831-1.0080796.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0080796/manifest