柔性制造系统中机床调度优化研究【28400字】【优秀机械毕业设计论文】

资源目录

柔性制造系统中机床调度优化研究【】【优秀机械毕业设计论文】.rar

设计PPT答辩.ppt---(点击预览)

毕业论文.doc---(点击预览)

开题报告.doc---(点击预览)

外文文献.doc---(点击预览)

中期检查.doc---(点击预览)

压缩包内文档预览：(预览前20页/共21页)

编号：609937 类型：共享资源大小：514.42KB 格式：RAR 上传时间：2016-02-29 上传人：木*** IP属地：江苏

20
积分

版权申诉 word格式文档无特别注明外均可编辑修改；预览文档经过压缩，下载后原文更清晰！ 立即下载

关键词：: 柔性制造系统机床调度优化研究钻研优秀优良机械毕业设计论文

资源描述：

文档包括:
说明书一份，48页，28400字左右。
开题报告一份。
设计PPT答辩一份。
外文文献一份。
中期检查一份。

题目柔性制造系统中机床调度优化研究

目录
第一章绪论 1
1.1 引言 1
1.2课题提出的目的和意义 1
1.3课题相关研究领域的发展状况及趋势 1
1.4 本课题主要研究内容和设计任务 2
第二章调度与遗传算法相关理论 4
2.1调度的定义 4
2.1.1机床调度的定义 4
2.1.2机床主要调度问题 4
2.2调度问题的描述和分类 4
2.3调度的优化算法 5
2.4遗传算法基本理论 7
2.5遗传算法基本概念 8
2.6遗传算法主要步骤 9
2.7适应度函数 9
2.8遗传操作算子 10
2.8.1选择算子 10
2.8.2交叉算子 11
2.8.3 变异算子 12
2.9遗传算法参数的选择 13
2.10 遗传算法的应用与发展趋势 13
第三章基于遗传算法进行机床调度 15
3.1静态车间调度 15
3.2 问题的描述 15
3.3基本遗传算法的构造 15
3.3.1编码 15
3.3.2 解码 16
1 基于机器编码的机器工件队列之间的冲突消解 16
2. 最后解码计算最大调度时间 17
3.4 初始种群的产生 17
3.5 选择操作 17
3.6交叉操作 18
3.7变异操作 18
3.8 动态车间调度 18
3.9动态调度类型 19
3.10动态调度控制方法 20
3.10.1急件到来 20
3.10.2机器故障 22
3.10.3订单取消 24
3.11应用实例 26
第四章C语言相关知识及编程 31
4.1 C语言相关知识 31
4.2 C语言程序的特点 31
4.3 C语言程序的开发步骤 32
4.4 C语言编程 32
4.5 输出结果 37
第五章全文总结与展望 39
5.1全文总结 39
5.2 展望 39
结束语 40
致谢 41
参考文献 42

柔性制造系统中机床调度优化研究
摘要:

随着市场的多变以及市场对产品个性化的需求，多品种、小批量生产方式已经逐渐成为制造业的发展主流。研究批量调度的优化方法，对于先进制造业的现代化具有重要的理论价值和实际意义。
本文介绍了机床调度的概念及其发展过程、研究现状和发展趋势；对车间调度的各种研究方法进行了简要的介绍和比较；概述了遗传算法的基本原理和步骤，介绍了遗传算法常用的一些算子，分析了遗传算法的特点，并对遗传算法的一些理论进行了讨论。
对三种常见的动态事件（急件到来、设备故障、订单取消）的重调度控制方法进行了研究，并在静态调度问题研究的基础上，运用自适应遗传算法对动态调度问题进行了研究，获得了动态调度的控制策略和重调度方法。此控制策略和重调度方法可以较好地解决由于动态事件的出现而导致的静态调度方案不再适用的问题，从而保证了FMS系统在有扰动时也能持续地运行。
关键词：遗传算法,动态调度,柔性制造系统

Flexible manufacturing system in machine tool research on Scheduling Optimization
Abstract：

With much change of the market and the diversification of customer need，variety and small batch production mode has become the main way of manufacturing gradually．The study of optimization method for batch scheduling is very important to modernization of advanced manufacturing because of its theoretical and practical in researches in current and in the future of job shop scheduling are introduced，some research methods are introduced and compared．Basic foundation,process and operations of GA are stated briefly，and the character is ticsander theoretic are discussed．
The re-scheduling control method of three dynamic events （the arrival of new parts , Mechanical failures , canceled orders ) are Studied, and based on the static scheduling problem , the adaptive genetic algorithm is used for the study of dynamic scheduling . In this part , Dynamic Scheduling and Control Strategy are put forward . Application of the control strategies and rescheduling methods can solve the problem that the appear of dynamic events led to static scheduling program is not apply , so ensuring the FMS system can continue to optimize the operation in the case of a disturbance happening.

KEY WORDS: genetic algorithms, workshop scheduling, FMS scheduling,dynamic scheduling

