?url_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adc&rft.relation=http%3A%2F%2Fmiis.maths.ox.ac.uk%2Fmiis%2F329%2F&rft.title=Pattern+Reduction+in+Paper+Cutting&rft.creator=Aldridge%2C+C.&rft.creator=Chapman%2C+S.+J.&rft.creator=Gower%2C+R.&rft.creator=Leese%2C+R.&rft.creator=McDiarmid%2C+C.&rft.creator=Shepherd%2C+M.&rft.creator=Tuenter%2C+H.&rft.creator=Wilson%2C+H.&rft.creator=Zinober%2C+A.&rft.subject=Discrete&rft.subject=Retail&rft.subject=None%2FOther&rft.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'%2C+in+as+economical+a+way+as+possible.+The+first+priority+is+to+minimize+the+waste%2C+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%2C+which+has+an+extensive+literature.+Greycon+have+developed+cutting+stock+algorithms+which+they+include+in+their+software+packages.%0D%0A%0D%0AGreycon's+initial+presentation+to+the+Study+Group+posed+several+questions%2C+which+are+listed+below%2C+along+with+(partial)+answers+arising+from+the+work+described+in+this+report.%0D%0A%0D%0A(1)+Given+a+minimum-waste+solution%2C+what+is+the+minimum+number+of+patterns+required%3F%0D%0A%0D%0AIt+is+shown+in+Section+2+that+even+when+all+the+patterns+appearing+in+minimum-waste+solutions+are+known%2C+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.%0D%0A%0D%0A(2)+Given+an+n+%E2%86%92+n-1+algorithm%2C+will+it+find+an+optimal+solution+to+the+minimum-+pattern+problem%3F%0D%0A%0D%0AThere+are+problems+for+which+n+%E2%86%92+n+-+1+reductions+are+not+possible+although+a+more+dramatic+reduction+is.%0D%0A%0D%0A(3)+Is+there++an+efficient++n+%E2%86%92+n-1+algorithm%3F%0D%0A%0D%0AIn+light+of+Question+2%2C+Question+3+should+perhaps+be+rephrased+as+'Is+there+an+efficient+algorithm+to+reduce+n+patterns%3F'+However%2C+if+an+algorithm+guaranteed+to+find+some+reduction+whenever+one+existed+then+it+could+be+applied+iteratively+to+minimize+the+number+of+patterns%2C+and+we+have+seen+this+cannot+be+done+easily.%0D%0A%0D%0A(4)+Are+there+efficient+5+%E2%86%92+4+and+4+%E2%86%92+3+algorithms%3F%0D%0A(5)+Is+it+worthwhile+seeking+alternatives+to+greedy+heuristics%3F%0D%0A%0D%0AIn+response+to+Questions+4+and+5%2C+we+point+to+the+algorithm+described+in+the+report%2C+or+variants+of+it.+Such+approaches+seem+capable+of+catching+many+higher+reductions.%0D%0A%0D%0A(6)+Is+there+a+way+to+find+solutions+with+the+smallest+++possible+number+of+single+patterns%3F%0D%0A%0D%0AThe+Study+Group+did+not+investigate+methods+tailored+specifically+to+this+task%2C+but+the+algorithm+proposed+here+seems+to+do+reasonably+well.+It+will+not+increase+the+number+of+singleton+patterns+under+any+circumstances%2C+and+when+the+number+of+singletons+is+high+there+will+be+many+possible+moves+that+tend+to+eliminate+them.%0D%0A%0D%0A(7)+Can+a+solution+be+found+which+reduces+the+number++of+knife+changes%3F%0D%0A%0D%0AThe+algorithm+will+help+to+reduce+the+number+of+necessary+knife+changes+because+it+works+by+bringing+patterns+closer+together%2C+even+if+this+does+not+proceed+fully+to+a+pattern+reduction.+If+two+patterns+are+equal+across+some+of+the+customer+widths%2C+the+knives+for+these+reels+need+not+be+changed+when+moving+from+one+to+the+other.&rft.type=Study+Group+Report&rft.type=NonPeerReviewed&rft.format=application%2Fpdf&rft.language=en&rft.identifier=http%3A%2F%2Fmiis.maths.ox.ac.uk%2Fmiis%2F329%2F1%2FPattern-reduction-in-paper-cutting.pdf&rft.identifier=++Aldridge%2C+C.+and+Chapman%2C+S.+J.+and+Gower%2C+R.+and+Leese%2C+R.+and+McDiarmid%2C+C.+and+Shepherd%2C+M.+and+Tuenter%2C+H.+and+Wilson%2C+H.+and+Zinober%2C+A.+++Pattern+Reduction+in+Paper+Cutting.++%5BStudy+Group+Report%5D+++++