{"id":201,"date":"2014-12-01T12:00:49","date_gmt":"2014-12-01T01:00:49","guid":{"rendered":"http:\/\/scipilot.org\/blog\/?p=201"},"modified":"2015-01-06T22:02:30","modified_gmt":"2015-01-06T11:02:30","slug":"cutlass-cut-less","status":"publish","type":"post","link":"https:\/\/scipilot.org\/blog\/2014\/12\/01\/cutlass-cut-less\/","title":{"rendered":"Cutlass – Cut Less!"},"content":{"rendered":"

While re-building my house I became obsessed with getting efficiency out of the timber 10materials I was using when planning cutting lists.\u00a0Most people would want to achieve an efficient cutting plan\u00a0because of cost-efficiency, effort-reduction or ecological\u00a0conservation, and of course that was true for me but being a huge nerd I was even more intrigued by the\u00a0devilishly difficult planning problem itself. Surely an algorithm could be produced to make cutting lists easy to produce, and thereby save enormous amounts of trees?<\/p>\n

So what’s the problem?<\/p>\n

The Problem<\/h2>\n

Well I have a) a long list of measured lengths to make tongue and grooved lining boards fit horizontally around our many doors and windows and b) a bunch of raw timber in standard lengths. The challenge is to cut the timber so the waste offcut each time can also be used.<\/p>\n

\"Cutlass<\/a><\/p>\n

The Solutions<\/h2>\n

The woodyard-recommended\u00a0solution is to order 10% more timber than you need and hope.\u00a0Then you just throw away the waste. Of course they would<\/em> recommend you spend 10% more, but I just don’t find this an acceptable attitude.<\/p>\n

After trying to figure out a process myself for three complex rooms and 150m of timber I\u00a0almost had a brain meltdown, I did some research into online tools and then common algorithms. Of course this is a\u00a0very\u00a0old problem!<\/p>\n

At first I researched the “cutting stock problem” but this is mostly oriented towards reducing waste from cutting 2D sheets of fabric, timber or metal and incorporates complex requirements like reducing knife-changing interruptions.<\/p>\n

I found it difficult to find a 1D cutting algorithm, until I came across the “bin packing problem”, which is functionally equivalent to this problem. All you have to do is tilt your head on one side, and view the ‘bins’ as\u00a0the original stock and the vertical heights of the objects being placed in the bins as the planned lengths required.<\/p>\n

\"Cutlass<\/a><\/p>\n

The first-fit algorithm is pretty simple: you find\u00a0the next longest length in\u00a0your requirement\u00a0plan and take that away from the first stock with enough left (i.e. put it in the first bin). Repeat.<\/p>\n

It’s not guaranteed to find the overall<\/em> best usage\u00a0for all items. In theory, if you tried all possible combinations you could probably get a lot more zero-waste planks, but this sounds like one of those more-atoms-than-the-universe scenarios to me. I might add some level of re-try to it later or do more research into simultaneous equations, which I suspect could offer\u00a0a solution.<\/p>\n

My Implementation<\/h2>\n

Of course programming this will have a few more practical details like initially sorting the required lengths and handling problems like running out of stock, but that’s the basic algorithm. So I cracked open a new Bootstrap theme and wrote it in Javascript to avoid any unnecessary back-end requirements:<\/p>\n

