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

《基于遗传算法求解作业车间调度问题毕业论文.docx》由会员分享，可在线阅读，更多相关《基于遗传算法求解作业车间调度问题毕业论文.docx（37页珍藏版）》请在第一文库网上搜索。

1、基于遗传算法求解作业车间调度问题毕业论文目录摘要错误!未定义书签。Abstract错误!未定义书签。1绪论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、.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 小结292吉论30致谢错误!未定义书签。参考文献31附录321绪论1.1 课题来源随着加入WTO,市场竞争越来越激烈，对制造企业来说，为了能够在竞争中立于不败，降低成本是不得不面临的问题，而确保

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

4、但至今尚未形成一套系统的方法和理论，理论研究与实际应用之间还存在着较大距离。目前的调度算法大多只关心工件的调度问题，而对其它资源分配问题则研究相对不多，将二者结合起来研究应该是值得注意的问题，目前已有不少学者开始关注该问题。由于一般车间调度问题的复杂性，各种不同的具体问题往往有许多不同的算法来解决，例如经典的启发式算法，传统的搜索方法等。由于遗传算法是一种借鉴生物界自然选择和进化机制发展起来的高度并行、随机、自适应搜索算法。它特别适合于处理传统搜索算法解决不好的复杂和非线性问题。一些学者们经过大量的实践证明了遗传算法在解决作业车间调度问题上比经典的启发式算法好，同时遗传算法比传统的搜索技术有更

5、强的优越性，因为它不仅能解决某一特定问题，而且可以适应不同的问题形式。1.2 作业车间调度问题表述作业车间调度(job-shop)问题可以表述为：设有N个工件在M台机器上加工，根据工件加工工艺的要求，每个工件使用机器的顺序及其每道工序所花时间已给定，调度问题的目标就是如何选择加工顺序使得总的加工时间最短最优。前提假设：1 .每一台机器每次只能加工一个工件，每一个工件在机器上的加工被成为一道工序。2 .不同工件的加工工序可以不同；3 .所有工件的工序数不大于设备数；4 .每道工序必须在指定的某种设备上加工；5 .任何作业没有抢先加工的优先权；6 .在作业优化过程中既没有新的工件加入也没有取消的工

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

7、。在实际生产中，这项任务可能是装配一种产品，也可能是完成一批工件的加工。而在本文中，为了研究方便，我们将这项任务限定为加工一批工件。在此基础上，可对车间作业调度问题进行一般性的描述:假定有多个工件，要经过多台机器加工。一个工件在一台机器上的加工程序称为一道“工序”，相应的加工时间称为该工序的“加工时间用事先给定的“加工路线”表示工件加工时技术上的约束，即工件的加工工艺过程。用“加工顺序”表示各台机器上各个工件加工的先后顺序。车间作业调度问题中，每个工件都有独特的加工路线。它所要解决的问题就是确定每台机器上不同工件的加工顺序，以及每个工件的所有工序的起始加工时间，以最优化某个性能指标。1.3车间

8、作业调度问题研究的假设条件及数学模型1.3.1 车间作业调度问题研究的假设条件在研究一般的车间作业调度问题中往往需要明确两类重要假设条件：1 .工艺路径约束:工件的任一工序必须在其前道工序完成后才能开始，并保证同一工件不会同时在两台机器上加工，反映了工件不同工序间的时序关系;2 .资源（机器）独占性约束:任一台机器每次只能加工一个工件，且一旦开工就不能中断，反映了加工队列中工件间的时序关系。止匕外，还有一些辅助假设条件，如下：1 .各工件经过其准备时间后可开始加工；2 .不考虑工件加工的优先权，即工件之间没有优先约束关系限制的;3 .工序允许等待，即前一个工序未完成，则后面工序需要等待；4 .

9、所有机器处理的加工类型均不同；5 .工件的加工时间事先给定，且在整个加工过程中保持不变；6 .缓冲区容量为无穷大。1.3.2车间作业调度问题的数学模型建立车间作业调度问题的数学模型，是我们研究该问题的出发点，同时也为其后的研究奠定了基础。假设有n个工件，要在m台机器上加工，每个工件有Pi道工序，每台机器上总共要加工Lj道工序。我们定义以下基本数学符号：J:所有工件的集合，J = JJ29-Jn；M:所有机器的集合，M =PjJ工件上的工序集合，P:所有工序的集合，此为xmax伍出，？矩阵。P （i, j）表示i工件的第j道工序。=表示i工件的所有工序按优先顺序的排列。不足max记出那么其空余的

