生产计划与调度问题的知识进化算法研究

VIP免费
3.0 赵德峰 2024-11-19 4 4 1.26MB 51 页 15积分
侵权投诉
目 录
中文摘要
ABSTRACT
第一章 绪论 .....................................................................................................................1
§1.1 课题的来源及意义 .............................................................................................. 1
§1.2 生产计划与调度问题的求解方法 ...................................................................... 2
§1.3 本文的主要内容 ................................................................................................... 5
第二章 智能优化算法 .................................................................................................... 7
§2.1 遗传算法 .............................................................................................................. 7
§2.2 模拟退火算法 ...................................................................................................... 8
§2.3 禁忌搜索算法 .................................................................................................... 10
§2.4 蚁群优化算法 .....................................................................................................11
§2.5 粒子群算法 ........................................................................................................ 13
§2.6 人工鱼群算法 .................................................................................................... 15
§2.7 量子算法 ............................................................................................................ 17
§2.8 知识进化算法 .................................................................................................... 19
§2.8.1 知识进化算法的基本框架..........................................................................19
§2.8.2 知识进化算法总体方案..............................................................................19
第三章 成组单元生产批量计划问题的知识进化算法研究...................................... 22
§3.1 引言 .................................................................................................................... 22
§3.2 成组单元有能力约束的生产批量计划模型 .................................................... 22
§3.3 求解成组单元生产批量计划问题的知识进化算法方案 ................................ 24
§3.3.1 算法编码......................................................................................................24
§3.3.2 初始化..........................................................................................................24
§3.3.3 选择操作、猜测操作和反驳操作..............................................................25
§3.3.4 假说的适应值计算......................................................................................25
§3.3.5 知识的进化..................................................................................................25
§3.3.6 算法流程......................................................................................................26
§3.4 仿真实验 ............................................................................................................. 26
§3.5 本章小结 ............................................................................................................. 28
第四章 半导体晶圆制造多厂区订单分配问题的知识进化算法研究 ...................... 29
§4.1 引言 .................................................................................................................... 29
§4.2 问题的描述和数学模型 .................................................................................... 30
§4.2.1 问题的描述..................................................................................................30
§4.2.2 问题的数学模型..........................................................................................30
§4.3 求解半导体多厂区订单分配问题的知识进化算法方案 ................................. 31
§4.3.1 算法编码......................................................................................................31
§4.3.2 初始化..........................................................................................................31
§4.3.3 选择操作、猜测操作和反驳操作..............................................................32
§4.3.4 假说的适应值计算......................................................................................32
§4.3.5 知识的进化..................................................................................................33
§4.3.6 算法流程......................................................................................................33
§4.4 仿真实验 ............................................................................................................ 33
§4.5 本章小结 ............................................................................................................ 35
第五章 半导体制造设备预维修调度问题的知识进化算法研究 .............................. 36
§5.1 引言 .................................................................................................................... 36
§5.2 问题的描述和数学模型 .................................................................................... 37
§5.2.1 问题的描述..................................................................................................37
§5.2.2 问题的数学模型..........................................................................................37
§5.3 求解半导体制造设备预维修调度问题的知识进化算法方案 ......................... 38
§5.3.1 算法编码......................................................................................................38
§5.3.2 算法流程......................................................................................................38
§5.4 仿真实验 ............................................................................................................. 39
§5.5 本章小结 ............................................................................................................. 42
第六章 总结与展望...................................................................................................... 43
参考文献 .........................................................................................................................45
在读期间公开发表的论文和承担科研项目及取得成果............................................ 50
致谢 .................................................................................................................................51
第一章 绪论
1
第一章 绪论
§1.1 课题的来源及意义
制造业是国家经济的支柱产业，是一个国家经济的基础。然而，近年来，随
着信息技术的高速发展、顾客消费水平的不断提高和全球一体化进程的不断加快，
企业之间竞争不断加剧，加上政治、科技、经济、社会环境等方面的巨大变化，
使得企业制造系统的决策人员不得不面对一系列挑战。如何协调时间、质量、成
本、服务和环境等因素，如何降低产品的成本，缩短制造周期，保证准时交货，
赢得更多的客户，成为制造业企业在竞争中获得成功的主要条件之一。因此，每
个企业都在寻求好的生产运作管理方式和决策系统，以提高企业的经营效率，最
终提高企业的竞争力 [1]。
制造业生产计划与调度问题是涉及应用数学、生产管理、运筹学、人工智能
和计算机科学等多学科交叉的综合性问题。目前生产计划与调度问题是理论上和
算法上研究的热点，也是企业中产生重大经济效益的问题之一。
1947 年12 月16 日，美国贝尔实验室的巴丁博士、布莱顿博士和肖克莱博士
合作发明了人类历史上第一个半导体元件。1958 年9月Jack kilby 工程师将电容、
电阻、二极管等分离的软件作在同一块半导体基件上，再将它们连接起来，制造
了世界上第一个集成电路[2]，一个新兴的产业——半导体产业就此诞生了，半导
体产业是一个非常庞大的产业，其产业链结构如图 1-1 所示。
图 1-1 半导体产业链结构[2]
根据国际半导体设备及材料协会中国区总裁丁辉文先生介绍：“2007 年中国
半导体芯片制造业产能比 2000 年增长 859%，产能增长率超过欧洲、美国和日本，
Manufacturing
制造业
(产值:63%)
Design
设计业
(产值:14%)
Assembly
封装业
(产值:19%)
Testing
测试业
(产值:4%)
Wafer (晶圆)
Mask (光罩)
Equipment (设备)
Chemicals (化学品)
生产计划与调度问题的知识进化算法研究
2
居全球之首。目前中国已成为国际半导体芯片制造业投资最为密集的地区之一”
[3]。从图 1-1 可以看出，半导体制造业的产值占整个半导体产业链的 60%以上，
因此研究半导体制造业中的生产计划与调度问题具有重要的现实意义。
不论是传统制造业还是半导体制造业，生产计划与调度问题的研究都是一个
复杂问题，本文以传统制造业和半导体制造业的生产计划与调度问题为背景，研
究优化该类问题的知识进化算法方案，本文的研究具有两个方面的主要意义：一
方面，可以为生产计划与调度问题的求解提供一种新的优化方案；另一方面，可
以拓展知识进化算法的应用领域。
§1.2 生产计划与调度问题的求解方法
生产计划与调度问题是一个非常复杂的问题，由于这类问题描述容易，但求
解却非常困难，因此吸引了众多的科学研究者。在过去的几十年中，许多新兴的
求解方法不断地被应用到生产计划与调度领域中，使得生产计划与调度问题的研
究工作不断充实和发展。
因为生产计划与调度问题的描述简单，因此大多已经存在数学规划模型，所
以主要研究热点在于求解方法方面。目前求解生产计划与调度问题的方法主要有
三大类方法：精确方法、近似算法和随机搜索算法。具体的分类可以如图 1-2 所
示。下面将分类介绍生产计划与调度问题求解方法的研究情况。
图1-2 求解生产计划与调度问题的方法分类
生
产
计
划
与
调
度
问
题
的
求
解
方
法
精确算法
近似算法
随机搜索算法
第一章 绪论
3
（1）求解生产计划与调度问题的精确算法研究现状
文献[4]中Kleinman 等应用动态规划方法解决了随机到达工件的调度安排
问题，并通过实证证明上述方法是可行的。文献[5]Suresh 等针对工件在单机情况
下动态到达的问题使用分枝定界法得以解决。文献[6]通过一些经典的 MILP 模型
为炼油厂调度优化问题进行建模。文献[7]建立了一个食品加工厂里稀有资源分配
的线性规划模型。文献[8] 中在电缆生产厂里分配光纤时利用了整数规划。文献[9]
采用一种基于 MILP 的算法很好地解决了生产调度和重调度问题，并将该算法应
用到造纸厂和制药厂生产实际中，取得较好的效果。文献[10]的作者提出经典的
最优化方法存在一定的局限性，往往只具有理论方面的价值，较少地应用到实际
生产中。
上述精确算法一般都是建立在理想化假设的基础上，针对生产过程中存在的
不确定性和动态性，并不能全面客观地反映实际中复杂的生产环境。并且由于精
确算法计算的复杂性，在求解较大规模的生产问题时，其求解最优解时间将随问
题规模的增加而呈指数级增长，因此该类算法距离实用还有很大距离。
（2）求解生产计划与调度问题的近似算法研究现状
所谓“近似”，就是指结果不一定是最优的，但是也在可以承受的范围内，而
且可以比精确求解消耗更少的资源。此处的资源是计算复杂性理论中的标准，可
以是时间或者空间等。换句话说，如果找不到最优解时，那么合理的做法是牺牲
一点最优性而去寻求有效的、好的、可行的近似解。当然在保证解的有效性时，
其最优性要尽可能的保留。近似算法的模式正是为了寻求这种平衡。
最早提出分派规则的是 Jackson[11]和Smith[12]等，文献[13]中提出了优先权规
则调度的典型算法。文献[14]Panwalker 和Iskander 对100 余种优先规则进行了归
纳。文献[15]采用基于启发式算法的关键路径法解决了多目标的车间调度问题。
文献[16]在并行多机成组工作情况下，使用启发式方法求解了总流水时间调度问
题。文献[17]阐述了一种分区算法和本地搜索技术等等。
（3）求解生产计划与调度问题的随机搜索算法研究现状
近几年来，随机搜索类优化算法大量涌现出来，诸如遗传算法、禁忌搜索算
法、模拟退火算法、粒子群算法和蚁群优化算法等，这些算法为求解各种复杂优
化问题开辟了一种新途径。
文献[18]中将遗传算法应用到静态、动态和非确定性生产环境的一般作业调
度中，较好地解决了上述问题。文献[19]中提出了用于柔性制造系统的新调度算
法，这一算法综合考虑了机器发生故障、订单紧急下达、订单优先级提高和订单
取消等四种事件的发生，起初使用稳态遗传算法进行初始调度，一旦发生意外情
生产计划与调度问题的知识进化算法研究
4
况将仅调度直接受到影响的工序。文献[20]把一个能够更新受干扰车间状态的数
据库应用到重调度系统中，同时利用了改进的自适应遗传算法求解该问题，避免
过早陷入局部解。文献[21]中Starkweather 把遗传算法应用到啤酒厂的多目标
Job-shop 调度问题，这些目标包括订单平均等待时间最小和商品平均存货时间最
小等。文献[22] 在并行多机调度问题的求解上采用了遗传算法来解决。文献[23]
研究了生产动态调度的知识获取问题，并应用遗传算法解决了该问题，通过实例
验证了其可行性。文献[24]研究了流程工业中生产和能量的调度优化问题，并提
出了遗传算法的解决方案。
遗传算法对技巧的要求不高，也不需要比较深入的了解问题本身，所以在求
解很多组合优化问题时得到广泛应用，并且它与其它启发式算法的兼容性较好。
文献[25] 用接受率来确定初始温度和最终温度，提出了临界区模拟退火
(critical block simulated annealing，CBSA)方法，在 SA 架构中内嵌一个来自于临
界区的邻域结构，以此使退火过程达到改善搜索的目的。文献[26]提出了快速模
拟退火(fast simulated annealing，FSA)算法，该算法允许偶然的长步长跳跃，可以
加速算法的收敛。文献[27]针对单元制造系统的调度问题，提出了求解该问题的
SA 算法方案。文献[28]的作者研究出了知识获取问题的一种 SA 方法。文献[29]
提出了一种基于 SA 的求解无等待约束多目标的调度方法。
模拟退火算法作为一种随机优化方法，它可以突破局域搜索的限制，在参数
选取得当的前提下，会在较短的时间内收敛。但是模拟退火算法在实际应用中由
于有时参数不易选择，往往不能得到较好的效果。
禁忌搜索算法也是优化算法中的一个成功应用。文献[30]对Job-Shop 的
Benchmark 问题的最优解进行了改进，提出了一种基于并行结构的禁忌搜索算法。
文献[31]提出了一种基于关键路径的邻域结构，这样做既改善了 Benchmark 问题
的解性能，同时也减少了计算时间。
文献[32]通过在不同车间环境下采用遗传算法和蚁群算法解决调度问题的比
较研究，表明在静态环境中，两种算法均能获得好解，但是蚁群算法比遗传算法
更能适应动态环境下的干扰，更适合动态调度问题。文献[33]研究了紧急订单插
入的动态车间重调度问题，利用了基于突变处理的蚁群算法，避免陷入局部最优。
综上所述，求解生产计划与调度问题的精确算法不适合求解大规模问题，在
现实应用中缺乏可行性，而近似算法对于问题的依赖性较强，不具有通用性。所
以近几年来，以遗传算法为代表的随机搜索算法在生产计划与调度问题的求解方
面研究越来越多，但目前针对于生产计划与调度问题还没有很好的求解方法，因
此探索研究该问题的求解方法具有重要的理论意义和现实意义。
摘要：

目录中文摘要ABSTRACT第一章绪论.....................................................................................................................1§1.1课题的来源及意义..............................................................................................1§1.2生产计划与调度问题的求解方法.........................................

展开>> 收起<<
生产计划与调度问题的知识进化算法研究.pdf

共51页,预览6页

还剩页未读， 继续阅读

相关推荐

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

开通VIP享超值会员特权

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

作者详情

相关内容

更多

推荐作者

热门标签

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