View Question
Q: Algorithm for optimization of sheet metal cutting (to minimize sheets consumed) ( Answered ,   3 Comments )
 Question
 Subject: Algorithm for optimization of sheet metal cutting (to minimize sheets consumed) Category: Computers > Algorithms Asked by: sheet_cutter-ga List Price: \$25.00 Posted: 10 Jan 2003 09:57 PST Expires: 09 Feb 2003 09:57 PST Question ID: 141254
 ```I need detailed (yet easy to understand) description of a procedure to solve the following problem (source code in VB6 would also be appreciated but not a must): I have raw metal sheets of various rectangular sizes (x1*y1, x2*y2, ... xn*yn). I want to cut them to various different sizes (a1*b1, a2*b2, ... ai*bi). In some cases a tolerence of t might be added to all four sides of each rectangle to be cut. I want an algorithm to generate a cutting plan that would MINIMIZE the number of raw sheets to be used and to minimize the scrap.``` Request for Question Clarification by mathtalk-ga on 10 Jan 2003 10:54 PST ```Hi, sheet_cutter-ga: The underlying problem you ask about is mathematically difficult if it is required to find the best of all possible solutions for general inputs. However I think I can help you find solutions that are of practical value. First let's clarify some of the ideas. It appears that you are cutting rectangular pieces from rectangular sheets. So let's say a "work order" (or combination of several work orders) calls for a certain number of each kind of piece: Dimensions : Count a1*b1 N1 a2*b2 N2 ... ... ai*bi Ni You mentioned that "a tolerence of t might be added to all four sides of each rectangle to be cut." We can assume that, if desired, this has already been done to the measurements shown. With the required pieces defined in this way, we can come up with lots of different cutting plans. Which one is best? You said you want "to generate a cutting plan that would MINIMIZE the number of raw sheets to be used and to minimize the scrap." The two goals, minimizing the number of sheets used and minimizing the scrap (unused area left over), are related but not identical. So we need to refine the objective to remove ambiguity. If all raw metal sheets had the same area, then the number of sheets used and the area of remaining scrap would be equivalent goals, since: #sheets * area of sheet = total area of pieces + total area of scrap However if the raw metal sheets are of different areas, then one cannot pursue both goals equally. Consider, for example, if all the pieces might be cut from a single very large sheet with substantial scrap, versus cutting the pieces from a number of smaller sheets with little or no waste. The first approach uses the smaller number of sheets, the second produces less scrap. I would suggest "blending" these goals by the use of a cost based metric. Consider for each size of raw metal sheet the cost, not only for the materials, but also the cost of setup (if appropriate). That is, there may be a labor cost associated with mounting a sheet, perhaps irrespective of the sheet's size. The materials cost might be greater for bigger sheets than smaller ones, but not strictly a function of the sheets' areas. The goal would then be to minimize a total cost of all sheets. A more complicated model objective could incorporate costs of tool repositioning, etc. but the above would incorporate the two objectives you mentioned in a natural way. There are some high powered and expensive CAD/CAM software products out there, and it sounds like you are hoping to substitute a homegrown Visual Basic program. In my experience a programming language like Prolog is a better fit for these sorts of "combinatorial" problems. However it also sounds like you'd be interested to start with learning some basics about the practical algorithms to solve these problems. If that's true, I believe I can be of assistance. regards, mathtalk-ga``` Clarification of Question by sheet_cutter-ga on 10 Jan 2003 13:52 PST ```Thanks a lot for your precise words. I'm amazed! Here is my clarifications: You said: Consider, for example, if all the pieces might be cut from a single very large sheet with substantial scrap, versus cutting the pieces from a number of smaller sheets with little or no waste. The first approach uses the smaller number of sheets, the second produces less scrap. My reply: Well .. in my situation, I actually have only 2 initial sheet sizes (in some rare occasions there are 3 sizes). But after cutting, some sheets contain large uncut areas and I wouldn't consider them to be scrap. I would use those remaining areas for subsequent cuts. So, may be I need to clarify that another condition might be necessary here: Scrap is defined as uncut areas of a sheet with with width or height of less than or equal s. =========== You said: Consider for each size of raw metal sheet the cost, not only for the materials, but also the cost of setup (if appropriate). My reply: Emmm ... I would assume equal setup costs for all sheet sizes. =========== You said: The materials cost might be greater for bigger sheets than smaller ones, but not strictly a function of the sheets' areas. My reply: Sheet costs are mainly based on weight rather than size, so I would say that this consideration might be ignored? I'm not sure ... ============ You said: The goal would then be to minimize a total cost of all sheets. My reply: Ok ... that's very reasonable. ============ You said: A more complicated model objective could incorporate costs of tool repositioning, etc. My reply: Well, no need for this in my situation. The actual cost of tool repositioning is time waste, but this is not a critical issue in my situation. I believe wasted repositioning time is too small to consider. ============ You said: There are some high powered and expensive CAD/CAM software products out there, and it sounds like you are hoping to substitute a homegrown Visual Basic program. My reply: I like the DIY stuff ;^) Besides, I tried one of these packages before (I don't remember its name) and found it too complicated to use. And I need to create a custom package since I will be integrating it with a scheduling and an inventory system, and because the users will need an interface that is not in English. ============ You said: In my experience a programming language like Prolog is a better fit for these sorts of "combinatorial" problems. However it also sounds like you'd be interested to start with learning some basics about the practical algorithms to solve these problems. If that's true, I believe I can be of assistance. My reply: I don't know prolog. Does this mean that VB will be too slow in solving this? How much slow? If it's going to take several hours, that's no big deal. I can write that program such that several cuts are scheduled for solving overnight, so that technicians will find all the cutting plans ready for them in the morning. We have a whole 16 hours to do the job :) I'm indeed intersted in learning the algorithms. But I need them explained very clearly, because honestly my math skills aren't so deep, and I don't have enough knowledge of algorithms and their terminology. I need easy steps that I can directly translate into code. Thanks a lot again for your careful detailed comments.``` Request for Question Clarification by mathtalk-ga on 10 Jan 2003 14:12 PST ```Hi, sheet_cutter-ga: Thanks for the clarifications! I have a few more points for you to address, but I can proceed to working on explaining the algorithms in the meantime. These points have more to do with strategy than "tactics". 1) How far ahead of time will the orders be known? You already touched on this point, but just to confirm, a reasonable scenario would involve having the orders in hand the evening before work is to begin on fulfilling them. 2) Are the sizes of the work pieces "standard" or do they vary considerably? I.e. the sizes of the raw metal sheets are "standard" and known in advance. I assume there are a relatively small number of sizes for the work pieces in any one order, but it would be significant if there are also a relatively small number of sizes that are used (or if the vast majority of pieces required are standard sizes, with only a few "exceptional" pieces in any one order). 3) In round numbers how many pieces are contained in a single (combined) order? I.e. how many pieces will be included in the cutting plan? The planning will be done more efficiently and exhaustively with a small number of pieces, but I suspect your interest is in coming up with a schedule for hundreds of pieces. regards, mathtalk-ga``` Clarification of Question by sheet_cutter-ga on 10 Jan 2003 21:59 PST ```Here are the clarifications: 1) Orders are usually known 2 or 3 days before starting to work on them, specially for larger orders. But for tiny orders, they could be known just in the same day. I'd call an order a small one if it consumes up to 10 sheets. Largest orders can consume 70 or 80 sheets. On average, a raw sheet is cut to 4 or 5 work pieces. Largest orders are known about a week beforehand. 2) I'd say the vast majority of pieces required have approximately equal sizes -- but not necessarily standard, with only a few "exceptional" pieces in any one order that are of much smaller or much larger sizes. 3) See 1! I think that the algorithm would ask me for the "quality" of the answer before working on it. If I request a higher quality, I except an answer that is of greater effeciency but takes longer time to reach.``` Clarification of Question by sheet_cutter-ga on 11 Jan 2003 14:02 PST ```Thanks a lot barry_hinz for the suggestion, but I agree with mathtalk that I need to know the algorithm to address those issues not addressed by sheetlayout. So, I'm eager to see the answer :)```
 Subject: Re: Algorithm for optimization of sheet metal cutting (to minimize sheets consumed) Answered By: mathtalk-ga on 11 Jan 2003 22:53 PST Rated:
 ```Hi, sheet_cutter-ga: Thanks for your patience. If quantity were the only consideration, I would have quickly fulfilled your request, as much has been written on this subject. But mindful of your wish to have clear directions that can be programmed, I try below to sketch an implementation in high-level algorithmic terms as concisely as possible. I wish I knew more about the typical nature of your work orders. You have said, if I remember correctly, that they are known at least the night before (and up to a week in advance for largest orders), and that they often require 10 to 80 sheets, mostly of about the same size but also a small number of pieces of exceptionally greater or smaller size than the rest. On average one fits perhaps 4 or 5 pieces to a stock sheet. It would be nice to know more about the aspect ratios of these rectangles, ie. the ratios of their "heights" to their "widths". Variously referred to as "bin packing", "stock cutting", or "cutting stock" problems, these are part of a larger family, problems in "geometric combinatorial optimization". Your specific problems seem to have these characteristics: + two-dimensional rectangular "bins" or stock (self-explanatory) + rectangular pieces (to be packed or to be cut) + non-guillotinable (cuts need not go all the way across, as they would with flat glass or stone) + non-orthogonal (rectangular pieces do not need to be laid out parallel to edges of stock) + off-line (layout is done with final knowledge of all required pieces, not "on-line" as orders come in) The algorithms for these problems must address two kinds of questions: (1) Which "bin" or stock sheet will hold which particular work pieces? (2) How will those work pieces on any particular sheet be laid out? Though we cannot entirely separate these two kinds of questions chronologically, we can think of the second question as logically "downstream" or nested "within" the answer to the first question. This is especially helpful in organizing our thoughts about a computer implementation. The most difficult part of the problem turns out to be (1). Before discussing an approach to solving (1), however, I'd like to describe, if only as a placeholder, a simple "sliding" heuristic approach to answering the layout questions (2): [BL] (Bottom-Left heuristic, Jacobs, 1996) Drop a piece onto the sheet in the upper-right corner. Slide it down until it meets a horizontal edge (of the sheet or of another piece already positioned on the sheet). Then slide it to the left until it meets a vertical edge (of the sheet or of another piece already positioned on the sheet). Repeat these sliding steps until the piece is "locked" in place. Improvements upon this strategy are possible and we will return to this topic, but I mention [BL] now for the sense of clarity and concreteness it will hopefully lend to our discussion of (1). Based partly on an analogy with one-dimensional results, I propose that you implement a "first fit descending height" strategy to answer (1). Here "first fit" means that we think of the "bins" as being numbered from left to right, and that in trying to assign our next work piece to a bin, we always start with the first (leftmost) bin to see if it "fits" there. If not, we check the next bin to the right and so, until the "first fit" is located. If no fit can be found, a new bin (stock sheet) is inserted in the rightmost position. We mean "descending height" in the sense that height is the longest dimension of a rectangular work piece, and we are to sort the input of work pieces accordingly. That is: [FFDH] (First fit-Descending height) Sort the required rectangles according to descending order on the longest dimensions of each. Taking the rectangles in this fixed order, assign them to bins (stock sheets) on a first-fit basis (see above). Note that to carry this out we must check whether a given piece "fits" into an existing bin, and for that purpose we will turn to [BL] or one of its improvements, not only to say how, but even whether the fitting/layout can be done. That is my high-level implementation plan in a nutshell. I will add a few words about how to incorporate varying sizes of stock sheets. The "scrap" sheets of odd sizes I would position at the beginning of the "array" of bins, which I think will tend to dispose of them as efficiently as possible. When new stock sheets are inserted, I would always insert ones of the larger size (assuming that there may be two such sheet sizes, a large and a small). The thinking here is on average the fixed cost of "set-up" for sheets will make use of the large sheets more attractive, given an equal density. However at the end of the "scheduling", each of the bins that reflects a large stock sheet should be tested to see if the same pieces on that sheet would also fit on one of the small stock sheets. Without knowing something about the relative sizes of these sheets, I cannot guess with much confidence how often this might occur. = = = = = = = = = = = = = = = = While I have, as a programmer, many thoughts about adding detail to the above, it may be best to give you a chance to read it over and digest it a bit before elaborating. Let me point you, however, to some of the resources out there on the Web. Although there is strikingly little in the way of open-source or free software for these stock cutting problems, there are some useful building blocks toward a large scale implementation. On the one hand are computational geometry libraries, while on the other are various kinds of optimization packages, e.g. frameworks for "genetic algorithms". But what I want to provide first are references to terminology and ideas that found there way into the approach outlined above. For a selected chronology of academic literature see here: [Stock Cutting: Bibliography] http://www.asap.cs.nott.ac.uk/themes/sc/scbib.htm Especially helpful in preparing my answer was the last paper cited on this list: [An Empirical Investigation of Meta-heuristic and Heuristic Algorithms for a 2-D Packing Problem] http://www.inf.utfsm.cl/~mcriff/EA/eva-space-planning/ht00.pdf which is closely related to this Web site: [Application of Genetic Algorithms in 2D Nesting Problems: PhD Project (Eva Hopper, 2000)] http://circuits.cf.ac.uk/hopper/ Here are a couple of relevant quotes from pages of that Web site: [Two-Dimensional Packing using Evolutionary Algorithms and other Meta-Heuristic Methods] http://circuits.cf.ac.uk/hopper/summary.html "Meta-heuristic techniques produced good results compared with published algorithms. Genetic algorithms were better suited to the solution of small to medium sized problems, at the expense of significant computation time. Simulated annealing produced very dense layouts but with an even greater increase in computation time. All of these techniques produced a limited improvement in the solution quality compared with standard packing techniques." [Example: Rectangular Packing Problem] http://circuits.cf.ac.uk/hopper/example.htm "A family of hybrid algorithms for the rectangle packing problem is implemented consisting of a combination of a meta-heuristic algorithm (GA, NE and SA) and heuristic packing routine to allocate the items on the object. The heuristic packing routines generate the layouts in a bottom-left justified manner. Whereas two of the techniques (BL and BLLT) are based on a sliding principle, the third one (BLF) is able to fill enclosures in the layouts, but at higher computational cost." As a quick tutorial site, I liked this one: [Bin Packing by Heidi Smith] http://www.cs.cf.ac.uk/user/C.L.Mumford/heidi/BinPacking.html Additional Links of Interest: [Exact and Heuristic Approaches for Assignment in Multiple-Container Packing] http://www.cs.uml.edu/~kdaniels/papers/BCtr-97-02.ps.gz [Handbook of Evolutionary Computing: The Packing Problem (by Kate Juliff)] http://www.iop.org/Books/CIL/HEC/pdf/ECF1_7.PDF regards, mathtalk-ga Search Strategy Keywords: 2D "bin packing" ://www.google.com/search?hl=en&ie=UTF-8&oe=UTF-8&q=2D+%22bin+packing%22&btnG=Google+Search Keywords: "cutting packing problems" ://www.google.com/search?hl=en&ie=UTF-8&oe=UTF-8&q=%22cutting+packing+problems%22&btnG=Google+Search Keywords: "cutting and packing problems" ://www.google.com/search?q=%22cutting+and+packing+problems%22&btnG=Google+Search&hl=en&lr=&ie=UTF-8&oe=UTF-8 Keywords: "stock cutting" "first fit decreasing" ://www.google.com/search?hl=en&ie=UTF-8&oe=UTF-8&q=%22stock+cutting%22+%22first+fit+decreasing%22&btnG=Google+Search```
 sheet_cutter-ga rated this answer: ```Thanks a lot mathtalk. The answer is very straight-forward. Thanks to Google too for their great service.```

 ```There is a good (commercial) program called Sheet Layout available from www.sheetlayout.com which optimizes both sheet and lineal materials. It is available in several sizes (costs) and has a demo version available. I personally use it all the time in my hobby shop. It will save trying to reinvent the process.```
 ```I'd like to thank barry_hinz-ga for the apt suggestion of the Sheet Layout website and commercial product. It does indeed tackle the sorts of problems proposed by sheet_cutter-ga (with some additional generality, e.g. grain direction) and at reasonable pricing (\$220 for the "commercial" version). Those color layout diagrams appear to be quite useful. However I would like to present an answer, both because Sheet Layout does not currently address the language issues raised by sheet_cutter-ga, and also because of the interest sheet_cutter-ga expressed in learning about algorithms for these sorts of problems. The phrase "panel optimization software" used to describe Sheet Layout seems to have currency among the wood-working community. It can be important in woodworking to consider grain direction, a distinction unimportant to cutting sheet metal. So, as this detail shows, specialized terminology to identify seemingly minor variants among related problem types can be helpful. regards, mathtalk-ga```
 ```There are quite a few approaches, depending on - size of problem - Do you have only one stock size or multiple (whence you have to select the best sizes). - The considerations (best yield, minimum layouts, simple layouts) - Shape of the parts and stocks - The constraints (depending on the cutting method : guillotine, orthogonal, for rectangular, and general profile cutting by gas/plasma/laser) I would suggest that you should see a few commertial packages available to see what options they provide. You may like to have a look at PLUS 2D from Nirvana Technologies. They have a demo for download and the website mentions a DLL/API interface. check out http://www.nirvanatec.com/downloadcenter.html regards,```