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

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
摘要：

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免费下载
客服
关注