外文翻译原文.pdf

CORRESPONDINGAUTHORTEL3031498143FAX3031498180EMAILADDRESSGEORGIADCPERICERTHGRMCGEORGIADISCOMPUTERSRECEIVEDINREVISEDFORM1SEPTEMBER2000ACCEPTED1OCTOBER2000ABSTRACTTHISPAPERPRESENTSANEWMATHEMATICALPROGRAMMINGFORMULATIONFORTHEPROBLEMOFDETERMININGTHEOPTIMALMANNERINWHICHSEVERALPRODUCTROLLSOFGIVENSIZESARETOBECUTOUTOFRAWROLLSOFONEORMORESTANDARDTYPESTHEOBJECTIVEISTOPERFORMTHISTASKSOASTOMAXIMIZETHEPRO“TTAKINGACCOUNTOFTHEREVENUEFROMTHESALES,THECOSTSOFTHEORIGINALROLLS,THECOSTSOFCHANGINGTHECUTTINGPATTERNANDTHECOSTSOFDISPOSALOFTHETRIMAMIXEDINTEGERLINEARPROGRAMMINGMILPMODELISPROPOSEDWHICHISSOLVEDTOGLOBALOPTIMALITYUSINGSTANDARDTECHNIQUESANUMBEROFEXAMPLEPROBLEMS,INCLUDINGANINDUSTRIALCASESTUDY,AREPRESENTEDTOILLUSTRATETHEECIENCYANDAPPLICABILITYOFTHEPROPOSEDMODELSCOPEANDPURPOSEONEDIMENSIONALCUTTINGSTOCKTRIMLOSSPROBLEMSARISEWHENPRODUCTIONITEMSMUSTBEPHYSICALLYDIVIDEDINTOPIECESWITHADIVERSITYOFSIZESINONEDIMENSIONEGWHENSLITTINGMASTERROLLSOFPAPERINTONARROWERWIDTHROLLSSUCHPROBLEMSOCCURWHENTHEREARENOECONOMIESOFSCALEASSOCIATEDWITHTHEPRODUCTIONOFTHELARGERRAWMASTERROLLSINGENERAL,THEOBJECTIVESINSOLVINGSUCHPROBLEMSARETO5P69MINIMIZETRIMLOSSP69AVOIDPRODUCTIONOVERRUNSAND/ORP69AVOIDUNNECESSARYSLITTERSETUPSTHEABOVEPROBLEMISPARTICULARLYIMPORTANTINTHEPAPERCONVERTINGINDUSTRYWHENASETOFPAPERROLLSNEEDTOBECUTFROMRAWPAPERROLLSSINCETHEWIDTHOFAPRODUCTISFULLYINDEPENDENTOFTHEWIDTHOFTHERAWPAPERAHIGHLYCOMBINATORIALPROBLEMARISESINGENERAL,THECUTTINGPROCESSALWAYSPRODUCESINEVITABLETRIMLOSSWHICHHASTOBEBURNEDORPROCESSEDINSOMEWASTETREATMENTPLANTTRIMLOSSPROBLEMSINTHEPAPERINDUSTRYHAVE,INRECENTYEARS,MAINLYBEENSOLVEDUSINGHEURISTICRULESTHEPRACTICALPROBLEMFORMULATIONHAS,THEREFORE,INMOSTCASESBEENRESTRICTEDBYTHEFACTTHATTHESOLUTIONMETHODSOUGHTTOBEABLETOHANDLETHEENTIREPROBLEMCONSEQUENTLY,ONLYASUBOPTIMALSOLUTIONTOTHEORIGINALPROBLEMHASBEENOBTAINEDAND03050548/02/SEEFRONTMATTERP72002ELSEVIERSCIENCELTDALLRIGHTSRESERVEDPIIS0305054800001027VERYOFTENTHISRATHERSIGNI“CANTECONOMICPROBLEMHASBEENLEFTTOAMANUALSTAGETHISWORKPRESENTSANOVELALGORITHMFORECIENTLYDETERMININGOPTIMALCUTTINGPATTERNSINTHEPAPERCONVERTINGPROCESSAMIXEDINTEGERLINEARPROGRAMMINGMODELISPROPOSEDWHICHISSOLVEDTOGLOBALOPTIMALITYUSINGAVAILABLECOMPUTERTOOLSANUMBEROFEXAMPLEPROBLEMSINCLUDINGANINDUSTRIALCASESTUDYAREPRESENTEDTOILLUSTRATETHEAPPLICABILITYOFTHEPROPOSEDALGORITHMP72002ELSEVIERSCIENCELTDALLRIGHTSRESERVEDKEYWORDSINTEGERPROGRAMMINGOPTIMIZATIONTRIMLOSSPROBLEMSPAPERCONVERTINGINDUSTRY1INTRODUCTIONANIMPORTANTPROBLEMWHICHISFREQUENTLYENCOUNTEREDININDUSTRIESSUCHASPAPERISRELATEDWITHTHEMOSTECONOMICMANNERINWHICHSEVERALPRODUCTROLLOFGIVENSIZESARETOBEPRODUCEDBYCUTTINGONEORMOREWIDERRAWROLLSAVAILABLEINONEORMORESTANDARDWIDTHSTHESOLUTIONOFTHISPROBLEMINVOLVESSEVERALINTERACTINGDECISIONSP69THENUMBEROFPRODUCTROLLSOFEACHSIZETOBEPRODUCEDTHISMAYBEALLOWEDTOVARYBETWEENGIVENLOWERANDUPPERBOUNDSTHEFORMERNORMALLYREECTTHE“RMORDERSTHATARECURRENTLYOUTSTANDING,WHILETHELATTERCORRESPONDTOTHEMAXIMUMCAPACITYOFTHEMARKETHOWEVER,CERTAINDISCOUNTSMAYHAVETOBEOEREDTOSELLSHEETSOVERANDABOVETHEQUANTITIESFORWHICH“RMORDERSAREAVAILABLEP69THENUMBEROFRAWROLLSOFEACHSTANDARDWIDTHTOBECUTROLLSMAYBEAVAILABLEINONEORMORESTANDARDWIDTHS,EACHOFADIERENTUNITPRICEP69THECUTTINGPATTERNFOREACHRAWROLLCUTTINGTAKESPLACEONAMACHINEEMPLOYINGANUMBEROFKNIVESOPERATINGINPARALLELONAROLLOFSTANDARDWIDTHWHILETHEPOSITIONOFTHEKNIVESMAYBECHANGEDFROMONEROLLTOTHENEXT,SUCHCHANGESMAYINCURCERTAINCOSTSFURTHERMORE,THEREMAYBECERTAINTECHNOLOGICALLIMITATIONSONTHEKNIFEPOSITIONSTHATMAYBEREALIZEDBYANYGIVENCUTTINGMACHINETHEOPTIMALSOLUTIONOFTHEABOVEPROBLEMISOFTENASSOCIATEDWITHTHEMINIMIZATIONOFTHETRIMAWASTETHATISGENERALLYUNAVOIDABLESINCEROLLSOFSTANDARDWIDTHSAREUSEDHOWEVER,TRIMLOSSMINIMIZATIONDOESNOTNECESSARILYIMPLYMINIMIZATIONOFTHECOSTOFTHERAWMATERIALSROLLSBEINGUSEDESPECIALLYIFSEVERALSTANDARDROLLSIZESAREAVAILABLEAMOREDIRECTECONOMICCRITERIONISTHEMAXIMIZATIONOFTHEPRO“TOFTHEOPERATIONTAKINGACCOUNTOFP69THEREVENUEFROMPRODUCTROLLSSALES,INCLUDINGTHEEECTSOFANYBULKDISCOUNTSP69THECOSTOFTHEROLLSTHATAREACTUALLYUSEDP69THECOSTS,IFANY,OFCHANGINGTHEKNIFEPOSITIONSONTHECUTTINGMACHINEP69THECOSTOFDISPOSINGOFTRIMWASTETHEABOVECONSTITUTESAHIGHLYCOMBINATORIALPROBLEMANDITISNOTSURPRISINGTHATTRADITIONALLYITSSOLUTIONHASOFTENBEENCARRIEDOUTMANUALLYBASEDONHUMANEXPERTISETHESIMPLI“EDVERSIONOFTHISPROBLEMISSIMILARTOTHECUTTINGSTOCKPROBLEMKNOWNINTHEOPERATIONRESEARCHLITERATURE,WHEREANUMBEROFORDEREDPIECESNEEDTOBECUTOBIGGERSTOREDPIECESINTHEMOSTECONOMICFASHIONINTHE1960SANDTHE1970S,SEVERALSCIENTI“CARTICLESWEREPUBLISHEDONTHEPROBLEMOF1042GSCHILLING,MCGEORGIADIS/COMPUTERSTHATRAWROLLSOFTHETYPETTHATPERMITSTHESMALLESTMINIMUM1044GSCHILLING,MCGEORGIADIS/COMPUTERSANDTHATEACHRAWROLLWILLBEUSEDTOPRODUCEPRODUCTROLLSOFASINGLETYPEONLYOVERALL,THISLEADSTOTHEFOLLOWINGUPPERBOUNDONTHENUMBEROFRAWROLLSTHATMAYBEREQUIREDJP13P0P24“P39P9P71P14P16NP13P0P24P71P87MINP82BP13P9P14P82/BP71P881WECANALSOCALCULATEALOWERBOUNDJP13P9P14ONTHEMINIMUMNUMBEROFRAWROLLSTHATARENECESSARYTOSATISFYTHEMINIMUMDEMANDFORTHEEXISTINGORDERSWEDOTHISBYASSUMINGTHATROLLSOFTHETYPETALLOWINGTHEMAXIMUMPOSSIBLEENGAGEMENTBP13P0P24P82AREUSED,ANDTHATNOTRIMISPRODUCEDHOWEVER,WEMUSTALSOTAKEACCOUNTOFPOSSIBLELIMITATIONSONTHENUMBEROFAVAILABLEKNIVESOVERALL,THISLEADSTOTHEFOLLOWINGLOWERBOUNDONTHENUMBEROFROLLSTHATMAYBEREQUIREDJP13P9P14“MAXP7P9P39P71P14P16NP13P9P14P71BP71MAXP82BP13P0P24P82,P9P39P71P14P16NP13P9P14P71MAXP82NP13P0P24P82P823MATHEMATICALFORMULATIONTHEAIMOFTHEMATHEMATICALFORMULATIONISTODETERMINETHETYPETOFEACHRAWROLLJTOBECUTANDTHENUMBEROFPRODUCTROLLSOFEACHTYPEITOBEPRODUCEDFROMIT31KEYVARIABLESTHEFOLLOWINGINTEGERVARIABLESAREINTRODUCEDNP71P72NUMBEROFPRODUCTROLLSOFTYPEITOBECUTOUTOFRAWROLLJAFII9773P71NUMBEROFPRODUCTROLLSOFTYPEIPRODUCEDOVERANDABOVETHEMINIMUMNUMBERORDEREDWENOTETHATNP71P72CANNOTEXCEEDP69THEMAXIMUMNUMBERNP13P0P24P71OFPRODUCTROLLSOFTYPEITHATCANBESOLDP69THEMAXIMUMNUMBEROFPRODUCTROLLSOFWIDTHBP71THATCANBEACCOMMODATEDWITHINAMAXIMUMENGAGEMENTBP13P0P24P82FORARAWROLLOFTYPETP69THEMAXIMUMNUMBERNP13P0P24P82OFKNIVESTHATCANBEAPPLIEDTOARAWROLLOFTYPETTHISLEADSTOTHEFOLLOWINGBOUNDSFORNP71P720NP71P72MINP1NP13P0P24P71,MAXP16P87P82P87P50BP13P0P24P82BP71,MAXP16P87P82P87P50NP13P0P24P82P2I“1,2,I,J“1,2,JP13P0P243ALSO0AFII9773P71NP13P0P24P71NP13P9P14P71,I“1,2,I4GSCHILLING,MCGEORGIADIS/COMPUTERSTHISSIMPLYIMPLIESTHATITISNOTNECESSARYTOCUTROLLJFURTHERMORE,THELIMITEDAVAILABILITYOFRAWROLLSOFAGIVENTYPETMAYBEEXPRESSEDINTERMSOFTHECONSTRAINTP40P13P0P24P9P72P14P16YP82P72JHP82,T“1,2,633CUTTINGCONSTRAINTSWENEEDTOENSURETHAT,IFAROLLJISTOBECUT,THENTHELIMITATIONSONTHEMINIMUMANDMAXIMUMENGAGEMENTAREOBSERVEDTHISISACHIEVEDVIATHECONSTRAINTSP50P9P82P14P16BP13P9P14P82YP82P72P39P9P71P14P16BP71NP71P72P50P9P82P14P16BP13P0P24P82YP82P72,J“1,2,JP13P0P247WENOTETHATTHEQUANTITYP9P39P71P14P16BP71NP71P72REPRESENTSTHETOTALWIDTHOFALLPRODUCTROLLSTOBECUTOUTOFRAWROLLJIFYP82P72“1FORSOMEROLLTYPET,THENCONSTRAINT7ENSURESTHATBP13P9P14P82P39P9P71P14P16BP71NP71P72BP13P0P24P821046GSCHILLING,MCGEORGIADIS/COMPUTERSONCEAGAIN,ATMOSTONEOFTHETERMSINTHISSUMMATIONCANBENONZEROCFCONSTRAINTS5AAND5BTHELATTERQUANTITYISGIVENBYP9P39P71P14P16BP71NP71P72OVERALL,TRIMDISPOSALRESULTSINTHEFOLLOWINGCOSTTERMCP3P9P19P16P40P13P0P24P9P72P14P16P1P50P9P82P14P16BP18P15P12P12P82YP82P72P39P9P71P14P16BP71NP71P72P2THEABOVETERMSCANNOWBECOLLECTEDINTHEFOLLOWINGOBJECTIVEFUNCTIONMAXP3P39P9P71P14P16PP71NP13P9P14P71AFII9773P71PP71CP3P9P19P2P71P40P13P0P24P9P72P14P16P9P82P14P16CP18P15P12P12P82YP82P72CP2P8P0P14P6P4P40P13P0P24P9P72P14P17ZP72CP3P9P19P16P40P13P0P24P9P72P14P16P1P50P9P82P14P16BP18P15P12P12P82YP82P72P39P9P71P14P16BP71NP71P72P2P411NOTETHATTHE“RSTTERMINTHEABOVEOBJECTIVEFUNCTIONIEP9P39P71P14P16PP71NP13P9P14P71ISACTUALLYACONSTANTANDDOESNOTAECTTHEOPTIMALSOLUTIONOBTAINED37DEGENERACYREDUCTIONANDCONSTRAINTTIGHTENINGINGENERAL,THEBASICFORMULATIONPRESENTEDABOVEISHIGHLYDEGENERATEGIVENANYFEASIBLEPOINT,ONECANGENERATEMANYOTHERSSIMPLYBYFORMINGALLPOSSIBLEORDERINGOFTHEROLLSSELECTEDTOBECUTMOREOVER,PROVIDEDALLRAWROLLSOFTHESAMETYPEARECUTCONSECUTIVELY,ALLTHESEFEASIBLEPOINTSWILLCORRESPONDTOEXACTLYTHESAMEVALUEOFTHEOBJECTIVEFUNCTIONTHEABOVEPROPERTYMAYHAVEADVERSEEECTSONTHEECIENCYOFTHESEARCHPROCEDURETHEREFORE,INORDERTOREDUCETHESOLUTIONDEGENERACYWITHOUTANYLOSSOFOPTIMALITY,WEINTRODUCETHEFOLLOWINGORDERINGCONSTRAINTSP39P9P71P14P16NP71P11P72P92P16P39P9P71P14P16NP71P72,J“2,2,JP13P0P2412THISENSURESTHATTHETOTALNUMBEROFPRODUCTROLLSCUTOUTOFRAWROLLJ1ISNEVERLOWERTHANTHECORRESPONDINGNUMBERFORROLLJALLCOMPLETELYUNUSEDRAWROLLSARELEFTLASTINTHISORDERING1048GSCHILLING,MCGEORGIADIS/COMPUTERSBP13P0P24P82BP13P9P14P82,WHICHRESULTSINONELESSCONSTRAINTFOREACHROLLJ4EXAMPLEPROBLEMSINTHISSECTION,WECONSIDERFOUREXAMPLEPROBLEMSOFINCREASINGCOMPLEXITYINORDERTOINVESTIGATETHECOMPUTATIONALBEHAVIOROFOURFORMULATIONFURTHERMOREANINDUSTRIALCASESTUDYISALSOPRESENTEDINALLCASES,WEASSUMETHATTHEMAXIMUMRAWROLLENGAGEMENTBP13P0P24P82ISEQUALTOTHECORRESPONDINGROLLWIDTHBP18P15P12P12P82THEGAMS/CPLEXVS60SOLVERHASBEENUSEDFORTHESOLUTION15ANDALLCOMPUTATIONSWERECARRIEDOUTONAALPHASERVER4100ANINTEGRALITYGAPOF01WASASSUMEDFORTHESOLUTIONOFALLPROBLEMS41EXAMPLE1OUR“RSTEXAMPLEISBASEDONTHATGIVENBYHARJUNKOSKI9SOMETRANSLATIONOFTHEVARIOUSCOSTCOECIENTSWASNECESSARYTOACCOUNTFORSLIGHTDIERENCESINTHEOBJECTIVEFUNCTIONSUSEDBYTHETWOFORMULATIONSALSONOTETHATTHEOBJECTIVEUSEDBYTHOSEAUTHORSISTHEMINIMIZATIONOFCOSTASOPPOSEDTOTHEMAXIMIZATIONOFPRO“TTHEREFORE,THESIGNOFTHEIROBJECTIVEFUNCTIONISOPPOSITETOTHATOFOURSGSCHILLING,MCGEORGIADIS/COMPUTERSTHUS,WITHTHEGIVENECONOMICDATATHEOPERATIONINCURSALOSSTHEOPTIMALSOLUTIONWITHINAMARGINOFOPTIMALITYOF01ISFOUNDWITHINLESSTHAN1CPUSATNODE49OFTHEBRANCHANDBOUNDALGORITHMUSINGABREADTH“RSTSEARCHSTRATEGYITMUSTBENOTEDTHATTHEINTEGRALITYGAPOFOURFORMULATIONISCOMPARABLETOTHATFORONEOFTHEFORMULATIONSPRESENTEDBYHARJUNKOSKI9DESPITETHEFACTTHATITDOESNOTEMPLOYANYAPRIORIENUMERATIONOFTHECUTTINGPATTERNSOURFORMULATIONALSOEXAMINESASMALLNUMBEROFNODESINORDERTODETECTTHEOPTIMALPOINTTABLE31050GSCHILLING,MCGEORGIADIS/COMPUTERS9849592GILMOREPC,GOMORYREALINEARPROGRAMMINGAPPROACHTOTHECUTTINGSTOCKPROBLEMPARTIIOPERATIONSRESEARCH196311863883HINXMANAITHETRIMLOSSANDASSORTMENTPROBLEMSASURVEYEUROPEANJOURNALOFOPERATIONALRESEARCH19805818GSCHILLING,MCGEORGIADIS/COMPUTERS44175845SWEENEYPE,HAESSLERRWONEDIMENSIONALCUTTINGSTOCKDECISIONSFORROLLSWITHMULTIPLEQUALITYGRADESEUROPEANJOURNALOFOPERATIONALRESEARCH199044224316FERREIRAJS,NEVESMA,FONSECAECASTROPATWOPHASEROLLCUTTINGPROBLEMEUROPEANJOURNALOFOPERATIONALRESEARCH199044185967GRADISARM,JESENKOJ,RESINOVICGOPTIMIZATIONOFROLLCUTTINGINCLOTHINGINDUSTRYCOMPUTERS10S945538GRADISARM,KLJAJICM,RESINOVICG,JESENKOJASEQUENTIALHEURISTICPROCEDUREFORONEDIMENSIONALCUTTINGEUROPEANJOURNALOFOPERATIONALRESEARCH1999114557689HARJUNKOSKII,WESTERLUNDT,ISAKSSONJ,SKRIFVARSHDIERENTFORMULATIONSFORSOLVINGTRIMLOSSPROBLEMSINAPAPERCONVERTINGMILLWITHILPCOMPUTERSANDCHEMICALENGINEERING199620S121610HARJUNKOSKII,WESTERLUNDT,PORNRDIERENTTRANSFORMATIONSFORSOLVINGNONCONVEXTRIMLOSSPROBLEMSBYMINLPEUROPEANJOURNALOFOPERATIONALRESEARCH199810559460311WESTERLUNDT,ISAKSSONJ,HARJUNKOSKIISOLVINGATWODIMENSIONALTRIMLOSSPROBLEMWITHMILPEUROPEANJOURNALOFOPERATIONALRESEARCH19981045728112WESTERLUNDT,HARJUNKOSKII,ISAKSSONJSOLVINGAPRODUCTIONOPTIMISATIONPROBLEMINAPAPERCONVERTINGMILLWITHMILPCOMPUTERSANDCHEMICALENGINEERING1998225637013WESTERLUNDT,IS