Re: Cutting stock problem

From: Richard Harter (cri_at_tiac.net)
Date: 04/09/04 

Date: Fri, 09 Apr 2004 14:58:09 GMT

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 *** 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?

Have you tried a straightforward greedy algoithm?

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