资源描述：
《基于遗传和禁忌搜索算法求解车间调度优化问题.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第26卷第4期计算机应用Vol.26No.42006年4月ComputerApplicationsApr.2006文章编号:1001-9081(2006)04-0857-04基于遗传和禁忌搜索算法求解车间调度优化问题1,2111梁迪,谢里阳,隋天中,陶泽(1.东北大学机械工程与自动化学院,辽宁沈阳110004;2.沈阳大学机械工程学院,辽宁沈阳110004)(ldcai@sohu.com)摘要:针对柔性生产环境下的车间调度问题,在考虑遗传算法早熟收敛问题和禁忌搜索法自适应优点的基础上,将遗传算法和禁忌搜索法结合起来,提出了基于遗传和禁忌
2、搜索的混合动态优化调度算法,并用实例对该算法进行了仿真研究。结果表明,此算法有很好收敛精度,是可行的,并且能够在扰动发生后提供新的调度计划,与传统的调度算法相比较,体现了明显的优越性。关键词:遗传算法;禁忌搜索算法;车间调度;组合优化中图分类号:TP311文献标识码:AResearchonshopschedulingoptimizationbasedongeneticandtabusearchhybridalgorithm1,2111LIANGDi,XIELi2yang,SUITian2zhong,TAOZe(1.SchoolofMec
3、hanicalEngineeringandAutomation,NortheasternUniversity,ShenyangLiaoning110004,China;2.SchoolofMechanicalEngineering,ShenyangUniversity,ShenyangLiaoning110044,China)Abstract:InordertoavoidprematureconvergenceandtobalancetheexplorationandexploitationabilitiesofsimpleGA,ahy
4、bridalgorithmwasproposedtosolvedynamicschedulingprobleminflexibleproductionenvironment.ItisusingGAexcellentwholesearchabilityandself2adaptivemeritofTabuSearch(TS),andtheconvergenceofresearchwasimproved.Itiscapableofgeneratingalternativescheduleafteruncertaindisturbanceta
5、kesplaceonajobshop.Afterusingcrossoverandmutationoperations,abestorsecondbestschedulingplancanbefound.Theresultofthetestshowsthatthemethodisfeasibleandefficient.Keywords:geneticalgorithm;tabusearch;jobshopscheduling;combinationoptimization度问题进行研究,这样有利于丰富优化过程中的搜索行为,增0引言强全
6、局和局部意义下的搜索能力和效率,与单纯的遗传算法生产调度是计算机集成制造系统(ComputerIntegrated和禁忌搜索算法相比有明显的优越性。ManufacturingSystem,CIMS)研究领域生产管理的核心内容和1问题描述关键技术,车间调度问题(JobshopSchedulingProblem,JSP)是最困难的约束组合优化问题和典型的NP难问题,其特点是2.1JSP的数学模型建立[1,2]没有一个有效的算法能在多项式时间内求出其最优解。JSP研究n个工件在m台机器上加工,已知各操作的加工到目前为止,已有一些传统的启发式算
7、法求解JSP优化时间和各工件在各机器上的加工次序约束,要求确定与工艺[3,4]调度问题。在文献[3]中,作者先是用Petri网对JSP进行约束条件相容的各机器上所有工件的加工开始时间或完成时建模,然后应用L1算法搜索最优解,L1算法其本质是分枝定间或加工次序,使加工性能指标达到最优。界法和动态规划法的混合运用。文献[4]是用遗传代码先确1)机器顺序阵JM,JM(i,j)表示加工i工件的第j个操作定各Job类型的调度先后顺序,然后用传统的人工智能中的的机器号,JM(i,·)表示i工件的所有操作按优先顺序加工的FBS(FilteredBea
8、mSearch)搜索方法对各个Job的每道工序按各机器号的排列。顺序进行安排调度。这种FBS搜索方法是宽度优先搜索法2)加工时间阵T,T(i,j)为j工件在机器上的加工时间。的一种改进方法。3)工件排列阵M
