资源描述：
《求解作业车间调度问题的全局邻域搜索方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第15卷第7期计算机集成制造系统Vol.15No.72009年7月ComputerIntegratedManufacturingSystemsJuly2009文章编号:1006-5911(2009)07-1383-06求解作业车间调度问题的全局邻域搜索方法崔健双,李铁克(北京科技大学经济管理学院,北京100083)摘要:采用传统的关键邻域搜索方法求解作业车间调度问题时,往往容易陷入局部极值而且难以跳出。为此,提出了一种具有动态调整能力的全局邻域交换策略,该策略有可能产生大量的不可行调度,需要一种筛选方法加以过滤。证明了一个新的邻域交换性
2、质,利用该性质可以对所得调度方案作可行性约束判定,从而有效地过滤掉不可行调度。在此基础上,提出了一种求解作业车间调度问题的算法。最后,取不同规模的Benchmark问题算例对该算法进行测试,结果表明,无论从解的质量还是计算时间都取得了较好的效果。关键词:邻域结构;关键路径;作业车间调度;邻域交换;调度算法中图分类号:TP18文献标识码:AGlobalneighborhoodalgorithmforJobShopschedulingproblemCUIJianshuang,LITieke(SchoolofEconomicManage
3、ment,UniversityofScience&TechnologyBeijing,Beijing100083,China)Abstract:TraditionalcriticalneighborhoodalgorithmsforJobShopschedulingproblemwereeasilytrappedintolocaloptimalandhardlytoescape.Todealwiththisproblem,aglobalneighborhoodswappingstrategywithdynamicadapatabilityw
4、asproposed.However,thisnewstrategymightpossiblyinduceinfeasiblesolutions.Thus,anewpropositionconcerningtheneighborhoodswappingstrategywaspresentedandproved,whichcouldbeusedtoverifywhetheraneighborhoodswappingwasacceptableornot.Basedonthisglobalneighborhoodstrategy,anewalgo
5、rithmwasdevelopedandtestedbyagroupofbenchmarkinstances.Theresultsindicatedthatthenewalgorithmobtainedsatisfactoryresultsbothonsolutionsqualityandcomputationtime.Keywords:neighborhoodstructure;criticalpath;JobShopscheduling;neighborhoodswapping;schedulingalgorithms调度问题的
6、难度有了进一步的认识,发展了关于调0引言度算法的有效性和计算复杂性理论,并且证明出许自从20世纪50年代以来,调度问题相关理论多调度问题包括多数作业车间调度问题(JobShop[1]及其应用技术的研究已经发展成为一门重要的学SchedulingProblem,JSP)都是NP完备问题。科,从经典的单机调度、并行机调度、车间调度发展JSP是利用一组有限资源对一批有限任务在满到后来的多目标调度、随机调度和模糊调度等内容。足给定约束条件下求解最优目标函数的一个复杂的调度问题成为从事运筹学、人工智能学和应用数学组合优化问题,也是迄今为止人们研究最
7、多、研究成等学科领域的学者们关注的焦点,相应的应用领域果最丰富、但仍未得到根本解决的问题之一。事实在不断地扩大。随着问题研究的深化,人们对解决表明,有些NP完备问题存在有限时间内的可行解,收稿日期:20080618;修订日期:20081013。Received18June2008;accepted13Oct.2008.基金项目:国家自然科学基金资助项目(70771008,70371057)。Foundationitem:ProjectsupportedbytheNationalNaturalScienceFundation,Chin
8、a(No.70771008,70371057).作者简介:崔健双(1971-),男,河北衡水人,北京科技大学经济管理学院副教授,博士,主要从事生产调度算法理论及应用、安全电子商务
