# Re: Cutting stock problem

**From:** Ronald Caudill (*ronaldc_at_juno.com*)

**Date:** 04/12/04

**Next message:**Joe \: "Re: a question in VB6"**Previous message:**Basel Saba: "a question in VB6"**In reply to:**Richard Harter: "Re: Cutting stock problem"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]

Date: 11 Apr 2004 17:59:46 -0700

cri@tiac.net (Richard Harter) wrote in message news:<4076b9c6.750546747@news.sbtc.net>...

*> On Wed, 07 Apr 2004 17:34:16 GMT, Peter Ammon
*

*> <gershwin@splintermac.com> 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.

Ronald

*>
*

*> Richard Harter, cri@tiac.net
*

*> http://home.tiac.net/~cri, http://www.varinoma.com
*

*> A university is what a college becomes when the faculty
*

*> loses interest in students. - John Ciardi
*

**Next message:**Joe \: "Re: a question in VB6"**Previous message:**Basel Saba: "a question in VB6"**In reply to:**Richard Harter: "Re: Cutting stock problem"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]