0

In our application, we need to calculate the number of sheets required to perform a manufacturing process.

So we start with a number of sheets of material, all of the same dimension - these are 2d, so it'll just be length x girth. We have a number of items to be cut from these sheets, all with different dimensions. We need to figure out how many sheets will be required for a list of items, and try to find the most efficient way of using the sheets. What'd be a huge plus is the ability for it to draw a simple diagram of how it'll look on the sheets.

I'm just wondering if there are any free libraries available that can do this?

rene
  • 41,474
  • 78
  • 114
  • 152
Chris
  • 7,415
  • 21
  • 98
  • 190
  • 4
    What you have is a 2D bin-packing problem. You can get a good description of the problem and a possible solution at http://stackoverflow.com/q/8762569/56778 – Jim Mischel Sep 16 '13 at 16:00
  • You need to apply a GRASP algorithm (greedy randomized adaptive search procedure). There are others but on this one I can give you some info about the logic implementation/sequence and methods (in italian) you can use google translator :-). It is a 111 pages document. – FeliceM Sep 16 '13 at 16:44
  • Are there mechanical or practical limitations to your cutting equipment (whatever it may be)? For example, is it feasible to have overlapping cut lines? Could you give examples of the shapes you need to cut and perhaps some other engineering specifications? This paper might provide enough of a review to get you started: http://cimar.mae.ufl.edu/CIMAR/pages/thesis/Pasha_A_CISE.pdf – Rethunk Sep 16 '13 at 23:51

1 Answers1

2

This seems like a pretty classical example of the Knapsack problem.

Instead of weight to fit in the knapsack, you're optimizing area to fit on each sheet.

It's a pretty well-studied, well-solved problem, so I would just google around for ways to implement it.

nathas
  • 949
  • 1
  • 9
  • 15
  • 2
    Hmm.. I think Knapsack in 2D is NP hard. I don't know that the algorithms for solving the Knapsack problem would be directly useful here. – Mike Dinescu Sep 16 '13 at 16:02