一、选题目的和意义：
“柔性”是指生产组织形式和生产产品及工艺的多样性和可变性，可具体表现为机床的柔性、产品的柔性、加工的柔性、批量的柔性等。柔性制造系统适合于多品种、中小批量生产，可迅速适应产品变化，具有进步设备利用率、减少在制品库存量、进步产品质量和一致性等诸多优点。但是系统的这些优点能否发挥，取决于各生产设备调度后的运行效率情况，如仓库的调度、机床的调度、物料运输车辆的调度等。其中机床的调度优化起到非常关键的作用。机床调度的目的是将工序合理的分配给各机床，并对各机床上的工序进行排序优化以使完成所有工序的时间最小。该调度的评价以目标函数为主，如“最小制造周期”、“机床利用率”、“工件流通时间”等，这些评价参数都对整个生产系统的加工效率具有直接的影响。所以合理的机床调度规则，在时间和空间上可有效利用系统的有限资源，以满足各项生产指标的要求。因此机床调度问题将直接影响系统的有效性和柔性，通过设计适合的调度算法对机床各种工作情况进行实时的调度研究，具有非常现实的意义，它的优化可提高生产任务的加工效率。
二、本课题在国内外的研究状况及发展趋势：
柔性制造系统是70年代末、80年代初出现的一种具有高度柔性的自动化制造系统。随着科学技术的发展，新产品的出现，产品市场寿命也随之缩短，相应的更新换代的速度加快，中小批量生产比例增加，以这种生产方式生产的产品占制造业总值的70%，其中采用优化调度的方法可提高30%的生产效率。尤其是近年来，国外一些工业技术比较发达的国家为进一步提高劳动生产率，降低生产成本，缩短产品的生产周期以增强产品更新换代和产品市场竞争力，所以柔性制造企业对调度优化的要求越来越高，由此带动的学术界对该问题的研究也越来越多。
由于调度问题的复杂性，不同的研究者提出不同的算法和优化过程，最初是集中在整数规划，仿真和简单的规则上，随着各种新的交叉学科和优化技术的建立和发展，出现了很多智能调度优化的方法，如神经网络，模拟退火法，遗传算法，禁忌搜索法等，使调度问题的方向向多元化方向发展。
在未来的发展中，如何在先进的柔性制造系统中实现各生产环节调度的实时性和高效性，确定简洁实用的算法将是重中之重。目前对物料运送车辆AGV的调度和对仓库的调度的研究非常多，而机床的调度相对薄弱，主要是通过一些经典的排队算法的简单应用。但机床在整个加工环节对整个系统效率的影响又是最大的，所以本课题将寻找简单、实用、可行的一种调度算法以提高系统的加工效率。

三、主要研究内容：
1．确定方案：了解柔性制造系统的工作原理及主要功能，提出该系统下机床优化调度设计方案；
2．算法分析：根据系统功能，选择合适的算法，实现机床的优化调度。
3．系统设计：用仿真软件实现对具体的算法仿真验证。
4. 完成毕业论文的撰写。

