组合机床外文文献

DOI10.1007/s00170-004-2493-9ORIGINALARTICLEIntJAdvManufTechnol(2006)29:178–183FerdaC.C¸etinkayaUnitsizedtransferbatchschedulinginanautomatedtwo-machineflow-linecellwithonetransportagentReceived:26July2004/Accepted:22November2004/Publishedonline:16November2005©Springer-VerlagLondonLimited2005AbstractTheprocessofsplittingajoblotcomprisedofsev-eralidenticalunitsintotransferbatches(someportionofthelot),andpermittingthetransferofprocessedtransferbatchestodownstreammachines,allowstheoperationsofajoblottobeoverlapped.Theessenceofthisideaistoincreasethemovementofworkinthemanufacturingenvironment.Inthispaper,theschedulingofmultiplejoblotswithunitsizedtransferbatchesisstudiedforatwo-machineflow-linecellinwhichasingletransportagentpicksacompletedunitfromthefirstmachine,deliversittothesecondmachine,andreturnstothefirstma-chine.Acompletedunitonthefirstmachineblocksthemachineifthetransportagentisintransit.Weexaminethisproblemforbothunitdependentandindependentsetupsoneachmachine,andproposeanoptimalsolutionproceduresimilartoJohnson’sruleforsolvingthebasictwo-machineflowshopschedulingproblem.KeywordsAutomatedguidedvehicle·Lotstreaming·Scheduling·Sequencing·Transferbatches1IntroductionMostclassicalshopschedulingmodelsdisregardthefactthatproductsareoftenproducedinlots,eachlot(processbatch)con-sistingofidenticalparts(items)tobeproduced.Thesizeofajoblot(i.e.,thenumberofitemsitconsistsof)typicallyrangesfromafewitemstoseveralhundred.Inanycase,joblotsareassumedtobeindivisiblesingleentities,althoughanentirejoblotconsistsofmanyidenticalitems.Thatis,partialtransferofcompleteditemsinalotbetweenmachinesontheprocessingroutingofthejoblotisimpossible.ButitisquiteunreasonabletowaitfortheF.C.Çetinkaya(
)DepartmentofIndustrialEngineering,EasternMediterraneanUniversity,Gazimagusa-T.R.N.C.,MersinTurkeyE-mail:[e-mail].:[phone]Fax:[phone]entirelottofinishitsprocessingonthecurrentmachine,whiledownstreammachinesmaybeidle.Itshouldbeobviousthatprocessingtheentirelotasasingleobjectcanleadtolargework-in-processinventoriesbetweenthemachines,andtoanincreaseinthemaximumcompletiontime(makespan),whichisthetotalelapsedtimetocompletetheprocessingofalljoblots.However,thesplittingofanentirelotintotransferbatchestobemovedtodownstreammachinespermitstheoverlappingofdifferentoper-ationsonthesameproductwhileworkproceeds,tocompletethelotontheupstreammachine.Therearemanywaystosplitalot:transferbatchesmaybeequalorunequal,withthenumberofsplitsrangingfromonetothenumberofunitsinthejoblot.Forinstance,considerajoblotconsistingof100identicalitemstobeprocessedinathree-stagemanufacturingenvironmentinwhichtheflowofitsoperationsisunidirectionalfromstage1throughstage3.Assumethattheunitprocessingtimeatstages1,2,and3are1,3,2min,respec-tively.Ifwedonotallowtransferbatches,thethroughputtimeis(100)(1+3+2)=600min(seeFig.1a).However,ifwecreatetwoequalsizedtransferbatchesthroughallstages,thethrough-puttimedecreasesto450min,areductionof25%(seeFig.1b).Itisclearthatthethroughputtimedecreasesasthenumberoftransferbatchesincreases.Flowshopproblemshavebeenstudiedextensivelyandre-portedintheliteraturewithoutexplicitlyconsideringtransferbatches.Johnson[1],inhispioneeringwork,proposedapoly-nomialtimealgorithmfordeterminingtheoptimalmakespanwhenseveraljobsareprocessedonatwo-machine(two-stage)flowshopwithunlimitedbuffer.Withthreeormoremachines,theproblemhasbeenproventobeNP-hard(Gareyetal.[2]).Be-sidestheextensionofthisproblemtothem-stageflowshopprob-lem,optimalsolutionstosomevariationsofthebasictwo-stageproblemhavebeensuggested.Mitten[3]consideredarbitrarytimelags,andoptimalschedulingwithsetuptimesseparatedfromprocessingwasdevelopedbyYoshidaandHitomi[4].Sep-arationofthesetup,processingandremovaltimesforeachjoboneachmachinewasconsideredbySuleandHuang[5].Ontheotherhand,flowshopschedulingproblemswithtrans-ferbatcheshavebeenexaminedbyvariousresearchers.Vickson179Fig.1.ProcessingawithouttransferbatchesandbwithtransferbatchesandAlfredson[6]examinedtwo-andthree-machineflowshopsassumingthereisnolimitonthenumberoftransferbatchessothatitisoptimaltouseunitsizedtransferbatches.Theyshowedthatthetwo-machineproblemwithunitsizedtransferbatchesiseasilysolvedbyaslightmodificationofJohnson’swellknownalgorithm,andalsoprovedthatpre-emptionofjoblotsisnotnecessaryintheoptimalsolution.Thatis,ajobissplitintounitsizedtransferbatchesthatareprocessedcon-secutively(notintermingledwiththetransferbatchesofotherjoblots).CetinkayaandKayaligil[7]andBaker[8]extendedthisstudytoobtainaunifiedsolutionprocedure,whichhan-dlesseparableandinseparablesetups,respectively.Cetinkaya[9]andVickson[10]independentlyshowedthattheschedulingproblemwitheitherequalorunequaltransferbatchesdecom-posesintoaneasilyidentifiablesequenceofsinglejobprob-lems,evenwithsetuptimesandtransfertimes.SriskandarajahandWagneur[11]studiedthelotstreamingandschedulingmultipleproductsintwo-machine,no-waitflowshops.Kimetal.[12]proposedaschedulingruleforatwo-stageflowshopwithidenticalparallelmachinesateachstage.Ontheotherhand,studiesonjoblotschedulingwitht