《基于遗传算法求解作业车间调度问题本科毕业设计论文.doc》由会员分享，可在线阅读，更多相关《基于遗传算法求解作业车间调度问题本科毕业设计论文.doc（43页珍藏版）》请在金锄头文库上搜索。
1、 辽宁科技大学本科生毕业设计 第I页基于遗传算法求解作业车间调度问题摘 要作业车间调度问题(JSP)简单来说就是设备资源优化配置问题。作业车间调度问题是计算机集成制造系统(CIMS)工程中的一个重要组成部分，它对企业的生产管理和控制系统有着重要的影响。在当今的竞争环境下，如何利用计算机技术实现生产调度计划优化，快速调整资源配置，统筹安排生产进度，提高设备利用率已成为许多加工企业面临的重大课题。近年来遗传算法得到了很大的发展，应用遗传算法来解决车间调度问题早有研究。本文在已有算法基础上详细讨论了染色体编码方法并对其进行了改进。在研究了作业车间调度问题数学模型和优化算法的基础上，将一种改进的自适应
2、遗传算法应用在作业车间调度中。该算法是将sigmoid函数的变形函数应用到自适应遗传算法中，并将作业车间调度问题中的完工时间大小作为算法的评价指标，实现了交叉率和变异率随着完工时间的非线性自适应调整，较好地克服了标准遗传算法在解决作业车间调度问题时的“早熟”和稳定性差的缺点，以及传统的线性自适应遗传算法收敛速度慢的缺点。以改进的自适应遗传算法和混合遗传算法为调度算法，设计并实现了作业车间调度系统，详细介绍了各个模块的功能与操作。最后根据改进的编码进行遗传算法的设计，本文提出了一种求解车间作业调度问题的改进的遗传算法，并给出仿真算例表明了该算法的有效性。关键词：作业车间调度；遗传算法；改进染色体
3、编码；生产周期 辽宁科技大学本科生毕业设计 第37页Solving jopshop scheduling problem based on genetic algorithmAbstractSimply speaking, the job shop scheduling problem(JSP) is the equipment resources optimization question. Job Shop Scheduling Problem as an important part of Computer IntegratedManufacturing System (CIMS) en
4、gineering is indispensable, and has vital effect onproduction management and control system. In the competion ecvironment nowadays, how touse the assignments quickly and to plan production with due consideration for all concernedhas become a great subject for many manufactory.In recent years,the gen
5、etic algorithms obtained great development it was used to solve the job shop scheduling problem early.This paper discusses the chromosome code method in detail based on the genetic algorithms and make the improvement on it. Through the research on mathematics model of JSP and optimized algorithm, th
6、eimproved adaptive genetic algorithm (IAGA) obtained by applying the improved sigmoidfunction to adaptive genetic algorithm is proposed. And in IAGA for JSP, the fitness ofalgorithm is represented by completion time of jobs. Therefore, this algorithm making thecrossover and mutation probability adju
7、sted adaptively and nonlinearly with the completiontime, can avoid such disadvantages as premature convergence, low convergence speed andlow stability. Experimental results demonstrate that the proposed genetic algorithm does notget stuck at a local optimum easily, and it is fast in convergence, sim
8、ple to be implemented. the job shop scheduling system based on IAGA and GASH is designed andrealized, and the functions and operations of the system modules are introduced detailedly. In the end ,according to the code with improved carries on the genetic algorithms desing, this paper offer one impro
9、ved genetic algorithms about soloving to the job shop scheduling problem, and the simulated example has indicated that this algorithm is valid.Keywords: jop shop scheduling; genetic algorithm; improvement chromosome code; production cycl毕业设计（论文）原创性声明和使用授权说明原创性声明本人郑重承诺：所呈交的毕业设计（论文），是我个人在指导教师的指导下进行的研究
10、工作及取得的成果。尽我所知，除文中特别加以标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研究成果，也不包含我为获得 及其它教育机构的学位或学历而使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体，均已在文中作了明确的说明并表示了谢意。作 者 签 名： 日 期： 指导教师签名： 日期： 使用授权说明本人完全了解 大学关于收集、保存、使用毕业设计（论文）的规定，即：按照学校要求提交毕业设计（论文）的印刷本和电子版本；学校有权保存毕业设计（论文）的印刷本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的
11、部分或全部内容。作者签名： 日 期： 学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名： 日期： 年 月 日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权 大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印
12、、缩印或扫描等复制手段保存和汇编本学位论文。涉密论文按学校规定处理。作者签名：日期： 年 月 日导师签名： 日期： 年 月 日目 录摘 要IAbstractII1 绪论11.1 课题来源11.2 作业车间调度问题表述11.3 车间作业调度问题研究的假设条件及数学模型21.3.1 车间作业调度问题研究的假设条件21.3.2 车间作业调度问题的数学模型31.4 课题研究内容及结构安排42 遗传算法相关理论与实现技术62.1 自然进化与遗传算法62.2 基本遗传算法72.2.1 遗传算法的基本思路72.2.2 遗传算法的模式定理72.2.3 遗传算法的收敛性分析92.2.4 基本遗传算法参数说明10
13、2.3 遗传算法的优缺点112.3.1 遗传算法的优点112.3.2 遗传算法的缺点112.4 遗传算法的进展122.5 小结153 用遗传算法对具体问题的解决与探讨163.1 研究过程中的几个关键问题163.1.1 设备死锁现象163.1.2 参数编码163.1.3 初始种群的生成193.1.4 个体的适应度函数203.1.5 算法参数203.1.6 遗传算子的设计213.2 遗传算法终止条件243.3 遗传算法解决车间调度问题的改进243.4 系统仿真243.5 小结29结 论30致 谢31参考文献32附 录331 绪论1.1 课题来源随着加入WTO，市场竞争越来越激烈，对制造企业来说，为
14、了能够在竞争中立于不败，降低成本是不得不面临的问题，而确保生产车间较高的生产能力和效率，是当务之急。此外，有效的调度方法已经成为先进制造技术实践的基础和关键，所以对它的研究具有重要的理论和实用价值。当前科学技术正进入多学科互相交叉、互相渗透、互相影响的时代，生命科学与工程科学的交叉、渗透和相互促进是其中一个典型例子，也是近代科学技术发展的一个显著特点。遗传算法的蓬勃发展正体现了科学发展的这一特点和趋势。所谓生产调度，即对生产过程进行作业计划，作为一个关键模块，是整个先进生产制造系统实现管理技术、运筹方法、优化技术、自动化与计算机技术发展的核心，有效的调度方法和优化技术的研究与应用，是实现先进制
15、造和提高生产效益的基础和关键。虽然对其研究已有几十年的历史但至今尚未形成一套系统的方法和理论，理论研究与实际应用之间还存在着较大距离。目前的调度算法大多只关心工件的调度问题，而对其它资源分配问题则研究相对不多，将二者结合起来研究应该是值得注意的问题，目前已有不少学者开始关注该问题。由于一般车间调度问题的复杂性，各种不同的具体问题往往有许多不同的算法来解决，例如经典的启发式算法，传统的搜索方法等。由于遗传算法是一种借鉴生物界自然选择和进化机制发展起来的高度并行、随机、自适应搜索算法1。它特别适合于处理传统搜索算法解决不好的复杂和非线性问题。一些学者们经过大量的实践证明了遗传算法在解决作业车间调度问题上比经典的启发式算法好
