Some time ago I had met at my work with an interesting problem. I was working for a construction company, in the warehouses, managers order different size tubes which are divided into smaller parts called panels. Panels have different lengths as well but always less than a length of tubes. To construct a building, the company needs to create a lot of panels which are obtained by cutting tubes. The leftover tubes cannot be combined with each other, hence, the rest of the used tube will be less than the smaller required panel it must be thrown away (so-called a scrap). Utilization of scrap is costly, so production excessive scrap is unfavorable.

What are the problems?

  • What length of tubes do managers need to order so that scrap amount will be as low as possible?
  • How to cut ordered tubes to get all the required panels?

Perhaps you guessed it! The problem is strongly related to the ‘bin packing problem’ but with a significant difference – containers (bins) can have a variable size. Unfortunately, the problem is not easy to fix, moreover, it belongs to NP-hardness class of problem.

How can it be resolved? I think there are many solutions, some are effective, others are time-consuming. I will try to quickly describe several of them.

Deep learning

One of the solutions is described here.

Heuristics

  • J.Kang, S.Park, Algorithms for the variable sized bin packing problem
  • M.Maiza, A.Labed M.S. Radjef, Efficient algorithms for the offline variable sized bin-packing problem

A simple case using only one length of the tube

If we choose only one length of tube (preferable, the longest), an unusual bin packing problem will start to occur with one exception – the last packing phase will select the shortest possible tube.

I recommend trying to implement one of above solution and test it using cases where usual bin packing algorithm does not return optimal results.

About The Author

I am a software developer from Poland, currently focused on the .NET platform. I’ve been incredibly passionate about IT since a young age and am always seeking to expand my skillset. Furthermore, my personal development plan includes machine learning, cryptocurrency, image processing, and the Scrum framework. Turning to the personal part of my life. I’m a licensed paraglider holding an International Pilot Proficiency Information Card, a proud Arsenal F.C. supporter and avid traveller with an infatuation for the natural beauty of New Zealand. I’m keen on unusual or extreme sports, and I love to discover and try out new things.

Related Posts

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.