资源目录
压缩包内文档预览：
编号：6099609
类型：共享资源
大小：1.15MB
格式：RAR
上传时间：2017-11-16
上传人：机****料
认证信息
个人认证
高**（实名认证）
河南
IP属地：河南
50
积分
- 关 键 词：
-
工业
机器人
设计
全套
cad
图纸
- 资源描述：
-
- 内容简介：
-
*Correspondingauthor.Tel.:#30-31-498-143;fax:#30-31-498-180.E-mail address: georgiadcperi.certh.gr(M.C.Georgiadis).Computers&OperationsResearch29(2002)10411058AnalgorithmforthedeterminationofoptimalcuttingpatternsGordianSchillingp0,MichaelC.Georgiadisp1p11*p0Ciba Specialty Chemicals Inc., CH-1870 Monthey, Switzerlandp1Centre for Research and Technology - Hellas, Chemical Process Engineering Research Institute, P.O. Box 361,Thermi 57001, Thessaloniki, GreeceReceived1June2000;receivedinrevisedform1September2000;accepted1October2000AbstractThispaperpresentsanewmathematicalprogrammingformulationfortheproblemofdeterminingtheoptimalmannerinwhichseveralproductrollsofgivensizesaretobecutoutofrawrollsofoneormorestandardtypes.Theobjectiveistoperformthistasksoastomaximizetheprottakingaccountoftherevenuefromthesales,thecostsoftheoriginalrolls,thecostsofchangingthecuttingpatternandthecostsofdisposalofthetrim.Amixedintegerlinearprogramming(MILP)modelisproposedwhichissolvedtoglobaloptimalityusingstandardtechniques.Anumberofexampleproblems,includinganindustrialcasestudy,arepresentedtoillustratethee$ciencyandapplicabilityoftheproposedmodel.Scope and purposeOne-dimensional cutting stock (trim loss) problems arise when production items must be physicallydividedintopieceswithadiversityofsizesinonedimension(e.g.whenslittingmasterrollsofpaperintonarrower width rolls). Such problems occur when there are no economies of scale associated with theproductionofthelargerraw(master)rolls.Ingeneral,theobjectivesinsolvingsuchproblemsareto5:p69 minimizetrimloss;p69 avoidproductionover-runsand/or;p69 avoidunnecessaryslittersetups.Theaboveproblemisparticularlyimportantinthepaperconvertingindustrywhenasetofpaperrollsneedtobecutfromrawpaperrolls.Sincethewidthofaproductisfullyindependentofthewidthoftherawpaperahighlycombinatorialproblemarises.Ingeneral,thecuttingprocessalwaysproducesinevitabletrim-losswhichhastobeburnedorprocessedinsomewastetreatmentplant.Trim-lossproblemsinthepaperindustryhave, in recent years, mainly been solved using heuristic rules. The practical problem formulationhas,therefore,inmostcasesbeenrestrictedbythefactthatthesolutionmethodsoughttobeabletohandletheentireproblem.Consequently,onlyasuboptimalsolutiontotheoriginalproblemhasbeenobtainedand0305-0548/02/$-seefrontmatter p7 2002ElsevierScienceLtd.Allrightsreserved.PII: S0305-0548(00)00102-7veryoftenthisrathersignicanteconomicproblemhasbeenlefttoamanualstage.Thisworkpresentsa novel algorithm for e$ciently determining optimal cutting patterns in the paper converting process.Amixed-integerlinearprogrammingmodelisproposedwhichissolvedtoglobaloptimalityusingavailablecomputertools.Anumberofexampleproblemsincludinganindustrialcasestudyarepresentedtoillustratetheapplicabilityoftheproposedalgorithm. p7 2002ElsevierScienceLtd.Allrightsreserved.Keywords: Integerprogramming;Optimization;Trim-lossproblems;Paperconvertingindustry1. IntroductionAnimportantproblemwhichisfrequentlyencounteredinindustriessuchaspaperisrelatedwiththemosteconomicmannerinwhichseveralproductrollofgivensizesaretobeproducedbycuttingoneormorewiderrawrollsavailableinoneormorestandardwidths.Thesolutionofthisprobleminvolvesseveralinteractingdecisions:p69 Thenumberofproductrollsofeachsizetobeproduced.Thismaybeallowedtovarybetweengivenlowerandupperbounds.Theformernormallyre#ectthe rmordersthatarecurrentlyoutstanding,whilethelattercorrespondtothemaximumcapacityofthemarket.However,certaindiscountsmayhavetobeo!eredtosellsheetsoverandabovethequantitiesforwhichrmordersareavailable.p69 Thenumberofrawrollsofeachstandardwidthtobecut.Rollsmaybeavailableinoneormorestandardwidths,eachofadi!erentunitprice.p69 Thecuttingpatternforeachrawroll.Cuttingtakesplaceonamachineemployinganumberofknivesoperatinginparallelonarollofstandardwidth.Whilethepositionoftheknivesmaybechangedfromonerolltothenext,suchchangesmayincurcertaincosts.Furthermore,theremaybecertaintechnologicallimitationsontheknifepositionsthatmayberealizedbyanygivencuttingmachine.Theoptimalsolutionoftheaboveproblemisoftenassociatedwiththeminimizationofthetrima waste that is generally unavoidable since rolls of standard widths are used. However,trim-lossminimizationdoesnotnecessarilyimplyminimizationofthecostoftherawmaterials(rolls)beingusedespeciallyifseveralstandardrollsizesareavailable.Amoredirecteconomiccriterionisthemaximizationoftheprotoftheoperationtakingaccountof:p69 therevenuefromproductrollssales,includingthee!ectsofanybulkdiscounts;p69 thecostoftherollsthatareactuallyused;p69 thecosts,ifany,ofchangingtheknifepositionsonthecuttingmachine;p69 thecostofdisposingoftrimwaste.Theaboveconstitutesahighlycombinatorialproblemanditisnotsurprisingthattraditionallyitssolutionhasoftenbeencarriedoutmanuallybasedonhumanexpertise.Thesimpliedversionofthisproblemissimilartothecuttingstockproblemknownintheoperation-researchliterature,whereanumberoforderedpiecesneedtobecuto!biggerstoredpiecesinthemosteconomicfashion.Inthe1960sandthe1970s,severalscienticarticleswerepublishedontheproblemof1042 G. Schilling, M.C. Georgiadis/Computers & Operations Research 29 (2002) 10411058minimizingtrimloss,e.g.1,2.Hinxman3presentsagoodoverviewoftheavailablesolutionmethodsfortrim-lossandassortmentproblems.GilmoreandGomory1presentedabasiclinearprogrammingapproachtothecuttingstockproblemwhilerelaxingsomeinteger-charactersof theproblem.GilmoreandGomory2de-scribed an iterative solution method that is suitable for very large number of orders and iscomputationalcheap,buttheresultingvaluesforthenumberofcuttingpatternstobeusedarenon-integeranditisnotpossibletoprovetheoptimalityorindicatethemarginofoptimalityofthese cutting patterns. Thus, the rounding values obtained by the algorithm of Gilmore andGomory2mayveryprobablyresultinpooreconomicperformance.Wascher4presentedalinearprogrammingapproachtocuttingstockproblemstakingintoaccountmultipleobjectivessuchascostoftherawmaterials,costoftheoverproductionstorage,trim-lossremovalcosts,etc.Sweeny5proposedaheuristicprocedureforsolvingone-dimensionalcuttingstockproblemswithmultiplequalitygrades.Ferreiraetal.6consideredthetwo-phaserollcuttingproblemsbased on a heuristic approach. Gradisar et al. 7 presented an e$cient sequential heuristicprocedureand a softwaretool for optimizationof roll cutting in theclothing industry.Later,Gradisaretal.8developedanimprovedsolutionstrategybasedonacombinationofapproxima-tionsandheuristicsleadingtoalmostoptimalsolutionsfortheone-dimensionalstockcuttingproblems.Asoftwaretoolwasalsodeveloped.Inrecentyears,integerprogrammingtechniqueshavebeenusedforthesolutionofthetrim-lossand production optimization problem in the paper industry. The work of Westerlund andcoworkersatAp15 boAkademiUniversityinFinlandisakeycontributioninthisarea.Harjunkoski9consideredamathematicalprogrammingapproachtothetrim-lossproblemandpresentedtwodi!erenttypesofformulation.Intherstone,boththecuttingpatternsthatneedtobeusedandthenumberofrollsthathavetobecutaccordingtoeachsuchpatternaretreatedasunknowns.Thisresultsinanintegernonlinearmathematicalproblem(INLP)involvingbilinearproblemsofthevariablescharacterizingeachcuttingpatternandthecorrespondingnumberofrollscutinthisway.Twodi!erentwaysoflinearizingtheINLPtoobtainamixedintegerlinearprogramming(MILP)modewerepresented.However,theselinearizationsoftenresultinasignicantincreaseinthenumberofvariablesandconstraints,aswellasalargeintegralitygap.ThesecondtypeofformulationpresentedbyHarjunkoski9isbasedonusingaxedsetofcuttingpatternsthatisdecidedapriori.ThisresultsinaMILPthathasamuchsmallerintegralitygapthantheoneresultingfromthelinearizationoftheINLPformulationmentionedabove.However,thesolutionobtainedisguaranteedtobeoptimalonlyifallnon-inferiorcuttingpatternsareidentiedandtaken into consideration. The number of such patterns may be quite substantial for realisticindustrialproblems.Extendingtheabovework,Harjunkoski10presentedlinearandconvexformulationsforsolvingthenon-convextrim-lossproblems.Westerlund11consideredthetwo-dimensionaltrim-lossprobleminpaperconverting.Anon-convexoptimizationmodelwasproposedwhereboththewidthsandthelengthsoftherawpaperwereconsideredasvariables.Atwo-stepsolutionprocedurewasusedwhereallfeasiblecuttingpatternswere rst generated and then a MILP problem was solved.In a similar fashion,theproductionoptimizationprobleminthepaperconvertingindustrywasaddressedbyWesterlund12.Schedulingaspectsofthecuttingmachinesinpaperconvertingweresimultaneouslycon-sideredwiththetrim-lossproblembyWesterlund13.Recently,Harjunkoski14incorporatedenvironmentalimpactconsiderationsintoageneralframeworkfortrim-lossminimization.G. Schilling, M.C. Georgiadis/Computers & Operations Research 29 (2002) 10411058 1043ThispaperpresentsanalternativemathematicalprogrammingformulationthatresultsdirectlyinaMILPofsmallintegralitygap.Thesalientfeatureofthismodelisthatitdoesnotrequireapriorienumerationofallpossiblecuttingpatterns.Thenextsectionpresentsaformalstatementoftheproblemunderconsiderationandthenotationused.Section3considersthemathematicalformulationoftheobjectivefunctionandtheoperationalconstraints.Thisisfollowedbysomeexampleproblemsincludinganindustrialcasestudyillustratingtheapplicabilityandcomputa-tionalbehavioroftheproposedformulation.2. Problem statement and dataThetaskbeingconsideredhereistoproduceproductrollsofIdi!erenttypes,thewidthoftypeibeingdenotedbyBp71,i1,2,Ifromoneormorestandardrolls.Thelengthsofallrawrollsandoftheproductrollsresultingfromthemareassumedtobeidenticalandxed.Itisbeyondthescopeofthisworktoconsiderthetwo-dimensionalproblemwhereboththewidthsandthelengthsofrawpaperrollsandthecuttingpatternsareconsideredvariables.Productrollsaremostlyproducedtoorder.Theminimumorderedquantityforproductrollsofwidth i is denoted by Np13p9p14p71and is given, and so is the correspondingunit price pp71. However,customersmaybewillingtobuyadditionalrollsoftypeiuptoamaximumquantityNp13p0p24p71subjecttoadiscountofcp3p9p19p2p71foreachproductrolloverandabovetheminimumnumberNp13p9p14p71.Ingeneral,thenumberofadditionalrollssoldinthismannertendstoberathersmallsincethemainincentiveofsuchdiscountingfromthe pointofviewofthe manufacturerismerelyto decreasethe lossthroughtrim.Theproductrollsaretobecutfromrawrollsofdi!erentstandardtypes.Theunitpriceforarawrolloftypetisdenotedbycp18p15p12p12p82anditsnominalwidthbyBp18p15p12p12p82.However,theusefulwidthofa roll of type t is determined by the cutting machine used. In particular, each raw roll typet1,2,ischaracterizedbyamaximumpossibletotalengagementBp13p0p24p82denotingthemaximumtotalwidthofallproductrollsthatcanbecutfromarawrollofthistype.Theremayalsobeaminimumrequiredtotalengagement Bp13p9p14p82forthistypeofroll.IngeneralBp13p9p14p82)Bp13p0p24p82)Bp82, t1,2,.Themaximumnumber Np13p0p24p82ofproductrollsthatcanbecutoutofarawrolloftype t willgenerally be determined by the knives and other characteristics of the available machine.Moreover,insomecases,theremaybelimitationsintheavailablenumberJHp82ofrawrollsofagiventype t.Thecuttingpatternforeachraw rollis determinedby the positionof theknives.Frequentchangesinthesepositionsaregenerallyundesirable.Eachsuchchangemaythereforebeassociatedwithanon-zerocost cp2p8p0p14p6p4.Theproductionoftherequiredproductrollsfromtheavailablerawrollsmayresultintrimwastewhichmayneedtobedisposedof.Thecostofsuchdisposalperunitwidthoftrimisdenotedby cp3p9p19p16.Basedonthegivendata,werstderiveanupperboundJonthenumberofrawrollsthatmayneedtobecut.ThisisobtainedbyassumingthatthemaximumnumberNp13p0p24p71ofproductrollsofeach type i will be produced; that raw rolls of the type t that permits the smallest minimum1044 G. Schilling, M.C. Georgiadis/Computers & Operations Research 29 (2002) 10411058engagement Bp13p9p14p82willbeused;andthateachrawrollwillbeusedtoproduceproductrollsofasingletypeonly.Overall,thisleadstothefollowingupperboundonthenumberofrawrollsthatmayberequired:Jp13p0p24p39p9p71p14p16Np13p0p24p71p87minp82Bp13p9p14p82/Bp71p88. (1)We can also calculate a lower bound Jp13p9p14 on the minimum number of raw rolls that arenecessarytosatisfytheminimumdemandfortheexistingorders.Wedothisbyassumingthatrollsof the type t allowing the maximum possible engagement Bp13p0p24p82are used, and that no trim isproduced.However,wemustalsotakeaccountofpossiblelimitationsonthenumberofavailableknives. Overall, this leads to the following lower bound on the number of rolls that mayberequired:Jp13p9p14maxp7p9p39p71p14p16Np13p9p14p71Bp71maxp82Bp13p0p24p82,p9p39p71p14p16Np13p9p14p71maxp82Np13p0p24p82p8. (2)3. Mathematical formulationTheaimofthemathematicalformulationistodeterminethetypetofeachrawrolljtobecutandthenumberofproductrollsofeachtype i tobeproducedfromit.3.1. Key variablesThefollowingintegervariablesareintroduced:np71p72:numberofproductrollsoftype i tobecutoutofrawroll jafii9773p71: numberofproductrollsoftype i producedoverandabovetheminimumnumberordered.Wenotethat np71p72cannotexceed:p69 themaximumnumber Np13p0p24p71ofproductrollsoftype i thatcanbesold;p69 themaximumnumberofproductrollsofwidth Bp71thatcanbeaccommodatedwithinamax-imumengagementBp13p0p24p82forarawrolloftype t;p69 themaximumnumber Np13p0p24p82ofknivesthatcanbeappliedtoarawrolloftype t.Thisleadstothefollowingboundsfor np71p72:0)np71p72)minp1Np13p0p24p71,maxp16p87p82p87p50Bp13p0p24p82Bp71,maxp16p87p82p87p50Np13p0p24p82p2i1,2,I, j1,2,Jp13p0p24. (3)Also0)afii9773p71)Np13p0p24p71!Np13p9p14p71, i1,2,I. (4)G. Schilling, M.C. Georgiadis/Computers & Operations Research 29 (2002) 10411058 1045Wenotethat afii9773p71needtobeincludedinthemodelonlyif Np13p0p24p71Np13p9p14p71.Wealsointroducethefollowingbinaryvariables:yp82p72p71 ifthe jthrolltobecutisoftype t,0 otherwise.zp72p71 ifthecuttingpatternforpaperroll j isdifferenttothatforroll j!1,0 otherwise.Wenotethat,ingeneral,theindexjwillbeintherange1,2,Jp13p0p24.However,theformulationtobepresentedwillassignatypet onlytotherawrollsjthatareactuallyused.Hence,thetotalnumberofrollstobecutwillalsobedeterminedbythesolutionoftheoptimizationproblem.Thiswillbecomeclearerinthenextsubsection.3.2. Roll type determination constraintsEachrawroll j tobecutmustbeofauniquetype t.Thisresultsinthefollowingconstraints:p50p9p82p14p16yp82p721, j1,2,Jp13p9p14, (5a)p50p9p82p14p16yp82p72)1, jJp13p9p14#1,2,Jp13p0p24. (5b)Notethatfor jJp13p9p14,itispossiblethat yp82p720for all types t;thissimplyimpliesthatitisnotnecessarytocutroll j.Furthermore,thelimitedavailabilityofrawrollsofagiventypetmaybeexpressedintermsoftheconstraintp40p13p0p24p9p72p14p16yp82p72)JHp82, t1,2,. (6)3.3. Cutting constraintsWeneedtoensurethat,ifarolljistobecut,thenthelimitationsontheminimumandmaximumengagementareobserved.Thisisachievedviatheconstraintsp50p9p82p14p16Bp13p9p14p82yp82p72)p39p9p71p14p16Bp71np71p72)p50p9p82p14p16Bp13p0p24p82yp82p72, j1,2,Jp13p0p24. (7)Wenotethatthequantityp9p39p71p14p16Bp71np71p72representsthetotalwidthofallproductrollstobecutoutofrawroll j.Ifyp82p721forsomerolltype t,thenconstraint(7)ensuresthatBp13p9p14p82)p39p9p71p14p16Bp71np71p72)Bp13p0p24p82.1046 G. Schilling, M.C. Georgiadis/Computers & Operations Research 29 (2002) 10411058Ontheotherhand,ifyp82p720forall t,thenconstraint(7)e!ectivelyforcesnp71p720foralli1,2,I.Thisexpressestheobviousfactthatifrolljisnotactuallycut,thennoproductrollsofanytypecanbeproducedfromit.Wealsoneedtoensurethatthenumberofproductrollscutoutofanyrolljoftypetdoesnotexceedthenumberofknivesthatcanbedeployedonrollsofthistype.Thisiswrittenas0)p39p9p71p14p16np71p72)p50p9p82p14p16Np13p0p24p82yp82p72, j1,2,Jp13p0p24. (8)3.4. Production constraintsThetotalnumberofproductrollsofeachtype i thatareproducedcomprisestheminimumorderedquantity Np13p9p14p71forthistypeplusthesurplusproductionafii9773p71:p40p13p0p24p9p72p14p16np71p72Np13p9p14p71#afii9773p71, i1,2,I. (9)Theseconstraints,togetherwiththeboundsonafii9773p71,ensurethatthequantityofproductrollsoftypei producedliesbetweentheminimumandmaximumbounds Np13p9p14p71and Np13p0p24p71,respectively.3.5. Changeover constraintsIfchangingthecuttingpatternincursanon-zerocost cp2p8p0p14p6p40,weneedtodeterminewhensuchchangeswilltakeplace.Tothisend,weincludethefollowingconstraint:!Mp71zp72)np71p72!np71p11p72p92p16)Mp71zp72, i1,2,I, j2,2,Jp13p0p24. (10)Notethatthiswillallowzp72tobezeroonlyifnp71p72np71p11p72p92p16forallproductrollsi,i.e.ifrollsjandj!1arecutinexactlythesameway.Here,theconstantMp71isanupperboundonnp71p72(seeSection3.1).3.6. Objective functionTheobjectiveoftheoptimizationistomaximizethetotalprotoftheoperationtakingaccountof:p69 Theincomefromthesalesofproductrollsofeachtype i.Thiscomprisestheincomefromsellingtheminimumorderedquantities Np13p9p14p71atthefullunitprice pp71,plus theincomeof sellingtheadditionalquantities afii9773p71atthe discountedunitpricepp71!cp3p9p19p2p71:p39p9p71p14p16(pp71Np13p9p14p71#afii9773p71(pp71!cp3p9p19p2p71).p69 Thecostsoftherollstobecut.Generally,thecostofeachrolldependsonitstype.Thetotalcostcanbewrittenasp40p13p0p24p9p72p14p16p9p82p14p16cp18p15p12p12p82yp82p72.G. Schilling, M.C. Georgiadis/Computers & Operations Research 29 (2002) 10411058 1047Wenotethat,foreachrollj,atmostonetermoftheinnersummationisnon-zero(cf.constraints(5a)and(5b).p69 Thecostsofchangingthepositionsoftheknives.Ingeneral,theknifepositionshavetobechangedifthecuttingpatternusedforagivenrolljisdi!erenttothatforthepreviousone.Thisisdeterminedbythevariableszp72andresultsinthecosttermcp2p8p0p14p6p4p40p13p0p24p9p72p14p17zp72,wherethesummationisequaltothetotalnumberofchangesthatarenecessary.p69 Thecostofdisposingofanytrimproduced.Thewidthoftrimproducedoutofrawrolljisgivenbythedi!erencebetweentherollwidthandthetotalwidthofallproductrollscutfromit.Theformerquantitydependsonthetypeoftherollandcanbeexpressedasp9p50p82p14p16Bp18p15p12p12p82yp82p72;onceagain,atmostoneofthetermsinthissummationcanbenon-zero(cf.constraints(5a)and(5b).Thelatterquantityisgivenbyp9p39p71p14p16Bp71np71p72.Overall,trimdisposalresultsinthefollowingcosttermcp3p9p19p16p40p13p0p24p9p72p14p16p1p50p9p82p14p16Bp18p15p12p12p82yp82p
- 温馨提示:
1: 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
人人文库网所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
川公网安备: 51019002004831号