资源描述：
《一种改进的作业车间调度转换瓶颈算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、http://www.paper.edu.cnAModifiedShiftingBottleneckProcedureforJobShop1SchedulingZhiHuangCollegeofComputerScienceandTechnology，HuazhongUniversityofScienceandTechnologyWuhan,P.R.China430074E-mail：huangzhi666@yahoo.com.cnAbstractInthispaper,thejobshopschedulingproblemwitht
2、heobjectivetominimizethemakespanisdiscussed.Thetheorem,whichguaranteestheshiftingbottleneckprocedure(SB)withSchrageone-machinesequencingalgorithmalwaysobtainsthefeasiblesolutionforanyinstance,isconciselyproven.AcounterexampleisgiventoshowthatSBwithCarlier’sone-machinese
3、quencingalgorithmcouldgettheinfeasiblesolution.Bytheway,wealsopointoutamistakemadeintheCarlier’stheoremwhichCarlier’salgorithmisbasedon,andcompleteitbysomemodifications.InordertoovercometheinfeasibilityweaknessofSBandexpectbetterperformance,amodifiedshiftingbottleneckpr
4、ocedure(MSB)forjobshopschedulingisproposed.Thetheorem,whichensuresMSBgetthefeasiblesolutionforanyinstanceoftheproblem,istestified.MSBistestedonagroupofbenchmarkinstances.ThecomputationalexperimentshowsthatMSBgetbettersolutionsthanSB.Keywords:Jobshopscheduling;Heuristic;
5、Feasibility;ShiftingBottleneck1IntroductionJobshopschedulingproblemisamongthehardestcombinatorialoptimizationproblems,andisstronglyNP-complete[1].Manyheuristicalgorithmshavebeendevelopedincludingdispatchingpriorityrules[2],localsearch[3],shiftingbottleneckprocedure[4],s
6、timulatedannealing[5]andtabusearch[7,8].Theresearchresultsoftheproblemshowthatitishardtoobtaingoodenoughsolutionsonlybysinglesearchscheme.Sothehybridheuristicmethodsthatcombineseveralheuristicschemeshavebeenproposed.Itisknownthatshiftingbottleneckprocedureandtaboosearch
7、arewidelyusedinhybridheuristicmethods[9-11].Adamsetal.proposedshiftingbottleneckprocedure[4],andtheymentionedthatitmightobtaininfeasiblesolutions,andtheyalsopointedoutthattheydidnotfindthecase.However,theydidnotexplainwhythecasemightexist,andtheydidnotprovethatthecasedo
8、esexist,orprovethecasewouldneverhappen.Storeretal.[12]mentionedthatthesimplifiedimplementationofSBtheyusedfail
