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 |