Hi there!

As promised in my previous dev post: I have performed series of test how efficient the algorithm is and the results are satisfactory – average of 82% utilisation.

* Methodology
*To measure the efficiency I ran 10 iterations of randomly generated set of rectangles. The size of the panel was fixed to 1500×3000 as this is standard size of sheet and most commonly used – at least that is my experience. Exact size of items was generated randomly, however there were some constraints to make the test more life-like. The list below illustrates that:

- 15 items of size 50 to 60% panel size
- 20 items of size 30 to 40% panel size
- 30 items of size 20 to 30% panel size
- 50 items of size 5 to 20% panel size

The number of panels was limited to 10 – this is to avoid having last panel filled only in quarter or half; the test is to check how densely the algorithm can pack items. In real application it is common to that the last panel is used only in fraction.

* Tool*To perform the test I used xUnit. I wrote a unit test which doesn’t assert anything, just print the output string.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
[Fact] public void RandomTester() { IBatch batch = GetRandomBatch(1500, 3000, 10, 15, 20, 30, 50); List<IPanel> panels = new List<IPanel>(); for(int i = 1; i <=10; i++) { panels.Add(new Panel(1500, 3000)); } ICalculation calc = new Calculation(batch, panels); calc.Calculate(ItemAreaComparer.Instance, ItemHeightComparer.Instance, ItemWidthComparer.Instance, HSector.Instance); output.WriteLine(calc.OutputBest()); } private IBatch GetRandomBatch(int _h, int _w, int _m, int _r1, int _r2, int _r3, int _r4) { Random randGen = new Random(DateTime.Now.GetHashCode()); Random randBool = new Random(DateTime.Now.GetHashCode()); IBatch batch = new Batch(); RandomRange r1 = new RandomRange(Convert.ToInt32(_h*0.6), Convert.ToInt32(_w * 0.6), Convert.ToInt32(_h * 0.5), Convert.ToInt32(_w * 0.5), _r1); RandomRange r2 = new RandomRange(Convert.ToInt32(_h * 0.4), Convert.ToInt32(_w * 0.4), Convert.ToInt32(_h * 0.3), Convert.ToInt32(_w * 0.3), _r2); RandomRange r3 = new RandomRange(Convert.ToInt32(_h * 0.3), Convert.ToInt32(_w * 0.3), Convert.ToInt32(_h * 0.2), Convert.ToInt32(_w * 0.2), _r3); RandomRange r4 = new RandomRange(Convert.ToInt32(_h * 0.2), Convert.ToInt32(_w * 0.2), Convert.ToInt32(_h * 0.05), Convert.ToInt32(_w * 0.05), _r4); RandomRange[] ranges = { r1, r2, r3, r4 }; foreach(RandomRange r in ranges) { for(int i = 1; i<=r.QTY; i++) { int h = randGen.Next(r.MinH, r.MaxH); int w = randGen.Next(r.MinW, r.MaxW); bool rot = false; if (randBool.Next(1, 1000) > 500) { rot = true; } batch.AddItem(new Item(h, w, _m, rot)); } } return batch; } private struct RandomRange { public int MaxH; public int MaxW; public int MinH; public int MinW; public int QTY; public RandomRange(int _maxH, int _maxW, int _minH, int _minW, int _qty) { MaxH = _maxH; MaxW = _maxW; MinH = _minH; MinW = _minW; QTY = _qty; } } |

*Results*

As written at the very beginning the average utilisation is around 82%. I find that value satisfactory. Here’s quick extract from the report with most important figures:

Overall average utilisation: 0.8226

Overall max utilisation: 0.838

Overall min utilisation: 0.807

Single panel max utilisation: 0.911

Single panel min utilisation: 0.694

*Conclusion*

The algorithm performs sufficiently well. At this point I won’t look for further improvements.

Thanks, Michal

Report in xlsx

SheetMetalArranger on GitHub