生产线平衡外文文献

AntalgorithmsforatimeandspaceconstrainedassemblylinebalancingproblemJoaquı´nBautista*,JordiPereiraNissanChairETSEIBUniversitatPolite`cnicadeCatalunya,7thFloor,AvdaDiagonal647,08028Barcelona,SpainAvailableonline2February2006AbstractThepresentarticlefocusesontheapplicationofaprocedurebasedonantcoloniestosolveanassemblylinebalanc-ingproblem.Afteranintroductiontoassemblylineproblems,theproblemunderstudyispresented:theTimeandSpaceconstrainedAssemblyLineBalancingProblem(TSALBP);andabasicmodelofoneofitsvariantsisputforwardforstudy.Subsequently,anantalgorithmispresentedthatincorporatessomeideasthathaveofferedgoodresultswithsimplebalancingproblems.Finally,thevalidityoftheproposedalgorithmsistestedbymeansofacomputationalexpe-riencewithreferenceinstances,andtheconclusionsofthestudyarepresented.2005ElsevierB.V.Allrightsreserved.Keywords:Artificialintelligence;Manufacturing;Metaheuristics;Production1.IntroductionAnassemblylineismadeupofanumberofworkstations,m,arrangedinseriesandinparallel,throughwhichtheworkinprogressonaproductflows.Thestationsarelinkedtogetherbyatransportsystemwhosemissionistosupplymaterialstothemainflowandtomovetheproductionitemsfromonestationtothenext.Productionitemsmaybeofonetype(single-model)orofseveraltypes(mixed-model).ThemanufacturingofaproductionitemisdividedupintoasetVofntasks;eachstationk(16k6m)isassignedasubsetoftasksSk(SkV)calledtheworkloadofstationk;ataskjmayonlybeassignedtoonestation.Eachtaskjrequiresanoperationtimetj0foritsexecutionthatisdeterminedasafunctionofthemanufacturingtechnologiesandtheemployedresources.Inmixed-modelassemblylines,itisusualto0377-2217/$-seefrontmatter2005ElsevierB.V.Allrightsreserved.doi:10.1016/j.ejor.2005.12.017*Correspondingauthor.Tel.:[phone];fax:[phone].E-mailaddresses:[e-mail](J.Bautista),[e-mail](J.Pereira).EuropeanJournalofOperationalResearch177(2007)2016–2032fferentmodelsishigh,unitsmustbesequencedaccordingly.Additionally,thetechnologyandnatureoftheproductitselfmeanthateachtaskjhasasetofimme-diatelypredecessortasks,Pj,whichmustbeaccomplishedbeforecommencingtaskj.Theseconstraintsarenormallyrepresentedbymeansofanacyclicprecedencegraphwhoseverticesrepresentthetasksandinwhicheachdirectedarc(i,j)indicatesthattaskimustbefinishedbeforecommencingtaskjontheline;thus,ifi2Shandj2Sk,thenh6kmustbefulfilled.Eachstationkpresentsastationworkloadtimet(Sk)thatisequaltothesumofthedurationsofthetasksassignedtostationk.Oncepermanentmanufacturingconditionshavebeenachieved,theproductionitemsflowalongthelineataconstantrate,andeachstationkhasatimec,calledthecycletime,tocarryoutitsassignedtasks.Onautomotivetrimorbodylines,theitemsnormallyremaininspacesallottedtoeachstation,wherethecorrespondingtasksareexecutedduringatimeequaltothecycle.Theitemsarethentransferredtothenextstationinaninsignificantperiodoftime,thusinitiatinganewcycle.Thecycletimecdeterminestheproductionrateroftheline(r=1/c),andcannotbelessthanthemaximumstationworkloadtime:cPmaxk{t(Sk)},normustitbegreaterthanthesumofthedurationsofthetasksofV:c6Pkt(Sk)=tsum.EachstationkpresentsaidletimeIk=ct(Sk).Thesumofthesepartialtimesgivesrisetothetotalidletime,Isum=PkIk=mÆctsum,whichisrelatedtotheinefficiencyoftheline.Ingeneral,ALBP(AssemblyLineBalancingProblems)focusongroupingtogetherthetasksinthesetVinworkstationsinanefficientandcoherentway.Inshort,thegoalistoachieveagroupingoftasksthatmini-mizestheinefficiencyofthelineoritstotaldowntimeandthatrespectsalltheconstraintsimposedonthetasksandonthestations.ALBPbelongstothegeneralclassofsequencingproblems(seeBaker,1974),andcanbeseenasBinPackingProblemswithadditionalsideconstraints,asprecedencerelationshipsbetweentasks.Theseprecedenceconstraintsestablishanimplicitorderofbins,derivinginasequenceofoperations.Afirstfamilyofproblems,knownasSALBP(SimpleAssemblyLineBalancingProblems)Baybars(1986),maybestatedinthefollowingway:givenasetofntaskswiththeirattributesandaprecedencegraph,eachtaskmustbeassignedtoasinglestationinsuchawaythatalltheprecedenceconstraintsaresatisfiedandnostationworkloadtime,t(Sk),isgreaterthanthecycletimec.TheSALBPfamilypresentsfourvariants:SALBP-1:minimizethenumberofstationsmgivenafixedvalueofthecycletimec;SALBP-2:minimizethecycletimec(maximizetheproductionrater)givenafixednumberofstationsm;SALBP-E:simultaneouslyminimizecandmconsideringtheirrelationwiththetotalidletimeortheinefficiencyoftheline;SALBP-F:givenmandc,determinethefeasibilityoftheproblem,andifitisfeasible,findasolution.WhenotherconsiderationsareaddedtothoseoftheSALBPfamily,theproblemsareknowninthelit-eraturebythenameofGALBP(GeneralAssemblyLineBalancingProblems).Thisfamilyincludesthoseproblemswithadditionalconstraints,suchasforinstancetheconsiderationofparallelstations,DaganzoandBlumfield(1994)andVilarinhoandSimaria(2002),forcedgroupingsoftasks,Deckro(1989)possibleincompatibilitiesamongtasks,Agnetisetal.(1995)anddifferencesbetweenworkstations,Nicosiaetal.(2002