Computers&OperationsResearch33(2006)15051520/locate/corGeneratingoptimaltwo-sectioncuttingpatternsforrectangularblanksYaodongCui,DongliHe,XiaoxiaSongDepartmentofComputerScience,GuangxiNormalUniversity,Guilin,Guangxi541004,ChinaAbstractThispaperpresentsanalgorithmforgeneratingunconstrainedguillotine-cuttingpatternsforrectangularblanks.Apatternincludesatmosttwosections,eachofwhichconsistsofstripsofthesamelengthanddirection.Thesizesandstripdirectionsofthesectionsmustbedeterminedoptimallytomaximizethevalueoftheblankscut.Thealgorithmusesanimplicitenumerationmethodtoconsiderallpossiblesectionsizes,fromwhichtheoptimalsizesareselected.ItmaysolveallthebenchmarkproblemslistedintheOR-Librarytooptimality.Thecomputationalresultsindicatethatthealgorithmisefcientbothincomputationtimeandinmaterialutilization.Finally,solutionstosomeproblemsaregiven.H170152004ElsevierLtd.Allrightsreserved.Keywords:Guillotine;Optimization;Cuttingstockproblem;Two-dimensionalcutting1. IntroductionTheunconstrainedtwo-dimensionalcuttingproblemistheproblemofcuttingfromasinglerectangularsheetanumberofsmallerrectangularblanks,eachofwhichisofagivensizeandagivenvalue,soastomaximizethevalueoftheblankscut.Thisproblemappearsinthecuttingofsteelsheetsintorequiredsizes,inthecuttingofwoodsheetstomakefurniture,andinseveralotherindustrialareas.Therelatedproblemofminimizingtheamountofwasteproducedbythecuttingcanbeconvertedintothisproblembymakingthevalueofallblanksequaltotheirareas.Correspondingauthor.Fax:+867735812383E-mailaddress:(Y.Cui).0305-0548/$-seefrontmatterH170152004ElsevierLtd.Allrightsreserved.doi:10.1016/j.cor.2004.09.0221506 Y.Cuietal./Computers&OperationsResearch33(2006)15051520Inpracticeitisoftensufcienttoconsideronlyguillotinecuts.Aguillotinecutonarectangleisacutfromoneedgeoftherectangletotheoppositeedgethatisparalleltothetworemainingedges.Werefertotheunconstrainedtwo-dimensionalguillotine-cuttingproblemastheUTDGCP.Young-Gun and Kang 1 pointed out that the UTDGCP should be distinguished from the two-dimensionalguillotine-cuttingstockproblem(TDGCSP).TheTDGCSPistheproblemofcuttingallrequirednumberofsmallrectangularblanksofdifferentsizesfromasetoflargerectangularsheetsatminimumsheetcost.AsolutionoftheTDGCSPconsistsofseveralcuttingpatterns,eachofwhichmaybeconstructedbyanalgorithmfortheUTDGCP.Thelinearprogramming(LP)approachiswidelyusedtosolvetheTDGCSP2.ItsolvestheTDGCSPthroughiteration.AlargenumberofUTDGCPmustbesolvedbeforetheLPapproachndsasolutionclosetooptimal.ThereareseveralexactalgorithmsfortheUTDGCP,suchasthedynamic-programmingproceduresin34,thetree-searchproceduresin57.BecausetheproblemisNPhard,thesealgorithmsarenotadequateforlarge-scaleproblems.TheyarealsonotadequateforconstructingcuttingpatternswhentheLPapproachisusedtosolvetheTDGCSP.Restrictionsonthecuttingpatternsareoftenusedtospeedupthesolutionprocess,suchasthestagedcuttingpatterns3,4.Hi8presentedtwoexactalgorithmsforlarge-scaleunconstrainedtwoandthreestagedcuttingproblems.FayardandZissimopoulos9proposedaheuristicthatselectsanoptimalsubsetof optimal generated strips by solving a sequence of one-dimensional knapsack problems.Althoughrestrictionsmaydecreasethevalueofthecuttingpatterns,theymaycutdownthecomputationtimedrastically.Thispaperputsforwardanewrestrictiononthecuttingpatterns.Itsuggeststheapplicationoftwo-sectionpatterns.Atwo-sectionpatterncontainsatmosttwosections.Allstripsinasectionareofthesamelengthanddirection.Astripiseitherauniformstripthatincludesonlyblanksofthesamesize,orageneralstripconsistingofblanksofdifferentsizes.Anexactalgorithm(referredtoastheTSECalgorithm)forgeneratingoptimaltwo-sectionpatternsisconstructed.Itconsidersallpossiblesectionsizesimplicitlyandndstheoptimalsizesthroughcomparisons.Tocomparethealgorithmwiththealgorithmsfornon-stagedandstagedcuttingpatterns,computationswereperformedonbothbenchmarkproblemsandrandomproblems.TheresultsindicatethattheTSECalgorithmisefcientbothincomputationtimeandinmaterialutilization,andmaysimplifythecuttingprocess.ItshouldbenotedthatthealgorithmpresentedmightbealsoseenasanimprovedversionofthatofFayardandZissimopoulos9.Theiralgorithmusesaseriesofone-dimensionalknapsackproblemsforgeneratingasetofoptimalstripsandthenllstheminthesheetinanoptimalway.Althoughnotdenitelypointedout,theiralgorithmgeneratesonlytwo-sectionpatterns.2. Two-sectionpatterns2.1. NotationandfunctionsTable1listssomenotationandfunctionstobeused.Mostofthemwillbere-introducedwheretheyareusedforthersttime.Thereadermaynditismoreconvenienttolookforthenotationdenitioninthetablethaninthetext.Y.Cuietal./Computers&OperationsResearch33(2006)15051520 1507Table1NotationandfunctionsL,W Lengthandwidthofthestocksheetli,wi,ciLength,widthandvalueoftheithrectangularblank,i =1,2,.,mFX(x) ValueofX-sectionx W inanX-patternFY(x) ValueofY-sectionx W inanX-patternfX(y) ValueofX-sectionL y inaY-patternfY(y) ValueofY-sectionL y inaY-pattern|L| NumberofXbreakpointsbetween0andL|W| NumberofYbreakpointsbetween0andWBXThesetofXbreakpoints, BX=bx,1,bx,2,.,bx,|L|BYThesetofYbreakpoints, BY=by,1,by,2,.,by,|W|u(i,x) ValueofanX-stripx wi,0lessorequalslantxlessorequalslantL,i =1,2,.,mv(i,y) ValueofaY-stripy li,0lessorequalslantylessorequalslantW,i =1,2,.,mint(x) ReturnthemaximumintegernotlargerthanxFig.1.Strips:(a)anX-strip,(b)aY-strip.2.2. StripsAssumethatthedirectionoftheblanksisxed.Thisrestrictionisnotserious,sinceifablankl wcanbecutwitheitherdirection,itmaybetreatedastwodifferentblanksl wandw l,eachofwhichhasaxeddirection.Bothgeneralanduniformstripswillbeconsideredingeneratingtwo-sectionpatterns.Auniformstripcontainsonlyblanksofthesamesizeanddirection.AsshowninFig.1,astripmaybeeitherinXorYdirection.AstripisanX-stripifitisinXdirection;otherwiseitisaY-strip.BlanksinX-stripsareleftjustied,andthoseinY-stripsarebottomjustied.ThestriplengthofanX-stripismeasuredhorizontally,andthestriplengthofaY-stripismeasuredvertically.Onlystripsofwidthequaltoablankwidth(horizontalstrips)orlength(verticalstrips)willbeconsid-ered.Assumethattherearemblanks.Theithblankisofsizeliwi,withliandwibeingpositiveintegers,i =1,2,.,m.ThentheithX-stripisofwidthwi,andtheithY-stripisofwidthli,i =1,2,.,m.1508 Y.Cuietal./Computers&OperationsResearch33(2006)15051520Fig.2.Sections:(a)anX-section,(b)aY-section.Fig.3.X-patterns.Fig.4.Y-patterns.2.3. SectionsStripsinasectionareofthesamedirectionandlength.Thedirectionofthestripsisreferredtoasthesectiondirection.AsectionisanX-sectionifthestripsareinXdirection,otherwiseitisaY-section.Fig.2ashowsanX-sectionandFig.2bshowsaY-section.2.4. Two-sectionpatternsFigs.3and4showallpossiblepatternsthatshouldbeconsidered.Thearrowineachsectionindicatesthedirectionofthesection.Thetwosectionsmaybejustiedeithervertically(Y-pattern)orhorizontally(X-pattern).ThepatternsofFigs.3aand4aareone-sectionpatterns,whicharethespecialcasesoftwo-sectionpatterns.ThepatternofFig.3amaybeseenasatwo-sectionpatterncontainingtwoY-sections,andthepatternofFig.4amaybetakenasatwo-sectionpatternconsistingoftwoX-sections.AssumethatthesheetsizeisLW.ThewidthofanX-sectioninanX-patternisW(Fig.3b),andthelengthofaY-sectioninaY-patternisL(Fig.4b).Y.Cuietal./Computers&OperationsResearch33(2006)15051520 15092.5. Break-pointsManyauthors49haveusednormalsetstodevelopalgorithmsforguillotine-cuttingpatterns.Theelementsofthenormalsetsarereferredtoasbreakpointsinthispaper.Theyaredenedas:X breakpoints: x =msummationdisplayi=1zililessorequalslantL, zigreaterorequalslant0 andinteger,Y breakpoints: y =msummationdisplayi=1ziwilessorequalslantW, zigreaterorequalslant0 andinteger. (1)DenotethesetofallXbreakpointsby BX, BX=bx,1,bx,2,.,bx,|L|,where |L| isthenumberofXbreakpointsbetween0andL,bx,i|L|.Step3. Letx = bx,i,V = FX(x) +maxFX(L x),FY(L x).Gotostep2ifV|W|.Step3. Letx = by,i,V = fY(y) +maxfY(W y),fX(W y).Gotostep2ifV10800U4 48350130 48350130 48350130 0.04 1.66 32.56W1 167751 168289 162279 167751 0.02 0.18 8.91 8280.80W2 37617 37621 37621 37621 0.01 0.03 4.59 1427.35W3 253617 253617 250830 253617 0.06 0.36 23.08 10800W4 378366 378366 377910 0.14 0.71 57.29TheH_3STGcouldnotverifytheoptimalityofproblemsU3andW3becausethatthecomputationtimeforeachproblemwasnotallowedtoexceed3h.ItalsocouldnotsolveproblemsU4andW4forthelargescaleoftheproblemsizes.Theseeightproblemsarealllarge-scaleproblems.Thesheetsizeofthemis45005000,50504070,73506579,73506579,50005000,34272769,75007381,and75007381,respectively.Thenumbersofblanksizesare10,10,20,40,20,20,40,and80respectively.AsmentionedinSection3.6,theTSECalgorithmsactuallygeneratetwoandthree-stagepatterns.v4shouldnotbesmallerthanv2foranyproblem,forthatitisthevalueoftheoptimalthree-stagedpattern.FromTable6weknowthatv4v2forproblemsU1,U2andW1.Therefore,wecanconcludethattheauthormadesomeerrorsinpresentingthecomputationalresultsin8.Tosupportthisconclusion,thetwo-sectionpatternsofthesethreeproblemsaregiveninFigs.68,andtheblankdataincludedareasfollows(forproblemsU1andU2:blankidnumberoftheblanklengthwidth;forproblemW1:blankidnumberoftheblanklengthwidthvalue):U1: 194371490,320237932,1020659921,U2: 3129321107,42598732,575691321,721248747,W1: 1754377312223,915985621564.4.4. ComparisonbetweentheTSECandtheFZalgorithmsBoth the TSEC and the FZ 9 algorithms will generate optimal two-section patterns. The TSECmaybeseenasanimprovedversionoftheFZ.ThethreetechniquesmentionedinSection3.4arenotused by the FZ.We used test problems of Group 8 to test the TSEC and FZ algorithms. The sheetsize is 8000 6000. The blank data are the same as Group 6. The average material utilization is99.98%, which is the same for the two algorithms, because both of them can generate optimal two-section patterns.The average computation time for one problem is 16.23s for the FZ, 1.98s for theTSEC_G. The average number of knapsack problems solved for one problem is 22,787 for the FZ,9542 for the TSEC_G. The average number of strips considered in solving a knapsack problem re-latedtoasectionis30fortheFZ,1.75fortheTSEC_G.WhentheTSEC_Uisapplied,theaveragecomputation time is 0.15s. The average material utilization is 99.97%, which is nearly the same asthat of the TSEC_Gor FZ. Both the TSEC_Gand the TSEC_U are much more time efcient thantheFZ.Y.Cuietal./Computers&OperationsResearch33(2006)15051520 1517Fig.6.ThepatternofproblemU1.Fig.7.ThepatternofproblemU2.BelowwegivethesolutionstotheproblemsinGroup9,whichmaybeusedbyfutureresearchersorpractitionerstotesttheiralgorithms.Thisgroupincludes12problems.Thesheetsizeis80006000.TherstsixproblemsarethoselistedinTable4.ProblemsP7P12areformedbycombiningtheblank1518 Y.Cuietal./Computers&OperationsResearch33(2006)15051520Fig.8.ThepatternofproblemW1.Table7ThecomputationalresultsofGroup9ID m v1v2v3t1t2t3P1 30 47993491 47993491 47992398 21.17 2.01 0.16P2 30 47991116 47991116 47991116 17.49 2.07 0.15P3 30 47987624 47987624 47983659 14.56 1.80 0.16P4 30 47993588 47993588 47993588 18.15 2.00 0.15P5 30 48000000 48000000 48000000 13.87 2.16 0.16P6 30 47997600 47997600 47997600 19.37 2.13 0.16P7 60 48000000 48000000 48000000 38.41 5.91 0.36P8 60 47998064 47998064 47998064 36.94 6.08 0.37P9 60 48000000 48000000 48000000 39.72 6.06 0.35P10 90 48000000 48000000 48000000 50.79 10.52 0.56P11 90 48000000 48000000 48000000 56.15 10.50 0.54P12 180 48000000 48000000 48000000 71.34 19.02 1.10dataoftwoormoreproblemsfromtherstsix.Namely,ProblemID P7 P8 P9 P10 P11 P12Blankdata P1+P2 P3+P4 P5+P6 P1+P2+P3 P4+P5+P6 P1+P2+P3+P4+P5+P6ThecomputationalresultsaresummarizedinTable7,wherev1andt1arethevalueandcomputationtimeoftheFZ,v2andt2arethoseoftheTSEC_G,v3andt3arethoseoftheTSEC_U.Y.Cuietal./Computers&OperationsResearch33(2006)15051520 15195. ConclusionsTheTSECmaygenerateoptimaltwo-sectionpatterns,whichareeithertwo-stageorthree-stagepat-terns. For the small-scale problems tested, the TSEC can solve most of them to optimality, and thesolutionsarenotinferiortothoseoftheoptimalthree-stagepatterns.Formedium-scaleproblems,theTSECcangivesolutionsveryclosetooptimal.FortheproblemsofGroup6,theaveragematerialutilizationisveryclosetooptimal(99.64%vs.99.74%),superiortothatoftheoptimaltwo-stagepatterns(99.64%vs.99.44%),andveryclosetothatoftheoptimalthree-stagepatterns(99.64%vs.99.66%).TheaveragecomputationtimeismuchmoreshorterthanthoseoftheB_OPTandB_3STG.Fortheeightlarge-scaleproblemstested(Group7),theTSECgivessolutionsnotinferiortothoseoftheH_3STG.AlthoughtheTSECwasexecutedonacomputerwithaclockrate19timesofthatusedbyHiff8(1.9GHzvs.0.1GHz),wemaystillinferthatitismoretimeefcientthantheH_3STGfromthehugedifferenceincomputationtimeshowninTable6.ApplyingthethreetechniquesdiscussedinSection3.4makestheTSECmuchmoretimeefcientthan the FZ. These techniques can also be used to improve the H_3STG. We have actually devel-oped an algorithm based on these techniques, which is able to generate optimal three-stage patternsefciently.AcknowledgementsGuangxiScienceFoundationsupportsthisprogramunderthegrantNo.0236017.Theauthorswishtoexpresstheirappreciationtothesupporter.Theauthorsarealsogratefultotheanonymousrefereewhosecommentshelpedtoimproveanearlyversionofthispaper.References1 Young-GunG,KangM-K.Anewupperboundforunconstrainedtwo-dimensionalcuttingandpacking.JournaloftheOperationalResear