CASIA OpenIR  > 毕业生  > 博士学位论文
一种新的项目调度解表示方法及其应用研究
其他题名A New representation for the solution of the resource-constrained project scheduling problem and its applying in algorithm designing
黄志宇
学位类型工学博士
导师裘聿皇
2008-07-23
学位授予单位中国科学院研究生院
学位授予地点中国科学院自动化研究所
学位专业控制理论与控制工程
关键词项目调度 搜索解空间 分散搜索 进化算法 Project Scheduling Search Space Scatter Search Evolutionary Algorithm
摘要具有资源约束的项目调度问题因其实际和理论意义一直是调度领域的重点内容。以往研究者提出了多种多样的算法,这些算法主要侧重于采用不同的算法结构和数学技巧来进行研究,很少有文献直接从搜索算法实质的角度出发来进行算法设计。针对这种情况,本论文对算法设计流程和搜索解空间的定义作了详细研究,主要研究工作如下: (1) 澄清了算法设计的主要阶段以及各个阶段的主要任务。认为设计调度算法可以从两个阶段来进行理解,一是调度解的构造阶段,另一个是调度解在搜索解空间内的迁移阶段。在构造解阶段,算法的主要任务是发现构成调度解的组成成分的最优组合过程;在解空间迁移搜索阶段,算法的主要任务是发现迁移的有利方向。 (2) 定义了一种新的调度解表示方法,并给出了距离的定义。该方法描述了项目调度问题中各个活动之间的连接关系,可以与任何启发式框架混用,在更高的层次上体现了解的调度性质。 (3) 扩展了前向-后向调度思想,定义了反向问题。反向问题保持了原问题的资源约束,活动间的先后关系约束与原问题相反。在反向问题中,所有正向问题的搜索操作都采用同样的方式进行,算法在需要的时候利用反向搜索一个解群来更新另一个解群。反向问题的定义,给算法设计带来了更多的灵活性。 (4) 按照分散搜索的思想设计了分散搜索算法。通过对基本分散算法的各个因素作了仿真分析,给出了调整方法。调整的结果得到了混合遗传算法和进化算法。通过对项目调度问题标准库中实例的仿真分析,混合遗传算法和进化算法都可以解决大规模调度问题,并在产生比较少解的情况下,得到最优解以及最优解出现的个数都达到了很高的水平。 (5) 根据新的表示方法,给出了解空间分解算法。并比较了一次分解算法和多次分解算法的效果。 (6) 根据新表示方法的二值性,设计了量子进化算法。指出了量子算法的一般结构以及调整方法,给出了单量子算法和双量子遗传算法。 仿真结果说明了本文思想的正确性和算法的有效性。
其他摘要The resource-constrained project scheduling problem (RCPSP) as its significations in the reality and theory fields is always an important issue in the scheduling field. There have been many algorithms provided, most of them pay more attention in designing different structure and applying different mathematic skills, there was rarely research which designed algorithm directly by the essentials of the scheduling process. As for this situation, this paper studies the searching process and search space in detail and gets the following results: (1) The main fields of algorithm designing and the main task of these fields are clarified. Constructing schedules phase and strolling in search space phase are regard as the main two phase for algorithm designing. In the constructing schedules phase, the main task of an algorithm will be finding the best procedure by ordering the constructing components, and in the search space strolling phase, the main task of an algorithm will be finding the most potential direction in which a better schedule can be found. (2) A new representation of solution for RCPSP and the distance between two solutions in the new search space are given. This new representation describes the linking relation between arbitrary activities pair, and it can be use in any generation scheme. It can be said that the new representation keeps the schedule property in high level. (3) A reverse problem which extends the ideal of forward-backward schedule is given. It keeps all the resource constraints of the original problem and includes the reverse linking relations as the original problem. All the operations applied in original problem are taken in the same style in reverse problem. When needed, a reverse scheduling for the population in one direction is used to update the population in the other direction. (4) Scatter search algorithm is designed. After analyzing the affections of the factors in the scatter search, improving methods are given. A hybrid genetic algorithm and an evolutional algorithm are given. The simulation results for the instances in the standard library show that these two algorithms all can resolve the large-sized problems and have reached high level in finding optimal solutions in generating less number of solutions. (5) Based on the new representation, decomposition algorithm for search space is given. The algorithms with one time and multi-times decomposition for the search space are given, and the simulation results are given. (6) Quantum-inspired evolutionary algorithm which uses the two values property of the new representation is given. The general structure of quantum-inspired evolutionary algorithm and the improving methods are given also. The algorithms which use one quantum solution and two quantum solutions respectively are given. The simulation results show that the ideals of this paper are correct and the algorithms given by this paper are effective.
馆藏号XWLW1287
其他标识符200218014603161
语种中文
文献类型学位论文
条目标识符http://ir.ia.ac.cn/handle/173211/6124
专题毕业生_博士学位论文
推荐引用方式
GB/T 7714
黄志宇. 一种新的项目调度解表示方法及其应用研究[D]. 中国科学院自动化研究所. 中国科学院研究生院,2008.
条目包含的文件
文件名称/大小 文献类型 版本类型 开放类型 使用许可
CASIA_20021801460316(1498KB) 暂不开放CC BY-NC-SA请求全文
个性服务
推荐该条目
保存到收藏夹
查看访问统计
导出为Endnote文件
谷歌学术
谷歌学术中相似的文章
[黄志宇]的文章
百度学术
百度学术中相似的文章
[黄志宇]的文章
必应学术
必应学术中相似的文章
[黄志宇]的文章
相关权益政策
暂无数据
收藏/分享
所有评论 (0)
暂无评论
 

除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。