文化进化算法在车间生产调度中的应用研究

VIP免费
3.0 赵德峰 2024-11-19 4 4 1.69MB 67 页 15积分
侵权投诉
I
目 录
中文摘要
ABSTRACT
第一章 绪 论 ................................................... 2
§1.1 课题的来源及意义 ..........................................2
§1.2 车间调度问题的国内外研究现状 ..............................3
§1.2.1 车间调度问题分类 ..................................... 3
§1.2.2 求解车间调度问题算法研究进展 ......................... 3
§1.3 本文主要研究的内容 ........................................4
第二章 文化进化理论研究进展 ..................................... 6
§2.1 文化进化理论发展 ..........................................8
§2.1.1 古典文化进化论 ........................................8
§2.1.2 新文化进化论 ..........................................8
§2.2 文化适应性及稳定性原则 ................................... 11
§2.3 文化进化优势法则 ......................................... 12
§2.4 文化进化潜势法则 ......................................... 12
§2.5 文化进化机制和超群进化理论 ...............................13
第三章 文化进化算法设计及研究进展 .............................. 14
§3.1 文化算法介绍 .............................................14
§3.1.1 文化算法简介 .........................................14
§3.1.2 文化算法研究及应用进展 .............................. 16
§3.2 文化进化算法设计 .........................................17
§3.2.1 文化进化算法相关概念描述 ............................ 17
§3.2.2 文化进化算法流程设计 ................................ 18
§3.3 文化进化算法与遗传算法、传统文化算法比较 .................21
第四章 置换 Flow shop 问题文化进化算法研究 ....................... 21
§4.1 引言 .....................................................22
§4.2 置换 Flow shop 问题描述及数学模型 ......................... 22
§4.3 求解置换 Flow shop 问题文化进化算法设计 ................... 22
§4.4 仿真测试及分析 ........................................... 24
§4.4.1 仿真测试 .............................................24
II
§4.4.2 结果分析 ............................................ 26
§4.5 本章小结 .................................................27
第五章 文化进化算法求解模糊交货期 Flow shop 问题 .................. 27
§5.1 引言 .....................................................27
§5.2 模糊交货期 Flow shop 问题描述及数学模型 ................... 28
§5.3 求解模糊交货期 Flow shop 问题文化进化算法设计 .............. 29
§5.4 仿真求解及分析 ........................................... 31
§5.4.1 仿真求解 .............................................31
§5.4.2 结果分析 ............................................ 33
§5.5 本章小结 .................................................33
第六章 典型 Job shop 问题文化进化算法研究 ......................... 34
§6.1 引言 .....................................................34
§6.2 典型 Job shop 问题描述及数学模型 ...........................34
§6.3 求解典型 Job shop 问题文化进化算法设计 .....................35
§6.4 仿真测试及分析 ........................................... 37
§6.4.1 仿真测试 .............................................37
§6.4.2 结果分析 ............................................ 40
§6.5 本章小结 .................................................40
第七章 文化进化算法求解多资源约束 Job shop 问题 ................... 41
§7.1 引言 .....................................................41
§7.2 多资源约束 Job shop 问题描述 ...............................41
§7.3 求解多资源约束 Job shop 问题文化进化算法设计 ...............41
§7.4 仿真求解及分析 ........................................... 43
§7.4.1 仿真求解 .............................................43
§7.4.2 结果分析 ............................................ 45
§7.4.3 现场改善及分析 .......................................45
§7.5 本章小结 .................................................45
第八章 总结与展望 ............................................... 47
附录 文化进化算法求解 Flow shop 问题部分源程序 .................... 49
参考文献 ........................................................ 61
在读期间公开发表的论文和承担科研项目及取得成果 .................. 65
致谢 ............................................................ 67
第一章 绪 论
文化进化算法在车间生产调度中的应用研究
2
§1.1 课题的来源及意义
制造业是国民经济的物质基础和工业化的产业主体，是社会进步与富民强国
之本。改革开放二十多年的发展，中国依靠政府优惠政策、国内巨大的消费市场
和廉价劳动力成本，成功的吸引了国外先进技术和雄厚资本进入，经济规模跃居
世界前列，经济实力得到明显增强。但是由于诸多原因，如劳动生产率比较低，
资源消耗严重、利用率低；产品以低端为主，附加价值不高，竞争力不强；自主
知识产权缺乏，创新能力不强等等，中国制造业大而不强的局面短期还无法改变。
由于处于国际产业链的低端，中国制造虽然耗费了大量资源，但获得的利润
却微乎其微。工业制造业盈利水平每况愈下，统计数据显示，2005 年与 2003 年相
比，我国制造业在销售收入增长 73.11%的同时，利润只增长 47.94%，销售成本利
润率由 5.96%下降到 4.94%。随着原材料不断上涨，以及国内人力成本不断上升等
因素，中国制造企业正在失去以前所依赖的低价竞争优势，进行产业升级和结构
调整，引入先进的管理思想和技术，降低制造成本，发掘新的利润增长点，是中
国制造企业面临的挑战。
以信息化带动工业化，走新型工业化道路，其重要途径就是用现代信息技术
改造传统产业，实现工业生产过程和经营管理的自动控制。这对强化质量控制、
节约资源消耗、降低生产成本、提高生产效率，能够起到倍增器的作用。在 21 世
纪，随着电子、信息等高新技术的不断发展，随着市场需求个性化与多样化，先
进制造技术发展的总趋势是向精密化、柔性化、网络化、虚拟化、智能化、清洁
化、集成化、全球化的方向发展。国外的先进制造理念和技术已在国内被广泛接
受及应用，如准时制生产思想（JIT）、约束理论（TOC）、计算机集成制造系统
（CIMS）、智能制造技术（IMT）、智能制造系统（IMS）、敏捷制造（AM）等等。
人们正试图将信息技术、管理技术与工艺技术紧密结合，创造出先进的制造生产
模式。
生产调度，即对生产过程进行作业计划，是整个先进制造系统实现管理技术、
运筹技术、优化技术、自动化与计算机技术发展的核心。生产调度是个交叉性研
究领域，涉及运筹、数学、计算机工程、控制工程、工业工程等多个学科相关知
识。有效的调度方法和优化技术的研究和应用，改善生产调度方案，可以大大提
高生产效益和资源利用率，进而增强企业的竞争能力。
车间生产调度问题大部分属于 NP-hard 问题，这类问题描述相对容易，但是求
解非常困难。随着调度规模的扩大，生产加工多品种、小批量的趋势，调度问题
日益复杂，许多调度问题的求解至今没有可以精确求得最优解的多项式时间算法。
第一章 绪论
3
对NP-hard 问题，目前常用随机搜索算法或智能启发式算法求解，如遗传算法、模
拟退火算法、蚂蚁算法、微粒群算法等等，通过获得满意解（非最优解）以满足
实际工程和生产需要。由于各种算法各有特点、各有优劣，从生物行为特点或者
社会进化规律中获取更多的灵感和启发，将更多的进化思想引入寻优过程，是算
法研究的发展趋势。探索实用和有效的算法，仍是国际上关注的热点研究课题。
§1.2 车间调度问题的国内外研究现状
§1.2.1 车间调度问题分类
调度问题通常指对生产过程的作业计划，如工件在机器上的加工顺序、生产
批量的划分等。按照研究问题的侧重点不同，调度问题有不同的分类方法。
按生产方式划分，调度问题可分为开环车间（open shop）型和闭环车间（closed
shop）型[1]。开环调度问题也称加工排序问题，本质上只研究工件的加工顺序，即
订单所要求的产品在所有机器上的加工顺序，不考虑库存；闭环调度问题除研究
工件的加工顺序外，还涉及各产品批量大小的设置，做生产计划时要考虑产品的
存储策略。
按调度优化的目标函数划分，车间调度问题可分为单目标调度和多目标调度。
单目标调度即以加工最短流程时间等单一目标作为目标函数；多目标调度则是综
合考虑加工流程时间、交货期、生产拖期时间等多个目标寻求最佳调度方案。
按零件到达车间的情况划分，排序问题可分为静态的排序问题（SS，Static
Scheduling）和动态的排序问题（DS，Dynamic Scheduling）[2]。当进行排序时，
所有零件都已到达，可以一次对它们进行排序，就是静态的排序问题；若零件陆
续到达，要随时安排它们的加工顺序，就是动态的排序问题。
按产品加工的工艺过程划分，车间调度问题可分为流水车间（Flow shop）调
度、作业车间（Job shop）调度、重入（Re-entrant）型调度。Flow shop 调度指所
有工件具有相同的工艺流程，不存在设备回访情况；Job shop 调度指每类工件有各
自的工艺流程，不同类型的工件间没有顺序约束；Re-entrant 型调度主要指半导体
制造系统中[3]，工艺流程中大量相同工序重复访问同一台设备的情况。
§1.2.2 求解车间调度问题算法研究进展
调度优化算法可分为精确求解方法和近似求解方法[1]。精确求解方法一般有解
文化进化算法在车间生产调度中的应用研究
4
析方法、穷举法、分支定界法等。此类方法对小规模调度问题比较有效，但对大
规模问题计算量和存储量难以满足。近似求解方法如构造法、启发式方法、随机
搜索方法等，由于可以快速找到满意解，在生产调度领域受到广泛的重视和研究，
而且各种混合式搜索方法在许多组合优化领域均得到广泛的应用。
构造性方法如 CDS（CDS，Campbell-Dudek-Smith）法、NEH（Nawaz－Enscore
－Ham）法[4]、移动瓶颈法（Shifting bottleneck）等。此类方法可以快速建立问题
的解，但通常构造复杂，解的质量较差，而且对初始解的要求较高。现在一般都
采用启发式方法构造其初始解，以提高其搜索性能。
启发式邻域搜索方法主要有进化计算（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]等。这
些算法的实现由于理论和技术有待完善，还未得到广泛的使用，但随着理论研究
的深入和相关支持技术的发展，其强大的搜索能力将使目前很多非常困难的问题
迎刃而解。
§1.3 本文主要研究的内容
本文主要研究的内容是车间生产调度问题的文化进化算法的设计及求解，在
文化算法的基础上，结合文化进化思想和超群进化思想，对算法流程进行重新思
考和设计，并针对几类典型的车间调度问题进行了求解。文中对文化进化算法的
设计思想和流程进行了详细的介绍，通过与其他算法的比较，介绍了其优点及不
足之处。针对典型的车间调度问题，文中分别设计了相应的求解算法，并利用
Matlab 语言编程模拟，通过仿真求解及与相关参考文献的比较，验证了算法的有
第一章 绪论
5
效性和优越性。
第一章：绪论。主要介绍了车间调度问题研究的背景和意义，简要介绍了车
间调度问题的分类及其求解算法的研究进展情况，最后介绍了本文的主要研究内
容。
第二章：文化进化理论研究进展。简要回顾了文化进化的研究历史，包括文
化进化理论研究的起源和发展；介绍了古典文化进化论学派和新文化进化论学派
的研究成果，如文化进化热力学理论、文化生态学理论、一般进化与特殊进化理
论、文化进化的 meme 理论等；重点介绍了文化进化相关的几个重要法则，如文
化进化适应性与稳定性原则、进化优势法则和进化潜势法则等，以及文化进化机
制和超群进化的相关理论。
第三章：文化进化算法设计及研究进展。简要介绍了文化算法的研究，在此
基础上，结合超群进化理论设计了文化进化算法。文中给出了相关的定义及算法
详细的流程设计，并与遗传算法、传统文化算法的搜索特点进行了比较，突出了
本文算法的特点。最后简要介绍了文化算法目前的研究及应用情况。
第四章：置换 Flow shop 问题文化进化算法研究。Flow shop 调度问题是许多
实际流水线生产调度问题的简化模型，置换 Flow shop 问题是其中最简单的一种。
文中设计了相应的文化进化算法，对 Car、Rec、Hel 三类典型的测试问题进行了
仿真求解，与已有文献相比较，取得了比较满意的效果；通过与自适应遗传算法
和局部搜索算法结合，提高了文化进化算法的收敛性能。
第五章：文化进化算法求解模糊交货期 Flow shop 问题。随着 JIT 思想的推广，
顾客对交货期提出了更高的要求。文中介绍了含模糊交货期 Flow shop 问题的数学
模型，并综合考虑加工时间和交货期目标进行生产优化，利用文化进化算法和已
有文献数据进行了仿真求解，为进一步研究打下了基础。
第六章：典型 Job shop 问题文化进化算法研究。
Job shop 调度问题的复杂性远
大于 Flow shop 问题，求解也更困难。文中介绍了 Job shop 问题数学模型，针对简
单的 Job shop 问题设计了相应的编码、活动化解码等策略及相应的操作算子。通
过仿真求解，结果优于文献中的遗传算法和改进微粒群算法。
第七章：文化进化算法求解多资源约束 Job shop 问题。多资源约束 Job shop
问题是考虑到人员、机器、工具等多种约束下如何进行生产调度规划的问题，由
于约束复杂，求解比较困难，文中用文化进化算法对文献中的算例尝试求解，得
到了文献中的最优解，同时考虑到生产现场情况，对进一步改善分析提出了建议。
第八章：总结与展望。对本文的主要研究工作进行了总结，同时提出了文中
的一些不足和待改进的地方，最后对文化进化算法的研究及应用前景进行了展望。
摘要：

I目录中文摘要ABSTRACT第一章绪论...................................................2§1.1课题的来源及意义..........................................2§1.2车间调度问题的国内外研究现状..............................3§1.2.1车间调度问题分类.....................................3§1.2.2求解车间调度问题算法研究进展.........................3§1.3本文主要研究的内容................

展开>> 收起<<
文化进化算法在车间生产调度中的应用研究.pdf

共67页,预览7页

还剩页未读， 继续阅读

相关推荐

更多
立即下载
作者：赵德峰 分类：高等教育资料 价格：15积分 属性：67 页 大小：1.69MB 格式：PDF 时间：2024-11-19

开通VIP享超值会员特权

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

作者详情

相关内容

更多

推荐作者

热门标签

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