CUTTING STOCK PROBLEMS

9th, April, 2019.

One interesting task that I have met in Optimisation coursework is the “cutting-stock” problem. The problem is that given unlimited standard rods of equal length \(L\) meters, we need to cut them into different smaller, yet specified sized pieces in order to produce enough required numbers of the small pieces, e.g. \(n_i\) number of small pieces of length \(l_i\) for \( i = 1, \cdots, m\), while minimizing the total wasted material.
The objective of the problem can be stated equivalently in a different way. Instead of minimizing material wasted, we prefer to consider minimizing the total number of used rods. It is apparent that the alternative optimisation problem is more advantageous than the original one since the objective function look simpler while retaining the same constraints and variables. Here the problem consists of two main constraints. The first constraint is to ensure that we have cut enough numbers of specific sized rods while the second one is to ensure that the cutting pattern is feasible or meaning, the total length of pieces, which are cut from one rod, is smaller or equal to the length of that rod.
Generally, the number of possible cutting patterns grows very quickly (exponential increasing) in terms of \(m\), number of different types of rod pieces. Hence, it may become impractical to generate all possible cutting patterns and use it as a part of the model. In terms of computational complexity, this problem is an NP-complete one. Even though there are more modern algorithms which can solve the one dimensional cutting problem up to very large scale but they are, in general, very expensive. Therefore, it is necessary to find the heuristic algorithm to find approximate solutions. Moreover, the below greedy type algorithm is such very fast algorithm, relevant to every kinds of data format and can be implemented to any available free programming software.
Here is the idea of the algorithm:

  • All required pieces of length which is larger than \(L\) are excluded from the problem. Since it is impossible to cut the rods of length \(L\) into items of larger size.
  • Make all required items sorted in descending order with respect to their lengths. Supposed that the problem requirement is to produce \(n_i\) rods of length \(l_i\) for \( i = 1, \cdots, m\) where \( l_1 \geq l_2 \geq \cdots \geq l_m\). Let call this set of items be \(S\).
  • Take each stock rod of length \(L\) each time.
  • If \( S \neq 0\) , then take the item \(i\) with lowest index with \(l_i < L\) , cut it from the rod and update the length of this rod is \( L = L – l_i\), the number required item of length \(l_i\) becomes \(n_i = n_i -1\) and discard this item from the list \(S\). If we do not find such item \(i\) and the set \(S\) is not empty , then take another rod and do it again.
  • If the set \(S\) is empty, then STOP.
Let’s see one simple illustrated example. We have unlimited rods of length \(6000\) mm. Here there are \(7\) different types (different length) with \(95\) pieces that is our desired output in the following table.

centered image

Table 1. - Requirement of the problem.
We need to discard the first \(4\) items having larger lengths than the standard rods. Now starting with the first rod. After cutting one item of length \(3880\), the remaining rod has the length of \(2115\) mm. Then considering the first item in \(S\) with length smaller than \(2115\) mm which is \(1675\) mm and we cut it from the rod. Then the remainder has the length of \(435\) mm. We cut the item has length \(70\) mm from the rod and so on. At the end we obtain the remainder has the length of \(45\) mm which is smaller than the smallest length in the table, therefore the wastage for the first rod is 45 mm. Similarly, we will perform the cutting rods one by one until we get the required output. And here is the results of this algorithm.

centered image

Table 2. Results of the cuttings from the algorithm.
This can been easily seen that the minimum number of rod that have to be cut for the solution is at least the maximum of the number of items with length \(l_i > L/2\), which is \(22\), and the ceiling of the total length of all required items divided by \(L\), which is \(21\). From the table, indeed, we use exactly \(22\) rods, hence we obtain the exact solution from this algorithm. However, as mentioned before, due to the cost of computation, the algorithm just ensures that the approximate solution obtained. Hence, in few cases, it is possible to derive not the most economical cutting. Therefore, further improvement of the greedy algorithm has been proposed, please find the reference.
There are an extension of the one dimensional cutting problem to the two dimensional one which is much more complex and states as following:
A piece of paper with width of \(X\) mm and length of \(Y\) mm is given. There are many small rectangles with dimensions \((a_i, b_i)\) with \( i = 1, . . . , n\) should be arranged over the paper. The aim is to arrange these rectangles such that they fill the entire width of the paper, however, with the minimal length of the sheet.
The formulation of higher dimensional cutting problem is exactly the same as one dimensional problem given above. However finding the feasible solution by solving the optimisation problem is expensive as well. Fortunately, the simple genetic type algorithm has been proposed in the following reference to find the near optimal solution.

Reference:
1. Avdzhieva, Ana & Balabanov, Todor & Kamburova, Detelina & Kostadinov, Hristo & Tsachev, Tsvetomir & Zhelezova, Stela & Zlateva, Nadia. (2015). Optimal Cutting Problem.
2. Robert W. Haessler, Paul E. Sweeney, Cutting stock problems and solution procedures, European Journal of Operational Research, Volume 54, Issue 2, 1991, Pages 141-150, ISSN 0377-2217.



Comments Please: