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.

---

---

• Are you posting in the right place? Check out Where do I post X? to know for sure.
• Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:

  <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>

• Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
• Want more info? How to link or How to display code and escape characters are good places to start.