Maximum packing of rectangles in a circle

Question

I work at a nanotech lab where I do silicon wafer dicing. (The wafer saw cuts only parallel lines) We are, of course, trying to maximize the yield of the die we cut. All the of die will be equal size, either rectangular or square, and the die are all cut from a circular wafer. Essentially, I am trying to pack maximum rectangles into a circle.

I have only a pretty basic understanding of MATlab and an intermediate understanding of calculus. Is there any (relatively) simple way to do this, or am I way over my head?

Answer 1

Packing arbitrary rectangles into a circle to meet a space efficiency objective is a non-convex (NP-Hard) optimization in general. This means there will be no elegant or simple solution that will solve this problem optimally. The solution methods are all going to depend on any specific domain knowledge you can use to prune the search tree or develop heuristics. If you have no experience in this type of problem you should probably consult with an expert.

Answer 2

Go from here, and good luck:

http://en.wikipedia.org/wiki/Knapsack_problem

and get here:

http://www-sop.inria.fr/mascotte/WorkshopScheduling/2Dpacking.pdf

At least you'll have some idea what are you tackling here.