When building log houses, you must first cut full-length logs from stock to smaller logs in the factory. These logs are packed into their own pallets in the order of installation and the pallets are delivered to the construction site.
While cutting the full-length logs to smaller logs, there will be some trim loss, also known as waste. We developed an algorithm to minimize the trim loss. On top of the trim loss minimization the algorithm had to consider the space limitations in the production lines in the factory. There is only room for a certain number of log pallets to simultaneously exist next to the production lines, and the logs must be cut so that this limit is never exceeded.
The solution we developed used dynamic programming with a heuristic algorithm. It allowed to reduce the trim loss from dozens of percentages to near one percentage. At the same time, the number of allowed open log pallets was never exceeded, and each log pallet contained only logs that were installed after each other.
Cutting stock problem
Cutting stock problem is a well known NP-hard branch of optimization problem that studies how to cut raw material (input/stock items) into smaller predefined shapes (output items or demand), while optimizing some objective or objectives, usually the trim loss, also known as waste. The topic is well researched since it’s such a usual problem to have across many industries, such as steel, glass, fiber, and wood industries.
The problem can be divided into three main categories by its dimensionality, that is three-, two-, and one-dimensional cutting stock problem. When planning how to cut logs, the correct algorithm can be found from the one-dimensional family of the problem, since we are only interested in the lengthwise cuts. Therefore, the algorithm we developed utilized algorithms that are applicable to one-dimensional problems.
Requirements for the algorithm
The literature on the cutting stock problem mostly considers the situation where you have predefined dimensions for the output items that can’t be changed. However, with logs the lengths of each log are not predefined. They can be cut into smaller parts and combined into larger parts as needed. For example, one eight meters long log could be formed from:
1. one eight meters log
2. two four meters logs
3. four two meters logs
4. one three meters, and one five meters logs
and so on.
However, while the trim loss would be rather easy to minimize by cutting as small logs as possible, that wouldn’t be visually pleasing, nor would it be structurally bearing. A wall that is built solely from short logs could collapse easier than a wall made of longer logs. So, we prefer to use as long logs as possible.
The algorithm should also consider the installation order of the logs and the capacity limitations of the production line. The output logs should be placed into pallets, so that each pallet only contains logs that are installed after each other. The production lines only have space for a limited number of simultaneous log pallets. So, if there were only room for three log pallets next to the production line, it would not be possible to cut logs that belong to ten different pallets. Also, the longest logs should be placed at the bottom of the pallets so shorter logs can be piled on top of them.
Example
Let’s consider the situation depicted in the Figure 1. We have an unlimited number of 10 meters long logs to use as input. We want to produce three logs of type A, and one log of type B and C each. A traditional cutting stock problem doesn’t allow you to divide and combine items, and an optimal solution for the given problem with a traditional approach would look as depicted in Figure 2. So as a result, there would be a total of 10 meters of trim loss.
If we could divide and combine the items, like it’s possible to do with logs, we might end up with an optimal cutting plan as depicted in Figure 3. Now there would be no trim loss at all, since we are able to combine the blue 3 meters, and 2 meters items into one 5 meters item.
Solution and results
We used dynamic programming with a heuristic algorithm to solve the problem. This approach is not guaranteed to produce the best possible results but it will provide good enough results most of the time. The solution we developed was tested with two real-life log house projects that were chosen randomly. We were able to reduce the trim loss from 15,3% to 1,1% for the first project and from 23,6% to 2,5% for the other project compared to a naïve algorithm to solve the problem.
Let’s say the raw material for logs for each of the projects we tested were to cost 20 000€. This would mean that we would save 2 840€ in material costs for the first project and 4 220€ for the second project.
The algorithm was tested with many different project and parameter configurations and the algorithm was found to be quite fast. The speed of the algorithm ranges between a dozen milliseconds for the easiest and 2.5 seconds for the hardest instance. This means the algorithm is easily viable for any real-life usage.
Future research and applications
The algorithm can be further developed to produce even lower trim loss, faster results, and support for new objectives and constraints can be added.
For example the trim loss could be further minimized by adding the residual pieces from processed input items as new available input items in the next stacks. For example, if we had stack four stacks and stacks {1,2} and {3,4} were processed together. After stacks {1,2} are processed, the leftover pieces could be added as available input items when processing stacks {3,4}. This way, items that would otherwise be counted as trim loss, can be made into better use.
The algorithm could be used outside log cutting, for example when cutting iron bars or any other one dimensional objects that can be divided and joined back together.