Roll cutting in the curtain industry, or: A well-solvable allocation problem

A. Alfieri, S.L. Velde, van de, G.J. Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)

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 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.
Original languageEnglish
Pages (from-to)1397-1404
JournalEuropean Journal of Operational Research
Volume183
Issue number3
DOIs
Publication statusPublished - 2007

Fingerprint Dive into the research topics of 'Roll cutting in the curtain industry, or: A well-solvable allocation problem'. Together they form a unique fingerprint.

  • Cite this