并行遗传算法在车间作业调度问题上应用

《并行遗传算法在车间作业调度问题上应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、并行遗传算法在车间作业调度问题上应用山东师范大学硕士学位论文摘要车间作业调度JSSP在企业生产经营活动中占有十分重要的地位。生产调度系统也是CIMS、ERP等系统中的重要组成部分。生产调度位于CIMS体系结构中的中间层，是控制与管理一体化的接合部。向上要给企业经营战略决策层提供决策依据，向下要安排生产加工任务，指导监督控制层的动作。因些，生产调度是实施CIMS的关键。由于车间作业调度问题是一个典型的NP．hard问题，因此受到学术界和工业界的广泛关注。对它的研究具有很高的理论意义和实际意义。迄今为止，已有很多关于车间作业调度问题的研究方法，如分枝定界法

2、、基于优先规则的启发式方法，但是常见的JSSP的困难性和复杂性使传统的搜索方法很难在合理的时间内找到最优解。近年来，已经引进了一些人工智领域的新技术来解决这些问题，如模拟退火SA、禁忌搜索TA、人工神经网络ANN、遗传算法GA等等。遗传算法是一类借鉴生物界的进化规律演化而来的随机化搜索方法，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，己被人门广泛地应用于组合优化、机器学习、信号处

3、理、自适应控制和人工生命等领域。并行遗传算法PGA是过去十几年以来GA研究的热点之一，无论是理论还是应用上都取得一些成熟的成果。因此本文将PGA用于求解JSSP调度问题，本文主要有以下几项内容：1介绍分析了车间作业调度的问题描述、模型表示、特点以及对它的研究方法和研究现状。本文将JSSP的研究方法分为两大类，最优化方法和近似／启发式方法；2作为并行遗传算法的基础，介绍了标准遗传算法的来源，生物学方面的背景，编码方式，适应度函数，基本遗传操作选择、交叉、变异，基本参数的设置原则；3介绍了并行遗传算法的分类，以及他们各自发展的历史现状，粗粒度并行遗传算法的

4、迁移策略，分为两种同步迁移和异步迁移；4详细介绍了针对JSSP的特点设计的新的粗粒度并行遗传算法，主要包括算法流程，编码方式，遗传操作，迁移策略。最后，对两个经典的JSSP的实例即FT6x6、LA01，进行了仿真实验。通过对结果的分析，得出设计的新算法比普通的遗法效率高的结论。山东师范大学硕士学位论文2关键字：并行遗传算法，车间作业调度，编码，迁移策略分类号：TP391山东师范大学硕士学位论文ABSTRACTJob?shopschedulingplaysareatroleintheproductionactivityofallenterprise，jo

5、b?shopschedulingsystemisalsoagreatpartofCIMSorEREProductionschedulingis缸themiddlelayerintheCIMSsystemstructure．whichistejointofcontrolandmanagement．Ononehand,itwillsupplydecisionsfrthenterprise；ontheotherhand，itwillarrangeproductiontasksadsupervisethecontrollayer．Sotheproduction

6、schedulingisthekeyoftheCIMS．JSSPisatypicalNP?hardproblem，soitattractsgreattentionfrmbothteacademiaandndustry．Therefore，thestudyofjobshopscheduleisofgreattheoreticalandpracticalmportance．SofartherehavebeenmanyresearchmethodstodealwithJSSP,suchasbranch-boundmethodandsomehuristicpr

7、oeduresbasedonpriorityrules，butthedifficultyandcomplexityofgeneralJSSPmakesitveryhardfortheconventionalsearch-basedmethodstofindanoptimalsolutioninreasonabletime．Newtchniquesemergingfromthefieldofartificialintelligencehavebeenitroducedtoadresstheseproblemsinrecentyears，suchassim

8、ulatednnealing，tabusearch，artificialneuralnetwo