蚁群算法的改进及其在生产调度中的应用

VIP免费
3.0 陈辉 2024-11-19 4 4 1.03MB 81 页 15积分
侵权投诉
I
目 录
中文摘要
ABSTRACT
第一章 绪 论 ........................................................ 1
§1.1 课题的来源及意义 ............................................. 1
§1.2 车间调度问题 ................................................. 2
§1.2.1 车间调度问题的描述 ....................................... 2
§1.2.2 车间调度问题的分类 ....................................... 3
§1.2.3 车间调度问题的研究进展 ................................... 4
§1.3 本文主要研究的内容 ........................................... 6
第二章 蚁群算法的基本原理 ........................................... 8
§2.1 引言 ......................................................... 8
§2.2 蚁群算法原理 ................................................. 8
§2.3 蚁群算法基本流程 ............................................ 11
§2.4 蚁群算法的特点 .............................................. 13
第三章 基于思维进化的蚁群算法 ...................................... 14
§3.1 引言 ........................................................ 14
§3.2 思维进化算法 ................................................ 14
§3.3 基于思维进化的蚁群算法 ...................................... 15
§3.4 旅行商问题算例 .............................................. 16
§3.5 本章小结 .................................................... 18
第四章 典型 Job shop 调度问题蚁群算法研究 ........................... 19
§4.1 引言 ........................................................ 19
§4.2 典型 Job shop 问题描述和模型 ................................. 19
§4.2.1 典型 Job shop 问题描述 ................................... 19
§4.2.2 典型 Job shop 整数规划模型 ............................... 20
§4.2.3 典型 Job shop 析取图模型 ................................. 20
§4.3 面向典型 Job shop 的蚁群算法研究 ............................. 21
§4.3.1 解构造过程 .............................................. 21
II
§4.3.2 面向 Job shop 调度问题的基本蚁群算法描述 ................. 22
§4.3.3 改进蚁群算法设计 ........................................ 23
§4.3.4 求解 Job shop 调度问题的基于思维进化改进蚁群算法 ......... 25
§4.4 仿真测试及分析 .............................................. 28
§4.4.1 仿真 1 ................................................... 28
§4.4.2 仿真 2 ................................................... 30
§4.5 本章小结 .................................................... 33
第五章 Flow shop 调度问题蚁群算法研究 .............................. 34
§5.1 引言 ........................................................ 34
§5.2 置换 Flow shop 问题描述及数学模型 ............................ 34
§5.2.1 Flow shop 问题描述 ....................................... 34
§5.2.2 Flow shop 问题整数规划模型 ............................... 35
§5.2.3 Flow shop 问题析取图模型 ................................. 35
§5.3 面向 Flow shop 问题的蚁群算法研究 ............................ 36
§5.3.1 解构造过程 .............................................. 36
§5.3.2 面向 Flow shop 调度问题的基本蚁群算法描述 ................ 37
§5.3.3 改进蚁群算法设计 ........................................ 38
§5.3.4 求解 Flow shop 调度问题的基于思维进化改进蚁群算法 ........ 40
§5.4 仿真测试及分析 .............................................. 41
§5.5 多目标 Flow shop 调度及其蚁群算法 ............................ 43
§5.6 本章小结 .................................................... 44
第六章 半导体炉管区批调度蚁群算法研究 .............................. 45
§6.1 引言 ........................................................ 45
§6.2 问题描述和数学模型 .......................................... 46
§6.2.1 问题描述 ................................................ 46
§6.2.2 数学模型 ................................................ 47
§6.3 解决半导体炉管调度的混合蚁群算法 ............................ 49
§6.3.1 解构造策略 .............................................. 49
§6.3.2 状态转移规则 ............................................ 51
§6.3.3 信息素更新策略 .......................................... 52
§6.3.4 算法描述 ................................................ 53
§6.4 实验算例 .................................................... 55
III
§6.5 本章小结 .................................................... 60
第七章 总结与展望 .................................................. 61
附 录 ............................................................... 62
参考文献 ............................................................ 75
在读期间公开发表的论文和承担科研项目及取得成果 ...................... 79
致 谢 ............................................................... 80
第一章 绪 论
1
第一章 绪 论
§1.1 课题的来源及意义
制造业是国民经济的物质基础和工业化的产业主体，是社会进步与富民强国
之本。改革开放三十年以来，中国依靠政府优惠政策、国内巨大的消费市场和廉
价劳动力成本，成功的吸引了国外先进技术和雄厚资本进入，经济规模跃居世界
前列，经济实力得到明显增强。今天的中国享受着“世界工厂”的美誉。“中国
制造”凭借物美价廉的优势，在世界每个角落几乎随处可见，“中国制造”已经
行销全球。据统计，在工业制成品中，中国已有超过 130 种产品的产量位居世界
第一。
我国制造业的发展取得了举世瞩目的成绩，但仍与发达国家存在着较大的差
距。由于诸多原因，如劳动生产率比较低，资源消耗严重、利用率低；产品以低
端为主，附加价值不高，竞争力不强；自主知识产权缺乏，创新能力不强等等，
中国只不过是国际产业链的分工里利润最薄的一环，中国制造业还处在大而不强
的局面。
随着科学技术的发展，市场竞争也越来越激烈，对企业的管理和对生产过程
的监控都提出了更高的要求。中国制造企业正在失去以前所依赖的低价竞争优势，
进行产业升级和结构调整，引入先进的管理思想和技术，降低制造成本，发掘新
的利润增长点，是中国制造企业面临的挑战。
在21 世纪，随着电子、信息等高新技术的不断发展，随着市场需求个性化与
多样化，先进制造技术发展的总趋势是向精密化、柔性化、网络化、虚拟化、智
能化、清洁化、集成化、全球化的方向发展。我国在工业化进程中恰逢信息化兴
起，信息技术的勃兴、渗透和催化为我国走新型工业化道路提供了难得的历史机
遇。以信息化带动工业化，走新型工业化道路，大力推进信息化与工业化融合，
其重要途径就是用现代信息技术改造传统产业，实现工业生产过程和经营管理的
自动控制。
国外的先进制造理念和技术已在国内被广泛接受及应用，如准时制生产思想
（JIT）、约束理论（TOC）、计算机集成制造系统（CIMS）、智能制造技术（IMT）、
智能制造系统（IMS）、敏捷制造（AM）等等。人们正试图将信息技术、管理技术
与工艺技术紧密结合，创造出先进的制造生产模式。
如今，随着全球化市场的形成，制造业企业之间的竞争越来越激烈。竞争使
各种产品寿命周期越来越短，产品品种数飞速膨胀，以往的大批量小品种的生产
蚁群算法的改进及其在生产调度中的应用
2
模式渐渐变成了小批量多品种的生产模式；不但每天的生产品种在不断地改变，
就连已经安排好的调度计划也会由于客户需求的突然改变而改变；以及随时可能
发生的诸如机床设备突然损坏等等情况，使得生产加工环境不断改变。面对这些
变化，要使企业的生产能力和效率始终保持较高的水平，如何较好地解决生产管
理这一问题是当前企业界与学术界都十分紧迫的任务之一。
生产计划与调度是生产管理的核心与最关键的部分，它直接关系着企业的产
出效率和生产成本，有效的计划与调度算法结合详细准确的外围信息能最大限度
地提高企业的效益，满足客户的需求。
对生产调度问题的研究源于上世纪 50 年代，生产调度是个交叉性研究领域，
涉及运筹、数学、计算机工程、控制工程、工业工程等多个学科相关知识。对企
业来说，生产过程中合理排产与调度对提高设备利用率，消除生产瓶颈，加快生
产进程，减小库存，降低成本等都起着重要的意义。生产调度问题一直以来都是
一种未能很好解决的理论难题，对生产调度问题的研究，吸引了国内外许多学者
和实际生产调度人员的关注。
同时，车间生产调度问题大部分属于 NP-hard 问题，这类问题描述相对容易，
但是求解非常困难。对 NP-hard 问题，目前常用随机搜索算法或智能启发式算法求
解，如遗传算法、蚂蚁算法、微粒群算法等等。对生产调度问题进行研究不仅可
以探索实用和有效的算法，推进相关算法的研究，而且还能在此基础上提出新的
算法，为其它领域类似问题的解决提供条件和手段。因此对生产调度问题进行研
究，不仅具有重要的现实意义，而且还具有相当大的理论意义。
§1.2 车间调度问题
§1.2.1 车间调度问题的描述
生产调度是生产管理的核心内容和关键技术，它是在时间和空间上合理配置
系统的有限可用资源，以满足某个性能指标集的要求，针对一项可分解的工作（如
产品制造），探讨在一定约束条件下，如何安排其组成部分（如操作）的资源占用、
加工时间及先后顺序，以获得产品制造时间或成本的最优化。理论研究中，生产
调度问题又称为排序问题或资源分配问题。在实际生产领域中，生产调度问题则
被称作生产作业计划。
典型的调度问题包括需要完成的工件集合，每个工件的一系列工序操作集合，
各个工序操作加工需要占用的设备或其他资源，并且必须按照一定的加工路线来
进行加工。而目标是指合理地安排机器和工件，满足约束条件，使一些例如工件
第一章 绪 论
3
总加工时间、工件的延误程度、总资源占用等的性能指标达到最优。
车间调度问题有以下几个特点：
1.计算复杂性大部分车间调度问题具有NP-Hard特性，因而计算复杂度高。动
态随机性制造系统的加工环境是不断变化的，在运行过程中会遇到多种随机干扰，
故生产调度过程是一个动态的随机过程。
2.多目标性实际的车间调度问题是多目标的，并且这些目标之间往往会发生
冲突。
3.多约束性车间调度受到多种加工资源的制约如加工机床、操作工人、运输
小车、刀具以及其它辅助生产工具等。
车间调度问题的优化目标是评价调度方案优劣的标准，常见的调度指标有：
1.反映调度成本的指标调度中发生的费用有：启动成本、换线成本、工人加
班费用、过期赔偿费用、在线库存费用、调度管理费用等。由于调度净现值指标
能综合反映上述费用，所以得到了广泛应用。
2.反映调度性能的指标包括：生产周期、平均流动时间、机床利用率、工人
利用率等。
3.反映用户要求的指标包括：最大拖期时间、平均拖期时间、拖期零件的数
量等。
§1.2.2 车间调度问题的分类
生产调度按照不同的分类标准[1]，有不同的分类方式，下面是一些典型的分类：
按生产需求的不同，可分为Open shop和Closed shop。Open shop是指所有的生
产由客户需求来决定，无成品库存贮备；Closed shop问题是指客户的需求由成品库
存贮备来满足，而生产任务由库存量来决定，在封闭车间问题（限制资源的排序
问题）中，主要任务是确定批量大小（Lot-sizing），当一组工件批量的大小确定之
后，应用在开放车间的排序算法就可以确定其调度顺序。
按系统处理的复杂性，可分为单机、多机并行、Flow shop和Job shop。单机指
的是所有工件均需在指定的单台机器上加工完成，即单机排序问题；多机并行指
的是能够完成某种功能的机器不止一台，即并行机排序问题；Flow shop是指所有
的产品都经过相同的处理单元和处理路径，但不同产品在同一处理单元上的处理
时间可能不同，这也叫多产品（Multi-products）生产过程：而Job shop则指每个工
件的加工路线都不相同的多机排序问题，也叫多目的（Multi-purposes）生产过程。
基于性能指标，可分为基于调度费用和调度性能的指标两大类。常用的主要
有使生产所有工件的总时间（Make span）最少；使所有工件的平均驻留时间（Mean
蚁群算法的改进及其在生产调度中的应用
4
Flow Time）最少；使最大或平均的延滞（Maximum/Mean Tardiness）最小（其中
延 滞 指 产 品 完 成 日 期 和 它 的 交 货 日 期 之 差 的 绝 对 值 ）； 使 切 换 或 装 配
（Changeover/Setup）的次数（费用）最少；使生产总成本（包括各种生产费用，
库存贮备费用，切换损耗等）最低。
按调度环境的特点，可分为静态调度和动态调度。静态调度是指待加工的工
件集合和加工时间是确定的，且生产时全部待加工的工件己经全部到位，即静态
调度要求利用整个生产系统的全部信息，是信息完全的调度；而动态调度是指加
工工件的数目和相关的参数是随时间变化的，由于生产系统的各种信息不可能完
全获得，所以是信息不完全的一类调度，它不是一下子产生全天的作业调度单，
而是根据现场实时信息产生调度命令序列。静态调度在使用时，又有预调度和再
调度的区别。预调度是指在加工前，预先依次排定各个工件的加工步骤以及所需
资源，因此，它只涉及生产计划、工艺计划和资源特征等静态信息。但是，生产
中各种情况在不断地变化，使预计的调度命令不能完全按原计划执行，结果发生
偏差。因此，预调度只能为实际生产提供参考，当偏差积累到一定程度时，可触
发调度在新的时间和状态起点上重新做一遍调度，其结果可能是回到原来的预调
度，也可能是达到目标的另一条途径，运行过程中计划的突然变更或系统内部的
意外改变都可能启动“再调度”，但再调度持续的时间不能过长，次数也受到限制。
按是否考虑不确定性因素，可分为确定性调度和不确定性的调度两类。确定
条件下的调度是指调度中所用的参数都是确定的数值，建立的数学模型较为简单，
处理起来也比较简单，但适用的范围较小。不确定性条件下的调度是指生产过程
中的某些参数不是固定不变的，而是与处理批量的大小、处理时的反应温度、液
体的流速和反应罐内的压力等因素有关。
按生产企业的过程特征，可分为离散型、批量间歇型和连续型三类。离散过
程生产调度的任务是合理安排加工顺序，取得满足交货期、机器利用率、加工时
间等的个体最优或综合最优。间歇过程生产调度的特点是间歇的生产成批产品，
分阶段使用设备，同时生产的品种多、批量多，许多资源是有限且共享的，而且
各品种需要完成的日期也不同。连续生产过程常常指生产过程不存在间断的生产，
其调度方案一般要在生产未开始时就制定，一旦生产开始调度方案就一直有效。
在现代连续过程行业，生产调度系统主要由静态调度、动态调度、动态监控和统
计报告四大功能模块组成，其中动态调度模块是整个调度系统得以实现的关键。
§1.2.3 车间调度问题的研究进展
车间调度问题大部分都是NP-Hard问题。对于NP-Hard问题求解所消耗的时间
第一章 绪 论
5
随着问题规模增大而呈指数增长。由于这种问题描述容易，但求解却非常困难，
因此在许多工程应用问题中都有所反映，因此吸引着众多的科学研究者。1954年，
Johnson研究了两台机床的流水车间调度问题[2]，这标志着调度理论研究的开始。
在对于车间调度问题进行研究的方法上，最初是集中在整数规划、仿真和简单的
规则上，这些方法不是调度结果不理想就是难以解决复杂的问题。随着各种新的
相关学科与优化技术的建立与发展，在调度领域也出现了许多新的优化方法，比
如人工神经网络，模拟退火法，遗传算法，禁忌搜索算法以及蚁群算法等，使得
调度问题的研究方法向多元化方向发展。
调度优化算法总体上可分为精确求解方法和近似求解方法[3]。
精确求解方法一般有解析方法、穷举法、分支定界法等。此类方法对小规模
调度问题比较有效，但对大规模问题计算量和存储量难以满足。近似求解方法如
构造法、启发式方法、随机搜索方法等，由于可以快速找到满意解，在生产调度
领域受到广泛的重视和研究，而且各种混合式搜索方法在许多组合优化领域均得
到广泛的应用。
构造性方法如CDS（Campbell-Dudek-Smith）法、NEH（Nawaz-Enscore-Ham）
法[4]、移动瓶颈法（Shifting Bottle-neck）等。此类方法可以快速建立问题的解，但
通常构造复杂，解的质量较差，而且对初始解的要求较高。现在一般都采用启发
式方法构造其初始解，以提高其搜索性能。
启发式邻域搜索方法主要有进化计算（EC，Evolutionary Computing）[5-6]、模
拟退火算法（SA，Simulated Annealing）[7-8]、禁忌搜索（TS，Tabu Search）[9]等。
此类方法从若干解出发，对其邻域的不断搜索和当前解的替换来实现优化。其中
遗传算法（GA，Genetic Algorithm）的局部搜索能力较弱，SA的退火时间较长，
TS的禁忌表的构造相对困难，所以实际应用中经常把这些启发式方法结合起来使
用。
人工智能方法如蚁群系统[10-11]（AS，Ant System）、神经网络[12]（NN，Neural
Network）、混沌搜索[13]
（CS，Chaotic Search）、免疫算法[14]
（IA，Immunity Algorithm）
等，也是常用到的一类启发式方法。此类方法利用人工智能的原理和技术进行搜
索，将优化过程转化为智能系统动态的演化过程，利用系统的动态演化来实现优
化，在应用中也取得了很好的效果。
随着人们认识的深入以及科学技术的发展，一些新兴的算法也越来越受到重
视，如 DNA 计算[15-17]、演化博弈计算[18]、量子计算[19-20]、文化算法[21-24]、思维进
化算法[25]等。这些算法的实现由于理论和技术有待完善，还未得到广泛的使用，
但随着理论研究的深入和优化技术的发展，目前很多非常困难的问题都将迎刃而
蚁群算法的改进及其在生产调度中的应用
6
解。
§1.3 本文主要研究的内容
本文主要是针对求解 NP-hard 的车间生产调度存在的问题，通过深入研究问题
的性质，设计蚁群算法的求解方法，并在蚁群算法的基础上，结合思维进化思想
和局部寻优思想，提出了基于思维进化的蚁群算法，对算法流程进行重新思考和
设计，并针对几类不同类型的车间调度问题进行了求解。文中对基于思维进化的
蚁群算法的设计思想和流程进行了详细的介绍，通过与其他算法的比较，介绍了
其优点及不足之处。针对几类不同类型的车间调度问题，文中分别设计了相应的
求解算法，并利用 Visual C 语言编程模拟，通过对仿真实例计算结果的分析及与
相关参考文献的比较，表明了算法的有效性和优越性。
第一章：绪论。主要介绍了车间调度问题的背景意义，介绍了车间调度问题
的分类，简要描述了其求解算法的研究进展情况，最后给出了本文的主要研究内
容。
第二章：蚁群算法的基本原理。简要回顾了蚁群算法的研究历史，概述了蚁
群算法的发展现状、基本原理及步骤，分析了蚁群算法的特点，并对蚁群算法的
一些理论进行了讨论。
第三章：基于思维进化的蚁群算法。介绍了思维进化算法的机制、具体模型
结构和具体流程。受思维进化算法的启发，提出了基于思维进化的蚁群算法，给
出了该算法的基本模型和基本流程。选取了旅行商问题为算法的测试对象，通过
对仿真实例的测试，表明了本文算法有效的解决了传统蚁群算法容易陷入局部最
优的缺点，提高了算法的全局搜索能力。
第四章：典型 Job shop 问题蚁群算法研究。文中介绍了 Job shop 问题的数学
模型和析取图模型，建立了基于 Make span 最小的 Job shop 调度模型，分析了 Job
shop 问题解的特点，针对典型的 Job shop 问题设计了相应的求解策略。对典型调
度问题进行了仿真求解，取得了满意的效果。
第五章：
Flow shop 问题蚁群算法研究。
Flow shop 调度问题是许多实际流水线
生产调度问题的简化模型。文中设计了相应的蚁群算法，对 Car 类典型的测试问
题进行了仿真求解，取得了比较满意的效果。
第六章：半导体炉管区批调度的蚁群算法研究。分析了半导体炉管区批调度
的特点，建立了半导体炉管区批调度的数学模型，构造了符合蚁群算法的分批调
度模型和平行机台调度模型，并针对文献中的问题进行了仿真求解，取得了满意
的效果。
摘要：

I目录中文摘要ABSTRACT第一章绪论........................................................1§1.1课题的来源及意义.............................................1§1.2车间调度问题.................................................2§1.2.1车间调度问题的描述.......................................2§1.2.2车间调度问题的分类......................................

展开>> 收起<<
蚁群算法的改进及其在生产调度中的应用.pdf

共81页,预览9页

还剩页未读， 继续阅读

相关推荐

更多
立即下载
作者：陈辉 分类：高等教育资料 价格：15积分 属性：81 页 大小：1.03MB 格式：PDF 时间：2024-11-19

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

推荐作者

热门标签

/ 81
评分 收藏
分享
立即下载 VIP免费下载
客服
关注