\/*\r\n * Best fit tries to fill the available slots with the minimum remaining.\r\n * Slots are only brought online when no previous slots can be fitted into.\r\n * You start with one slot online, and put the first item into it.\r\n *\/\r\nbestFitAlgorithm: function(aTimberList, aCuttingList){\r\n  \/\/ first we assume there's only one entry in the timber list - phase one!\r\n  var iPlankSize = aTimberList[0][0];\r\n  var iNoPlanks = aTimberList[0][1];\r\n  var aPlanks = [];\r\n  var count, len, min, p, remaining;\r\n\r\n  \/\/ iterate over the required lengths\r\n  for(var i in aCuttingList){\r\n    len = aCuttingList[i][0];\r\n    count = aCuttingList[i][1];\r\n    while(count--){\r\n      \/\/ Check all online planks in order\r\n      min = iPlankSize;\r\n      p = null;\r\n      for(var j in aPlanks){\r\n        remaining = aPlanks[j].remaining - len;\r\n        if(remaining >= 0 && remaining < min){\r\n           min = remaining;\r\n          p = j;\r\n        }\r\n      }\r\n      if(p != null){\r\n        \/\/ p is the best fit.\r\n         aPlanks[p].remaining = min;\r\n        aPlanks[p].pieces.push(len);\r\n      }\r\n      else {\r\n        \/\/ No fit found, bring another plank online\r\n        aPlanks.push({remaining:iPlankSize-len, pieces:[len]});\r\n      }\r\n    }\r\n  }\r\n  return aPlanks;\r\n}<\/pre>\n
I surrounded this with some self-unit-testing, a JQuery plugin wrapper and a basic form UI to talk to the humans, and went to work.<\/p>\n
The Real World Beta Test – My Lining Boards<\/h2>\n
The plan\u00a0that I actually needed was as follows, with length of item in mm (len) and how many\u00a0(off).<\/p>\n
len  off\r\n3100 2\r\n2900 1\r\n360 1\r\n305 16\r\n1300 2\r\n245 13\r\n3740 4\r\n440 8\r\n1070 1\r\n190 7\r\n900 1\r\n4000 2\r\n3820 5\r\n140 9\r\n110 15\r\n1200 2\r\n230 15\r\n120 15\r\n1450 23\r\n500 15\r\n2820 1\r\n120 15\r\n380 15\r\n200 9\r\n1150 3\r\n1150 6\r\n140 9\r\n1270 18<\/pre>\n
My stock was 5400mm lengths of pre-primed T&G grooved panelling. The algorithm\u00a0came up with the following cutting list, where the first number is the stock plank index, then the length to cut and finally the waste.<\/p>\n
I added a default 3mm kerf (the width of the cut made by the saw) which is easy to forget when planning cuts and soon adds up to a significant amount\u00a0– especially when you are trying to achieve near zero-wastage with many small pieces (see bottom planks).<\/p>\n
0: 4000,1300 waste:100\r\n1: 4000,1300 waste:100\r\n2: 3820,1450,120 waste:10\r\n3: 3820,1450,120 waste:10\r\n4: 3820,1450,120 waste:10\r\n5: 3820,1450,120 waste:10\r\n6: 3820,1450,120 waste:10\r\n7: 3740,1450,200 waste:10\r\n8: 3740,1450,200 waste:10\r\n9: 3740,1450,200 waste:10\r\n10: 3740,1450,200 waste:10\r\n11: 3100,1450,500,305 waste:45\r\n12: 3100,1450,500,305 waste:45\r\n13: 2900,1450,900,140 waste:10\r\n14: 2820,1450,1070 waste:60\r\n15: 1450,1450,1450,500,500 waste:50\r\n16: 1450,1450,1450,500,500 waste:50\r\n17: 1450,1450,1450,500,500 waste:50\r\n18: 1450,1270,1270,1270,140 waste:0\r\n19: 1270,1270,1270,1270,305 waste:15\r\n20: 1270,1270,1270,1270,305 waste:15\r\n21: 1270,1270,1270,1270,305 waste:15\r\n22: 1270,1270,1270,1200,380 waste:10\r\n23: 1200,1150,1150,1150,500,245 waste:5\r\n24: 1150,1150,1150,1150,500,245 waste:55\r\n25: 1150,1150,500,500,500,500,500,440,140 waste:20\r\n26: 440,440,440,440,440,440,440,380,380,380,380,380,380 waste:40\r\n27: 380,380,380,380,380,380,380,380,360,305,305,305,305,305,305,140 waste:30\r\n28: 305,305,305,305,305,245,245,245,245,245,245,245,245,245,245,245,230,230,230,230,230 waste:30\r\n29: 230,230,230,230,230,230,230,230,230,230,200,200,200,200,200,190,190,190,190,190,190,190,140,140,140,140,140 waste:70\r\n30: 140,140,140,140,140,140,140,140,140,120,120,120,120,120,120,120,120,120,120,120,120,120,120,120,120,120,120,120,120,120,120,120,120,120,110,110,110,110,110,110,110,110,110,110 waste:40\r\n31: 110,110,110,110,110 waste:4850\r\n\r\nTotal timber length: 167005\r\nTotal waste:5795\r\nPercentace waste:3.47%<\/pre>\n
So that was pretty impressive 3.5% wastage which is a third of the accepted industry standard.<\/p>\n
In theory!<\/p>\n