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

基于遗传算法求解作业车间调度问题毕业论文 目 录 摘 要 I Abstract II 1 绪论 1 1.1 课题来源 1 1.2 作业车间调度问题表述 1 1.3 车间作业调度问题研究的假设条件及数学模型 2 1.3.1 车间作业调度问题研究的假设条件 2 1.3.2 车间作业调度问题的数学模型 3 1.4 课题研究内容及结构安排 4 2 遗传算法相关理论与实现技术 6 2.1 自然进化与遗传算法 6 2.2 基本遗传算法 7 2.2.1 遗传算法的基本思路 7 2.2.2 遗传算法的模式定理 7 2.2.3 遗传算法的收敛性分析 9 2.2.4 基本遗传算法参数说明 10 2.3 遗传算法的优缺点 11 2.3.1 遗传算法的优点 11 2.3.2 遗传算法的缺点 11 2.4 遗传算法的进展 12 2.5 小结 15 3 用遗传算法对具体问题的解决与探讨 16 3.1 研究过程中的几个关键问题 16 3.1.1 设备死锁现象 16 3.1.2 参数编码 16 3.1.3 初始种群的生成 19 3.1.4 个体的适应度函数 20 3.1.5 算法参数 20 3.1.6 遗传算子的设计 21 3.2 遗传算法终止条件 24 3.3 遗传算法解决车间调度问题的改进 24 3.4 系统仿真 24 3.5 小结 29 结 论 30 致 谢 31 参考文献 32 附 录 33 1 绪论 1.1 课题来源 随着加入WTO，市场竞争越来越激烈，对制造企业来说，为了能够在竞争中立于不败，降低成本是不得不面临的问题，而确保生产车间较高的生产能力和效率，是当务之急。此外，有效的调度方法已经成为先进制造技术实践的基础和关键，所以对它的研究具有重要的理论和实用价值。当前科学技术正进入多学科互相交叉、互相渗透、互相影响的时代，生命科学与工程科学的交叉、渗透和相互促进是其中一个典型例子，也是近代科学技术发展的一个显著特点。遗传算法的蓬勃发展正体现了科学发展的这一特点和趋势。 虽然对其研究已有几十年的但至今尚未形成一套系统的方法和理论，理论研究与实际应用之间还存在着较大距离。目前的调度算法大多只关心工件的调度问题，而对其它资源分配问题则研究相对不多，将二者结合起来研究应该是值得注意的问题，目前已有不少学者开始关注该问题。［1］遗传算法比经典的启发式算法好，同时遗传算法比传统的有哪些信誉好的足球投注网站技术更强的性，因为它不仅能解决某一特定问题，而且可以适应不同的问题形式1.2 作业车间调度问题表述 作业车间调度（job-shop）问题可以表述为：设有N个工件在M台机器上加工，根据工件加工工艺的要求，每个工件使用机器的顺序及其每道工序所花时间已给定，调度问题的目标就是如何选择加工顺序使得总的加工时间最短最优。 前提假设［3］： 1. 每一台机器每次只能加工一个工件，每一个工件在机器上的加工被成为一道工序。 2. 不同工件的加工工序可以不同； 3. 所有工件的工序数不大于设备数； 4. 每道工序必须在指定的某种设备上加工； 5. 任何作业没有抢先加工的优先权； 6. 在作业优化过程中既没有新的工件加入也没有取消的工件； 调度问题具有相当的难度，目前调度问题的理论研究成果主要在job-shop问题为代表的基于最小完工时间的调度问题上。 求解调度问题的方法称为调度优化算法。它可分为精确求解方法和近视求解方法。其中精确求解方法包括解析方法、穷举方法（包括分支定界）等；近似求解方法包括基于规则的构造性方法、邻域有哪些信誉好的足球投注网站算法（如进化遗传算法，模拟退火算法）以及人工智能方法（如神经网络）［4］等。而传统的运筹学方法，即便在较大规模的基于单目标优化的静态调度问题中也难以有效应用。本文从实际和理论两方面进行研究和深入，重点研究了现代进化算法中有代表性发展优势的遗传算法。 车间作业是指利用车间资源(如机床、刀具、夹具等)完成的某项任务。在实际生产中，这项任务可能是装配一种产品，也可能是完成一批工件的加工。而在本文中，为了研究方便，我们将这项任务限定为加工一批工件。在此基础上，可对车间作业调度问题进行一般性的描述:假定有多个工件，要经过多台机器加工。一个工件在一台机器上的加工程序称为一道“工序”，相应的加工时间称为该工序的“加工时间”。用事先给定的“加工路线”表示工件加工时技术上的约束，即工件的加工工艺过程。用“加工顺序”表示各台机器上各个工件加工的先后顺序。车间作业调度问题中，每个工件都有独特的加工路线［5］。它所要解决的问题就是确定每台机器上不同工件的加工顺序，以及每个工件的所有工序的起始加工时间，以最优化某个性能指标。 1.3 车间作业调度问题研究的假设条件及数学模型 1.3.1 车间作业调度问题研究的假设条件 在研