内容简介：: 西安文理学院本科毕业设计（论文）中期检查表题目柔性制造系统中机床调度优化研究学生姓名王磊学号 08102080225 专业名称机械设计制造及其自动化指导教师边培莹、吕荣生检查时间 2011 级 08 机械 2 班毕业设计（论文）进展情况通过对柔性制造系统中机床调度优化研究的相关资料的学习，以及对整个设计的了解，现基本完成以下设计工作：床调度优化目标的总结与分析。基本了解实现机床调度优化的算法。方案，以及具体采用的调度优化算法。遗传算法进行深入学习，并学习 C+的相关知识。 4. 初步确定了论文的提纲和核心下一步设计工作内容是通过采用遗传算法实现对机床的调度优化，并利用 C+软件仿真得出结果。以及毕业论文的撰写。指导教师意见自开题以来，通过查阅资料并积极与老师的沟通，该生比较清楚自己的设计内容和技术路线，能按计划、分步骤的展开设计任务，并能按时接受指导，有问题随时联系老师，保持了良好的指导关系。基本达到了上述设计进展。签字：年月日教研室意见签字：年月日一种新的改进遗传算法及其性能分析摘要：虽然遗传算法以其全局搜索、并行计算、更好的健壮性以及在进化过程中不需要求导而著称，但是它仍然有一定的缺陷，比如收敛速度慢。本文根据几个基本定理，提出了一种使用变异染色体长度和交叉变异概率的改进遗传算法，它的主要思想是：在进化的开始阶段，我们使用短一些的变异染色体长度和高一些的交叉变异概率来解决，在全局最优解附近，使用长一些的变异染色体长度和低一些的交叉变异概率。最后，一些关键功能的测试表明，我们的解决方案可以显著提高遗传算法的收敛速度，其综合性能优于只保留最佳个体的遗传算法。关键字：编译染色体长度；变异概率；遗传算法；在线离线性能遗传算法是一种以自然界进化中的选择和繁殖机制为基础的自适应的搜索技术，它是由975 年首先提出的。它以其全局搜索、并行计算、更好的健壮性以及在进化过程中不需要求导而著称。然而它也有一些缺点，如本地搜索不佳，过早收敛，以及收敛速度慢。近些年，这个问题被广泛地进行了研究。本文提出了一种使用变异染色体长度和交叉变异概率的改进遗传算法。一些关键功能的测试表明，我们的解决方案可以显著提高遗传算法的收敛速度，其综合性能优于只保留最佳个体的遗传算法。在第一部分，提出了我们的新算法。第二部分，通过几个优化例子，将该算法和只保留最佳个体的遗传算法进行了效率的比较。第三部分，就是所得出的结论。最后，相关定理的证明过程可见附录。 1. 算法的描述些定理在提出我们的算法之前，先给出一个一般性的定理（见附件），如下：我们假设有一个变量（多变量可以拆分成多个部分，每一部分是一个变量） x a, b , x R，二进制的染色体编码是 1. 定理 1 染色体的最小分辨率是 s = 定理 2 染色体的第 ( i = 1,2, l ) 定理 3 单点交叉的染色体搜索步骤的数学期望 Ec(x)是 x) = 中定理 4 位变异的染色体搜索步骤的数学期望 Em(x)是 x ) = ( b- a) 中法机制在进化过程中，我们假设变量的值域是固定的，交叉的概率是一个常数，所以从定理 1 和定理 3我们知道，较长的染色体长度有着较少的染色体搜索步骤和较高的分辨率；反之亦然。同时，交叉概率与搜索步骤成正比。由定理 4，改变染色体的长度不影响变异的搜索步骤，而变异概率与搜索步骤也是成正比的。进化的开始阶段，较短染色体（可以是过短，否则它不利于种群多样性）和较高的交叉和变异概率会增加搜索步骤，这样可进行更大的域名搜索，避免陷入局部最优。而全局最优的附近，较长染色体和较低的交叉和变异概率会减少搜索的步骤，较长的染色体也提高了变异分辨率，避免在全局最优解附近徘徊，提高了算法收敛速度。最后，应当指出，染色体长度的改变不会使个体适应性改变，因此它不影响选择（轮盘赌选择）。法描述由于基本遗传算法没有在全局优化时收敛，而遗传算法保留了当前一代的最佳个体，我们的方法采用这项策略。在进化过程中，我们跟踪到当代个体平均适应度的累计值。它被写成： X(t) = (t) 其中当累计平均适用性增加到最初个体平均适应度的 k ( k 1, k R) 倍，我们将染色体长度变为其自身的 m (m 是一个正整数 ) 倍，然后减小交叉和变异的概率，可以提高个体分辨率、减少搜索步骤以及提高算法收敛速度。算法的执行步骤如下：第一步：初始化群体，并计算个体平均适应度后设置改变参数的标志 . 第二步：在所保留的当代的最佳个体，进行选择、再生、交叉和变异，并计算当代个体的累积平均适应度三步：如果且 1，把染色体的长度增加至自身的 m 倍，减少交叉和变异概率，并设置于 0;否则继续进化。第四步：如果满足结束条件，停止；否则转自第二步。 2. 测试和分析我们采用以下两种方法来测试我们的方法，和只保留最佳个体的遗传算法进行比较：敛的分析在功能测试中，我们进行了以下政策：轮盘赌选择，单点交叉，位变异。种群的规模是 60。 L 是染色体长度，们随机选择 4 个遗传算法所保留的最佳个体来与我们的方法进行比较，它们具有不同的固定染色体长度和交叉和变异的概率。表 1 给出了在 100 次测试的平均收敛代。在我们的方法中，我们采取的初始参数是 10， k = 满足改变参数的条件时，我们调整参数 l = 30，从表 1 中得知，我们的方法显著提高了遗传算法的收敛速度，正符合上述分析。表 1 功能测试结果方法我们的算法 l=10 m=0.1 l=10 m=0.1 l=30 m=0.1 l=30 m=0.1 57 15236 35791 1626 4363 98 26973 42374 450 5433 线和离线性能的分析出了遗传算法的定量评价方法，包括在线和离线性能评价。前者测试动态性能，而后者评估收敛性能。为了更好地分析测试功能的在线和离线性能，我们把个体的适应性乘以 10，并别给出了 4 000 和 1 000 代的曲线： (a) 在线 (b) 离线图 1 (a) 在线 (b) 离线图 2 从图 1和图 2可以看出，我们方法的在线性能只比第四种情况差一点点，但比第二种、第三种、第五种好很多，这几种情况下的在线性能几乎完全相同。同时，我们方法的离线性能也比其他四种好很多。 3. 结论本文提出了一种使用变异染色体长度和交叉变异概率的改进遗传算法。一些关键功能的测试表明，我们的解决方案可以显著提高遗传算法的收敛速度，其综合性能优于只保留最佳个体的遗传算法。附件有了第一部分中假定的条件，定理 1 和定理 2 的验证是显而易见的。下面给出定理 3和定理 4的证明过程：定理 3 单点交叉的染色体搜索步骤的数学期望 Ec(x)是 x) = 中证明：如图示，我们假设交叉发生在第 k 个基因位点，从 k到 l 的父基因位点没有变化，基因位点 1 到 k 上的基因改变了。在交叉过程中， 1 到 k 基因位点上的基因改变的概率为 1”变化 ”0”或者 ”0”变为 ”1”)，因此，交叉之后，基因位点上的染色体搜索步骤从 1到 k 的数学期望是此外，每个位点的染色体发生交叉的概率是相等的，即叉后，染色体搜索步骤的数学期望是把 ( 换为 ( 我们得到其中 l 是非常大的，，所以图 1 单点交叉定理 4 位变异的染色体搜索步骤的数学期望是其中证明：每个基因位点上的基因的变异概率是相等的，比如此变异搜索步骤的数学期望是：参考 1 自适应变异概率的遗传算法以及其性能分析 . J. 1999, 27( 5) : 89 2. 2 基于大规模的分布式系统损失最小化的改进遗传算法 . A. 进化计算议 C . 1995: 120 25. 3 一种改进的遗传算法以及它在 E 计划波导过滤器设计重点额应用 J . 2000, 28( 6) : 12124. 4 T J . 应用智能 , 2000, 12: 163 81. 5 . 经典遗传算法的收敛分析 . J . 基于神经网络的 1994, 5( 1) : 96 01. it as In on an of is is as at of of at of of of is of is an on a in it in 970s. It it as as as In In an is it is of In , is in , of is of in 1 of we as us is be x a, b , x R, . of is s = of of ( i = 1,2, l ) c(x) of c (x) = Pc c is of x ) of m ( x ) = ( b- a) Pm m is of 1. 2 of we of of is a so , we of is in to , of of is in to At of be it is to of at of of of up it be it . 1. 3 of to on at we of up to It is (t) = (t) is is to k k 1, k R) of we to m m is a of of up is as . on of of up to ; k , to m of of ; If is go . 2 e to it 2. 1 of we of 0, l is m of we of to 1 00 In we 10, 0.1 k= is we to l= 30, 1, we of it of ur l=10 m=0.1 l=10 m=0.1 l=30 m=0.1 l=30 m=0.1 57 15236 35791 1626 4363 98 26973 42374 450 5433 2. 2 of of To of w e of 0, we a 000 000 f1 (a) (b) 1 of a) (b) 2 of 1 2, we of is of it is of At of is of 3 n on an of is it of is of of , we c(x) of c(x) = c is of As we on i. e. s k to l do on to k of on to k (“1” 0” 0” 1”). of on to k of on of is of q. ( q. ( , we l is , ne of m is of of on of is m, of 1 of J . 1999, 27( 5) : 89 2. 2 A . of C . 1995: 120 25. 3 An it s J . 2000, 28( 6) : 121 24. 4 T of in As J . 2000, 12: 163 5 . of J . 1994, 5( 1) : 96 01. 西安文理学院机械电子工程系本科毕业设计（论文）题目柔性制造系统中机床调度优化研究专业班级 08 级机械（ 2）班学号 08102080225 学生姓名王磊指导教师边培莹吕荣生设计所在单位西安文理学院 2012 年 5 月西安文理学院本科毕业设计（论文）任务书题目柔性制造系统中机床调度优化研究学生姓名王磊学号 08102080225 专业班级 08 级机械 (2)班指导教师边培莹、吕荣生职称助教、副教授教研室机械毕业设计（论文）任务与要求 1 在柔性生产方式下，机床设备的调度对生产效率的影响非常大，设计适合的调度算法对机床各种工作情况进行实时的调度，以优化提高生产任务的加工效率； 2 设计要求：分析机床的各种主要工作情况及设备状态，对应的设计调度算法，要有评价方法对调度效果作出评价； 3 开题报告及中期检查各一份； 4 利用仿真软件进行算法优化的仿真论证或寻找其他的论证方法； 5 撰写毕业论文，包括文献综述（另翻译英文资料一份）及主要仿真结果说明等；毕业设计（论文）工作进程起止时间工作内容析任务书，了解所选课题，选择相应期刊及论文资料，制定开题报告。研究学习各种调度优化算法工作原理、及仿真软件的编程语言（如语言），并提出该机床的调度方案。进行详细调度优化算法的设计并论证其合理性。进一步对确定的方案进行设计，并编制仿真程序。完成毕业设计论文的撰写、整理工作。开始日期 2012 完成日期 2012 教研室主任（签字）系主任（签字）西安文理学院本科毕业设计（论文）开题报告题目柔性制造系统中机床调度优化研究学生姓名王磊学号 08102080225 专业名称机械设计制造及其自动化指导教师边培莹、吕荣生开题时间 2012 级 08 机电（ 2）班一、选题目的和意义： “ 柔性 ” 是指生产组织形式和生产产品及工艺的多样性和可变性，可具体表现为机床的柔性、产品的柔性、加工的柔性、批量的柔性等。柔性制造系统适合于多品种、中小批量生产，可迅速适应产品变化，具有进步设备利用率、减少在制品库存量、进步产品质量和一致性等诸多优点。但是系统的这些优点能否发挥，取决于各生产设备调度后的运行效率情况，如仓库的调度、机床的调度、物料运输车辆的调度等。其中机床的调度优化起到非常关键的作用。机床调度的目的是将工序合理的分配给各机床，并对各机床上的工序进行排序优化以使完成所有工序的时间最小。该调度的评价以目标函数为主，如 “ 最小制造周期 ”、“ 机床利用率 ”、“ 工件流通时间 ” 等，这些评价参数都对整个生产系统的加工效率具有直接的影响。所以合理的机床调度规则，在时间和空间上可有效利用系统的有限资源，以满足各项生产指标的要求。因此机床调度问题将直接影响系统的有效性和柔性，通过设计适合的调度算法对机床各种工作情况进行实时的调度研究，具有非常现实的意义，它的优化可提高生产任务的加工效率。二、本课题在国内外的研究状况及发展趋势：柔性制造系统是 70年代末、 80年代初出现的一种具有高度柔性的自动化制造系统。随着科学技术的发展，新产品的出现，产品市场寿命也随之缩短，相应的更新换代的速度加快，中小批量生产比例增加，以这种生产方式生产的产品占制造业总值的 70%，其中采用优化调度的方法可提高 30%的生产效率。尤其是近年来，国外一些工业技术比较发达的国家为进一步提高劳动生产率，降低生产成本，缩短产品的生产周期以增强产品更新换代和产品市场竞争力，所以柔性制造企业对调度优化的要求越来越高，由此带动的学术界对该问题的研究也越来越多。由于调度问题的复杂性，不同的研究者提出不同的算法和优化过程，最初是集中在整数规划，仿真和简单的规则上，随着各种新的交叉学科和优化技术的建立和发展，出现了很多智能调度优化的方法，如神经网络，模拟退火法，遗传算法，禁忌搜索法等，使调度问题的方向向多元化方向发展。在未来的发展中，如何在先进的柔性制造系统中实现各生产环节调度的实时性和高效性，确定简洁实用的算法将是重中之重。目前对物料运送车辆机床的调度相对薄弱，主要是通过一些经典的排队算法的简单应用。但机床在整个加工环节对整个系统效率的影响又是最大的，所以本课题将寻找简单、实用、可行的一种调度算法以提高系统的加工效率。三、主要研究内容： 1 确定方案：了解柔性制造系统的工作原理及主要功能，提出该系统下机床优化调度设计方案； 2 算法分析：根据系统功能，选择合适的算法，实现机床的优化调度。 3 系统设计：用仿真软件实现对具体的算法仿真验证。 4. 完成毕业论文的撰写。指导教师意见及建议：王磊同学能较认真的查阅本毕业设计课题相关的参考资料与相关文献，对所设计的机床调度问题发展现状清楚、调度方案思路清晰，也积极展开了相关软件的学习。同意开题！签字：年月日教研室审核意见：签字：年月日注：此表前三项由学生填写后，交指导教师签署意见，经教研室审批后，才能开题。西安文理学院机械电子工程系本科毕业设计（论文）题目柔性制造系统中机床调度优化研究专业班级 08 级机械（ 2）班学号 08102080225 学生姓名王磊指导教师边培莹吕荣生设计所在单位西安文理学院 2012 年 5 月 2 目录第一章绪论 . 1 言 . 1 . 1 关研究领域的发展状况及趋势 . 1 课题主要研究内容和设计任务 . 2 第二章调度与遗传算法相关理论 . 4 . 4 床调度的定义 . 4 床主要调度问题 . 4 . 4 . 5 本理论 . 7 本概念 . 8 要步骤 . 9 . 9 . 10 择算子 . 10 叉算子 . 11 异算子 . 12 . 13 遗传算法的应用与发展趋势 . 13 第三章基于遗传算法进行机床调度 . 15 . 15 题的描述 . 15 . 15 码 . 15 码 . 16 1 基于机器编码的机器工件队列之间的冲突消解 . 16 2. 最后解码计算最大调度时间 . 17 始种群的产生 . 17 择操作 . 17 . 18 . 18 态车间调度 . 18 . 19 . 20 件到来 . 20 器故障 . 22 单取消 . 24 . 26 第四章 C 语言相关知识及编程 . 31 3 语言相关知识 . 31 语言程序的特点 . 31 语言程序的开发步骤 . 32 语言编程 . 32 出结果 . 37 第五章全文总结与展望 . 39 . 39 望 . 39 结束语 . 40 致谢 . 41 参考文献 . 42 柔性制造系统中机床调度优化研究摘要 : 随着市场的多变以及市场对产品个性化的需求，多品种、小批量生产方式已经逐渐成为制造业的发展主流。研究批量调度的优化方法，对于先进制造业的现代化具有重要的理论价值和实际意义。本文介绍了机床调度的概念及其发展过程、研究现状和发展趋势；对车间调度的各种研究方法进行了简要的介绍和比较；概述了遗传算法的基本原理和步骤，介绍了遗传算法常用的一些算子，分析了遗传算法的特点，并对遗传算法的一些理论进行了讨论。对三种常见的动态事件（急件到来、设备故障、订单取消）的重调度控制方法进行了研究，并在静态调度问题研究的基础上，运用自适应遗传算法对动态调度问题进行了研究，获得了动态调度的控制策略和重调度方法。此控制策略和重调度方法可以较好地解决由于动态事件的出现而导致的静态调度方案不再适用的问题，从而保证了关键词：遗传算法 ,动态调度 ,柔性制造系统 2 in of of of of is to of of in in in of A is on is of In of of to is so MS to in of a 1 第一章绪论言近一世纪以来，企业所处的环境经历了巨大的变化。 20 世纪初期，现代企业处于刚刚起步的阶段，生产规模尚未达到一定的程度，产品处于供不应求阶段，企业只要保障生产能力和基本产品质量即可。但从 70 年代开始，企业所面临的环境发生了极大的变化，主要体现在： 1市场需求的改变： 20世纪 50年代以后，全球制造业生产能力不断扩大，生产规模和效率迅速提高。进入 70 年代，世界主要市场开始进入需求导向的时代。消费观念也出现了结构性变化，消费需求趋向多样化和个性化。 20世纪 90年代，产品的销售半径不断增大，制造商必须面对处于不同地域、不同文化和不同环境下的全球用户。进入 21世纪，全球市场需求的多样化趋势更加明显，制造业面临全球性多样化、个性化需求的挑战。 2技术的不断创新：科学技术日新月异，以信息技术、自动化技术、现代管理与制造技术相结合的先进制造技术应运而生。 3全球化的竞争：随着科技的发展和全球贸易的提出，生产和销售已经变得的没有国界。这种情况，加剧了企业之间的竞争，对产品的生产提出了更高的要求。题提出的目的和意义 “ 柔性 ” 是指生产组织形式和生产产品及工艺的多样性和可变性，可具体表现为机床的柔性、产品的柔性、加工的柔性、批量的柔性等。柔性制造系统适合于多品种、中小批量生产，可迅速适应产品变化，具有进步设备利用率、减少在制品库存量、进步产品质量和一致性等诸多优点 1、 2。但是系统的这些优点能否发挥，取决于各生产设备调度后的运行效率情况，如仓库的调度、机床的调度、物料运输车辆的调度等。其中机床的调度优化起到非常关键的作用。机床调度的目的是将工序合理的分配给各机床，并对各机床上的工序进行排序优化以使完成所有工序的时间最小。该调度的评价以目标函数为主，如 “ 最小制造周期 ” 、“ 机床利用率 ”、“ 工件流通时间 ” 等，这些评价参数都对整个生产系统的加工效率具有直接的影响。所以合理的机床调度规则，在时间和空间上可有效利用系统的有限资源，以满足各项生产指标的要求。因此机床调度问题将直接影响系统的有效性和柔性，通过设计适合的调度算法对机床各种工作情况进行实时的调度研究，具有非常现实的意义，它的优化可提高生产任务的加工效率。本文主要针对机加工车间加工机床的调度问题进行研究，并运用经典调度算法进行优化，寻求最佳加工路径。题相关研究领域的发展状况及趋势 20 世纪 50 年代调度问题受到了应用数学、运筹学、工程技术等多个领域学者的关注，并运用运筹学中的线性规划、动态规划及决策分析等方法，研究和解决了一系列具有代表意义的调度和优化问题。柔性制造系统是 70年代末、 80年代初出现的一种具有高度柔性的自动化制造系统。随着科学技术的发展，新产品的出现，产品市场寿命也随之缩短，相应 2 的更新换代的速度加快，中小批量生产比例增加，以这种生产方式生产的产品占制造业总值的 70%，其中采用优化调度的方法可提高 30%的生产效率 3、 4、 5。尤其是近年来，国外一些工业技术比较发达的国家为进一步提高劳动生产率，降低生产成本，缩短产品的生产周期以增强产品更新换代和产品市场竞争力，所以柔性制造企业对调度优化的要求越来越高，由此带动的学术界对该问题的研究也越来越多。由于调度问题的复杂性，不同的研究者提出不同的算法和优化过程，最初是集中在整数规划，仿真和简单的规则上，随着各种新的交叉学科和优化技术的建立和发展，出现了很多智能调度优化的方法，如神经网络，模拟退火法，遗传算法，禁忌搜索法等，使调度问题的方向向多元化方向发展 6。在未来的发展中，如何在先进的柔性制造系统中实现各生产环节调度的实时性和高效性，确定简洁实用的算法将是重中之重。目前对物料运送车辆机床的调度相对薄弱，主要是通过一些经典的排队算法的简单应用。但机床在整个加工环节对整个系统效率的影响又是最大的，所以本课题将寻找简单、实用、可行的一种调度算法以提高系统的加工效率。为解决存在的问题，对调度问题的研究主要有以下几种发展趋势：（ 1）调度算法和调度系统的深入研究和开发：目前对调度算法和调度系统的研究己取得很大进展，但由于调度问题的性质而不可能在短期内取得突破性进展，这就要求人们进一步拓宽研究范围和思路，在原来调度算法的基础上继续寻找可行的能够获得最优解而且求解速度快的调度算法。基于人工智能、计算智能和实时智能的调度算法将会是未来调度算法的主流 7。（ 2）调度专家的作用问题研究：调度专家具有丰富的经验，纯粹的自动调度是不现实且很难实现的。因此，具有最终决策职责的调度专家的重要作用在任何时候都不能忽略。所以研究调度专家的作用以及如何与调度系统的协调等问题也是一个重要的研究方向。（ 3）多种调度方法的结合研究：目前许多新的算法应用于调度领域，但由于需要特定的应用环境 ,所以就出现了调度理论和实践的不一致性 8、 9。因此 ,集成各种调度算法求解生产调度问题充分发挥各种调度算法自身的优势，是今后研究和解决实际调度问题的重要方向之一 10、 11。总之，车间调度领域的研究，随着科学的进一步发展，必然朝着集成化、柔性化，多标准化、动态实用化高层次优化方向发展。课题主要研究内容和设计任务本课题主要是运用生产调度相关知识来解决机加工车间的机床调度优化问题。本课题的设计任务是：分析机床的各种主要工作情况及设备状态，对应的设计调度算法，要有评价方法对调度效果作出评价；利用仿真软件进行算法优化的仿真论证或寻找其他的论证方法。本文的主要内容是 :主要针对机床调度问题的调度方法进行研究，并运用遗传算法对调度问题进行优化，寻求最佳调度方案。本文共分五章：第一章首先提出通过引言提出课题研究的目的和意义；然后进一步介绍了机床调度问题的研究现状，研究方法，存在的问题及发展趋势；最后给出课题的主要工作及内容。第二章首先阐述了调度的相关理论；然后对调度问题进行分类和总结其特点，说明在实际调度问题中需要调度的方面；其次对调度算法进行归类，并分别 3 描述各算法的基本思想和特点。根据调度问题选择遗传算法，并对遗传算法的基本理论和操作步骤进行描述。为下文的实例做理论铺垫。第三章依据上述的调度和遗传算法基本理论，分静态和动态分别应用遗传算法进行调度，并给出实例。第四章给出基于遗传算法进行调度的实例 ,并根据所给的实例进行编程，验证算法的可行性和调度后起到的优化作用。第五章结论与展望 4 第二章调度与遗传算法相关理论度的定义床调度的定义机床调度可以描述为若干个任务在一些机器上进行加工，如何按时间对机器和工序等进行安排，使某些目标函数，例如产品制造时间或者成本等达到最优。在一定的约束条件下，调度的目标是将生产合理地安排到各机床，并合理安排作业的加工次序和加工开始时间，同时优化一些性能指标 12。机床调度目标是在满足系统约束条件下，依据反映了客户需求和市场需求的生产计划合理安排各加工任务的实施时间及使用的设备，为生产线上的各台设备和各个工件形成可行的加工安排，并尽可能优化系统的性能指标，最佳地安排与组织生产，为企业带来显著的经济效益。床主要调度问题机床调度问题一般可以描述为 :n 个工件在 m 台机器上加工，一个工件 k 道工序，每道工序可以在若干台机器上加工。每台机器在每个时刻只能加工某个工件的某道工序，而且只能在上道工序加工完成后才能开始下一道工序的加工 12。机床调度问题是根据加工对象的加工需求，运用不同的调度决策规则和优化算法，规划系统的加工事件，并根据系统动态仿真运行的结果或者优化结果形成最佳的生产加工顺序，同时实现设备集和任务集的合理最优化结合。调度的特点是多个工件在有限的机器上加工，每台机器在切换不同的工件生产时需要一定的准备时间。调度的决策内容包括分配决策 (工件的加工顺序 )和时间决策 (工件各工序的加工时间 )以及路径决策 (工件各工序的加工设备的分配 )。度问题的描述和分类生产调度问题是一类典型的实际调度问题，它很早就受到了生产管理者们的关注，但那时还没有进入到理论研究的阶段，只是一些简单的思想，也没有被广泛的应用到实际中。那时人们主要关注的问题是如何分配工作以及哪些操作者能够胜任这样的工作。起初人们主要从应用数学的角度来研究调度问题，调度问题通常被定义为：“对一种资源进行分配来执行一种任务”，也就是对零件进行“排序（的问题。如出了使用可视化的图标来表示生产的进度状况，述了一种机械的调度技术。而在后来的生产中，针对先进制造系统，调度问题被更为具体地定义为：“生产调度是针对一项可分解的生产任务 ,探讨在尽可能满足约束条件的前提下 ,通过下达生产指令 ,安排其组成部分使用哪些资源、其加工时间以及加工顺序 ,以获得生产任务执行时间或成本的最优化6 。所以车间调度就是在一定条件下，对一个可用的加工设备集，在时间上进行加工任务分配，以满足某个给定的性能指标。 (1)根据加工任务，可将调度分为静态调度和动态调度。静态调度是指所有待安 5 排加工的工件均处于待加工状态，因而进行一次调度后，各作业的加工被确定，在以后的加工过程中就不再改变；动态调度是指作业依次进入待加工状态，各种作业不断进入系统接受加工，同时完成加工的作业又不断离开，还要考虑作业环境中不断出现的不可预测的动态扰动，如作业加工超时、设备损坏等。实际生产调度问题往往是由其体现的特征是随机性的、动态的 13。 (2)根据零件和车间构成不同进行分类有 : （ a）单机车间调度问题加工系统中只有一台机床，所有零件都在该机床上进行加工，待加工的零件有且只有一道工序。一般来说，此问题是最简单的调度问题。（ b）并行机车间调度问题加工系统中所有的加工机床是完全相同的，工件可以在任意一台机床上进行加工，并且每个工件只有一道工序。（ c）开放车间调度问题工件的加工没有特定的路线约束，每个工序之间没有先后关系的约束。每个零件工序之间的加工顺序是任意的。零件的加工可以从任何一道工序开始，在任何一道工序结束。（ d）流水车间调度问题加工系统中有一组功能不同的机床，待加工的零件包含多道工序，每道工序在一台机床上加工，所有零件的加工路线都是相同的。每个工件的工序之间有先后顺序约束关系。（ e）作业车间调度问题加工系统中有一组功能不同的机床，待加工的零件包含多道工序，每道工序在一台机床上加工，零件的加工路线互不相同。每个工件工序之间有先后顺序约束，不同工件 (3)根据性能指标可以分为基于调度费用和调度性能的指标。 (4)根据生产环境的特点将调度问题分为确定性调度、随机性调度。 (5)根据作业的加工特点分为静态调度、动态调度。静态调度是指所有的加工的作业都处于待加工状态，因此进行一次调度后所有作业的各个加工都被确定下来，而且在以后的加工过程中不再改变；动态调度是指作业依次进入系统进行加工。完成加工的作业一次离开，同时还要考虑实际加工环境中不断出现的动态扰动，如作业的加工超时、机床损坏等。因此动态调度要根据系统中作业、机床等状况不断地进行重调度。本文在机加工车间环境下，在考虑机床一种资源的情况下，主要针对单件、小批量生产车间如何安排零件在机床上的加工顺序的调度问题进行研究，同时考虑实际生产中的约束条件和优化目标的限制，使得系统能够高效、优化地运行，以确保生产的最大利润。度的优化算法调度问题的研究方法，最初是集中在整数规划、仿真和简单的规则上，这些方法一般都存在一定的局限性，不是调度结果不理想就是难以解决复杂问题。随着各种新的相关学科与优化技术的建立与发展，在调度领域出现了许多新的优化方法，比如神经网络、模拟退火算法、遗传算法、禁忌搜索法等，使得调度问题的研究方法向多元化方向发展。总结起来，现有调度问题的研究方法大体上可以分为以下几种类别： 6 （ 1）数学规划方法：即运筹学（法，将生产调度问题简化为数学规划模型，采用基于枚举思想的分枝定界法解决调度最优化或近似优化问题，属于精确方法。这类方法虽然从理论上能求得最优解，但由于其计算复杂的原因而难以真正实用。对于复杂调度问题，这种纯数学方法由于存在模型提取困难、运算量大、算法难以实现的弱点，仅适合较小规模的调度问题 15。（ 2）基于启发式规则的调度方法：从实用角度来看，启发式算法因其易于实现、计算复杂度低等原因，在实际中得到了比较广泛的应用，并且不断涌现出许多新的调度规则，可将其分为三类 :简单规则、复杂规则、启发式规则。虽然启发式规则常被用于实际当中，但它们一般不具有全局优化的特点 16。（ 3）基于人工智能 (方法：法是通过提高调度方法的智能而解决各类生产调度问题方法的总称。单一的数学方法和工具不足以解决实际的调度问题，专家系统（出现对解决调度的实时性和智能性提供了新的辅助手段 17。（ 4）基于仿真的方法：由于制造系统的复杂性，以致于很难用精确的解析模型对其进行描述分析。但仿真却能提供理想模型，且可以定量地进行评估，从而对实际系统采用合适的调度方法 18。仿真方法用于调度的优点有：实验时间短，不受时空限制；可以测试不同调度决策的性能，从而选择较优的调度决策；能够用分析方法解决问题并寻求可行解。其不足之处是：由于仿真具有实验的特点，很难从特定的实验中提炼出一般的规律性；生产调度成本高；仿真结果的价值和可信度严重依赖仿真模型、仿真方法及仿真实验输入数据；仿真的准确性受程序员判断能力和技能的限制。（ 5）计算智能方法：近年来，一些高级局域搜索法由于具有普遍适用性和较低的经验复杂性等优点，得到了广泛的重视和应用。主要有以下几种方法：遗传算法 ( 次将用到实际工程系统的优化当中。由于理和操作简单，通用性强，不受限制条件的约束，且具有隐含并行性和全局空间搜索能力，尤其适用于处理传统搜索方法难以解决的复杂的非线性问题。在机器学习、模式识别、控制工程等领域，尤其在生产调度领域都得到了广泛地应用。然而遗传算法对于大规模的组合优化问题，搜索空间大，搜索时间较长，往往会出现早收敛的现象；对初始种群很敏感，初始种群选择不好会影响解的质量和算法效率。目前，人们主要从两方面入手：一是对遗传算法本身进行改进；一是与其他算法结合，取长补短。神经网络 (化法：用于车间调度，主要有三类方式 :利用其并行计算能力，求解优化调度，以克服调度的题。利用其学习能力，从优化轨迹中提取调度知识。用描述调度约束或调度策略，以实现对生产过程的可行或次优调度。（ 6）组合调度方法：由于各种调度算法都不同程度地存在不足之处，所以学者们开始关注各种近似算法的组合研究，以弥补各自的缺点，发挥各自的优势，达到高度优化的目标。目前，各种算法的组合应用己成为解决优化调度问题很有前途的方法。 (7)基于对于车间类型的样可用其解析模型与方法来解决车间调度问题。如极大代数法、动态规划法。但它们都只是适合于制造系统的性能分析。于混合遗传算法的车间调度方法研究与应用发、动态、直观等优点外， 7 还有能够准确快速地反映制造系统适时调度的离散性与随机性等特点，所以它与其它方法相结合在调度问题中得到了广泛的应用。目前，节点语义的单义性，使得所携带的系统信息不够丰富。重用性差。当调度规则或方法复杂时，建模困难。 (8)禁忌搜索 ( 善和发展 1 羽。目前，在调度、交通运输、题、电子电路设计等诸多领域中得到应用。 (9)模拟退火 (求得组合优化问题的最优或次最优解，首次将于优化领域的是尝试了将外， ob (10)拉氏松弛法拉氏松弛法由于其在可行的时间里能对复杂的规划问题提供好的次优解，并能对解的次优性进行定量的评估，近年来已经成为解决复杂车问调度问题的一种重要方法，但不可避免的是，拉氏松弛法对其对偶问题存在搜索效率低、可行调度的构造有待进一步研究等问题。 (11)基于模糊数学理论的方法客观现象具有确定性与不确定性两个基本方面，经典数学表达的是现象的确定性，不确定性一方面表现为随机性，另一方面表现为模糊性。正是利用此特点，许多学者把它引入调度领域 11 引，但与专家系统相似，这种方法同样存在开发周期长。需要丰富的调根据以上优化方法的分析比较，采用遗传算法进行调度 ,计算复杂度低，调度全面 ,并在实际中得到了比较广泛的应用。所以最终确定采用遗传进行优化，获得最终的调度方案，使得加工路径能够完成优化。传算法基本理论遗传算法（对于古典的启发式算法具有更好的性能 1，它可以适应不同的问题形式，对搜索问题的限制少，减少了要解决的问题的复杂性。遗传算法可以同时搜索解空间内的许多点，有效地防止了搜索过程中收敛到局部最优解的情况。并且因其在搜索的过程中有目标性和方向性，相对于其它搜索方法，在计算时间上更有优势【 19、 20】。遗传算法（一种模拟生物自然进化现象的优化算法，其核心思想是借用遗传学中的思想以及达尔文进化论的 “ 物竞天择，适者生存 ” ，最早由美国密歇根大学（ 1989年 7在其著作中对遗传算法进行了更为全面和系统的总结，并由此奠定了遗传算法的基础。遗传算法将问题的解表示为 “ 染色体 ” ，通过模拟自然界中物种的选择、复制、交叉和变异等操作，以实现个体适应度的提高，并通过不断的迭代和对个体的评价选择，逐步寻找最优解（或次优解）【 21、22】。五个基本要素包括：编码解码，种群初始化，构造适应度函数，构造遗传算子（包括选择、复制、交叉、变异等）和遗传参数设置（包括种群的规模、遗传算子的概率等）。下面给出一般遗传算法基本求解的步骤，其流程框图如图 2示。步骤 1：随机产生一个初始种群，并令其规模为 P。 8 步骤 2：对种群中的每个个体评价其适应度值。步骤 3：如果满足算法终止条件，则输出结果；如果不满足，则继续下一步骤。步骤 4：按照一定的策略和规则进行交叉、变异和选择等操作。步骤 5：产生下一代种群并返回到步骤 2。图 2传算法流程图遗传算法具有（ 1）不受限制性条件的约束，设计简单且适应性广；（ 2）隐含并行搜索能力，能够在复杂空间进行全局优化搜索；（ 3）较高的搜索效率；（ 4）较强的鲁棒性，易得到全局最优解的同时减小陷入局部极小的可能性；（ 5）编码技术和遗传操作比较简单，优化算法通用性强等特点。相对于其他传统算法，遗传算法更能适用于不确定条件下的柔性作业车间调度问题的求解【 24】。传算法基本概念由于遗传算法是因进化论和遗传学机理而产生的直接搜索优化方法，故而在这个算法中要用到各种进化和遗传学的概念。这些概念如下： 1串它是个体的形式，在算法中称为字符串，并且对应于遗传学中的染色体。 2群体对问题进行编码产生初始种群 p(t) 计算种群个体适应度进行遗传操作：选择、交叉、变异产生种群p(t+1) 最佳个体是否满足优化准则初始种群 p(t)种群 p(t+1) 开始 n y 9 个体的集合称为群体，串是群体中的元素。 3群体大小在群体中个体的数量称为群体的大小。 4基因基因是串中的元素，基因用于表示个体的特征。例如有一个串 S=1001，则其中的 1、 0、 0、 1这 4 个元素分别称为基因。它们的值称为等位基因。 5基因位置一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置由串的左侧向右侧计算，例如在串 S=1101中，。基因位置对应于遗传学中的地点。 6基因特征值在用串表示整数时，基因的特征值与二进制数的权一致。例如在 ,s=1011中，基因位置 3中的 1，它的基因特征值为 2，基因位置 1中的 l，它的基因特征值为 8。 7串的结构空间在串中，基因任意组合构成了串的集合。基因操作是在串结构空间中进行的。串结构空间对应于遗传学中的基因型的集合。 8参数空间是串空间在物理系统中的映射，它对应于遗传学中的表现型的集合。 9适应度表示某一个体对于环境的适应程度。传算法主要步骤遗传算法的主要步骤如下所示： 1编码：遗传算法在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合便构成了不同的点。编码的目的主要是使优化问题解的表现形式适合于遗传算法中的遗传运算。 2初始群体的生成：随机生成一定数目的初始群体，以此群体为基础，开始迭代运算。 3确定适应度函数：适应度函数基本上依据优化问题的目标函数而定，其作用是表明个体的优劣性。 4选择：当适

温馨提示:
1: 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

人人文库网所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。