{"id":465,"date":"2026-04-06T19:42:58","date_gmt":"2026-04-06T19:42:58","guid":{"rendered":"https:\/\/permutationcity.co.uk\/bp\/?p=465"},"modified":"2026-04-07T08:40:25","modified_gmt":"2026-04-07T08:40:25","slug":"bin-packing-problem","status":"publish","type":"post","link":"https:\/\/permutationcity.co.uk\/bp\/2026\/04\/06\/bin-packing-problem\/","title":{"rendered":"Bin-packing problem"},"content":{"rendered":"\n

I’ve been woodworking for a while.\nBig things, cabinets and a kitchen table, and small things, jewellery boxes and drawers.\nI was given a wooden jigsaw puzzle at Christmas and\nthis led to my latest interest.\nA laser cutter is amazingly precise.\nThe beam is 0.1 mm wide and the parts can be whatever shape you can design.\nHowever everything has to be cut out of flat sheets and then assembled from there.\nIt feels like a different direction from taking a 2×4 timber and a table saw.<\/p>\n\n\n\n

Shape placement<\/h2>\n\n\n\n

Once you have your individual shapes you have to fit them on to, say, plywood sheets. To avoid waste you want to fit as many as possible on each sheet. Obviously this can be done by hand. It doesn’t take that long with 10-20 shapes. However if there’s lots then it’s easier to just let the software do it.<\/p>\n\n\n\n

I’ve been using\nOnshape<\/a>\nfor my designs.\nIt’s got a laser cutter plug-in to do this placement.\nIt’s quick but not optimal.\nFortunately there are other options.\nI’ve settled on\ndeepnest-next<\/a>.\nIt comes up with a basic solution and then iterates looking for better solutions.<\/p>\n\n\n\n

This is a computationally hard problem. The bin packing problem<\/a> is part of the NP-complete<\/a> family. You probably won’t be finding a perfect solution to any of these. Sometimes you need to quickly recognise that perfection is impossible and look for something that is good enough.<\/p>\n\n\n\n

Apothecary cabinet<\/h2>\n\n\n\n

My latest design are for things like this,\na prototype for an\napothecary cabinet<\/a>.<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

After iterating for a while this is what deepnest came up with this:<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

<\/p>\n\n\n\n

I’m struck by how messy it looks.\nThat doesn’t matter to the laser but is less convenient when I’m taking the parts out later.\nThe software is optimising for two things: space used and time to cut.\nThe first is obvious but the second less so.\nIf two parts can share an edge then the laser only has to make one cut.\nIt does look as though switching some parts around would increase sharing.\nWhat’s going on?<\/p>\n\n\n\n

Details matter<\/h2>\n\n\n\n

The laser cut is small, 0.1 mm.\nWhile that’s small it’s not nothing.\nYou have to account for this in your shapes.\nI’ve been relying on a kerf offset<\/em> that automatically adjusts the beam by that amount as it cuts the shape.\nI told deepnest to leave at least this much room between the parts.\nIt could be that with gaps between all the shapes it can’t optimise them to share lines?<\/p>\n\n\n\n

Another option is to offset the shapes by 0.1 mm before you start.\nThis adds a manual step but gives deepnest the real<\/em> shape to work with.\nLet’s see if it can do any better:<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

<\/p>\n\n\n\n

The big pieces are in the same places. The small pieces are scattered differently. No, no it can’t do better.<\/p>\n\n\n\n

Manual layout<\/h2>\n\n\n\n

Here’s my own attempt:<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

<\/p>\n\n\n\n

This is what I mean by better. The laser cutting software predicts this will be faster to cut out, 24 minutes compared to 27 for the deepnest versions. By placing similar pieces next to each other I get them to share more of their lines. Not only that but the layout just looks<\/em> better. Each type of shapes is grouped together. It’s going to be easier to sort the parts out. Plus there’s some left over plywood that I can reuse later. I know the deepnest software uses a genetic algorithm<\/a>. That means it has a method of evaluating cut patterns to assign them a score. In theory it could be extended to value putting like with like.<\/p>\n\n\n\n

In the end<\/h2>\n\n\n\n

I want the software to do things it’s not been written to do.\nIt only cares about space and time,\nnot about making things neat.\nHowever in this small<\/em> case I was able to do better with both myself.\nFor bigger cases I think the software would start winning.\nI can lay out a single sheet but\nif there a dozen sheets then I’m going to get tired and the software isn’t.<\/p>\n","protected":false},"excerpt":{"rendered":"

I’ve been woodworking for a while. Big things, cabinets and a kitchen table, and small things, jewellery boxes and drawers. I was given a wooden jigsaw puzzle at Christmas and this led to my latest interest. A laser cutter is amazingly precise. The beam is 0.1 mm wide and the parts can be whatever shape […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_import_markdown_pro_load_document_selector":0,"_import_markdown_pro_submit_text_textarea":"","footnotes":""},"categories":[1],"tags":[22],"class_list":["post-465","post","type-post","status-publish","format-standard","hentry","category-general","tag-algorithms"],"_links":{"self":[{"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/posts\/465","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/comments?post=465"}],"version-history":[{"count":9,"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/posts\/465\/revisions"}],"predecessor-version":[{"id":486,"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/posts\/465\/revisions\/486"}],"wp:attachment":[{"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/media?parent=465"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/categories?post=465"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/tags?post=465"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}