Although creating the best possible solutuion is NP-complete, there exist heurisic methods that are polynomial in time and usually do a fine job. An example of a heuristic method in a perl module is Algorithm::Bucketizer:

use Algorithm::Bucketizer;

# Create a bucketizer
my $bucketizer = Algorithm::Bucketizer->new(bucketsize => $size);

# Add items to it
$bucketizer->add_item($item, $size);

# Optimize distribution
$bucketizer->optimize(maxrounds => 100);

# When done adding, get the buckets
# (they're of type Algorithm::Bucketizer::Bucket)
my @buckets = $bucketizer->buckets();

# Access bucket content by using
# Algorithm::Bucketizer::Bucket methods
my @items  = $bucket->items();
my $serial = $bucket->serial();
[download]

This module only deals with linear objects inserted into linear bins, whereas you have 2D rectangles cut from rectangular plates. But the heurisitic algorithm would be the same and then modules methods could be overridden:

• sort rectanges to be cut by area -> that is your linear measure
• create a method to determine whether another rect can be cut from a partially used plate -> here you will have to do some thinking according to the details of your stock and set of rectangle shapes.

To get help for the second point, look at "cutting stock problems" on the web, e.g., Two-Dimensional Cutting Stock Problem.

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.