10、位置用0填满。园2乙弓.（叫 E(1.1)乙：机器顺序阵，此为xmax优出，月J矩阵。（i, j）表示i工件的第j道工序的机器号，4亿）表示i工件的所有工序按优先顺序加工的各机器号的排列。注意:如果某工件的工序数不足max/；匕,那么其空余的位置用0填满。4AMp Mp 力I 712人000(1.2)00,V*i-l7Mp Mp M p M p册 I启2 hmv修+1T:加工时间阵,此为xmax匕鸟，匕矩阵。T（i, j）表示工件i的第j道工序在与（i, j）上的加工时间。同样地，如果某工件的工序数不足max几鸟,匕,那么其空余的位置用0填满。(1.3)Mj工件排列阵，此为max匕6,匕x矩阵

11、。M/i, j）表示在i机器上排在第j位加工的工件号，表示i机器上依次加工的各工件的排列。同上，如果某工件的工序数不足max记出，勺，那么其空余的位置用0填满。事实上，工件排列阵就是调度的一种表示形式。由此，我们可以给出一般性的车间作业调度数学模型的定义：如果对应于一个确定的,满足=或JJJJJ/（M；） = max/（M）/（M；）,/（M；）。即M；使得目标函数/（；%）取值最小（或最大），且与人相容，则称例；为车间作业调度问题在此目标函数下的最优解。生产调度问题存在多种优化目标或者综合优化目标，调度问题的优化目标通常从两个方面来考虑:生产成本和生产时间。调度问题从生产成本方面来考虑，其优

12、化目标有:库存最少、在制品最少、设备利用率最高等;从生产时间方面来考虑，其优化目标有:最大程度满足交货期、最小完成时间、最小流动时间和最小等待时间等。两个方向的优化目标之间彼此不是相互孤立的，其中的许多具体目标之间的联系很密切，有的相互促进,有的相互冲突，也有的毫无联系。1.4课题研究内容及结构安排本文共分为三章。第一章简要介绍了车间调度问题和求解调度问题的基本方法；第二章介绍了遗传算法的基本理论；第三章用遗传算法来解决车间调度问题,其中介绍了常用的几种编码方式，在比较的情况下提出本文主要用基于操作的编码方式.还有提出了几种主要的遗传算子。并且以四个工件四个机器问题进行举例,说明了用遗传算法解

13、决车间调度问题的可行性。2遗传算法相关理论与实现技术遗传算法(Genetic Algorithm, GA)是一种基于自然群体遗传演化机制的高效探索算法，它是美国学者Holland于1975年首先提出来的。它摒弃了传统的搜索方式，模拟达尔文的遗传选择和自然淘汰的生物进化过程。它将问题域中的可能解看作是群体的一个个体或染色体，并将每一个体编码成符号串形式，对群体反复进行基于遗传学的操作(遗传，交叉和变异)，根据预定的目标适应度函数对每个个体进行评价，依据适者生存，优胜劣汰的进化规则，不断得到更优的群体，同时以全局并行搜索方式来搜索优化群体中的最优个体，求得满足要求的最优解。2.1 自然进化与遗传算

14、法自从达尔文的进化论得到人们的接受之后，生物学家们就对进化机制产生了极大的兴趣。化石记录表明我们所观察的复杂结构的生命是在相对短的时间进化而来的，对这一点包括生物学家在内的许多人都感到惊奇。虽然目前人们对进化机制在一些方面还没有弄清楚，但它们的一些特征已为人所知。进化是发生在编码染色体上，通过对染色体的译码部分生成生物体，但下面几个关于进化理论的一般特性已被广大人们所接受。1 .进化过程发生在染色体上，而不是发生在它们所编码地生物个体上。2 .自然选择把染色体以及由它们所译成的结构表现联系在一起，哪些适应性好地个体的染色体经常比差的个体的染色体有更多的繁殖机会。3 .繁殖过程是进化发生的那一刻

15、，变异可以使生物体子代的染色体不同于它们父代的染色体，通过结合两个父代染色体的物质，重组过程可以在子代中产生有很大差异的染色体。4 .生物进化没有记忆。有关产生个体的信息包含在个体所携带的染色体的集合以及染色体编码的结构之中，这些个体会很好的适应它们的环境。大多数生物体是通过自然选择和有性生殖这两种基本过程进行演化的。自然选择的原则是适应者生存，不适者淘汰。自然选择决定了群体中那些个个体能存活并繁殖，有性生殖保证了后代基因中的混合与重组。比起那些仅包含单个亲本的基因拷贝和依靠偶然变异来改进的后代，这种由基因重组产生的后代进化要快得多。2.2 基本遗传算法2.2.1 遗传算法的基本思路L首先确定问题的求解空间；2 .