Hi all!

Quoting "Lic. Edgar J. De Cleene" <edgardec2001 at yahoo.com.ar>:
> > Anybody here with good knowledge about the cutting stock problem and
> > algorithms for that?
> > Especially interested in some advice about the jungle of different
> > approaches.
> > 
> > This particular problem is meant to be applied on rectangular stock
> > (multiple sheets of different size) and with "cutting out pieces"
> with
> > arbitrary shapes (but rather simple geometric ones).
> > 
> > regards, Göran
> 
> Göran , I wish more details about this .
> You mean 
> NumberOfsheets _ (valueMin to valueMax) atRandom "What valueMin and
> valueMax
> yoy wish ? "
> sheetInstance _ Rectangle origin: 0 at 0 corner: x @ y . " x y atRandom too
> "
> 
> shape1 shape2 ... shapeN "Rectangles, triangles , circles , other ? "
> 
> And if we cut this shapes on each sheetInstance we finish with a
> minimun
> waste of sheets material ?

Well, something like that yes. I have been looking around on the net and this
problem is NP hard in general. There are a number of approaches and combinations
of approaches and the constraints for the special cases apparently make a
general good solution nonattainable. Linear programming, dynamic programming,
genetic algorithms have been used (and in combinations) with various success.

The problem itself appears a lot in the industry (glass cutting, production of
clothes, cutting pieces out of raw material and so on).

> We could use this as programming problem in class ?

Well, I can't give you the details for my special situation. But if you search
for "stock cutting" or "bin packing" on Google you will find tons of material.

regards, Göran

Göran Hultgren, goran.hultgren at bluefish.se
GSM: +46 70 3933950, http://www.bluefish.se
\"Department of Redundancy department.\" -- ThinkGeek