人人文库网 > 图纸下载 > 毕业设计 > 柔性制造系统中机床调度优化研究【研究类】【无图】

柔性制造系统中机床调度优化研究论文.doc

柔性制造系统中机床调度优化研究【研究类】【无图】

资源目录

柔性制造系统中机床调度优化研究【研究类】【无图】.rar

柔性制造系统中机床调度优化研究论文.doc---(点击预览)

柔性制造系统中机床调度优化研究答辩PPT.ppt---(点击预览)

柔性制造系统中机床调度优化研究开题报告.doc---(点击预览)

任务书.doc---(点击预览)

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

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

编号：273350 类型：共享资源大小：426.91KB 格式：RAR 上传时间：2014-04-26 上传人：上*** IP属地：江苏

40
积分

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

关键词：: 柔性制造系统机床调度优化研究钻研

资源描述：

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

48页 28000字数+说明书+开题报告+任务书+答辩PPT

中期检查.doc

任务书.doc

柔性制造系统中机床调度优化研究开题报告.doc

柔性制造系统中机床调度优化研究答辩PPT.ppt

柔性制造系统中机床调度优化研究论文.doc

第一章绪论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系统在有扰动时也能持续地运行。

关键词：遗传算法,动态调度,柔性制造系统1.2课题提出的目的和意义

　　　“柔性”是指生产组织形式和生产产品及工艺的多样性和可变性，可具体表现为机床的柔性、产品的柔性、加工的柔性、批量的柔性等。柔性制造系统适合于多品种、中小批量生产，可迅速适应产品变化，具有进步设备利用率、减少在制品库存量、进步产品质量和一致性等诸多优点[1、2]。但是系统的这些优点能否发挥，取决于各生产设备调度后的运行效率情况，如仓库的调度、机床的调度、物料运输车辆的调度等。其中机床的调度优化起到非常关键的作用。机床调度的目的是将工序合理的分配给各机床，并对各机床上的工序进行排序优化以使完成所有工序的时间最小。该调度的评价以目标函数为主，如“最小制造周期”、“机床利用率”、“工件流通时间”等，这些评价参数都对整个生产系统的加工效率具有直接的影响。所以合理的机床调度规则，在时间和空间上可有效利用系统的有限资源，以满足各项生产指标的要求。因此机床调度问题将直接影响系统的有效性和柔性，通过设计适合的调度算法对机床各种工作情况进行实时的调度研究，具有非常现实的意义，它的优化可提高生产任务的加工效率。

　　　本文主要针对机加工车间加工机床的调度问题进行研究，并运用经典调度算法进行优化，寻求最佳加工路径。

1.3课题相关研究领域的发展状况及趋势

20世纪50年代调度问题受到了应用数学、运筹学、工程技术等多个领域学者的关注，并运用运筹学中的线性规划、动态规划及决策分析等方法，研究和解决了一系列具有代表意义的调度和优化问题。

柔性制造系统是70年代末、80年代初出现的一种具有高度柔性的自动化制造系统。随着科学技术的发展，新产品的出现，产品市场寿命也随之缩短，相应1.4 本课题主要研究内容和设计任务

本课题主要是运用生产调度相关知识来解决机加工车间的机床调度优化问题。本课题的设计任务是：分析机床的各种主要工作情况及设备状态，对应的设计调度算法，要有评价方法对调度效果作出评价；利用仿真软件进行算法优化的仿真论证或寻找其他的论证方法。

　　　本文的主要内容是:主要针对机床调度问题的调度方法进行研究，并运用遗传算法对调度问题进行优化，寻求最佳调度方案。本文共分五章：

　　　第一章首先提出通过引言提出课题研究的目的和意义；然后进一步介绍了FMS中机床调度问题的研究现状，研究方法，存在的问题及发展趋势；最后给出课题的主要工作及内容。

　　　第二章首先阐述了调度的相关理论；然后对调度问题进行分类和总结其特点，说明在实际调度问题中需要调度的方面；其次对调度算法进行归类，并分别描述各算法的基本思想和特点。根据调度问题选择遗传算法，并对遗传算法的基本理论和操作步骤进行描述。为下文的实例做理论铺垫。

　　　第三章依据上述的调度和遗传算法基本理论，分静态和动态分别应用遗传算法进行调度，并给出实例。

　　　第四章给出基于遗传算法进行调度的实例,并根据所给的实例进行编程，验证算法的可行性和调度后起到的优化作用。

　　第五章结论与展望

