Roll cutting in the curtain industry, or: A well-solvable allocation problem
European Journal of Operational Research , Volume 183 - Issue 3 p. 1397- 1404
We study the problem of cutting a number of pieces of the same length from n rolls of different lengths so that the remaining part of each utilized roll is either sufficiently short or sufficiently long. A piece is ‘sufficiently short’, if it is shorter than a pre-specified threshold value δmin, so that it can be thrown away as it cannot be used again for cutting future orders. And a piece is ‘sufficiently long’, if it is longer than a pre-specified threshold value δmax (with δmax > δmin), so that it can reasonably be expected to be usable for cutting future orders of almost any length. We show that this problem, faced by a curtaining wholesaler, is solvable in O(nlogn) time by analyzing a non-trivial class of allocation problems.
|Polynomial time algorithm, allocation problem, cutting, future orders|
|ERIM Top-Core Articles|
|European Journal of Operational Research|
|Organisation||Erasmus Research Institute of Management|
Alfieri, A, Woeginger, G.J, & van de Velde, S.L. (2007). Roll cutting in the curtain industry, or: A well-solvable allocation problem. European Journal of Operational Research, 183(3), 1397–1404. doi:10.1016/j.ejor.2005.11.065