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 :)

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

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,