基于遗传算法求解作业车间调度问题论文

《基于遗传算法求解作业车间调度问题论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于遗传算法求解作业车间调度问题毕业论文目录摘要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基本遗传算法参数说明102.3遗传算法的优缺点112.3.1遗传算法的优点112.3.2遗传算法的缺点112.4遗传算法的进展122.5小结1

2、53用遗传算法对具体问题的解决与探讨163.1研究过程中的几个关键问题163.1.1设备死锁现象16363.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附录33361绪论1.1课题来源随着加入WTO，市场竞争越来越激烈，对制造企业来说，为了能够在竞争中立于不败，降低成本是不得不面临的问题，而确保生产车间较高的生产能力和效率，是当务之急。此外，有效的调度方法已经成为先进制造技术实践的基础和关

3、键，所以对它的研究具有重要的理论和实用价值。当前科学技术正进入多学科互相交叉、互相渗透、互相影响的时代，生命科学与工程科学的交叉、渗透和相互促进是其中一个典型例子，也是近代科学技术发展的一个显著特点。遗传算法的蓬勃发展正体现了科学发展的这一特点和趋势。所谓生产调度，即对生产过程进行作业计划，作为一个关键模块，是整个先进生产制造系统实现管理技术、运筹方法、优化技术、自动化与计算机技术发展的核心，有效的调度方法和优化技术的研究与应用，是实现先进制造和提高生产效益的基础和关键。虽然对其研究已有几十年的历史但至今尚未形成一套系统的方法和理论，理论研究与实际应用之间还存在着较大距离。目前的调度算法大多只

4、关心工件的调度问题，而对其它资源分配问题则研究相对不多，将二者结合起来研究应该是值得注意的问题，目前已有不少学者开始关注该问题。由于一般车间调度问题的复杂性，各种不同的具体问题往往有许多不同的算法来解决，例如经典的启发式算法，传统的搜索方法等。由于遗传算法是一种借鉴生物界自然选择和进化机制发展起来的高度并行、随机、自适应搜索算法［1］。它特别适合于处理传统搜索算法解决不好的复杂和非线性问题。一些学者们经过大量的实践证明了遗传算法在解决作业车间调度问题上比经典的启发式算法好，同时遗传算法比传统的搜索技术有更强的优越性，因为它不仅能解决某一特定问题，而且可以适应不同的问题形式［2］。1.2作业车间

5、调度问题表述作业车间调度（job-shop）问题可以表述为：设有N个工件在M台机器上加工，根据工件加工工艺的要求，每个工件使用机器的顺序及其每道工序所花时间已给定，调度问题的目标就是如何选择加工顺序使得总的加工时间最短最优。前提假设［3］：361.每一台机器每次只能加工一个工件，每一个工件在机器上的加工被成为一道工序。2.不同工件的加工工序可以不同；3.所有工件的工序数不大于设备数；4.每道工序必须在指定的某种设备上加工；5.任何作业没有抢先加工的优先权；6.在作业优化过程中既没有新的工件加入也没有取消的工件；调度问题具有相当的难度，目前调度问题的理论研究成果主要在job-shop问题为代表的

6、基于最小完工时间的调度问题上。求解调度问题的方法称为调度优化算法。它可分为精确求解方法和近视求解方法。其中精确求解方法包括解析方法、穷举方法（包括分支定界）等；近似求解方法包括基于规则的构造性方法、邻域搜索算法（如进化遗传算法，模拟退火算法）以及人工智能方法（如神经网络）［4］等。而传统的运筹学方法，即便在较大规模的基于单目标优化的静态调度问题中也难以有效应用。本文从实际和理论两方面进行研究和深入，重点研究了现代进化算法中有代表性发展优势的遗传算法。车间作业是指利用车间资源(如机床、刀具、夹具等)完成的某项任务。在实际生产中，这项任务可能是装配一种产品，也可能是完成一批工件的加工。而在本文中，

7、为了研究方便，我们将这项任务限定为加工一批工件。在此基础上，可对车间作业调度问题进行一般性的描述:假定有多个工件，要经过多台机器加工。一个工件在一台机器上的加工程序称为一道“工序”，相应的加工时间称为该工序的“加工时间”。用事先给定的“加工路线”表示工件加工时技术上的约束，即工件的加工工艺过程。用“加工顺序”表示各台机器上各个工件加工的先后顺序。车间作业调度问题中，每个工件都有独特的加工路线［5］