Roll cutting in the curtain industry,or: A well-solvable allocation problem |
| |
| Authors: | Arianna Alfieri Steef van de Velde Gerhard J Woeginger |
| |
| Institution: | 1. Dipartimento dei Sistemi di Produzione ed Economia dell’Azienda, Polytechnic University of Turin, Corso Duca degli Abruzzi, 24, 10129 Torino, Italy;2. RSM, Erasmus University, P.O. Box 1738, 3000 DR Rotterdam, The Netherlands;3. Department of Mathematics and Computer Science, Eindhoven University of Technology, P.O. Box 516, 5600 MB Eindhoven, The Netherlands |
| |
| Abstract: | 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. |
| |
| Keywords: | Cutting Allocation problem Polynomial time algorithm |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
