TY - JOUR
T1 - Roll cutting in the curtain industry, or: A well-solvable allocation problem
AU - Alfieri, A.
AU - Velde, van de, S.L.
AU - Woeginger, G.J.
PY - 2007
Y1 - 2007
N2 - 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 dmin, 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 dmax (with dmax > dmin), 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.
AB - 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 dmin, 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 dmax (with dmax > dmin), 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.
U2 - 10.1016/j.ejor.2005.11.065
DO - 10.1016/j.ejor.2005.11.065
M3 - Article
VL - 183
SP - 1397
EP - 1404
JO - European Journal of Operational Research
JF - European Journal of Operational Research
SN - 0377-2217
IS - 3
ER -