abstract complexity of flow shop scheduling problems with

《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