Nesting Problem: Randomly-Generated Rectangles In Series Within Larger Rectangle

Question

How efficiently can randomly-generated rectangles be nested within a larger rectangle of defined width (say, 30”) and fairly long length, where each inner rectangle must be placed/nested permanently before the next one is generated? That is, what percent of the larger rectangle will be filled. The inner rectangles may be rotated and may butt up against each other, but may not overlap. (This is to estimate material utilization where rectangular parts orders are printed on, or cut from, a web of material when received.)

Answer 1

In general these type of problems are called knapsack problems. There is a lot of literature on how to solve these problems efficiently. Although these problems are NP-complete there are efficient methods for solving these problems. Your question is ill-posed, as the probability distribution of the dimensions will heavily influence how much wastage you will have. For example, if most of your rectangles are slightly more than half the sheet length and half the sheet width, the rest of the sheet will go waste. I don't think there is a simple answer. See this paper for an algorithm to solve a "chance constrained" knapsack problem where they assume normal distribution of the input sizes.

If you are looking for a practical solution, first estimate the distributions of the dimensions of the rectangles. Typically you approximate them using an iid normal distribution. Once you get those, just run a simulation by drawing random rectangles from this distribution and use a knapsack solver to see how many you can fit on a sheet. If you do enough sampling -- assuming your assumption of normal distribution works in practice -- you will get an approximate estimate for the amount of wastage.