资源描述：
《有准备时间无等待流水车间调度的搜索算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、计算机研究与发展ISSN100021239ΠCN1121777ΠTPJournalofComputerResearchandDevelopment47(4):6532662,2010有准备时间无等待流水车间调度的搜索算法王初阳1,2李小平1,2茜1,2苑迎春3王1(东南大学计算机科学与工程学院南京210096)2(计算机网络和信息集成教育部重点实验室(东南大学)南京210096)3(河北农业大学信息科学与技术学院河北保定071001)(wangcyonline2000@yahoo.com.cn)ANewLocalSearchAlgori
2、thmforNo2WaitFowshopswithSetupTimeWangChuyang1,2,LiXiaoping1,2,WangQian1,2,andYuanYingchun31(SchoolofComputerScienceandEngineering,SoutheastUniversity,Nanjing210096)2(KeyLaboratoryofComputerNetworkandInformationIntegration(SoutheastUniversity),MinistryofEducation,Nanjing
3、210096)3(FacultyofInformationScienceandTechnology,AgricultureUniversityofHebei,Baoding,Hebei071001)AbstractAnewlocalsearchalgorithmcalledIVNS(iteratedvariableneighborhoodsearch)isproposedfortheno2waitflowshopschedulingproblemwithsetuptimetominimizethetotalcompletiontime.
4、ThreekeyfactorsaretakenintoconsiderationwhendesigninglocalsearchalgorithmslikeIVNS:neighborhoods,neighboringsolutionevaluationsandstrategiesforescapinglocaloptima.Firstly,threenewneighborhoodswithlargersizesareintroducedtoenhancethechanceoffindinghighqualitysolutions.The
5、neighborhoodsarebasedonjobblockexchangeandhavesizesofO(n3)orO(n4),largerthanthecommonly2usedinsertionandexchangeneighborhoods.Secondly,anobjectiveincrementmethodisadoptedtospeeduptheevaluationofneighboringsolutionsintheneighborhoods,leadingtotwoneighboringsolutionscompar
6、edinconstanttimeandtheneighborhoodscompletelyexploredintimesproportionaltotheirsizes.TheobjectiveincrementmethodalsoreducesthetimecomplexityofthefamousNEHalgorithmbyoneorder.Finally,IVNStriestoescapelocaloptimabyswitchingbetweendifferentneighborhoodsaswellasrestartingfro
7、mperturbationoflocaloptima.IVNSiscomparedwiththebestknownalgorithmsfortheconsideredproblemon5400benchmarkinstancesunderidenticalCPUtimes.StatisticanalysisoftheexperimentresultsverifiesthatIVNSremarkablyoutperformsthereferencealgorithmsinaveragesolutionquality.Keywordsloc
8、alsearch;no2waitflowshop;scheduling;setuptime;totalcompletiontime;neighborhood摘要利用迭代变化邻域搜索算法(IVNS)求解最小化
