资源描述:
《abstract complexity of flow shop scheduling problems with》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、EuropeanJournalofOperationalResearch161(2005)32–41www.elsevier.com/locate/dswComplexityofflowshopschedulingproblemswithtransportationconstraintsa,*baA.Soukhal,A.Oulamara,P.MartineauaLaboratoired’Informatique,EcolePolytechniquedel’UniversitedeTours,64avenueJeanPortalis,37200Tours,FrancebLaboratoi
2、reLeibnizIMAGGrenoble,46AvFelixViallet,38000Grenoble,FranceAvailableonline27November2003AbstractInmostmanufacturinganddistributionsystems,semi-finishedjobsaretransferredfromoneprocessingfacilitytoanotherbytransporterssuchasAutomatedGuidedVehicles,robotsandconveyors,andfinishedjobsaredeliveredtowar
3、ehousesorcustomersbyvehiclessuchastrucks.Thispaperinvestigatestwo-machineflowshopschedulingproblemstakingtransportationintoaccount.Thefinishedjobsaretransferredfromtheprocessingfacilityanddeliveredtocustomersbytruck.Bothtransportationcapacityandtransportationtimesareexplicitlytakenintoaccountinthe
4、semodels.Westudytheclassofflowshopproblemsbyanalysingtheircomplexity.Forthemakespanobjectivefunction,weprovethatthisproblemisstronglyNP-hardwhenthecapacityofatruckislimitedtotwoorthreepartswithanunlimitedbufferattheoutputoftheeachmachine.Thisproblemwithadditionalconstraints,suchasblocking,isalsopr
5、oventobestronglyNP-hard.Ó2003ElsevierB.V.Allrightsreserved.Keywords:Flexiblemanufacturingsystems;Flowshop;Scheduling;Complexity1.Introductionoftransportersforjob-deliveringorthatjobsareinstantaneouslytransportedfromonelocationtoAFlexibleManufacturingSystem(FMS)isananotherwithnotransportationtime
6、takenintointegratedsystemcomposedofautomatedmate-account.rialhandlingdevicesandofnumericallycontrolledInfact,inmostmanufacturinganddistributionmachinesthatcanprocessavarietyofparttypessystems,semi-finishedjobsaretransferredfrom[12].Thissystemhasbeenintroducedtoincreaseoneprocessingfacilitytoanoth
7、erbytransportersflexibilitybyovercomingthetraditionalhypothe-suchasAutomatedGuidedVehicles(AGVs),ro-sesassumingthateitherthereisaninfinitenumberbotsandconveyors,andfinishedjobsaredeliveredtowarehousesorcustomersbyvehiclessuchas