Re: Cutting stock problem

From: Ronald Caudill (
Date: 04/12/04

Date: 11 Apr 2004 17:59:46 -0700 (Richard Harter) wrote in message news:<>...
> On Wed, 07 Apr 2004 17:34:16 GMT, Peter Ammon
> <> wrote:
> >I have a number of rectangles: at least 60, with lots more possible.
> >The rectangles all have their edges parallel to the X or Y axis (that
> >is, they aren't rotated wrt one another), but their sizes can be different.
> >
> >I need to position them at the top of a rectangular sheet of fixed width
> >and infinite height so that as little space possible is wasted (that is,
> >their enclosing rectangle is as small as possible).
> >
> >This is a variant of the cutting stock problem. Unfortunately, it seems
> >that every instance of the cutting stock problem is a variant, and I
> >wasn't able to find a solution given these constraints.
> >
> >Anyone have any ideas?

If you want a practical solution as opposed to a theoretical one, here
is what I do in my upholstery shop to plan cutting fabric of a
constant 54" width. (I use a spreadsheet).
First sort the sizes of all rectangles into a list from the largest to
the smallest along the dimension that will fit widthwise into the
fixed dimension which I call the width. Then just go down the list
starting at the top (widest piece). Put the widest piece down first
then subtract this width from the sheet width and select the widest
piece that will fit in. repeat this "subtract and place widest piece"
process till the width is filled as good as possible. Now the length
of this first row is considered the length of a cutting block. If some
of the pieces dont' fill out the length fit some of the smaller pieces
in. Now, just go down the length block after block, always putting
down the biggest pieces first and fitting the small pieces in. This
has worked well in my shop for years with remarkably little waste.
Like I said, I just use a semi-automated process with a spreadsheet
but I believe the process could pretty easily be fully automated.

> Richard Harter,
> A university is what a college becomes when the faculty
> loses interest in students. - John Ciardi