内容简介：: 西安文理学院本科毕业设计（论文）中期检查表题目柔性制造系统中机床调度优化研究学生姓名王磊学号08102080225专业名称机械设计制造及其自动化指导教师边培莹、吕荣生检查时间2011-4-6班级08机械2班毕业设计（论文）进展情况通过对柔性制造系统中机床调度优化研究的相关资料的学习，以及对整个设计的了解，现基本完成以下设计工作：1.完成机床调度优化目标的总结与分析。基本了解实现机床调度优化的算法。2.确定了总体设计方案，以及具体采用的调度优化算法。3.开始对遗传算法进行深入学习，并学习C+的相关知识。4. 初步确定了论文的提纲和核心下一步设计工作内容是通过采用遗传算法实现对机床的调度优化，并利用C+软件仿真得出结果。以及毕业论文的撰写。指导教师意见自开题以来，通过查阅资料并积极与老师的沟通，该生比较清楚自己的设计内容和技术路线，能按计划、分步骤的展开设计任务，并能按时接受指导，有问题随时联系老师，保持了良好的指导关系。基本达到了上述设计进展。签字：年月日教研室意见签字：年月日西安文理学院本科毕业设计（论文）任务书题目柔性制造系统中机床调度优化研究学生姓名王磊学号08102080225专业班级08级机械(2)班指导教师边培莹、吕荣生职称助教、副教授教研室机械毕业设计（论文）任务与要求1 在柔性生产方式下，机床设备的调度对生产效率的影响非常大，设计适合的调度算法对机床各种工作情况进行实时的调度，以优化提高生产任务的加工效率；2 设计要求：分析机床的各种主要工作情况及设备状态，对应的设计调度算法，要有评价方法对调度效果作出评价；3 开题报告及中期检查各一份；4 利用仿真软件进行算法优化的仿真论证或寻找其他的论证方法；5 撰写毕业论文，包括文献综述（另翻译英文资料一份）及主要仿真结果说明等；毕业设计（论文）工作进程起止时间工作内容2012.1.10-2012.2.282012.3.1-2012.3.202012.3.21-2012.4.102012.4.11-2012.4.202012.4.21-2012.5.11分析任务书，了解所选课题，选择相应期刊及论文资料，制定开题报告。研究学习各种调度优化算法工作原理、及仿真软件的编程语言（如VC+语言），并提出该机床的调度方案。进行详细调度优化算法的设计并论证其合理性。进一步对确定的方案进行设计，并编制仿真程序。完成毕业设计论文的撰写、整理工作。开始日期 2012-1-10 完成日期 2012-5-11 教研室主任（签字）系主任（签字）西安文理学院机械电子工程系本科毕业设计（论文）题目柔性制造系统中机床调度优化研究专业班级 08级机械（2）班学号 08102080225 学生姓名王磊指导教师边培莹吕荣生设计所在单位西安文理学院 2012年 5 月西安文理学院本科毕业设计（论文）开题报告题目柔性制造系统中机床调度优化研究学生姓名王磊学号08102080225专业名称机械设计制造及其自动化指导教师边培莹、吕荣生开题时间20122.28班级08机电（2）班一、选题目的和意义：“柔性”是指生产组织形式和生产产品及工艺的多样性和可变性，可具体表现为机床的柔性、产品的柔性、加工的柔性、批量的柔性等。柔性制造系统适合于多品种、中小批量生产，可迅速适应产品变化，具有进步设备利用率、减少在制品库存量、进步产品质量和一致性等诸多优点。但是系统的这些优点能否发挥，取决于各生产设备调度后的运行效率情况，如仓库的调度、机床的调度、物料运输车辆的调度等。其中机床的调度优化起到非常关键的作用。机床调度的目的是将工序合理的分配给各机床，并对各机床上的工序进行排序优化以使完成所有工序的时间最小。该调度的评价以目标函数为主，如“最小制造周期”、“机床利用率”、“工件流通时间”等，这些评价参数都对整个生产系统的加工效率具有直接的影响。所以合理的机床调度规则，在时间和空间上可有效利用系统的有限资源，以满足各项生产指标的要求。因此机床调度问题将直接影响系统的有效性和柔性，通过设计适合的调度算法对机床各种工作情况进行实时的调度研究，具有非常现实的意义，它的优化可提高生产任务的加工效率。二、本课题在国内外的研究状况及发展趋势：柔性制造系统是70年代末、80年代初出现的一种具有高度柔性的自动化制造系统。随着科学技术的发展，新产品的出现，产品市场寿命也随之缩短，相应的更新换代的速度加快，中小批量生产比例增加，以这种生产方式生产的产品占制造业总值的70%，其中采用优化调度的方法可提高30%的生产效率。尤其是近年来，国外一些工业技术比较发达的国家为进一步提高劳动生产率，降低生产成本，缩短产品的生产周期以增强产品更新换代和产品市场竞争力，所以柔性制造企业对调度优化的要求越来越高，由此带动的学术界对该问题的研究也越来越多。由于调度问题的复杂性，不同的研究者提出不同的算法和优化过程，最初是集中在整数规划，仿真和简单的规则上，随着各种新的交叉学科和优化技术的建立和发展，出现了很多智能调度优化的方法，如神经网络，模拟退火法，遗传算法，禁忌搜索法等，使调度问题的方向向多元化方向发展。在未来的发展中，如何在先进的柔性制造系统中实现各生产环节调度的实时性和高效性，确定简洁实用的算法将是重中之重。目前对物料运送车辆AGV的调度和对仓库的调度的研究非常多，而机床的调度相对薄弱，主要是通过一些经典的排队算法的简单应用。但机床在整个加工环节对整个系统效率的影响又是最大的，所以本课题将寻找简单、实用、可行的一种调度算法以提高系统的加工效率。三、主要研究内容：1确定方案：了解柔性制造系统的工作原理及主要功能，提出该系统下机床优化调度设计方案；2算法分析：根据系统功能，选择合适的算法，实现机床的优化调度。3系统设计：用仿真软件实现对具体的算法仿真验证。4. 完成毕业论文的撰写。指导教师意见及建议：王磊同学能较认真的查阅本毕业设计课题相关的参考资料与相关文献，对所设计的机床调度问题发展现状清楚、调度方案思路清晰，也积极展开了相关软件的学习。同意开题！签字：年月日教研室审核意见：签字：年月日注：此表前三项由学生填写后，交指导教师签署意见，经教研室审批后，才能开题。设计题目柔性制造系统中机床调度优化研究机械电子工程系08级机电 2 班王磊指导老师边培莹柔性制造系统中机床调度优化研究一选题目的和意义二调度与遗传算法相关理论三基于遗传算法进行机床调度四 C语言相关知识及编程五总结一选题的目的和意义柔性制造系统具有提高设备利用率减少在制品库存量进步产品质量和一致性等诸多优点但是系统的这些优点能否发柔挥取决于各生产设备调度后的运行效率情况如仓库的调度机床的调度物料运输车辆的调度等其中机床的调度优化起到非常关键的作用通过设计适合的调度算法对机床各种工作情况进行实时的调度研究具有非常现实的意义它的优化可提高生产任务的加工效率本文主要针对机加工车间加工机床的调度问题进行研究并运用遗传算法进行优化寻求最佳加工路径二调度与遗传算法相关理论调度是针对一项可分解的生产任务探讨在尽可能满足约束条件的前提下通过下达生产指令安排其组成部分使用哪些资源其加工时间以及加工顺序以获得生产任务执行时间或成本的最优化 2 1机床调度的分类1 根据零件和车间构成不同分为单机车间调度问题并行机车间调度问题开放车间调度问题流水车间调度问题作业车间调度问题2 根据作业的加工特点分为静态调度动态调度 2 2调度的优化算法 1 数学规划方法 2 基于启发式规则的调度方法 3 基于人工智能 AI 的方法 4 基于仿真的方法 5 计算智能方法 6 组合调度方法 7 基于DEDS的解析模型方法 8 禁忌搜索 9 模拟退火 10 拉氏松弛法根据以上优化方法的分析比较最终确定采用遗传进行优化获得最终的调度方案使得加工路径能够完成优化 2 3遗传算法的基本理论遗传算法是将问题的解表示为染色体通过模拟自然界中物种的选择复制交叉和变异等操作以实现个体适应度的提高并通过不断的迭代和对个体的评价选择逐步寻找最优解基本流程如图所示遗传算法流程图初始种群p t 种群p t 1 2 4遗传算法基本操作 1 适应度函数的选择常用的方法是将适应度函数取为目标函数的倒数即g x 为时间函数最小值2 选择算子比例选择法是基本的选择方法也叫轮盘赌选择法它的基本思想是个体被选中的概率与其适应度大小成正比设群体大小为M 个体i的适应度为Fi 选择概率Pi为 2 5交叉算子所谓交叉操作是指对两个相互配对的个体按某种方式相互交换其部分基因从而形成两个新的个体单点交叉在个体串中随机设定一个交叉点实行交叉时该点前或后的两个个体的部分结构进行互换并生成两个新的个体如图所示父体A11011110 11011001子体A 父体B10111001 10111110子体B 2 6变异算子变异运算是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其它等位基因来替换从而形成一个新的个体基本变异算子是指对群体中的个体码串随机挑选一个或多个基因并对这些基因座的基因值作变动依变异概率作变动 0 1 二值码串中基本变异操作如图所示变异前1101001 1001011变异后 2 7遗传算法参数选择 1 染色体位串长度L本文中将采用基于工序的实数编码染色体的每个基因位代表一道工序染色体长度表示所有待加工工序数的总和 2 群体规模popsize本文实例是针对较小批量和较大批量的零件加工故取群体规模popsize 40 3 交叉概率Pc一般取Pc 0 6 1 本文取Pc 0 8 4 变异概率Pm一般取Pm 0 005 0 01 本文取Pm 0 01 三基于遗传算法进行机床调度 3 1静态车间调度静态车间调度是指所有待安排加工的工件均处于待加工状态因而进行一次调度后各作业的加工被确定在以后的加工过程中就不再改变故静态车间调度不考虑零件在加工过程中出现的意外情况如机床突然损坏零件的交货期提前有更紧迫的零件要求被加工等等主要步骤 1 编码 2 初始种群的产生 3 选择操作 4 交叉操作 5 变异操作 6 解码 3 1静态车间调度实例调度前工件加工顺序如表所示调度后合理加工顺序 3 2动态车间调度在FMS实际加工环境下当不可预知的事情发生时原有的调度方案不得不中止且调度系统必须及时地调整工件原有的加工路径和其他资源调度的状况同时必须对突发事件做出迅速响应以确保调度系统能够持续优化地进行这种能够引起原有调度方案的更改从而需要采取动态调度措施的突发事件称之为动态事件也称重调度因子或扰动动态事件类型分为 1 急件到来 2 机器故障 3 订单取消急件到来的调度Gantt图取消订单的调度Gantt图设备故障的调度Gantt图四 C语言相关知识及编程根据上述算法过程分别进行编程得到编程结果如下 1 急件到来 2 机器故障 3 订单取消五总结本文针对FMS机床调度问题的调度方法进行了研究采用自然数编码方法简单容易理解进行遗传操作方便采用最优优先的比例选择法既避免了最优个体被漏选的可能又能保证算法在全局中寻优考虑三种动态事件采用自适应遗传算法对动态问题进行了重调度研究了FMS动态调度问题但是应用于实际问题还需要进一步的研究谢谢各位老师祝老师身体健康工作顺利西安文理学院机械电子工程系本科毕业设计（论文）题目柔性制造系统中机床调度优化研究专业班级 08级机械（2）班学号 08102080225 学生姓名王磊指导教师边培莹吕荣生设计所在单位西安文理学院 2012年 5 月目录第一章绪论11.1 引言11.2课题提出的目的和意义11.3课题相关研究领域的发展状况及趋势11.4 本课题主要研究内容和设计任务2第二章调度与遗传算法相关理论42.1调度的定义42.1.1机床调度的定义42.1.2机床主要调度问题42.2调度问题的描述和分类42.3调度的优化算法52.4遗传算法基本理论72.5遗传算法基本概念82.6遗传算法主要步骤92.7适应度函数92.8遗传操作算子102.8.1选择算子102.8.2交叉算子112.8.3 变异算子122.9遗传算法参数的选择132.10 遗传算法的应用与发展趋势13第三章基于遗传算法进行机床调度153.1静态车间调度153.2 问题的描述153.3基本遗传算法的构造153.3.1编码153.3.2 解码161 基于机器编码的机器工件队列之间的冲突消解162. 最后解码计算最大调度时间173.4 初始种群的产生173.5 选择操作173.6交叉操作183.7变异操作183.8 动态车间调度183.9动态调度类型193.10动态调度控制方法203.10.1急件到来203.10.2机器故障223.10.3订单取消243.11应用实例26第四章C语言相关知识及编程314.1 C语言相关知识314.2 C语言程序的特点314.3 C语言程序的开发步骤324.4 C语言编程324.5 输出结果37第五章全文总结与展望395.1全文总结395.2 展望39结束语40致谢41参考文献4244柔性制造系统中机床调度优化研究摘要: 随着市场的多变以及市场对产品个性化的需求，多品种、小批量生产方式已经逐渐成为制造业的发展主流。研究批量调度的优化方法，对于先进制造业的现代化具有重要的理论价值和实际意义。本文介绍了机床调度的概念及其发展过程、研究现状和发展趋势；对车间调度的各种研究方法进行了简要的介绍和比较；概述了遗传算法的基本原理和步骤，介绍了遗传算法常用的一些算子，分析了遗传算法的特点，并对遗传算法的一些理论进行了讨论。对三种常见的动态事件（急件到来、设备故障、订单取消）的重调度控制方法进行了研究，并在静态调度问题研究的基础上，运用自适应遗传算法对动态调度问题进行了研究，获得了动态调度的控制策略和重调度方法。此控制策略和重调度方法可以较好地解决由于动态事件的出现而导致的静态调度方案不再适用的问题，从而保证了FMS系统在有扰动时也能持续地运行。关键词：遗传算法,动态调度,柔性制造系统Flexible manufacturing system in machine tool research on Scheduling OptimizationAbstract： 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 graduallyThe 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 comparedBasic foundation,process and operations of GA are stated briefly，and the character is ticsander theoretic are discussedThe 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第一章绪论1.1 引言近一世纪以来，企业所处的环境经历了巨大的变化。20世纪初期，现代企业处于刚刚起步的阶段，生产规模尚未达到一定的程度，产品处于供不应求阶段，企业只要保障生产能力和基本产品质量即可。但从70年代开始，企业所面临的环境发生了极大的变化，主要体现在：1市场需求的改变：20世纪50年代以后，全球制造业生产能力不断扩大，生产规模和效率迅速提高。进入70年代，世界主要市场开始进入需求导向的时代。消费观念也出现了结构性变化，消费需求趋向多样化和个性化。20世纪90年代，产品的销售半径不断增大，制造商必须面对处于不同地域、不同文化和不同环境下的全球用户。进入21世纪，全球市场需求的多样化趋势更加明显，制造业面临全球性多样化、个性化需求的挑战。2技术的不断创新：科学技术日新月异，以信息技术、自动化技术、现代管理与制造技术相结合的先进制造技术应运而生。3全球化的竞争：随着科技的发展和全球贸易的提出，生产和销售已经变得的没有国界。这种情况，加剧了企业之间的竞争，对产品的生产提出了更高的要求。1.2课题提出的目的和意义“柔性”是指生产组织形式和生产产品及工艺的多样性和可变性，可具体表现为机床的柔性、产品的柔性、加工的柔性、批量的柔性等。柔性制造系统适合于多品种、中小批量生产，可迅速适应产品变化，具有进步设备利用率、减少在制品库存量、进步产品质量和一致性等诸多优点1、2。但是系统的这些优点能否发挥，取决于各生产设备调度后的运行效率情况，如仓库的调度、机床的调度、物料运输车辆的调度等。其中机床的调度优化起到非常关键的作用。机床调度的目的是将工序合理的分配给各机床，并对各机床上的工序进行排序优化以使完成所有工序的时间最小。该调度的评价以目标函数为主，如“最小制造周期”、“机床利用率”、“工件流通时间”等，这些评价参数都对整个生产系统的加工效率具有直接的影响。所以合理的机床调度规则，在时间和空间上可有效利用系统的有限资源，以满足各项生产指标的要求。因此机床调度问题将直接影响系统的有效性和柔性，通过设计适合的调度算法对机床各种工作情况进行实时的调度研究，具有非常现实的意义，它的优化可提高生产任务的加工效率。本文主要针对机加工车间加工机床的调度问题进行研究，并运用经典调度算法进行优化，寻求最佳加工路径。1.3课题相关研究领域的发展状况及趋势 20世纪50年代调度问题受到了应用数学、运筹学、工程技术等多个领域学者的关注，并运用运筹学中的线性规划、动态规划及决策分析等方法，研究和解决了一系列具有代表意义的调度和优化问题。柔性制造系统是70年代末、80年代初出现的一种具有高度柔性的自动化制造系统。随着科学技术的发展，新产品的出现，产品市场寿命也随之缩短，相应的更新换代的速度加快，中小批量生产比例增加，以这种生产方式生产的产品占制造业总值的70%，其中采用优化调度的方法可提高30%的生产效率3、4、5。尤其是近年来，国外一些工业技术比较发达的国家为进一步提高劳动生产率，降低生产成本，缩短产品的生产周期以增强产品更新换代和产品市场竞争力，所以柔性制造企业对调度优化的要求越来越高，由此带动的学术界对该问题的研究也越来越多。由于调度问题的复杂性，不同的研究者提出不同的算法和优化过程，最初是集中在整数规划，仿真和简单的规则上，随着各种新的交叉学科和优化技术的建立和发展，出现了很多智能调度优化的方法，如神经网络，模拟退火法，遗传算法，禁忌搜索法等，使调度问题的方向向多元化方向发展6。在未来的发展中，如何在先进的柔性制造系统中实现各生产环节调度的实时性和高效性，确定简洁实用的算法将是重中之重。目前对物料运送车辆AGV的调度和对仓库的调度的研究非常多，而机床的调度相对薄弱，主要是通过一些经典的排队算法的简单应用。但机床在整个加工环节对整个系统效率的影响又是最大的，所以本课题将寻找简单、实用、可行的一种调度算法以提高系统的加工效率。为解决存在的问题，对调度问题的研究主要有以下几种发展趋势：（1）调度算法和调度系统的深入研究和开发：目前对调度算法和调度系统的研究己取得很大进展，但由于调度问题的性质而不可能在短期内取得突破性进展，这就要求人们进一步拓宽研究范围和思路，在原来调度算法的基础上继续寻找可行的能够获得最优解而且求解速度快的调度算法。基于人工智能、计算智能和实时智能的调度算法将会是未来调度算法的主流7。（2）调度专家的作用问题研究：调度专家具有丰富的经验，纯粹的自动调度是不现实且很难实现的。因此，具有最终决策职责的调度专家的重要作用在任何时候都不能忽略。所以研究调度专家的作用以及如何与调度系统的协调等问题也是一个重要的研究方向。（3）多种调度方法的结合研究：目前许多新的算法应用于调度领域，但由于需要特定的应用环境,所以就出现了调度理论和实践的不一致性8、9。因此,集成各种调度算法求解生产调度问题充分发挥各种调度算法自身的优势，是今后研究和解决实际调度问题的重要方向之一10、11。总之，车间调度领域的研究，随着科学的进一步发展，必然朝着集成化、柔性化，多标准化、动态实用化高层次优化方向发展。1.4 本课题主要研究内容和设计任务本课题主要是运用生产调度相关知识来解决机加工车间的机床调度优化问题。本课题的设计任务是：分析机床的各种主要工作情况及设备状态，对应的设计调度算法，要有评价方法对调度效果作出评价；利用仿真软件进行算法优化的仿真论证或寻找其他的论证方法。本文的主要内容是:主要针对机床调度问题的调度方法进行研究，并运用遗传算法对调度问题进行优化，寻求最佳调度方案。本文共分五章：第一章首先提出通过引言提出课题研究的目的和意义；然后进一步介绍了FMS中机床调度问题的研究现状，研究方法，存在的问题及发展趋势；最后给出课题的主要工作及内容。第二章首先阐述了调度的相关理论；然后对调度问题进行分类和总结其特点，说明在实际调度问题中需要调度的方面；其次对调度算法进行归类，并分别描述各算法的基本思想和特点。根据调度问题选择遗传算法，并对遗传算法的基本理论和操作步骤进行描述。为下文的实例做理论铺垫。第三章依据上述的调度和遗传算法基本理论，分静态和动态分别应用遗传算法进行调度，并给出实例。第四章给出基于遗传算法进行调度的实例,并根据所给的实例进行编程，验证算法的可行性和调度后起到的优化作用。第五章结论与展望第二章调度与遗传算法相关理论2.1调度的定义2.1.1机床调度的定义机床调度可以描述为若干个任务在一些机器上进行加工，如何按时间对机器和工序等进行安排，使某些目标函数，例如产品制造时间或者成本等达到最优。在一定的约束条件下，调度的目标是将生产合理地安排到各机床，并合理安排作业的加工次序和加工开始时间，同时优化一些性能指标12。机床调度目标是在满足系统约束条件下，依据反映了客户需求和市场需求的生产计划合理安排各加工任务的实施时间及使用的设备，为生产线上的各台设备和各个工件形成可行的加工安排，并尽可能优化系统的性能指标，最佳地安排与组织生产，为企业带来显著的经济效益。2.1.2机床主要调度问题机床调度问题一般可以描述为:n个工件在m台机器上加工，一个工件k道工序，每道工序可以在若干台机器上加工。每台机器在每个时刻只能加工某个工件的某道工序，而且只能在上道工序加工完成后才能开始下一道工序的加工12。机床调度问题是根据加工对象的加工需求，运用不同的调度决策规则和优化算法，规划系统的加工事件，并根据系统动态仿真运行的结果或者优化结果形成最佳的生产加工顺序，同时实现设备集和任务集的合理最优化结合。调度的特点是多个工件在有限的机器上加工，每台机器在切换不同的工件生产时需要一定的准备时间。调度的决策内容包括分配决策(工件的加工顺序)和时间决策(工件各工序的加工时间)以及路径决策(工件各工序的加工设备的分配)。2.2调度问题的描述和分类生产调度问题是一类典型的实际调度问题，它很早就受到了生产管理者们的关注，但那时还没有进入到理论研究的阶段，只是一些简单的思想，也没有被广泛的应用到实际中。那时人们主要关注的问题是如何分配工作以及哪些操作者能够胜任这样的工作。起初人们主要从应用数学的角度来研究调度问题，调度问题通常被定义为：“对一种资源进行分配来执行一种任务”，也就是对零件进行“排序（sequencing）”的问题。如Gantt提出了使用可视化的图标来表示生产的进度状况，Co阐述了一种机械的调度技术。而在后来的生产中，针对先进制造系统，调度问题被更为具体地定义为：“生产调度是针对一项可分解的生产任务,探讨在尽可能满足约束条件的前提下,通过下达生产指令,安排其组成部分使用哪些资源、其加工时间以及加工顺序,以获得生产任务执行时间或成本的最优化6 。所以车间调度就是在一定条件下，对一个可用的加工设备集，在时间上进行加工任务分配，以满足某个给定的性能指标。(1)根据加工任务，可将调度分为静态调度和动态调度。静态调度是指所有待安排加工的工件均处于待加工状态，因而进行一次调度后，各作业的加工被确定，在以后的加工过程中就不再改变；动态调度是指作业依次进入待加工状态，各种作业不断进入系统接受加工，同时完成加工的作业又不断离开，还要考虑作业环境中不断出现的不可预测的动态扰动，如作业加工超时、设备损坏等。实际生产调度问题往往是由Job-shop和Flow-shop等基本调度类型组合而成，而其体现的特征是随机性的、动态的13。(2)根据零件和车间构成不同进行分类有:（a）单机车间调度问题加工系统中只有一台机床，所有零件都在该机床上进行加工，待加工的零件有且只有一道工序。一般来说，此问题是最简单的调度问题。（b）并行机车间调度问题加工系统中所有的加工机床是完全相同的，工件可以在任意一台机床上进行加工，并且每个工件只有一道工序。（c）开放车间调度问题工件的加工没有特定的路线约束，每个工序之间没有先后关系的约束。每个零件工序之间的加工顺序是任意的。零件的加工可以从任何一道工序开始，在任何一道工序结束。（d）流水车间调度问题加工系统中有一组功能不同的机床，待加工的零件包含多道工序，每道工序在一台机床上加工，所有零件的加工路线都是相同的。每个工件的工序之间有先后顺序约束关系。（e）作业车间调度问题加工系统中有一组功能不同的机床，待加工的零件包含多道工序，每道工序在一台机床上加工，零件的加工路线互不相同。每个工件工序之间有先后顺序约束，不同工件(3)根据性能指标可以分为基于调度费用和调度性能的指标。(4)根据生产环境的特点将调度问题分为确定性调度、随机性调度。(5)根据作业的加工特点分为静态调度、动态调度。静态调度是指所有的加工的作业都处于待加工状态，因此进行一次调度后所有作业的各个加工都被确定下来，而且在以后的加工过程中不再改变；动态调度是指作业依次进入系统进行加工。完成加工的作业一次离开，同时还要考虑实际加工环境中不断出现的动态扰动，如作业的加工超时、机床损坏等。因此动态调度要根据系统中作业、机床等状况不断地进行重调度。本文在机加工车间环境下，在考虑机床一种资源的情况下，主要针对单件、小批量生产车间如何安排零件在机床上的加工顺序的调度问题进行研究，同时考虑实际生产中的约束条件和优化目标的限制，使得系统能够高效、优化地运行，以确保生产的最大利润。2.3调度的优化算法调度问题的研究方法，最初是集中在整数规划、仿真和简单的规则上，这些方法一般都存在一定的局限性，不是调度结果不理想就是难以解决复杂问题。随着各种新的相关学科与优化技术的建立与发展，在调度领域出现了许多新的优化方法，比如神经网络、模拟退火算法、遗传算法、禁忌搜索法等，使得调度问题的研究方法向多元化方向发展。总结起来，现有调度问题的研究方法大体上可以分为以下几种类别：（1）数学规划方法：即运筹学（OR）方法，将生产调度问题简化为数学规划模型，采用基于枚举思想的分枝定界法解决调度最优化或近似优化问题，属于精确方法。这类方法虽然从理论上能求得最优解，但由于其计算复杂的原因而难以真正实用。对于复杂调度问题，这种纯数学方法由于存在模型提取困难、运算量大、算法难以实现的弱点，仅适合较小规模的调度问题15。（2）基于启发式规则的调度方法：从实用角度来看，启发式算法因其易于实现、计算复杂度低等原因，在实际中得到了比较广泛的应用，并且不断涌现出许多新的调度规则，可将其分为三类:简单规则、复杂规则、启发式规则。虽然启发式规则常被用于实际当中，但它们一般不具有全局优化的特点16。（3）基于人工智能(AI)的方法：AI方法是通过提高调度方法的智能而解决各类生产调度问题方法的总称。单一的数学方法和工具不足以解决实际的调度问题，AI和专家系统（ES）的出现对解决调度的实时性和智能性提供了新的辅助手段17。（4）基于仿真的方法：由于制造系统的复杂性，以致于很难用精确的解析模型对其进行描述分析。但仿真却能提供理想模型，且可以定量地进行评估，从而对实际系统采用合适的调度方法18。仿真方法用于调度的优点有：实验时间短，不受时空限制；可以测试不同调度决策的性能，从而选择较优的调度决策；能够用分析方法解决问题并寻求可行解。其不足之处是：由于仿真具有实验的特点，很难从特定的实验中提炼出一般的规律性；生产调度成本高；仿真结果的价值和可信度严重依赖仿真模型、仿真方法及仿真实验输入数据；仿真的准确性受程序员判断能力和技能的限制。（5）计算智能方法：近年来，一些高级局域搜索法由于具有普遍适用性和较低的经验复杂性等优点，得到了广泛的重视和应用。主要有以下几种方法：遗传算法(GA)：Goldberg首次将GA应用到实际工程系统的优化当中。由于GA原理和操作简单，通用性强，不受限制条件的约束，且具有隐含并行性和全局空间搜索能力，尤其适用于处理传统搜索方法难以解决的复杂的非线性问题。在机器学习、模式识别、控制工程等领域，尤其在生产调度领域都得到了广泛地应用。然而遗传算法对于大规模的组合优化问题，搜索空间大，搜索时间较长，往往会出现早收敛的现象；对初始种群很敏感，初始种群选择不好会影响解的质量和算法效率。目前，人们主要从两方面入手：一是对遗传算法本身进行改进；一是与其他算法结合，取长补短。神经网络(NN)优化法：用于车间调度，主要有三类方式:利用其并行计算能力，求解优化调度，以克服调度的NP难题。利用其学习能力，从优化轨迹中提取调度知识。用NN来描述调度约束或调度策略，以实现对生产过程的可行或次优调度。（6）组合调度方法：由于各种调度算法都不同程度地存在不足之处，所以学者们开始关注各种近似算法的组合研究，以弥补各自的缺点，发挥各自的优势，达到高度优化的目标。目前，各种算法的组合应用己成为解决优化调度问题很有前途的方法。(7)基于DEDS的解析模型方法:对于车间类型的DEDS，同样可用其解析模型与方法来解决车间调度问题。如QN、极大代数法、动态规划法。但它们都只是适合于制造系统的性能分析。Petri网除具有并基于混合遗传算法的车间调度方法研究与应用发、动态、直观等优点外，还有能够准确快速地反映制造系统适时调度的离散性与随机性等特点，所以它与其它方法相结合在调度问题中得到了广泛的应用。目前，Petri网用于制造系统调度存在以下问题：节点语义的单义性，使得所携带的系统信息不够丰富。重用性差。当调度规则或方法复杂时，建模困难。(8)禁忌搜索(TS)TS是解决复杂组合优化问题的一种搜索策略和方法，由Glover等人提出、完善和发展1羽。目前，TS已在调度、交通运输、TSP问题、电子电路设计等诸多领域中得到应用。(9)模拟退火(sA)SA可求得组合优化问题的最优或次最优解，首次将SA用于优化领域的是Kirkpatrick，他尝试了将SA用于TSP问题的求解，此外，SA在Job shop和Flow shop问题中也得到了一定的应用。(10)拉氏松弛法拉氏松弛法由于其在可行的时间里能对复杂的规划问题提供好的次优解，并能对解的次优性进行定量的评估，近年来已经成为解决复杂车问调度问题的一种重要方法，但不可避免的是，拉氏松弛法对其对偶问题存在搜索效率低、可行调度的构造有待进一步研究等问题。(11)基于模糊数学理论的方法客观现象具有确定性与不确定性两个基本方面，经典数学表达的是现象的确定性，不确定性一方面表现为随机性，另一方面表现为模糊性。正是利用此特点，许多学者把它引入调度领域11引，但与专家系统相似，这种方法同样存在开发周期长。需要丰富的调根据以上优化方法的分析比较，采用遗传算法进行调度,计算复杂度低，调度全面,并在实际中得到了比较广泛的应用。所以最终确定采用遗传进行优化，获得最终的调度方案，使得加工路径能够完成优化。2.4遗传算法基本理论遗传算法（Genetic Algorithm，GA）相对于古典的启发式算法具有更好的性能1，它可以适应不同的问题形式，对搜索问题的限制少，减少了要解决的问题的复杂性。遗传算法可以同时搜索解空间内的许多点，有效地防止了搜索过程中收敛到局部最优解的情况。并且因其在搜索的过程中有目标性和方向性，相对于其它搜索方法，在计算时间上更有优势【19、20】。遗传算法（Genetic Algorithm，GA）是一种模拟生物自然进化现象的优化算法，其核心思想是借用遗传学中的思想以及达尔文进化论的“物竞天择，适者生存”，最早由美国密歇根大学（University of Michigan）的John Holland教授于1975年提出的，1989年Goldberg67在其著作中对遗传算法进行了更为全面和系统的总结，并由此奠定了遗传算法的基础。遗传算法将问题的解表示为“染色体”，通过模拟自然界中物种的选择、复制、交叉和变异等操作，以实现个体适应度的提高，并通过不断的迭代和对个体的评价选择，逐步寻找最优解（或次优解）【21、22】。Michalewicz对遗传算法的五个基本要素做了总结，这五个基本要素包括：编码解码，种群初始化，构造适应度函数，构造遗传算子（包括选择、复制、交叉、变异等）和遗传参数设置（包括种群的规模、遗传算子的概率等）。下面给出一般遗传算法基本求解的步骤，其流程框图如图2-1 所示。步骤1：随机产生一个初始种群，并令其规模为P。步骤2：对种群中的每个个体评价其适应度值。步骤3：如果满足算法终止条件，则输出结果；如果不满足，则继续下一步骤。步骤4：按照一定的策略和规则进行交叉、变异和选择等操作。步骤5：产生下一代种群并返回到步骤2。对问题进行编码产生初始种群p(t)计算种群个体适应度进行遗传操作：选择、交叉、变异产生种群p(t+1)最佳个体是否满足优化准则初始种群p(t)种群p(t+1)开始ny图2-1遗传算法流程图遗传算法具有（1）不受限制性条件的约束，设计简单且适应性广；（2）隐含并行搜索能力，能够在复杂空间进行全局优化搜索；（3）较高的搜索效率；（4）较强的鲁棒性，易得到全局最优解的同时减小陷入局部极小的可能性；（5）编码技术和遗传操作比较简单，优化算法通用性强等特点。相对于其他传统算法，遗传算法更能适用于不确定条件下的柔性作业车间调度问题的求解【24】。2.5遗传算法基本概念由于遗传算法是因进化论和遗传学机理而产生的直接搜索优化方法，故而在这个算法中要用到各种进化和遗传学的概念。这些概念如下：1串它是个体的形式，在算法中称为字符串，并且对应于遗传学中的染色体。2群体个体的集合称为群体，串是群体中的元素。3群体大小在群体中个体的数量称为群体的大小。4基因基因是串中的元素，基因用于表示个体的特征。例如有一个串S=1001，则其中的1、0、0、1这4个元素分别称为基因。它们的值称为等位基因。5基因位置一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置由串的左侧向右侧计算，例如在串S=1101中，O的基因位置是3。基因位置对应于遗传学中的地点。6基因特征值在用串表示整数时，基因的特征值与二进制数的权一致。例如在,s=1011中，基因位置3中的1，它的基因特征值为2，基因位置1中的l，它的基因特征值为8。7串的结构空间在串中，基因任意组合构成了串的集合。基因操作是在串结构空间中进行的。串结构空间对应于遗传学中的基因型的集合。8参数空间Sr这是串空间在物理系统中的映射，它对应于遗传学中的表现型的集合。9适应度表示某一个体对于环境的适应程度。2.6遗传算法主要步骤遗传算法的主要步骤如下所示：1编码：遗传算法在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合便构成了不同的点。编码的目的主要是使优化问题解的表现形式适合于遗传算法中的遗传运算。2初始群体的生成：随机生成一定数目的初始群体，以此群体为基础，开始迭代运算。3确定适应度函数：适应度函数基本上依据优化问题的目标函数而定，其作用是表明个体的优劣性。4选择：当适应度函数确定以后，计算群体中各个个体的适应度。自然选择规律是以适应度函数值的大小决定的概率分布来确定哪些染色体适应生存，哪些被淘汰，生存下来的染色体组成种群，形成一个可以繁殖下一代的群体。5交叉：交叉操作是遗传算法种最主要的遗传操作。父代的遗传基因结合是通过父代染色体之间的交叉并到达下一代个体的。子代的产生是一个生殖过程，它产生了一个新解。6变异：新解产生过程中可能发生基因变异，变异使某些解的编码发生变化，使解有更大的遍历性，变异运算后得到下一代群体。7终止条件判断：在所有新一代群体中，是否存在满足条件的最优个体。如果存在，则停止迭代运算，输出最优解，否则继续迭代运算。2.7适应度函数遗传算法遵循自然界优胜劣汰的原则，在进行搜索中基本上不用外部信息，而用适应度表示个体的优劣，作为遗传算法操作的依据。个体的适应度高，被选择的概率就高，反之，被选择的概率就低。适应度函数是用来区分群体中个体好坏的标准，是算法演化过程的驱动力，是进行自然选择的唯一依据。改变群体内部结构的操作都是通过适应值加以控制。在具体应用中，适应度函数的设计要结合求解问题本身的要求而定【25】。遗传算法的目标函数不受连续可微的约束且定义域可以为任意集合。对目标函数的唯一要求是，针对输入可计算出能加以比较的非负结果。这一特点使得遗传算法的应用范围很广。1目标函数映射成适应度函数对于求解效能函数和利润函数u(x)的最大值问题，一种最自然的想法就是将目标函数作为适应度函数。但是许多优化问题是求取费用函数占g(x)的最小值，而遗传算法的要求适应度函数取正值，而且适应度越大，个体越好。因此，在不少场合采用问题的目标函数作为个体的适应性度量时，必须将目标函数转化为求最大值形式，而且保证适应度函数非负。一般可采用以下的方法进行转换：显然，存在多种方式选择系数。可以是一个合适的输入值，也可采用迄今为止进化过程中g(x)的最大值或当前群体中g(x)的最大值。当然最好与群体无关。还有一种较常用的方法是将适应度函数取为目标函数的倒数。即2.8遗传操作算子选择、交叉和变异算子是遗传算法“优胜劣汰”思想的主要体现，也是构成算法具备很强的全局搜索能力的核心，利用遗传操作算子能够产生新一代种群，实现种群向更优方向进化。2.8.1选择算子选择算子又称繁殖或者再生，是对群体中的个体按照优胜劣汰的方式选取，并遗传到下一代的操作，它是建立在群体中个体的适应度评价基础上，并选择适应值高的个体进行复制。通过选择机制可以避免优秀基因的流失，能够提高全局收敛性和算法的效率【26】。比例选择法：比例选择法是基本的选择方法，也叫轮盘赌选择法。它的基本思想是：个体被选中的概率与其适应度大小成正比。设群体大小为M，个体i的适应度为Fi，选择概率Pi为： (3-1)式中Pi体现了个体i在整个群体的个体适应度总和中所占的比例，个体适应度值越大，其被选中的概率就越大。但是，采用比例选择法会因为随机数的产生而有可能使适应度高的个体没有被选中的，而适应度低的个体反而被选中。期望值法：期望值方法的基本思想是根据每个个体在下一代群体中的生存期望概率值来进行随机选择运算。个体在下一代群体中生存的期望数目Ni为：（3-2）最佳个体保存法：此方法的思想是把群体中最优的个体挑选出来，直接复制到下一代种群中去，故这种方法又称为精英保护法。最优保存策略成功地改善了遗传算法的局部收敛特性，能够防止优秀个体由于复制、交叉和变异中偶然因素而被破坏，也是一种增强算法稳定性和收敛性的有效方法【27】。但是，应用最优保存法时，应避免使进化计算陷入局部极值，以至于丧失了全局寻优的机会。以上几种选择方法均以适应度为基础进行选择，这就可能在进化过程中导致遗传算法的早期收敛的问题，可采用适应度函数尺度变换的方法来解决，此外还可采用部分个体的替换选择法、自适应变异概率选择法等选择方法来提高遗传算法性能。比例选择法是最基础的选择方法，且易于实现，但是因为这种方法有可能使适应度高的个体没有被选中，而适应度低的个体反而被选中。所以本文将采用比例选择法与最佳个体保存法相结合的选择方法，既避免了最优个体被漏选又能保证算法在全局中寻优。2.8.2交叉算子遗传算法中的所谓交叉操作，是指对两个相互配对的个体按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其它进化计算的重要特征，它在遗传算法中起着关键的作用，是产生新个体的主要方法。目前有如下几种基本交叉方法【28】。1. 单点交叉在个体串中随机设定一个交叉点，实行交叉时，该点前或后的两个个体的部分结构进行互换，并生成两个新的个体。例如图2-2所示。父体A 1 1 O l 1 1 1 0- 1 1 0 1 1 O 0 1 子体A 父体B 1 0 1 1 1 0 0 1- 1 0 1 1 l l 1 0 子体B图2-2单点交叉2. 两点交叉两点交叉的操作与单点交叉类似，只是设置了两个交叉点(依然是随机设定)。两个交叉点之间的码串相互交换，如图2-3所示。父体A 1 0 l 1 1 l 1-1 0 0 1 0 l l 子体A父体B 0 0 0 l 0 0 0-0 0 l 1 1 0 0 子体B图2-3两点交叉3. 多点交叉将单点交叉与二点交叉的概念加以推广，可得到多点交叉的概念。多点交叉是指在个体编码串中随机设置多个交叉点，然后进行基因交换。多点交叉又称广义交叉，其操作过程与二点交叉相类似。一般来讲，多点交叉较少使用，因为不能有效地保存重要的模式，影响了遗传算法性能。2.8.3 变异算子遗传算法中的变异运算是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其它等位基因来替换，从而形成一个新的个体。从遗传运算过程中产生新个体的能力方面来说，交叉运算是产生新个体的主要方法，它决定了遗传算法的全局搜索能力，而变异运算只是产生新个体辅助方法，但它也是必不可少的一个步骤，因为它决定了遗传算法的局部搜索能力【29】。交叉算子与变异算子的相互配合，共同完成对搜索空间的全局搜索和局部搜索，从而使得遗传算法能够以良好的搜索性能完成最优化问题的寻优过程。在遗传算法中使用变异算子的目的有两个：一是改善遗传算法的局部搜索能力。遗传算法使用交叉算子已经从全局的角度出发找一些较好的个体，它们己接近或有助于接近问题最优解。但仅使用交叉算子无法对搜索空间的细节进行局部搜索。这时若再使用变异算子来调整个体编码串中的部分基因值，就可以从局部的角度出发使个体更加逼近最优解，从而提高了遗传算法的局部搜索能力。二是使遗传算法可维持群体的多样性，以防止出现未成熟收敛现象。下面介绍在二进制编码常用的几个变异算子：1 基本变异算子基本变异算子是指对群体中的个体码串随机挑选一个或多个基因并对这些基因座的基因值作变动(依变异概率作变动)，0，1二值码串中基本变异操作如图2-4所示。变异前 1 1 0 1 0 0 1 - 1 0 0 1 0 1 1 变异后图2-4基本变异算子2. 逆转变异算子在个体码串中随机挑选二个逆转点，然后将两个逆转点间的基因值逆向排列，逆转操作如图2-5所示。变异前 1 1 0 1 0 0 1 - 1 1 0 0 1 0 1 变异后图2-5基本变异算子3. 自适应变异算子该算子与基本变异算子的操作内容类似，唯一不同的是变异概率不是固定不变而是随群体中个体的多样性程度而自适应调整。一般是根据交叉所得两个新个体的海明距离进行变化。海明距离越小，变异概率越大，反之变异概率越小。2.9遗传算法参数的选择遗传算法参数主要包括：染色体位串长度、群体规模n、交叉概率Pc和变异概率Pm。由于这组参数的选择对遗传算法的性能有很大影响，所以在初始阶段或进化过程中需要合理地选择和控制，使算法以最佳的轨迹接近最优解【30】。许多学者经过大量地实验研究，给出了最优参数选择的建议：（1）染色体位串长度L：取决于特定问题解的精度。要求精度越高，位串就越长，但需要很长的计算时间。为了提高效率，变长度位串或者在当前所达到的较小可行域内重新编码，是一种可行的方法，并显示了其良好的性能。但在实际中，要根据具体问题选择具有针对性的位串长度。如本文中将采用基于工序的实数编码，染色体的每个基因位代表一道工序，染色体长度表示所有待加工工序数的总和。（2）群体规模popsize：大群体含有较多的模式，为遗传算法提供了足够的模式采样容量，可以改进GA搜索质量，防止早熟现象的产生。但大的群体增加了个体适应度评价的计算量，从而使收敛速度降低。一般情况下专家建议popsize=20200。本文实例是针对较小批量和较大批量的零件加工，故取群体规模popsize=20100。（3）交叉概率Pc：交叉概率控制着交叉算子的应用频率。交叉概率越高，群体中新结构的引入就愈快，优良基因结构的破坏速度也响应上升；交叉概率越低，则可能导致搜索停滞不前。一般取Pc=0.61。自适应遗传算法能够在进化中根据个体优劣和群体分散度对控制参数进行自动调节，可较好地解决标准遗传算法在应用中遇到的收敛性差和早熟问题，所以本文将采用自适应交叉、变异概率作为参数的选择方法，即当群体中新个体产生的速度较小时就增大Pc和Pm，以产生多个新的模式结构；否则就取较小的Pc和Pm，以保证优良的个体不被破坏。（4）变异概率Pm：变异操作是保持群体多样性的有效手段。在交叉操作后产生的新群体中全部个体位串上的每位等位基因按变异概率Pm随机改变，Pm太小可能使某些基因位过早丢失的信息无法恢复，过高则遗传搜索将变成随机搜索，一般取Pm=0.0050.01。实际上，遗传参数的选择很大程度上与问题的类型有着直接的关系，问题的目标函数越复杂，参数选择就越困难。从理论上说，不存在一组适应于所有问题的最佳参数值，随着问题特征的变化，有效参数的差异往往就非常显著。所以如何设定控制参数以使遗传算法的性能得到改善，还需要结合实际问题深入研究，以及依赖遗传算法理论研究的新进展。2.10 遗传算法的应用与发展趋势遗传算法提供了一种求解复杂系统优化问题的框架，它不依赖于问题的具体领域，且具有很强的鲁棒性，在许多工程领域都有成功的应用【31】。遗传算法的主要应用领域有：组合优化：计划调度问题、TSP问题、图的划分问题、运输问题函数优化：多峰函数优化、多目标函数优化、不稳定函数的优化控制：模糊控制器的设计、机器人控制、过程控制、系统辨识规划：0-1整数规划、生产规划、并行任务处理图象处理：模式识别、特征提取、分类设计：结构、布局设计，参数选择优化目前，遗传算法的发展趋势主要有以下几个方面：（1）算法的数学基础：包括算法的收敛性，收敛速度估计，早熟机理的探索与预防，交叉算子的几何意义与统计解释，参数设置对算法的影响等方面。（2）算法与其他优化技术的组合：充分利用遗传算法的大空间群体搜索性能与快速收敛的局部优化方法混合产生有效的全局优化方法，从而从根本上提高遗传算法的计算性能。（3）遗传算法的改进：根据具体应用领域对遗传算法进行改进和完善。（4）算法的并行化研究：遗传算法的群体、适应度评价、随机搜索等特征使其具有明显的并行性。因此，设计各种并行进化策略，建立相应的并行化算法的数学基础，有着非常重要的意义。第三章基于遗传算法进行机床调度3.1静态车间调度静态车间调度是指所有待安排加工的工件均处于待加工状态，因而进行一次调度后，各作业的加工被确定，在以后的加工过程中就不再改变。故静态车间调度不考虑零件在加工过程中出现的意外情况，如机床突然损坏、零件的交货期提前，有更紧迫的零件要求被加工等等【32】。由以下实例说明。3.2 问题的描述研究n个工件在m 台机床的加工, 已知各个工件的各个工序的加工时间和在各机床上的加工次序约束, 调度开始时间为0, 并且开始时刻各机器上没有任何的任务安排, 调度的目标是确定与工艺约束条件相容的各机器上所有工件加工开始时间和加工结束时间, 使得完成全部加工的总时间最少, 同时还应该满足下面的条件:( 1)同一设备在某一时刻只能处理一个任务( 2)每个任务不能同时在两台设备上被处理;( 3)每一任务的各个操作之间有确定的技术顺序约束;( 4)工序的处理一旦开始就不能被打断。3.3基本遗传算法的构造3.3.1编码编码问题是设计遗传算法的首要和关键问题, 遗传算法的编码技术必须考虑染色体0的合法性、可行性、有效性以及问题解空间表征的完全性。其中编码方式包括有基于操作的编码基于工件的编码、基于先后表的编码、基于工件对关系的编码和基于机器的编码等等。本文采用基于机器的编码, 下面以典型的作业车间调度问题( FT06)为例说明编码的过程:FT06为6个工件6台机床的作业调度问题, 各工件的技术约束和加工时间如表3-1所示, 为方便起见把各工件的编码从0 5改为1 6。表3-1 FT06的加工工艺约束和加工时间工件号第i道工序所在的加工机床号(加工时间)i=1i=2i=3i=4i=5i=613(1)1(3)2(6)4(7)6(3)5(6)22(8)3(5)5(10)6(10)1(10)4(4)33(5)4(4)6(8)1(9)2(1)5(7)42(5)1(5)3(5)4(3)5(8)6(9)53(9)2(3)5(5)6(4)1(3)4(1)62(3)4(3)6(9)1(10)5(4)3(1)由上述表格可以很简单的建立一个基于机器的工件加工顺序表如表3-2所示。表3-2 工件加工顺序工件号第i道工序所在的加工机床号(加工时间)i=1i=2i=3i=4i=5i=613( 4)1( 2)2( 5)6( 4)4( 2)5( 5)22( 1)3( 5)5( 2)4( 1)1( 3)6( 1)36( 6)4( 3)1( 1)5( 1)2( 2)3( 1)41( 4)4( 4)2( 6)6( 2)3( 2)5( 6)52( 3)1( 6)4( 5)6( 5)5( 3)3( 6)64( 6)2( 4)6( 3)3( 3)5( 4)1( 5)表3-2第一行指机器1上首先加工工件3的第4道工序, 然后加工工件1的第二道工序, 以此类推。FT06基于机器的编码就是建立长度为6* 6的染色体如表3-3所示(表中每个数字含义和表3-2相同):表3-3 染色体3( 4 )1( 2 )2( 5 )6 ( 4)4 ( 2)5( 5)2( 1 )3( 5 )5( 2 )4 ( 1)1 ( 3)6( 1)6( 6 )4( 3 )1( 1 )5 ( 1)2 ( 2)3( 1)1( 4 )4( 4 )2( 6 )6 ( 2)3 ( 2)5( 6)2( 3 )1( 6 )4( 5 )6 ( 5)5 ( 3)3( 6)4( 6 )2( 4 )6( 3 )3 ( 3)5 ( 4)1( 5)3.3.2 解码解码过程包括两部分, 首先对随机产生的调度方案进行机器工件队列之间的冲突消解, 然后在进行解码计算最终调度时间。1 基于机器编码的机器工件队列之间的冲突消解n* m 的Job-Shop调度问题就包含有( n! )m 个调度方案, 当采用基于机器的编码时, 调换各机器上加工工件顺序就可以得到不同的调度方案, 但是这种通过随机调换工件顺序而产生的调度方案不一定符合工件的实际加工要求和加工技术路线的约束, 当产生的调度方案和实际加工要求约束不符合时就有必要对该调度方案进行冲突消除。下面以FT06为例说明该冲突消解的过程:表3-2为一种随机产生的调度方案, 现在分析其中的工件3和工件6加工顺序约束:对于机器1: 工件3( 4)加工顺序应该优先于6( 4)对于机器2: 工件3( 5)加工顺序应该优先于6( 1)对于机器3: 工件6( 6)加工顺序应该优先于3( 1)对于机器4: 工件6( 2)加工顺序应该优先于3( 2)对于机器5: 工件6( 5)加工顺序应该优先于3( 6)对于机器6: 工件6( 3)加工顺序应该优先于3( 3)3( 1) 3( 2) 3( 3) 3( 4) 3( 5) 3( 6) 6( 1) 6( 2) 6( 3) 6( 4) 6( 5) 6( 6)图3-1 工件3和工件6的加工路线图在图3-1工件3和工件6的加工路线中, i ( j)表示工件i的第j 道工序, 这样可得到的技术路线为: 3( 1) 3( 2) 3( 3) 3( 4)6( 4) 6( 5) 6( 6) 3( 1), 这样显然是和实际加工矛盾的, 所以必须通过机器工件队列之间的冲突消解才能得到合理的调度方案, 冲突消除算法如下:设 D ( op ): 已处理工序集W ( op ): 待处理工序集op ( i, j)代表( 2)中第i行第j列处的工序step0: 置D ( op ) = , Wop = op ( i, j ) | i, j= 1 6;step1: 对设备k ( k= 1 6)的工序队列顺序扫描最前面的未调度工序op ( k, s), 若op ( k, s)为对应工件技术路线中当前待加工工序, 则转向step2; 否则step3;step2: 调度op ( k, s), 将op ( k, s)从W ( op )中删除并加入到D ( op ), 转向step3继续本轮扫描;step3: 若W ( op ) = , 转向steps5; 否则若本轮扫描已完成, 转向step4; step4: 若本轮有工序被调度, 转向step1开始新一轮调度; 否则, 找到W ( op )中距离末调度工序队列头最近的就绪工序(技术路线中的当前可加工工序), 交换至相应机床未调度工序队列之首, 转向step1继续扫描调度;step5: 结束;2. 最后解码计算最大调度时间其实计算调度时间的解码过程已经被嵌入到了冲突消除算法中, 在冲突消除算法中取出op ( k, s) 处理时, op ( k, s) 的起始时间为max 同一工件上道工序完成时间, 设备k 的最早可用时间, 通过这样的解码过程可以得到该调度方案最终的调度时间。3.4 初始种群的产生由于本文采用的是十进制的编码方式, 在这里采用一种/原型+ 随即扰动0的方法产生初始种群, 也就是在一个给定的合理的染色体的基础上, 产生两个随机数作为交换位置再交换两位置之间的基因, 进而产生新的染色体, 如表3-3中的第一行为:机器13（4）1(2)2(5)6(4)4(2)5（5）两随机数为2和4, 交换位置后为:机器13（4）6(4)2(5)1(2)4(2)5（5）3.5 选择操作常用的方法有比例选择、基于排名、和锦标赛选择, 这里采用比例选择的方法: 用正比于个体适应度值的概率来选择相应的个体, 随机产生数 0, 1 , 就按选择状态i来进行复制选择, 其中的f i为个体i适配值。3.6交叉操作本文采用单位置次序交叉: 只产生一个交叉位置,然后保留父代个体p1 交叉位置前的基因片段, 并在另一父代个体p 2 种删除p1 中保留的基因, 然后将剩余基因片段填入p 1 的交叉位置后进而生成后代个体q1 8 。如父代p 1 为 2 6 4 7 3 5 8 9 1 , p2 为 4 5 2 1 8 7 6 9 3 , 交叉位置为4, 则后代q1 为 2 6 4 7 5 1 8 9 3, q2为 4 5 2 1 6 7 3 8 9。3.7变异操作组合优化问题中的置换编码GA 通常采用互换、逆序和插入变异。本文采用逆序的方式进行变异操作, 即将染色体中两不同随机位置间的基因串逆序。如变异前为 2 6 4 7 3 5 8 9 1 , 两随机位置为2, 7, 变异后则为 2 8 5 3 7 4 6 9 1。表3-2的调度方案执行该冲突消除算法后得到的合理调度方案如表3-4所示。表3-4合理调度方案工件号第i道工序所在的加工机床号(加工时间)i=1i=2i=3i=4i=5i=611(2)4(2)2(5)6(4)3(4)5(5)22(1)4(1)1(3)5(2)6(1)3(5)31(1)5(1)4(3)2(2)3(4)6(6)41(4)4(4)2(6)6(2)3(2)5(6)52(3)1(6)4(5)5(3)6(5)3(6)61(5)2(4)4(6)6(3)3(3)5(4)3.8 动态车间调度在FMS实际加工环境下，当不可预知的事情发生时，原有的调度方案不得不中止，且调度系统必须及时地调整工件原有的加工路径和其他资源调度的状况，同时必须对突发事件做出迅速响应，以确保调度系统能够持续、优化地进行。这种能够引起原有调度方案的更改，从而需要采取动态调度措施的突发事件称之为动态事件，也称重调度因子或扰动【33】。动态事件的种类有很多，如表3-5所示，Suresh等人将动态事件分成以下种类。表3-5 动态事件类型调度类型调度的动态事件与工件相关工件随机到达工件订单变化加工时间不确定动态优先级调整交货期改变与机器相关机器故障机器的阻塞/死锁刀具的不可访问负载限制生产能力冲突与工序相关工序延迟质量问题产量不稳定其它情况原材料传输延迟原材料有缺陷操作员不在场动态路径规划等本文在采用自适应遗传算法求解FMS动态调度问题时，主要研究了与两种调度类型有关的几个动态事件（如急件到来、设备故障、订单取消）发生时，控制机制采取怎样的应对措施处理问题.3.9动态调度类型动态调度类型主要包括反馈调度、自适应调度、实时调度、离线与在线调度四种调度类型，具体描述如下：（1）反馈调度反馈调度是最近几年出现的一个新的概念，并没有统一的定义，它与动态调度没有大的区别。反馈调度是动态和随机环境下的调度，它主要强调环境变化时系统调度方案对突变环境的快速响应能力，因此可把反馈调度看成是动态调度的一种处理方式或响应机制。（2）自适应调度自适应调度是基于以下事实提出的:如果原来的调度有较好的调度效果和鲁棒性，则当动态扰动事件发生时，由于过于频繁的重调度不仅没有必要，而且很容易造成系统的不稳定，所以应尽量减少重调度的次数以尽可能的恢复原有调度。自适应调度可以看作是动态调度的一种实现思想。（3）实时调度实时调度是相对于批处理调度而言，强调在条件发生变化时系统能及时有效地做出反应。实时调度是典型的事件驱动方式。（4）在线调度和离线调度按照运行方式调度计划通常被分为在线调度和离线调度两类，在线调度要求在生产连续进行的情况下，对环境变化做出及时地响应，在线调度也是一种连续调度方式。相对于在线调度而言，离线调度则严格要执行调度计划，无视在计划形成之后发生的任何事件。这是一种容量受限的调度方法，预先计划好的调度时间轴上的资源分配给每个加工行为，在旧的调度方案执行完之前不会执行新的调度方案。调度计划通常采用实时或离线重调度的方法，离线重调度由于考虑了未来并产生了优化的调度而更具有优势。因此，本节采用了离线的重调度方法，并结合重调度两种生成方式求解FMS动态调度问题。3.10动态调度控制方法动态调度问题的处理方法是重调度的核心部分，针对不同的动态事件需采用不同的处理方式。根据以上对调度策略的研究，本文对急件到来和订单取消的动态调度问题采用的是再生式的重调度处理方式，而对设备故障的动态调度问题采用的是修正的处理方法。以下是三个常见的动态事件的具体处理方法：3.10.1急件到来急件到来时，采用再生式的重调度方法，此方法是通过对原调度方案中剩余未加工工序（不包括未完成的工序）的完全再生而产生新的调度任务数据，从而获得新的调度方案。在系统正常运行的某时刻不得不插入一个或者一批新的零件，与当前零件一起加工时，应对的措施是：扰动出现时刻，正在被加工的零件不能被中断，并假定这些零件的重调度是实时必须完成的；保留扰动出现时刻机器加工任务中的剩余工序和未完成工序的所有信息，并与新到达零件一起进行重调度；对已进行路径选择的零件保留其原有路径，紧急定单的优先级体现在分配给零件的更大的权值上。t时刻，急件到来判断各机床j的加工状态StateM=?机床处于Busy,计算剩余被占用时间更新调度任务数据，并对part和mach清0系统正常运行StateM=0StateM=1TjMax（t）,(t)Tjt形成新的调度方案机床处于Idle,剩余被占用时间0图3-2急件调度的流程图图中t表示扰动发生的时刻，Tj表示机床在重调度中最早访问时间，StateM表示机床的加工状态，表示机床剩余被占用的时间，表示一次重调度需要的近似计算时间，part表示某个工件的工序集合，mach表示某台机床的加工任务工序集合。急件到达的动态调度实现过程如下：系统按照周期调度策略正常运行。t时刻，紧急情况发生，一批新零件要求插入到当前零件中，与当前零件一起进行调度。判断各加工机器的加工状态StsteM，如果机器有未完成的工序，则计算其被继续占用的时间。如果StsteM=1，机床空闲，表明该机器可以执行新方案的重调度，则令其=0；如果StsteM=0，机床处于繁忙状态，计算机床继续被占用的时间，并且不中断正在加工的零件，假设其重调度是实时进行。在t到t+时间段内使机器完成原始方案中的当前工序，令为GA完成一次重调度的近似计算时间（本章设0），确定新调度方案中各个机器的最早访问时间为Tj：令处于空闲状态的机床（StsteM=1）重调度的初始访问时间Tjt；令处于繁忙状态的机床（StsteM=0）重调度的初始访问时间TjMax（t）,(t)。通过确定新方案中机器的最早访问时间，则可以将新调度方案与原调度方案有效衔接起来，从而有效地避免了工件冲突现象的发生。根据各工件的剩余工序（不包括当前未加工完成的工序）信息以及新零件的工序信息形成新的调度任务数据：对所有工件的当前工序集合Part以及所有机床当前加工任务工序集合mach进行清0，剔除原有数据表中已加工完成的工序信息；添加新零件的所有工序信息到剩余工序任务数据表中，形成新的调度任务数据，并统计新调度任务数据表中的工序数、工件数以及需求的设备数量。根据新的调度任务数据表形成新的调度方案，并采用遗传算法对其进行优化。如上图3-2所示，表示急件动态调度的流程图。3.10.2机器故障机器故障时，如果机器不能修复正常使用的话，采用对剩余工序进行修订的重调度方式。具体处理措施如下：如果不能及时修复的故障机器有同类型机器，那么重调度机制将故障机器加工任务中所有剩余工序（不包括未完成工序）移到某台同类机器上；然后将所有与故障机器及其同类机器有关的剩余工序，重新组成新的工序队列进行重调度；保留扰动出现时刻机器加工任务中的剩余工序和未完成工序的所有加工信息。如果故障机器没有同类机器，表明该机器加工任务中的所有剩余工序均不能继续加工，则删除与其有关的所有工序。如果故障机器上存在未加工完成的工序，那么删除旧的调度任务数据中与该工序所属的零件有关的所有工序信息。如果故障机器被及时修复，该机器又成为可利用的生产资源，为使系统的生产资源得到充分地利用，应使它尽快地投入生产，并参与加工系统的重新调度。t时刻，机床M发生故障把mach中的剩余工序添加到mach中，并在系统中删除mach机床处于Busy,计算剩余被占用时间更新调度任务数据，并对part和mach清0系统正常运行StateM=0StateM=1机床处于Idle,剩余被占用时间0TMax（t）,(t)Tt形成新的调度方案判断机床M有无同类型机床MY判断正常机床的加工状态StateM=?删除与M有关的所有工序信息N图3-3机器故障动态调度的流程图图中t表示扰动发生的时刻，M表示出现故障的机床，M表示故障机床M的同类机床，Tj表示机床在重调度中最早访问时间。设备故障的动态调度实现过程如下：系统按照周期调度策略正常运行。t时刻，突发事件出现，其中机床M发生故障，且不能及时修复。判断故障机床M是否存在同类型的机床，如果存在，则把机床M加工任务工序集合mach中的所有剩余工序（不包括未加工完成工序）添加到其同类机床M加工任务工序集合mach中，并在系统中删除故障机床加工任务工序集合mach。如果故障机床M没有同类机床，表明机床M加工任务中的所有剩余工序均不能继续加工，则删除与其有关的所有工序。判断各加工机器的加工状态StsteM，如果机器有未完成的工序还必须计算其被继续占用的时间。如果StsteM=1，机床空闲，表明该机器可以执行新方案的重调度，则令其=0；如果StsteM=0，机床处于繁忙状态，计算机床继续被占用的时间，并且不中断正在加工的零件，假设重调度实时进行。在t到t+时间段内使机器完成原始方案中的当前工序，令为GA完成一次重调度的近似计算时间，确定新调度方案中各个机器的最早访问时间为Tj：令处于空闲状态机床重调度的初始访问时间Tjt；令处于繁忙状态机床（StsteM=0）重调度的初始访问时间TjMax（t）,(t)。如果故障机床M上存在未加工完成的工序，那么删除原有调度任务表中与该工序所属的零件有关的所有工序信息。对所有工件的工序集合Part以及所有机床加工任务工序集合mach进行清0，剔除原有数据表中已加工完成的工序信息，根据各工件的剩余工序信息形成新的调度任务数据表，并统计新调度任务数据表中的工序数、工件数以及需求的设备数量。根据新的调度任务数据表形成新的调度方案，并采用遗传算法对其进行优化。机器故障动态调度的流程如上图3-3所示3.10.3订单取消订单取消的动态事件采用再生的重调度方式。即系统正常工作，t时刻，某种未加工或正在被加工的零件突然要求被取消任务，具体处理措施如下：该零件不再占用机床设备，且必须从加工任务中删除被指定为取消的订单。所有正在机床上被加工的零件（要求被取消的零件除外）不被中断，且假定这些零件的重调度是实时完成的。保留扰动出现时刻机器加工任务中的剩余工序和未完成工序（要求被取消的工序除外）的所有信息，把机床上所有剩余未加工工序（不包括当前未加工完成的工序）作为新的调度对象进行重调度。订单取消的动态调度实现过程如下：系统按照周期调度正常运行。t时刻，突发事件出现，要求取消零件i的加工任务。判断零件i在系统中的加工状态StstePi，如果StstePi2，说明该零件已经加工完毕，则系统继续工作；如果StstePi0或1，说明该零件正在被加工或者处于等待加工状态，则删除零件i在机床加工任务中的所有有关信息，并在系统中删除零件i的工序集合parti。t时刻，要求取消零件i机床处于Busy,计算剩余被占用时间更新调度任务数据，并对part和mach清0系统正常运行StateM=0StateM=1机床处于Idle,剩余被占用时间0TMax（t）,(t)Tt形成新的调度方案判断零件i的加工状态StstePi=?StstePi=0或1StstePi=2系统继续工作删除零件i的所有加工信息和parti判断正常机床的加工状态StateM=?图3-4订单取消调度的流程图判断各加工机器的加工状态StsteM，如果机器有未完成的工序还必须计算其被继续占用的时间。如果StsteM=1，机床空闲，表明该机器可以执行新方案的重调度，则令其=0；如果StsteM=0，说明机床处于繁忙状态，计算机床继续被占用的时间，并且不中断正在加工的零件，假设重调度实时进行。在t到t+时间段内使机器完成原始方案中的当前工序，令为GA完成一次重调度的近似计算时间，确定新调度方案中各个机器的最早访问时间为Tj：令处于空闲状态的机床（StsteM=1）重调度的初始访问时间Tjt；令处于繁忙状态的机床（StsteM=0）重调度的初始访问时间TjMax（t）,(t)。对所有剩余工件的当前工序集合Part以及所有机床当前加工任务工序集合mach进行清0，剔除原有数据表中已加工完成的工序信息；根据各工件的剩余工序信息形成新的调度任务数据表，并统计新调度任务数据表中的工序数、工件数以及需求的设备数量。根据新的调度任务数据表形成新的调度方案，并采用遗传算法对其进行优化。订单取消调度的流程如上图3-4所示。3.11应用实例FMS车间有4台机床，分3种类型，其中机床1和机床2属于同类型。在考虑机床一种资源的情况下，计划在某时间段（单位：min）完成7种零件共20道工序的加工，加工任务如表3-6所示。FMS生产环境下，根据本章对几种动态调度控制方法的研究，运用自适应交叉、变异的遗传算法对工序进行寻优排序。以最小化工件交货延迟时间的加权平方和为评价函数，设每个工件的交货期均为30，每台机床的开始处理时间为0。表3-6 调度任务数据表工件工序机器类型工序关系加工时间工序初始状态111/21 32120239031/2502*444 56051/260361/26 7 880745083904*91/29 1040104605113 1211 13100121/2501331006*141/2 15 14 16 17 18701548016350171/260181/270719319 206020480系统按原有最佳调度方案正常运行，各机器按此调度计划向前推进生产，FMS系统的控制级监视各机器的进度以及各类事件的突发。试验通过仿真来模拟这一实际进程，这里考虑了三类常见的扰动因子，分别为机器故障、紧急订单以及取消订单。各扰动因子的作用对象以随机方式产生。现以t=5时刻出现上述任意一种扰动因子为例。设交货期为30，假定完成一次重调度的时间0，种群规模popsize=40，进化代数为100（1）急件到来表3-7 新任务数据表工件号工序号设备号加工时间8211/298221/212823311924459251/289261/21092731610284710291/21110301/261031318103249图3-5增加的新零件t=5时刻，增加3个零件（如表3-7，图3-5所示，零件8、9、10，共包含12道工序），这时机床m2和m4处于“busy”状态，而m1和m3在t=5时刻正处“idle”状态，因此机床m2和m4继续加工其当前工序。如图3-8所示，机床m2正在加工当前工序14（工件6），其剩余加工时间为2分钟；机床m4正在加工当前工序4（工件2），其剩余加工时间为1分钟；机床m1空闲，机床m3上的工序7刚好加工完毕。由于t=5时刻动态事件发生，即要增加零件8、9、10，根据事件对系统造成的影响程度判断是否进行重调度，任务数据及时地进行自动更新，最终只保留了需要参加重调度的剩余工序信息和系统资源数据信息，遗传算法依据新的调度任务数据快速优化出新的调度方案。在t=5时刻，只有机床m1和m3可以开始执行新方案。而其它两台机床只有等到当前工序14和4加工结束后，才开始执行新的调度方案；各个机床的新调度方案开始生效时刻分别为t=5，t=7，t=5，t=6。目标函数值为Fun=368.5，程序执行的时间为30秒。增加3个工件后的动态调度的工序开始和完工时间如表3-8所示；所得到的新调度方案如图3-8所示，表示其调度结果的Gantt图。最佳调度方案：2 29 8 24 30 19 21 10 11 6 15 32 5 17 28 16 20 23 12 31 22 25 1 18 3 13 26 27表3-8 最佳调度方案中工序的开始和结束时间设备号工序号开始和结束时间设备号工序号开始和结束时间234423123234112298243019211011615325177，165，166，1515，2016，225，1116，2522，2811，2128，3621，2922，3125，3131，37444343211231232816202312312225118313262731，3838，4343，5129，3651，5638，5636，4237，4545，5743，5056，6157，6750，6061，77图3-8 急件到来的调度Gantt图（2）取消订单当t=5时刻，取消工件1，此时所得到的新调度方案如图3-9所示，表示其调度结果Gantt图，表3-9表示取消订单后的最佳调度方案中工序的开始和结束时间；目标函数值Fun=464；程序执行的时间为25秒。最佳调度方案：11 17 18 13 8 6 16 15 5 19 12 10 20如图3-9所示，各机床在重调度中的理论开始访问时间为5、7、5、6，但由于工件1的取消而对系统调度方案造成的影响，因而进行一次重调度后获得的最佳调度方案中工序的加工顺序以及工序在机床上的相对加工顺序发生了变化，使得重调度中机床m1和m2的实际开始访问时间为7、13。从图中可以看出，在新的调度方案中，因为工序17必须等待其所属的工件6的工序集合中先于它调度的上一当工序14加工完毕才能开始加工，从而导致机床m1初始访问时间为工序14的加工结束时间；同样，工序18必须等待工序17加工完毕才能开始加工，从而导致机床m2初始访问时间为工序17的加工结束时间。表3-9最佳调度方案中工序的开始和结束时间设备号工序号开始和结束时间设备号工序号开始和结束时间31214241117181386165，157，1313，2015，256，1520，2820，253134241551912102025，3325，3133，3925，3028，3439，47图3-9取消工件1后的调度Gantt图（3）设备故障当t=5时刻，机床m2发生故障且不能及时修复，此时所得到的新调度方案如图3-10所示，表示其调度结果Gantt图；表3-10表示设备故障后的最佳调度方案中工序的开始和结束时间；目标函数植为Fun=1435；程序执行的时间为35秒。最佳调度方案：11 19 12 2 1 5 10 20 3 8 6 13如图3-10所示，各机床在重调度中的理论开始访问时间为5、5、7，但由于机床m2出现故障而对系统调度方案造成的影响，使得重调度中机床m4的实际初始访问时间为15。从图中可以看出，在新的调度方案中，因为工序12必须等待其所属的工件5的工序集中先于它调度的上一当工序11加工完毕才能开始加工，从而导致机床m4的初始访问时间为工序11的加工结束时间。此外，故障机床m2的剩余工序2、6、10、已经转移到它的同类机床m1上，而与机床m2上未加工完成工序14有关的所有信息已经不存在。表3-10最佳调度方案中工序的开始和结束时设备号工序号开始和结束时间设备号工序号开始和结束时间3341111119122155，1515，2115，205，1414，2626，3214341110203861332，3821，2926，3129，3838，4646，56图3-10 机床2出现故障后的调度甘特图总之，从以上Gantt图3-8、3-9、3-10可看出，自适应遗传算法对动态调度问题的优化是有效的，可求得问题的最优调度方案。但对于图3-8，因为新零件的加入使得工件的生产周期（77分钟）比原有调度的生产周期（44分钟）增加了33分钟；图3-9，3-10中由于订单的取消和设备故障的出现而影响到调度算法的性能，机床出现了许多空闲的时间，使得调度结果不是很理想。第四章C语言相关知识及编程4.1 C语言相关知识C语言是一种计算机程序设计语言。它既具有高级语言的特点，又具有汇编语言的特点。它由美国贝尔研究所的D.M.Ritchie于1972年推出。1978后，C语言已先后被移植到大、中、小及微型机上。它可以作为工作系统设计语言，编写系统应用程序，也可以作为应用程序设计语言，编写不依赖计算机硬件的应用程序。它的应用范围广泛，具备很强的数据处理能力，不仅仅是在软件开发上，而且各类科研都需要用到C语言，适于编写系统软件，三维，二维图形和动画。C语言的祖先是BCPL语言。 1967年，剑桥大学的 Martin Richards 对CPL语言进行了简化，于是产生了BCPL（Basic Combined Programming Language)语言。 1970年，美国贝尔实验室的 Ken Thompson。以BCPL语言为基础，设计出很简单且很接近硬件的B语言（取BCPL的首字母）。并且他用B语言写了第一个UNIX操作系统。在1972年，美国贝尔实验室的 D.M.Ritchie 在B语言的基础上最终设计出了一种新的语言，他取了BCPL的第二个字母作为这种语言的名字，这就是C语言。为了使UNIX操作系统推广，1977年Dennis M.Ritchie发表了不依赖于具体机器系统的C语言编译文本可移植的C语言编译程序。 1978年由美国电话电报公司(AT&T)贝尔实验室正式发表了C语言。同时由B.W.Kernighan和D.M.Ritchie合著了著名的The C Programming Language一书。通常简称为K&R，也有人称之为K&R标准。但是，在K&R中并没有定义一个完整的标准C语言，后来由美国国家标准化协会（American National Standards Institute）在此基础上制定了一个C语言标准，于一九八三年发表。通常称之为ANSI C。4.2 C语言程序的特点1C是高级语言。它把高级语言的基本结构和语句与低级语言的实用性结合起来。C 语言可以像汇编语言一样对位、字节和地址进行操作，而这三者是计算机最基本的工作单元。 2C是结构式语言。结构式语言的显著特点是代码及数据的分隔化，即程序的各个部分除了必要的信息交流外彼此独立。这种结构化方式可使程序层次清晰，便于使用、维护以及调试。C 语言是以函数形式提供给用户的，这些函数可方便的调用，并具有多种循环、条件语句控制程序流向，从而使程序完全结构化。 3C语言功能齐全。具有各种各样的数据类型，并引入了指针概念，可使程序效率更高。而且计算功能、逻辑判断功能也比较强大，可以实现决策目的的游戏。 4C语言适用范围大。适合于多种操作系统，如Windows、DOS、UNIX等等；也适用于多种机型。 C语言对编写需要硬件进行操作的场合，明显优于其它高级语言，有一些大型应用软件也是用C语言编写的。4.3 C语言程序的开发步骤针对一个实际问题，用C语言设计一个实用程序时，通常要经过如下五个开发步骤：1.用户需求分析根据要解决的实际问题，分析用户的所有需求，并用合适的方法、工具进行详细的描述。2.根据用户的要求，设计C源程序利用C的集成环境或某一种文件编辑器将设计好的源程序输入到计算机中的一个文件中，文件的扩展名为.cpp。3.编译源程序文件，并产生目标程序在编译源程序文件时，若发生语法或语义错误时，要修改源程序文件，直到没有编译错误为止。编译后，为源程序产生了目标文件。在PC机上，目标程序文件的扩展名为.obj。4.将目标文件连接成可执行文件将一个或多个目标程序与库函数连接后，可产生一个执行文件。在PC机上，可执行文件的扩展名为.exe。5.调试程序运行可执行文件，输入测试数据，并分析运行结果。若运行结果不正确，则要修改源程序，并重复以上的过程，直到得到正确的结果为止。4.4 C语言编程为了体现使用规则优化的结果并验证其实用性和正确性，将动态调度遗传算法编写为C语言程序，得出最优解，证明遗传算法的可行性。遗传算法主程序如下：/ GA.cpp : Defines the entry point for the console application./#include stdlib.h#include stdafx.h#include math.h#include stdio.h#include time.h#define PI 3.1415926#define accurate 6 /定义保留小数点后的精度#define low -1/定义解区间下界#define high 2/定义解区间上界#define size 40 / 定义种群数目int length=log(high-low)*pow(10,accurate)/log(2)+1; / 定义每条染色体长度double fitnesssize;/ 定义适应值数组double fitmax=0;double xsize;/ 定义对应染色体从二进制转换成十进制数的数组double tsize;/定义对应十进制转换到阈值空间的实数数组 #define pc 0.8 / 定义交叉率#define pm 0.01 /定义变异率int *chro;/ 所有种群的染色体数组/* 计算适应值函数*/void Computefitness()int i,j;for(i=0;isize;i+) xi=0;/ printf(%dn,xi);for(i=0;isize;i+) for(j=0;jlength;j+)xi=xi+chroij*pow(2,length-j-1);/ 将每条染色体转换成为十进制数存入想xi/ printf(x%d是%lfn,i,xi);for(i=0;ifitmax) fitmax=fitnessi;printf(实数值是：%lfn,ti);printf(该实数对应的染色体的目前最大适应值是：%lfn,fitmax);void Intial() chro=new int*size;int i,j;for(i=0;isize;i+)chroi=new intlength;srand(unsigned)time( NULL );/* 产生所需要的染色体*/for(i=0;isize;i+)for(j=0;jlength;j+)chroij=rand()%2;/ 每一位基因随机为0或1/ printf(%d,chroij);/ printf(n);/ 显示所有染色体Computefitness();void ChroShow()int i,j;for(i=0;isize;i+)for(j=0;jlength;j+)/ printf(%d,chroij);/ printf(n);/ 显示所有染色体void SelectionOp()int i,j; /step1 Calculate the total fitness F for the populationdouble f=0;for(i=0;isize;i+)f+=fitnessi;/ printf(适应值总和为%lfn,f);/step2 Calculate selection probability pk for each chromosome vkdouble psize;for(i=0;isize;i+)pi=fitnessi/f;/ printf(P%d是：%lfn,i+1,pi);/step3 Calculate cumulative probability qk for each chromosome vk.double qsize;for(i=1;isize;i+)qi=0;q0=p0;/ printf(q0是：%lfn,q0);for(j=1;jsize;j+) for(i=0;ij;i+) qj=qj-1+pj;/ printf(q%d是：%lfn,i,qj);/ step 4: Generate a random number r from the range 0,1.double rsize;for(i=0;isize;i+) ri=(double)rand()/RAND_MAX;/ printf(r%d是：%lfn,i+1,ri);/step 5：根据q数组和r数组每个数的大小进行染色体选择int *v;v=new int*size;for(i=0;isize;i+)vi=new intlength;/ 产生一个新的存储染色体的数组vfor(i=0;isize;i+)for(j=0;jlength;j+)vij=chroij;/ 赋上chro初始值for(i=0;isize;i+) for(j=0;jsize;j+)if( ri=qj)for(int k=0;klength;k+)vik=chrojk;/ 赋值给新的染色体数组break; for(i=0;isize;i+)for(j=0;jlength;j+)chroij=vij;/ 将临时的v转换到chro数组/ 显示所有染色体/ printf(*选择以后的染色体显示*n);/ ChroShow();Computefitness();/* 交差函数 */*/void CrossOver()int i,j,k;for(k=0;k=(double)rand()/RAND_MAX)i=j=0;while(i=j)i=rand()%size;/ 0到size-1j=rand()%size;/ printf(i是%d j是%dn,i,j);int p=rand()%(size-2)+1;/ p是从下标1到size-1/ printf(p是%dn,p);/ 进行两个染色体的裁剪交差for(int m=p-1;mlength;m+)int alt;alt=chroim;chroim=chrojm;chrojm=alt;/ printf(*交叉以后的染色体显示*n);/ ChroShow();/*进行变异*/void Mutation()int i,j;for( i=0;isize;i+)for(j=0;j(double)rand()/RAND_MAX)/ printf(%d的%d位置发生变异!n,i+1,j+1);chroij=1-chroij;/ printf(*变异以后的染色体显示*n);/ ChroShow();int main(int argc, char* argv)Intial();/初始化int step=0;while(step10000)SelectionOp();/ 选择CrossOver();/交差Mutation();/变异step+;printf(最小值是：%lfn,fitmax);return 0;4.5 输出结果1. 急件到来 2.取消订单 4. 设备故障由C语言输出结果得到最佳工序调度方案，从而实现各工序之间的顺序加工，上文所举的动态事件调度方案得到优化，与未调度之前相比，提高了机床的利用率，缩短

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

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