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
