relation: http://miis.maths.ox.ac.uk/miis/329/
title: Pattern Reduction in Paper Cutting
creator: Aldridge, C.
creator: Chapman, S. J.
creator: Gower, R.
creator: Leese, R.
creator: McDiarmid, C.
creator: Shepherd, M.
creator: Tuenter, H.
creator: Wilson, H.
creator: Zinober, A.
subject: Discrete
subject: Retail
subject: None/Other
description: A large part of the paper industry involves supplying customers with reels of specified width in specifed quantities. These 'customer reels' must be cut from a set of wider 'jumbo reels', in as economical a way as possible. The first priority is to minimize the waste, i.e. to satisfy the customer demands using as few jumbo reels as possible. This is an example of the one-dimensional cutting stock problem, which has an extensive literature. Greycon have developed cutting stock algorithms which they include in their software packages.    Greycon's initial presentation to the Study Group posed several questions, which are listed below, along with (partial) answers arising from the work described in this report.    (1) Given a minimum-waste solution, what is the minimum number of patterns required?    It is shown in Section 2 that even when all the patterns appearing in minimum-waste solutions are known, determining the minimum number of patterns may be hard. It seems unlikely that one can guarantee to find the minimum number of patterns for large classes of realistic problems with only a few seconds on a PC available.    (2) Given an n → n-1 algorithm, will it find an optimal solution to the minimum- pattern problem?    There are problems for which n → n - 1 reductions are not possible although a more dramatic reduction is.    (3) Is there  an efficient  n → n-1 algorithm?    In light of Question 2, Question 3 should perhaps be rephrased as 'Is there an efficient algorithm to reduce n patterns?' However, if an algorithm guaranteed to find some reduction whenever one existed then it could be applied iteratively to minimize the number of patterns, and we have seen this cannot be done easily.    (4) Are there efficient 5 → 4 and 4 → 3 algorithms?  (5) Is it worthwhile seeking alternatives to greedy heuristics?    In response to Questions 4 and 5, we point to the algorithm described in the report, or variants of it. Such approaches seem capable of catching many higher reductions.    (6) Is there a way to find solutions with the smallest   possible number of single patterns?    The Study Group did not investigate methods tailored specifically to this task, but the algorithm proposed here seems to do reasonably well. It will not increase the number of singleton patterns under any circumstances, and when the number of singletons is high there will be many possible moves that tend to eliminate them.    (7) Can a solution be found which reduces the number  of knife changes?    The algorithm will help to reduce the number of necessary knife changes because it works by bringing patterns closer together, even if this does not proceed fully to a pattern reduction. If two patterns are equal across some of the customer widths, the knives for these reels need not be changed when moving from one to the other.
type: Study Group Report
type: NonPeerReviewed
format: application/pdf
language: en
identifier: http://miis.maths.ox.ac.uk/miis/329/1/Pattern-reduction-in-paper-cutting.pdf
identifier:   Aldridge, C. and Chapman, S. J. and Gower, R. and Leese, R. and McDiarmid, C. and Shepherd, M. and Tuenter, H. and Wilson, H. and Zinober, A.   Pattern Reduction in Paper Cutting.  [Study Group Report]