| 题名 | 基于启发式规则和阶乘码的零等待流水车间调度算法研究 |
| 作者 | 雷文昌 |
| 答辩日期 | 2017 |
| 导师 | 赵付青 |
| 关键词 | 零等待流水车间调度 傅里叶变换 拼图算法 阶乘码 |
| 学位名称 | 硕士 |
| 英文摘要 | 零等待流水车间广泛的存在与现代制造系统中,如钢铁、医药等制造系统。在零等待流水车间中,假设有n个工件被m台机器加工。各个工件由z个工序组成,每个工序与机器是一一对应的,即一种机器只能加工一种工序,一个工序只能在一台机器上进行加工。一个工件的连续两道加工工序不能出现中断。一台机器不能同时加工多个工件。因此零等待流水车间调度算是一个典型的NP-hard问题。已有的调度策略和传统的调度方法已无法满足实际生产过程中的各种复杂需求。因此调度理论方面的学术研究以及在实际的制造业生产之中,有效的调度方案研究仍然是本领域的一个热点。本文的主要研究内容如下:1.针对快速缩小搜索空间问题提出了基于傅里叶变换和搜索区域分割的启发式算法。本文提出的基于快速傅里叶变换的方法使得搜索空间不再是以点为基本单元,而是以每个维度最小频率对应的周期的1/2或更小所围成的区域为基本单元。这种分割方法能保证在每个维度上只存在4种可能性:1)单调上升;2)单调下降;3)有且只有1个极大值点;4)有且只有1个极小值点。在这种特殊的区域内我们使用二分查找法来寻找每个维度上所能达到的最好值所在位置的集合。各个维度上的最好位置组合成的个体便是这个区域内的最好值所在的位置。这使得算法不再与点的数量有关,而是和数据的最小频率的数量有关。这将极大的减少了搜索空间,增加搜索效率。2.针对零等待流水车间调度问题的甘特图特性提出一种拼图游戏启发的算法。该算法将两个工件之间的总空余时间作为两个工件是否契合的标准。算法开始时,先计算每个工件与其它工件之间的空余时间,对空余时间进行由小到大排序,从而每个工件都有个匹配队列。然后每个工件分别作为第一工件并且在它的匹配队列中找出空余时间最小同时又不在已有序列中的工件作为下一个工件。此时这两个工件即为局部最优匹配,可将其视为一个工件。不断迭代当前步骤直至所有工件都出现在已有队列中。此时每个工件作为第一个工件的调度序列组就产生了。最后选择其中加工时间最小的序列作为调度结果。3.针对零等待流水车间调度问题中的Landscape提出了一种基于阶乘码和种群调整的粒子群优化算法。这篇文章中提出的一种基与阶乘的编/解码方法的种群调整的粒子群算法用来解决零等待流水车间调度中寻找调度序列使得最小完成时间达到最小。此编码将排列组合和自然数相互转换。采用的是一一对应的方式,即一个排列组合唯一对应一个自然数,一个自然数唯一对应一个排列组合。同时,通过这种编码方法,我们可以得出各个调度模型的Landscape,然后通过分析Landscape选择相应的调整机制对算法进行改进。我们选择的这个改进方式是通过欧氏距离来测量粒子群算法中的种群多样性,当种群多样性降低的时候通过高斯分布进行随机初始化增加种群的多样性。 |
| 语种 | 中文 |
| 页码 | 95 |
| URL标识 | 查看原文 |
| 内容类型 | 学位论文 |
| 源URL | [http://ir.lut.edu.cn/handle/2XXMBERH/92799]  |
| 专题 | 兰州理工大学 |
| 作者单位 | 兰州理工大学 |
| 推荐引用方式 GB/T 7714 | 雷文昌. 基于启发式规则和阶乘码的零等待流水车间调度算法研究[D]. 2017. |
| 个性服务 |
| 查看访问统计 |
| 相关权益政策 |
| 暂无数据 |
| 收藏/分享 |
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。
修改评论