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();
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.